分布式应用服务中的流控技术 (第二部分)

[abbshr]

Chapter 3: 切换到分布式环境

前一部分主要是针对流控算法进行的介绍, 下面我们涉入分布式架构, 继续探讨分布式流控技术.

为了实现全局流控, 这里有两个方案可选:

方案A.

每个进程从一个存储系统中获取状态并独占它(加锁), 其他进程要等待这个进程读写等事务完成之后(释放锁)才能获取状态数据. 但这种方案丧失了可用性.

方案B.

进程之间独立, 各自维护自己的状态, 集群内周期性异步通讯以保持状态一致, 但这肯定会有不一致产生, 因此丧失了数据一致性.

所以借用CAP理论, 必须以牺牲一致性或可用性为代价.

既然这样, 没必要追求完美了, 但我们仍然可以根据需求及使用场景灵活选择合适的策略.

精准流控

这里我们首先考虑设计精准流控的方案. 为啥要精准限流?

涉及到money问题, 不得不慎重. :)

所以我们暂时抛弃前面提到的方案B. 这种需求下要保持强一致性!

接下来考虑两个

1. 在调度器上做限流逻辑

理论上这是正确而高效的做法, 因为调度器是一个全局入口, 如果把限流做在这里面, 那问题就很简单了. 但是有几点不得不考虑到:

• 调度器的性能
• 限流模式

限流算法或者请求存储系统(同步阻塞I/O)或者从本地的一张超大的表里查找对应的全局状态, 计算之后放行流量.

另外, 限流模式不确定, 可能根据用户, API id, IP地址或时间段等等策略限流, 这就需要调度器进行不同程度的数据解析, 拿到确定的匹配模式才能做进一步流控, 这也将产生性能损耗.

调度器是整个集群的咽喉要道, 如果这里出现了性能损耗, 那么将会对整个集群的并发能力产生影响!

2. 将限流逻辑分布到工作进程中

Unix设计哲学告诉我们, "write good program that do one thing and do it well".

我们第二个精准流控模型就是这样的. 调度器只做本职工作, 工作进程负责控制全局状态的一致性, 这本来就是它们该做的事.

由此开始, 限流算法衍生为分布式限流算法. 下面讨论这种模型下分布式限流的具体思路.

设计分布式限流算法

这又是一个笼统的话题, 我们先从性能优先考虑.

存储上我们可以选择极好支持分布式的存储系统Cassandra, 也可以选择极速轻量级的Redis. 为了说明细节(也是偏爱), 这里以Redis做存储系统为例.

都需要存储哪些主要数据呢?

首先是几个常量(如果只是试验也可以就放在工作进程内存里):

• threshold
• interval

这是流控配置. 其次是状态变量, 如计数器, 访问时间等等等.

性能优先

性能优先的话, 就是让每个工作进程独立工作, 并各自分配threshold作为最大访问量独立限流.

使用定时器周期性轮询Redis中存储的状态数据更新到本地限流算法的参数上.

由于采用了周期性数据同步, 这种方法无法实现精确的流控效果. 此外, 如counter变量, 他们由于无法控制并发读写而产生严重偏差. 工作进程始终保持绝对的高性能, 但我打赌这肯定不是你想要的.

准确性考虑

为实现精确流控, 在工作进程与redis之间增加一层channel进程.

channel负责实现进程锁: 每次只允许一个工作进程通过, 直到它完成了特定工作主动释放channel或发生超时, 其他进程才可以占用channel. (这种锁的实现可以是单进程+标记文件, 见node-lock的使用)

这样每次读写状态变量时, 无数据竟态产生, 没有进入channel的进程将会在channel的next tick里再次尝试获取channel所有权.

但产生的问题是:

1. 工作进程可能在channel上产生阻塞, 影响执行效率.
2. 为了实现lock/wait语义, channel进程不得不进行反复重试, 肯定会消耗大量资源.
3. 工作进程对某个API上的阻塞操作会直接影响不相关API的调用请求(其他API不得不等待占用channel的进程释放channel).
4. 这种方法只适用于本地进程集群, 换做广义上的分布式系统一致性就失效了.

借助存储系统实现增强版

如果Redis能解决上面的问题, 何不用之?

借助Redis实现锁的机制, 就能够避免工作进程与channel, channel与Redis server的二次通信以及对前一种方案中不同API限流时出现的互相影响局面.

Redis实现锁的思路很简单. 以某个限流模式(如API path)做key, 一个概率上几乎是unique的随机数做value(可以从/dev/urandom读取), worker进程内部维护这一键值对.

加锁实现: 检查这个key是否存在, 是则返回失败, 否则以某个过期时间set这个key.

解锁同样简单: 先检查key是否存在, 如果存在继续检查value是否等于自己保存的, 只有相等才清除这个key.

选择随机数的目的是防止客户端误删其他客户端加的锁, 这种情况往往发生在持有锁超时(可能是任务时间过长或发生网络隔离)后才完成任务时.

看似比较完美的锁方案, 但这只是单实例的Redis啊, 如果存储系统也变成分布式的, 这么做肯定不行.

然而外部持久化基本上都是分布式的, 各大存储产品在节点间的数据同步也有其独门秘籍. 这里仍然拿设计相对简单的Redis为例.

Redis节点之间的主从复制是异步的, 并且多个redis节点的话, 如果仅仅使用前面的方法请求锁肯定会破坏锁的安全语义.

为此, Redis社区提出一种分布式锁算法: Redlock.

分布式锁

RedLock基于前面提到的单实例存储系统的锁实现的分布化. 相比于其他库提供的重量级分布式锁, RedLock的核心则非常简单.

其加锁过程是这样的:

客户端使用单实例锁思路, 生成key:value对.

用这个键值对依次同步的向Redis集群中的节点发起加锁请求, 并为每把锁设置TTL作为自动释放时间. 同时请求时设置超时时间timeout(远远小于TTL), 如果请求超时, 立即放弃这个节点. 记录首次申请成功时的时间戳T1.

每当请求结束, 记录此时的时间戳T2. 如果在满足T2 - T1 < TTL时成功锁住N/2 + 1个节点, 那么就表示加锁成功, 否则加锁失败.

如果加锁失败, 就立即释放刚才锁住的所有节点.

在获取了分布式锁之后, 如何确定超时时间? 在此之前, 我们还需要了解Clock Drift, 即时钟漂移.

时钟漂移是分布式系统中普遍存在的现象. 即每个节点都有自己独立的时钟, 并且他们的速度各不相同.

clock drift是一个因子(factor), 表示速度差, 所以实际的时间偏移量是它与时间差的积. 由于漂移现象诞生了所谓的时钟同步算法. 但RedLock算法中并不强制要求时钟同步.

在RedLock中, 成功获得分布式锁之后, 为了补偿时钟漂移问题, 其生存时间将这样计算:

TTL' = TTL - (T2 - T1) * (1 + CLOCK_DRIFT)

这里的CLOCK_DRIFT将采用一个经验值作为平均值, 一般是10^-6.

解锁非常简单, 可以是主动解锁, 或者超时释放:

主动解锁: 客户端可以并发解锁, 解锁逻辑同单实例解锁方法.
超时释放: 自从第一个申请的锁到期, 就表示分布式锁超时了.

给集群装备免疫系统

到目前为止, 我们介绍了所有精准流控的方法, 但是在更一般的环境里, 我们可能只是需要一个保护机制, 并不严格要求单位时间的访问量.

下面要说的就是这样一种流控思路.

Elastic Quota

多数流控的目的都是为了实现QoS, 所以普遍情况下对流控的要求没那么苛刻.

而我们提供服务时, 实际上允许略微的突发访问产生, 只要没达到服务器压力的极限, 偶尔的超量也是可以放行的, 这就模糊了设定的限度.

因为我们希望给服务消费者提供友好的访问体验, 随着请求速率的增加, 在超过额定限制时, 接下来的请求会在一定概率上失败, 并且失败率随请求次数增加而增大, 直到到达一个底限才100%拒绝服务.

这种平缓的限流策略称作弹性配额.

基本实现思路

为实现集群上的弹性配额, 我们要设定一个因子factor.

quota = threshold * factor

作为interval时间内访问量的最大上限, 起到一个兜底作用.

一个调度进程scheduler独立运行. 监控全部工作进程的访问量变化, 并周期性聚合工作进程的总访问量.

当检测到该时间段内总访问量≥threshold, 计算△d=quota-count的值, 并依据一个配额分配算法按比例划分△d给各个工作进程, 作为其访问量配额(这时工作进程的访问控制是有quota来管理的), 并且随着周期性计算的△d, 分得配额将呈现跳跃变化. scheduler上的还有一个定时器, 以另一个周期resetInterval做counter和quota重置.

Rate Limiting

最后说一个常见的概念, 访问限速. 限速跟开始说的按访问量计费不同, 属于附加保护措施.

同elastic quota相似, 在个别情况下允许一定的异常流量. 但限制的是多数情况下的访问速度尽可能不会超标, 属于那种平缓的限速策略(在访问超速后, 适当的减速仍然可以请求成功而不会在很长一段时间内拒绝服务).

符合这一特点, Leaky Bucket, Token Bucket就可以派上用场了, 前面已经讲过这里不再赘述.

两篇笔记里提到的各种方案实现, 今后会陆续以通用库的形式开源.

[abbshr]

第一部分: #51

[fuhaibo]

@abbshr 集群上的弹性配额，这块我想深入了解下。当节点多的时候，比如20几个。这个调度进程scheduler，压力大吗，有瓶颈吗，是不是也要做个集群或者主备？

[abbshr]

@fuhaibo 肯定要集群化调度器. 我测试时是在一台机器上, 调度器和工作进程都是拿共享内存交换数据的所以调度那边并没有什么压力. 但你所说几十个节点肯定是部署在不同主机上的进程. 通过网络搜集大量工作进程的信息, 如果只是一个调度器, load肯定会高(主要是连接量, 计算量是次要的), 但是每个节点本地部署一个调度器, 他们的压力都不大, 这样部署层级结构的调度集群, 本地调度器作为agent, 跟上级调度器交换信息, 降低每个调度器的连接数和计算量. 但这样做蛋疼之处一是要把配额分配算法并行化, 二是要考虑时延问题(同步变慢导致配额失效)...

[fuhaibo]

@abbshr 那在这些节点上使用某些缓存插件（例ehcache之类的java缓存）实现集群内cache共享，我就不用再单独弄个调度器，配额逻辑都在节点里面做。

[fuhaibo]

会不会好点

[abbshr]

@fuhaibo 我觉得其实都是一个道理, 理论上层级结构调度器也相当于共享cache的server, 也变相的维护一个共享cache, 至于实际效果如何看具体场景, 我也不好说~~

[fuhaibo]

@abbshr 当检测到该时间段内总访问量≥threshold，我想问下，若在这段时间内高并发访问，远超过弹性的最大上限。那怎么做了呢

[fuhaibo]

调度器到某个时间检测总访问量，是不是一开始每个节点都不分配阀值，只是周期内通过调度器来每次统计下总和？

[abbshr]

@fuhaibo 恩, 只知道thresholdfactor, 不分配threshold. 调度器检查到有节点临界请求量临界threshold才开始分配总配额. 如果统计期间请求量超thresholdfactor, 总配额直接清零, 直到下一个重置周期.

[fuhaibo]

@abbshr 那如果统计期间请求量超出很多，那不是这次流控失败了？

[abbshr]

@fuhaibo 不是精确限制, 允许超量存在.

[fuhaibo]

@abbshr 那有可能超很多不是？比如最大限定的是1000，我这统计期间内有可能访问频繁，比如1500。但这1500是我不能接受的流控范围。

[abbshr]

@fuhaibo 对于一个分布式系统来说, 性能(可用性)和一致性肯定二选一了, 绝对精准的限流要以牺牲整体性能为代价, 或者是允许一定范围内的误差, 这个范围怎么定, 要求是否严格, 要看限流算法怎么做. 当前讨论这种限流做法是有这个问题的, (因为是想讨论弹性配额这种架构,当然具体限流算法是架构无关的), 如果需要细粒度控制, 可以用滑动窗口算法精准限流(对单节点绝对严格控制请求量).