ratelimiter

A generic concurrent rate limiter library for Golang based on Sliding-window rate limitng algorithm.

The implementation of rate-limiter algorithm is based on Scalable Distributed Rate Limiter algorithm used in Kong API gateway. Read this blog for more details.

This library can be used in your codebase to rate-limit literally anything. For example, you can integrate this library to provide rate-limiting for your REST/gRPC APIs or you can use this library to rate-limit the number of go-routines spawned or number of tasks submitted to a function/module per given time interval. This library provides generic rate check APIs that can be used anywhere. The library is built with concurrency in mind from the groud up, the rate-limiter can be used across go-routines without having to worry about synchronization issues. This library also provides capability to create and manage multiple rate-limiters with different configurations assiociated with unique keys.

How is this different from Go's official rate package?

The official Go package provides a rate limiter implementation which uses Token Bucket Algorithm. This repository (i.e the current repository) implements rate limiting functionalities using Sliding Window Rate Limiting Algorithm as used in Kong API gateway. Both of these libraries provide the same functionality, but there are trade-offs between these two algorithms, this blog properly explains these trade-offs. Understand the trade-offs and match them with your requirements to decide which algorithm to use.

Installation:

The package can be installed as a Go module.

go get github.com/Narasimha1997/ratelimiter

Using the library:

There are two types of rate-limiters used.

All APIs:

1. Generic rate-limiter:

	/* creates an instance of DefaultLimiter and returns it's pointer.
	   Parameters:
	 		limit: The number of tasks to be allowd
			size: duration
	*/
	func NewDefaultLimiter(limit uint64, size time.Duration) *DefaultLimiter

	/*
		Kill the limiter, returns error if the limiter has been killed already.
	*/
	func (s *DefaultLimiter) Kill() error

	/*
		Makes decison whether n tasks can be allowed or not.
		Parameters:
			n: number of tasks to be processed, set this as 1 for a single task. 
				(Example: An HTTP request)
		Returns (bool, error),
			if limiter is inactive (or it is killed), returns an error
			the boolean flag is either true - i.e n tasks can be allowed or false otherwise.
	*/
	func (s *DefaultLimiter) ShouldAllow(n uint64) (bool, error)

	/*
		Kill the limiter, returns error if the limiter has been killed already.
	*/
	func (s *DefaultLimiter) Kill() error	

2. On-demand rate-limiter

	/*  creates an instance of SyncLimiter and returns it's pointer.
	 	Parameters:
	 		limit: The number of tasks to be allowd
			size: duration
	*/
	func NewSyncLimiter(limit uint64, size time.Duration) *SyncLimiter

	/*
		Kill the limiter, returns error if the limiter has been killed already.
	*/
	func (s *SyncLimiter) Kill() error

	/*
		Makes decison whether n tasks can be allowed or not.
		Parameters:
			n: number of tasks to be processed, set this as 1 for a single task. 
				(Example: An HTTP request)
		Returns (bool, error),
			if limiter is inactive (or it is killed), returns an error
			the boolean flag is either true - i.e n tasks can be allowed or false otherwise.
	*/
	func (s *SyncLimiter) ShouldAllow(n uint64) (bool, error)

	/*
		Kill the limiter, returns error if the limiter has been killed already.
	*/
	func (s *SyncLimiter) Kill() error

3. Attribute based Rate Limiter

	/*
		Creates an instance of AttributeBasedLimiter and returns it's pointer.
		Parameters:
			backgroundSliding: if set to true, DefaultLimiter will be used as an underlying limiter.
							   else, SyncLimiter will be used.
	*/
	func NewAttributeBasedLimiter(backgroundSliding bool) *AttributeBasedLimiter

	/*
		Check if AttributeBasedLimiter has a limiter for the key.
		Parameters:
			key: a unique key string, example: IP address, token, uuid etc
		Returns a boolean flag, if true, the key is already present, false otherwise.
	*/
	func (a *AttributeBasedLimiter) HasKey(key string) bool

	/*
		Create a new key-limiter assiociation.
		Parameters:
			key: a unique key string, example: IP address, token, uuid etc
			limit: The number of tasks to be allowd
			size: duration
		Returns error if the key already exist.
	*/

	func (a *AttributeBasedLimiter) CreateNewKey(
		key string, limit uint64, 
		size time.Duration,
	) error

	/* 
	   check if AttributeBasedLimiter has a limiter for the key.
	   Create a new key-limiter assiociation if the key not exists.
	   Parameters:
	    key: a unique key string, example: IP address, token, uuid etc.
		limit: The number of tasks to be allowd
		size: duration
		Return true if the key exists or is created successfully.
	*/
	func (a *AttributeBasedLimiter) HasOrCreateKey(key string, limit uint64, size time.Duration);

	/*
		Makes decison whether n tasks can be allowed or not.
		Parameters:
			key: a unique key string, example: IP address, token, uuid etc
			n: number of tasks to be processed, set this as 1 for a single task. 
				(Example: An HTTP request)
		Returns (bool, error),
			if limiter is inactive (or it is killed) or key is not present, returns an error
			the boolean flag is either true - i.e n tasks can be allowed or false otherwise.
	*/
	func (a *AttributeBasedLimiter) ShouldAllow(key string, n uint64) (bool, error)

	/* 
		MustShouldAllow makes decison whether n tasks can be allowed or not.
		Creates a new key if it does not exist.
		Parameters:
			key: a unique key string, example: IP address, token, uuid etc
			n: number of tasks to be processed, set this as 1 for a single task.
			(Example: An HTTP request)
			limit: The number of tasks to be allowd
			size: duration

		Returns bool.
			(false) when limiter is inactive (or it is killed) or n tasks can be not allowed.
			(true) when n tasks can be allowed or new key-limiter.
	*/
	func (a *AttributeBasedLimiter) MustShouldAllow(key string, n uint64, limit uint64, size time.Duration) bool

	/*
		Remove the key and kill its underlying limiter.
		Parameters:
			key: a unique key string, example: IP address, token, uuid etc
		Returns an error if the key is not present.
	*/
	func (a *AttributeBasedLimiter) DeleteKey(key string) error

Examples and Explanation of each type of rate-limiter:

Generic rate-limiter

The generic rate-limiter instance can be created if you want to have a single rate-limiter with single configuration for everything. The generic rate-limiter can be created by calling NewDefaultLimiter() function and by passing the limit and size as parameters. Example:

func GenericRateLimiter() {
	/* create an instance of Limiter.
	format: NewLimiter(limit uint64, size time.Duration),
	where:
		limit: The number of tasks/items that should be allowed.
		size: The window size, i.e the time interval during which the limit
				should be imposed.
		To summarize, if limit = 100 and duration = 5s, then allow 100 items per 5 seconds
	*/

	limiter := ratelimiter.NewDefaultLimiter(
		100, time.Second*5,
	)

	/*
		Cleaning up the limiter: Once the limiter is no longer required,
		the underlying goroutines and resources used by the limiter can be cleaned up.
		This can be done using:
			limiter.Kill(),
		Returns an error if the limiter is already being killed.
	*/

	defer limiter.Kill()

	/*
		the limiter provides ShouldAllow(N uint64) function which
		returns true/false if N items/tasks can be allowed during current
		time interval.

		An error is returned if the limiter is already killed.
	*/

	// ShouldAllow(N uint64) -> returns bool, error

	// should return true
	fmt.Println(limiter.ShouldAllow(60))
	// should return false, because (60 + 50 = 110) > 100 during this window
	fmt.Println(limiter.ShouldAllow(50))
	// sleep for some time
	time.Sleep(5 * time.Second)
	// should return true, because the previous window has been slided over
	fmt.Println(limiter.ShouldAllow(20))
}

On demand window sliding:

The previous method i.e the Generic Rate limiter spins up a background goroutine that takes care of sliding the rate-limiting window whenever it's size expires, because of this, rate-limiting check function ShouldAllow has fewer steps and takes very less time to make decision. But if your application manages a large number of Limiters, for example a web-server that performs rate-limiting across hundreds of different IPs, then your AttributeBasedRateLimiter spins up a goroutine for each unique IP and thus lot of such routines needs to be manitanied, this might induce scheduling pressure.

An alternative solution is to use a rate-limiter does not require a background routine, instead the window is sliding is taken care by ShouldAllow function itself, this method can be used to maintain large number of rate limiters without any scheduling pressure. This limiter is called SyncLimiter and can be used just like DefaultLimiter, because SyncLimiter and DefaultLimiter are built on top of the same Limiter interface. To use this, just replace NewDefaultLimiter with NewSyncLimiter

......

	limiter := ratelimiter.NewSyncLimiter(
		100, time.Second*5,
	)
......

Attribute based rate-limiter:

Attribute based rate-limiter can hold multiple rate-limiters with different