hilts-vaughan / distributed-token-bucket

A small library for creating persistence-backed token buckets with Redis and Golang

Distributed Token Bucket with Redis and Golang

The token bucket algorithm is useful for things like rate-limiting and network congestion control.

Normally token buckets are implemented in-memory which is helpful for high performance applications. But what happens if you need rate limiting across a distributed system?

This library attempts to solve said problem by utilizing Redis as the token broker powering the token bucket. Redis is particularly good at this because of it's relatively high level of performance and concurrency control via its single-threaded runtime.

Install

go get github.com/b3ntly/distributed-token-bucket

Basic Usage

package main

import (
    tb "github.com/b3ntly/distributed-token-bucket
    "github.com/go-redis/redis"
)

func main(){
    storageOptions = &redis.Options{
        Addr:     "127.0.0.1:6379",
        Password: "", // no password set
        DB:       1,  // use default DB
    }
    
    // initialize a bucket with 5 tokens
    bucket, err = tb.NewBucket(key, 5, storageOptions)
    
    // take 5 tokens
    err := bucket.Take(5)
    
    // try to take 5 tokens, this will return an error as there are not 5 tokens in the bucket
    err = bucket.Take(5)
    // err.Error() => "Insufficient tokens."
    
    // put 5 tokens back into the bucket
    err = bucket.Put(5)
    
    // wait for at least 10 tokens to be in the bucket (currently 5)
    done = bucket.Watch(10)
    
    // put 5 tokens into the bucket
    err = bucket.Put(5)
    
    // listen for bucket.Watch to return via the returned channel
    err = <- done
    
    // (err == nil)
}

Notes

• Test coverage badge is stuck in some cache and is out of date, click the badge to see the actual current coverage

Examples

http-server

Benchmarks

These benchmarks are fairly incomplete due to a couple of reasons:

• Currently each instance of a bucket gets it's own redis.Client instance which do not pool or share connections between them. This is really inefficient when creating large numbers of buckets.

• Most operations in this library are singular redis operations meaning the benchmark themselves are almost entirely pinned to the performance of Redis which is dominated by whatever network latencies present between the instance and whatever process is utilizing this library.

Benchmark	Operations	ns/op
BenchmarkBucket_Create-8	10000	139613
BenchmarkBucket_Take-8	30000	40868
BenchmarkBucket_Put-8	50000	29234