İçeriğe geç

Token bucket ile rate limiter

Kolay#token-bucket#integer-math~15 dk

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

Hedef zaman
O(n)
Hedef alan
O(n)

Kısıtlar

  • request times are in milliseconds, in order

Kodda değil de fikirde mi takıldın? Rate limiting bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case