Token Bucket Algorithm

Being used by both Amazon and Stripe. The algorithm is as follow:

• We have a bucket with n capcity tokens
• There is a refiller which will refill x token per second/minute/hour, ...
• Each request will consume 1 token.
  • If we don't have enough token, we drop the request

Example

Parameters

• BucketSize: maximum token allowed in 1 bucket
• Refill rate: how many token do you put in per second

So how many bucket: normally we do 1 API 1 bucket because each API has different throttling rule. For example 1 user can add 1 post per second, make 150 friends per day, ...

Pros and Cons

Pros

• Memory efficient because of limited bucket size
• Easy to implement
• Allows burst traffic in short periods. Request can go through as long as there are token

Cons

• Parameters are hard to tune