令牌桶算法、漏桶算法

1、前言

网上很多人说漏桶、令牌桶算法，其实乍一看好像都差不多，但是漏桶因为通过的速率恒定，应对不了突发流量，所以一般都用令牌桶。所谓的速率恒定可以看下面这个例子：
假设漏桶容量为10，每次下漏速度为1，令牌桶的容量也是10。如果同一时间来了100个请求，那么针对漏桶来说，它只能接受10个请求，剩余90个丢弃，令牌桶也只能接受10个请求，拒绝90个。但是后续流程中，漏桶的漏下的速率只能是1，但是令牌桶在同一时间能发出10个令牌，通过10个请求，所以令牌桶能接受短暂的尖刺流量。

2、漏桶算法和令牌桶算法

漏桶的示意图如下：

漏桶算法
漏桶算法：

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;

/**
 * @author xushu
 * @create 12/26/20 8:46 PM
 * @desc
 */
public class LeakyBucketLimiter {

    private Logger logger = LoggerFactory.getLogger(LeakyBucketLimiter.class);

    private ScheduledExecutorService service = Executors.newScheduledThreadPool(5);

    // 桶容量
    private int capicaty = 10;

    // 当前流出水量
    private int water = 0;

    // 桶流水速率  rate/s
    private int rate = 4;

    // 上次放水入桶时间
    private long lastTime = System.currentTimeMillis();


    public void accquire(){
        service.scheduleAtFixedRate(() -> {
            // 记录当前时间
            long now = System.currentTimeMillis();

            // 计算流出水量
            water = Math.max(0, water - (int)(now - lastTime) / 1000 * rate);

            // 模拟当前请求 1 ~ 8
            int request = (int)(Math.random() * 8) + 1;

            logger.info("当前请求：" + request + "，桶剩余容量：" + (capicaty - water));

            lastTime = now;

            if(capicaty - water < request){
                int permits = capicaty - water;
                water += permits;
                logger.info("限流了，只允许" + permits + "个请求，其余" + (request - permits) + "个丢弃，桶剩余容量为" + (capicaty - water));
            }else {
                water += request;
                logger.info("允许了" + request + "个请求，桶剩余容量为" + (capicaty - water));
            }

        }, 3, 1, TimeUnit.SECONDS);
    }


    public static void main(String[] args) {
        LeakyBucketLimiter leakyBucketLimiter = new LeakyBucketLimiter();
        leakyBucketLimiter.accquire();
    }
}

令牌桶示意图如下：

令牌桶
令牌桶算法：

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;

/**
 * @author xushu
 * @create 12/26/20 9:28 PM
 * @desc
 */
public class TokensLimiter {

    private Logger logger = LoggerFactory.getLogger(TokensLimiter.class);

    private ScheduledExecutorService service = Executors.newScheduledThreadPool(5);

    // 令牌桶的容量
    private int capicaty = 10;

    // 令牌生成速率  /s
    private int rate = 4;

    // 上次令牌生成时间
    private long lastTime = System.currentTimeMillis();

    // 当前生成令牌数
    private int currentTokens;

    public void accquire(){
        service.scheduleAtFixedRate(() -> {
            long now = System.currentTimeMillis();

            // 当前令牌生成数量
            currentTokens = Math.min(capicaty, currentTokens + (int)(now - lastTime) / 1000 * rate);

            // 当前请求数量 1 ~ 8
            int request = (int)(Math.random() * 8) + 1;

            logger.info("请求令牌数：" + request + "，当前令牌数：" + currentTokens);

            lastTime = now;

            if(currentTokens < request){
                int permits = currentTokens;
                currentTokens = 0;
                logger.info("限流了，只允许拿" + permits +  "个令牌，其余" + (request - permits)  + "个请求被拒绝");
            }else {
                currentTokens -= request;
                logger.info("剩余令牌数：" + currentTokens);
            }
        }, 3, 1, TimeUnit.SECONDS);
    }


    public static void main(String[] args) {
        TokensLimiter tokensLimiter = new TokensLimiter();
        tokensLimiter.accquire();
    }

}

一般工程上还是使用 Guava 的 RateLimiter 来使用令牌桶算法，他的使用也比较简单：

import com.google.common.util.concurrent.RateLimiter;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @author xushu
 * @create 12/26/20 9:57 PM
 * @desc
 */
public class RateLimiterTest {

    private static Logger logger = LoggerFactory.getLogger(RateLimiterTest.class);

    public static void main(String[] args) {
        // 每秒3个
        RateLimiter limiter = RateLimiter.create(2);

        // 此 for 循环一般计算机允许的很快，但是因为 RateLimiter 的限制，所以每秒只能打印2个
        for(int i = 0; i < 1000; i++){
            limiter.acquire();
            logger.info("用户" + i + "获取到了");
        }
    }
}

3、总结

漏桶跟令牌桶区别在于，漏桶能够强行限制数据的传输速率，而令牌桶能够在限制数据的传输速率的基础上，还允许突发流量，相对而言适用范围广一些。