为什么需要限流？

计数器算法 (Fixed Window Counter)

  • window_start_time
  • counter
  • limit = rate * window_size
  • window_size
    初始化：
  • counter=1
  • window_start_time = 初始时间戳
    请求到来
  • 根据请求到来的时间戳判断是否超过当前时间窗口
    • 超过：window_start_time=当前请求时间戳
    • 未超过：counter>limit
      • 大于：拒绝请求
      • 小于等于：counter++ 允许请求

滑动窗口算法

基于日志(Sliding Window Log)

  • window_start_time
  • counters[]
  • limit = rate * window_size
  • window_size
    初始化
  • 维护一个有序列表(队列最佳)，记录请求带来的时间戳序列
    请求到来
  • 清除now_time-window_size之前的请求记录
  • 当前列表数量<limit?
    • 是：允许请求，将当前请求的时间戳加入列表
    • 否：拒绝请求

      基于分格(Sliding Window Counter ) More Common

  • limit = rate * window_size
  • window_size = sub_window_count * sub_window_size
  • sub_window_count
  • counters[sub_window_count] 哈希表
    初始化:
  • counters中计数器为0
    请求到来
  • 计算窗口起始位置 window_start_time = now-window_size
  • 清理起始位置之前窗口(定时),通过清理sub_window_size * key< window_start_time的元素
  • 计算当前窗口总数： total_count = 累加counters 中的值，key值应该在(window_start_time之后)
  • 判断是否超限：total_count>=limit?
    • 是：拒绝请求
    • 否：接受请求，确定计数器累加的窗口key = now/sub_window_size
      • 存在该key，计数器++
      • 不存在该key，创建key，val=1

        漏桶算法 (Leaky Bucket)

        状态
  • 上次请求时间戳 last_time
  • 桶容量
  • 上次桶水量 lastwater
  • 速率 rate
    请求到来
  • 获取漏水量=(now-last_time) * rate
  • 获得桶水量 = current_water-漏水量
  • 判断当前桶是否满
    • 是：拒绝
    • 否：当前桶水量++，放行请求。last_water=当前桶水量

      令牌桶算法 (Token Bucket)

      状态
  • 上次令牌数量 last_token
  • 最大token数量 max_token
  • 速率 rate
  • 上次请求时间 last_time
    请求到来:
  • 计算添加令牌 add = rate * (now-last_time)
  • 计算当前令牌 = min(last_token+add,max_token)
  • 判断是否存在令牌 当前令牌>0
    • 存在：当前令牌— 允许请求
    • 不存在：拒绝请求