Rate Limiting Algorithms Leaky/Leaking Bucket aka Spike Control Policy - Sabit Hızdadır

Giriş

Açıklaması şöyle. Bu yöntem de üst sınır aşılırsa istek es geçilmez ve sonra işlenmek üzere kuyruğa atılır. Bu yöntemi gerçekleştiren bir sınıf burada. Kuyruk ta artık dolarsa, yeni istekler dikkate alınmıyor

The Spike Control Policy is provided for smoothing API traffic. The policy ensures that within any given period of time, no more than the maximum configured requests are processed.
If there is no request quota in the current window, the policy allows requests to be queued for later reprocessing without closing the connection to the client.

Açıklaması şöyle

The leaky bucket limits the constant outflow rate, which is set to a fixed value. For example, if the outflow rate is set to one request per second, it cannot process two requests per second. This ensures the outflow rate is always stable, regardless of the inflow rate.

Şeklen şöyle

Bir başka şekil şöyle

Gerçekleştirim şöyle

In terms of algorithm implementation, a queue can be prepared to save requests, and a thread pool (ScheduledExecutorService) can be used to periodically obtain requests from the queue and execute them, and multiple concurrent executions can be obtained at one time.

This algorithm also has drawbacks after use: it cannot cope with short-term burst traffic.

Bu algoritmanın bir dezavantajı şöyle

This algorithm also has drawbacks after use: it cannot cope with short-term burst traffic.

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.

Rate Limiting Algorithms

Giriş

Algoritmalar şöyle

1. Fixed Window Counter

2. Sliding Window Counter

3. Token Bucket

4. Leaky Bucket

5. Sliding Logs

1. Counter algorithm aka Fixed window counter - Burst Desteklemez

Bu algoritmanın kötü tarafı şöyle

For example, if the limit is 100 requests per minute, a user could send 100 requests in the last second of the current minute and 100 more in the first second of the next minute—effectively sending 200 requests within two seconds.

2. Sliding window

Açıklaması şöyle. Diyelim ki dakikada 100 istek işliyoruz. En son gelen istekten bir dakika öncesine gideriz ve sliding window logda toplam kaç tane istek olduğunu sayarız. Eğer bu sayı 100 veya daha büyükse yeni istek reddedilir. Eğer küçükse yani yeni istek kabul edilecekse 1 dakikadan önceki eski istekler de logdan silinir.

Sliding window log algorithm keeps a log of request timestamps for each user (Generally redis sorted sets are used for this). When a request comes, we first remove all outdated timestamps before inserting the new request time to the log. Then we decide whether this request should be processed depending on whether the log size has exceeded the limit.

Örnek

Şöyle yaparız. Burada window olarak HashMap kullanmanın bir özelliği yok. List te olabilirdi

public static void main(String[] args) {
  int[] data = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 21}; // input data
  int windowSize = 4; // size of the sliding window
  int slideInterval = 4; // slide interval

  Map<Integer, Integer> window = new HashMap<>(); // the sliding window

  for (int i = 0; i < data.length; i++) {
    window.put(i, data[i]); // add the current element to the window

    if (window.size() == windowSize) { // check if the window is full

      String joined = window.values().stream()
                        .map(Object::toString)
                        .collect(Collectors.joining(", "));
      System.out.println("Window : " + joined);

      Iterator<Map.Entry<Integer, Integer>> iterator = window.entrySet().iterator();
      for (int remove = 0; remove < slideInterval && iterator.hasNext(); remove++) {
        iterator.next();
        iterator.remove();
      }
      i = (i - windowSize) + slideInterval + 1; // slide the window
    }
  }
}

Çıktı şöyle

Window : 2, 4, 6, 8
Window : 12, 14, 16, 18

3. Token Bucket - Burst Destekler
Token Bucket yazısına taşıdım

4. Leaky Bucket aka Spike Control Policy - Sabit Hızdadır

Leaky Bucket yazısına taşıdım