面试要求：4种经典限流算法详解

最近我们的业务系统引入了Guava的RateLimiter限流组件，它是基于令牌桶算法实现的，令牌桶是一个非常经典的限流算法。本文将和大家一起学习几种经典的限流算法。什么是限流？维基百科的概念是这样的：在计算机网络中，速率限制用于控制网络接口控制器发送或接收请求的速率。可用于防止DoS攻击和限制网络抓取简单翻译：在计算机网络中，节流是控制网络接口发送或接收请求的速率，从而防止DoS攻击和限制网络爬虫。限流，也称为流量控制。意思是当系统面临高并发或大流量请求时，限制新的请求进入系统，以保证系统的稳定性。限流会导致部分用户请求处理不及时或被拒绝，影响用户体验。因此，一般需要平衡系统稳定性和用户体验。举个生活中的例子：★一些热门的旅游景点一般都有每日游客人数限制。每天只售出固定数量的门票，比如5,000张。如果5月1日和国庆假期去的晚了，当天的票可能已经售罄，无法进去游玩。即使进去，排队也能让你怀疑人生。》普通限流算法Fixedwindow限流算法首先维护一个计数器，把单位时间段看成一个窗口，计数器记录这个窗口接收请求的次数。当次数小于限流阈值时，允许访问，计数器+1，当次数大于限流阈值时，拒绝访问，当前时间窗口过去后，清零计数器，假设单位时间为1秒，则限流阈值为3，在单位时间的1秒内，每有一个请求过来，计数器就加1，如果计数器累计的次数超过限流阈值3，则拒绝所有后续请求。1s后为结束，计数器清零，重新开始计数。如下图所示：伪代码如下：/***固定窗口时间算法*@return*/booleanfixedWindowsTryAcquire(){longcurrentTime=System.currentTimeMillis();//获取系统当前时间if(currentTime-lastRequestTime>windowUnit){//检查是否在时间窗口内counter=0;//计数器清0lastRequestTime=currentTime;//开启一个新的时间窗口}if(countercounters=newTreeMap<>();/***滑动窗口时间算法实现*/booleanslidingWindowsTryAcquire(){longcurrentWindowTime=LocalDateTime.now().toEpochSecond(ZoneOffset.UTC)/SUB_CYCLE*SUB_CYCLE;//获取哪个小循环windowthecurrenttimeisintcurrentWindowNum=countCurrentWindow(currentWindowTime);//当前窗口的请求总数//超过阈值限流if(currentWindowNum>=thresholdPerMin){returnfalse;}//Counter+1counters.get(currentWindowTime)++;returntrue;}/***统计当前wi的请求数ndow*/privateintcountCurrentWindow(longcurrentWindowTime){//计算窗口起始位置longstartTime=currentWindowTime-SUB_CYCLE*(60s/SUB_CYCLE-1);intcount=0;//遍历存储的计数器Iterator>迭代器=计数器.entrySet().iterator();while(iterator.hasNext()){Map.Entryentry=iterator.next();//删除无效的过期子窗口计数器if(entry.getKey()0){currentToken--;//TokenQuantity-1returntrue;}returnfalse;}如果token发行策略正确，系统不会被拖累，机器的利用率也可以提高。Guava的RateLimiter限流组件是基于令牌桶算法实现的。本文转载自微信公众号“捡蜗牛的小男孩”，可通过以下二维码关注。转载请联系捡蜗牛的小男孩公众号。