Token Bucket: .NET ile Rate Limiting’in Temel Algoritması

Yediğin meyve bile, toprağa ekildiği andan itibaren sana yazılı; sen hala doğru kişilerin seni bulup bulamayacağından şüphe ediyorsun.

Token Bucket

Neden Rate Limiting?

Çarşamba sabahı saat 09:14. Production’a önceki gün küçük bir feature deploy etmişsiniz, Slack sakin. Bir anda alarm patlıyor: API’niz 502 dönmeye başlamış. Logları açıyorsunuz ve bir endpoint’e dakikada kırk bin istek geliyor, downstream’de kullandığınız ödeme sağlayıcı sizi rate limit’e takmış, bağlantı havuzu dolmuş, sağlıklı trafik bile kuyrukta beklemeye başlamış. Saldırı değil, sadece bir müşteri yeni bir entegrasyon yazmış ve

while (true)
{
    // feature
}

döngüsünde retry yapıyor.

Bu hikayenin yüzlerce varyantı var. Pahalı bir downstream servisin (OpenAI, Twilio, ödeme sağlayıcı) maliyetini kontrol altında tutmak, brute force login denemelerini sınırlamak, multi-tenant SaaS’ta bir tenant’ın diğerlerinin kaynaklarını tüketmemesini sağlamak, background worker’ın veritabanını ezmemesi… Hepsinin ortak çözümü aynı kavramda gizli: rate limiting.

Bu yazıda rate limiting algoritmaları arasında en yaygın kullanılanı olan Token Bucket’ı sıfırdan implement edeceğiz, neden bu kadar popüler olduğunu kavramsal olarak göreceğiz. Ardından ASP.NET Core’un built-in desteğiyle nasıl entegre edildiğini, dağıtık ortamda Redis ile nasıl kullanıldığını ve production’da karşılaşacağımız edge case’leri inceleyeceğiz.

Token Bucket Nedir?

Algoritmayı kodla görmeden önce zihninizde bir kova canlandırın. Bu kovanın sabit bir kapasitesi var — diyelim ki yüz token alıyor. Üstten belirli bir hızla token damlıyor — saniyede on token. Şu anda kova ağzına kadar dolu. Sisteme bir istek geldiğinde kovadan bir token alınıyor. Token varsa istek geçiyor, kova bir azalıyor. Token yoksa istek reddediliyor. Bu kadar basit.

Bu modelin iki kritik parametresi var:

Capacity (Kapasite): Kovanın tutabildiği maksimum token sayısı. Bu, sistemin tolere edebileceği burst büyüklüğünü belirler. Kapasite yüz ve kova doluysa, bir anda gelen yüz isteği herhangi bir gecikme yaşamadan kabul edebilirsiniz.

Refill Rate: Birim zamanda kovaya eklenen token miktarı. Bu, sistemin sürdürülebilir uzun vadeli throughput’unu belirler. Saniyede on token doluyorsa, sistem uzun vadede saniyede on isteği rahatça karşılar.

Sezgisel olarak: kapasite ne kadar burst’e izin veriyorum sorusunu, rate ise uzun vadede ne kadar trafiği taşıyabilirim sorusunu cevaplıyor. Bu ayrım Token Bucket’ı diğer rate limiting algoritmalarından ayıran şey.

Token Bucket tek başına değerlendirilemez. En yaygın alternatiflerle nasıl ilişkilendiğini bilmek, doğru durumda doğru aracı seçmenizi sağlar. İki algoritmayı özellikle iyi anlamak gerekir. Bunlar; Leaky Bucket ve Sliding Window Counter.

Leaky Bucket Token Bucket’a en yakın algoritmalardan biridir. Fakat felsefesi farklıdır. Leaky Bucket kovasından sabit hızla sızıntı vardır. Trafik nasıl gelirse gelsin, çıktı hep aynı hızda akar. Bu, ses/video streaming gibi smooth output gerektiren senaryolar için idealdir.

Token Bucket ise tam tersini yapar: kovaya sabit hızla token gelir ama isteklerin işlenme hızını sınırlamaz. Kovada token olduğu sürece istekler hızlıca geçer. Yani Token Bucket “burst-friendly bir smooth limiter”, Leaky Bucket ise “pure smoother”dır.

Sliding Window Counter ise daha sıkı bir limiter’dır. “Son altmış saniyede en fazla yüz istek” gibi katı SLA’lar için uygundur. Token Bucket bu tür hard limit’i garanti edemez — kapasite kadar burst her zaman mümkündür.

.NET ile Implementation

Peki bu algoritmayı .net ekosisteminde nasıl implemente edeceğiz? Bunu direk göstermenin algoritmanın anlaşılmasını zorlaştıracağını düşünüyorum. Bu yüzden algoritmayı dört aşamada implement edeceğiz. Her aşama bir öncekinin eksiğini giderecek ve bu sayede son aşamada ulaşılan hedefin nasıl geliştiğini daha iyi anlamış olacağız.

Basit Versiyon

İlk versiyon en sade haliyle algoritmayı gösteriyor. Thread safety umrumuzda değil, tek amacımız algoritmanın ne kadar küçük olduğunu görmek.

public class NaiveTokenBucket
{
    private readonly int _capacity;
    private readonly double _refillRatePerSecond;
    private double _tokens;
    private DateTime _lastRefill;

    public NaiveTokenBucket(int capacity, double refillRatePerSecond)
    {
        _capacity = capacity;
        _refillRatePerSecond = refillRatePerSecond;
        _tokens = capacity;
        _lastRefill = DateTime.UtcNow;
    }

    public bool TryConsume(int tokens = 1)
    {
        Refill();
        if (_tokens >= tokens)
        {
            _tokens -= tokens;
            return true;
        }
        return false;
    }

    private void Refill()
    {
        var now = DateTime.UtcNow;
        var elapsed = (now - _lastRefill).TotalSeconds;
        _tokens = Math.Min(_capacity, _tokens + elapsed * _refillRatePerSecond);
        _lastRefill = now;
    }
}

Toplamda otuz satır. Algoritma tam olarak bu kadar. Ama bu kod ASP.NET Core’da bir sıkıntı yaratır: yüzlerce thread aynı anda _tokens değişkenine dokunduğunda race condition garantilidir. Aynı anda gelen iki istek son token’ı paylaşıp ikisi birden geçebilir, ya da Refill çağrısı yarıda kalıp tutarsız değer üretebilir.

Thread-Safe Versiyon

En basit doğru çözüm: her şeyi lock altına almak.

public class LockingTokenBucket
{
    private readonly int _capacity;
    private readonly double _refillRatePerSecond;
    private readonly object _lock = new();
    private double _tokens;
    private DateTime _lastRefill;

    public LockingTokenBucket(int capacity, double refillRatePerSecond)
    {
        _capacity = capacity;
        _refillRatePerSecond = refillRatePerSecond;
        _tokens = capacity;
        _lastRefill = DateTime.UtcNow;
    }

    public bool TryConsume(int tokens = 1)
    {
        lock (_lock)
        {
            Refill();
            if (_tokens >= tokens)
            {
                _tokens -= tokens;
                return true;
            }
            return false;
        }
    }

    private void Refill()
    {
        var now = DateTime.UtcNow;
        var elapsed = (now - _lastRefill).TotalSeconds;
        _tokens = Math.Min(_capacity, _tokens + elapsed * _refillRatePerSecond);
        _lastRefill = now;
    }
}

Lock blokları kısa tutulduğu sürece çoğu API senaryosunda performans açısından yeterlidir. .NET tarafında lock mekanizması oldukça optimize çalışır ve normal yük altında ciddi bir maliyet oluşturmaz. Saniyede on binlerce isteğin işlendiği sistemlerde bile çoğu zaman sorunsuz şekilde kullanılabilir. Ancak yüksek contention oluştuğunda (örneğin tüm instance’ların aynı bucket yapısını paylaştığı ve çok yoğun trafik alan sistemlerde) thread’lerin lock bekleme süreleri artmaya başlar. Bu da latency üzerinde doğrudan etkili olabilir. Bu tip senaryolarda lock-free yaklaşımlar veya daha dağıtık tasarımlar değerlendirilmeye başlanır.

Lock-Free Versiyon

Interlocked.CompareExchange ile atomik compare-and-swap kullanarak lock’sız bir versiyon da yazabiliriz. Bu yaklaşımda token sayısı genellikle double yerine integer tabanlı tutulur. Amaç, atomik güncelleme işlemlerini daha güvenli ve düşük maliyetli hale getirmektir.

public class LockFreeTokenBucket
{
    private readonly long _capacityScaled;       // capacity * 1000
    private readonly double _refillRatePerSecond;
    private long _tokensScaled;                  // tokens * 1000
    private long _lastRefillTicks;

    public LockFreeTokenBucket(int capacity, double refillRatePerSecond)
    {
        _capacityScaled = capacity * 1000L;
        _refillRatePerSecond = refillRatePerSecond;
        _tokensScaled = _capacityScaled;
        _lastRefillTicks = DateTime.UtcNow.Ticks;
    }

    public bool TryConsume(int tokens = 1)
    {
        var costScaled = tokens * 1000L;
        var spinner = new SpinWait();

        while (true)
        {
            var nowTicks = DateTime.UtcNow.Ticks;
            var lastTicks = Volatile.Read(ref _lastRefillTicks);
            var currentTokens = Volatile.Read(ref _tokensScaled);

            var elapsedSec = (nowTicks - lastTicks) / (double)TimeSpan.TicksPerSecond;
            var refillAmount = (long)(elapsedSec * _refillRatePerSecond * 1000);
            var refilledTokens = Math.Min(_capacityScaled, currentTokens + refillAmount);

            if (refilledTokens < costScaled)
                return false;

            var afterConsume = refilledTokens - costScaled;

            if (Interlocked.CompareExchange(ref _tokensScaled, afterConsume, currentTokens) == currentTokens)
            {
                Interlocked.Exchange(ref _lastRefillTicks, nowTicks);
                return true;
            }
            spinner.SpinOnce();
        }
    }
}

Burada bilinçli bir sadeleştirme yapıyoruz. Token sayısı ve refill zamanı ayrı alanlarda tutulduğu için bu iki değerin her zaman tamamen senkron güncellendiği garanti edilmez. Gerçek production sistemlerinde bu tip yapılarda genellikle daha atomik ve tutarlı güncelleme stratejileri tercih edilir. Bu seviyedeki lock-free concurrency konuları başlı başına oldukça geniş bir alan. Bu yazının odağı Token Bucket algoritmasının çalışma mantığı olduğu için detaylara girmiyoruz. Ancak merak edenler CAS (Compare-And-Swap) ve lock-free veri yapıları üzerine kaynakları ayrıca inceleyebilir.

Async Bekleyen Versiyon

Buraya kadarki versiyonlar reddetme mantığıyla çalışıyordu token yoksa hemen false dönüyordu. Bazı senaryolarda, özellikle pull-based pipeline’larda, “token gelene kadar bekle” davranışı daha uygundur.

public class WaitingTokenBucket
{
    private readonly LockingTokenBucket _bucket;
    private readonly double _refillRatePerSecond;

    public WaitingTokenBucket(int capacity, double refillRatePerSecond)
    {
        _bucket = new LockingTokenBucket(capacity, refillRatePerSecond);
        _refillRatePerSecond = refillRatePerSecond;
    }

    public async Task<bool> WaitAndConsumeAsync(
        int tokens,
        TimeSpan timeout,
        CancellationToken ct = default)
    {
        var deadline = DateTime.UtcNow + timeout;

        while (DateTime.UtcNow < deadline)
        {
            if (_bucket.TryConsume(tokens))
                return true;

            // Yeterli token birikene kadar yaklaşık ne kadar beklemeli?
            var waitMs = (int)Math.Ceiling(tokens / _refillRatePerSecond * 1000);

            // 100ms üst sınırı: bir şey yanlışsa erken uyan
            await Task.Delay(Math.Min(waitMs, 100), ct);
        }
        return false;
    }
}

Bu yaklaşım özellikle iki senaryoda değerlidir: kuyruktan job çeken background worker’lar (DB’yi ezmemek için) ve dış API’lere outbound çağrı yapan istemciler (sağlayıcının rate limit’ine uymak için). HTTP request handler’ında pek önerilmez; connection ve thread pool’u tüketir, backpressure’ı yukarı taşımak daha sağlıklıdır.

Yapmış olduğumuz tüm örneklerde amaç algoritmanın çalışma mantığını ve trade-off’larını daha görünür hale getirmekti. Ancak production ortamlarında çoğu zaman sıfırdan implementasyon geliştirmek yerine framework seviyesindeki hazır çözümler tercih edilir. .NET 7 ile birlikte gelen built-in RateLimiter API’si de Token Bucket dahil dört farklı rate limiting algoritmasını standart olarak sunmaktadır.

using System.Threading.RateLimiting;

builder.Services.AddRateLimiter(options =>
{
    options.AddTokenBucketLimiter("api", o =>
    {
        o.TokenLimit = 100;                              // capacity
        o.TokensPerPeriod = 10;                          // her periyotta eklenecek token
        o.ReplenishmentPeriod = TimeSpan.FromSeconds(1); // periyot uzunluğu
        o.QueueProcessingOrder = QueueProcessingOrder.OldestFirst;
        o.QueueLimit = 50;                               // bekleme kuyruğu
        o.AutoReplenishment = true;
    });

    options.RejectionStatusCode = StatusCodes.Status429TooManyRequests;
});

var app = builder.Build();
app.UseRateLimiter();

app.MapGet("/api/data", () => "Hello").RequireRateLimiting("api");

Gerçek dünyada nadiren tek bir global limit istersiniz. Genellikle her kullanıcı, API key veya tenant için ayrı limit gerekir. Bu, partition yapısıyla çözülür:

options.AddPolicy("per-user", httpContext =>
    RateLimitPartition.GetTokenBucketLimiter(
        partitionKey: httpContext.User.Identity?.Name ?? "anonymous",
        factory: _ => new TokenBucketRateLimiterOptions
        {
            TokenLimit = 100,
            TokensPerPeriod = 10,
            ReplenishmentPeriod = TimeSpan.FromSeconds(1),
            AutoReplenishment = true,
            QueueLimit = 0
        }));

Bu yapıda her kullanıcı için ihtiyaç duyulduğunda ayrı bir bucket lazy olarak oluşur. Aktif olmayan kullanıcılar için hafıza tüketimi yoktur. Peki ne zaman framework’ü bırakıp kendi versiyonunuzu yazarsınız? Cevap genellikle “özel kuralınız olduğunda”: kullanıcının abonelik tier’ına göre dinamik refill rate, hafta sonu iki katı kapasite, bir Circuit Breaker ile koordineli çalışan adaptive limit, ya da Token Bucket’ın iki farklı varyantını birleştiren hibrit bir kural. Standart kullanım için her zaman framework versiyonu tercih edilir.

Distributed Token Bucket

Buraya kadar anlattığımız Token Bucket örnekleri tek bir process içinde çalışıyordu. Ancak gerçek sistemlerde genellikle birden fazla API instance’ı bulunur. Eğer her instance kendi bucket bilgisini tutarsa, belirlenen limit instance sayısı kadar genişler. Örneğin 100/s limit tanımlı bir sistem 5 instance ile fiilen 500/s davranmaya başlayabilir. Bu yüzden distributed rate limiting senaryolarında bucket state’i ortak bir yerde tutulmalıdır. Pratikte bu iş için en sık kullanılan çözümlerden biri Redis’tir. Çünkü düşük latency sunar ve Lua script desteği sayesinde birden fazla işlemi atomik olarak çalıştırabilir.

Buradaki kritik nokta şudur: refill ve consume işlemi tek bir atomik işlem gibi çalışmalıdır. Aksi halde iki request aynı anda mevcut token sayısını okuyup yanlış karar verebilir. Redis Lua script kullanımı bu race condition riskini azaltır.

Aşağıdaki örnek, token bilgisini Redis hash içinde tutan basitleştirilmiş bir Distributed Token Bucket uygulamasıdır. Kaynaklar kısmında refere ettiğim redis.io sitesinden alınmış olan örneğin .NET tarafında kullanım şekli ile ilgili örnek aşağıdaki gibidir;

-- KEYS[1]: bucket key
-- ARGV[1]: capacity
-- ARGV[2]: refill_rate_per_sec
-- ARGV[3]: now_ms
-- ARGV[4]: cost
-- ARGV[5]: ttl_ms

local bucket = redis.call("HMGET", KEYS[1], "tokens", "ts")
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local cost = tonumber(ARGV[4])

local tokens = tonumber(bucket[1]) or capacity
local last = tonumber(bucket[2]) or now

local elapsed = math.max(0, (now - last) / 1000)
tokens = math.min(capacity, tokens + elapsed * refill_rate)

local allowed = 0
if tokens >= cost then
    tokens = tokens - cost
    allowed = 1
end

redis.call("HSET", KEYS[1], "tokens", tokens, "ts", now)
redis.call("PEXPIRE", KEYS[1], tonumber(ARGV[5]))

return allowed

.NET tarafında StackExchange.Redis ile çağırıyoruz:

public class RedisTokenBucket
{
    private readonly IDatabase _db;
    private readonly LuaScript _script;
    private readonly int _capacity;
    private readonly double _refillRate;

    private const string LuaText = @"
local bucket = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local cost = tonumber(ARGV[4])

local tokens = tonumber(bucket[1]) or capacity
local last = tonumber(bucket[2]) or now

local elapsed = math.max(0, (now - last) / 1000)
tokens = math.min(capacity, tokens + elapsed * refill_rate)

local allowed = 0
if tokens >= cost then
    tokens = tokens - cost
    allowed = 1
end

redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], tonumber(ARGV[5]))

return allowed";

    public RedisTokenBucket(IDatabase db, int capacity, double refillRate)
    {
        _db = db;
        _capacity = capacity;
        _refillRate = refillRate;
        _script = LuaScript.Prepare(LuaText);
    }

    public async Task<bool> TryConsumeAsync(string key, int cost = 1)
    {
        var nowMs = DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();
        var result = (int)await _db.ScriptEvaluateAsync(
            _script,
            new
            {
                KEYS = new RedisKey[] { key },
                ARGV = new RedisValue[] { _capacity, _refillRate, nowMs, cost }
            });
        return result == 1;
    }
}

Distributed Token Bucket bedava bir çözüm değildir. Her request artık Redis’e gitmek zorunda olduğu için request path’e ek latency eklenir. Aynı veri merkezinde bu genellikle kabul edilebilir seviyededir; ancak cross-region senaryolarda ciddi maliyet oluşturabilir.

İkinci konu failure mode’dur. Redis erişilemez olduğunda sistemin nasıl davranacağı önceden belirlenmelidir. Fail-open seçilirse servis çalışmaya devam eder ama limit korunamaz. Fail-closed seçilirse limit korunur ama kullanıcı istekleri reddedilebilir.

Üçüncü konu hot key problemidir. Global bucket veya çok popüler bir tenant tüm trafiği tek Redis key’i üzerinde toplarsa, ilgili shard darboğaza dönüşebilir. Bu durumda limit anahtarını daha ince granüler tasarlamak veya bazı senaryolarda local + distributed hibrit model kullanmak gerekebilir.

Ne Zaman Token Bucket Kullanmamalı?

Token Bucket oldukça esnek ve güçlü bir algoritma olsa da her senaryo için doğru seçim değildir.

Katı limitlerin gerektiği durumlarda yeterli olmayabilir. Örneğin “saniyede tam olarak 100 istekten fazlası geçmemeli” gibi net bir kontrat varsa, Token Bucket kapasite kadar burst’e izin verdiği için beklenenden daha fazla isteğin kısa süre içinde geçmesine neden olabilir. Bu tip senaryolarda Sliding Window tabanlı yaklaşımlar daha uygundur. Eğer amaç trafiği mümkün olduğunca düz ve sabit akıtmaksa Leaky Bucket daha doğru bir tercih olabilir. Çünkü Token Bucket kontrollü burst’e izin verirken, Leaky Bucket çıkış hızını daha stabil tutmaya çalışır.

Bazı durumlarda ise Token Bucket gereğinden fazla karmaşık kalabilir. Örneğin günlük veya saatlik basit kullanım kotalarında Fixed Window Counter yaklaşımı çoğu zaman yeterlidir. Ayrıca aynı anda birden fazla kaynağın yönetilmesi gereken senaryolarda da Token Bucket tek başına yeterli olmayabilir. CPU, database connection veya dış servis çağrıları gibi farklı kaynakların birlikte sınırlandırılması gerekiyorsa semaphore veya concurrency limiter tabanlı yaklaşımlar daha uygun hale gelir.

Token Bucket oldukça esnek ve güçlü bir algoritma olsa da her senaryo için doğru seçim değildir.

Eğer amaç trafiği mümkün olduğunca düz ve sabit akıtmaksa Leaky Bucket daha doğru bir tercih olabilir. Çünkü Token Bucket kontrollü burst’e izin verirken, Leaky Bucket çıkış hızını daha stabil tutmaya çalışır.

Bazı durumlarda ise Token Bucket gereğinden fazla karmaşık kalabilir. Örneğin günlük veya saatlik basit kullanım kotalarında Fixed Window Counter yaklaşımı çoğu zaman yeterlidir.

Ayrıca aynı anda birden fazla kaynağın yönetilmesi gereken senaryolarda da Token Bucket tek başına yeterli olmayabilir. CPU, database connection veya dış servis çağrıları gibi farklı kaynakların birlikte sınırlandırılması gerekiyorsa semaphore veya concurrency limiter tabanlı yaklaşımlar daha uygun hale gelir.

Kaynaklar;