分布式限流

2020年7月3日凌晨

4.1k 字 34 分钟

下面所说到的并发数，除了考虑请求接受的速度以外，还需要考虑每个请求的处理时间的。
但是为了方便讨论，这里就假设这些请求都能在较短的时间内完成，在合理的请求速度下，请求不会因为处理时间过长而堆积。

固定窗口计数器

例如每秒钟限制20个请求，每一秒为一个窗口，计数器记录一秒钟的请求数量，超过20次则触发限流，到下一秒计数器重置。
固定窗口计数器能控制总的请求数，但是并发数可能会是请求数的两倍。
例如第一秒的最后面和第二秒的最前面集中了这40次的请求，那么最大并发数就可能是40。

滑动窗口计数器

例如每秒钟限制20个请求，滑动窗口大小为一秒，将每秒划分为十个区间，并且会保存最近的十个区间的请求数量。
当请求来的时候，会对最近十个区间进行求和。如果和大于20次，则触发限流。
滑动窗口计数器只是固定窗口计数器的平滑版本，区间越小，平滑程度越高所需的储存空间也越大。
但是固定窗口计数器有的问题他依然有。

漏桶算法

将请求都放进大小有限的队列（桶）里面，然后以固定的速度从队列里取出请求进行处理（漏桶），如果队列慢了则触发限流。
漏桶算法虽然控制了请求数和并发数，但是当一开始没有请求，然后突然有大量请求，却依然慢吞吞的固定速度取请求。
导致一开始有的资源空闲着，有的请求在等待，降低了吞吐。

令牌桶算法

令牌以固定的速度生成，放在大小有限的桶里，桶满了则令牌丢弃。每个请求都往桶里取令牌，取不到令牌则触发限流。
令牌算法既能控制请求数量，由令牌的生成速度决定。
又能承受突发的大量请求，这个由桶的大小决定，并且桶的大小决定了最大并发数。
假设一开始没有请求，然后突然大量请求，桶里满的令牌一下子就被拿完了，达到最大并发数，并且触发了限流。

令牌桶算法的实现

令牌桶算法是使用比较广泛的限流算法，可以使用redis的lua脚本实现。lua大致的思路是：
+ 根据key获取令牌剩余数量和上次获取令牌时间
+ 如果是第一次获取令牌，默认桶满，令牌取一，更新获取时间，返回成功
+ 根据令牌剩余数量、令牌增长速度、上次获取令牌时间和当前时间，计算到现在令牌应该增长到的数量
+ 判断还有没有令牌可取，没有则返回失败
+ 有令牌则取一，更新获取时间，返回成功

具体的lua脚本这里先贴《分布式服务限流实战，已经为你排好坑了》和《基于redis的分布式限流方案》。
这两个脚本感觉可以合并一下（待续）

《分布式服务限流实战，已经为你排好坑了》

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进行修正
  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

《基于redis的分布式限流方案》

-- key
local key = KEYS[1]
-- 最大存储的令牌数
local max_permits = tonumber(KEYS[2])
-- 每秒钟产生的令牌数
local permits_per_second = tonumber(KEYS[3])
-- 请求的令牌数
local required_permits = tonumber(ARGV[1])

-- 下次请求可以获取令牌的起始时间
local next_free_ticket_micros = tonumber(redis.call('hget', key, 'next_free_ticket_micros') or 0)

-- 当前时间
local time = redis.call('time')
local now_micros = tonumber(time[1]) * 1000000 + tonumber(time[2])

-- 查询获取令牌是否超时
if (ARGV[2] ~= nil) then
    -- 获取令牌的超时时间
    local timeout_micros = tonumber(ARGV[2])
    local micros_to_wait = next_free_ticket_micros - now_micros
    if (micros_to_wait > timeout_micros) then
        return micros_to_wait
    end
end

-- 当前存储的令牌数
local stored_permits = tonumber(redis.call('hget', key, 'stored_permits') or 0)
-- 添加令牌的时间间隔
local stable_interval_micros = 1000000 / permits_per_second

-- 补充令牌
if (now_micros > next_free_ticket_micros) then
    local new_permits = (now_micros - next_free_ticket_micros) / stable_interval_micros
    stored_permits = math.min(max_permits, stored_permits + new_permits)
    next_free_ticket_micros = now_micros
end

-- 消耗令牌
local moment_available = next_free_ticket_micros
local stored_permits_to_spend = math.min(required_permits, stored_permits)
local fresh_permits = required_permits - stored_permits_to_spend;
local wait_micros = fresh_permits * stable_interval_micros

redis.replicate_commands()
redis.call('hset', key, 'stored_permits', stored_permits - stored_permits_to_spend)
redis.call('hset', key, 'next_free_ticket_micros', next_free_ticket_micros + wait_micros)
redis.call('expire', key, 10)

-- 返回需要等待的时间长度
return moment_available - now_micros