limiters

Algorithms that require consistency during concurrent requests need a distributed lock. If your application runs as a single instance, you can use LockNoop as all algorithms are thread-safe.

Supported distributed lock backends include:

• etcd
• Consul
• Zookeeper
• Redis
• Memcached
• PostgreSQL

Use the provided Makefile commands to run the project's test suite and benchmarks locally:

• Run tests: make test
• Run benchmarks: make benchmark
• Run both: make

To use Azure Cosmos DB for NoSQL, you must create a database and a container beforehand.

Requirements:

• The container must have a default TTL set; otherwise, the TTL functionality will not work.
• The partition key must be set to /partitionKey.

The FixedWindowIncrementer interface defines how the request counter is incremented for a specific time window. This allows the rate limiter to work in both single-node and distributed environments.

Available implementations:

• FixedWindowInMemory: For single-process, in-memory limiting.
• FixedWindowRedis: Uses a Redis client (redis.UniversalClient) and a key prefix.
• FixedWindowMemcached: Uses a Memcached client (*memcache.Client) and a key prefix.
• FixedWindowDynamoDB: Uses an AWS DynamoDB client (*dynamodb.Client). Requires a table with a SortKey and TTL enabled.
• FixedWindowCosmosDB: Uses an Azure Cosmos DB client (*azcosmos.ContainerClient).

Using DynamoDB requires a pre-existing table. Depending on the algorithm used, the table must have specific attributes:

• Partition Key: String (Required for all backends)
• Sort Key: String (Required for FixedWindow and SlidingWindow)
• TTL: Number (Required for FixedWindow, SlidingWindow, LeakyBucket, and TokenBucket)

You can provide a DynamoDBTableProperties struct manually or use LoadDynamoDBTableProperties(tableName) to fetch and verify the table configuration from AWS. Results from LoadDynamoDBTableProperties are cached.

The SlidingWindow algorithm calculates a weighted total of requests based on the current and previous windows.

1. It calls Increment on the backend to get the count for the prev and curr windows.
2. It calculates the total using the formula: total = (prev * ttl / rate) + curr, where ttl is the time remaining in the current window.
3. If total - capacity >= epsilon, the limit is exhausted.
4. The Limit method returns the time.Duration the client should wait before retrying. If the request is allowed, it returns 0, nil.

The DistLocker interface provides a context-aware mechanism for distributed locking, similar to Go's sync.Locker. It is used to coordinate access to shared resources across multiple distributed instances. Implementations include support for Etcd, Consul, Zookeeper, Redis, Memcached, and PostgreSQL.

To use a distributed lock, call Lock(ctx) to acquire the lock and Unlock(ctx) to release it. Always ensure Unlock is called (ideally via defer) to prevent deadlocks.

// Example of using a DistLocker
err := locker.Lock(ctx)
if err != nil {
    return err
}
defer locker.Unlock(ctx)

// Perform protected operation

The TokenBucketStateBackend interface is used to persist the TokenBucketState (which contains Last timestamp and Available token count). This allows the rate limiter to work across multiple distributed instances.

Available implementations include:

• TokenBucketInMemory: Non-persistent, local to the instance.
• TokenBucketEtcd: Uses etcd for storage.
• TokenBucketRedis: Uses Redis for storage (supports a new JSON format and an old multi-key format).
• TokenBucketMemcached: Uses Memcached.
• TokenBucketDynamoDB: Uses AWS DynamoDB.
• TokenBucketCosmosDB: Uses Azure Cosmos DB for NoSQL.

The project provides a docker-compose.yml file containing various backend services used for testing distributed rate limiters. You can use this file to spin up local instances of supported storage backends like Redis, Etcd, DynamoDB, and Cosmos DB emulator.

docker-compose up