System - Rate Limiter

Posted at 2022-05-30Updated at 2022-05-30 interview  interview system 

Designing a Rate Limiter

Protect system from DDoS or abnormal user requests.

# Basics

# Fixed Window

Reset Counter

# Slide Window

Multiple Window

# Leaky Bucket

Buffer requests in a queue

# Token Bucket

Buffer tokens in a queue, request try to get token

# Requirements

# Functional Requirements

1. limit number of requests
2. error on single server / cluster

# Non-functional requirements

1. Highly available
2. Performance

# Estimation

# Memory Estimation

Key:{LastTime,CurrentTokenCount}

Key={service}:{resource}:{uid}

Let’s assume we are keeping all of the data in a hash-table. Let’s say we have a structure of key-value pair. The key would be the hash value of user ID, and the value would be a structure of count and startTime, e.g., UserId {Count, StartTime}

Now, let’s assume ‘UserID’ takes 8 bytes and 2 bytes for ‘Count,’ which can count up to 65k, which is sufficient for our use case. Although the end time will need 4 bytes, we can store only the minute and second parts. The hour part is not necessary if we are not considering a window of an hour. Now, it will take 2 bytes. So, we need a total of 12 bytes to store a user’s data.

Now, if our hash-table has an overhead of 20 bytes for each record and we need to track 1 million users at any time, the total memory we need would be :

$32 bytes * 1 million user * 128 => 4096MB => 4GB$

# Domain Model

# Single Server

Persistence: DB

# Service In Cluster

Availability: Multiple Rate Limiter Instances, DB Cluster
Performance: Cache, In-Mem DB
Lock: Lock-free Redis, Distributed Lock

# Practical

Redis+lua分布式限流器 固定窗口法
Redis+lua分布式限流器 令牌桶法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

local ratelimit_info = redis.pcall('HMGET',KEYS[1],'last_time','current_token')
local last_time = ratelimit_info[1]
local current_token = tonumber(ratelimit_info[2])
local max_token = tonumber(ARGV[1])
local token_rate = tonumber(ARGV[2])
local current_time = tonumber(ARGV[3])
local reverse_time = 1000/token_rate
if current_token == nil then
  current_token = max_token
  last_time = current_time
else
  local past_time = current_time-last_time
  local reverse_token = math.floor(past_time/reverse_time)
  current_token = current_token+reverse_token
  last_time = reverse_time*reverse_token+last_time
  if current_token>max_token then
    current_token = max_token
  end
end
local result = 0
if(current_token>0) then
  result = 1
  current_token = current_token-1
end
redis.call('HMSET',KEYS[1],'last_time',last_time,'current_token',current_token)
redis.call('pexpire',KEYS[1],math.ceil(reverse_time*(max_token-current_token)+(current_time-last_time)))
return result