常见限流算法

发表于 2020-01-19 更新于 2023-03-22 分类于 java ， algorithm

前言

工作中遇到了限制请求数的场景，学习和记录一下解决办法。

总结

在开发高并发系统时有三把利器用来保护系统：缓存、降级和限流
缓存:缓存的目的是提升系统访问速度和增大系统处理容量
降级:降级是当服务器压力剧增的情况下，根据当前业务情况及流量对一些服务和页面有策略的降级，以此释放服务器资源以保证核心任务的正常运行
限流:限流的目的是通过对并发访问/请求进行限速，或者对一个时间窗口内的请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务、排队或等待、降级等处理

限流

常见的限流算法有计数器、令牌桶和漏桶算法

计算器算法

计数器算法是限流算法里最简单也是最容易实现的一种算法
示例1：用AomicInteger来记录并发数

public class CountRateLimiter {

    private static AtomicInteger count = new AtomicInteger(0);

    public void exec() {
        if (count.get() >= 10) {
            System.out.println("请求用户过多，请稍后在试！" + System.currentTimeMillis() / 1000);
        } else {
            count.incrementAndGet();
            try {
                // 处理核心逻辑
                TimeUnit.SECONDS.sleep(1);
                System.out.println("--" + System.currentTimeMillis() / 1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                count.decrementAndGet();
            }
        }

    }

}

示例2：使用信号量来控制并发的次数

public class CountRateLimiterSmp {

    private static Semaphore semaphore = new Semaphore(10);

    public void exec() {
        try {
            semaphore.acquire();
            // 处理核心逻辑
            TimeUnit.SECONDS.sleep(1);
            System.out.println("--" + System.currentTimeMillis() / 1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            semaphore.release();
        }
    }

}

用Atomic和Semaphore的最大区别为，如果是瞬时的高并发，可以使请求在阻塞队列中排队，而不是马上拒绝请求，从而达到一个流量削峰的目的。

令牌桶算法

令牌桶算法概念如下：

令牌以固定速率生成；
生成的令牌放入令牌桶中存放，如果令牌桶满了则多余的令牌会直接丢弃，当请求到达时，会尝试从令牌桶中取令牌，取到了令牌的请求可以执行；
如果桶空了，那么尝试取令牌的请求会被直接丢弃。

令牌桶算法既能够将所有的请求平均分布到时间区间内，又能接受服务器能够承受范围内的突发请求，因此是目前使用较为广泛的一种限流算法。Google 的开源项目 guava 提供了 RateLimiter 类，实现了单点的令牌桶限流。为了学习,模拟一下该算法的实现

/**
 * 简单限流器-令牌桶算法<br/>
 * 只需要记录一个下一令牌产生的时间，并动态更新它，就能够轻松完成限流功能
 */
public class SimpleLimiter {
    // 当前令牌桶中的令牌数量
    long storedPermits = 0;
    // 令牌桶的容量
    long maxPermits = 3;
    // 下一令牌产生时间
    long next = System.nanoTime();
    // 发放令牌间隔：纳秒
    long interval = 1000_000_000;

    // 请求时间在下一令牌产生时间之后,则
    // 1.重新计算令牌桶中的令牌数
    // 2.将下一个令牌发放时间重置为当前时间
    void resync(long now) {
        if (now > next) {
            // 新产生的令牌数
            long newPermits = (now - next) / interval;
            // 新令牌增加到令牌桶
            storedPermits = Math.min(maxPermits, storedPermits + newPermits);
            // 将下一个令牌发放时间重置为当前时间
            next = now;
        }
    }

    // 预占令牌，返回能获取令牌的时间
    synchronized long reserve(long now) {
        resync(now);
        // 能够获取令牌的时间
        long at = next;
        // 令牌桶中能提供的令牌
        long fb = Math.min(1, storedPermits);
        // 令牌净需求：首先减掉令牌桶中的令牌
        long nr = 1 - fb;
        // 重新计算下一令牌产生时间
        next = next + nr * interval;
        // 重新计算令牌桶中的令牌
        this.storedPermits -= fb;
        return at;
    }

    // 申请令牌
    void acquire() {
        // 申请令牌的时间
        long now = System.nanoTime();
        // 预占令牌
        long at = reserve(now);
        long waitTime = Math.max(at - now, 0);
        // 按照条件等待
        if (waitTime > 0) {
            try {
                TimeUnit.NANOSECONDS.sleep(waitTime);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

}

测试代码

    public static void main(String[] args) {
        // 限流器流速
        SimpleLimiter limiter = new SimpleLimiter();
        // 执行任务的线程池
        ExecutorService es = Executors.newFixedThreadPool(20);
        // 记录上一次执行时间
        long prev = System.nanoTime();
        // 测试执行20次
        for (int i = 0; i < 20; i++) {
            // 限流器限流
            limiter.acquire();
            // 提交任务异步执行
            long cur = System.nanoTime();
            es.execute(new Task(prev, cur, i));
            prev = cur;
        }
        es.shutdown();
    }
class Task implements Runnable {
    private long prev;
    private long cur;
    private int index;

    public Task(long prev, long cur, int index) {
        this.prev = prev;
        this.cur = cur;
        this.index = index;
    }
    @Override
    public void run() {
        // 打印时间间隔:毫秒
        System.out.println(index + " : " + (cur - prev) / 1000_000);
    }
}

漏桶算法

漏桶算法概念如下：

将每个请求视作 “ 水滴 “ 放入 “ 漏桶 “ 进行存储；
“漏桶 “ 以固定速率向外 “ 漏 “ 出请求来执行如果 “ 漏桶 “ 空了则停止 “ 漏水”；
如果 “ 漏桶 “ 满了则多余的 “ 水滴 “ 会被直接丢弃。

漏桶算法多使用队列实现，服务的请求会存到队列中，服务的提供方则按照固定的速率从队列中取出请求并执行，过多的请求则放在队列中排队或直接拒绝。

缺点：漏桶算法的缺陷也很明显，当短时间内有大量的突发请求时，即便此时服务器没有任何负载，每个请求也都得在队列中等待一段时间才能被响应。