Limiting Traffic

发表于 | 分类于

Algorithm

Leaky Bucket - 漏桶

The image shows the usage of leaky bucket algorithm in traffic shaping. If we map(与..有关)) it our limiting requests to server use case, water drops from the faucets(水龙头) are the requests, the bucket is the request queue and the water drops leaked from the bucket are the responses. Just as the water dropping to a full bucket will overflow, the requests arrive after the queue becomes full will be rejected.

Token Bucket

Suppose there are a few tokens in a bucket. When a request comes, a token has to be taken from the bucket for it to be processed. If there is no token available in the bucket, the request will be rejected and the requester has to retry later. The token bucket is also refilled per time unit.

Fixed Window Counter

Sliding Window Log

Sliding window log algorithm keeps a log of request timestamps for each user. When a request comes, we first pop all outdated timestamps before appending the new request time to the log. Then we decide whether this request should be processed depending on whether the log size has exceeded the limit. For example, suppose the rate limit is 2 requests per minute:

Sliding Window

Reference