Token bucket ile rate limiter
Görev tanımı
Problem
Bir API gateway (API geçidi) her istemciyi bir token bucket ile sınırlıyor. Bucket en fazla capacity token tutuyor ve 0 zamanında dolu başlıyor. Token'lar saniyede per_second token hızıyla, kapasiteyi asla aşmadan sürekli geri damlıyor ve her istek bir tam token harcıyor ya da reddediliyor. Sırasıyla milisaniye cinsinden istek zamanları verildiğinde, her biri için izin verilip verilmediğini döndür. Dolumlar kesirli; yani saniyede 4 token'da çeyrek saniye tam olarak bir token'dır. Kayan noktadan kaçın ki tam sınırdaki bir istek asla bir yuvarlama hatasıyla reddedilmesin.
Örnekler
Input: capacity = 2, per_second = 1, times_ms = [0, 0, 0, 500, 1000, 3000]
Output: [True, True, False, False, True, True]
Neden: üçlük ani yük iki tane alıyor; 500'deki yarım token yetmiyor; bucket sonra doluyor
Input: capacity = 1, per_second = 4, times_ms = [0, 100, 250, 260]
Output: [True, False, True, False]
Neden: 250 ms'de tam olarak bir token geri gelmiş
Input: capacity = 3, per_second = 1, times_ms = []
Output: []
Neden: edge case: trafik yok
İpuçları
0 / 3
Hiçbir zaman bir zamanlayıcıya ihtiyacın yok. Bucket'ın seviyesi tembel biçimde, bir istek geldiği anda, son istekten beri geçen süreden güncellenebilir.
Kayan nokta sınır durumunu kırılgan yapar. Bunun yerine token'ın binde birleri cinsinden say: o zaman her milisaniye tam olarak per_second binde bir, yani bir tam sayı ekler.
Seviyeyi binde birler cinsinden ve son istek zamanını tut. Her istek için (t - last) × per_second ekle, capacity × 1000'de sınırla ve en az 1000 kalıyorsa isteğe izin verip 1000 çıkar.
- Hedef zaman
- O(n)
- Hedef alan
- O(n)
Kısıtlar
- request times are in milliseconds, in order
Çözüm
Bir token bucket arka planda dolum işine ihtiyaç duymaz: seviye bir istek geldiğinde öncekinden beri ne kadar geçtiğinden yeniden hesaplanabilir; bu, tıkırdayan bir zamanlayıcının vereceği cevabın aynısıdır. Token'ın binde birleri cinsinden saymak her dolumu bir tam sayı yapar, çünkü saniyede per_second token'da bir milisaniye tam olarak per_second binde birdir; böylece tam bir token tamamlandığı anda gelen bir isteğe her zaman izin verilir. Sınır bucket'ın boyutunu modeller; sessiz bir dönemden sonraki ani yükü sınırlayan da budur. Her istek O(1)'dir; bütün çalışma O(n), istemci başına durum O(1).
def token_bucket(capacity, per_second, times_ms):
# count in thousandths of a token so every refill is exact integer maths
full, tokens, last, out = capacity * 1000, capacity * 1000, 0, []
for t in times_ms:
tokens = min(full, tokens + (t - last) * per_second) # refill since last
last = t
if tokens >= 1000:
tokens -= 1000 # spend one whole token
out.append(True)
else:
out.append(False)
return out
print(token_bucket(2, 1, [0, 0, 0, 500, 1000, 3000])) # -> [True, True, False, False, True, True]
print(token_bucket(1, 4, [0, 100, 250, 260])) # -> [True, False, True, False]
print(token_bucket(3, 1, [])) # -> []Kodda değil de fikirde mi takıldın? Rate limiting bunu anlatıyor.