限流的算法

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

计数器

• 设定单位时间限制接口的请求数量为n，单位时间内的每次请求加1，如果超过请求数量的限制，则拒绝或者等待下一个单位时间的但来，缺点：请求不均衡，导致响应不平滑，有时集中、有时稀疏

令牌桶算法

令牌桶算法是一个存放固定容量令牌的桶，按照固定速率往桶里添加令牌。令牌桶算法的描述如下：

• 假设限制 2r/s ，则按照 500 毫秒的固定速率往桶中添加令牌；
• 桶中最多存放 b 个令牌，当桶满时，新添加的令牌被丢弃或拒绝；
• 当一个 n 个字节大小的数据包到达，将从桶中删除 n 个令牌，接着数据包被发送到网络上；（或者说n个请求，请求想要执行必须先拿到执行令牌，同时令牌桶内相应的减少n个令牌，没拿到令牌的请求被拒绝或者等待）
• 如果桶中的令牌不足 n 个，则不会删除令牌，且该数据包将被限流（要么丢弃，要么缓冲区等待）。

漏桶算法

漏桶作为计量工具（ The Leaky Bucket Algorithm as a Meter ）时，可以用于流量整形（ Traffic Shaping ）和流量控制（ TrafficPolicing ），漏桶算法的描述如下：

• 一个固定容量的漏桶，按照常量固定速率流出水滴；
• 如果桶是空的，则不需流出水滴；
• 可以以任意速率流入水滴到漏桶；
• 如果流入水滴超出了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。