限流算法—令牌桶和漏桶

缺乏、安全感 2022-10-27 15:00 197阅读 0赞

转自：[https://blog.csdn.net/m\_\_l\_\_/article/details/109175787][https_blog.csdn.net_m_l_article_details_109175787]

## 令牌桶算法： ##

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

*  假设限制2r/s，则按照500毫秒的固定速率往桶中添加令牌。
 *  桶中最多存放b个令牌，当桶满时，新添加的令牌被丢弃或拒绝。
 *  当一个n个字节大小的数据包到达，将从桶中删除n个令牌，接着数据包被发送到网络上。
 *  如果桶中的令牌不足n个，则不会删除令牌，且该数据包将被限流（要么丢弃，要么在缓冲区等待）。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fX0xfXw_size_16_color_FFFFFF_t_70_pic_center]

## 漏桶算法： ##

*  一个固定容量的漏桶，按照常量固定速率流出水滴。
 *  如果桶是空的，则不需要流出水滴。
 *  可以以任意速率流入水滴到漏桶。
 *  如果流入水滴超过了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fX0xfXw_size_16_color_FFFFFF_t_70_pic_center 1]  
    **令牌桶和漏桶算法对比：**
 *  令牌桶是按照固定速率往桶中添加令牌，请求是否被处理需要看桶中令牌是否足够，当令牌数减为零时，则拒绝新的请求。
 *  漏桶则是按照常量固定速率流出请求，流入请求速率任意，当流入的请求数累积到漏桶容量时，则新流入的请求被拒绝。
 *  令牌桶限制的是平均流入速率（允许突发请求，只要有令牌就可以处理，支持一次拿3个令牌，或4个令牌），并允许一定程度的突发流量。
 *  漏桶限制的是常量流出速率（即流出速率是一个固定常量值，比如都是1的速率流出，而不能一次是1，下次又是2），从而平滑突发流入速率。
 *  令牌桶允许一定程度的突发，而漏桶主要目的是平滑流入速率。
 *  两个算法实现可以一样，但是方向是相反的，对于相同的参数得到的限流效果是一样的。

[https_blog.csdn.net_m_l_article_details_109175787]: https://blog.csdn.net/m__l__/article/details/109175787
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fX0xfXw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/5f79563d409c462e917ac682f9091591.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fX0xfXw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221024/072fee36f93a450b93caf68ba0063a02.png