overload_control/flow_control:smooth_limiter 精度以及效率问题

[AntiBargu]

问题发现与测试用例补充

在对应 issue #144 （目前已关闭）的时候，我发现了滑动窗口流量控制存在窗口更新不及时的问题。

发现问题的具体代码在这个 branch:

https://github.com/f1akeee/trpc-cpp/tree/sliding_window_limiter_test

（仅据参考，直接看下面的 case即可）

稍加整理，设计出一个 adversary case 😈

相关单元测试用例：

TEST_F(SmoothLimiterTest, Overload) {
  ServerContextPtr context = MakeRefCounted<ServerContext>();
  ProtocolPtr req_msg = std::make_shared<TrpcRequestProtocol>();
  context->SetRequestMsg(std::move(req_msg));
  context->SetFuncName("trpc.test.flow_control.smooth_limiter");

  ASSERT_EQ(smooth_limiter_->GetMaxCounter(), 3);
  for (int i{0}; i < 4; ++i) {
    ASSERT_EQ(smooth_limiter_->GetCurrCounter(), 0);
    ASSERT_EQ(smooth_limiter_->CheckLimit(context), false);
    ASSERT_EQ(smooth_limiter_->CheckLimit(context), false);
    ASSERT_EQ(smooth_limiter_->GetCurrCounter(), 2);
    ASSERT_EQ(smooth_limiter_->CheckLimit(context), false);
    ASSERT_EQ(smooth_limiter_->CheckLimit(context), true);
    ASSERT_EQ(smooth_limiter_->CheckLimit(context), true);
    std::this_thread::sleep_for(std::chrono::seconds(1));
  }
}

单元测试说明：

单元测试中的 smooth_limiter_ 滑窗对象配置为每秒允许通过3个请求。故而对于1秒内的5个请求，前3个请求是准许通过的，后两个请求应该被拒绝。1秒过后，滑窗应该更新，对于新到的5个请求，应该也是通过3个，拒绝两个。

实际测试结果：

exec ${PAGER:-/usr/bin/less} "$0" || exit 1
Executing tests from //trpc/overload_control/flow_control:smooth_limiter_test
-----------------------------------------------------------------------------
Running main() from gmock_main.cc
[==========] Running 3 tests from 2 test suites.
[----------] Global test environment set-up.
[----------] 1 test from SmoothLimiter
[ RUN      ] SmoothLimiter.Contruct
[       OK ] SmoothLimiter.Contruct (30 ms)
[----------] 1 test from SmoothLimiter (30 ms total)

[----------] 2 tests from SmoothLimiterTest
[ RUN      ] SmoothLimiterTest.CheckLimit
[       OK ] SmoothLimiterTest.CheckLimit (1007 ms)
[ RUN      ] SmoothLimiterTest.Overload
trpc/overload_control/flow_control/smooth_limiter_test.cc:75: Failure
Expected equality of these values:
  smooth_limiter_->GetCurrCounter()
    Which is: 3
  0
[  FAILED  ] SmoothLimiterTest.Overload (1006 ms)
[----------] 2 tests from SmoothLimiterTest (2013 ms total)

[----------] Global test environment tear-down
[==========] 3 tests from 2 test suites ran. (2044 ms total)
[  PASSED  ] 2 tests.
[  FAILED  ] 1 test, listed below:
[  FAILED  ] SmoothLimiterTest.Overload

 1 FAILED TEST

在 1000ms（1s）后，smooth_limiter_ 的当前窗口的活跃连接数依然为 3。

trpc::smooth_limiter 目前的机制

将单位时间 1S 分为 N 个部分，每一个部分称为1帧（frame），默认配置的 fps 为100，即每10ms 为一帧。帧和秒的关系，类比于现实中秒和分钟、分钟和小时的关系，只不过是进制单位不同，帧与秒采用百进制。类比时钟，不难想到用 ringbuffer，实际上，trpc 也是这样实现的。其中 ringbuffer 中每个 slot 对某一帧的计数器，对 ringbuffer 的 slot 计数器求和，即可得到 1s 的有效请求计数。引入外部定时器，用于驱动帧的“滴答”切换。

这是一个符合滑动窗口定义的朴素实现。下面分析一下这个朴素实现存在的问题🤔

机制问题分析

• 精度问题

  使用“分帧分边沿”的滑动窗口的计算精度跟帧的大小有关：

  • 极限状态下，将 fps 设置为1后退化为固定窗口算法（无法处理窗口边沿点的突发流量）

  • 滑动窗口的左右边沿帧可能存在误 reject 的情况（如之前的问题描述），简单的画个图描述如下，其中数字表示帧计数器的值，绿色表示通过，红色表示拒绝：

• 效率问题

  • 引入外部定时器线程

  • 对于每个请求都要做 HitQueue::ActiveSum()，这是一个 O(n) 的运算。（其实，针对 这个 O(n) 的处理可以用前缀和的方式进行优化，优化后 ActiveSum() 可以降到 O(1)，数据类型使用 uint64_t，当 uint64_t 耗尽的时候可以利用减法下溢的特性得到正确的结果）

    int64_t HitQueue::ActiveSum() const {
      const int begin = window_begin_.load(std::memory_order_acquire);
      const int end = (begin + WindowSize()) % frame_hits_.size();
      int64_t sum = 0;
      for (int i = begin; i != end; i = NextIndex(i)) {
        sum += frame_hits_.at(i).load(std::memory_order_acquire);
      }
      return sum;
    }

[AntiBargu]

解决方案

通过引入 RecentQueue 来实现滑动窗口算法。

RecentQueue 用来保存滑动窗口内最近所有活跃请求的时间戳。从实现上说，依然使用 ring queue，该队列的初始大小为 QPS（滑动窗口内能够保存连接的最大值）。

不难看出，由于 RecentQueue 保存时序，所以在 RecentQueue 内时间戳螺旋递增，RecentQueue 是一个有序结构。

在 RecentQueue 中cur 表示存放当前请求时间戳的位置。当新请求到达的时候，cur 指示 RecentQueue 中缓存最久的时间戳。

过滤请求

当一个请求到达的时候，该请求的时间戳为 now。

当 now - 1s < RecentQueue[cur] 时，说明当前 RecentQueue 已满，且缓存最久时间戳 RecentQueue[cur] 比较新，不能被淘汰，故应拒绝本次访问；

当 now - 1s ≥ RecentQueue[cur] 时，说明缓存最久时间戳 RecentQueue[cur] 缓存时间超过1s 可以被淘汰，故更新 RecentQueue。

流程的时间复杂度为O(1)。

求当前时刻滑动窗口内活跃请求总数

由于 RecentQueue 具有螺旋递增的性质，其逻辑结构是一个有序结构，故能够通过二分查找找到第一个满足大于 now - 1s 的位置，与当前 cur 做偏移量计算即可得到当前时刻滑动窗口内活跃请求总数。

流程的时间复杂度为O(logn)。

调用时机：或许只有开启 report 后才会调用。

算法设计思想

• 惰性求值

  这一点沿用了之前设计令牌桶算法时的思想。

• 建模——以缓存设计的角度解决滑动窗口问题

  熟悉缓存策略的朋友应该不难看出这个算法有点像 LRU。 RecentQueue 和 Least Recently Used 稍有区别：

  • RecentQueue 缓存时间戳只访问/缓存一次； Least Recently Used 缓存的对象可能被访问多次。访问次数的差异，造成了在底层数据结构选型的不同，LRU 需要频繁插入、删除，故而使用双向链表结构，另外，为了提升 LRU 查找的能力，通常在 LRU 实现的时候维护 hash 表。
  • RecentQueue 有拒绝更新缓存的能力；相反，LRU 没有。

算法优点

• 不引入额外的定时器
• 不以帧为单位的累加计数器求和的方式计算当前活跃连接数
• 纳秒级精度，误差忽略不计
• 算法效率高