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