【系统设计】Design Netflix & Design User System & Design Rate Limiter - Road to Glory - SegmentFault

【系统设计】Design Netflix & Design User System & Design Rate Limiter - Road to Glory - SegmentFault

Design Rate Limiter

Requirement

防止爬虫；例如，Kafka中上层producer产生太快限制其他producer的资源。
基本限制 QPS limit = 5

四种算法

1. 隔离算法 —

Make sure the gap between two requests >= 1s/5 = 0.2s

1. 充分满足限制；  2. 但是会误杀很多合理的request，例如0.2 0.4 0.6 0.8 0.9中的0.9         Acquire()  Time now = Time.getCurrentSecond();  if (now - lastReq <= 0.2) return false;  else {      lastReq = now;      return true;  }    

2. 吊桶算法 — time-bucket

Acquire()  Time now = Time.getCurrentSecond();  if (counter[now] >= 5) return false;  else {      counter[now]++;      return true;  }      

Time-bucket with Database: O(1) space

Acquire()  Time now = Time.getCurrentSecond();  counter = DB.get(now);  if (counter != null && counter >= 5) return false;  else {      DB.increase(s, 1);      DB.expire(s, 1);      return true;  }      

Time-bucket: one bucket O(1) space

Acquire()  Time curSecond = Time.getCurrentSecond();  if (curSecond != preSecond) {      counter = 0;      preSecond = curSecond;  }  if (counter >= 5) return false;  else {      counter++;      return true;  }  

Bad Case: 假设0 - 1s正好5个request，但是0.5s - 1.5s中出现了6个request，bucket无法检测任何一个1s区间内的准确性

3. Solution: 队列算法 — Algorithm of Request List

Acquire()  curSecond = getCurrentSecond();  preFifthSecond = requestList.get(requestList.size()-5);  if (curSecond-preFifthSecond < 1) return false; //indicating this is the 6th request in this second  else {      requestList.add(curSecond);      return true;  }      

还是有问题：如果一秒有很多request，比如说one million, 都要记录在request list吗？
Nah...
用一个fixed size(5)的request list + 轮询：只记录最近的5个request

Acquire()  curSecond = getCurrentSecond();  if (curSecond-requestList.get(index) < 1) return false;  else {      requestList.set(index, curSecond);      index = (index+1)%5;      return true;  }    

Follow up 1: how to save space with 10^9 queries per hour?

Batch queries. 损失精度换取空间复杂度。
对邻近时间的query打包，每个包里有10^6个query，这样，就只需要在request list中存储10^3个query/hr，也就是每3.6秒存储一个。

Follow up 2: how to support multiple threads?

Lock.

Follow up 3: how to support limiter on users?

<userId, requestList> 每个用户有自己的request list

Follow up 4: how to support query with different quotas? 不同配额呢

acquire(quota)

4. 令牌算法 — Token bucket

每0.2s产生一个令牌，没有使用的话则累积，供并发请求调用，时间为O(1)

Read full article from 【系统设计】Design Netflix & Design User System & Design Rate Limiter - Road to Glory - SegmentFault