A concurrent rate limiter library for Golang based on Sliding-Window rate limiter algorithm.

Overview

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.

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.

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 NewLimiter() 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.NewLimiter(
		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))
}

Attribute based rate-limiter:

Attribute based rate-limiter can hold multiple rate-limiters with different configurations in a map of type. Each limiter is uniquely identified by a key. Calling NewAttributeBasedLimiter() will create an empty rate limiter with no entries.

func AttributeRateLimiter() {
	/*
		Attribute based rate-limiter can hold multiple
		rate-limiters with different configurations in a map
		of 
   
     type. Each limiter is uniquely identified
   
		by a key. Calling NewAttributeBasedLimiter() will create an empty
		rate limiter with no entries.
	*/
	limiter := ratelimiter.NewAttributeBasedLimiter()

	/*
		Now we are adding a new entry to the limiter, we pass:
			key: A string that is used to uniquely identify the rate-limiter.
			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.

		returns error if the key already exists in the map.
	*/
	// we have two articles here (for example)
	article_ids := []string{"article_id=10", "article_id=11"}

	// for article_id=10, allow 10 tasks/items per every second
	err := limiter.CreateNewKey(&article_ids[0], 10, 5*time.Second)
	if err != nil {
		log.Fatalln(err)
	}
	// for article_id=11, allow 100 tasks/items per every 6 minutes
	err = limiter.CreateNewKey(&article_ids[1], 100, 6*time.Minute)
	if err != nil {
		log.Fatalln(err)
	}
	// rates can be checked by passing key and N as parameters
	// Can I make 8 requests to article_id=10 during this time window?

	// ShouldAllow(key *string, N uint64) returns (bool, error)
	// the bool is true/false, true if it can be allowed
	// false if it cant be allowed.
	// error if key is not found.

	fmt.Println(limiter.ShouldAllow(&article_ids[0], 8))
	// Can I make 104 requests to article_id=11 during this time window?
	fmt.Println(limiter.ShouldAllow(&article_ids[0], 104))

	/*
		Other functions:
			1. HasKey: to check if the attribute already has given key
			   call: HasKey(key string) function.
			   Example: limiter.HasKey(&article_id[0])
			   Returns a bool, true if exists, false otherwise

			2. DeleteKey: to remove the key from attribute map
			   call: DeleteKey(key string) function.
			   Example: limiter.DeleteKey(&article_id[1])
			   Returns an error, if key was not in the map.
	*/
}

Testing

Tests are written in attribute_limiter_test.go and limiter_test.go files. To execute the tests, simply run:

go test ./ -v

These are some of the results from tests:

  1. Single goroutine, Generic limiter: This test configures the rate-limiter to allow 100 requests/sec and fires 500 requests/sec with a time gap of 2ms each, allowed requests are counted and is tested with difference +/- 3. The same test is run for 10 samples. Here are the results:
=== RUN   TestLimiterAccuracy
Iteration 1, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 2, Allowed tasks: 101, passed rate limiting accuracy test.
Iteration 3, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 4, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 5, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 6, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 7, Allowed tasks: 101, passed rate limiting accuracy test.
Iteration 8, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 9, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 10, Allowed tasks: 100, passed rate limiting accuracy test.
--- PASS: TestLimiterAccuracy (10.01s)
  1. 4 goroutines, Generic Limiter: This test configures the limiter to allow 100 requests/sec and spins up 4 goroutines, the same limiter is shared across all the routines. Each goroutine generates 500 requests/sec with 2ms time gap between 2 requests. Allowed requests are counted per each goroutine, the result sum of all counts should be almost equal to 100. The accuracy is measured considering +/- 3 as error offset. The same test is conducted 10 times. Here are the results:
=== RUN   TestConcurrentLimiterAccuracy
Iteration 1, Allowed tasks: 101, passed rate limiting accuracy test.
Iteration 2, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 3, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 4, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 5, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 6, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 7, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 8, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 9, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 10, Allowed tasks: 100, passed rate limiting accuracy test.
--- PASS: TestConcurrentLimiterAccuracy (10.01s)
  1. 2 goroutines, 2 attribute keys, Attribute based limiter: An attribute based limiter is created with 2 keys, these keys are configured to allow 100 requests/sec and 123 requests/sec respectively. Two goroutines are created and same attribute based limiter is shared across. Each goroutine produces 500 requests/sec per key. The overall count is then verified for each goroutine with error offset of +/- 3. Here are the results:
=== RUN   TestAttributeBasedLimiterAccuracy
Iteration 1, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 1, Allowed tasks: 123, passed rate limiting accuracy test.
Iteration 2, Allowed tasks: 101, passed rate limiting accuracy test.
Iteration 2, Allowed tasks: 124, passed rate limiting accuracy test.
Iteration 3, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 3, Allowed tasks: 123, passed rate limiting accuracy test.
Iteration 4, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 4, Allowed tasks: 123, passed rate limiting accuracy test.
Iteration 5, Allowed tasks: 100, passed rate limiting accuracy test.
Iteration 5, Allowed tasks: 123, passed rate limiting accuracy test.
--- PASS: TestAttributeBasedLimiterAccuracy (5.00s)

Code coverage: To generate code coverage report, execute:

go test -coverprofile=c.out

This should print the following after running all the tests.

coverage: 98.6% of statements
ok      github.com/Narasimha1997/ratelimiter    25.099s

You can also save the results as HTML for more detailed code view of the coverage.

go tool cover -html=c.out -o coverage.html

This will generate a file called coverage.html. The coverage.html is provided in the repo which is pre-generated.

Notes on test:

The testing code produces 500 requests/sec with 2ms precision time gap between each request. The accuracy of this 2ms time tick generation can differ from platform to platform, even a small difference of 500 micorseconds can add up together and give more time for test to run in the end because of clock drift, as a result the error offset +/- 3 might not always work. On Windows for example, the 2ms precision time ticks can be inconsistent because the windows scheduler wakes up every 15ms causing a drift in the clock time, however Linux based distros have precise timers that allow us to obtain precise 2ms time tikcs.

Contributing

Feel free to raise issues, make pull requests or suggest new features.

Issues
  • How does this differ from golang.org/x/time/rate?

    How does this differ from golang.org/x/time/rate?

    https://pkg.go.dev/golang.org/x/time/rate is a popular rate-limiter. How does this package differ from that? Would it make sense to write a paragraph about this in the README? ๐Ÿค”

    opened by JensRantil 3
  • The possible problems and optimization of the attribute-based speed limiter

    The possible problems and optimization of the attribute-based speed limiter

    Hi,

    Suppose you use ratelimiter to build a web middleware based on IP current limiting.

    Using NewAttributeBasedLimiter, each IP uses limiter.CreateNewKey, so it is easy to appear a large number of progressiveWindowSlider coroutines, each coroutine only serves its own IP.

    limiter.CreateNewKey(req.RemoteAddr, 20, 1*time.Second)
    

    https://github.com/Narasimha1997/ratelimiter/blob/31364b3bcf38d4a570d29e8f73f64348b69510af/limiter.go#L94

    Is it possible to use only one progressiveWindowSlider coroutine? For example, is it better to align all WindowSliders with the time scale of 0.1*size, and slide all windows uniformly in the form of a time wheel?

    And there is no automatic cleaning mechanism, there will be a large number of invalid progressiveWindowSlider coroutines.

    opened by fufuok 3
Releases(v1.1.0)
  • v1.1.0(Oct 10, 2021)

    Adds new functions and test cases for these.

    1. func (a *AttributeBasedLimiter) MustShouldAllow(key string, n uint64, limit uint64, size time.Duration) bool
    2. func (a *AttributeBasedLimiter) HasOrCreateKey(key string, limit uint64, size time.Duration) bool

    Thanks @fufuok for these contributions.

    Source code(tar.gz)
    Source code(zip)
  • v1.0.0(Oct 3, 2021)

    Releasing the first initial stable version of rate-limiter. New additions:

    1. SyncLimiter : A new limiter implementation that require no goroutine in the background to maintain the sliding window.
    2. More tests that cover SyncLimiter.
    3. AttrubuteBasedLimiter can be configured to use DefaultLimiter and SyncLimiter by passing backgroundSlider flag.
    4. Added docs
    Source code(tar.gz)
    Source code(zip)
  • v0.3.0(Sep 30, 2021)

    New things:

    1. Added test coverage
    2. Fixed an issue that could probably cause deadlock when Kill() is called.
    3. AttributeBasedRateLimiter not accepts string as paramter across various functions instead of *string.
    Source code(tar.gz)
    Source code(zip)
  • v0.2.0(Sep 30, 2021)

    Additions:

    1. Now we can call defer limiter.Kill() to clean up or deactivate the limiter when it is not in use anymore. This will also kill the underlying goroutine and avoids resource leak.
    2. limiter.ShouldAllow(N uint64) now returns bool, error. error is not nil if ShouldAllow is called on a limiter that is killed or inactive.
    Source code(tar.gz)
    Source code(zip)
  • v0.1.2(Sep 29, 2021)

Owner
Narasimha Prasanna HN
๐Ÿง”Human | Indian | Programmer | Full Stack Developer | AI Engineer
Narasimha Prasanna HN
Scalable golang ratelimiter using the sliding window algorithm. Currently supports only Redis.

go-ratelimiter Scalable golang ratelimiter using the sliding window algorithm. Currently supports only Redis. Example usage client := redis.NewClient

null 0 Oct 19, 2021
A simple business indicator tool that uses a sliding window to detect whether the indicator exceeds the threshold

melon A simple business indicator tool that uses a sliding window to detect whether the indicator exceeds the threshold Usage //create the metric //th

believe 4 Jul 11, 2021
A simple thread-safe, fixed size LRU written in Go. Based on dominictarr's Hashlru Algorithm. ๐Ÿ”ƒ

go-hashlru A simple thread-safe, fixed size LRU written in Go. Based on dominictarr's Hashlru Algorithm. ?? Uses map[interface{}]interface{} to allow

Saurabh Pujari 70 Jul 3, 2022
a thread-safe concurrent map for go

concurrent map As explained here and here, the map type in Go doesn't support concurrent reads and writes. concurrent-map provides a high-performance

Or Hiltch 3.2k Aug 8, 2022
A concurrent Download Manager written in Go

golang-download-manager A concurrent Download Manager written in Go Changes In main.go file paste the file url in fileUrl variable paste the path for

Sabuj Jana 2 May 4, 2022
A thread-safe concurrent map for go

concurrent map Original repo didn't support go mod and no any tags,so I forkd this repo add go mod support and patch a tag on this repo. No any code c

Yusan Kurban 0 Dec 7, 2021
Leftright - A concurrent map that is optimized for scenarios where reads are more frequent than writes

leftright A concurrent map that is optimized for scenarios where reads are more

Yang Pan 1 Jan 30, 2022
golang implement gossip algorithm

golang implement gossip algorithm

Gabriella Munger 3 Jan 14, 2022
A faster RWLock primitive in Go, 2-3 times faster than RWMutex. A Go implementation of concurrency control algorithm in paper

Go Left Right Concurrency A Go implementation of the left-right concurrency control algorithm in paper <Left-Right - A Concurrency Control Technique w

wangyi 40 Apr 4, 2022
EVM-compatible chain secured by the Lachesis consensus algorithm.

ICICB-Galaxy EVM-compatible chain secured by the Lachesis consensus algorithm. Building the source Building galaxy requires both a Go (version 1.14 or

null 2 Oct 7, 2021
The main goal of this code is to create a basic dnstap printing tool based on the golang-dnstap library.

dnstap-parse The main goal of this code is to create a basic dnstap printing tool based on the golang-dnstap library. The output is supposed to mimic

Patrik Lundin 1 Nov 14, 2021
go generate based graphql server library

gqlgen What is gqlgen? gqlgen is a Go library for building GraphQL servers without any fuss. gqlgen is based on a Schema first approach โ€” You get to D

99designs 7.8k Aug 2, 2022
A Golang tool to whitelist ASN's based on organization name

A Golang tool to whitelist ASN's based on organization name. This works by providing a list of ASN org names. This tool uses goPacket to monitor incoming traffic, capturing the IP's and checking the IP to see if it is a part of a whitelisted ASN. If it is not, it blocks that connection and future connections using iptables.

JP 14 Jul 23, 2022
ptypes is a pointer-based box typing system for golang.

ptypes bypass go's type system through unsafe pointers the paradigm is to created a "boxed" type with .From and then use whatever types we want by ass

prequist 3 Aug 26, 2021
GoLang-based client-side circuit breakers and helpers

Overview Example library for circuit breaking in GoLang. Written to support a blog post on https://www.wojno.com. Use this library in your SDK's to pr

Chris Wojno 0 Dec 5, 2021
Goridge is high performance PHP-to-Golang codec library which works over native PHP sockets and Golang net/rpc package.

Goridge is high performance PHP-to-Golang codec library which works over native PHP sockets and Golang net/rpc package. The library allows you to call Go service methods from PHP with a minimal footprint, structures and []byte support.

Spiral Scout 1.1k Aug 5, 2022
Fast, scalable pseudo random number generator based on xxh3

XXH3-Based Pseudorandom Number Generator This package contains an experimental implementation of a noise based pseudorandom number generator that scal

Roman Atachiants 6 Nov 7, 2021
Script Based Alerting Manager

A Project in active development. Features may have breaking changes at any time before v1.0.0 version Telegram Group Balerter is a scripts based alert

Balerter 273 Jul 30, 2022
Daypaper sets your GNOME wallpaper based on the time of day from a random and relevant Unsplash image.

Daypaper Daypaper sets your GNOME wallpaper based on the time of day from a random and relevant Unsplash image. Installation You will need an Access T

Matteo Guglielmetti 15 May 23, 2022