【限流算法】计数器、漏桶、令牌桶算法

 

1 计数器

使用计数器实现限流，可限制在指定时间间隔内请求数小于阈值的情况，但存在临界问题。如图1-17所示，假设每分钟系统限流500个请求，在XX:00:59时刻系统接收到500个请求，在XX:01:00时刻系统又接收到500个请求，那么系统在1秒内就处理了1000个请求，超出了1分钟限流500个请求的要求。

为此引入滑动窗口解决该问题，如图1-18所示，加粗黑色竖线为滑动窗口左右边界，窗口大小为1分钟，窗口被划分成6个格子，每个格子代表10秒钟，每过10秒钟，时间窗口往右滑动一格。每个格子都有独立的计数器，比如一个请求在XX:00:06时刻到达，那么XX:00:00～XX:00:09对应的计数器就会加1。

结合图1-17和图1-18，XX:00:59时刻到达的500个请求会落在第6个灰色格子里，而XX:01:00到达的500个请求会落在第7个格子中，但当时间到达XX:01:00时，窗口会往右滑动一格，此时时间窗口内的总请求数为1000个，可以触发系统500个请求的限流。因此，滑动窗口能够解决计数器临界问题，窗口中的格子时间粒度越细，限流的统计就会越准确。

2 漏桶算法

漏桶算法如图1-19所示，把请求当作水流，桶为系统容量，水来了先存入桶里，并以最大恒定速率放水，桶满水溢出则代表拒绝服务。

当桶中没有积水时：

● 若进水速度小于或等于出水速度，则出水速率等于进水速率。

● 若进水速度大于出水速度，则多余的水积压在桶中。

当桶中有水时：

● 若漏桶未满，则进水会积压在漏桶中。

● 若漏桶已满，则进水溢出桶外

3 令牌桶算法

令牌桶算法如图1-20所示。令牌桶算法的思想是以恒定速率生产令牌并放入令牌桶中，用户每次请求都得申请令牌，如果令牌不足，则拒绝请求；当令牌桶已满时，若再向桶中投放令牌，则多余的令牌会被丢弃。

该算法的特点是以恒定速率生产令牌，可以接收突发流量。