Java 实现令牌桶限流算法 原生极简实现 包括单机和多线程版本

令牌桶算法简介

令牌桶是指一个限流容器，容器有最大容量，每秒或每100ms产生一个令牌（具体取决于机器每秒处理的请求数），当容量中令牌数量达到最大容量时，令牌数量也不会改变了，只有当有请求过来时，使得令牌数量减少（只有获取到令牌的请求才会执行业务逻辑），才会不断生成令牌，所以令牌桶算法是一种弹性的限流算法

限流完下一步我们可以做什么呢，限流完后所有请求都是获取令牌的，都是我们要执行的，但是如果还有很多请求，这时我们要有一个方式决定怎样执行这些请求，这个方式称为调度，可以看我这篇文章 调度算法

令牌桶算法限流范围：

假设令牌桶最大容量为n，每秒产生r个令牌

1. 平均速率：则随着时间推延，处理请求的平均速率越来越趋近于每秒处理r个请求，说明令牌桶算法可以控制平均速率
2. 瞬时速率：如果在一瞬间有很多请求进来，此时来不及产生令牌，则在一瞬间最多只有n个请求能获取到令牌执行业务逻辑，所以令牌桶算法也可以控制瞬时速率

在这里提下漏桶，漏桶由于出水量固定，所以无法应对突然的流量爆发访问，也就是没有保证瞬时速率的功能，但是可以保证平均速率

单机版实现

1. capacity为当前令牌桶的中令牌数量，timeStamp为上一次请求获取令牌的时间，我们没必要真的实现计时器每秒产生多少令牌放入容器中，只要记住上一次请求到来的时间，和这次请求的差值就知道在这段时间内产生了多少令牌
2. 下面假设100ms产生1个令牌，且令牌桶最大容量为10
3. Thread.sleep是模拟不同请求到来的间隔，改变间隔可以看到不同现象

public class LeakyBucketAlgorithm {
    private int capacity = 10;
    private long timeStamp = System.currentTimeMillis();

    public boolean getToken() {
        if (capacity > 0) {
            capacity--;
            return true;
        }
        long current = System.currentTimeMillis();
        if (current - timeStamp >= 100) {
            if ((current - timeStamp) / 100 >= 2) {
            	// 假设100ms产生一个令牌
                capacity += (int)((current - timeStamp) / 100) - 1;
            }
            timeStamp = current;
            if (capacity > 10) capacity = 10;
            return true;
        }
        return false;
    }

    public static void main(String[] args) throws InterruptedException {
        LeakyBucketAlgorithm leakyBucketAlgorithm = new LeakyBucketAlgorithm();
        while (true) {
//            Thread.sleep(10);
            Thread.sleep(100);
            if (leakyBucketAlgorithm.getToken()) {
                System.out.println("获取令牌成功，可以执行业务逻辑了");
            } else {
                System.out.println("获取令牌失败，请稍后重试");
            }
        }
    }
}

多线程版实现

1. 多线程实现也非常简单，只要在方法加一个同步锁，保证同时只有一个请求能尝试获取令牌就可以了
2. Thread.sleep(1000)是因为有10个线程在抢令牌，而每100ms才产生一个令牌，所以每隔1秒抢一次，可以改变这个值看现象

public class LeakyBucketAlgoritmThread {
    private int capacity = 10;
    private long timeStamp = System.currentTimeMillis();


    public synchronized boolean getToken() {
        if (capacity > 0) {
            capacity--;
            return true;
        }
        long current = System.currentTimeMillis();
        if (current - timeStamp >= 100) {
            if ((current - timeStamp) / 100 >= 2) {
                capacity += (int)((current - timeStamp) / 100) - 1;
            }
            timeStamp = current;
            if (capacity > 10) capacity = 10;
            return true;
        }
        return false;
    }

    public static void main(String[] args) throws InterruptedException {
        LeakyBucketAlgoritmThread leakyBucketAlgorithmThread = new LeakyBucketAlgoritmThread();
        for (int i = 0; i < 10; i++) {
            new Thread(new Runnable() {
                @Override
                public void run() {
                    while (true) {
                        try {
//                            Thread.sleep(900);
                            Thread.sleep(1000);
                            if (leakyBucketAlgorithmThread.getToken()) {
                                System.out.println(Thread.currentThread().getName()+" 获取令牌成功，可以执行业务逻辑了");
                            } else {
                                System.out.println(Thread.currentThread().getName()+" 获取令牌失败，请稍后重试");
                            }
                        } catch (Exception e) {
                            e.printStackTrace();
                        }
                    }
                }
            }).start();
        }
    }
}