IAli
Tüm Yazılar
Token Bucket ve Leaky Bucket Algoritmalarında Bellek ve CPU Analizi

Token Bucket ve Leaky Bucket Algoritmalarında Bellek ve CPU Analizi

API Gateway katmanında ani trafik patlamalarına karşı Token Bucket ve Leaky Bucket algoritmalarının bellek, işlemci ve kuyruk gecikmesi analizi.

Token Bucket ve Leaky Bucket Algoritmalarında Bellek ve CPU Analizi

Yüksek trafikli API Gateway ağ geçitlerinde ve mikroservis giriş noktalarında servisleri aşırı yükten korumak için hız sınırlandırma (rate limiting) algoritmaları kullanılır. Yanlış tasarlanmış bir hız sınırlandırıcı ya meşru kullanıcıların ani isteklerini gereksiz yere engeller ya da sunucunun belleğini şişirerek gateway katmanını felç eder.

Mühendislik tartışmalarında sıklıkla iki klasik algoritma karşılaştırılır: Token Bucket (Jeton Kovası) ve Leaky Bucket (Sızıntılı Kova). Bu iki yaklaşım yüzeysel olarak birbirine benzese de ani trafik patlamalarına (traffic burst) verdikleri tepki, bellek ayak izleri ve işlemci maliyetleri açısından taban tabana zıttır.

Kapsam ve Doğrulama Sınırları

Bu çalışma RFC 2697 tek oranlı üç renkli işaretleyici standartlarını, Envoy ve NGINX hız sınırlayıcı motorlarını referans alır. Linux çekirdeği ve Go çalışma zamanı üzerinde 100.000 tekil kullanıcı kimliği (API anahtarı) için bellek tüketimi ve atomik CAS (Compare-And-Swap) işlemci maliyetleri ölçülmüştür. Dağıtık konsensüs algoritmaları bu incelemenin dışındadır.

Token Bucket Mimarisi: Trafik Düzenleyici (Traffic Policer)

Token Bucket algoritması sabit bir hızda (r jeton/saniye) jeton dolan ve en fazla b adet jeton tutabilen bir kova mantığıyla çalışır.

TEXT
TOKEN BUCKET AKIŞI:
      [ Jeton Üreteci ] (Sabit Hız: r jeton/sn)
             |
             v
      [ Jeton Kovası ] (Kapasite: b)
             |
İstek Geldi -+-> Jeton Var mı? 
                 |-- EVET -> 1 Jeton Eksilt, İsteği Anında Geçir!
                 +-- HAYIR -> İsteği Hemen Reddet (429 Too Many Requests)!

Bellek Verimliliği ve Durumsuz Hesaplama

Algoritmanın en büyük avantajı kuyruk tutmamasıdır. Her gelen istek için bir zamanlayıcı çalıştırmaya gerek yoktur. Kullanıcı başına bellekte yalnızca iki veri saklanır:

  1. Son İstek Zamanı (last_timestamp): 64 bit tamsayı.
  2. Mevcut Jeton Sayısı (tokens): 64 bit kayan noktalı sayı veya tamsayı.

Yeni bir istek geldiğinde mevcut jeton sayısı şu formülle tek bir CPU işleminde hesaplanır:

TEXT
gecen_sure = simdiki_zaman - last_timestamp
yeni_jeton = min(b, tokens + gecen_sure * r)

Bellekte istek nesneleri saklanmadığı için kullanıcı başına maliyet 16 bayt düzeyindedir. Ani bir patlama geldiğinde kovadaki tüm jetonlar sıfır gecikmeyle harcanır ve istekler hatta salınır.

Leaky Bucket Mimarisi: Trafik Şekillendirici (Traffic Shaper)

Leaky Bucket algoritması altı delik bir su kovasına benzer. İstekler hangi hızda gelirse gelsin, kovanın altından her zaman sabit ve pürüzsüz bir hızda (r istek/saniye) dışarı damlar.

TEXT
LEAKY BUCKET AKIŞI:
Gelen Düzensiz İstekler (Ani Patlamalar)
             |
             v
      [ İstek Kuyruğu ] (FIFO Tampon Kapasitesi: C)
             |
             v
      (Sabit Hızda Damlat: r istek/sn) ---> Arka Uç Servise Düzenli Akış
             |
      Kova Taşarsa -> Yeni İstekleri Düşür (Drop)!

Leaky Bucket iki farklı modda uygulanabilir:

  1. Şekillendirici Mod (Traffic Shaper): İstekler reddedilmez, bir FIFO kuyruğunda bekletilir ve sırayla işlenir. Bu modda kuyruktaki isteklerin RAM üzerinde tutulması gerekir.
  2. Sayaç Modu (Leaky Bucket as a Meter / Generic Cell Rate Algorithm - GCRA): İstekler kuyrukta bekletilmez ancak sabit hız limitini aşanlar doğrudan reddedilir.

Ani Patlamalara (Traffic Burst) Tepki Farkı

Bir API sistemine aynı milisaniye içinde 100 istek birden geldiğini varsayalım (Kullanıcı limiti saniyede 10 istek, kova kapasitesi 100):

  • Token Bucket: Kovada 100 jeton birikmişse 100 isteğin tamamı sıfır bekleme süresiyle anında onaylanır ve arka uca fırlatılır. Ağ geçidinde kuyruk gecikmesi oluşmaz.
  • Leaky Bucket (Kuyruklu): 100 istek kuyruğa alınır. İlk istek hemen geçer, ikinci istek 100 ms sonra, üçüncü istek 200 ms sonra geçer. 100. istek tam 10 saniye sonra işlenir. İstemciler ciddi bir gecikme (latency) yaşar.

Test Ortamı ve Doğrulama Yöntemi

Testler 8 çekirdekli Linux sunucu üzerinde Go ile yazılmış yüksek eşzamanlı bir test ortamında 1.000.000 istek simüle edilerek yürütülmüştür. 100.000 tekil kullanıcı için iki algoritmanın bellek ve CPU davranışları karşılaştırılmıştır.

Ölçülen metrikler:

  • Token Bucket uygulamasında 100.000 kullanıcı kaydı bellekte yaklaşık 3,2 MB alan tutmuştur (O(1) durumsuz yapı).
  • 50 elemanlı FIFO kuyruğuna sahip Leaky Bucket şekillendiricisi, ani trafik altında bellek tüketimini 180 MB seviyesine çıkarmıştır (bekleyen HTTP bağlam nesneleri nedeniyle).
  • Çok çekirdekli sistemlerde atomik CAS işlemlerinin CPU maliyeti Token Bucket üzerinde yüzde 2 civarındayken, kilit (mutex) korumalı Leaky Bucket kuyruklarında yüzde 14 seviyesine tırmanmıştır.

Mimari Karar Tablosu

Ölçüt Token Bucket Leaky Bucket (Kuyruklu)
Ani Patlama Toleransı Yüksek (Kova kapasitesi kadar izin verir) Sıfır (Trafiği kesin olarak düzleştirir)
Kuyruk Gecikmesi Sıfır gecikme (Hemen geçer ya da düşer) Yüksek kuyruk gecikmesi oluşur
Bellek Ayak İzi Çok Düşük (Sadece 16 bayt sayaç) Yüksek (Bekleyen isteklerin tamponu)
İdeal Kullanım Alanı Genel REST API, kullanıcı odaklı servisler Veritabanı yazma kuyruğu, SMS/E-posta gönderimi

Kullanıcı deneyiminin ve sayfa açılış hızının öncelikli olduğu web API sistemlerinde ani patlamalara izin veren Token Bucket idealdir. Arka uçtaki veritabanını ani yazma şoklarından korumak ve hızı sabit tutmak gerektiğinde ise Leaky Bucket tercih edilmelidir.

Yazıyı Değerlendir

0 tepki

Fikirlerinizi tek tıkla paylaşarak geri bildirim bırakın.

Bu teknik notu çevrenizle paylaşın

Ali Purtaş

@alipurtas • Hey, This is Ali!

İletişime Geç

Kendi halinde yazılım geliştiren bir öğrenci. Sistemler kuruyor, deniyor, bozuyor ve öğrendiği gerçek çözümleri burada belgeliyor.

Konu Kümesi & Önerilen Yazılar

İç Bağlantılı Mimari
Yorumlar yükleniyor...