系统限流
最近在系统中对一个资源访问做了限流，写篇文章聊聊这个话题。
为什么要限流
在衡量Web系统性能的指标中，最重要的参数是极限QPS，它表示系统每秒最多能够处理的Query数。从定义中可以知道QPS是一个描述系统处理速度的指标，当存在需要处理的流量（Query数）使得系统即使以极限QPS处理也无法在短时间内处理完所有流量，则称这个段时间内系统处于承压状态。
当系统处于承压状态，容易理解超出系统能力的那部分流量无法正常处理，可系统能力范围内的那部分流量也无法正常处理则比较反直觉。
假设某API的极限QPS是200，即理论上一分钟可以处理的Query数为12000(200 x 60)，如果在持续一分钟的时间内每秒收到300个Query，原以为系统依旧能处理12000个Query，只有6000个Query无法处理，实际情况可能是前10s处理2000个Query后系统就处于异常状态，接着其他Query都无法在正常时间内得到处理
由于系统承压导致原本1分钟可以处理12000个Query骤降为2000，更致命的是接着的几分钟甚至几十分钟内系统QPS将持续保持一个相对较低的值，甚至系统完全无法正常运行，这种性能表现模式对大部分系统都比较常见，原因在后一小节分析。
大部分系统无法长时间处于高压状态，一旦承压程度超过一定的阀值，系统性能表现会急剧下降，而为了解决这一问题所普遍采用的方案是在系统中实现限流策略，始终保持系统压力处于合理范围从而让系统整体效率最高。
QPS/TPS tips:
QPS全称是Query Per Second，TPS则是Transaction Per Second，中文可以翻译成每秒查询数与每秒事务数，但查询与事务两者的定义用来形容Web Server的request与response都不是完美契合，可概念相似，即我们可以把对Web Server的QPS描述理解成每秒能够完成的request与response数量，后文也就使用Query指代Request与Response
承压导致性能骤降的原因
系统承压会导致性能表现下降严重甚至无法提供服务，导致这一切的原因是由于一定时间内用来达成目标的可用资源（CPU、内存、带宽、IO等）不足进而出现相互争夺资源的情况，最终导致目标一直无法达成，且争夺过程本身也会对资源造成额外的负担。
举个例子，假设某CPU每秒可提供的计算能力用数值100表示，某类型任务1s完成需要的计算能力为1，那么此CPU每秒最多完成100个该任务，而当CPU每秒收到200个任务时：
- 1s后，100算力平分给200个任务，每个任务完成度是0.5
- 2s后，100算力平分给400个任务（1s:200 + 2s:200），1s:200完成度0.75，2s:200完成度0.5
- 3s后，100算力平分给600个任务（1s:200 + 2s:200 + 3s:200），1s:200完成度0.91，2s:200完成度0.66，3s:200完成度0.16
- 4s后，100算力平分给800个任务（...），1s:200全部完成，后几秒的任务完成度依旧小于1
- 继续一段时间后发现任务越来越难完成，从外部看CPU虽然满负荷运行但已经完全无法完成任务
100算力每次都能平分给所有任务只是理想模型，现实情况是任务之间争夺CPU有额外开销，100个任务争夺100算力的CPU也许每个任务只能得到0.8，而200个任务争夺100算力可能导致每个任务只有0.3。
上述CPU例子中，如果外部任务数下降后系统能够恢复正常，勉强能接受，可现实情况往往是系统的部分承压会牵连其他部分。比如上诉的任务其实是HTTP请求，由于CPU资源不够导致系统堆积了1万请求，那这1万个请求涉及的内存需求能否被满足？1万请求的内存需求可以满足，10万呢？如果不能很好的解决承压问题，系统迟早被拖垮。
限流场景
通过前面两节已经明白限流的原因是为了避免系统过载，但没有明确主体，即谁保护谁。第一个“谁”默认是当前系统，而针对第二个“谁”我认为有两种选择：被依赖方、自己。
保护被依赖方
保护被依赖方指的是作为调用方控制自己调用被依赖方的频率，不让因自己调用产生的压力超过被依赖方极限承压能力，用可持续发展的方式让被依赖方持续提供服务。
除了保护被依赖方的正常运行，这么做还可以保护自己，假设自己是一个Web Server，向外提供的API接口平均QPS是1000，这其中有一个接口依赖的第三方服务QPS只有100，如果我们不保护这个第三方服务，当其承压时可能会拖垮自己，因此需要在这个接口内部保护此第三方服务让其不处于承压状态。
上诉场景中保护第三方服务的目的是避免拖垮自己，但也有其他更直接原因：
- 第三方服务缺少自我保护能力，这导致第三方服务无法在承压状态正常工作
- 第三方服务的QPS与自己差距较大，如果自己能支持QPS也只有100，保护该第三方就没多大必要
在写这篇文章的同时，经过思考认为大部分情况下保护被依赖方是一个伪需求，主要原因如下：
- 为了保护自己而保护被依赖方可转换成直接保护自己
原本能支持1000QPS的接口受到被依赖方的QPS限制只能支持100QPS，可以由保护被依赖方变成保护自己，即人为控制自己系统中该接口的调用QPS不超过100，间接也对被依赖方产生保护效果
- 被依赖方不确定会被哪些以及多少依赖方依赖，从而使得对被依赖方的保护措施是做无用功
假设存在极限QPS为200的系统A，而它被B、C系统依赖，哪怕B、C系统为A做了保护措施也不一定能避免A承压异常，因为B、C只能控制自己调用A的QPS不超过200，但两者加起来却可能达到400
- 被依赖方实现自我保护是上策
一个被依赖方被多方依赖，如果坚持让依赖方做流量保护，那么这些依赖方之间会增加耦合度，因为它们一定存在共享内容，比如上述B、C依赖A的例子，B、C为保护A的QPS不超过200，它们之间肯定会共享A的QPS信息，这种做法导致B、C系统之间增加了耦合度，所以被依赖方自我保护是上策
保护自己
保护被依赖方是一个不被推荐的方式，保护自己则是比较可取的方式，保护自己的目的是确保系统处于一定承压状态时依旧可正常运行。
假设系统某接口在没做限流保护时的极限QPS是200，紧接着的一分钟系统面临QPS压力保持在300，未做限流保护时，系统这一分钟内能完成的Query数远小于12000，而通过限流保护可使系统在这一分钟内能够完成的Query数尽可能接近12000，另外的6000丢弃或者排队。
这种自我限流保护可以让系统在承压状态保持正常运行不至于瘫痪，一旦压力缓和，系统随即恢复正常。
自我限流保护的基本原理是控制争夺资源的Query数不超过极限值，且实施控制的成本要尽可能的小，比如一个没加限流控制逻辑的接口极限QPS是200，增加了限流控制后极限QPS变为198，这几乎没影响。
限流的两个维度
我认为限流可以从两个主要维度考虑，分别是速率与并发，它们与前文反复提到的QPS有很大联系。QPS100是指每秒可以处理100个Query，但并未说明并发数与平均处理时间，100QPS可以理解成并发为1时每个Query处理花费10ms，也可以理解成并发为2时每个Query处理花费20ms，又或者是并发为100时每个Query处理花费1s。
上述3种并发与平均处理时间的假设关系不一定成立，一般而言系统极限QPS是指系统在某个合理范围内的并发下能得到的最大值，当并发数超过或者低于该范围时QPS都会下降，因为并发数减少会导致资源利用不完全，因此处理时间不会线性缩短，而并发数的增加会导致资源不够用，从而处理时间变长。
并发数、平均处理时长和QPS，由于平均处理时长受限于具体的业务逻辑，无法直接控制与优化，故我们从并发数与QPS（速率）着手进行限流。
速率
限制速率是控制系统的实际QPS，假设系统某API的极限QPS是100，速率控制可以在入口处保证每秒最多准入90个Query，超出部分丢弃或排队。如果没有异常情况，被准入的90个Query都应该能在这1秒内被处理完，因此系统不会堆积处理中的Query，也就不会拖垮系统。
并发
光有上述速率限制还不够可靠，因为一些不可预知的外部因素可能导致系统可用资源波动。紧接前面速率的例子，原本系统CPU的100算力都会被用于处理准入的90个Query，所以都能在1秒内处理完，但这时系统中出现一个其他任务争夺CPU，它持续30秒占用了50算力，此情况下入口处持续每秒准入90个Query，由于算力只有之前的一半，这被准入的90个Query在1秒后完成度只有0.5，下一秒又来了90个Query，最终系统这个接口将处于瘫痪状态，且不确定会不会引发其它问题，也不确定多久能恢复。
为避免上述问题，我们需要在速率的背后加上一道并发限制的关卡，速率限制1秒内准入90个Query，接着并发限制依据前1秒准入的90个Query完成情况决定这次放行多少，这样可以缓解系统承压状态。
速率VS并发
从上面速率与并发的讨论中，可以知道只有速率控制不足以规避风险，那只用并发控制是否可以达成目标？答案是也不可靠，因为并发控制无法很好的处理瞬时并发流量，而速率控制可以有效平衡瞬时并发流量的时间分布。
针对QPS1000的系统接口做速率控制，入口每秒准入1000个Query，但准入的细节前面并没有提及，可以是一秒开始的瞬间把1000个Query放进去，也可以是每1毫秒放入一个Query，这两种不同的策略对系统的运行产生的影响相差甚大，因为瞬间准入1000个Query可能将系统直接击垮，细水长流的方式则不会让系统有任何波澜。
只做速率控制无法良好应对资源抖动，只做并发控制无法很好处理瞬时流量，所以一个追求极致的系统应该是这两道保险措施都加上。
我个人认为速率控制可以保守一点，即比极限QPS小，而并发控制可以激进一些，并且当实际流量达到到并发控制的阀值时，系统可以实施一些其它策略，比如暂停准入一小段时间。
限流算法
为了实现前面的速率与并发控制，我们需要一个合适且性能优秀的算法，这里主要介绍漏桶与令牌桶算法，
漏桶
图片来源阿里某博客
漏桶算法与令牌桶算法都是形象易理解的，漏桶算法是不管外部流量以何种并发与速率到达系统，都把它们暂存在一个“桶”中，同时这个桶以恒定速率往外流出流量，桶满的时候丢弃或排队到达系统的流量，用漏桶比喻这个过程非常形象和贴切。
令牌桶
图片来源阿里某博客
漏桶算法在任何情况下都保证流量以恒定速率准入，但这不一定是最佳，假设某API使用漏桶实现限流且支持的QPS为100，某瞬间有20个Query到达系统需要被处理，漏桶会保持每10ms准入一个Query，假设此情况下每个Query处理完成的平均时间为200ms，则这20个Query共花费6100ms，计算方式是20个Query的等待时间(10 + 20 + 30 + ... + 200 = 2100)加上执行时间(200 * 20 = 4000)，实际上我们可以同时准入20个Query，这时每个Query的平均响应也许由200ms变为220ms，但20个Query最终花费的时间只有4400ms，通过该优化我们让用户节省了30%的等待时间。
令牌桶就是可以满足上述场景中的期望的算法，允许一定量的瞬时并发同时又限制整体速率。令牌桶算法单独维护一个令牌桶，桶中初始令牌数为b(burst)，每次准入必须消耗一个令牌，同时会有人以恒定速率往桶中添加令牌且保持令牌数小于等于b。
针对前面的100QPS希望瞬时准入支持20的场景，我们可以借助一个burst=20且令牌添加速率为10ms/个的令牌桶实现，当系统瞬间收到100Query的行为是立即准入20个，随后每10ms准入一个。
限流的实现
解释完漏桶和令牌桶限流算法后，我们用代码来实现一番，主要包含两段代码：
- 借助Redis实现分布式令牌桶算法做速率限制
虽然在令牌桶算法中把加令牌操作描述为由“另外一个人”完成，可此方式必须依赖定时器且效率低下，所以这里采用的是一个优化方案：“将加令牌操作合并在取令牌操作中”
- 模仿计算机PV原语实现并发限制
把允许的并发数作为资源S看待 P(S)表示申请一个资源，S减1，若减1后S>=0则准入；若减1后S<0，表示已无资源可用，将自己放入阻塞队列 V(S)表示释放一个资源，S加1，若加1后S<=0，从阻塞队列上取第一个准入
令牌桶限制速率
以下是一个用于速率限流的令牌桶模块示例，代码主要为了传达核心逻辑，但展现完整的速率限流方案。
// rateLimit.js
const _ = require('lodash');
const BB = require('bluebird');
const lib = require(process.env.lib);
const redis = lib.redis.createClient();
const keyPrefix = 'lib:rate-limit';
const id2Limit = {};
// 在Redis中用hset存储了一个对象{rate, burst, permits, last_ms}数据
// 令牌桶的核心逻辑在luaScript中，每次eval调用即申请ARGV[1]个令牌
const luaScript = `
local apply_permits = tonumber(ARGV[1])
local current_ms = tonumber(ARGV[2])
local rate_limit = redis.call("HMGET", KEYS[1], "burst", "rate", "permits", "last_ms")
local burst = tonumber(rate_limit[1])
local rate = tonumber(rate_limit[2])
local permits = tonumber(rate_limit[3])
local last_ms = tonumber(rate_limit[4])
local reverse_permits = math.floor(((current_ms - last_ms) / 1000) * rate)
local remaining_permits = math.min(reverse_permits + permits, burst)
if (reverse_permits > 0) then
redis.call("HSET", KEYS[1], "last_ms", current_ms)
end
local result = 0
if (remaining_permits - apply_permits >= 0) then
result = apply_permits
redis.call("HSET", KEYS[1], "permits", remaining_permits - apply_permits)
else
redis.call("HSET", KEYS[1], "permits", remaining_permits)
end
return result
`;
exports.init = init; // 初始化令牌桶
exports.applyPermits = applyPermits; // 申请令牌
exports.waitPermits = waitPermits; // 等待令牌，在超时时间内自动重试申请令牌
async function init(id, rate, burst) {
let key = `${keyPrefix}:${id}`; // redis中速率控制的key
let args = _.flatten(_.toPairs({
rate, // 令牌桶添加令牌的速率(个/s)，计算时采用毫秒
burst, // 令牌桶最大令牌数，决定瞬时并发数
permits: burst, // 令牌桶中当前的令牌
last_ms: Date.now() // 最后一次添加令牌的毫秒时间戳
}));
await redis.hmsetAsync(key, ...args);
id2Limit[id] = {
rate
};
}
async function applyPermits(id, count = 1) {
let key = `${keyPrefix}:${id}`;
return await redis.evalAsync(luaScript, 1, key, count, Date.now()) === count;
}
async function waitPermits(id, count = 1, timeout) {
if (_.isEmpty(id2Limit[id])) {
throw new Error(`rate limit not initialized id:${id}`);
}
let key = `${keyPrefix}:${id}`;
let {
rate
} = id2Limit[id];
return await new BB(async(resolve, reject) => {
let hasPermits = false;
let timeouted = false;
// 等待令牌超时
setTimeout(() => {
resolve(false);
timeouted = true;
}, timeout);
try {
do {
// 在此处申请令牌过程中恰好超时，会导致count个令牌浪费
hasPermits = await applyPermits(id, count);
if (!hasPermits) {
// 未申请到令牌，随机延迟一定时间后再尝试申请
await _sleep(Math.floor(1000 / rate + Math.random() * 200));
}
}
while (!hasPermits && !timeouted);
if (hasPermits && !timeouted) {
resolve(true);
}
}
catch (err) {
reject(err);
}
});
// 模拟sleep
async function _sleep(ms) {
return await new BB((resolve) => {
setTimeout(() => resolve(), ms);
});
}
}
PV限制并发
以下是一个用于限制fn并发调用数的PV代码示例，代码主要为了传达核心逻辑，但不是完整的并发限流方案。
const _ = require('lodash');
const BB = require('bluebird');
const lib = require(process.env.lib);
const redis = lib.redis.createClient();
const keyPrefix = 'lib:invoke-limit';
const id2Item = {};
exports.init = init; // 初始化id对应的并发数（资源数）
exports.invoke = invoke; // 某id对应的一次调用
async function init(id, concurrency) {
let key = `${keyPrefix}:${id}`;
await redis.setAsync(key, concurrency); // 此处concurrency即资源S
id2Item[id] = {
queue: []
};
}
async function invoke(id, timeout, fn) {
if (_.isEmpty(id2Item[id])) {
throw new Error(`invoke limit not initialized id:${id}`);
}
let {
queue
} = id2Item[id];
let fulfiled = false;
try {
return await new BB(async(resolve, reject) => {
try {
if (await _P(id) >= 0) {
return resolve(await fn());
}
queue.push(async() => {
try {
// 假设在被wakeup前已经超时，不应该执行fn
!fulfiled && resolve(await fn());
}
catch (err) {
reject(err);
}
});
setTimeout(() => {
reject(new Error(`overload id:${id}`));
}, timeout);
}
catch (err) {
reject(err);
}
});
}
finally {
fulfiled = true;
if (await _V(id) <= 0) {
let wakeup = queue.shift(); // 从等待队列首部进行唤醒
wakeup && await wakeup();
}
}
}
// 此处是id对应的资源S执行P操作
async function _P(id) {
let key = `${keyPrefix}:${id}`;
return await redis.incrbyAsync(key, -1);
}
// 此处是id对应的资源S执行V操作
async function _V(id) {
let key = `${keyPrefix}:${id}`;
return await redis.incrbyAsync(key, 1);
}
关于系统限流的话题就写到这吧，有点累...