作者：harkinli 腾讯CSIG工程师
|导语 在Node服务开发中，常常需要对许多批量请求进行限频发送，以保证被调用方的系统安全或者调用限制，这里以企业微信API的客户标签修改为例，讲述在企业微信API的限频要求下的分布式限频模块的算法和设计细节。
01
前言
后端服务是十分重视容灾和负载的，特别是在系统的承载服务急剧增加之后，各种性能瓶颈就开始出现了，其中比较常见的则是对高并发下场景的调用支持程度。本篇文章并不是介绍如何去设计支持高并发的系统设计，这整个主题过于庞大，小编也是在学习之中，待有所收获后和大家分享。
在业务开发中，我们更多的是会遇到我们所依赖的业务系统为了应对高并发场景而采用的限频设计， 本质是对第三方业务系统的限流，保证系统不会被第三方业务系统的过高流量而服务崩溃。这里以企业微信API的高并发下的调用限制则是：每个 IP 的调用不得超过 20000 次/每分钟，而我们的业务系统中许多批量任务调用速度往往会超过这个限制，导致整个服务被企业微信官方限制服务，到这里实际也就引申楚今天的主题：如何做分布式调用限频限流的开发设计来保证服务能够稳定持续运行下去。
02
需求
在业务系统中，用户需要对所有客户对批量的标签标注，来赋予每个客户其在业务系统中的属性和特色，方便管理。
需求要点：
1、支持所有用户(客户数是百万级别)的批量修改也能够支持单个用户的修改；
2、服务稳定，请求耗时不可过长，能够满足前端调用需要；
3、批量任务要保证全部执行完成。
当然需求描述是很简单，接下来我们对功能进行拆解。
Node的服务器目前共有深圳、南京、广州三地机房的服务器，共有 15 个 POD 实例（每个实例拥有一个独立 IP），每个实例拥有 8 个 worker 进程。负载均衡假定是平均分配的话，理论上系统能够支持 2000 / 60(s) * 15 (IP 数) = 5000 TPS 的并发请求。
03
方案设计
这里首先介绍下 “流量整形” 概念，wikipedia解释是一种控制网络数据包传输的技术，通过控制数据速率使数据较为均匀发送。流量整形可以一定程度减少网络拥塞，并减弱突发流量带来的影响。限频限流的思想就来自于流量整形，其解释是：在一个指定的速率上分发许可（permit）,当每次来请求的时候，线程会阻塞，直到获取到可用的permit，使用完这些permit之后不需要进行释放的操作。
常见的限频策略有：计数器、固定窗口、滑动窗口、漏桶算法(Leaky Bucket)、令牌桶算法(Token Bucket)、分布式限流。这里我们先从业务本身出发，按照业务本身的细节逐步介绍和分析。
计数器 固定窗口方案
既然要做限频调用，那么我们一般第一个想到的是对每次调用进行计数，如果调用次数超过限制则堵塞请求，每个单位时间开始时去清除计数。这是简单的固定窗口 计数器方案。
这里解释下什么固定时间窗口，就是你的单位时间是一旦固定在每个时刻的开始和结束位置，是无法移动和调整的，例如单位时间是一秒，那么它就必须是在一秒的开始和一秒的结束，而无法调整。
这个方案看似已经很好，但是在分布时场景下就会存在一些缺陷，其计数维护将是一个很麻烦的过程，而且这个上限往往是在系统初始化时就设定好了，无法灵活变更，因此我们需要更好的方案。
令牌桶算法(Token Bucket)
漏桶算法是网络世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）时经常使用的一种算法。
当每个请求到来时，首先去 token 桶中获取 token，如果获取到则执行并移除一个 token，否则丢弃此次请求；同时存在一个定时器，在每个单位时间向 token 桶投递一定数量的 tokens，若最终 tokens 的总数超过上限 b，则会移除多余部分。
这种方案通过 tokens 的投放速率来控制整体的执行速度， 通过控制 token 桶的上限 b 来控制并发的上限。相对前一个方案无疑是更加合理了。
但是在实际开发中，细心的大家就会发现企业微信官方的限频时间窗口可能是滑动的，那么你会发现你的实际高并发的上限则是 2b。那么将不得不将上限 b 降低到原来的 1 / 2，那么意味我们要牺牲一半的性能了。
漏桶算法(Leaky Bucket)方案
漏桶算法是网络世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）时经常使用的一种算法，它的主要目的是控制数据注入到网络的速率，平滑网络上的突发流量。漏桶算法提供了一种机制，通过它，突发流量可以被整形以便为网络提供一个稳定的流量。
相对于令牌桶算法，漏桶算法不同的地方则是在 token 的取出也是按照 1 / t 个单位时间来取出的，也就是说这个方案是存在两个不同的定时器来分别控制桶的流入和流出，漏桶算法的流量整形更加平滑。
那它能给我们带来什么好处呢？它实际解决了在面对滑动窗口场景时令牌桶算法的一半性能牺牲，其次整体调用更加平滑和稳定。那它的副产物则是当突增请求来的时候它的丢失更加分散和无规律，毕竟令牌桶还有令牌桶的容量作为突增请求的缓存和平衡。
到这里为止，实际初步方案大家都有腹案了，回归需求点：
1、支持所有用户(客户数是百万级别)的批量修改也能够支持单个用户的修改；
2、服务稳定，请求耗时不可过长，能够满足前端调用需要；
3、批量任务要保证全部执行完成。
我们最终选择了令牌桶算法，没有选择更加优秀的漏桶算法，根本原因则是在于漏桶算法的请求是无法主动获取 token 的，因此其需要将所有需求存放在一个请求/调用队列中，导致整个请求变成了一个异步请求，对于单个请求来说是无法立刻获取的执行结果的，为了弥补这个缺点要付出的成本相对于一半的性能牺牲的性价比是不足的，且令牌桶的对于突增请求的具有一定的缓冲能力，更加符合业务需要。
但是令牌桶也是无法根本上解决请求丢失的场景的，
因此增加待执行请求队列（redis）来缓存丢弃的请求，增加一个定时器来定期检查令牌桶的容量，如果有空闲 token 在执行待执行队列中的请求。
04
方案实现优化
令牌桶算法的方案只是从脱离实现细节的宏观上论证了方案的可行性，在实际实现中，我们需要针对的一个 IP 即一个 POD 实例来进行设计的，其实是存在 8 个不同的 worker 进程来执行的，因此令牌桶是多个进程之间共享的，这个就涉及到分布式限频限流的设计。
在分布式的场景中首要解决的是操作的幂等行，更加具体一点则是如何保证放入和取出 token 操作的幂等性，不能出现 2 - 1 - 1 = 1 （-1 是个异步操作）的异步操作bug。
首先是令牌桶采用的 Redis 来实现，其高并发低延时的特性能够极大降低操作间的延时。
首先是放入 token 的定时器，通过检查
“process.env.IMSERVER_WORKER_ID” 在 master worker 中启动定时器，保证只有一个 worker 进程来放入 token；这里有兴趣的同学可以看下之前的 Node开发实践总结-定时脚本的设计与实现 中定时器知识。
令牌桶的取出操作增加读写锁，将读取 删除进行封装，保证同时只有一个进程在读取 token，其他的进程处于阻塞状态。读写锁的状态位采用的 POD 容器的环境变量来实现，性能会提升一点。
05
滑动窗口方案的思考
在方案设计中，我们提到了“滑动窗口方案”，可能大家会好奇为何没有采用滑动窗口方案，很明显这个方案更加符合业务限制：“每个 IP 的调用不得超过 20000 次/每分钟”。
实际在未接触到令牌桶算法之前，我预期的方案是：将每次调用执行的时间戳和 IP 存储到 redis 的 hash 数据结构中；每次请求到来时，检查距离当前时间的单位时间内的请求总数，如果超过调用限制则阻塞。
但是在真正的开发场景中面临了诸如时间戳不同步、幂等性问题（计算成本高，查询 删除操作的时间gap）、执行上限无法动态调整（每个进程都是按照自己的上限进行调用检查的）等问题，最终放弃了滑动窗口的方案。
06
结语
实际在业务开发中并没有“银弹”，需要对自己的业务需求，开发背景，技术方案进行深层次的分析和规划，谋求最佳的实现方案，也欢迎大家多多指点关于这方面的思考和想法。
近期热文
To B产品商业化的真相
视频号多模态学习应用初探
小商店从0到1的系统能力构建之路
让我知道你在看
