系统设计之限流

对于有庞大用户量的系统必然会遇到某一个时段业务高峰。由于前期性能预估不足、业务量急增，而某个系统组件性能存在瓶颈，该组件无法工作，整个系统请求拥堵。

在高可用系统中，限流是解决此类问题的一个性价比很高的技术手段。通过限流，在大量请求的高压之下仍可以在保证整个系统在其能力范围内稳定的工作。

限流大致有几个措施：
消息队列（MQ）业务请求先写入MQ，后台系统从MQ读取业务请求，MQ做为缓冲区。后台系统躲在MQ后面，不直接承受业务压力，可以稳定对于业务请求进行服务。使用MQ的场景一般是业务的实时要求不高，业务请求可以延时处理。如下图，P（producer） 负责将业务请求写入队列， C(consumer)负责读入请求，进行服务。

令牌桶算法（token bucket）网络设备多用token bucket实现流量整形和流量限速，而后台系统也多用它来使用流量控制。如nginx的limit_req模块就是基于此实现的。
假设每秒产生r个token。算法概要：

1. 所有的流量在放行之前需要获取一定量的 token；
2. 每 1/r 秒，都会往bucket（桶） 当中加入一个 token；
3. bucket 有最大容量，在 bucket 中的 token 数量等于最大容量，新的额外的 token 会被抛弃。

当业务请求进来时：若bucket里有剩余的token，那么bucket里的token数减一，将请求放进来，为它提供服务。若bucket里没有token时，就直接回绝请求。
如下图示：

可以形象理解为在干旱地区一个不停往下滴水的水龙头，人们想喝水，只能用桶接，人可以拿起水瓢舀点水喝，可以等半天积满，一次喝个够，也可以等一会儿喝一小口，你随便。但是如果这会儿桶里的水喝光了，对不起，你只能慢慢等了。
漏桶算法(leaky bucket)
原理如下图（图来自wikipedia)

业务请求用水滴来类比，水滴可以断断续续进入水桶中，水桶底部有一个洞，可以均速往下漏水，当进入水桶的水速度过多时，水桶中积水便会溢出。
通过桶底的洞漏出来的水滴，就是进入系统得到服务的业务请求。
漏桶算法和令牌桶算法区别在于：漏桶算法后端服务只能匀速的接受业务请求，而令牌桶算法可以在一定程度允许后台服务程序承受一定量的突发情求。最大突发量就是bucket的容量。
计数器
计数器算法最简单，假设1秒允许100请求。

• 1秒内每接受一个请求，counter++；
• 当counter < 100 时， 请求运行进入。
• 当counter >= 100时，禁止请求进入。
• 下一秒， counter清空，重新执行第一步的算法。

这个算法的弊病，实际流量会呈锯齿状，控制不准。

token bucket等算法在上古时代（UNIX时代）的网络设备就已经广泛采用了。直到现在仍然在发光发热，这也侧面说明越本质的东西，其生命周期就越长。