Spring WebFlux + Bucket4j

[sbilello]

Hello!

I am trying to understand how I can integrate with Spring WebFlux correctly.

Is Bucket thread-safe?
If yes I would create several Bucket Singleton instances and in particular one for each endpoint.

The goal is to have a Server-Side Rate Limiter in a Spring WebFlux CRUD Application.

import com.giffing.bucket4j.spring.boot.starter.webflux.WebfluxRateLimitException;
import io.github.bucket4j.*;
import lombok.extern.slf4j.Slf4j;
import org.springframework.context.annotation.Configuration;
import org.springframework.core.Ordered;
import org.springframework.http.server.reactive.ServerHttpRequest;
import org.springframework.http.server.reactive.ServerHttpResponse;
import org.springframework.web.server.ServerWebExchange;
import org.springframework.web.server.WebFilter;
import org.springframework.web.server.WebFilterChain;
import reactor.core.publisher.Mono;

import java.time.Duration;

@Configuration
@Slf4j
public class RateLimitingFilter implements WebFilter, Ordered {

    private Bucket bucket;

    public RateLimitingFilter() {
        Bandwidth limit = Bandwidth.simple(5, Duration.ofSeconds(5));
        bucket = Bucket4j.builder().withNanosecondPrecision().addLimit(limit).build();
    }


    @Override
    public Mono<Void> filter(ServerWebExchange exchange, WebFilterChain chain) {
        ServerHttpRequest request = exchange.getRequest();
        ServerHttpResponse response = exchange.getResponse();
        ConsumptionProbe consumptionProbe = getBucket().tryConsumeAndReturnRemaining(1);
        Long remainingLimit = consumptionProbe.getRemainingTokens();
        if (consumptionProbe.isConsumed()) {
          log.info("Remaining {}", remainingLimit);
        } else {
           return Mono.error(new WebfluxRateLimitException("TOO MANY REQUEST"));
        }
        response.getHeaders().set("X-Rate-Limit-Remaining", String.valueOf(remainingLimit));   
        return chain.filter(exchange);
    }

    @Override
    public int getOrder() {
        return -1;
    }

}

LOG

Why do the tokens consumed are more than 5 in 5 seconds?

I would have expected only no more than 5 tokens consumed in 5 seconds.

2021-01-13 18:47:54.596][XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 4
2021-01-13 18:47:56.076][XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 4
2021-01-13 18:47:56.974][XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 3
2021-01-13 18:47:57.716][XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 3
2021-01-13 18:47:58.320][XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 3
2021-01-13 18:47:58.882][XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 2
2021-01-13 18:47:59.417][XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 2
2021-01-13 18:47:59.888][XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 1
2021-01-13 18:48:00.346][XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 1
2021-01-13 18:48:00.782][XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 0
2021-01-13 18:48:01.381][XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 0

[vladimir-bukhtoyarov]

@sbilello hello,

Of course, bucket is thread-safe. When you create bucket via this code

Bandwidth limit = Bandwidth.simple(5, Duration.ofSeconds(5));

you get bucket with 5 initial tokens and 1 token is added to the bucket each second.

[sbilello]

I changed with

Bandwidth limit = Bandwidth.simple(5, Duration.ofSeconds(5)).withInitialTokens(0);
bucket = Bucket4j.builder().withNanosecondPrecision().addLimit(limit).build();

now the log shows

2021-01-14 14:13:12.799[XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 4
2021-01-14 14:13:13.115[XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 3
2021-01-14 14:13:13.497[XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 2
2021-01-14 14:13:13.912[XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 2
2021-01-14 14:13:14.299[XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 1
2021-01-14 14:13:14.685[XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 0
2021-01-14 14:13:15.060[XNIO-1 I/O-11][INFO][RateLimitingFilter:?] ? - Remaining 0
2021-01-14 14:13:19.386[XNIO-1 I/O-11][ERROR][GlobalExceptionConfigurer:?] ? - unexpected-error: request uri: [GET] [http://127.0.0.1:9090/hello] exception: [429 TOO_MANY_REQUESTS "TOO MANY REQUEST"]

This means that I am able to execute the API call more than 5 times in 5 seconds.
It is not super precise. Is this expected?

[sbilello]

I tried also

Refill refill = Refill.intervally(1, Duration.ofSeconds(5));
Bandwidth limit = Bandwidth.classic(1, refill);
bucket = Bucket4j.builder().withNanosecondPrecision().addLimit(limit).build();

2021-01-14 16:21:28.570[XNIO-1 I/O-10][INFO][RateLimitingFilter:?] ? - Remaining 0
2021-01-14 16:21:29.589[XNIO-1 I/O-10][INFO][RateLimitingFilter:?] ? - Remaining 0
2021-01-14 16:21:30.431[XNIO-1 I/O-10][ERROR][GlobalExceptionConfigurer:?] ? - unexpected-error: request uri: [POST] [http://127.0.0.1:9090/hello?reason=check_server&msg=unos] exception: [429 TOO_MANY_REQUESTS "TOO MANY REQUEST"]
2021-01-14 16:21:31.349[XNIO-1 I/O-10][ERROR][GlobalExceptionConfigurer:?] ? - unexpected-error: request uri: [POST] [http://127.0.0.1:9090/hello?reason=check_server&msg=unos] exception: [429 TOO_MANY_REQUESTS "TOO MANY REQUEST"]

It should not be able to consume more than 1 token every 5 seconds! I don't understand what I am missing in the configuration.
Remaining N means that the request was served to the client

[vladimir-bukhtoyarov]

It should not be able to consume more than 1 token every 5 seconds!

It is not true. Pay deep attention that token-bucket does not declare contract in the form N tokens/M timewindow. Declared contact is more complex https://en.wikipedia.org/wiki/Token_bucket#Algorithm One time when the bucket is full you are able to consume 1 token, and one token will be added immediately after 5 seconds(because 1 token is added every 5 seconds), so after 5 seconds you are able to consume the token again, that leads to the possibility to come in a situation when you are able to consume 2 tokens during 5 seconds.

Also, I want to notice that mocking a clock is the best way to play with Token-bucket algorithm, see example there #128 (comment)

[sbilello]

After reading that comment I understood.
Do you know how it can be achieved a behavior that would define the contract of no more than N tokens in an M time window?
So if you want to use this algorithm to cap the maximum number of requests served by an API in an M time window like no more than 100 API calls per second?
Is there a way to use it or I should look for another library or create a fork of the current library?
Thanks for your reply!

[vladimir-bukhtoyarov]

@sbilello all solutions based on Token-Bucket/Leaky-Bucket(and similar algorithms that use fixed memory) are not suitable to cover these hard requirements.

[sbilello]

https://medium.com/nlgn/design-a-scalable-rate-limiting-algorithm-system-design-nlogn-895abba44b77#:~:text=1)%20Leaky%20Bucket,the%20queue%20is%20not%20full. I was reading this article to understand which options might be available. I would like to understand what's the behavior of this library given the fact that we might be able to consume more than tokens N in a period M?
What's the contract defined from this

Refill refill = Refill.intervally(1, Duration.ofSeconds(5));
Bandwidth limit = Bandwidth.classic(1, refill);
bucket = Bucket4j.builder().withNanosecondPrecision().addLimit(limit).build();

How can we translate this into plain English to understand the behavior from client's perspective?
The bucket has a size of 1 and a token is added every 5 seconds but we might be able to consume more than 1 token in a 5 second window because between consume and refill we have another consume operation and we may consume more than N tokens in the particular M refill time.

[vladimir-bukhtoyarov]

@sbilello try to read this part of documentation https://github.com/vladimir-bukhtoyarov/bucket4j/blob/master/doc-pages/token-bucket-brief-overview.md it should give you neccessary explanations

[sbilello]

Thanks, @vladimir-bukhtoyarov I found this interesting article https://stripe.com/blog/rate-limiters giving a broad overview of the problem and the different algorithms available. However, Is it correct to say that a bucket with a B capacity allows serving at most B requests per second? Is withNanosecondPrecision() required to achieve second precision?

[vladimir-bukhtoyarov]

No. Imagine a backet with capacity 10 and refill 5 tokens/1 second. With this settings bucket will allow to consume:

• 15 tokens per 1 second (calculated as 10 + 5 *1), rate per second = 15
• 60 tokens per 10 seconds (calculated as 10 + 5 *10), rate per second = 6
• 310 tokens per 1 minute (calculated as 10 + 60 * 5), rate per second = 5.166666
• 18010 tokens per 1 hour (calculated as 10 + 3600 * 5), rate per second = 5.0027777

As, you can see on long distance consumption rate equals to refill rate, but at moment max amount of tokens that can be consumed per time T equals to capacity + R, where R is number of tokens that can be refilled during the time period T.

[sbilello]

if we make capacity 10 and refill 1 token/second

• 11 tokens per 1 second (calculated as 10 + 1 * 1), rate per second = 11
• 20 tokens per 1 second (calculated as 10 + 1 * 10), rate per second = 20/6 = 3.33
• 70 tokens per 1 minute (calculated as 10 + 1 * 60 ), rate per second = 70/60 = 1.16
• 3610 tokens per 1 hour (calculated as 10 + 1 * 3600), rate per second = 3610/3600 = 1.02

I think that I got your point. It was one of the best discussions and explanations! Thank you very much! It looks like that after 1 hour the rate-limiting factor is given by the refill frequency