限流算法之漏桶算法和令牌桶算法

柔情只为你懂 2023-06-03 04:57 18阅读 0赞

漏桶算法与令牌算法相比，**令牌桶算法的业务峰值有一定的处理能力，但漏桶法几乎没有**。  
![Snipaste\_2019-10-05\_21-06-03.jpg][Snipaste_2019-10-05_21-06-03.jpg]  
**漏桶算法**：水(请求)先进入到漏桶里,漏桶以一定的速度出水(接口有响应速率),当水流入速度过大会直接溢出(访问频率超过接口响应速率),然后就拒绝请求,可以看出漏桶算法能强行限制数据的传输速率.

把请求放在一个队列中，以一定的频率去处理队列中的请求，避免瞬间来的大流量把服务冲垮  
![Snipaste\_2019-10-05\_21-05-27.jpg][Snipaste_2019-10-05_21-05-27.jpg]  
**令牌桶算法**：随着时间流逝,系统会按恒定1/QPS时间间隔(如果QPS=100,则间隔是10ms)往桶里加入Token(想象和漏洞漏水相反,有个水龙头在不断的加水),如果桶已经满了就不再加了.新请求来临时,会各自拿走一个Token,如果没有Token可拿了就阻塞或者拒绝服务.

令牌桶的另外一个好处是可以方便的改变速度. 一旦需要提高速率,则按需提高放入桶中的令牌的速率. 一般会定时(比如100毫秒)往桶中增加一定数量的令牌, 有些变种算法则实时的计算应该增加的令牌的数量.

> **注意：令牌桶对系统有一定容忍度，当瞬间有跟多个请求时依然可以处理**

**令牌桶实现**

/** * @author minghai * @description 令牌桶对业务有一定的容忍度 * @date 2020/4/27 */
    public class TokenBucket { 
    
        private int bucketNums = 100; // 桶的容量
        private int rate = 1;         // 流入速度
        private int nowTokens;        // 当前令牌桶数量
        private long timesamp = getNowTime();         // 时间
    
        private long getNowTime(){ 
            return System.currentTimeMillis();
        }
    
        public boolean getToken(){ 
            // 记录来拿令牌的时间
            long nowTime = getNowTime();
    
            // 添加令牌【判断该有多少个令牌】
            nowTokens = nowTokens + (int)((nowTime - timesamp) * rate);
    
            // 添加后的令牌数量与桶的容量那个小
            nowTokens = nowTokens <bucketNums ? nowTokens : bucketNums;
            // 修改拿令牌的时间
            timesamp = getNowTime();
            // 判断令牌是否足够
            if(nowTokens < 1){ 
               return false;
            }else{ 
                nowTokens -= 1;
                return true;
            }
        }

[Snipaste_2019-10-05_21-06-03.jpg]: /images/20230601/f27d1041b2ef48bea83b4de8ac547747.png
[Snipaste_2019-10-05_21-05-27.jpg]: /images/20230601/a0e72767e467401c86998ddb7269fc7b.png