Go implementation of the Controlled Delay algorithm
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
cmd/sim
stats
.travis.yml
CODE_OF_CONDUCT.md
LICENSE
README.md
codel.go
codel_test.go

README.md

codel

Build Status GoDoc

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/joshbohde/codel

Example

import (
    "context"
    "github.com/joshbohde/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