限流算法之令牌桶

令牌桶

原理解析

一个桶，每秒向里面放置n个令牌，当请求来了之后，尝试排队拿取m个令牌，当令牌不足时，轮询等候。

实现代码

public class TestRateLimiter {
    public static final SimpleDateFormat sip = new SimpleDateFormat("YYYY-MM-dd HH:mm:ss:SS");

    public static final int THREAD_COUNT = 25;

    public static final int MAX_ACQUIRE = 1;

    @Test
    public void test(){
        RateLimiter rateLimiter = RateLimiter.create(5);
        Thread[] threads = new Thread[THREAD_COUNT];
        for (int i = 0; i < THREAD_COUNT; i++) {
            threads[i] = new Thread((Runnable) new RateLimiterThread(rateLimiter),"RateLimiterThread-"+i);
        }
        for (int i = 0; i < THREAD_COUNT; i++) {
            threads[i].start();
        }
        for (;;) ;
    }

    public class RateLimiterThread implements Runnable{

        private RateLimiter rateLimiter;

        public RateLimiterThread(RateLimiter rateLimiter) {
            this.rateLimiter = rateLimiter;
        }

        @Override
        public void run() {
            rateLimiter.acquire(MAX_ACQUIRE);
            System.out.println(Thread.currentThread().getName()+"获取到令牌，时间为："+ sip.format(new Date()));
        }
    }
}

RateLimiterThread-0获取到令牌，时间为：2021-07-19 14:46:38:487
RateLimiterThread-24获取到令牌，时间为：2021-07-19 14:46:38:684
RateLimiterThread-23获取到令牌，时间为：2021-07-19 14:46:38:884
RateLimiterThread-22获取到令牌，时间为：2021-07-19 14:46:39:84
RateLimiterThread-21获取到令牌，时间为：2021-07-19 14:46:39:284
RateLimiterThread-20获取到令牌，时间为：2021-07-19 14:46:39:484
RateLimiterThread-19获取到令牌，时间为：2021-07-19 14:46:39:684
RateLimiterThread-18获取到令牌，时间为：2021-07-19 14:46:39:884
RateLimiterThread-17获取到令牌，时间为：2021-07-19 14:46:40:84
RateLimiterThread-16获取到令牌，时间为：2021-07-19 14:46:40:284
RateLimiterThread-15获取到令牌，时间为：2021-07-19 14:46:40:484
RateLimiterThread-14获取到令牌，时间为：2021-07-19 14:46:40:685
RateLimiterThread-13获取到令牌，时间为：2021-07-19 14:46:40:884
RateLimiterThread-12获取到令牌，时间为：2021-07-19 14:46:41:84
RateLimiterThread-9获取到令牌，时间为：2021-07-19 14:46:41:285
RateLimiterThread-10获取到令牌，时间为：2021-07-19 14:46:41:484
RateLimiterThread-11获取到令牌，时间为：2021-07-19 14:46:41:684
RateLimiterThread-7获取到令牌，时间为：2021-07-19 14:46:41:884
RateLimiterThread-8获取到令牌，时间为：2021-07-19 14:46:42:84
RateLimiterThread-6获取到令牌，时间为：2021-07-19 14:46:42:284
RateLimiterThread-4获取到令牌，时间为：2021-07-19 14:46:42:484
RateLimiterThread-5获取到令牌，时间为：2021-07-19 14:46:42:685
RateLimiterThread-3获取到令牌，时间为：2021-07-19 14:46:42:884
RateLimiterThread-2获取到令牌，时间为：2021-07-19 14:46:43:84
RateLimiterThread-1获取到令牌，时间为：2021-07-19 14:46:43:284

每秒向桶中放置5个令牌，每个线程执行拿取一个令牌，所以一次有五个线程执行。

令牌桶预处理机制

将MAX_ACQUIRE修改为20，即一次x消费20个令牌

public class TestRateLimiter {
    public static final SimpleDateFormat sip = new SimpleDateFormat("YYYY-MM-dd HH:mm:ss:SS");

    public static final int THREAD_COUNT = 25;

    public static final int MAX_ACQUIRE = 10;

    @Test
    public void test(){
        RateLimiter rateLimiter = RateLimiter.create(5);
        Thread[] threads = new Thread[THREAD_COUNT];
        for (int i = 0; i < THREAD_COUNT; i++) {
            threads[i] = new Thread((Runnable) new RateLimiterThread(rateLimiter),"RateLimiterThread-"+i);
        }
        for (int i = 0; i < THREAD_COUNT; i++) {
            threads[i].start();
        }
        for (;;) ;
    }

    public class RateLimiterThread implements Runnable{

        private RateLimiter rateLimiter;

        public RateLimiterThread(RateLimiter rateLimiter) {
            this.rateLimiter = rateLimiter;
        }

        @Override
        public void run() {
            double acquire = rateLimiter.acquire(MAX_ACQUIRE);
            System.out.println(Thread.currentThread().getName()+"获取到令牌，时间为："+ sip.format(new Date())+",耗时为："+acquire);
        }
    }
}

RateLimiterThread-0获取到令牌，时间为：2021-07-19 14:54:00:952,耗时为：0.0
RateLimiterThread-24获取到令牌，时间为：2021-07-19 14:54:02:943,耗时为：1.989051
RateLimiterThread-23获取到令牌，时间为：2021-07-19 14:54:04:943,耗时为：3.989033
RateLimiterThread-22获取到令牌，时间为：2021-07-19 14:54:06:942,耗时为：5.989021
RateLimiterThread-21获取到令牌，时间为：2021-07-19 14:54:08:943,耗时为：7.989006
RateLimiterThread-20获取到令牌，时间为：2021-07-19 14:54:10:943,耗时为：9.988992
RateLimiterThread-19获取到令牌，时间为：2021-07-19 14:54:12:942,耗时为：11.98892
RateLimiterThread-17获取到令牌，时间为：2021-07-19 14:54:14:942,耗时为：13.9889
RateLimiterThread-18获取到令牌，时间为：2021-07-19 14:54:16:942,耗时为：15.988648
RateLimiterThread-16获取到令牌，时间为：2021-07-19 14:54:18:942,耗时为：17.988616
RateLimiterThread-15获取到令牌，时间为：2021-07-19 14:54:20:942,耗时为：19.988587
RateLimiterThread-14获取到令牌，时间为：2021-07-19 14:54:22:942,耗时为：21.988553
RateLimiterThread-13获取到令牌，时间为：2021-07-19 14:54:24:943,耗时为：23.988543
RateLimiterThread-12获取到令牌，时间为：2021-07-19 14:54:26:942,耗时为：25.988529
RateLimiterThread-11获取到令牌，时间为：2021-07-19 14:54:28:942,耗时为：27.988519
RateLimiterThread-10获取到令牌，时间为：2021-07-19 14:54:30:941,耗时为：29.988499
RateLimiterThread-9获取到令牌，时间为：2021-07-19 14:54:32:941,耗时为：31.988492
RateLimiterThread-8获取到令牌，时间为：2021-07-19 14:54:34:941,耗时为：33.988482
RateLimiterThread-7获取到令牌，时间为：2021-07-19 14:54:36:941,耗时为：35.988472
RateLimiterThread-6获取到令牌，时间为：2021-07-19 14:54:38:942,耗时为：37.988464
RateLimiterThread-5获取到令牌，时间为：2021-07-19 14:54:40:941,耗时为：39.988454
RateLimiterThread-4获取到令牌，时间为：2021-07-19 14:54:42:941,耗时为：41.988441
RateLimiterThread-3获取到令牌，时间为：2021-07-19 14:54:44:941,耗时为：43.98843
RateLimiterThread-2获取到令牌，时间为：2021-07-19 14:54:46:941,耗时为：45.988419
RateLimiterThread-1获取到令牌，时间为：2021-07-19 14:54:48:941,耗时为：47.988406

由此可见，第一次令牌桶中虽然没有足够的令牌，但可以“预支”给第一个线程，然后再进行补充，当补充完成后，再将令牌“预支”给第二个线程。因此，我们可以通过设置多个请求累加到上限后消费令牌桶的方式，来保证突发流量的服务可用性。