分布式 漏桶算法 总结

前言

---

 相关系列

• 《分布式 & 目录》
• 《分布式 & 漏桶算法 & 总结》
• 《分布式 & 漏桶算法 & 问题》
   
   

概述

---

简介

    LBA @ Leaky Bucket Algorithm @ 漏桶算法是一种流行于网络通信领域的流量控制/频率限制算法。漏桶算法的核心原理是通过一个概念上的“漏桶”来控制请求的访问频率，这个漏桶会在指定的容量范围内接收&保存所有的请求，并以指定的频率将请求渗出以允许其正式访问系统，从而达到持续控制请求访问数量&频率的效果。
 

场景

• 限制网络带宽：控制访问流量；
• 限制API频率：限制API调用频率；
• 功能分级：为不同级别的用户提供不同频率的服务；
• 任务调度：限制任务执行频率以避免资源争用。
   
   

原理

---

 

概念

• 漏桶：用于存放请求的概念容器，通常使用Redis一类的中间件配合队列结构实现；
• 漏桶容量：漏桶所能保存的最大请求数量，一般是系统平均QPS * 最大延迟时间；
• 请求泄漏/渗出频率：漏桶向系统发送请求的频率，通常是系统的平均QPS。
   

流程

• 客户端访问系统，在网关被拦截。随后网关会判断当前请求是否免限流，是则直接访问；
• 如果当前请求限流，则网关会继续判断漏桶是否已满，是则直接拒绝请求；否则将请求置于漏桶中等待；
• 网关会以指定频率从漏桶中取出请求以允许按预期目的访问系统。
   

缺点

• 漏桶算法不太合适处理同步/即时请求，因为请求在被置于漏桶中处理时需要连同线程一同保存/等待，这可能会耗尽系统线程池的资源，并且请求在漏桶中的等待时间也可能难以评估，因此漏桶算法其实更适用于处理异步请求；
• 漏桶算法难以/无法处理流量高发/突发的情况，因为其泄露/渗出请求的频率是始终不变的。