美文网首页
高手在民间!看菜市场大爷玩转令牌桶算法

高手在民间!看菜市场大爷玩转令牌桶算法

作者: 码神手记 | 来源:发表于2020-05-31 18:10 被阅读0次

    码神手记——资深攻城狮的私房笔记。微信公众平台/知乎/头条/简书同步发文。感谢关注与转发。

    故事是这样的

    码农小刘去菜市场买菜。刚到门口,一个大爷就盯上了他,从兜里掏出了一支......体温枪,“36.2,进去吧”。小刘刚要抬腿进去,身后又传来大爷的声音:“等会~,带上限流牌!”。


    大爷的限流牌回收箱

    大爷是谁,限流牌是什么?

    大爷今年35,去年转行来到菜市场做保安。头发花白,发量略少,但精神很好(可能是个老码农了)。疫情期间,大爷祭出了曾经用过的令牌桶(Token Bucket)算法,准备为疫情期间的人群限流做贡献。

    画外音:令牌桶算法是网络流量整形(Traffic Shaping)速率限制(Rate Limiting)中最常使用的一种算法。典型情况下,令牌桶算法用来控制发送到网络上的数据的数目,并允许突发数据的发送。——来自百度百科

    限流牌如何控制菜市场人流量?

    对当时菜市场门口的信息做以下梳理:

    • 篮子里的限流牌数量有限,总共50个。
    • 每进去一个顾客,就随身带进去1个。
    • 当篮子里没有限流牌时,新来的顾客只能等着,直到篮子里有限流牌,或者放弃。
    • 每出来一个顾客,就必须把自己的限流牌放回箱子中(省略消毒过程)。

    当100个大爷大妈在早上九点同时来到菜市场时,只有50个眼疾手快的能拿到限流牌先进去,剩下的就得等,出来一个进去一个。

    这是有放回的令牌桶策略,令牌桶算法最简单的一种应用。菜市场就好比系统资源,买菜的大爷大妈们就是一个个想要访问系统资源的请求,50个限流牌的总量就是系统同时能支撑的并发请求数。

    相信你已经了解了令牌桶的作用,以及在菜市场限流场景下的简单应用。接下来用一张图说明下令牌桶算法在互联网系统中的应用逻辑,并结合实际场景进行分析。


    令牌桶算法

    应用场景:系统防护之限流

    高并发系统防护三板斧:缓存、限流、降级,在这里主要说限流。在《真实案例-高并发系统的缓存设计思路》中介绍过缓存方面的实战经验,以后有时间可以再讲讲降级。

    限流是保护系统可用性的一种手段。服务集群能承受的qps是有一个阈值的,流量突增时,一旦超过了集群能够承受的范围,就会发生响应超时,甚至服务宕机的后果,严重影响用户体验。如果给收入带来了极大损失,或许就有程序员要被“祭天”了。

    比如:
    系统A有一个获取商品信息的接口,长期以来高峰qps是10000次/s,目前部署的服务器资源可以支持最多12000次/s。双十一前,运维部门提前对集群进行了扩容,预计支撑50000次/s,准备应对超高峰的到来。
    万万没想到,双十一0点后,访问人数比预计要多很多,qps达到了惊人的80000次/s,此时有服务器撑不住了,cpu、内存资源告急。开始陆续有用户打不开页面,疯狂刷新,导致更多的用户请求涌入不堪重负的服务集群。终于,服务彻底无法访问了。

    如果网关做了限流,qps超过50000时就随机抛弃部分请求,那绝大多数的用户还是可以愉快玩耍的。此时,大可以不慌不忙地增加机器,然后再把限流阈值调高。

    关于限流的一些优秀轮子

    Nginx接入层:自带模块ngx_http_limit_req_module,漏桶算法实现的。漏桶算法与令牌桶算法看起来很相似,实则拥有完全不同的特性,不支持突发流量。

    应用层:google有一个神奇的包:Guava,其中有一个RateLimiter类,可以使用它来实现限流的功能,API也很简单。

    感兴趣可以去网上查一查,资料非常多。

    小结

    今天的内容并不复杂,纯粹因为小刘去了趟菜市场,遇见了玩令牌桶的大爷后有感而发。为什么没有贴一堆代码来讲解?因为百度上到处都是。分享下个人在学习这件事上的方法论:在计算机科学/操作系统等方面的学习应深度优先,最佳实践/领域解决方案上以广度优先

    码神手记,资深攻城狮的私房笔记。微信公众平台/知乎/头条/简书同步发文。感谢关注与转发。

    相关文章

      网友评论

          本文标题:高手在民间!看菜市场大爷玩转令牌桶算法

          本文链接:https://www.haomeiwen.com/subject/ucsrzhtx.html