限流算法

漏桶算法

漏桶算法很简单，如下图所示，水直接进入漏桶，漏桶按一定的速度出水，当水进入速度过大会直接溢出，由此可以看出漏桶算法的优势在于能够限制数据的传输速率。

漏桶的出水速度是固定的参数，所以无论并发的请求数是多少，释放出来的速度恒定，无法为某一个单独的流改变端口速率。

因此其显而易见的缺点就是不能有效利用网络资源，无法承担突发的流量请求，效率偏低。

令牌桶算法

令牌桶的原理也好理解，其实就是系统以一个恒定的速度往桶中放置令牌，当请求进来时，先从桶里拿令牌，成功拿到令牌就通过，当没有令牌时直接被拒绝。

这些被拒绝的请求，也可以将其存放到队列中，等待桶中生成了足够数量的令牌中再次进行传输。

可以看出令牌桶与漏桶的区别就在于此，漏桶算法是强制数据的传输速率，而令牌桶不仅能够限制传输速率，同时也可以根据令牌的生成速率，承受突发请求直到令牌生成速率上限。

限流工具

RateLimiter

大名鼎鼎的Guava工具包提供了限流工具类RateLimiter，该类基于令牌桶算法实现限流，广泛适用于单机程序的限流处理。

提供一些简单的示例：

package com.easyboot.framework.limit;

import cn.hutool.core.thread.ThreadUtil;
import cn.hutool.json.JSONUtil;
import com.google.common.util.concurrent.RateLimiter;
import io.rong.models.User;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

/**
 * Guava令牌桶限流
 *
 * @author wujiawei0926@yeah.net
 * @see
 * @since 2020/4/16
 */
@Slf4j
public class GuavaRateLimiter {

    @Test
    public void useLimit() {

        // 创建令牌桶：每秒只能2次请求
        RateLimiter limiter = RateLimiter.create(1.0);

        // 模拟多个请求
        for (int i = 0; i < 20; i++) {
            double acquire = limiter.acquire();
            log.info("获取令牌成功，消耗=" + acquire);

            List<User> list = new ArrayList<>();
            for (int j = 0; j < 3; j++) {
                User user = new User(j + "", "12", "测试" + j);
                list.add(user);
            }

            log.info("远程返回：" + JSONUtil.toJsonStr(list));
        }

        log.info("结束");
    }

    @Test
    public void useLimitWithThread(){
        RateLimiter limiter = RateLimiter.create(2.0);

        ExecutorService service = Executors.newFixedThreadPool(4);
        for (int i = 0; i < 20; i++) {
            service.submit(()->{
                double acquire = limiter.acquire(1);
                log.info("获取令牌成功，消耗=" + acquire);
                System.out.println("token ");

                ThreadUtil.sleep(100);

                log.info("执行成功");
            });

        }
    }

    @Test
    public void common() {
        for (int i = 0; i < 20; i++) {
            log.info("开始远程");
            List<User> list = new ArrayList<>();
            for (int j = 0; j < 3; j++) {
                User user = new User(j + "", "12", "测试" + j);
                list.add(user);
            }

            log.info("远程返回：" + JSONUtil.toJsonStr(list));
        }

        log.info("结束");
    }

}

Redis

如果是分布式的应用，需要利用Redis来进行限流，虽然Redis没有提供现成的实现方法，但我们可以通过Lua脚本实现限流功能。

private String buildLuaScript() {
    StringBuilder lua = new StringBuilder();
    lua.append( " local key = KEYS[1]" );
    lua.append( "\nlocal limit = tonumber(ARGV[1])" );
    lua.append( "\nlocal curentLimit = tonumber(redis.call('get', key) or \"0\")" );
    lua.append( "\nif curentLimit + 1 > limit then" );
    lua.append( "\nreturn 0" );
    lua.append( "\nelse" );
    lua.append( "\n redis.call(\"INCRBY\", key, 1)" );
    lua.append( "\nredis.call(\"EXPIRE\", key, ARGV[2])" );
    lua.append( "\nreturn curentLimit + 1" );
    lua.append( "\nend" );
    return lua.toString();
}

---

下一单元将会讲解SpringBoot实现API限流的完整流程，整个流程将会充分利用AOP特性与线程安全的对象池。

且看下回分解！