Rate Limiting Algorithms - Token Bucket - Burst Destekler

Giriş

Açıklaması şöyle

The token-bucket algorithm is explained with the analogy of a bucket with finite capacity, into which tokens are added at a fixed rate. But it can’t fill up infinitely. If a token arrives when the bucket is complete, it’s discarded. On every request, some tokens are removed from the bucket. The request is rejected if there are fewer tokens in the bucket.

Belli bir süre örneğin 1 dakika içinde 100 tane istek işlenir. 100 istek arasındaki süre önemli değildir. 1 dakika geçince tekrar 100 tane token kovaya eklenir. Şeklen şöyle

Dolayısıyla token'lar bir anda tüketilebilir. Açıklaması şöyle

The token bucket allows for sudden increase in traffic to some extent, while the leaky bucket is mainly used to ensure the smooth outflow rate.

Bu algoritmanın bir problemi şöyle. Yani bir sonraki pencerenin tam bitiminde ve bir sonraki pencerenin tam başında kova tam dolarken iki tane 100'lük istek gelirse üst sınır aşma ihtimali var. Bir anda 200 istek işlerken bulabiliriz kendimizi. Böylece sistem aslında saniyede en fazla 100 istek işleyebilirlen aslında saniyede 200 istek işlemek zorunda kalıyor

I’ll show the problem with a perfect example to short explain the idea:

1. At some moments, our bucket contains 100 tokens.

2. At the same time, we consume 100 tokens.

3. After one second, the refiller again fills 100 tokens.

4. At the same time, we consume 100 tokens.

Açıklaması şöyle

Implementation idea: You can prepare a queue to save tokens, and periodically generate tokens through a thread pool and put them in the queue. Every time a request comes, get a token from the queue and continue to execute.