限流算法

概要

限流目的是通过对并发访问/请求进行限速或者一个时间窗口内的请求进行限速来保护系统,一旦达到限制速率则可以拒绝服务、排队或者等待、降级。

限流算法

常见的限流算法有:令牌桶算法、漏桶算法、计数器算法。

1、令牌桶算法

令牌桶算法是一个存放固定容量令牌的桶,按照固定速率往桶里添加令牌。

  • 假设限制2r/s,则每500毫秒向桶中添加令牌
  • 桶总最多存放b个令牌,当桶满时,新添加的令牌被丢弃或者拒绝
  • 当一个n字节的请求到达,将从桶中删除n个令牌,接着请求被放行
  • 如果桶中的令牌不足n个,则不会删除令牌,且该请求将被限速(被丢弃或在缓冲区等待)

2、漏桶算法

漏桶算法非常简单。

  • 一个固定容器的漏桶,按照固定速率放行请求
  • 请求可以以任意速率请求到漏桶
  • 如果请求超出桶的容量,则请求将被限速(被丢弃)

3、计数器算法

计数器主要用来限制总并发数,只要全局总请求数或者一定时间段的总请求数达到设定的阈值,则进行限速。该算法是一种简单粗暴的总数量限流,而不是平均速率限流。

区别

  • 令牌桶是按照固定速率往桶中添加令牌,请求是否被处理需要看桶中令牌是否足够,当令牌数减至0时,则拒绝新的请求
  • 漏桶则是按照固定速率流出请求,流入请求速率任意,当流入的请求数累积到漏桶容量时,则新流入的请求被拒绝
  • 令牌桶限制的是平均速率(允许突发请求),并允许一定程度的突发流量
  • 漏桶限制的是流出速率,从而平滑突发请求
  • 令牌桶和漏桶算法实现可以一样,但是方向是相反的,对于相同参数得到的流速效果一样
  • 计数器算法是总数量限流,令牌桶和漏桶都是平均速率限流