What is Token Bucket and Leaky Bucket algorithms
Both algorithms are traffic shaping algorithms that used to control traffic, originally that used in packet switched computer networks and telecommunications networks. Nowadays, we usually use for ecommerce campaign and control requests, e.g. we could use it controls stress test maximum QPS.
Token bucket Diagram
- Rate Limiting: produce rate of token
- Bucket Sizes: number of token
- Token Check: if token valid, process data
- Golang library: https://godoc.org/golang.org/x/time/rate#Limiter
Leaky bucket Diagram
- Rate Limiting: consume rate of data
- Bucket Sizes: number of data
- Golang library: https://github.com/uber-go/ratelimit
Token bucket vs. Leaky bucket
| Token bucket | Leaky bucket |
|---|---|
| The token bucket is an algorithm that can be used to check that data transmissions, in the form of packets, conform to defined limits on bandwidth and burstiness. | The leaky bucket is an algorithm that can be used to determine whether some sequence of discrete events conforms to defined limits on their average and peak rates or frequencies. |
| The output rate vary depending on the size of burst. | The input rate can vary but the output rate remains constant. |
| If bucket is full, token are discarded but not the packet. | If bucket is full, packet or data is discarded. |
| It is Token dependent. | x |
Case study
-
Leaky bucket algorithm used to stress test.
For stress test, we use leaky bucket to make the brust of requests to constant, e.g. create 600 query per second (1 request per 100ms).
-
Token bucket algorithm used to booking.
For booking, we use token bucket to make the limitation of requester, e.g. sell 600 tickets for campaign per second (redirect others requester to queue).
