分布式服务系统限流方法及分布式服务系统转让专利
申请号 : CN202110417484.X
文献号 : CN113098793B
文献日 : 2021-12-14
发明人 : 杨帆 , 张树行
申请人 : 南京甄视智能科技有限公司
摘要 :
本发明公开了一种分布式服务系统限流方法，对于所述分布式服务系统所提供的任一服务，系统中每个节点的每个服务请求均需消费一个由该服务相应的令牌桶所生成的令牌才可以得到处理；系统中的每个节点从所述令牌桶中预取多个令牌存储于本地，并在前次预取令牌消费完后再次从所述令牌桶中预取多个令牌存储于本地，各节点的服务请求只能消费本地的预取令牌。本发明还公开了一种分布式服务系统。本发明在传统令牌桶算法的基础上，针对分布式服务系统的集群分布式特点，通过为各节点引入令牌预取机制，有效降低了大量服务请求对令牌桶进行访问所导致的巨量网络消耗，从而可以极低的网络资源消耗和时延为代价，实现高效的分布式服务系统服务限流。
权利要求 :
1.一种分布式服务系统限流方法，对于所述分布式服务系统所提供的任一服务，系统中每个节点的每个服务请求均需消费一个由该服务相应的令牌桶所生成的令牌才可以得到处理；其特征在于，系统中的每个节点从所述令牌桶中预取多个令牌存储于本地，并在前次预取令牌消费完后再次从所述令牌桶中预取多个令牌存储于本地，各节点的服务请求只能消费本地的预取令牌；节点在每次预取令牌后按照以下方法动态调整下次的期望预取令牌数目：
如果本次的实际预取令牌数目低于本次的期望预取令牌数目的预设比例，则降低下次的期望预取令牌数目；如果本次的实际预取令牌数目大于等于本次的期望预取令牌数目的预设比例但小于本次的期望预取令牌数目，则保持下次的期望预取令牌数目不变；如果本次的实际预取令牌数目等于本次的期望预取令牌数目，则将下次的期望预取令牌数目提高至一个不大于maxNum的数目；maxNum为单个节点每次预取令牌的最大数量，所述预设比例的取值范围为(0，1)。
2.如权利要求1所述分布式服务系统限流方法，其特征在于，单个节点每次预取令牌的最大数量maxNum按照下式动态计算：其中，QPS为所述分布式服务系统每秒可以处理的服务请求数，instancesNum为所述分布式服务系统中的节点数量，Math.floor()为向下取整函数，M为每个时间单位内预取令牌的最小次数。
3.如权利要求1所述分布式服务系统限流方法，其特征在于，所述预设比例的取值为1/
2。
4.如权利要求1所述分布式服务系统限流方法，其特征在于，如果本次的实际预取令牌数目等于本次的期望预取令牌数目，则将下次的期望预取令牌数目提高为本次的实际预取令牌数目的二倍与maxNum之间的较小值。
5.如权利要求1所述分布式服务系统限流方法，其特征在于，每个节点预取某一服务对应令牌的频率不高于产生一个所述令牌的时间间隔。
6.如权利要求1～5任一项所述分布式服务系统限流方法，其特征在于，所述令牌桶在每次处理请求之前实时计算出要填充的令牌数目并按照所计算数目进行令牌填充。
7.如权利要求6所述分布式服务系统限流方法，其特征在于，令牌桶每次要填充的令牌数目tokens按照以下公式计算：式中，Match.min()为取最小值函数，Math.floor()为向下取整函数，currentMs为当前时间，lastMs为上一次填充令牌的时间，QPS为所述分布式服务系统每秒可以处理的服务请求数，maxPermits为令牌桶的最大容量。
8.一种分布式服务系统，其特征在于，使用如权利要求1～7任一项所述限流方法。
说明书 :
分布式服务系统限流方法及分布式服务系统
技术领域
[0001] 本发明涉及一种服务的限流方法，尤其涉及一种分布式服务系统限流方法。
背景技术
[0002] 服务调用限流对于构建高可用的微服务非常重要。限流技术最早出现在网络设备上，是为了解决突发网络流量引起的网络拥塞问题。与通常的网络限流不同，微服务调用限
流是一种更高层次、更细粒度的限流方法，限制对象是接口的请求调用。随着微服务网关概
念的日益清晰，微服务调用限流技术逐渐得到应用。目前的大多数限流算法和实现都是单
机版的，没有考虑集群模式下的分布式限流。即使个别支持集群模式，具体的实现往往会给
服务调用路径增加一定的延迟，以达到集群的限流。
流是一种更高层次、更细粒度的限流方法，限制对象是接口的请求调用。随着微服务网关概
念的日益清晰，微服务调用限流技术逐渐得到应用。目前的大多数限流算法和实现都是单
机版的，没有考虑集群模式下的分布式限流。即使个别支持集群模式，具体的实现往往会给
服务调用路径增加一定的延迟，以达到集群的限流。
发明内容
[0003] 本发明所要解决的技术问题在于克服现有技术不足，提供一种分布式服务系统限流方法，可以极低的网络资源消耗和时延为代价，实现高效的分布式服务系统服务限流。
[0004] 本发明具体采用以下技术方案解决上述技术问题：
[0005] 一种分布式服务系统限流方法，对于所述分布式服务系统所提供的任一服务，系统中每个节点的每个服务请求均需消费一个由该服务相应的令牌桶所生成的令牌才可以
得到处理；系统中的每个节点从所述令牌桶中预取多个令牌存储于本地，并在前次预取令
牌消费完后再次从所述令牌桶中预取多个令牌存储于本地，各节点的服务请求只能消费本
地的预取令牌。
得到处理；系统中的每个节点从所述令牌桶中预取多个令牌存储于本地，并在前次预取令
牌消费完后再次从所述令牌桶中预取多个令牌存储于本地，各节点的服务请求只能消费本
地的预取令牌。
[0006] 优选地，节点在每次预取令牌后按照以下方法动态调整下次的期望预取令牌数目：
[0007] 如果本次的实际预取令牌数目低于本次的期望预取令牌数目的预设比例，则降低下次的期望预取令牌数目；如果本次的实际预取令牌数目大于等于本次的期望预取令牌数
目的预设比例但小于本次的期望预取令牌数目，则保持下次的期望预取令牌数目不变；如
果本次的实际预取令牌数目等于本次的期望预取令牌数目，则将下次的期望预取令牌数目
提高至一个不大于maxNum的数目；maxNum为单个节点每次预取令牌的最大数量，所述预设
比例的取值范围为(0，1)。
目的预设比例但小于本次的期望预取令牌数目，则保持下次的期望预取令牌数目不变；如
果本次的实际预取令牌数目等于本次的期望预取令牌数目，则将下次的期望预取令牌数目
提高至一个不大于maxNum的数目；maxNum为单个节点每次预取令牌的最大数量，所述预设
比例的取值范围为(0，1)。
[0008] 进一步优选地，单个节点每次预取令牌的最大数量maxNum按照下式动态计算：
[0009]
[0010] 其中，QPS为所述分布式服务系统每秒可以处理的服务请求数，ins tan cesNum为所述分布式服务系统中的节点数量，Math.floor()为向下取整函数，M为每个时间单位内
预取令牌的最小次数。
预取令牌的最小次数。
[0011] 进一步优选地，所述预设比例的取值为1/2。
[0012] 进一步优选地，如果本次的实际预取令牌数目等于本次的期望预取令牌数目，则将下次的期望预取令牌数目提高为本次的实际预取令牌数目的二倍与maxNum之间的较小
值。
值。
[0013] 优选地，每个节点预取某一服务对应令牌的频率不高于产生一个所述令牌的时间间隔。
[0014] 优选地，所述令牌桶在每次处理请求之前实时计算出要填充的令牌数目并按照所计算数目进行令牌填充。
[0015] 进一步优选地，令牌桶每次要填充的令牌数目tokens按照以下公式计算：
[0016]
[0017] 式中，Match.min()为取最小值函数，Math.floor()为向下取整函数，currentMs为当前时间，lastMs为上一次填充令牌的时间，QPS为所述分布式服务系统每秒可以处理的
服务请求数，maxPermits为令牌桶的最大容量。
服务请求数，maxPermits为令牌桶的最大容量。
[0018] 基于同一发明构思还可以得到以下技术方案：
[0019] 一种分布式服务系统，使用如上任一技术方案所述限流方法。
[0020] 相比现有技术，本发明技术方案具有以下有益效果：
[0021] 本发明在传统令牌桶算法的基础上，针对分布式服务系统的集群分布式特点，通过为各节点引入令牌预取机制，有效降低了大量服务请求对令牌桶进行访问所导致的巨量
网络消耗，从而可以极低的网络资源消耗和时延为代价，实现高效的分布式服务系统服务
限流。
网络消耗，从而可以极低的网络资源消耗和时延为代价，实现高效的分布式服务系统服务
限流。
附图说明
[0022] 图1为实施例中的分布式服务系统架构；
[0023] 图2a、图2b分别为令牌桶主动实时生成令牌的间隔策略和贪婪策略的原理示意图；
[0024] 图3为实施例中单个节点服务请求的处理流程；
[0025] 图4为令牌预取数量动态计算的一个伪代码算法实例；
[0026] 图5为实施例中的分布式服务系统实现服务限流的原理示意图。
具体实施方式
[0027] 为了实现分布式服务系统的服务调用限流，本发明的解决思路是在传统令牌桶算法的基础上，针对分布式服务系统的集群分布式特点，通过为各节点引入令牌预取机制，有
效降低大量服务请求对令牌桶进行访问所导致的巨量网络消耗，从而可以极低的网络资源
消耗和时延为代价，实现高效的分布式服务系统服务限流。
效降低大量服务请求对令牌桶进行访问所导致的巨量网络消耗，从而可以极低的网络资源
消耗和时延为代价，实现高效的分布式服务系统服务限流。
[0028] 具体而言，本发明所提出的技术方案具体如下：
[0029] 一种分布式服务系统限流方法，对于所述分布式服务系统所提供的任一服务，系统中每个节点的每个服务请求均需消费一个由该服务相应的令牌桶所生成的令牌才可以
得到处理；系统中的每个节点从所述令牌桶中预取多个令牌存储于本地，并在前次预取令
牌消费完后再次从所述令牌桶中预取多个令牌存储于本地，各节点的服务请求只能消费本
地的预取令牌。
得到处理；系统中的每个节点从所述令牌桶中预取多个令牌存储于本地，并在前次预取令
牌消费完后再次从所述令牌桶中预取多个令牌存储于本地，各节点的服务请求只能消费本
地的预取令牌。
[0030] 优选地，节点在每次预取令牌后按照以下方法动态调整下次的期望预取令牌数目：
[0031] 如果本次的实际预取令牌数目低于本次的期望预取令牌数目的预设比例，则降低下次的期望预取令牌数目；如果本次的实际预取令牌数目大于等于本次的期望预取令牌数
目的预设比例但小于本次的期望预取令牌数目，则保持下次的期望预取令牌数目不变；如
果本次的实际预取令牌数目等于本次的期望预取令牌数目，则将下次的期望预取令牌数目
提高至一个不大于maxNum的数目；maxNum为单个节点每次预取令牌的最大数量，所述预设
比例的取值范围为(0，1)。
目的预设比例但小于本次的期望预取令牌数目，则保持下次的期望预取令牌数目不变；如
果本次的实际预取令牌数目等于本次的期望预取令牌数目，则将下次的期望预取令牌数目
提高至一个不大于maxNum的数目；maxNum为单个节点每次预取令牌的最大数量，所述预设
比例的取值范围为(0，1)。
[0032] 进一步优选地，单个节点每次预取令牌的最大数量maxNum按照下式动态计算：
[0033]
[0034] 其中，QPS为所述分布式服务系统每秒可以处理的服务请求数，ins tan cesNum为所述分布式服务系统中的节点数量，Math.floor()为向下取整函数，M为每个时间单位内
预取令牌的最小次数。
预取令牌的最小次数。
[0035] 进一步优选地，所述预设比例的取值为1/2。
[0036] 进一步优选地，如果本次的实际预取令牌数目等于本次的期望预取令牌数目，则将下次的期望预取令牌数目提高为本次的实际预取令牌数目的二倍与maxNum之间的较小
值。
值。
[0037] 优选地，每个节点预取某一服务对应令牌的频率不高于产生一个所述令牌的时间间隔。
[0038] 优选地，所述令牌桶在每次处理请求之前实时计算出要填充的令牌数目并按照所计算数目进行令牌填充。
[0039] 进一步优选地，令牌桶每次要填充的令牌数目tokens按照以下公式计算：
[0040]
[0041] 式中，Match.min()为取最小值函数，Math.floor()为向下取整函数，currentMs为当前时间，lastMs为上一次填充令牌的时间，QPS为所述分布式服务系统每秒可以处理的
服务请求数，maxPermits为令牌桶的最大容量。
服务请求数，maxPermits为令牌桶的最大容量。
[0042] 为了便于公众理解，下面通过一个具体实施例并结合附图来对本发明的技术方案进行详细说明：
[0043] 本实施例分布式服务系统的基本架构如图1所示。当外部请求到达时，请求首先到达接口平台接入层，经过参数校验、服务鉴权、服务路由等前置逻辑后，进入服务限流逻辑，
在服务限流逻辑中获取限流的令牌，如果获取到通行令牌，则请求通过服务路由分发给对
应服务的某个实例去处理。
在服务限流逻辑中获取限流的令牌，如果获取到通行令牌，则请求通过服务路由分发给对
应服务的某个实例去处理。
[0044] 在服务调用场景下，专门针对每个服务设置令牌生成器实时生成令牌的方式增加了复杂性和准确性的问题，会导致在系统比较空闲，调用量比较小的情况下令牌生成器也
要不停息的进行令牌生成。并且在具体实现时，由于操作系统的分时机制以及用户进程或
者进程内部的线程会被操作系统调度而短时间暂停执行，基本很难实现真正的实时。即便
能够实现理想情况下的实时加入令牌，由于使用不同的令牌桶控制不同的服务的调用流
量，有的服务的调用量较少，如果要针对每个服务都实现实时地向各服务的令牌桶加入令
牌，这将存在巨大的计算资源浪费，性价比不高。因此本实施例选择令牌桶算法作为分布式
服务限流的基础算法，并选择延迟生成令牌的令牌生成策略。
要不停息的进行令牌生成。并且在具体实现时，由于操作系统的分时机制以及用户进程或
者进程内部的线程会被操作系统调度而短时间暂停执行，基本很难实现真正的实时。即便
能够实现理想情况下的实时加入令牌，由于使用不同的令牌桶控制不同的服务的调用流
量，有的服务的调用量较少，如果要针对每个服务都实现实时地向各服务的令牌桶加入令
牌，这将存在巨大的计算资源浪费，性价比不高。因此本实施例选择令牌桶算法作为分布式
服务限流的基础算法，并选择延迟生成令牌的令牌生成策略。
[0045] 令牌桶的实现一般有两种不同的方式。一种方式是主动实时生成令牌放入到令牌桶中，处理请求时从令牌桶中获取并消费令牌，主动实时生成令牌又可分为间隔策略和贪
婪策略，间隔策略是每隔一段时间，一次性的填充所有令牌，贪婪策略则尽可能以更小的时
间间隔每次添加对接时间间隔的令牌，最理想的情况是以固定的速率每次添加一个令牌。
间隔策略如图2a所示，每隔一分钟填充5个令牌。贪婪策略如图2b所示，尽可能贪婪的填充
令牌，会将一分钟划分成5个更小的时间单元，每隔12秒填充1个令牌。第二种方式是本实施
例所采用的延迟生成令牌的方式，每次处理请求之前实时的计算出要填充的令牌数目并进
行填充，然后从中消费令牌允许请求被放通。
婪策略，间隔策略是每隔一段时间，一次性的填充所有令牌，贪婪策略则尽可能以更小的时
间间隔每次添加对接时间间隔的令牌，最理想的情况是以固定的速率每次添加一个令牌。
间隔策略如图2a所示，每隔一分钟填充5个令牌。贪婪策略如图2b所示，尽可能贪婪的填充
令牌，会将一分钟划分成5个更小的时间单元，每隔12秒填充1个令牌。第二种方式是本实施
例所采用的延迟生成令牌的方式，每次处理请求之前实时的计算出要填充的令牌数目并进
行填充，然后从中消费令牌允许请求被放通。
[0046] 在本实施例中，某一服务所对应的令牌桶在每次处理请求之前实时计算出要填充的令牌数目并按照所计算数目进行令牌填充，要填充的令牌数目tokens具体按照以下公式
计算：
计算：
[0047]
[0048] 式中，Match.min()为取最小值函数，Math.floor()为向下取整函数，currentMs为当前时间，lastMs为上一次填充令牌的时间，QPS为所述分布式服务系统每秒可以处理的
服务请求数，maxPermits为令牌桶的最大容量。
服务请求数，maxPermits为令牌桶的最大容量。
[0049] 当令牌消费者需要获取令牌时，根据从上次令牌生成时刻到当前时刻过去的时间段，采用上述公式进行计算令牌数量，能够按需使用计算资源。当然延迟计算会带来一定的
计算延迟，在实际中由于计算公式比较简单，计算延迟可以忽略。
计算延迟，在实际中由于计算公式比较简单，计算延迟可以忽略。
[0050] 如果完全采用现有令牌桶的算法，每个服务请求到达时，均去令牌桶中获取令牌，这一方面会让每个请求增加令牌桶访问来回的网络消耗，另一方面也给令牌桶带来1比1的
具体调用量。虽然令牌桶可通过集群部署的方式进行扩容，但对于高流量服务还是会造成
个别令牌桶成为热点的问题。为解决这一问题，本发明引入了令牌预取机制，即系统中的每
个节点从令牌桶中预取多个令牌存储于本地，并在前次预取令牌消费完后再次从所述令牌
桶中预取多个令牌存储于本地，各节点的服务请求只能消费本地的预取令牌。这样就可有
效避免令牌桶成为热点的问题。如图3所示，当服务请求到达某一节点时，该节点先查询本
地的预取令牌配额，如果本地还有预取令牌，则消费本地的预取令牌进行服务调用；否则，
节点从服务所对应的令牌桶中预取多个令牌存储于本地。这样，通过每次从令牌桶中申请
多个令牌,预先将部分令牌拿到本地，然后本地的该服务下次请求时直接消费，则大大减少
了令牌桶的调用量。
具体调用量。虽然令牌桶可通过集群部署的方式进行扩容，但对于高流量服务还是会造成
个别令牌桶成为热点的问题。为解决这一问题，本发明引入了令牌预取机制，即系统中的每
个节点从令牌桶中预取多个令牌存储于本地，并在前次预取令牌消费完后再次从所述令牌
桶中预取多个令牌存储于本地，各节点的服务请求只能消费本地的预取令牌。这样就可有
效避免令牌桶成为热点的问题。如图3所示，当服务请求到达某一节点时，该节点先查询本
地的预取令牌配额，如果本地还有预取令牌，则消费本地的预取令牌进行服务调用；否则，
节点从服务所对应的令牌桶中预取多个令牌存储于本地。这样，通过每次从令牌桶中申请
多个令牌,预先将部分令牌拿到本地，然后本地的该服务下次请求时直接消费，则大大减少
了令牌桶的调用量。
[0051] 采用令牌预取机制，每个节点每次预取的数量怎么确定是首先需要考虑的问题。假设某个服务的整体限流用所述分布式服务系统每秒可以处理的服务请求数QPS来表征，
则每个节点预取的数量应该是由多个节点平分；又假设预先限定了每个时间单位内预取令
牌的最小次数，则单个节点每次预取令牌的最大数量maxNum按照下式动态计算：
则每个节点预取的数量应该是由多个节点平分；又假设预先限定了每个时间单位内预取令
牌的最小次数，则单个节点每次预取令牌的最大数量maxNum按照下式动态计算：
[0052]
[0053] 其中，QPS为所述分布式服务系统每秒可以处理的服务请求数，ins tan cesNum为所述分布式服务系统中的节点数量，Math.floor()为向下取整函数，M为每个时间单位内
预取令牌的最小次数。
预取令牌的最小次数。
[0054] 在微服务网关支持节点动态伸缩的情况下，可以借助开源的分布式协调部件，比如ZooKeeper、Eureka、Nacos等，来实现简单易用的节点管理功能，在保证实现轻量化的同
时，实时可靠地获取系统中的当前节点数量ins tan cesNum。
时，实时可靠地获取系统中的当前节点数量ins tan cesNum。
[0055] 本实施例中，各节点根据服务配置的QPS限制以及预取令牌的最大数量限制maxNum，在每次预取令牌后按照以下方法动态调整下次的期望预取令牌数目：如果本次的
实际预取令牌数目低于本次的期望预取令牌数目的预设比例，则降低下次的期望预取令牌
数目；如果本次的实际预取令牌数目大于等于本次的期望预取令牌数目的预设比例但小于
本次的期望预取令牌数目，则保持下次的期望预取令牌数目不变；如果本次的实际预取令
牌数目等于本次的期望预取令牌数目，则将下次的期望预取令牌数目提高至一个不大于
maxNum的数目；maxNum为单个节点每次预取令牌的最大数量，所述预设比例的取值范围为
(0，1)。
实际预取令牌数目低于本次的期望预取令牌数目的预设比例，则降低下次的期望预取令牌
数目；如果本次的实际预取令牌数目大于等于本次的期望预取令牌数目的预设比例但小于
本次的期望预取令牌数目，则保持下次的期望预取令牌数目不变；如果本次的实际预取令
牌数目等于本次的期望预取令牌数目，则将下次的期望预取令牌数目提高至一个不大于
maxNum的数目；maxNum为单个节点每次预取令牌的最大数量，所述预设比例的取值范围为
(0，1)。
[0056] 例如，可使用如图4所示的令牌预取数量动态计算算法：如果本次实际预取令牌数目小于提交申请的预取令牌数目的二分之一，则将下次提交申请的预取令牌数目缩小到本
次申请令牌数的二分之一；如果大于等于提交申请的预取令牌数目的二分之一并且小于提
交申请的预取令牌数目，则保持下次提交申请的预取令牌数目不变；如果等于提交申请的
预取令牌数目，则将下次提交申请的预取令牌数目增加到本次提交申请的预取令牌数目的
二倍与maxNum之间的较小值。
次申请令牌数的二分之一；如果大于等于提交申请的预取令牌数目的二分之一并且小于提
交申请的预取令牌数目，则保持下次提交申请的预取令牌数目不变；如果等于提交申请的
预取令牌数目，则将下次提交申请的预取令牌数目增加到本次提交申请的预取令牌数目的
二倍与maxNum之间的较小值。
[0057] 除了以上所讨论的令牌预取数量问题,也需要考虑预取频次的问题。在请求流量高峰期，经常会出现令牌数被很快消耗，在消耗完令牌的时刻到下一个产生令牌的时刻存
在一定的时间间隔，如果在该时间间隔内高频次的请求中心存储，会对中心存储产生过量
的请求，从而造成中心存储迅速过载。为解决这一问题,本实施例中设定每个节点预取某一
服务对应令牌的频率不高于产生一个所述令牌的时间间隔。
在一定的时间间隔，如果在该时间间隔内高频次的请求中心存储，会对中心存储产生过量
的请求，从而造成中心存储迅速过载。为解决这一问题,本实施例中设定每个节点预取某一
服务对应令牌的频率不高于产生一个所述令牌的时间间隔。
[0058] 如图5所示，当服务调用请求到达网关进行限流时，首先根据请求携带的元数据获取请求对应的服务名称等信息，然后根据服务名称从本地预取令牌管理器获取通行使用的
令牌。本地令牌管理器会优先从本地查找可用令牌，当本地可用令牌数目为零时，则本地令
牌管理器会尝试从远端令牌生成器(令牌桶，这里假设是Redis实现)申请某个数目的令牌
数目。申请令牌的数目根据对应的动态调整算法获得。从远端获取到令牌后，会存放到当前
网关节点内部，供令牌获取请求使用。
令牌。本地令牌管理器会优先从本地查找可用令牌，当本地可用令牌数目为零时，则本地令
牌管理器会尝试从远端令牌生成器(令牌桶，这里假设是Redis实现)申请某个数目的令牌
数目。申请令牌的数目根据对应的动态调整算法获得。从远端获取到令牌后，会存放到当前
网关节点内部，供令牌获取请求使用。