# rate limiter

* token bucket
* leaking bucket
* fixed window counter
* sliding window log
* sliding window counter

### purpose

A rate limiter is a tool used to control the amount of traffic that can be sent to a server or application over a specific period of time. By setting a limit on the rate of requests or connections that can be made within a given timeframe, a rate limiter can help prevent Distributed Denial of Service (DDoS) attacks, but not eliminate the ddos, with great amount requests, the system still be overwhelmed.

### token bucket

bucket with token refilled periodically,
2 paramter tune: 1. bucket size(token capacity) 2. refilled rate

pro: memory efficient, could cope with a burst traffic.
cons: hard to tune 2 params


### leaking bucket

use queue record unprocessed task,
queue size as bucket.
two parameter: queue size/ processed rate

pro: memory efficient, suitable for cases that stable outflow rate is needed
cons: hard to tune 2 params,


### fixed window counter

count event each window size, if smaller than limit then processed, or reject.

pros: memory efficient
cons: burst traffic might over the limit


##### burst case


### sliding window log

record each event log timestamp(ex. redis sorted set), when get new event, remove outdated log(those records older than the start of the current time window) and count log within period is under over the limit

pros: avoid the issue when burst events over the limit still can process

cons: memory cost, record all event timestamp


### sliding window counter

record event count in each fixed time window, count the current event with current and previous time window( as event exist in previous window as steady rate)

Requests in current window + (requests in the previous window * overlap percentage of the rolling window and previous window)

pros: memory efficient
cons: work on not-strict look back window

> [3 + 5 * 0.7% = 6.5]

### sorted set do sliding window count

for assigned bucket

batch to do txn in redis

1. remove the record older than current time window.

2. get all window case.

3. add 1 record as the input event

4. set ttl back to redis

exec command

count the current record, if over the limit then skip action.

this method record non processed issue too.

ref:
1. https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/

2. https://github.com/peterkhayes/rolling-rate-limiter/blob/master/src/index.ts