[date: 2019-05-05 00:35] [visits: 11]

系统限流

最近在系统中对一个资源访问做了限流,写篇文章聊聊这个话题。

为什么要限流

在衡量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个任务时:

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,如果我们不保护这个第三方服务,当其承压时可能会拖垮自己,因此需要在这个接口内部保护此第三方服务让其不处于承压状态。

上诉场景中保护第三方服务的目的是避免拖垮自己,但也有其他更直接原因:

在写这篇文章的同时,经过思考认为大部分情况下保护被依赖方是一个伪需求,主要原因如下:

原本能支持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准入一个。

限流的实现

解释完漏桶和令牌桶限流算法后,我们用代码来实现一番,主要包含两段代码:

虽然在令牌桶算法中把加令牌操作描述为由“另外一个人”完成,可此方式必须依赖定时器且效率低下,所以这里采用的是一个优化方案:“将加令牌操作合并在取令牌操作中”

把允许的并发数作为资源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);
}

关于系统限流的话题就写到这吧,有点累...