Rate limiter

1. Token bucket:
   • Counter and a last request timestamp.
   • Increment counter based on (now - last timestamp) times a fixed rate. Counter shouldn't exceed capacity value.
   • O(1) space but approximate. Allows bursts (upto 2x), but doesn't hard block the client like fixed window. Better choice than fixed window because of no hard block and allowed burst is smoother.
   • The fill rate and capacity are independent parameters allowing us to tweak the burst usage.
   • Redis: LUA script to do the counter update and check.
2. Fixed window:
   • Counts in current timewindow
   • O(1) space but approximate (allows upto 2x burst at the edge)
   • Redis: INCR a counter with EXPIRE set when counter is set to 1
3. Two fixed windows:
   • Counts in current and previous timewindow
   • count = current count + (1 - elapsed proportion) * previous count
   • O(1) space. Approximate but doesn't allow 2x burst.
   • Used by cloudflare. A decent compromise.
4. Timestamps Log:
   • Store last N timestamps in circular buffer
   • Redis: store requests in a sorted set with timestamp as score. Then remove old requests (ZREMRANGEBYSCORE), check the set size (ZCARD), and decide.
   • O(N) with space but exact.
5. Leaky bucket:
   • A FIFO queue of fixed capacity, request are put in queue or dropped. Consume pulls request at a fixed rate.
   • Not a traditional rate limit where yes/no decision is required.
   • Similar to token bucket but the outflow is always smooth.
   • Redis: Use streams.

     • Check stream size and then do

       XADD stream_key <* | id> field value [field value ..]

     • Consumer will fetch unprocessed entries

       XREADGROUP GROUP group_name consumer_name COUNT count STREAMS stream_name >

       (">" means it will fetch new entries not sent to others)

     • process them and then ack. XACK stream_name group_name
     • Periodically, claim from the pending list (items that were sent but not acked), with XCLAIM based on min-idle-time.