高并发限流

高并发限流

问题描述

突然发现自己的接口请求量突然涨到之前的10倍,带宽被占满,没多久该接口几乎不可使用,并引发连锁反应导致整个系统崩溃。

计数器(固定窗口)算法

计数器算法是使用计数器在周期内累加访问次数,当达到设定的限流值时,触发限流策略。下一个周期开始时,进行清零,重新计数。

此算法在单机还是分布式环境下实现都非常简单,使用redis的incr原子自增性和线程安全即可轻松实现。

高并发限流

这个算法通常用于QPS限流和统计总访问量,对于秒级以上的时间周期来说,会存在一个非常严重的问题,那就是临界问题,如下图:

高并发限流

假设1min内服务器的负载能力为100,因此一个周期的访问量限制在100,然而在第一个周期的最后5秒和下一个周期的开始5秒时间段内,分别涌入100的访问量,虽然没有超过每个周期的限制量,但是整体上10秒内已达到200的访问量,已远远超过服务器的负载能力,由此可见,计数器算法方式限流对于周期比较长的限流,存在很大的弊端。

滑动窗口算法

滑动窗口算法是将时间周期分为N个小周期,分别记录每个小周期内访问次数,并且根据时间滑动删除过期的小周期。

如下图,假设时间周期为1min,将1min再分为2个小周期,统计每个小周期的访问数量,则可以看到,第一个时间周期内,访问数量为75,第二个时间周期内,访问数量为100,超过100的访问则被限流掉了
高并发限流

由此可见,当滑动窗口的格子划分的越多,那么滑动窗口的滚动就越平滑,限流的统计就会越精确。

此算法可以很好的解决固定窗口算法的临界问题。

使用Redis中Zset方法可以实现滑动窗口,在一个列表中,value可以是随机值,但是score是时间戳,zset中range方法可以拿到两个时间戳间隔内的个数,如果超过则直接返回。

漏桶算法

漏桶算法是访问请求到达时直接放入漏桶,如当前容量已达到上限(限流值),则进行丢弃(触发限流策略)。漏桶以固定的速率进行释放访问请求(即请求通过),直到漏桶为空。

高并发限流

令牌桶算法

一个存放固定容量令牌的桶,按照固定速率(每秒/或者可以自定义时间)往桶里添加令牌,然后每次获取一个令牌,当桶里没有令牌可取时,则拒绝服务
令牌桶分为2个动作,动作1(固定速率往桶中存入令牌)、动作2(客户端如果想访问请求,先从桶中获取token)

高并发限流

RateLimiter

create(double permitsPerSecond)根据指定的稳定吞吐率创建RateLimiter,这里的吞吐率是指每秒多少许可数(通常是指QPS,每秒多少查询)

create(double permitsPerSecond, long warmupPeriod, TimeUnit unit)根据指定的稳定吞吐率和预热期来创建RateLimiter,这里的吞吐率是指每秒多少许可数(通常是指QPS,每秒多少个请求量),在这段预热时间内,RateLimiter每秒分配的许可数会平稳地增长直到预热期结束时达到其最大速率。(只要存在足够请求数来使其饱和)

两个方法区别:第一个方法固定速率生成令牌数,第二个方法有预热时间段,在预热阶段内不超过设定的令牌数,超过预热期后以固定时间速率生成令牌,当出现突然出现大量数据。
明显区别:使用第一种方法可能会使消费方(后台服务)没有消费完成,一直往系统塞数据导致服务器不可用,使用第二种方法将流量比较平滑的过渡,从而降低后台服务down掉的风险(就是预热期内设置的令牌数少,不容易一下子把系统攻破)

RateLimiter是一个抽象类,限流器有两个实现类:1、SmoothBursty;2、SmoothWarmingUp

SmoothBursty是以稳定的速度生成permit。SmoothWarmingUp是渐进的生成,最终达到最大值趋于稳定。

偿还机制:当前请求的债务(请求的令牌大于限流器存储的令牌数)由下一个请求来偿还(上个请求亏欠的令牌,下个请求需要等待亏欠令牌生产出来以后才能被授权)acquire多个token时生效。

stableIntervalMircos //稳定生成令牌的时间间隔。

maxBurstSeconds  //1秒生产的令牌。

maxPermits //最大存储令牌数。

nextFreeTicketMicros //下个请求可被授权令牌的时间(不管请求多少令牌),实现当前债务由下一个请求来偿还机制关键。

storedPermits //已存储的令牌,生产过剩的令牌存储小于等于maxPermits,是应对突发流量的请求的关键。
    
//从RateLimiter中获取一个permit,阻塞直到请求可以获得为止。
public double acquire(){
	Return acquire(1);
}


//从RateLimiter中获取指定数量的permits,阻塞直到请求可以获得为止
public double acquire(int permits) {
	//计算获得这些数量需等待时间
        long microsToWait = reserve(permits);
		//不可被打断的等待
        stopwatch.sleepMicrosUninterruptibly(microsToWait);
		//单位转换为秒
        return 1.0 * microsToWait / SECONDS.toMicros(1L);
    }

//预订给定数量的permits来使用,计算需要这些数量permits等待时间。
final long reserve(int permits) {
		//校验负数
        checkPermits(permits);
		//抢占锁,这里的锁使用单例模式获得
        synchronized (mutex()) {
			//计算等待时间
            return reserveAndGetWaitLength(permits, stopwatch.readMicros());
        }
}

//具体计算等待时间的逻辑(继承上一次债务,并且透支本次所需要的所有permits)
//注意这里返回的是时间点
final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
		
		//	同步时间轴
        resync(nowMicros); 
        //	继承上次债务
        long returnValue = nextFreeTicketMicros;
		//	跟桶内存储量比,本次可以获取到的permit数量,如果存储的permit大于本次需要的permit数量则此处是0,否则是一个正数
        double storedPermitsToSpend = min(requiredPermits, this.storedPermits); 
        
        //	还缺少的permits数量
        double freshPermits = requiredPermits - storedPermitsToSpend;    

        //	计算需要等待的时间(微秒)
        long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend) + (long) (freshPermits * stableIntervalMicros);    
		 //	继承上一次债务时间点+这次需要等待的时间,让下一次任务去等待
        this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);
        //	减去本次消费的permit数
        this.storedPermits -= storedPermitsToSpend;    
        //	本次只需要等待到上次欠债时间点即可
        return returnValue; 
}

源码示例

/**
<dependency>
   <groupId>com.google.guava</groupId>
   <artifactId>guava</artifactId>
   <version>25.1-jre</version>
</dependency>
**/

@RestController
public class HelloController {

    private static final SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");

    private static final RateLimiter rateLimiter = RateLimiter.create(2);

    /**
     * tryAcquire尝试获取permit,默认超时时间是0,意思是拿不到就立即返回false
     */
    @RequestMapping("/sayHello")
    public String sayHello() {
        if (rateLimiter.tryAcquire()) { //  一次拿1个
            System.out.println(sdf.format(new Date()));
            try {
                Thread.sleep(500);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }else {
            System.out.println("limit");
        }
        return "hello";
    }

    /**
     * acquire拿不到就等待,拿到为止
     */
    @RequestMapping("/sayHi")
    public String sayHi() {
        rateLimiter.acquire(5); //  一次拿5个
        System.out.println(sdf.format(new Date()));
        return "hi";
    }

}

各算法比较

高并发限流

漏桶

漏桶的出水速度是恒定的,那么意味着如果瞬时大流量的话,将有大部分请求被丢弃掉(也就是所谓的溢出)。

令牌桶

生成令牌的速度是恒定的,而请求去拿令牌是没有速度限制的。这意味,面对瞬时大流量,该算法可以在短时间内请求拿到大量令牌,而且拿令牌的过程并不是消耗很大的事情。

最后,不论是对于令牌桶拿不到令牌被拒绝,还是漏桶的水满了溢出,都是为了保证大部分流量的正常使用,而牺牲掉了少部分流量,这是合理的,如果因为极少部分流量需要保证的话,那么就可能导致系统达到极限而挂掉,得不偿失。

并不能说明令牌桶一定比漏洞好,她们使用场景不一样。令牌桶可以用来保护自己,主要用来对调用者频率进行限流,为的是让自己不被打垮。所以如果自己本身有处理能力的时候,如果流量突发(实际消费能力强于配置的流量限制),那么实际处理速率可以超过配置的限制。

而漏桶算法,这是用来保护他人,也就是保护他所调用的系统。主要场景是,当调用的第三方系统本身没有保护机制,或者有流量限制的时候,我们的调用速度不能超过他的限制,由于我们不能更改第三方系统,所以只有在主调方控制。这个时候,即使流量突发,也必须舍弃。因为消费能力是第三方决定的。

如果要让自己的系统不被打垮,用令牌桶。如果保证别人的系统不被打垮,用漏桶算法

这是单机(单进程)的限流,是JVM级别的的限流,所有的令牌生成都是在内存中,在分布式环境下不能直接这么用。

如果我们能把permit放到Redis中就可以在分布式环境中用了。

参考资料

高并发限流

上一篇:Centos Yum 安装 Postgres


下一篇:使用kubeadm部署k8s集群v1.21【其他版本通用】