常见的限流算法

限流的定义

限流，也称流量控制。是指系统在面临高并发，或者大流量请求的情况下，限制新的请求对系统的访问，从而保证系统的稳定性。限流会导致部分用户请求处理不及时或者被拒，这就影响了用户体验。所以一般需要在系统稳定和用户体验之间平衡一下。

一般对于一些调用需要付费的接口，对用户进行限流操作，限制用户的请求次数。
比如：限制单个用户每秒只使用一次

固定窗口算法

单位时间内允许部分操作
维护一个计数器，将单位时间段当做一个窗口，计数器记录这个窗口接收请求的次数。
当次数少于限流阀值，就允许访问，并且计数器+1 当次数大于限流阀值，就拒绝访问。
当前的时间窗口过去之后，计数器清零,开始下一个窗口。

假设单位时间是1秒，限流阀值为3。在单位时间1秒内，每来一个请求,计数器就加1，如果计数器累加的次数超过限流阀值3，后续的请求全部拒绝。等到1s结束后，计数器清0，重新开始计数

优点：实现简单
缺点：会出现流量突刺

滑动窗口算法

单位时间内允许部分操作，但这个单位时间是滑动的,需要指定一个滑动单位。

优点：解决了流量突刺问题
缺点：实现较麻烦，很难找到准确的滑动单位,滑动单位越小，效果越好。

漏桶算法（推荐）

以固定速率处理请求(漏水操作)，当请求桶满了之后，就拒绝请求

优点：在一定程度上能够应对流量突刺，以固定速率处理请求，能够保证服务器的安全
缺点：无法迅速的对请求做出处理,只能一个个按顺序处理(固定速率处理的缺点)

令牌桶算法(推荐)

以固定速率向令牌桶添加令牌，每个令牌代表一定数量的请求，请求需要获取令牌之后才能够被处理。没有令牌的请求会被拒绝。

优点:能够并发的处理请求，并发的性能会更高一点。
缺点：还是存在时间单位选取的问题

限流粒度

1.针对某个方法进行限流，单位时间内最多允许XXX个操作使用使用这个方法。
2,针对某个用户进行限流，某个用户单位时间内最多执行XXX个操作
3.针对某个用户X方法，单个用户单位时间内最多执行XXX次这个方法

本地限流（单机限流）

这里采用谷歌的Guava RateLimiter实现

import com.google.common.util.concurrent.RateLimiter;

public static void main(String[] args) {
    // 每秒限流5个请求
    RateLimiter limiter = RateLimiter.create(5.0);
    while (true) {
        if (limiter.tryAcquire()) {
            // 处理请求
        } else {
            // 超过流量限制，需要做何处理
        }
    }
}

分布式限流（多机限流）

如果你的项目有多个服务器，比如微服务，那么建议使用分布式限流。
1.把用户的使用频率等数据放到一个集中的存储进行统计；比如Redis，这样无论用户的
请求落到了哪台服务器，都以集中存储中的数据为准。(Redisson --是一个操作 Redis 的工具库)
2.在网关集中进行限流和统计(比如 Sentinel、Spring Cloud Gateway)

import org.redisson.Redisson;
import org.redisson.api.RSemaphore;
import org.redisson.api.RedissonClient;

public static void main(String[] args) {
    // 创建RedissonClient
    RedissonClient redisson = Redisson.create();

    // 获取限流器
    RSemaphore semaphore = redisson.getSemaphore("mySemaphore");

    // 尝试获取许可证
    boolean result = semaphore.tryAcquire();
    if (result) {
        // 处理请求
    } else {
        // 超过流量限制，需要做何处理
    }
}

分布式限流的实现

redission配置

package com.cheng.config;


import org.redisson.config.Config;
import lombok.Data;
import org.redisson.Redisson;
import org.redisson.api.RedissonClient;
import org.springframework.boot.context.properties.ConfigurationProperties;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

@Configuration
@ConfigurationProperties(prefix = "spring.redis")
@Data
public class RedissonConfig {

    private String host;

    private Integer port;

    private Integer database;

    private String password;

    @Bean
    public RedissonClient redissonClient() {
        Config config = new Config();
        config.useSingleServer()
        .setAddress("redis://" + host + ":" + port)
        .setDatabase(database)
        .setPassword(password);
        return Redisson.create(config);
    }
}

RedisLimiterManager服务的实现

package com.cheng.manager;


import com.cheng.common.ErrorCode;
import com.cheng.exception.BusinessException;
import org.redisson.api.RRateLimiter;
import org.redisson.api.RateIntervalUnit;
import org.redisson.api.RateType;
import org.redisson.api.RedissonClient;
import org.springframework.stereotype.Service;

import javax.annotation.Resource;

/**
 * 专门提供 RedisLimiter 限流基础服务
 */
@Service
public class RedisLimiterManager {

    @Resource
    private RedissonClient redissonClient;

    /**
     * 采用令牌桶限流算法
     * 每个用户一个限流器
     *
     * 限流操作
     *
     * @param key 区分不同的限流器，比如不同的用户 id 应该分别统计
     */
    public void doRateLimit(String key) {

        // 创建一个名称为user_limiter的限流器，每秒最多访问 2 次
        RRateLimiter rateLimiter = redissonClient.getRateLimiter(key);

        //RateType.OVERALL 统一速率，全局的
        rateLimiter.trySetRate(RateType.OVERALL, 2, 1, RateIntervalUnit.SECONDS);
        // 每当一个操作来了后，请求一个令牌
        boolean canOp = rateLimiter.tryAcquire(1);
        if (!canOp) {
            throw new BusinessException(ErrorCode.REQUEST_OVER);
        }
    }
}

测试类

package com.cheng.springbootinit.manager;

import org.junit.jupiter.api.Test;
import org.springframework.boot.test.context.SpringBootTest;

import javax.annotation.Resource;

import static org.junit.jupiter.api.Assertions.*;

@SpringBootTest
class RedisLimiterManagerTest {

    @Resource
    private RedisLimiterManager redisLimiterManager;

    @Test
    void doRateLimit() throws InterruptedException {
        // 模拟一下操作
        String userId = "1";
        // 瞬间执行2次,每成功一次,就打印'成功'
        for (int i = 0; i < 2; i++) {
            redisLimiterManager.doRateLimit(userId);
            System.out.println("成功");
        }
        // 睡1秒
        Thread.sleep(1000);
        // 瞬间执行5次,每成功一次,就打印'成功'
        for (int i = 0; i < 5; i++) {
            redisLimiterManager.doRateLimit(userId);
            System.out.println("成功");
        }
    }
}