常见的限流算法原理和实现

　　前言
　　在高并发系统中，我们通常需要通过各种手段来提供系统的可以用性，例如缓存、降级和限流等，本文将针对应用中常用的限流算法进行详细的讲解。简介
　　限流简称流量限速（RateLimit）是指只允许指定的事件进入系统，超过的部分将被拒绝服务、排队或等待、降级等处理。常见的限流方案如下：
　　固定时间窗口
　　固定时间窗口是最常见的限流算法之一。其中窗口的概念，对应限流场景当中的限流时间单元。原理时间线划分为多个独立且固定大小窗口；落在每一个时间窗口内的请求就将计数器加1；如果计数器超过了限流阈值，则后续落在该窗口的请求都会被拒绝。但时间达到下一个时间窗口时，计数器会被重置为0。示例说明
　　说明：如上图场景是每秒钟限流10次，窗口的大小为1秒，每个方块代表一个请求，绿色的方块代表正常的请求，红色的方法代表被限流的请求，在每秒10次的场景中，从左往右当来看，当进入10个请求后，后面的请求都被会被限流。优缺点优点逻辑简单、维护成本比较低；缺点
　　窗口切换时无法保证限流值。相关实现
　　固定时间窗口的具体实现，可以采用Redis调用lua限流脚本来实现。限流脚本localkeyKEYS〔1〕localcounttonumber（ARGV〔1〕）localtimetonumber（ARGV〔2〕）localcurrentredis。call（get，key）ifcurrentandtonumber（current）countthenreturntonumber（current）endcurrentredis。call（incr，key）iftonumber（current）1thenredis。call（expire，key，time）endreturntonumber（current）复制代码具体实现publicLongratelimiter（Stringkey，inttime，intcount）throwsIOException｛ResourceresourcenewClassPathResource（ratelimiter。lua）；StringredisScriptIOUtils。toString（resource。getInputStream（），StandardCharsets。UTF8）；ListStringkeysCollections。singletonList（key）；ListStringargsnewArrayList（）；args。add（Integer。toString（count））；args。add（Integer。toString（time））；longresultredisTemplate。execute（newRedisCallbackLong（）｛OverridepublicLongdoInRedis（RedisConnectionconnection）throwsDataAccessException｛ObjectnativeConnectionconnection。getNativeConnection（）；if（nativeConnectioninstanceofJedis）｛return（Long）（（Jedis）nativeConnection）。eval（redisScript，keys，args）；｝return1l；｝｝）；｝复制代码测试RequestMapping（valueRateLimiter，methodRequestMethod。GET）publicStringRateLimiter（）throwsIOException｛inttime3；intcount1；Stringkeyredis：LongnumberredisLockUtil。ratelimiter（key，time，count）；logger。info（count：｛｝，number）；MapString，ObjectmapnewHashMap（）；if（numbernullnumber。intValue（）count）｛map。put（code，1）；map。put（msg，访问过于频繁，请稍候再试）；｝else｛map。put（code，200）；map。put（msg，访问成功）；｝returnJSON。toJSONString（map）；｝复制代码
　　说明：测试为3秒钟访问1次，超过了次数会提示错误。滑动时间窗口
　　滑动时间窗口算法是对固定时间窗口算法的一种改进，在滑动窗口的算法中，同样需要针对当前的请求来动态查询窗口。但窗口中的每一个元素，都是子窗口。子窗口的概念类似于方案一中的固定窗口，子窗口的大小是可以动态调整的。实现原理将单位时间划分为多个区间，一般都是均分为多个小的时间段；每一个区间内都有一个计数器，有一个请求落在该区间内，则该区间内的计数器就会加一；每过一个时间段，时间窗口就会往右滑动一格，抛弃最老的一个区间，并纳入新的一个区间；计算整个时间窗口内的请求总数时会累加所有的时间片段内的计数器，计数总和超过了限制数量，则本窗口内所有的请求都被丢弃。示例说明
　　说明：比如上图中的场景是每分钟限流100次。每一个子窗口的时间维度设置为1秒，那么一分钟的窗口有60个子窗口。这样每当一个请求来了之后，我们去动态计算这个窗口的时候，我们最多需找60次。时间复杂度，从线性变成常量级了，时间的复杂度相对来说也会更低了。具体实现
　　关于滑动时间窗的实现，可以采用sentinel，关于sentinel的使用后续将详细进行讲解。漏桶算法
　　漏桶算法是水先进入到漏桶里，漏桶再以一定的速率出水，当流入水的数量大于流出水时，多余的水直接溢出。把水换成请求来看，漏桶相当于服务器队列，但请求量大于限流阈值时，多出来的请求就会被拒绝服务。漏桶算法使用队列实现，可以以固定的速率控制流量的访问速度，可以做到流量的平整化处理。原理
　　说明：将每个请求放入固定大小的队列进行中队列以固定速率向外流出请求，如果队列为空则停止流出。如队列满了则多余的请求会被直接拒绝具体实现longtimeStampSystem。currentTimeMillis（）；当前时间longcapacity1000；桶的容量longrate1；水漏出的速度longwater100；当前水量publicbooleanleakyBucket（）｛先执行漏水，因为rate是固定的，所以可以认为时间间隔rate即为漏出的水量longnowSystem。currentTimeMillis（）；waterMath。max（0，water（nowtimeStamp）rate）；timeS水还未满，加水if（watercapacity）｛waterwater100；｝水满，拒绝加水else｛｝｝RequestMapping（valueleakyBucketLimit，methodRequestMethod。GET）publicvoidleakyBucketLimit（）｛for（inti0；i20；i）｛fixedThreadPool。execute（newRunnable（）｛Overridepublicvoidrun（）｛if（leakyBucket（））｛logger。info（threadname：Thread。currentThread（）。getName（）sdf。format（newDate（）））；｝else｛logger。error（请求频繁）；｝｝｝）；｝｝复制代码令牌桶算法
　　令牌桶算法是基于漏桶之上的一种改进版本，在令牌桶中，令牌代表当前系统允许的请求上限，令牌会匀速被放入桶中。当桶满了之后，新的令牌就会被丢弃原理
　　令牌以固定速率生成并放入到令牌桶中；如果令牌桶满了则多余的令牌会直接丢弃，当请求到达时，会尝试从令牌桶中取令牌，取到了令牌的请求可以执行；如果桶空了，则拒绝该请求。具体实现RequestMapping（valueratelimit，methodRequestMethod。GET）publicvoidratelimit（）｛每1s产生0。5个令牌，也就是说接口2s只允许调用1次RateLimiterrateLimiterRateLimiter。create（0。5，1，TimeUnit。SECONDS）；for（inti0；i10；i）｛fixedThreadPool。execute（newRunnable（）｛Overridepublicvoidrun（）｛获取令牌最大等待10秒if（rateLimiter。tryAcquire（1，10，TimeUnit。SECONDS））｛logger。info（threadname：Thread。currentThread（）。getName（）sdf。format（newDate（）））；｝else｛logger。error（请求频繁）；｝｝｝）；｝｝复制代码
　　执行结果：〔pool1thread3〕ERROR请求频繁〔pool1thread2〕ERROR请求频繁〔pool1thread1〕INFOthreadname：pool1thread12022080715：44：00〔pool1thread8〕ERROR〔〕请求频繁〔pool1thread9〕ERROR〔〕请求频繁〔pool1thread10〕ERROR〔〕请求频繁〔pool1thread7〕INFO〔〕threadname：pool1thread72022080715：44：03〔pool1thread6〕INFO〔〕threadname：pool1thread62022080715：44：05〔pool1thread5〕INFO〔〕threadname：pool1thread52022080715：44：07〔pool1thread4〕INFO〔〕threadname：pool1thread42022080715：44：09复制代码
　　说明：接口限制为每2秒请求一次，10个线程需要20s才能处理完，但是rateLimiter。tryAcquire限制了10s内没有获取到令牌就抛出异常，所以结果中会有5个是请求频繁的。小结固定窗口：实现简单，适用于流量相对均匀分布，对限流准确度要求不严格的场景。滑动窗口：适用于对准确性和性能有一定的要求场景，可以调整子窗口数量来权衡性能和准确度漏桶：适用于流量绝对平滑的场景令牌桶：适用于流量整体平滑的情况下，同时也可以满足一定的突发流程场景总结
　　本文针对了几种限流的算法的原理和实现进行详细讲解，如有疑问，请随时反馈。
　　作者：剑圣无痕
　　链接：https：juejin。cnpost7129067013015601188