TakéToken bucket algorithm, Token Bucket Filter, TBFPokročilý
Definice
Token bucket je algoritmus pro řízení rychlosti požadavků, paketů nebo úloh pomocí virtuální nádoby s tokeny. Tokeny se doplňují nastaveným tempem až do maximální kapacity a každá akce je spotřebuje. Díky tomu lze omezit dlouhodobý průměr, ale zároveň povolit krátké nárazové špičky.
Nezaměňujte: Token bucket je algoritmus pro řízení rychlosti, nikoli token ve smyslu přístupového údaje nebo jednotky textu.
Jak token bucket funguje
Token bucket modeluje povolenou zátěž jako nádobu s tokeny. Systém do nádoby průběžně přidává tokeny pevnou rychlostí, například deset tokenů za sekundu, ale nikdy nepřekročí nastavenou kapacitu. Příchozí požadavek, paket nebo úloha si vezme jeden nebo více tokenů podle své velikosti nebo ceny. Když tokeny stačí, operace projde okamžitě. Když tokeny chybí, implementace ji buď odmítne, zařadí do fronty, nebo počká na doplnění.
Důležitá jsou dvě čísla: rychlost doplňování a velikost bucketu. Rychlost určuje dlouhodobý průměr, kapacita určuje povolený krátký náraz. API tak může povolit běžně 100 požadavků za minutu, ale současně snést menší vlnu požadavků po otevření stránky. Nevyužité tokeny se do kapacity ukládají, takže klient, který chvíli mlčí, může později krátce poslat více provozu.
Implementace nemusí v každém okamžiku fyzicky přidávat tokeny časovačem. Častější je výpočet při příchodu požadavku: podle času od poslední kontroly se dopočítá, kolik tokenů přibylo, stav se ořízne na maximum a teprve potom se rozhodne. Tento postup je levný a dobře funguje v procesových i distribuovaných systémech.
Kdy token bucket použít a kdy ne
Token bucket se hodí pro rate limiting API, ochranu backendu před špičkami, regulaci front úloh a tvarování síťového provozu. Výhoda spočívá v tom, že algoritmus neškrtí každý krátký výkyv stejně tvrdě jako pevné okno. Uživatel tedy může provést několik akcí rychle za sebou, pokud předtím limit nevyčerpal.
Token bucket není ideální, když pravidla vyžadují přesný počet akcí v kalendářním okně, například striktně nejvýše 100 požadavků od 12:00 do 12:01. Pro takový požadavek se lépe hodí sliding window nebo pevné počítadlo, podle požadované přesnosti. Token bucket také sám neřeší férové rozdělení mezi uživateli, pokud všichni sdílejí jeden bucket.
Na co si dát pozor
Distribuované nasazení je nejčastější zdroj chyb. Více instancí aplikace musí sdílet stav bucketu, nebo musí mít limity rozdělené tak, aby součet nepřekročil záměr. U API se stav často ukládá do rychlého úložiště s atomickými operacemi, protože dvě souběžná volání nesmí spotřebovat stejný token.
Volba reakce na prázdný bucket ovlivňuje uživatelský zážitek. Odmítnutí je jednoduché a dává smysl u veřejného API, typicky s odpovědí HTTP 429. Čekání může být vhodné u interní fronty, ale může také prodloužit latenci a nahromadit požadavky. Důležité je také nastavit cenu operací: upload velkého souboru může spotřebovat více tokenů než jednoduché čtení stavu.
Příklady z praxe
Limit veřejného API
Veřejné REST API povoluje dlouhodobě 20 požadavků za sekundu a krátký burst 40 požadavků. Klient po minutě nečinnosti odešle 30 rychlých dotazů, které projdou, protože bucket je plný. Dalších 30 dotazů hned poté už částí narazí na HTTP 429, dokud se tokeny znovu nedoplní.
function allow(nowMs, bucket) { const elapsed = (nowMs - bucket.updatedAt) / 1000; bucket.tokens = Math.min(bucket.capacity, bucket.tokens + elapsed * bucket.refillPerSecond); bucket.updatedAt = nowMs; if (bucket.tokens >= 1) { bucket.tokens -= 1; return true; } return false; }Tvarování síťového provozu
Edge router používá token bucket pro zákaznický provoz s průměrnou rychlostí podle tarifu. Krátké načtení webu projde svižně, protože uložené tokeny pokryjí špičku paketů. Dlouhý přenos velkého souboru se po vyčerpání bucketu ustálí na smluveném průměru.
Časté omyly
- MýtusToken bucket znamená přesně N požadavků za každou minutu.
- Ve skutečnostiToken bucket nepracuje primárně s pevnými kalendářními okny. Algoritmus hlídá doplňování tokenů v čase a dovoluje krátké špičky podle kapacity bucketu.
- MýtusKdyž je bucket plný, systém může posílat neomezeně rychle.
- Ve skutečnostiPlný bucket dovolí jen burst do své kapacity. Po vyčerpání tokenů se rychlost vrátí k tempu doplňování nebo se požadavky začnou odmítat či zdržovat.
- MýtusJeden globální token bucket stačí pro férové API.
- Ve skutečnostiJeden globální bucket chrání celkovou kapacitu služby, ale neřeší rozdělení mezi klienty. Pro férovost se často používají samostatné buckety pro uživatele, klíče nebo tenanty.
Časté dotazy
- Jaký je rozdíl mezi token bucket a leaky bucket?
- Token bucket omezuje dlouhodobou průměrnou rychlost, ale dovoluje krátké špičky do velikosti kapacity bucketu. Leaky bucket se často popisuje jako odtok konstantní rychlostí, takže provoz vyhlazuje přísněji. V praxi se názvy někdy pletou, protože některé implementace kombinují frontu, čekání a zahazování. Rozhodující je, zda se nevyužitá kapacita ukládá pro pozdější burst.
- Jak token bucket funguje v rate limitingu API?
- Token bucket se pro rate limiting používá tak, že každá identita, například uživatel, API klíč nebo IP adresa, dostane vlastní stav s počtem tokenů. Každý požadavek tokeny spotřebuje a stav se průběžně doplňuje podle času. Když tokeny nestačí, server obvykle vrátí HTTP 429, případně požadavek zpozdí nebo zařadí do fronty.
- Je token bucket férový vůči všem uživatelům?
- Token bucket může být spravedlivý pouze tehdy, když je správně navržený rozsah bucketů. Jeden společný bucket chrání službu jako celek, ale nebrání jednomu klientovi spotřebovat většinu kapacity. Férovější návrh obvykle používá samostatný bucket pro uživatele, tenanty nebo API klíče a někdy přidává ještě globální limit pro ochranu infrastruktury.
- Jak implementovat token bucket ve více instancích aplikace?
- Token bucket v distribuované aplikaci potřebuje konzistentní práci se stavem, protože více instancí může rozhodovat současně. Běžné řešení používá sdílené úložiště s atomickou aktualizací, případně lokální bucket na každé instanci s opatrně rozdělenou kapacitou. Bez synchronizace se limit snadno překročí, protože dvě instance mohou současně vidět stejné dostupné tokeny.
Zdroje
- RFC 2697: A Single Rate Three Color Marker(otevře se v novém okně)
- RFC 2698: A Two Rate Three Color Marker(otevře se v novém okně)
- RFC 3290: An Informal Management Model for Diffserv Routers(otevře se v novém okně)
- Token bucket(otevře se v novém okně)
Související pojmy
