Categorygithub.com/mennanov/limiters
modulepackage
0.1.1
Repository: https://github.com/mennanov/limiters.git
Documentation: pkg.go.dev
Versions
1
Dependencies
17
Dependents
3
Files
1.2k SLOC

# README

Distributed rate limiters for Golang

Build Status codecov Go Report Card GoDoc

Rate limiters for distributed applications in Golang with configurable back-ends and distributed locks.
Any types of back-ends and locks can be used that implement certain minimalistic interfaces. Most common implementations are already provided.

  • Token bucket

    • in-memory (local)
    • redis
    • etcd

    Allows requests at a certain input rate with possible bursts configured by the capacity parameter.
    The output rate equals to the input rate.
    Precise (no over or under-limiting), but requires a lock (provided).

  • Leaky bucket

    • in-memory (local)
    • redis
    • etcd

    Puts requests in a FIFO queue to be processed at a constant rate.
    There are no restrictions on the input rate except for the capacity of the queue.
    Requires a lock (provided).

  • Fixed window counter

    • in-memory (local)
    • redis

    Simple and resources efficient algorithm that does not need a lock.
    Precision may be adjusted by the size of the window.
    May be lenient when there are many requests around the boundary between 2 adjacent windows.

  • Sliding window counter

    • in-memory (local)
    • redis

    Smoothes out the bursts around the boundary between 2 adjacent windows.
    Needs as twice more memory as the Fixed Window algorithm (2 windows instead of 1 at a time).
    It will disallow all the requests in case when a client is flooding the service with requests. It's the client's responsibility to handle a disallowed request properly: wait before making a new one again.

  • Concurrent buffer

    • in-memory (local)
    • redis

    Allows concurrent requests up to the given capacity.
    Requires a lock (provided).

gRPC example

Global token bucket rate limiter for a gRPC service example:

// examples/example_grpc_simple_limiter_test.go
rate := time.Second * 3
limiter := limiters.NewTokenBucket(
    2,
    rate,
    limiters.NewLockerEtcd(etcdClient, "/ratelimiter_lock/simple/", limiters.NewStdLogger()),
    limiters.NewTokenBucketRedis(
        redisClient,
        "ratelimiter/simple",
        rate, false),
    limiters.NewSystemClock(), limiters.NewStdLogger(),
)

// Add a unary interceptor middleware to rate limit all requests.
s := grpc.NewServer(grpc.UnaryInterceptor(
    func(ctx context.Context, req interface{}, info *grpc.UnaryServerInfo, handler grpc.UnaryHandler) (resp interface{}, err error) {
        w, err := limiter.Limit(ctx)
        if err == limiters.ErrLimitExhausted {
            return nil, status.Errorf(codes.ResourceExhausted, "try again later in %s", w)
        } else if err != nil {
            // The limiter failed. This error should be logged and examined.
            log.Println(err)
            return nil, status.Error(codes.Internal, "internal error")
        }
        return handler(ctx, req)
    }))

For something close to a real world example see the IP address based gRPC global rate limiter in the examples directory.

Distributed locks

Some algorithms require a distributed lock to guarantee consistency during concurrent requests.
In case there is only 1 running application instance then no distributed lock is needed as all the algorithms are thread-safe (use LockNoop).

Supported backends:

Testing

Run tests locally:

docker-compose up -d  # start etcd and Redis
ETCD_ENDPOINTS="127.0.0.1:2379" REDIS_ADDR="127.0.0.1:6379" ZOOKEEPER_ENDPOINTS="127.0.0.1" CONSUL_ADDR="127.0.0.1:8500" go test -race -v

Run Drone CI tests locally:

for p in "go1.13" "go1.12" "go1.11" "lint"; do drone exec --pipeline=${p}; done

# Packages

# Functions

NewConcurrentBuffer creates a new ConcurrentBuffer instance.
NewConcurrentBufferInMemory creates a new instance of ConcurrentBufferInMemory.
NewConcurrentBufferRedis creates a new instance of ConcurrentBufferRedis.
NewFixedWindow creates a new instance of FixedWindow.
NewFixedWindowInMemory creates a new instance of FixedWindowInMemory.
NewFixedWindowRedis returns a new instance of FixedWindowRedis.
NewLeakyBucket creates a new instance of LeakyBucket.
NewLeakyBucketEtcd creates a new LeakyBucketEtcd instance.
NewLeakyBucketInMemory creates a new instance of LeakyBucketInMemory.
NewLeakyBucketRedis creates a new LeakyBucketRedis instance.
NewLockConsul creates a new LockConsul instance.
NewLockEtcd creates a new instance of LockEtcd.
NewLockNoop creates a new LockNoop.
NewLockZookeeper creates a new instance of LockZookeeper.
NewRegistry creates a new instance of Registry.
NewSlidingWindow creates a new instance of SlidingWindow.
NewSlidingWindowInMemory creates a new instance of SlidingWindowInMemory.
NewSlidingWindowRedis creates a new instance of SlidingWindowRedis.
NewStdLogger creates a new instance of StdLogger.
NewSystemClock creates a new instance of SystemClock.
NewTokenBucket creates a new instance of TokenBucket.
NewTokenBucketEtcd creates a new TokenBucketEtcd instance.
NewTokenBucketInMemory creates a new instance of TokenBucketInMemory.
NewTokenBucketRedis creates a new TokenBucketRedis instance.

# Variables

ErrLimitExhausted is returned by the Limiter in case the number of requests overflows the capacity of a Limiter.
ErrRaceCondition is returned when there is a race condition while saving a state of a rate limiter.

# Structs

ConcurrentBuffer implements a limiter that allows concurrent requests up to the given capacity.
ConcurrentBufferInMemory is an in-memory implementation of ConcurrentBufferBackend.
ConcurrentBufferRedis implements ConcurrentBufferBackend in Redis.
FixedWindow implements a Fixed Window rate limiting algorithm.
FixedWindowInMemory is an in-memory implementation of FixedWindowIncrementer.
FixedWindowRedis implements FixedWindow in Redis.
LeakyBucket implements the https://en.wikipedia.org/wiki/Leaky_bucket#As_a_queue algorithm.
LeakyBucketEtcd is an etcd implementation of a LeakyBucketStateBackend.
LeakyBucketInMemory is an in-memory implementation of LeakyBucketStateBackend.
LeakyBucketRedis is a Redis implementation of a LeakyBucketStateBackend.
LeakyBucketState represents the state of a LeakyBucket.
LockConsul is a wrapper around github.com/hashicorp/consul/api.Lock that implements the DistLocker interface.
LockEtcd implements the DistLocker interface using etcd.
LockNoop is a no-op implementation of the DistLocker interface.
LockZookeeper is a wrapper around github.com/samuel/go-zookeeper/zk.Lock that implements the DistLocker interface.
Registry is a garbage-collectable registry of values.
SlidingWindow implements a Sliding Window rate limiting algorithm.
SlidingWindowInMemory is an in-memory implementation of SlidingWindowIncrementer.
SlidingWindowRedis implements SlidingWindow in Redis.
StdLogger implements the Logger interface.
SystemClock implements the Clock interface by using the real system clock.
TokenBucket implements the https://en.wikipedia.org/wiki/Token_bucket algorithm.
TokenBucketEtcd is an etcd implementation of a TokenBucketStateBackend.
TokenBucketInMemory is an in-memory implementation of TokenBucketStateBackend.
TokenBucketRedis is a Redis implementation of a TokenBucketStateBackend.
TokenBucketState represents a state of a token bucket.

# Interfaces

Clock encapsulates a system Clock.
ConcurrentBufferBackend wraps the Add and Remove methods.
DistLocker is a context aware distributed locker (interface is similar to sync.Locker).
FixedWindowIncrementer wraps the Increment method.
LeakyBucketStateBackend interface encapsulates the logic of retrieving and persisting the state of a LeakyBucket.
Logger wraps the Log method for logging.
SlidingWindowIncrementer wraps the Increment method.
TokenBucketStateBackend interface encapsulates the logic of retrieving and persisting the state of a TokenBucket.