一文了解限流策略的原理与实现_编程技术

引言

限流策略主要用来控制在高并发、大流量的场景中对服务接口请求的速率。

比如双十一秒杀、抢购、抢票、抢单等场景。

举个例子，假设某个接口能够扛住的QPS为1k，这时有1w个请求进来，经过限流模块，会先放1k个请求，其余的请求会阻塞一段时间。不简单粗暴地返回404，让客户端重试，同时又能起到流量削峰的作用。

在业务迭代开发过程中，系统的稳定性和可靠性变得越来越重要，其中，限流算法是一种非常重要的技术手段之一。

限流算法可以有效地帮助系统控制请求的流量，防止系统因为流量过大而崩溃。在高并发的情况下，如果没有限流机制，系统可能会因为请求过多而导致响应变慢，甚至瘫痪。此外，限流算法还可以保护系统免受恶意攻击、恶意爬虫等不良行为的侵害，提高系统的安全性和稳定性。

本文我们将基于限流策略，讨论常见的限流算法的实现方式，以及如何从0到1设计一套可用的限流实现方案。

1. 简介

设计一套限流算法主要包含以下三个步骤：

流量统计：记录在特定时间段内通过的流量数，为后续限流判断提供依据。
限流判断：判断当前的流量是否可以正常通过。
流量控制：对于已被限流的请求，需要进行的特殊处理。

2. 流量统计

流量统计主要有两种方式：固定窗口统计和滑动窗口统计。

2.1 固定窗口统计

固定窗口统计是将时间划分为固定长度的时间窗口，并在每个时间窗口内统计通过系统的请求数量。例如，下图中将时间划分为1秒的时间窗口，统计每秒通过系统的请求数量。在固定窗口统计中，每个时间窗口的计数器都会在窗口结束时清零，重新开始统计下一个窗口的请求数量。

一文了解限流策略的原理与实现

这种统计方式简单易懂，实现简单，但是在流量不均匀的情况下容易出现突发流量问题，导致限流不准确。如下图所示，假设限流设置为1秒内通过qps数为2，由于在1s的时候统计窗口清零，对于500ms-1000ms这个区间内通过的2条请求没有记忆，1000ms-1500ms这个区间内的请求能正常通过，但实际上在500ms-1500ms这个区间的请求数已经是3了，超过设定的2的限流值，在极限情况下，固定窗口的真实流量可能达到限流值的2倍。

一文了解限流策略的原理与实现

由于固定窗口实现简单，在对限流准确度要求不高的情况下，也经常有使用到，以下是Apinto网关用固定窗口进行限流的实际场景应用。

//固定窗口结构体
type rateTimer struct {
        // 已请求数量
        requestCount     int64
        // 限制数量
        limitCount        int64
        timerType int
        expire    time.Duration
        startTime time.Time
}


// 检查是否超过了限制
func (r *rateTimer) check() bool {
        if time.Now().Sub(r.startTime) > r.expire {
                r.reset()
                return true
        }
        c := atomic.LoadInt64(&r.requestCount)
        localCount := c + 1
        r.add()
        if localCount > r.limitCount {
                return false
        }
        return true
}

2.2 滑动窗口统计

滑动窗口统计是一种流量统计方式。它将时间划分为固定长度的时间窗口，但每个时间窗口的开始和结束时间是根据当前时间动态滑动的。在每个时间窗口内，统计通过系统的请求数量，并根据窗口的滑动来更新统计数据。

一文了解限流策略的原理与实现

在滑动窗口统计中主要涉及两个概念：

统计周期：其中统计周期即为采样周期，比如设定1s最多通过2次请求，这里的1s则是统计周期。
窗口大小：一个统计周期内的最小统计单元，比如下图，1s时间划分成4个小窗口，每个窗口负责的采样大小即为250ms，窗口越小，一个统计周期内窗口数量越多，则统计越精准（由于最后一个小窗口总是处于未完成统计的状态，实际的统计周期总比设定的统计周期要小）。

一文了解限流策略的原理与实现

滑动窗口中小窗口数据结构设计上需要包含窗口统计的“开始时间”以及在需要“被统计的元素”的基本信息（这里主要是当前窗口通过的请求数），小窗口设计数据结构如下BucketWrap所示。

//小窗口的设计
type BucketWrap struct {
   // BucketStart represents start timestamp of this statistic bucket wrapper.
   BucketStart uint64
   // Value represents the actual data structure of the metrics (e.g. MetricBucket).
   Value atomic.Value
}


type AtomicBucketWrapArray struct {
   // The base address for real data array
   base unsafe.Pointer // 窗口数组首元素地址
   // The length of slice(array), it can not be modified.
   length int // 窗口数组的长度
   data   []*BucketWrap //窗口数组
}

同时，一个统计周期是由多个小窗口顺序组合而成，设计上为了避免内存空间使用上的浪费，采用原子时间轮的方式来将小窗口进行收尾相连，以循环队列的方式进行编排，数据结构是AtomicBucketWrapArray，示意图如下。

一文了解限流策略的原理与实现

当前时间对应的窗口可以通过计算时间戳取模得到。如果请求在当前窗口内，则记录请求，更新窗口内的请求次数。如果当前时间已经超过了当前窗口，就开始一个新的采样周期，即重置窗口开始时间和请求计数。

比如此刻的时间戳是300ms，计算当前时刻的下标是(300/200)%8=1，当前窗口的开始时间是200ms；通过计算出来的窗口的开始时间与当前时间一致，则记录请求。如果时间划拨到了下一个采样周期，比如此刻时间是1801ms，计算的下标是(1801/200)%8=1，开始时间是1800ms，由于窗口记录的开始时间是200ms，则表示当前窗口的数据超采样周期了，将下标为1的窗口开始时间重置为1800ms，并对重置窗口记录，作为新的采样周期进行统计计数。

// 计算开始时间
func calculateStartTime(now uint64, bucketLengthInMs uint32) uint64 {
   return now - (now % uint64(bucketLengthInMs))
}
// 窗口下标位置
func (la *LeapArray) calculateTimeIdx(now uint64) int {
    timeId := now / uint64(la.bucketLengthInMs)
    return int(timeId) % la.array.length
}

一文了解限流策略的原理与实现

要获取滑动窗口采样周期内通过的请求数，主要方式是将原子时间轮进行遍历，将符合条件的采样窗口中请求数进行累加统计。

// 匹配符合条件的窗口
func (la *LeapArray) ValuesConditional(now uint64, predicate base.TimePredicate) []*BucketWrap {
   if now <= 0 {
      return make([]*BucketWrap, 0)
   }
   ret := make([]*BucketWrap, 0, la.array.length)
   for i := 0; i < la.array.length; i++ {
      ww := la.array.get(i)
      if ww == nil || la.isBucketDeprecated(now, ww) || !predicate(atomic.LoadUint64(&ww.BucketStart)) {
         continue
      }
      ret = append(ret, ww)
   }
   return ret
}

3. 限流判断

通过上述采样窗口的设计，我们可以获取任何一个采样周期内通过的请求数。通过流量统计，我们可以得到当前时间窗口内的请求量和相关数据，将其与限流规则进行比较，以判断当前请求是否满足通过条件。如果请求满足通过条件，则可以直接通过，否则需要进行限流措施。

常用的限流判断方式是令牌桶算法。该算法基于令牌桶的概念，即以固定的速率向令牌桶中添加令牌。每次请求需要从令牌桶中获取一个令牌才能被处理。如果令牌桶中没有足够的令牌，则请求将被暂时阻塞或拒绝，直到令牌桶中有足够的令牌可以被获取。

一文了解限流策略的原理与实现

限流判断的核心在于计算当前时刻允许通过的令牌数，即token的计算策略。主要的计算策略包括固定阈值、预热以及内存自适应三种。

3.1 固定阈值（Threshold）

这种token计算策略比较简单，它的意思是在一个统计周期内允许通过的请求数是固定的。只需要比较统计周期内统计的通过请求数和阈值，就能判断当前请求是否需要被限流。

func (d *DirectTrafficShapingCalculator) CalculateAllowedTokens(uint32, int32) float64 {
   return d.threshold
}

然而，固定阈值的方式存在一个问题，即在流量突增的情况下，通过的请求数会一瞬间达到阈值，容易对下游系统造成较大压力，简单来说，过刚易折，因此，另一种提前预热的策略应运而生。

3.2 预热（WarmUp）

基于固定阈值的token计算方案存在一个问题，即在流量突增的情况下，通过的请求数会一瞬间达到阈值，容易对下游系统造成较大压力。因此，期望流量能够经过一段时间的预热再达到阈值，这样能给下游系统一定的缓冲时间。

下图展示了预热（冷启动）过程中允许通过请求数随时间变化的关系图。该方案的主要设计要求包括：

当流量较低时，不进行限流。（下图1->3）
当流量达到冷启动阈值时，触发系统的冷启动策略。(下图3)
经过一段时间的预热后，允许通过的请求数达到设定的阈值，并保持不变。（下图2）
当流量下降后再次突增时，同样需要再次触发冷启动策略。

一文了解限流策略的原理与实现

为了满足设计要求，我们需要设计一个预热算法，其中启动阈值的设计非常关键。为此，我们引入了一个冷却因子的概念（coldFactor），它控制着触发冷启动的先决条件。具体来说，触发冷启动所需的请求量为 Threshold/coldFactor，如下图所示。可以看出，冷却因子越小，启动预热的阈值就越高。例如，当冷却因子为2时，需要达到阈值的一半才会开始启动预热。

一文了解限流策略的原理与实现

在预热过程中间，需要设计一些变量来控制令牌桶的运作。具体来说，我们可以采用以下的变量：

storeToken：代表令牌桶中当前的令牌数。该变量与允许通过的请求数量成负相关，即storeToken越小，允许通过的请求越多，直到达到指定的阈值。
maxToken：代表令牌桶的最大容量，在预热启动时，storeToken的值为maxToken。
warningToken：代表令牌桶的预警数量，在预热结束时，storeToken的值为warningToken。
aboveToken：代表距离预热结束还剩余的令牌数量，即storeToken与warningToken的差值。这个变量用于辅助计算当前允许通过的请求数量。
slope：代表斜率，用来计算生成每个令牌所需的时间间隔。

warningToken := uint64((float64(rule.WarmUpPeriodSec) * rule.Threshold) / float64(rule.WarmUpColdFactor-1))


maxToken := warningToken + uint64(2*float64(rule.WarmUpPeriodSec)*rule.Threshold/float64(1.0+rule.WarmUpColdFactor))


slope := float64(rule.WarmUpColdFactor-1.0) / rule.Threshold / float64(maxToken-warningToken)




//允许通过过请求数计算，当restToken=warningToken预热过程结束
if restToken >= int64(c.warningToken) {
    aboveToken := restToken - int64(c.warningToken)
    warningQps := math.Nextafter(1.0/(float64(aboveToken)*c.slope+1.0/c.threshold), math.MaxFloat64)
    return warningQps
} else {
    return c.threshold
}

一文了解限流策略的原理与实现

以下是生产令牌的条件：

达到 warningToken 阈值：即预热阶段结束并到达指定阈值。
通过的请求数passQps 低于Threshold/coldFactor：未满足预热条件，正常生产令牌。

综上来说，在遇见突发流量的预热过程中会停止令牌的生成，此过程会不断消耗令牌，直到桶里的令牌数到达warningToken，结束预热，重新生产令牌。

oldValue := atomic.LoadInt64(&c.storedTokens)
if oldValue < int64(c.warningToken) {
           newValue = int64(float64(oldValue) + (float64(currentTime)-float64(atomic.LoadUint64(&c.lastFilledTime)))*c.threshold/1000.0)
} else if oldValue > int64(c.warningToken) {
    if passQps < float64(uint32(c.threshold)/c.coldFactor) {
        newValue = int64(float64(oldValue) + float64(currentTime-atomic.LoadUint64(&c.lastFilledTime))*c.threshold/1000.0)
    }
}

预热过程（上图从右往左看）：

当流量通过较少时，令牌桶不断填充新的令牌，因为未达到预热阈值（threshold/coldFactor）且消耗的令牌数少于分配的令牌数，令牌桶中的 storeToken 逐渐填满，接近于 maxToken后保持稳定。
当流量突然增加时，达到预热阈值，此时令牌桶停止生成新令牌，但由于不断有请求通过，令牌桶中的令牌不断消耗，导致 storeToken 从右上角的 maxToken 向左下角的 warningToken 移动。
经过预设的预热时间，令牌桶容量达到 warningToken 预警数量，此时 aboveToken 为 0，预热结束，允许的通过请求数达到最大阈值，此时生产的令牌与消耗的令牌相等，令牌桶中令牌数保持稳定。

对于预热我们做了一个仿真，以下是仿真的过程，在 Threshold 设定为 10，codeFactor 设定为 3 的情况下，参数随时间变化的情况如下图所示。

第一阶段：流量突增，正常冷启动过程，此时storeToken从最大值往warningToken移动，允许通过的流量逐步上升到指定的阈值10
第二阶段：限流阶段，超过阈值10的请求都被限流
第三阶段：请求量下降到2，在Threshold/coldFactor（3.33）以下，正常为storeToken分配令牌，storeToken主键补充到maxToken后停止增加，此时请求都正常通过
第四阶段：流量再次突增，重复冷启动的过程直到达到请求阈值
第五阶段：限流阶段
第六阶段：请求量下降到4，小于阈值且大于Threshold/coldFactor（3.33），此时storeToken在小于warningToken时候正常分配令牌，在大于warningToken的时候停止分配令牌，但会按实际的请求量消耗令牌，从而使得storeToen在warningToken附近左右横跳。

通过仿真可以发现，在面对突发流量时，真实允许通过的请求量需要经过一段时间的预热才能到达指定阈值。并且随着真实请求量的变化，预热过程可以来回进行，符合预热设计的预期。

一文了解限流策略的原理与实现

3.3 内存自适应

这是一种根据机器使用内存的多少来动态调节token数量的计算方式。其核心思想是在内存使用较少的情况下，允许通过的请求数量越高；而在内存使用较多的情况下，允许通过的请求数量将会降低。该方式会根据设定的阈值范围，随着内存使用量的增加而线性调整。

{
   Resource:               resName,
   TokenCalculateStrategy: flow.MemoryAdaptive,
   ControlBehavior:        flow.Reject,
   StatIntervalInMs:       1000,
   LowMemUsageThreshold:   1000, // 低水位限流阈值
   HighMemUsageThreshold:  100,  // 高水位限流阈值
   MemLowWaterMarkBytes:  1024,  // 低水位内存字节
   MemHighWaterMarkBytes: 2048,  // 高水位内存字节
}

在上述配置中，下图显示了内存实际使用量与允许通过请求量的变化关系。然而，在实际线上情况下，大部分情况下是由于请求量增长导致CPU增加，而不是因为内存使用量突然增加而需要进行限流，因此这种限流方式使用较少，或者可以采用类似的思路来实现基于cpu的自适应方式的限流方式的开发。

一文了解限流策略的原理与实现