限流相关算法
1、漏桶算法
用于流量整形及流量控制
其算法描述为
- 对于固定容量的漏桶，以固定的速率流出水滴
- 如果桶是空的，则不需流出水滴
- 可以以任意速率流入水滴到漏桶
- 如果流入水滴超出的桶的容量，则流入的水滴溢出了，而漏桶容量不变
2、令牌桶算法
是一个存放固定容量令牌的桶，按照固定速率往桶里添加令牌。
算法描述为
- 按照固定的速率往桶里添加令牌
- 桶中最多存放b个令牌，当桶满时，新添加的令牌被丢弃
- 当请求令牌资源n时，从桶中删除n个令牌。
- 如果桶中的令牌不足n个，则不会删除令牌，要么等待或者丢弃。
3、区别
- 漏桶是按照常量固定速率流出请求，流入请求速率任意。当流入的请求数累积到漏桶容量时，新流入的请求被拒绝。令牌桶是按照固定速率往桶中添加令牌，请求是否被处理需要看桶中令牌是否足够，当令牌减为零时，新请求被拒绝
- 漏桶限制的常量流出速率，从而平滑突发流入速率。令牌桶限制的是平均流入速率，允许突发请求，并允许一定程度的突发流量。