限速器算法

限速器

限速模拟器

限速器类型

• Leaky Bucket：漏桶算法(和令牌桶(token bucket)非常相似)是一种非常简单，使用队列来进行限流的算法。当接收到一个请求时，会将其追加到队列的末尾，系统会按照先进先出的顺序处理请求，一旦队列满，则会丢弃额外的请求。队列中的请求数目受限于队列的大小。
  
  这种方式可以缓解突发流量对系统的影响，缺点是在流量突发时，由于队列中缓存了旧的请求，导致无法处理新的请求。而且也无法保证请求能够在一定时间内处理完毕。
• 
  

令牌桶不会缓存请求，它通过颁发令牌的方式来允许请求，因此它存在和漏桶算法一样的问题。

• Fixed Window：该系统使用n秒的窗口大小(通常使用人类友好的值，例如60或3600秒)来跟踪固定窗口下的请求速率。每接收到一个请求都会增加计算器，当计数器超过阈值后，则会丢弃请求。通常当前时间戳的下限来定义定义窗口，如12:00:03(窗口长度为60秒)将位于12:00:00的窗口中。
  
  该算法可以保证最新的请求不受旧请求的影响。但如果在窗口边界出现突发流量，由于短时间内产生的流量可能会同时被计入当前和下一个窗口，因此可能会导致请求速率翻倍。如果有多个消费者等待窗口重置，则在窗口重置后的一开始会出现踩踏效应。跟漏桶算法一样，固定窗口算法是针对所有消费者而非单个消费者进行限制的。
• 
  
• Sliding Log：滑动日志会跟踪每个消费者的请求对应的时间戳日志。系统会将这些日志保存在按时间排序的哈希集或表中，并丢弃时间戳超过阈值的日志。当接收到一个请求后，会通过计算日志的总数来决定请求速率。如果请求超过速率阈值，则暂停处理该请求。
• 
  
  这种算法的优点在于它不存在固定窗口中的边界限制，因此在限速上更加精确。由于系统会跟踪每个消费者的滑动日志，因此也不存在固定窗口算法中的踩踏效应。
• 
  但保存无限量的请求会带来存储成本，且该算法在接收到请求时都需要计算消费者先前的请求总和(有可能需要跨服务器集群进行运算)，因此计算成本也很高。基于上述原因，该算法在处理突发流量或DDos攻击等问题上存在扩展性问题。
• 
  
• Sliding Window：滑动窗口算法结合了固定窗口算法中的低成本处理以及滑动日志中对边界条件的改进。像固定窗口算法一样，该算法会为每个固定窗口设置一个计数器，并根据当前时间戳来考虑前一窗口中的请求速率的加权值，用来平滑突发流量。
• 
  例如，假设有一个每分钟允许100个事件的限速器，此时当前时间到了75s点，那么内部窗口如下：
  

此时限速器在15秒前开始的当前窗口期间(15s~75s)内已经允许了12个事件，而在前一个完整窗口期间允许了86个事件。滑动窗口内的计数近似值可以这样计算：

count = 86 * ((60-15)/60) + 12
      = 86 * 0.75 + 12
      = 76.5 events

86 * ((60-15)/60)为与上一个窗口重叠的计数，12为当前窗口的计数

由于每个关键点需要跟踪的数据量相对较少，因此能够在大型集群中进行扩展和分布。

推荐使用滑动窗口算法，它在提供灵活扩展性的同时，保证了算法的性能。此外它还避免了漏桶算法中的饥饿问题以及固定窗口算法中的踩踏效应。

分布式系统中的限速

可以采用中央数据存储(如redis或Cassandra)的方式来实现多节点集群的全局限速。中央存储会为每个窗口和消费者收集请求次数。但这种方式会给请求带来延迟，且存储可能会存在竞争。

在采用get-then-set(即获取当前的限速器计数，然后增加计数，最后将计数保存到数据库)模式时可能会产生竞争，导致数据库计数不一致。

解决该问题的一种方式是使用锁，但锁会带来严重的性能问题。更好的方式是使用set-then-get模式，并依赖原子操作来提升性能。

性能优化

即使是Redis这种快速存储也会给每个请求带来毫秒级的延迟。可以采用本地内存检查的方式来最小化延迟。

为了使用本地检查，需要放宽速率检查条件，并使用最终一致性模型。例如，每个节点都可以创建一个数据同步周期，用来与中央数据存储同步。每个节点周期性地将每个消费者和窗口的计数器增量推送到数据库，并原子方式更新数据库值。然后，节点可以检索更新后的值并更新其内存版本。在集中→发散→再集中的周期中达到最终一致。

同步周期应该是可配置的，当在集群中的多个节点间分发流量时，较短的同步间隔会降低数据点的差异。而较长的同步间隔会减少数据存储的读/写压力，并减少每个节点获取新同步值所带来的开销。

Golang中的滑动窗口

Golang的滑动窗口实现比较好的实现有mennanov/limiters和RussellLuo/slidingwindow，个人更推荐后者。下面看下RussellLuo/slidingwindow的用法和实现。

简单用法

下面例子中，创建了一个每秒限制10个事件的限速器。lim.Allow()会增加当前窗口的计数，当计数达到阈值(10)，则会返回false。

package main
import (
  "fmt"
  sw "github.com/RussellLuo/slidingwindow"
  "time"
)
func main() {
  lim, _ := sw.NewLimiter(time.Second, 10, func() (sw.Window, sw.StopFunc) {
    return sw.NewLocalWindow()
  })
  for i := 1; i < 12; i++ {
    ok := lim.Allow()
    fmt.Printf("ok: %v\n", ok)
  }
}

对外接口如下：

• lim.SetLimit(newLimit int64)：设置窗口大小
• lim.Allow()：就是AllowN(time.Now(), 1)
• lim.AllowN(now time.Time, n int64)：判断当前窗口是否允许n个事件，如果允许，则当前窗口计数器+n，并返回true，反之则返回false
• lim.Limit()：获取限速值
• lim.Size()：获取窗口大小

实现

首先初始化一个限速器，NewLimiter的函数签名如下：

func NewLimiter(size time.Duration, limit int64, newWindow NewWindow) (*Limiter, StopFunc)

• size：窗口大小
• limit：窗口限速
• newWindow：用于指定窗口类型。本实现中分为LocalWindow和SyncWindow两种。前者用于设置单个节点的限速，后者用于和中央存储联动，可以实现全局限速。

下面看下核心函数AllowN和advance的实现：

实现中涉及到了3个窗口：当前窗口、当前窗口的前一个窗口以及滑动窗口。每个窗口都有计数，且计数不能超过限速器设置的阈值。当前窗口和当前窗口的前一个窗口中保存了计数变量，而滑动窗口的计数是通过计算获得的。

// AllowN reports whether n events may happen at time now.
func (lim *Limiter) AllowN(now time.Time, n int64) bool {
  lim.mu.Lock()
  defer lim.mu.Unlock()
  lim.advance(now)//调整窗口
  elapsed := now.Sub(lim.curr.Start())
  weight := float64(lim.size-elapsed) / float64(lim.size)
  count := int64(weight*float64(lim.prev.Count())) + lim.curr.Count() //计算出滑动窗口的计数值
  // Trigger the possible sync behaviour.
  defer lim.curr.Sync(now)
  if count+n > lim.limit { //如果滑动窗口计数值+n大于阈值，则说明如果运行n个事件，会超过限速器的阈值，此时拒绝即可。
    return false
  }
  lim.curr.AddCount(n) //如果没有超过阈值，则更新当前窗口的计数即可。
  return true
}

// advance updates the current/previous windows resulting from the passage of time.
func (lim *Limiter) advance(now time.Time) {
  // Calculate the start boundary of the expected current-window.
  newCurrStart := now.Truncate(lim.size) //返回将当前时间向下舍入为lim.size的倍数的结果，此为预期当前窗口的开始边界
  diffSize := newCurrStart.Sub(lim.curr.Start()) / lim.size
  if diffSize >= 1 {
    // The current-window is at least one-window-size behind the expected one.
    newPrevCount := int64(0)
    if diffSize == 1 {
      // The new previous-window will overlap with the old current-window,
      // so it inherits the count.
      //
      // Note that the count here may be not accurate, since it is only a
      // SNAPSHOT of the current-window's count, which in itself tends to
      // be inaccurate due to the asynchronous nature of the sync behaviour.
      newPrevCount = lim.curr.Count()
    }
    lim.prev.Reset(newCurrStart.Add(-lim.size), newPrevCount)
    // The new current-window always has zero count.
    lim.curr.Reset(newCurrStart, 0)
  }
}

advance函数用于调整窗口大小，有如下几种情况：

需要注意的是，newCurrStart 和lim.curr.Start()相差0或多个lim.size，如果相差0，则newCurrStart等于lim.curr.Start() ，此时滑动窗口和当前窗口有重叠部分。

• 如果diffSize == 1说明记录的当前窗口和预期的当前窗口是相邻的(如下图)。
  因此需要将记录的当前窗口作为前一个窗口(lim.prev)，并将预期的当前窗口作为当前窗口，设置计数为0。转化后的窗口如下：
  
• 如果如果diffSize > 1说明记录的当前窗口和预期的当前窗口不相邻，相差1个或多个窗口(如下图)，说明此时预期的当前窗口的前一个窗口内没有接收到请求，因而没有对窗口进行调整。
  此时将前一个窗口的计数设置为0。并将预期的当前窗口作为当前窗口，设置计数为0。
  

此时AllowN中的运算如下：

1. 计算出当前时间距离当前窗口开始边界的差值(elapsed)
2. 计算出滑动窗口在前一个窗口中重叠部分所占的比重(百分比)
3. 使用滑动窗口在前一个窗口中重叠部分所占的比重乘以前一个窗口内的计数，再加上当前窗口的计数，算出滑动窗口的当前计数
4. 如果要判断滑动窗口是否能够允许n个事件，则使用滑动窗口的当前计数+n与计数阈值进行比较。如果小于计数阈值，则允许事件，并让滑动窗口计数+n，否则返回false。

• 如果diffSize<1，说明滑动窗口和当前窗口有重叠部分，此时不需要调整窗口。AllowN中的运算与上述逻辑相同：