Understanding the default limiter

[patrickjane]

I created a limiter like this:

self.limiterGlobal = ratelimiter.NewDefaultLimiter(10, time.Minute)

And in the middleware of my HTTP server I am doing this:

allowed, _ = self.limiterGlobal.ShouldAllow(1)

// if allowed return HTTP200, otherwise HTTP429

Then I fired curl requests in a loop in the console, with 1s pause.

Expected result:
It will allow the first 10 requests, then block further requests until 1 minute has passed, then every second another request will be allowed.

Actual result:

---------
Di 1. Nov 14:47:23 CET 2022
200
---------
Di 1. Nov 14:47:24 CET 2022
200
---------
Di 1. Nov 14:47:25 CET 2022
200
---------
Di 1. Nov 14:47:26 CET 2022
200
---------
Di 1. Nov 14:47:27 CET 2022
200
---------
Di 1. Nov 14:47:28 CET 2022
200
---------
Di 1. Nov 14:47:29 CET 2022
200
---------
Di 1. Nov 14:47:30 CET 2022
200
---------
Di 1. Nov 14:47:31 CET 2022
200
---------
Di 1. Nov 14:47:32 CET 2022
200
---------
Di 1. Nov 14:47:33 CET 2022
429
---------
Di 1. Nov 14:47:34 CET 2022
429
---------
Di 1. Nov 14:47:35 CET 2022
429
---------
Di 1. Nov 14:47:36 CET 2022
429
---------
Di 1. Nov 14:47:37 CET 2022
429
---------
Di 1. Nov 14:47:38 CET 2022
429
---------
Di 1. Nov 14:47:39 CET 2022
429
---------
Di 1. Nov 14:47:40 CET 2022
429
---------
Di 1. Nov 14:47:41 CET 2022
429
---------
Di 1. Nov 14:47:42 CET 2022
429
---------
Di 1. Nov 14:47:43 CET 2022
429
---------
Di 1. Nov 14:47:44 CET 2022
429
---------
Di 1. Nov 14:47:45 CET 2022
429
---------
Di 1. Nov 14:47:46 CET 2022
429
---------
Di 1. Nov 14:47:47 CET 2022
429
---------
Di 1. Nov 14:47:48 CET 2022
429
---------
Di 1. Nov 14:47:49 CET 2022
429
---------
Di 1. Nov 14:47:51 CET 2022
429
---------
Di 1. Nov 14:47:52 CET 2022
429
---------
Di 1. Nov 14:47:53 CET 2022
429
---------
Di 1. Nov 14:47:54 CET 2022
429
---------
Di 1. Nov 14:47:55 CET 2022
429
---------
Di 1. Nov 14:47:56 CET 2022
429
---------
Di 1. Nov 14:47:57 CET 2022
429
---------
Di 1. Nov 14:47:58 CET 2022
429
---------
Di 1. Nov 14:47:59 CET 2022
429
---------
Di 1. Nov 14:48:00 CET 2022
429
---------
Di 1. Nov 14:48:01 CET 2022
429
---------
Di 1. Nov 14:48:02 CET 2022
429
---------
Di 1. Nov 14:48:03 CET 2022
429
---------
Di 1. Nov 14:48:04 CET 2022
429
---------
Di 1. Nov 14:48:05 CET 2022
429
---------
Di 1. Nov 14:48:06 CET 2022
429
---------
Di 1. Nov 14:48:07 CET 2022
429
---------
Di 1. Nov 14:48:08 CET 2022
429
---------
Di 1. Nov 14:48:09 CET 2022
429
---------
Di 1. Nov 14:48:10 CET 2022
429
---------
Di 1. Nov 14:48:11 CET 2022
429
---------
Di 1. Nov 14:48:12 CET 2022
429
---------
Di 1. Nov 14:48:13 CET 2022
429
---------
Di 1. Nov 14:48:14 CET 2022
429
---------
Di 1. Nov 14:48:15 CET 2022
429
---------
Di 1. Nov 14:48:16 CET 2022
429
---------
Di 1. Nov 14:48:17 CET 2022
429
---------
Di 1. Nov 14:48:18 CET 2022
429
---------
Di 1. Nov 14:48:19 CET 2022
429
---------
Di 1. Nov 14:48:20 CET 2022
200
---------
Di 1. Nov 14:48:21 CET 2022
429
---------
Di 1. Nov 14:48:22 CET 2022
429
---------
Di 1. Nov 14:48:23 CET 2022
429
---------
Di 1. Nov 14:48:24 CET 2022
429
---------
Di 1. Nov 14:48:25 CET 2022
429
---------
Di 1. Nov 14:48:26 CET 2022
200
---------
Di 1. Nov 14:48:27 CET 2022
429
---------
Di 1. Nov 14:48:28 CET 2022
429
---------
Di 1. Nov 14:48:29 CET 2022
429
---------
Di 1. Nov 14:48:30 CET 2022
429
---------
Di 1. Nov 14:48:31 CET 2022
429
---------
Di 1. Nov 14:48:33 CET 2022
200
---------
Di 1. Nov 14:48:34 CET 2022
429
---------
Di 1. Nov 14:48:35 CET 2022
429
---------
Di 1. Nov 14:48:36 CET 2022
429
---------
Di 1. Nov 14:48:37 CET 2022
429
---------
Di 1. Nov 14:48:38 CET 2022
429
---------
Di 1. Nov 14:48:39 CET 2022
200
---------
Di 1. Nov 14:48:40 CET 2022
429
---------
Di 1. Nov 14:48:41 CET 2022
429
---------
Di 1. Nov 14:48:42 CET 2022
429
---------
Di 1. Nov 14:48:43 CET 2022
429
---------
Di 1. Nov 14:48:44 CET 2022
429
---------
Di 1. Nov 14:48:45 CET 2022
200
---------
Di 1. Nov 14:48:46 CET 2022
429
---------
Di 1. Nov 14:48:47 CET 2022
429
---------
Di 1. Nov 14:48:48 CET 2022
429
---------
Di 1. Nov 14:48:49 CET 2022
429
---------
Di 1. Nov 14:48:50 CET 2022
429
---------
Di 1. Nov 14:48:51 CET 2022
200

You can see that indeed the first 10 requests are allowed, and subsequent requests are blocked. However, a single new request is allowed at 14:48:20, which is only 57s after the first request. That means, that at this point 11 requests within 60s had been allowed. Now further requests got blocked again, with the next request allowed at 14:48:26 (63s after first request). This could be okay (taking into account the false-allowed at 14:48:20). Then again requests are blocked until at 14:48:33, which is seven seconds later.

Maybe I have a misunderstanding here, but I thought that if e.g. the current time is 14:48:30, the limiter would count the requests during the last 60 seconds (= 14:47:30 - 14:48:30), and in case the count is less than 10, the request would be allowed. In my example the number of requests in the timerange 14:47:30 - 14:48:30 is 5, so at 14:48:30 a request should be allowed, which is not the case.

Could you maybe explain the intended behaviour of the limiter? Maybe I understood something wrong here. Thanks!

[Narasimha1997]

@patrickjane thanks for your query.

Did you try SyncLimiter just interested to know the behaviour.

Also you can understand how "sliding window rate limiting" is different from normal fixed time based limiters by checking out the following blogs.

1. https://dev.to/satrobit/rate-limiting-using-the-sliding-window-algorithm-5fjn

2. https://konghq.com/blog/how-to-design-a-scalable-rate-limiting-algorithm

Sliding window rate limiter also takes into account the previous window's outcome to make the rate limiting more smooth. You can better understand from the blogs mentioned.

[patrickjane]

No I haven't tried the SyncLimiter. So you say the behaviour is correct?

[patrickjane]

With SyncLimitier same behaviour:

08:13:07          08:13:16                  08:14:00    08:14:06
|                 |                         |           |
|                 |                         |           |
1 1 1 1 1 1 1 1 1 1                         1           1

According to https://dev.to/satrobit/rate-limiting-using-the-sliding-window-algorithm-5fjn with a window-size of 60s the whole timerange should be within the first frame / 60s window at timestamp 08:14:06, and the count is 12 while it should have allowed only 10.

Either I still don't understand how it should work, or something is going wrong here?

[Narasimha1997]

Let me look into the issue in depth.

[Narasimha1997]

Okay, here are my comments,

1. Consideration of start time: If you look at the code snippet of initializing the window, the startTime is set to zero, that means the timer starts at the init. of window itself.

func NewSyncLimiter(limit uint64, size time.Duration) *SyncLimiter {
	current := NewWindow(0, time.Unix(0, 0))
	previous := NewWindow(0, time.Unix(0, 0))

	return &SyncLimiter{
		previous: previous,
		current:  current,
		lock:     sync.Mutex{},
		killed:   false,
		size:     size,
		limit:    limit,
	}
}

But in your examples, have you considered the time-gap between the initialization of the window and the time of arrival of the first request? It is very well possible that the arrival of first request is bit later than the actual window initialization time - which is unclear in your examples. In the second comment you made, the window actually started 7 seconds before the first request arrival probably.

2. Uniformity: The sliding window rate limiter cares about uniformity than the fixed window sizes, in traditional algorithms it will allow a burst of requests at the beginning and sits idle throughout rest of the window - this actually takes into effect from the second window because at any given point in time, whether a request should be allowed or not will be determined by:
   (previousAllowed * (( windowSize - offsetIntoCurrentWindow ) / windowSize) + currentAllowed) <= limit

For first window previousAllowed is zero, so it allows a burst, starting from second window uniformity is achieved.

From your example, you can see that every 6-7 seconds a request is allowed, because 60/10 = 6 (windowSize / limit), which is almost uniform, which is evident in your example.

I just wrote a basic python code which simulates this:

import time

max = 10
window = 60
previous = 0
ticks = 0
current = 0
totalTicks = 0

while True:

    ticks+=1

    w = (window - ticks) / window
    delta = previous * w + current
    if delta + 1 <= max:
        current +=1
        print('at {} allowed, current {}'.format(ticks, current))
    
    if ticks == window:
        print('window ended, allowed total: {}'.format(current))
        previous = current + 1
        current = 0
        ticks = 0
        totalTicks += ticks

This outputs (truncated for 3 windows):

at 1 allowed, current 1
at 2 allowed, current 2
at 3 allowed, current 3
at 4 allowed, current 4
at 5 allowed, current 5
at 6 allowed, current 6
at 7 allowed, current 7
at 8 allowed, current 8
at 9 allowed, current 9
at 10 allowed, current 10
window ended, allowed total: 10
at 11 allowed, current 1
at 17 allowed, current 2
at 22 allowed, current 3
at 28 allowed, current 4
at 33 allowed, current 5
at 39 allowed, current 6
at 44 allowed, current 7
at 50 allowed, current 8
at 55 allowed, current 9
at 60 allowed, current 10
window ended, allowed total: 10
at 11 allowed, current 1
at 17 allowed, current 2
at 22 allowed, current 3
at 28 allowed, current 4
at 33 allowed, current 5
at 39 allowed, current 6
at 44 allowed, current 7
at 50 allowed, current 8
at 55 allowed, current 9
at 60 allowed, current 10
window ended, allowed total: 10

The above outputs are in par with 1 and 2.

[patrickjane]

Alright, thanks for the explanation. I actually changed my test in a way that it creates the window upon first request, but still I get the 11th allowed requests after 58s, while I thought that it should be after 60s. But that difference is marginal.
I think I'm just gonna accept this, since overall, after your explanation, the limiter seems to do the job well.

[patrickjane]

Okay so I am afraid I still have more questions. I have added this library to my request gateway, to block excessive requests. As with all functionality, I am writing automated tests to test everything within my service, which now includes the rate limiter functionality.

So I wrote a test with starts my gateway, then fires 11 requests, and expects 10 requests to pass and 1 to fail (limit set to 10 per minute).
This works fine for 1) the default limiter 2) the attribute based limiter without background sliding but fails for 3) the attribute based limiter with background sliding enabled.

I have this in my middleware:

haskey := self.limiterIP.HasKey(clientIp)

ok := self.limiterIP.HasOrCreateKey(clientIp, 10, time.Minute)

allowed, err := self.limiterIP.ShouldAllow(clientIp, 1)

log.Info("IP: %s did have key: %v create key: %v allowed: %v allow-error: %s", clientIp, haskey, ok, allowed, err)

When using the attribute based limiter without background sliding, I get this output:

22/11/08 10:20:34 info: router.go:107: IP: 127.0.0.1 did have key: false create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:20:34 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:20:34 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:20:34 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:20:34 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:20:34 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:20:34 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:20:34 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:20:34 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:20:34 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:20:34 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: false allow-error: %!s(<nil>)

However, once I set background sliding to true, this is what I get instead:

22/11/08 10:21:32 info: router.go:107: IP: 127.0.0.1 did have key: false create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:21:32 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:21:32 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:21:32 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:21:32 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:21:32 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:21:32 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:21:32 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:21:32 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:21:32 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)
22/11/08 10:21:32 info: router.go:107: IP: 127.0.0.1 did have key: true create key: true allowed: true allow-error: %!s(<nil>)

You can see that 11 requests had been allowed instead of 10. When I set the limit to 20/min, it will allow 21, when I set it to 30/min, it will allow 31.
So it seems like it counts 1 extra each time.

How does this come?

[Narasimha1997]

@patrickjane sorry for the delay in response had been on some work.

Maybe there is a minor issue in when background sliding, I Will look into this, but anyday I would recommend you to turn off background sliding because it spawns up a goroutine for each attribute you have created and is not scalable when you have hundreds of attributes - as it takes more memory and some kind of userspace scheduling overhead on go runtime. SyncLimiter is the efficient way of doing rate limiting. Turn off background sliding by setting that parameter to false.

[patrickjane]

Yes I am using the SyncLimiter anyway, but I noticed this behaviour when writing unit tests for my service.