codel

README

codel

codel implements the Controlled Delay algorithm for overload detection, providing a mechanism to shed load when overloaded. It optimizes for latency while keeping throughput high, even when downstream rates dynamically change.

codel keeps latency low when even severely overloaded, by preemptively shedding some load when wait latency is long. It is comparable to using a queue to handle bursts of load, but improves upon this technique by avoiding the latency required to handle all previous entries in the queue.

In a simulation of 1000 reqs/sec incoming, 500 reqs/sec outgoing averages for 10 seconds, here's the corresponding throughput and latency profile of both a queue and codel. Throughput is slightly higher than the average due to randomness in the simulation.

method	throughput	p50	p95	p99
queue	507.41	963.604953ms	1.024595796s	1.041455537s
codel	513.17	27.718827ms	44.085795ms	62.756499ms

Source code for the simulations are included in the sim directory.

Installation

$ go get github.com/bohde/codel

Example

import (
    "context"
    "github.com/bohde/codel"
)

func Example() {
	c := codel.New(codel.Options{
		// The maximum number of pending acquires
		MaxPending: 100,
		// The maximum number of concurrent acquires
		MaxOutstanding: 10,
		// The target latency to wait for an acquire.
		// Acquires that take longer than this can fail.
		TargetLatency: 5 * time.Millisecond,
	})

	// Attempt to acquire the lock.
	err := c.Acquire(context.Background())

	// if err is not nil, acquisition failed.
	if err != nil {
		return
	}

	// If acquisition succeeded, we need to release it.
	defer c.Release()

	// Do some process with external resources
}

Benchmarks

The Lock serializes access, introducing latency overhead. When not overloaded, this overhead should be under 1us.

BenchmarkLockUnblocked-4        20000000                73.1 ns/op             0 B/op          0 allocs/op
BenchmarkLockBlocked-4           2000000               665 ns/op             176 B/op          2 allocs/op

Documentation

Overview

Package codel implements the Controlled Delay (https://queue.acm.org/detail.cfm?id=2209336) algorithm for overload detection, providing a mechanism to shed load when overloaded. It optimizes for latency while keeping throughput high, even when downstream rates dynamically change. It keeps latency low when even severely overloaded, by preemptively shedding some load when wait latency is long. It is comparable to using a queue to handle bursts of load, but improves upon this technique by avoiding the latency required to handle all previous entries in the queue.

Example

c := New(Options{
	// The maximum number of pending acquires
	MaxPending: 100,
	// The maximum number of concurrent acquires
	MaxOutstanding: 10,
	// The target latency to wait for an acquire.
	// Acquires that take longer than this can fail.
	TargetLatency: 5 * time.Millisecond,
})

// Attempt to acquire the lock.
err := c.Acquire(context.Background())

// if err is not nil, acquisition failed.
if err != nil {
	return
}

// If acquisition succeeded, we need to release it.
defer c.Release()

// Do some process with external resources

Index

• Variables
• type Lock
  • func New(opts Options) *Lock
  • func (l *Lock) Acquire(ctx context.Context) error
  • func (l *Lock) Release()
• type Options
• type PLock
  • func NewPriority(opts Options) *PLock
  • func (l *PLock) Acquire(ctx context.Context, priority int) error
  • func (l *PLock) Release()

Examples

• Package

Variables

var Dropped = errors.New("dropped")

Dropped is the error that will be returned if this token is dropped

Types

type Lock

type Lock struct {
	// contains filtered or unexported fields
}

Lock implements a FIFO lock with concurrency control, based upon the CoDel algorithm (https://queue.acm.org/detail.cfm?id=2209336).

func New

func New(opts Options) *Lock

func (*Lock) Acquire

func (l *Lock) Acquire(ctx context.Context) error

Acquire a Lock with FIFO ordering, respecting the context. Returns an error it fails to acquire.

func (*Lock) Release

func (l *Lock) Release()

Release a previously acquired lock.

type Options

type Options struct {
	MaxPending     int           // The maximum number of pending acquires
	MaxOutstanding int           // The maximum number of concurrent acquires
	TargetLatency  time.Duration // The target latency to wait for an acquire. Acquires that take longer than this can fail.
}

Options are options to configure a Lock.

type PLock

type PLock struct {
	// contains filtered or unexported fields
}

PLock implements a FIFO lock with concurrency control and priority, based upon the CoDel algorithm (https://queue.acm.org/detail.cfm?id=2209336).

func NewPriority

func NewPriority(opts Options) *PLock

func (*PLock) Acquire

func (l *PLock) Acquire(ctx context.Context, priority int) error

Acquire a PLock with FIFO ordering, respecting the context. Returns an error it fails to acquire.

func (*PLock) Release

func (l *PLock) Release()

Release a previously acquired lock.