YazılarYayımlandı

Sliding Window: Token Bucket’ın Yeterli Olmadığı Yerler

Bir önce ki yazıda Token Bucket’ı kurduk. Kova (Bucket), jetonlar, ve dolum hızını anladık. Ortalama hızı kibarca yöneten, kontrollü bir burst’e nefes payı bırakan sağlam bir algoritma.

Talip olduğun yolu yokuşuyla seveceksin!

Token Bucket’ın yeterli olmadığı yerde Sliding Window

Bu yazıyı okumadan önce tavsiyem Token Bucket: .NET ile Rate Limiting’in Temel Algoritması yazısını okumanız olacaktır.

Bir önce ki yazıda Token Bucket’ı kurduk. Kova (Bucket), jetonlar, ve dolum hızını anladık. Ortalama hızı kibarca yöneten, kontrollü bir burst’e nefes payı bırakan sağlam bir algoritma.

Sistemimizi kullanan bir kullanıcıya “dakika da 100 istek” demek çok kolaydır. Peki bu istek zamanın hangi anında geçerlidir. Bunu nasıl tarif edeceğiz. İşte işin zor kısmı budur.

Peki her problem bir ortalama hız problemi midir? Bu yazının derdi tek bir soruya cevap vermektir.

Token Bucket’i bildiğimize göre neden başka bir algoritmaya ihtiyaç duyuyoruz?

Aslında cevap gözümüzün önünde. Sadece oraya bakmıyoruz. Diyelim ki bir servis için limit belirledik ve dakikada 100 istek olarak kuralımızı hayata geçirdik. Aşağıdaki şekilde farklı iki zaman diliminde (buna görsellerde window diyeceğim) belirlediğimiz limite uygun şekilde istekler geldi.

10:00:58
████████████████████████  100 request
        ↓
10:01:01
████████████████████████  100 request

İşte sihir burada başlıyor. Üç saniye de sistem 200 isteği kabul etti. Loglara baktık ve bir ihlal görmedik. Kural neydi? Dakika da 100 istek. İlk 100 istek 10:00 diliminde ikinci 100 istek ise 10:01 diliminde geldi. Ama gerçek dünya da gerçekten böyle mi oldu? Yoksa kullanıcı “dakikada 100 saniye” limitini üç saniye de iki katına mı çıkarmış oldu?

İşin özü kağıt üzerinde limiti koruduk ama sahada başarısız olduk. Hem sahada edindiğim deneyim hem de yaptığım örnekler sonrasında fark ettim ki iki bitişik zaman diliminde her bir zaman dilimi verdiğim kurala uymasına rağmen toplam trafiğin limiti aşılmış oluyor. Buna Sınır Sızıntısı adını verdim.

Peki ama bu algoritmaları bizleri bu gibi durumlara karşı da korusun diye kullanmıyor muyuz? Fixed Window buna neden izin veriyor? İşte burada bilmemiz gereken bu algoritmanın zamanı nasıl yönettiğidir.

Fixed Window’un mantığı çok basittir. Zamanı sabit dilimlere böler. Örnekte gördüğümüz 10:00:00–10:00:59 aralığı bir dilimdir. Her zaman dilimi bir sayaç tutar ve bu aralık bittiğinde sayaç sıfırlanır.

Her iki zaman dilimi de kurala uyar ve ~2sn’de 200 request geçer. Bu sızıntı bir teori değildir.

public bool TryAcquire(double t)
{
    long w = (long)(t / _window);          // istek hangi zaman dilimine düşüyor?
    int c = _counts.GetValueOrDefault(w);   // zaman diliminin sayacı
    if (c < _limit) { _counts[w] = c + 1; return true; }
    return false;
}

İşte sorun tam da “w”’nin değiştiği anda olur. Zaman dilimi değiştiğinde “_counts” yeni zaman diliminin sayacı olmuştur. Yani kullanıcının önünde tertemiz hiç kullanılmamış bir kota vardır artık. Zaman diliminin son saniyesinde kotasını dolduran kullanıcı yeni dilimin ilk saniyesinde de bu aralığın kotasını tüketip kısa sürede her iki dilime ait kotayı tüketmiş olur.

Buradan şu çıkarımı yapıyoruz: Fixed Window akışa bakmıyor zaman dilimine bakıyor.

Peki ilk yazıda çalışma mantığını öğrendiğimiz Token Bucket bu sorunu çözmez mi? Ani bir şekil de gelen istekler (jetonlar) bucket (kova) içinde birikir ve yığılma bir nebzede olsa törpülenmiş olur. Ama Token Bucket’ın asıl işi bu değildir. Token Bucket algoritmasının tasarlanma amacı ortalama hızı sabit tutmaktır. Kısacası burst bir kusur değildir bir özelliktir bu algoritma için. Mesela bir OTP servisini düşünelim. Kullanıcının kısa sürede on kod istemesi ile bu on kodu on ayrı dakikada istemesi aynı şey değildir. Eğer burada ortalama hız kullanırsak yanılırız. Bizim için bu örnekte önemli olan herhangi bir zaman diliminde ki tepe değeridir.

OTP’yi dakikada 100 ile sınırladık ama biri saniyeler içinde 200 kod aldı ve hiçbir alarm çalmadı. Token Bucket yanlış çalışmadı. Sadece yanlış soruya doğru cevap vermiş oldu.

Peki Sliding Window Nasıl Çalışır?

Sliding yani kayma. Aslında bu kadar basit. Zaman dilimini sabit tutmak yerine kayan bir pencerede yönetmek. Sayaç sıfırlanmaz. Her bir istek geldiğinde algoritma hemen şu soruyu sorar: “Şu andan itibaren son 60sn’de kaç istek geldi?” Eğer cevap limitin altındaysa istek geçer, değilse reddedilir. Zaman çizgisi üzerinde ki pencere hiçbir zaman durmaz. İleri doğru hareket eder. İşte bu hareket sayesinde başta söylemiş olduğum Sınır Sızıntısı sorunu da ortadan kalkar. Peki ama sorduğumuz soruda şuandan itibaren geri dönük 60sn’yi nasıl sayacak? İşte burada iki yöntem var.

Zaman aralığı sürekli ileri doğru kayar ve 60sn’yi geçen istekler artık sayıma dahil edilmez

Yöntem 1: Sliding Window Log

Bu yöntem aslında sonucun en doğru hesaplandığı yöntemdir.

public bool TryAcquire(double t)
{
    double cutoff = t - _window;
    while (_log.Count > 0 && _log.Peek() <= cutoff)
        _log.Dequeue(); // 60 saniyeden eski kaydı at

    if (_log.Count < _limit) 
      _log.Enqueue(t); return true;

    return false;
}

Örnekte fark ettiyseniz sıfırlanan bir counter yok. Her bir request öncesinde 60 saniyeden eski kayıtlar temizleniyor ve sonra kalanlar sayılıyor. Bu yöntem çok hassastır ve kesin sonuç verir. Fakat bunun da bir bedeli vardır. Her bir request için zaman damgası (timestamp) saklamak gerekir. Memory gelen request’in hacmiyle birlikte şişer. Bu maliyete bir de eski kayıtların silinmesini de eklemek gerek tabi. Yüksek trafikli sistemlerde bu bir sorundur.

Yöntem 2: Sliding Window Counter

Bir çok production ortamında kullanılan yöntemdir. Her bir istek için timestamp tutmak yerine iki sayaç vardır. Mevcut ve önce ki zaman dilimi. Sonuç iki pencerenin ağırlıklı bir bileşimiyle tahmin edilir.

double elapsedFraction = (t - w * _window) / _window;
int prev = _counts.GetValueOrDefault(w - 1);
int cur  = _counts.GetValueOrDefault(w);

double estimate = cur + prev * (1 - elapsedFraction);   // ağırlıklı tahmin
if (estimate < _limit) { _counts[w] = cur + 1; return true; }

Bu kodda ki en önemli kısım (1 — elapsedFraction) kısmıdır. Eğer mevcut zaman diliminin %25’lik kısmındaysak önce ki zaman diliminin %75’lik sayısı hesaba katılır. Aslında bu bir tahmindir. Kazanç bir önce ki yönteme göre çok büyüktür. Artık memory request arttıkça şişmez, eski kayıtların silinme derdi yoktur. Kayıp ise nispeten daha azdır.

Log kesin değer verir (O(n)) Counter ise tahmini bir değer verir (O(1))

Bu iki yöntemi ve Fixed Window test ettiğimde elde ettiğim sonuçlarda her şeyi net bir şekilde ortaya koydu.

Toplam gönderilen istek : 200  (100 + 100, ~3 saniye arayla)
Limit                   : dakika da 100 istek
------------------------------------------------
Fixed Window            : 200 kabul   <- Sınır Sızıntısı
Sliding Window Log      : 100 kabul   <- tam
Sliding Window Counter  : 102 kabul   <- yaklaşık

Fixed Window 3 saniye içinde aslında 2 dakikada tüketilmesi gereken limiti tüketti. Sliding Window Log yöntemi tam 100’de durdu ve gelen diğer isteklerin hepsini engelledi. Sliding Window Counter ise 102 isteğe izin verdi. İşte burada mimar olarak şu trade-off’ları bilerek bir tercih yamak gerekir.

Fixed Window hassasiyet ve memory kullanımı olarak çok düşük ve Sınır Sızıntılarına açık bir yapıdır.

Sliding Window Log hassasiyet olarak tam istediğini verir. Memory kullanımı yüksektir fakat Sınır Sızıntılarına karşı kapalıdır.

Sliding Window Counter ise yaklaşık bir hassasiyete sahipken memory kullanımı açısından ikinci sırada yer alır. Sınır Sızıntısına karşıda kısmen bir koruma sağlar.

İşte bu trade-off’ların ışığında seçim yapılması gerekmektedir. Sliding Window, Fixed Window’a göre daha dik bir yoldur. Eğer servislerinize eklediğiniz rate limitinde zaman adaleti gerekirse bu dik yolu seçmek gerekir. Yazının başında da belirttiğim üzere “Talip olduğun yolu yokuşuyla seveceksin” :)

Peki Sliding Window her zaman doğru cevap mıdır?

Burası aslında tek bir doğrunun olmadığını söylemem gereken yer. İhtiyaçlara göre seçimler yapmak gerekmektir. Eğer gelen trafikte kontrollü bir burst’a izin verecekseniz ya da düşük maliyetli veya çok basit bir günlük kota yetiyorsa o zaman bu algoritmayı kullanmak gereksiz olur.

Burst kabul ediliyor ise Token Bucket, limit tanımı yapılmış ve net ise Sliding Window

Buradan şu sonuca varmamak gerekiyor. Token Bucket yanlış bir algoritmadır ve kullanmak can sıkabilir. Eğer ortalama hızı ölçüp ilerliyorsanız işinizi görür. Ama limitlere uyum kesin ise işte o zaman Sliding Window öne çıkar.

Bir sonra ki yazıda bir production ortamında süreç nasıl ilerliyor onu göstermeye çalışacağım. Özellikle .Net’in yerleşik SlidingWindowLimiter’ını daha net göreceğiz. Window ve SegmentsPerWindow parametrelerinin nasıl bir kolaylık ve alternatif sağladığını beraber inceleyeceğiz.

Zaman ayırıp okuduğunuz için teşekkür ederim. Geri dönüşleriniz benim için değerlidir.

Kaynaklar