接口限流算法令牌桶、滴桶算法

接口限流算法令牌桶、滴桶算法

接口限流算法的概括

在接口限流算法的介绍当中，主要存在四种算法;
1、固定窗口算法
2、滑动窗口算法
3、滴桶算法
4、令牌桶算法
这里要对滴桶算法、令牌桶算法 做叙述和算法的代码实现。

滴桶算法

大致的漏桶限流规则如下：

（1）进水口（对应客户端请求）以任意速率流入进入漏桶。

（2）漏桶的容量是固定的，出水（放行）速率也是固定的。

（3）漏桶容量是不变的，如果处理速度太慢，桶内水量会超出了桶的容量，则后面流入的水滴会溢出，表示请求拒绝

滴桶算法，首先需要有一个容器，然后有水滴不断的从容器上方的口，做填充，与此同时，容器底部有漏口，漏口处均匀的滴出水滴。其中当容器当中的水，已经盛满的状态下，水滴会溢出。

特点：填充容器的水滴，其滴入的速度是不受限制的，而漏口处的水滴是均匀流出的。
这里的水滴 就是不断涌来的请求，当容器当中的请求已经达到阈值，则会对接下来的请求做拒绝策略。水滴的滴出 就是请求不断被处理的过程。

削峰： 有大量流量进入时,会发生溢出,从而限流保护服务可用

缓冲： 不至于直接请求到服务器, 缓冲压力

@RestController
public class DemoTestController {public static final String SUCCESS = "SUCCESS";public static Map<String, Integer> MAP = null;/*** bucket size */public static final int BUCKET_SIZE = 1000;/*** minus size */public static final int MINUS_SIZE = 10;/*** current size identity */public static final String CURRENT_SIZE_IDENTITY = "CURRENT_SIZE_IDENTITY";@PostConstructpublic void init() {//init containerMAP = new ConcurrentHashMap<>(1);MAP.put(CURRENT_SIZE_IDENTITY, 0);}/*** execute once every 1 seconds* if it has executed ,current bucket size - MINUS_SIZE*/@Scheduled(cron = "0/1 * * * * ?")public void minus() {//get current bucket sizeInteger currentBucketSize = (CURRENT_SIZE_IDENTITY);if (currentBucketSize >= MINUS_SIZE) {MAP.put(CURRENT_SIZE_IDENTITY, currentBucketSize - MINUS_SIZE);}System.out.println(currentBucketSize);}@RequestMapping("/demoTest")public String demoTest() {//get current bucket sizeInteger currentBucketSize = (CURRENT_SIZE_IDENTITY);if (currentBucketSize > BUCKET_SIZE - 1) {System.out.println("sorry,request too fast!");}else{MAP.put(CURRENT_SIZE_IDENTITY, currentBucketSize + 1);}return SUCCESS;}
}

上面的代码，就是滴桶算法的体现，
其中请求接口，就是水滴滴入容器的过程，要保证请求的加入，不会让桶溢出。
其中定时的方法啊，就是模拟了一个请求被处理完成，这时候就会被移出水桶，上图是假设业务处理时间为 1秒。

二、令牌桶算法

令牌桶限流大致的规则如下：

（1）进水口按照某个速度，向桶中放入令牌。

（2）令牌的容量是固定的，但是放行的速度不是固定的，只要桶中还有剩余令牌，一旦请求过来就能申请成功，然后放行。

（3）如果令牌的发放速度，慢于请求到来速度，桶内就无牌可领，请求就会被拒绝。
总之，令牌的发送速率可以设置，从而可以对突发的出口流量进行有效的应对。

令牌桶算法中新请求到来时会从桶里拿走一个令牌，如果桶内没有令牌可拿，就拒绝服务。 当然，令牌的数量也是有上限的。令牌的数量与时间和发放速率强相关，时间流逝的时间越长，会不断往桶里加入越多的令牌，如果令牌发放的速度比申请速度快，令牌桶会放满令牌，直到令牌占满整个令牌桶。

特点：相比较滴桶算法，令牌桶算法会允许某个时间进入较多的请求，并加以处理，因为滴桶算法，滴出水滴的速度是恒定的，但是令牌桶，如果聚集了很多的令牌，此时就允许很多请求同时涌入。

@RestController
public class DemoTestController {public static final String SUCCESS = "SUCCESS";public static Map<String, Integer> MAP = null;/*** bucket size */public static final int BUCKET_SIZE = 10000;/*** add size */public static final int ADD_SIZE = 100;/*** current size identity */public static final String CURRENT_SIZE_IDENTITY = "CURRENT_SIZE_IDENTITY";@PostConstructpublic void init() {//init containerMAP = new ConcurrentHashMap<>(1);MAP.put(CURRENT_SIZE_IDENTITY, 1000);}/*** execute once every 1 seconds* if it has executed ,current bucket size - MINUS_SIZE*/@Scheduled(cron = "0/1 * * * * ?")public void minus() {//get current bucket sizeInteger currentBucketSize = (CURRENT_SIZE_IDENTITY);if (currentBucketSize <= BUCKET_SIZE - ADD_SIZE) {MAP.put(CURRENT_SIZE_IDENTITY, currentBucketSize + ADD_SIZE);}System.out.println(currentBucketSize);}@RequestMapping("/demoTest")public String demoTest() {//get current bucket sizeInteger currentBucketSize = (CURRENT_SIZE_IDENTITY);if (currentBucketSize == 0) {System.out.println("sorry,request too fast!");} else {MAP.put(CURRENT_SIZE_IDENTITY, currentBucketSize - 1);}return SUCCESS;}
}

总结

1、漏桶算法：水（请求）先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大会直接溢出（拒绝服务），可以看出漏桶算法能强行限制数据的传输速率

流入：以任意速率往桶中放入水滴。
流出：以固定速率从桶中流出水滴。
缺点：因为当流出速度固定，大规模持续突发量，无法多余处理，浪费网络带宽
优点：无法击垮服务

2、令牌桶算法：一个存放固定容量令牌的桶，按照固定速率（每秒/或者可以自定义时间）往桶里添加令牌，然后每次获取一个令牌，当桶里没有令牌可取时，则拒绝服务
令牌桶分为2个动作，动作1(固定速率往桶中存入令牌)、动作2(客户端如果想访问请求，先从桶中获取token)

流入：以固定速率从桶中流入水滴
流出：按照任意速率从桶中流出水滴

技术上使用Google开源工具包Guava提供了限流工具类RateLimiter，该类基于令牌桶算法来完成限流，非常易于使用
优点：支持大的并发，有效利用网络带宽