摆烂基地

限流

谈谈限流

WHY限流

​ 在很多场景中,业务上下游无法接受激增的流量(业务流量波动/被攻击/流量超出接口性能),也无需将流量丢进MQ(可能会造成大量lag),可以采用限流的方式,将请求阻塞或丢弃一部分以保证服务的整体稳定性. 比较常见的是网关层的限流和应用层的限流, 最近需求有用到相关组件, 写个博客记录下.

限流算法

固定窗口算法

固定时间内只允许固定的调用, 生成一个计数器, 设置固定的调用次数. 定时清空

@Service
@Slf4j
public class FixedWindowRateLimiter {

    @Autowired
    private RedisTemplate<String, Object> redisTemplate;

    private static final int LIMIT = 5;

    private static final String FIX_WINDOW_KEY_PREFIX = "fixed-time-rate-limiter";
    private static final int TIME = 3;


    public boolean tryAcquire() {
        String key = getKey();
        long count = redisTemplate.opsForValue().increment(key, 1);
        if (count == 1) {
            redisTemplate.expire(key, TIME, TimeUnit.SECONDS);
        }
        return count <= LIMIT;
    }

    public String time(){
        DateTimeFormatter dtf=DateTimeFormatter.ofPattern("yyyy-MM-dd-hh:mm:ss");
        return dtf.format(LocalDateTime.now());
    }

    private String getKey() {
        return FIX_WINDOW_KEY_PREFIX;
    }
}

@SpringBootTest
public class FixWindowTest {
    @Autowired
    FixedWindowRateLimiter fixedWindowRateLimiter;
    @Test
    public void test(){
        for (int i = 0; i < 1000; i++) {
            try {
                if (fixedWindowRateLimiter.tryAcquire()){
                    System.out.println(fixedWindowRateLimiter.time() +" 处理");
                    sleep(123);
                } else {
                    System.out.println(fixedWindowRateLimiter.time() + "丢弃");
                    sleep(25);
                }
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
        }
    }
}

优点

  • 这种限流实现起来比较简单,可以将机器信息放入key中简单实现分布式限流.

缺点

  • 这种限流算法无法保证限流速率，因而无法保证突然激增的流量

img

滑动窗口算法

@Service
@Slf4j
public class SlidingWindowRateLimiter {

    @Autowired
    private RedisTemplate<String, Object> redisTemplate;

    private static final int LIMIT = 5;

    private static final String SLIDING_WINDOW_KEY_PREFIX = "sliding-window-rate-limiter";
    private static final int WINDOW_SIZE = 60;


    public boolean tryAcquire() {
        String key = getKey();
        long count = redisTemplate.opsForValue().increment(key, 1);
        if (count == 1) {
            redisTemplate.expire(key, WINDOW_SIZE, TimeUnit.SECONDS);
        }
        return count <= LIMIT;
    }

    public String time(){
        DateTimeFormatter dtf=DateTimeFormatter.ofPattern("yyyy-MM-dd-hh:mm:ss");
        return dtf.format(LocalDateTime.now());
    }

    private String getKey() {
        return SLIDING_WINDOW_KEY_PREFIX + ":" + time();
    }
}

@SpringBootTest
public class SlidingWindowTest {
    @Autowired
    SlidingWindowRateLimiter rateLimiter;
    @Test
    public void test(){
        for (int i = 0; i < 100; i++) {
            try {
                if (rateLimiter.tryAcquire()){
                    System.out.println(rateLimiter.time() +" 处理");
                    sleep(150);
                } else {
                    System.out.println(rateLimiter.time() + "丢弃");
                }
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
        }
    }
}

优点

  • 滑动窗口计数器算法相比于固定窗口计数器算法的优化在于, 它把时间以一定比例分片, 当滑动窗口的格子划分的越多，滑动窗口的滚动就越平滑，限流的统计就会越精确

缺点

  • 依赖于时间片大小, 仍然会存在时间边界前后

img

漏桶算法

虽然滑动窗口有效避免了时间临界点的问题，但是依然有时间片的概念，而漏桶算法

有一个固定的桶，进水的速率是不确定的，但是出水的速率是恒定的，当水满的时候是会溢出的

@Slf4j
@Service
public class LeakyBucketRateLimiter{
    @Autowired
    private RedisTemplate<String, Object> redisTemplate;

    private static final long BUCKET_RATE = 10; // 令牌生成速率（令牌/秒）

    private static final String BUCKET_KEY_PREFIX = "leaky-bucket-rate-limiter";
    private static final long BUCKET_CAPACITY = 100L;

    public boolean tryAcquire() {
        long currentTime = System.currentTimeMillis();
        String currentKey = String.valueOf(currentTime);
        // 尝试从令牌桶中获取一个令牌
        Long tokenCount = count();
        if (tokenCount < BUCKET_CAPACITY) {
            // 令牌桶未满，添加一个令牌
            redisTemplate.opsForZSet().add(BUCKET_KEY_PREFIX, currentKey, currentTime);
            //令牌桶数量变化
            return count()!=tokenCount;
        } else {
            // 令牌桶已满，移除过期的令牌
            long removeCount = redisTemplate.opsForZSet().removeRangeByScore(BUCKET_KEY_PREFIX, 0, currentTime - 1000);
            if (removeCount < BUCKET_RATE) {
                // 未移除足够数量的令牌，请求被限流
                return false;
            } else {
                // 移除了足够数量的令牌，添加新令牌
                redisTemplate.opsForZSet().add(BUCKET_KEY_PREFIX, currentKey, currentTime);
                return true;
            }
        }
    }

    public String time(){
        DateTimeFormatter dtf=DateTimeFormatter.ofPattern("yyyy-MM-dd-hh:mm:ss");
        return dtf.format(LocalDateTime.now());
    }

    private String getKey() {
        return BUCKET_KEY_PREFIX;
    }

    private long count(){
        return  redisTemplate.opsForZSet().zCard(BUCKET_KEY_PREFIX);
    }
}

@SpringBootTest
public class LeakyBucketTest {
    @Autowired
    LeakyBucketRateLimiter rateLimiter;
    @Test
    public void test(){
        for (int i = 0; i < 1000; i++) {
            try {
                if (rateLimiter.tryAcquire()){
                    System.out.println(rateLimiter.time() +" 处理");
//                    sleep(50);
                } else {
                    System.out.println(rateLimiter.time() + "丢弃");
//                    sleep(50);
                }
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
    }
}

上面的写法其实是有问题的,只能算是毫秒级的滑动窗口,懒着改了,想要优化达到真正意义的漏桶算法,需要在拿新令牌的时候校验桶中最大的时间戳+漏桶漏水滴时间间隔和当前key时间戳的关系

令牌桶

注意到，漏桶的出水速度是恒定的，那么意味着如果瞬时大流量的话，将有大部分请求被丢弃掉（也就是所谓的溢出）。为了解决这个问题，令牌桶进行了算法改进, 本质上就是在拿令牌的时候提供阻塞的方法。

img

生成令牌的速度是恒定的，而请求去拿令牌是没有速度限制的。这意味，面对瞬时大流量，该算法可以在短时间内请求拿到大量令牌，而且拿令牌的过程并不是消耗很大的事情。（有一点生产令牌，消费令牌的意味）
不论是对于令牌桶拿不到令牌被拒绝，还是漏桶的水满了溢出，都是为了保证大部分流量的正常使用，而牺牲掉了少部分流量，这是合理的，如果因为极少部分流量需要保证的话，那么就可能导致系统达到极限而挂掉，得不偿失。

这里可以使用Guava RateLimiter

@SpringBootTest
public class TokenBucketTest {
    private static RateLimiter rateLimiter = RateLimiter.create(5);

    /**
     * 非阻塞
     */
    @Test
    public void test1(){
        for (int i = 0; i < 100; i++) {
            try {
                if (rateLimiter.tryAcquire()){
                    System.out.println(time() +" 处理");
                    sleep(150);
                } else {
                    System.out.println(time() + "丢弃");
                }
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
        }
    }
    /**
     * 阻塞
     */
    @Test
    public void test2(){
        for (int i = 0; i < 100; i++) {
            try {
                rateLimiter.acquire();
                System.out.println(time() +" 处理");
                sleep(150);
            } catch (InterruptedException e) {
                System.out.println(time() +" 处理失败/丢弃");
                throw new RuntimeException(e);
            }
        }
    }
    public String time(){
        DateTimeFormatter dtf=DateTimeFormatter.ofPattern("yyyy-MM-dd-hh:mm:ss");
        return dtf.format(LocalDateTime.now());
    }
}

TODO:

预热限流 网关限流 分布式限流 先鸽了 慢慢补

其他

github/WangJunnan/learn

github/li-ruida/blog

逐行拆解Guava限流器RateLimiter - 知乎

分布式限流的主流方案有哪些？ - 知乎

面试官：来，年轻人！请手撸5种常见限流算法y

实战 Spring Cloud Gateway 之限流篇 - 知乎

超详细的Guava RateLimiter限流原理解析 - 知乎

分布式接口幂等性、分布式限流（Guava 、nginx和lua限流） - 知乎

居高声自远,非是藉秋风

© 2024 摆烂基地