令牌桶算法
前言
在开发高并发系统时，有三把利器用来保护系统：缓存、降级和限流。本文围绕限流，讨论令牌桶相关算法。
背景
令牌桶算法最初来源于计算机网络。在网络传输数据时，为了防止网络拥塞，需限制流出网络的流量，使流量以比较均匀的速度向外发送。
令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。
流程
- 产生令牌：周期性的以一定速率往令牌桶中增加令牌。如果桶中的令牌数达到桶容量，丢弃多余令牌。
- 消耗令牌：接受请求或输入数据时会消耗桶中的令牌。以请求或消息为单位时，可以一次消耗一个令牌。在网络传输中，消耗令牌的数量可以根据数据包的大小决定。
- 是否通过：
桶中的令牌 >= 所需令牌时，请求或者数据包通过，否者被限流。对于被限流的请求或者数据包，可以有不同的处理方式。（1、直接丢弃；2、进队列等待； 3、可以通过，但需要做特殊标记）