1      概述

ROMA平台的核心系统ROMA Connect源自华为流程IT的集成平台，在华为内部有超过15年的企业业务集成经验。依托ROMA Connect，可以将物联网、大数据、视频、统一通信、GIS等基础平台及各个应用的服务、消息、数据统一集成适配以及编排，屏蔽各个平台对上层业务的接口差异性，对上提供服务、消息、数据集成使能服务，以支撑新业务的快速开发部署，提升应用开发效率。适用于平安园区、智慧城市、企业数字化转型等场景，图1展示了ROMA Connect的功能视图。

图1 ROMA Connect功能视图

其中APIC(APIC Connect)作为核心组件包含了API Gateway能力，承载了API的集成和开放能力，流控作为API Gateway的关键特性，为用户的API集成、开放提供了快速、有效的安全防护，本文将详细描述API Gateway流控实现，揭开高性能秒级流控的技术细节。

2      高并发高吞吐系统流控需求

2.1      流量控制的动因

在高并发高吞吐系统中，通常的技术关键词是降级、缓存、流控等，流控更是其中的核心技术，当然，这些技术是相辅相成的。

• 流控的价值
  1. 提升系统稳定性/防止雪崩
  2. 保障高优先级服务
  3. 降低响应时延，提升用户体验
  4. 提升系统有效吞吐量
  5. 限制性业务使用等
  6. …
• 流控的目标参数
  1. 限制总并发数（比如数据库连接池、线程池）
  2. 限制瞬时并发数（如nginx的limit_conn模块）
  3. 限制时间窗口内的平均速率
  4. 限制远程接口调用速率
  5. 限制MQ的消费速率
  6. 限制网络流量
  7. 限制CPU与内存的使用率
  8. …

2.2      业务挑战

在大业务场景下，主要挑战是高并发、低时延、高精度、多维度灵活扩展等诉求。

图2 业务挑战

而对于流控的具体挑战如下：

• 每天10次与每分钟10万次的流控同时存在
• 流控反馈周期比流控周期还久
• 流控的维度特别多
• 流控同步处理时间影响用户体验
• 流控静态设置，要么过高要么过低
• 流控失效造成业务失效
• 流控节点部署复杂资源消耗高
• …

3      常见流控技术分析

3.1      常见流控逻辑架构

图3 常见流控逻辑架构

各种方案的优缺点如下表所示：

3.2      常见流控算法

3.2.1        计数器算法

优点：1. 算法简单易实现。

不足：1. 输出不平滑。2. 有临界问题，在流控周期边界处易发生输出激增，大幅超过流控阈值，冲坏后端服务。

3.2.2        滑动窗口算法

优点：1. 可以解决计数器算法的临界问题。2. 算法简单易实现。

不足：1. 精度要求越高需要的窗口格子越多，内存开销较大。2. 不保证输出平滑。

3.2.3        漏桶算法

优点：1. 输出速度与输入速度无关，是恒定的，流控效果平滑。2. 无临界问题。3. 不依赖令牌。

不足：1. 由于漏桶输出速度恒定，所以不支持一定程度的突发请求。2. 如果桶满，输入数据会被丢弃

3.2.4        令牌桶算法

优点：1. 允许一定程度的突发流量。2. 通过定制令牌添加方法，可定制复杂的流控策略。3. 无临界问题。

不足：1. 当桶内无可用令牌时，输入请求会被直接丢弃。2. 不支持按优先级处理输入请求。

4      ROMA Connect流控技术实现

4.1      总体策略

• 对高精度与高吞吐进行分层， 区别不同场景的流控，采用不同策略与算法
  • 对高精度低吞吐流控进行持久化； 高吞吐高频纯内存计数策略
  • 高吞吐高频流控， 不进行 HA 保障， 故障后数据清零重新计算
• 多维度多优先级，采用 Policy 多维度控制， 单一请求可触发多 Policy
  • 解耦复杂控制， 采用多条简单策略分别映射；降低用户使用复杂度
  • 单一请求可触发所有满足条件的 Policy， 进行综合流控
• 通过分发策略、异步、批申报等机制，降低请求时延与降低 Controller 工作量
  • 尽可能在 Filter/SDK 级别处理， 避免流控请求影响业务时延
  • 尽可能少上报到 Controller， 降低 Controller 负载提升 Controller 效率
• Filter 与算法门限降级放通，避免Ratelimit机制故障对业务造成影响
• 采用 KEY/VALUE 模式和多维， 提供通用机制，适应不同场景不同应用流控诉求
  • 立足API Gateway第一个应用场景
  • Controller 不需理解具体业务，由基于SDK封装的Filter适配具体业务与流控Controller

4.2      逻辑视图

• RateLimit SDK访问根据一致性hash访问sharding后的RateLimit Controller，对于高吞吐高精度的流控集中在Controller内存进行限流计算。
• RateLimit Controller对于高精度高吞吐只集中在本地内存计算，无需考虑crash后保留历史限流信息。
• RateLimit Controller对于高精度低吞吐的限流采取异步持久化策略，确保Controller crash后流控的精度。
• 当Ratelimit Controller服务终止的时候，Ratelimit SDK支持自动降级。
• 根据API Gateway采集的API Response latency等信息反馈，支持动态调整流控策略。
• 支持SLA-Based 流控 Policies。

4.3      架构设计

• 采用独立的Controller 方案
  • 独立集群 Controller 提供全局精确高吞吐流控
  • Controller 内部采用 Sharding 机制
• 采用通用的Policy与Key/Value模型
  • 采用可扩展的 Domain/Policy机制，适应不同业务场景
  • 不同Policy关联不同的算法
• 提供SDK与Tools，开发API G等插件
  • 提供可重用的SDK与调试工具等
  • 预实现API Gateway等流控插件
• 外置日志、流控数据分析模块
  • 通过数据挖掘、预测等反馈到配置/策略管理模块，动态修订流控策略

4.4      内置算法

4.4.1        带缓存带颜色的令牌桶算法

• 令牌桶算法的问题：
  • 当无可用令牌时， 请求会被立即拒绝。而用户可能会继续不断发送请求，直到有可用的令牌。这会增加API Gateway的负载和流控服务的负载。
  • 所有的请求以同样的概率获得令牌，不支持优先级。而在实际应用中，一些请求需要被优先处理，另一些请求可以被延迟处理或者直接拒绝。例如，应该优先处理电子商务网站的付款请求，而浏览商品的请求可以被延迟处理。
• 设计了一种支持缓存和优先级的令牌桶算法
  • 缓存：
    • 当无可用令牌时，把请求暂时放在请求队列里，待有可用令牌时再处理。
    • 采用FCFS算法处理请求。
    • 如果缓存也无可用空间，就直接拒绝请求。
  • 令牌
    • 令牌分为多种颜色，不同颜色代表不同优先级，如绿色、黄色、红色表示优先级由高至低。
    • 在API配置文件里，可配置不同API的优先级。根据预先配置的优先级，对请求分配相应颜色的令牌。如果请求没有优先级，则使用默认优先级。
    • 根据API Gateway系统的能力配置令牌的数量。
    • 当低优先级的请求到达时，如果高优先级的令牌量大于预留的数量，也可分配高优先级的令牌给该低优先级的请求。对令牌设置预留量，保证低优先级请求不会耗尽高优先级的令牌。
    • 每种颜色的令牌有单独的请求缓存。

4.4.2        高精度高吞吐量的流控算法

• 问题：高精度、高吞吐的矛盾
  • 为了实现高精度流控，API Gateway需要为每个API请求发送流控请求至流控服务，会很大程度降低处理请求的吞吐量。
  • 为了提高吞吐量，API Gateway需降低发送流控请求的频度，这会降低流控的精度。发送流控请求的频度越低，流控的精度越低。
• 提出一种高精度高吞吐量的流控算法HAT（High Accuracy, High Throughput）
  • 把流控分为自主流控阶段和流控服务流控阶段。
  • 设流控阈值为L，自主流控阈值为S，API Gateway集群节点数量为N，当前流控周期内已经处理的API数量为R。
  • 流控服务计算：自主流控阈值S = L/N，并分发给每个API Gateway节点。
  • 在自主流控阈值范围内，每个API Gateway节点可做自主流控，无需向流控服务发送流控请求。
  • 当API Gateway集群中有一个节点的API请求量超过自主流控阈值–α时，该节点发送流控请求至流控服务，申请新的流控阈值。此时，流控服务联系API Gateway的其它节点获得它们处理的API请求量。然后，流控服务重新计算自主流控阈值S = （L – R）/ N，并发送给各个API Gateway节点。
  • 当流量余额 < δ时，不再更新自主流控阈值。
  • 当进入下一流控周期时，流控服务重置S，各API Gateway节点联系流控服务更新自主流控阈值。
• 算法分析
  • 设u是单个流控周期内自主流控阈值更新的次数，P_i表示第i个API Gateway节点处理API的速度。
  • 单个流控周期的流控请求的数量由L降至u*N。
  • 最优情况是API Gateway集群的每个节点的性能完全一样，此时，u = 1。当流控阈值是10000，API Gateway节点数量是10时，单个流控周期的流控请求从10000降至10。
  • API Gateway集群的每个节点的性能越接近，u越接近1。API Gateway集群的每个节点的性能差距越大，u越大。

4.4.3        动态流控算法

基于运行状态、趋势、API调用链进行动态流控。

• 请求取得令牌后，流控服务开始处理请求，生成流控响应（接受/拒绝，降级，或黑白名单）。
• 基于运行状态的动态流控策略
  • 根据使用网络状态（可用连接数，网络延迟），请求处理延迟，API Gateway的cpu、memory等运行状态，动态修改流控阈值。也可等等。
  • 当cpu、内存等使用率远小于阈值时，正常处理请求。
  • 当cpu、内存等使用率接近阈值时，降低流控阈值（降级），减少API Gateway的负载。
  • 当cpu、内存等使用率超过阈值很多时，提高降低流控阈值的速度。
  • 当无可用cpu、内存时，直接拒绝请求。
  • 当cpu、内存等使用率降低至正常水平时，恢复流控阈值。
• 基于运行状态趋势的动态流控策略
  • 利用机器学习，分析历史数据，生成预测模型，预测API Gateway的负载，提前修改流控阈值或降级服务，保证API Gateway负载平滑稳定。
  • 利用机器学习发现应加入黑名单的请求。
• 基于API调用流的动态流控策略
  • Case: API调用流。
  • 设计一种基于API调用流的动态流控策略。
    • 利用机器学习发现API调用流。流控服务保存API调用关系。
    • 当系统负载较高时，当一个API请求达到阈值被限流后， 对于相关联的同一层次和低层次的所有API请求，不再访问Redis获取实时数据和处理，而是直接延迟处理或拒绝。
    • 当API Gateway系统负载正常时，不启动该动态流控策略。
    • 通过这种方式，可在基本不影响API处理速度的前提下，降低API Gateway的负载和流控服务的负载。