Skip to content

Instantly share code, notes, and snippets.

@xeoncross
Created June 20, 2022 20:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save xeoncross/3f1b6c01a0ab0eb6cb3743c62b30f5e6 to your computer and use it in GitHub Desktop.
Save xeoncross/3f1b6c01a0ab0eb6cb3743c62b30f5e6 to your computer and use it in GitHub Desktop.
Distributed rate limiting with non-whole time periods (max 3 requests every 5 seconds)

Rate Limiting Redis with multiples of a time.Duration

In a distributed system, you want the API layer to be stateless. So the app can offload rate limiting to a redis instance. This way, you can use the INCR to both increment and return the number of requests a given IP/Client/API Key has made across any number of App / serverless instances.

However, what do you do if the limit isn't roundable to the current second/minute/hour/day? How does each instance agree which key to use? The answer is to modulo the previous and future keys to find the right one.

For example, 3 requests every 5 seconds is the desired limit. That means we can use -max-1:+max-1 as the range of values to scan to find the key we should use.

max := 5

	// Pretent we are fetching keys every second over the next minute
	for second := 0; second < 60; second++ {

		var key int
		for i := second - (max - 1); i < second+(max-1); i++ {
			if i%max == 0 {
				// first value is the correct key, some positions have two matches
				key = i
				break
			}
		}

		fmt.Printf("%2d: key: %2d\n", second, key)
	}

demo here

This solves the problem of trying to collect data from multiple keys as is often down with a sliding window where there might be multiple keys or a list of timestamps which need to be cleaned and appended to.

@xeoncross
Copy link
Author

The math is timestamp -= timestamp % duration. So 1234 rounded to every 10 seconds would be 1234 -= 1234%10 which is 1230.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment