33｜限流算法：如何防止系统过载？
黄清昊
该思维导图由 AI 生成，仅供参考
你好，我是微扰君。
上一讲我们学习了业务场景中频繁会使用到的延时队列，能帮助处理很多业务上的定时任务问题，因为这个组件的功能和具体业务往往没有关系，我们通常会利用各种中间件来实现延时队列的能力。
今天我们来探讨另外一个算法的原理和实现，它也和业务本身没有强关联，但是在各个业务场景下都非常常见，那就是限流算法。
限流算法，也被我们常称为流控算法，顾名思义就是对流量的控制。日常生活中有很多例子，比如地铁站在早高峰的时候，会利用围栏让乘客们有序排队，限制队伍行进的速度，避免大家一拥而上，这就是一种常见的限流思路；再比如在疫情期间，很多景点会按时段限制售卖的门票数量，避免同一时间在景区的游客太多等等。
这些真实生活中的方案本质都是因为在某段时间里资源有限，我们需要对流量施以控制。其实同样的，在互联网的世界里，很多服务，单位时间内能承载的请求也是存在容量上限的，我们也需要通过一些策略，控制请求数量多少，实现对流量的控制。
当然在工程中，“流量”的定义也是不同的，可以是每秒请求的数量、网络数据传输的流量等等，所以在不同的场景下，我们也需要用不同的方式限制流量，以保证系统不至于被过多的流量压垮。虽然，限流一定会导致部分请求响应速度下降或者直接被拒绝，但是相比于系统直接崩溃的情况，限流还是要好得多。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
限流算法在控制流量方面起着重要作用，可以避免系统过载。本文介绍了限流算法的重要性以及在业务开发中的常见场景。针对限流算法的实现，文章提出了基于计数的限流器和基于滑动窗口的限流器两种算法，并详细讨论了它们的原理和实现方式。此外，文章还介绍了漏桶算法和令牌桶算法，并着重介绍了令牌桶算法及其代码实现。通过对这些限流算法的介绍，读者可以更好地理解限流算法的原理和应用，为系统的流量控制提供有效的支持。文章还总结了不同限流算法的特点和适用场景，提醒读者在选择实现方式时需权衡各自的优缺点。最后，文章提出了课后习题，鼓励读者实现漏桶算法，并思考其他内存使用更少的实现方式。整体而言，本文全面介绍了限流算法的原理、实现和应用，对于需要进行流量控制的开发人员具有一定的参考价值。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《业务开发算法 50 讲》，新⼈⾸单¥59
《业务开发算法 50 讲》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(7)
- 最新
- 精选
乔克叔叔这个rate什么含义作者回复: 限流用英文说就是ratelimit rate本身有速率得意思
2022-04-281- 乔克叔叔漏桶算法好像消息队列的削峰
作者回复: 嗯嗯 主要是漏桶中的队列和MQ是思想上比较接近的东西
2022-04-271 
那时刻我想漏桶算法，可以通过一个计数器来计算目前in flight的数据包数量，如果来了数据包则加一，数据包处理完减一，如果计数器超过limit，则限流返回。作者回复: 嗯嗯 这个和计数器法是类似的 我现在认为不用queue可能不太容易保证输出速度恒定
2022-03-101
小智漏桶算法如何能实现目标限流一秒100qps？作者回复: 控制消费速率每秒100即可
2022-04-05
peter请教老师两个问题： Q1：云产品例子中： A 是哪个公司的产品？阿里？或者仅仅是个示例？ B 该产品是个消息队列吗？ C 5000连接 / 最高 10,000TPS，连接数和TPS有数量关系吗？ 此处好像是2倍关系。另外，连接数是指同时连接数吧。 Q2：漏桶消费线程怎么实现“稳定消费”？定时消费吗？ 令牌桶的放令牌线程，也是“稳定放入令牌”，也是定时放入令牌吗？作者回复: A1: 产品是我司的emqx cloud； https://www.emqx.com/zh/cloud 是一个 mqtt 的 broker 是指同时连接数 和 TPS 没有直接联系哦 A2: 漏桶可以通过定时消费实现 令牌桶也可以通过定时生产实现；不过一般我们会选择直接计算的方式进行
2022-03-10- Paul Shan漏桶算法也可以用一个计数器来维护当前的请求数目，新来一个请求，如果计数器到达上限就拒绝请求，如果没有到达上限，计数器自增后把请求交给具体的处理器，请求被处理完毕的时候计数器自减。
作者回复: 我理解这和漏桶算法还是有一些不一样哦 漏桶算法强调输出的速度稳定；计数器并不能保证这一点 我现在认为可能不用queue很难保证漏桶消费的速度恒定；欢迎指正。
2022-03-10 
Mike老师，我想说一个用计数器实现漏桶的思路，不知道可不可行？ 假设漏桶每秒处理1000个请求(1000rps) ，也就是1毫秒滴一滴，漏桶有个最大容量，计为capacity，如果新进来请求时发现漏桶已经满了，直接拒绝；如果新进来的请求是800号，也就是等待800ms就能执行（因为出水是匀速的，1ms出1滴，那排800，自然等待800ms就能执行了。伪代码如下 RateLimiter rateLimiter = new RateLimiter(1000); // 1000 permitted requests per seconds void submitTasks(Runnable task, Executor executor) { int sleepMs = rateLimiter.acquire(); if (sleepMs > 0) { Thread.sleep(sleepMs); executor.execute(task); } else { // acquire() 返回-1表示漏桶已满 throw new RequestNotPermittedException(); } } 请老师指教2022-05-13
收起评论
