令牌桶算法_令牌桶算法java实现 - CSDN
精华内容
参与话题
  • 令牌桶算法原理及实现

    千次阅读 2019-09-25 21:50:05
    令牌桶算法是经典的网络限流算法,它可以限制带宽,使流量以一个较为均匀的速度向外发送。我们可以把令牌桶算法想象成一个有固定容量的桶,每个数据包都要经过这个桶处理。如果当前数据包的大小 大于 桶内的令牌数,...

        令牌桶算法是经典的网络限流算法,它可以限制带宽,使流量以一个较为均匀的速度向外发送。我们可以把令牌桶算法想象成一个有固定容量的桶,每个数据包都要经过这个桶处理。如果当前数据包的大小 大于 桶内的令牌数,则放行该数据包,否则丢掉该数据包,或者延时发送。

     一、先来看几个名词解释:

    1.令牌数:可以把令牌数理解为字节数或者比特数。

    2.桶的容量:就是允许的最大突发信息传输速率,即允许的最大瞬时带宽。

    3.带宽:单位时间内能够在线路上传送的数据量,常用的单位是bps(bit per second)。

    二、性质:(假设:限制带宽为20kbps)

    1.令牌桶的容量是固定的,令牌桶中可以保存的最大令牌数永远不会超过桶的大小。

    2.令牌桶处理数据包会消耗令牌桶内的令牌,消耗的令牌数.等于数据包的大小。

    3.令牌桶以恒定的速率产生令牌,速率大小就是限制的带宽,即,v = 20kbps。

    三、代码实现

    #include <iostream>
    #include <atomic> 
    #include <ctime>
    #include <time.h>
    
    
    class TokenBucket {
    	typedef enum color{
    		GREEN,
    		RED
    	}COLOR;
    private :
    	int m_cir; // 添加令牌的速率
    	int m_cbs; // 桶的容量
    
    	std::atomic<int64_t> m_clsLastUpdateTime; // 上次桶内令牌数更新时间
    	std::atomic<int64_t> m_clsCurTokenNum; // 当前桶内令牌数
    
    	// 毫秒级时间,不够用可以自己重写
    	int64_t _get_cur_time() {
    		return clock();
    	}
    
    public:
    	TokenBucket(int cir, int cbs) {
    		m_cir = cir;
    		m_cbs = cbs;
    		m_clsLastUpdateTime = _get_cur_time();
    	}
    
    	~TokenBucket() {}
    
    	/************************ 
    	  数据包处理函数
    	  参数:token, 数据包大小
    	  返回值:RED, 惩罚处理
    		     GREED, 放行
    	************************/
    	COLOR packetProcess(int token) {
    		int64_t nowTime;
    		int64_t timeInterval;
    		int64_t updateTokenNum;
    		int64_t curTokenNum = m_clsCurTokenNum.load();
    		if (token <= curTokenNum) {
    			m_clsCurTokenNum.fetch_sub(token);
    			return GREEN;
    		}
    		nowTime = _get_cur_time();
    		timeInterval = nowTime - m_clsLastUpdateTime.load();
    		updateTokenNum = timeInterval * m_cir + curTokenNum;
    		if (updateTokenNum < token) {
    			return RED;
    		}
    		else {
    			updateTokenBucket(nowTime, updateTokenNum);
    		}
    		m_clsCurTokenNum.fetch_sub(token);
            return GREEN;
    	}
    
    	/************************ 
    	  更新令牌桶内的时间以及数量
    	  参数:time, 更新时间
    		    num, 数量
    	  返回值:void
    	************************/
    	void updateTokenBucket(int64_t time, int64_t num) {
    		m_clsLastUpdateTime.store(time);
    		m_clsCurTokenNum.store(num);
    	}
    };

     

    展开全文
  • 令牌桶算法

    千次阅读 2017-09-06 10:02:30
    令牌桶算法(token bucket algorithm)  在实施QOS策略时,可以将用户的数据限制在特定的带宽,当用户的流量超过额定带宽时,超过的带宽将采取其它方式来处理。要衡量流量是否超过额定的带宽,网络设备并...

    令牌桶算法(token bucket algorithm)

           在实施QOS策略时,可以将用户的数据限制在特定的带宽,当用户的流量超过额定带宽时,超过的带宽将采取其它方式来处理。要衡量流量是否超过额定的带宽,网络设备并不是采用单纯的数字加减法来决定的,也就是说,比如带宽为100K,而用户发来的流量为110K,网络设备并不是靠110K减去100K等于10K,就认为用户超过流量10K。网络设备

    衡量流量是否超过额定带宽,需要使用令牌桶算法来计算。下面详细介绍令牌桶算法机制:

    当网络设备衡量流量是否超过额定带宽时,需要查看令牌桶,而令牌桶中会放置一定数量的令牌,一个令牌允许接口发送或接收1bit数据(有时是1 Byty数据),当接口通过1bit数据后,同时也要从桶中移除一个令牌。当桶里没有令牌的时候,任何流量都被视为超过额定带宽,只有当桶中有令牌时,数据才可以通过接口。令牌桶中的令牌不仅仅可以被移除,同样也可以往里添加,所以为了保证接口随时有数据通过,就必须不停地往桶里加令牌,由此可见,往桶里加令牌的速度,就决定了数据通过接口的速度。因此,我们通过控制往令牌桶里加令牌的速度从而控制用户流量的带宽。而设置的这个用户传输数据的速率被称为承诺信息速率(CIR),通常以秒为单位。比如我们设置用户的带宽为1000  bit每秒,只要保证每秒钟往桶里添加1000个令牌即可。

     

    例:

    将CIR设置为8000  bit/s,那么就必须每秒将8000个令牌放入桶中,当接口有数据通过时,就从桶中移除相应的令牌,每通过1  bit,就从桶中移除1个令牌。当桶里没有令牌的时候,任何流量都被视为超出额定带宽,而超出的流量就要采取额外动作。

     

    每秒钟往桶里加的令牌就决定了用户流量的速率,这个速率就是CIR,但是每秒钟需要往桶里加的令牌总数,并不是一次性加完的,一次性加进的令牌数量被称为Burst  size(Bc),如果Bc只是CIR的一半,那么很明显每秒钟就需要往桶里加两次令牌,每次加的数量总是Bc的数量。

    还有就是加令牌的时间,Time interval(Tc),Tc表示多久该往桶里加一次令牌,而这个时间并不能手工设置,因为这个时间可以靠CIR和Bc的关系计算得到,  Bc/ CIR= Tc。

    例:

    如果CIR是8000,Bc是4000,那就是每秒加两次,Tc就是4000/8000=0.5,也就是0.5秒,即500 ms。

    如果Bc设为2000,那Tc就是2000/8000=0.25, 也就是250  ms。




    一、在流量监管中的应用

    约定访问速率(CAR)是流量监管常用技术之一,可以应用在端口进和出方向,一般应用在入方向,它的监管原理如图1所示。

    a. 按特定的速率向令牌桶投放令牌

    b. 根据预设的匹配规则先对报文进行分类,不符合匹配规则的报文不需要经过令牌桶的处理,直接发送;

    c. 符合匹配规则的报文,则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去,同时令牌桶中的令牌 量按报文的长度做相应的减少;

    d. 当令牌桶中的令牌不足时,报文将不能被发送,只有等到桶中生成了新的令牌,报文才可以发送。这就可以限制报文的流量只能是小于等于令牌生成的速度,达到限制流量的目的。

    二、在通用流量整形中的应用

    a. 按特定的速率向令牌桶投放令牌

    b. 根据预设的匹配规则先对报文进行分类,不符合匹配规则的报文不需要经过令牌桶的处理,直接发送;

    c. 符合匹配规则的报文,则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去,同时令牌桶中的令牌 量按报文的长度做相应的减少;

    d. 对超过速率限制的报文进行缓冲即当令牌桶的令牌少到报文不能再发送时,报文将被缓存入队列,等有了足够的令牌之后再发送,

    e. 当令牌桶中的令牌不足时,报文将不能被发送,只有等到桶中生成了新的令牌,报文才可以发送。

    通用流量整形中( GTS)CAR的原理稍有差别:

    第一,GTS只用于出方向流量限速CAR出入方向均可以,但一般多用于入方向;

    第二,利用CAR进行报文流量控制时,对超过速率限制的报文直接丢弃,而GTS是对超过速率限制的报文进行缓冲即当令牌桶的令牌少到报文不能再发送时,报文将被缓存入队列,等有了足够的令牌之后再发送,这样就减少了报文的丢弃,但是要注意的是,如果缓存队列已满,这时到达的报文仍旧会被丢弃。

    三、在端口限速 中的应用

    端口限速(LR)(如图3所示)也用于出方向,但不同于GTS 的是:第一,GTSCAR是在IP层实现的,所以对于不经过IP层处理的报文不起作用,而LR能够限制在物理接口上通过的所有报文;第二,LR不但能够对超过流量限制的报文进行缓存,并且可以利用QoS丰富的队列如优先级队列(PQ)、自定  队列(CQ)、加权公平对列(WFQ)等来缓存报文。

    a. 按特定的速率向令牌桶投放令牌

    b. 根据预设的匹配规则先对报文进行分类,利用QoS丰富的队列如优先级队列(PQ)、自定  队列(CQ)、加权公平对列(WFQ)等来缓存报文

    c. 符合匹配规则的报文,则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去,同时令牌桶中的令牌 量按报文的长度做相应的减少;

    d. 对超过速率限制的报文进行缓冲即当令牌桶的令牌少到报文不能再发送时,报文将被缓存入队列,等有了足够的令牌之后再发送,

    e. 当令牌桶中的令牌不足时,报文将不能被发送,只有等到桶中生成了新的令牌,报文才可以发送。


    展开全文
  • 参考: http://www.cnblogs.com/LBSer/p/4083131.html https://blog.csdn.net/scorpio3k/article/details/53103239 https://www.cnblogs.com/clds/p/5850070.html ... ht...

    参考:
    https://www.cnblogs.com/xuwc/p/9123078.html
    http://www.cnblogs.com/LBSer/p/4083131.html

    https://blog.csdn.net/scorpio3k/article/details/53103239

    https://www.cnblogs.com/clds/p/5850070.html

    http://jinnianshilongnian.iteye.com/blog/2305117

    http://iamzhongyong.iteye.com/blog/1742829

    一、问题描述

    某天A君突然发现自己的接口请求量突然涨到之前的10倍,没多久该接口几乎不可使用,并引发连锁反应导致整个系统崩溃。如何应对这种情况呢?生活给了我们答案:比如老式电闸都安装了保险丝,一旦有人使用超大功率的设备,保险丝就会烧断以保护各个电器不被强电流给烧坏。同理我们的接口也需要安装上“保险丝”,以防止非预期的请求对系统压力过大而引起的系统瘫痪,当流量过大时,可以采取拒绝或者引流等机制。

    二、常用的限流算法

      常用的限流算法有两种:漏桶算法和令牌桶算法。
    
      漏桶算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水,当水流入速度过大会直接溢出,可以看出漏桶算法能强行限制数据的传输速率。
    

    在这里插入图片描述图1 漏桶算法示意图

      对于很多应用场景来说,除了要求能够限制数据的平均传输速率外,还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了,令牌桶算法更为适合。如图2所示,令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务。
    

    在这里插入图片描述
    三、限流工具类RateLimiter

    Google开源工具包Guava提供了限流工具类RateLimiter,该类基于令牌桶算法来完成限流,非常易于使用。RateLimiter类的接口描述请参考:RateLimiter接口描述,具体使用请参考:RateLimiter使用实践。

      下面是主要源码:
    
    
    public double acquire() {
            return acquire(1);
        }
    
     public double acquire(int permits) {
            checkPermits(permits);  //检查参数是否合法(是否大于0)
            long microsToWait;
            synchronized (mutex) { //应对并发情况需要同步
                microsToWait = reserveNextTicket(permits, readSafeMicros()); //获得需要等待的时间 
            }
            ticker.sleepMicrosUninterruptibly(microsToWait); //等待,当未达到限制时,microsToWait为0
            return 1.0 * microsToWait / TimeUnit.SECONDS.toMicros(1L);
        }
    
    private long reserveNextTicket(double requiredPermits, long nowMicros) {
            resync(nowMicros); //补充令牌
            long microsToNextFreeTicket = nextFreeTicketMicros - nowMicros;
            double storedPermitsToSpend = Math.min(requiredPermits, this.storedPermits); //获取这次请求消耗的令牌数目
            double freshPermits = requiredPermits - storedPermitsToSpend;
    
            long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
                    + (long) (freshPermits * stableIntervalMicros); 
    
            this.nextFreeTicketMicros = nextFreeTicketMicros + waitMicros;
            this.storedPermits -= storedPermitsToSpend; // 减去消耗的令牌
            return microsToNextFreeTicket;
        }
    
    private void resync(long nowMicros) {
            // if nextFreeTicket is in the past, resync to now
            if (nowMicros > nextFreeTicketMicros) {
                storedPermits = Math.min(maxPermits,
                        storedPermits + (nowMicros - nextFreeTicketMicros) / stableIntervalMicros);
                nextFreeTicketMicros = nowMicros;
            }
        }
    

    服务治理—限流(令牌桶算法)

    1、最近在写一个分布式服务的框架,对于分布式服务的框架来说,除了远程调用,还要进行服务的治理

    当进行促销的时候,所有的资源都用来完成重要的业务,就比如双11的时候,主要的业务就是让用户查询商品,以及购买支付,

    此时,金币查询、积分查询等业务就是次要的,因此要对这些服务进行服务的降级,典型的服务降级算法是采用令牌桶算法,

    因此在写框架的时候去研究了一下令牌桶算法

    2、在实施QOS策略时,可以将用户的数据限制在特定的带宽,当用户的流量超过额定带宽时,超过的带宽将采取其它方式来处理。

    要衡量流量是否超过额定的带宽,网络设备并不是采用单纯的数字加减法来决定的,也就是说,比如带宽为100K,而用户发来

    的流量为110K,网络设备并不是靠110K减去100K等于10K,就认为用户超过流量10K。网络设备衡量流量是否超过额定带宽,

    需要使用令牌桶算法来计算。下面详细介绍令牌桶算法机制:

    当网络设备衡量流量是否超过额定带宽时,需要查看令牌桶,而令牌桶中会放置一定数量的令牌,一个令牌允许接口发送

    或接收1bit数据(有时是1 Byte数据),当接口通过1bit数据后,同时也要从桶中移除一个令牌。当桶里没有令牌的时候,任何流

    量都被视为超过额定带宽,只有当桶中有令牌时,数据才可以通过接口。令牌桶中的令牌不仅仅可以被移除,同样也可以往里添加,

    所以为了保证接口随时有数据通过,就必须不停地往桶里加令牌,由此可见,往桶里加令牌的速度,就决定了数据通过接口的速度。

    因此,我们通过控制往令牌桶里加令牌的速度从而控制用户流量的带宽。而设置的这个用户传输数据的速率被称为承诺信息速率(CIR),

    通常以秒为单位。比如我们设置用户的带宽为1000 bit每秒,只要保证每秒钟往桶里添加1000个令牌即可。

    3、举例:

    将CIR设置为8000 bit/s,那么就必须每秒将8000个令牌放入桶中,当接口有数据通过时,就从桶中移除相应的令牌,每通过1 bit,

    就从桶中移除1个令牌。当桶里没有令牌的时候,任何流量都被视为超出额定带宽,而超出的流量就要采取额外动作。每秒钟往桶里加的令牌

    就决定了用户流量的速率,这个速率就是CIR,但是每秒钟需要往桶里加的令牌总数,并不是一次性加完的,一次性加进的令牌数量被称为Burst size(Bc),

    如果Bc只是CIR的一半,那么很明显每秒钟就需要往桶里加两次令牌,每次加的数量总是Bc的数量。还有就是加令牌的时间,Time interval(Tc),

    Tc表示多久该往桶里加一次令牌,而这个时间并不能手工设置,因为这个时间可以靠CIR和Bc的关系计算得到, Bc/ CIR= Tc。

    4、令牌桶算法图例
    在这里插入图片描述a. 按特定的速率向令牌桶投放令牌

    b. 根据预设的匹配规则先对报文进行分类,不符合匹配规则的报文不需要经过令牌桶的处理,直接发送;

    c. 符合匹配规则的报文,则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去,同时令牌桶中的令牌 量按报文的长度做相应的减少;

    d. 当令牌桶中的令牌不足时,报文将不能被发送,只有等到桶中生成了新的令牌,报文才可以发送。这就可以限制报文的流量只能是小于等于令牌生成的速度,达到限制流量的目的。

    5、Java参考代码:

     package com.netease.datastream.util.flowcontrol;
    
    import java.io.BufferedWriter;
    import java.io.FileOutputStream;
    import java.io.IOException;
    import java.io.OutputStreamWriter;
    import java.util.Random;
    import java.util.concurrent.ArrayBlockingQueue;
    import java.util.concurrent.Executors;
    import java.util.concurrent.ScheduledExecutorService;
    import java.util.concurrent.TimeUnit;
    import java.util.concurrent.locks.ReentrantLock;
    
    
    /**
     * <pre>
     * Created by inter12 on 15-3-18.
     * </pre>
     */
    public class TokenBucket {
    
        // 默认桶大小个数 即最大瞬间流量是64M
        private static final int DEFAULT_BUCKET_SIZE = 1024 * 1024 * 64;
    
        // 一个桶的单位是1字节
        private int everyTokenSize = 1;
    
        // 瞬间最大流量
        private int maxFlowRate;
    
        // 平均流量
        private int avgFlowRate;
    
        // 队列来缓存桶数量:最大的流量峰值就是 = everyTokenSize*DEFAULT_BUCKET_SIZE 64M = 1 * 1024 *
        // 1024 * 64
        private ArrayBlockingQueue<Byte> tokenQueue = new ArrayBlockingQueue<Byte>(
                DEFAULT_BUCKET_SIZE);
    
        private ScheduledExecutorService scheduledExecutorService = Executors
                .newSingleThreadScheduledExecutor();
    
        private volatile boolean isStart = false;
    
        private ReentrantLock lock = new ReentrantLock(true);
    
        private static final byte A_CHAR = 'a';
    
        public TokenBucket() {
        }
    
        public TokenBucket(int maxFlowRate, int avgFlowRate) {
            this.maxFlowRate = maxFlowRate;
            this.avgFlowRate = avgFlowRate;
        }
    
        public TokenBucket(int everyTokenSize, int maxFlowRate, int avgFlowRate) {
            this.everyTokenSize = everyTokenSize;
            this.maxFlowRate = maxFlowRate;
            this.avgFlowRate = avgFlowRate;
        }
    
        public void addTokens(Integer tokenNum) {
    
            // 若是桶已经满了,就不再家如新的令牌
            for (int i = 0; i < tokenNum; i++) {
                tokenQueue.offer(Byte.valueOf(A_CHAR));
            }
        }
    
        public TokenBucket build() {
    
            start();
            return this;
        }
    
        /**
         * 获取足够的令牌个数
         * 
         * @return
         */
        public boolean getTokens(byte[] dataSize) {
    
    //        Preconditions.checkNotNull(dataSize);
    //        Preconditions.checkArgument(isStart,
    //                "please invoke start method first !");
    
            int needTokenNum = dataSize.length / everyTokenSize + 1;// 传输内容大小对应的桶个数
    
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                boolean result = needTokenNum <= tokenQueue.size(); // 是否存在足够的桶数量
                if (!result) {
                    return false;
                }
    
                int tokenCount = 0;
                for (int i = 0; i < needTokenNum; i++) {
                    Byte poll = tokenQueue.poll();
                    if (poll != null) {
                        tokenCount++;
                    }
                }
    
                return tokenCount == needTokenNum;
            } finally {
                lock.unlock();
            }
        }
    
        public void start() {
    
            // 初始化桶队列大小
            if (maxFlowRate != 0) {
                tokenQueue = new ArrayBlockingQueue<Byte>(maxFlowRate);
            }
    
            // 初始化令牌生产者
            TokenProducer tokenProducer = new TokenProducer(avgFlowRate, this);
            scheduledExecutorService.scheduleAtFixedRate(tokenProducer, 0, 1,
                    TimeUnit.SECONDS);
            isStart = true;
    
        }
    
        public void stop() {
            isStart = false;
            scheduledExecutorService.shutdown();
        }
    
        public boolean isStarted() {
            return isStart;
        }
    
        class TokenProducer implements Runnable {
    
            private int avgFlowRate;
            private TokenBucket tokenBucket;
    
            public TokenProducer(int avgFlowRate, TokenBucket tokenBucket) {
                this.avgFlowRate = avgFlowRate;
                this.tokenBucket = tokenBucket;
            }
    
            @Override
            public void run() {
                tokenBucket.addTokens(avgFlowRate);
            }
        }
    
        public static TokenBucket newBuilder() {
            return new TokenBucket();
        }
    
        public TokenBucket everyTokenSize(int everyTokenSize) {
            this.everyTokenSize = everyTokenSize;
            return this;
        }
    
        public TokenBucket maxFlowRate(int maxFlowRate) {
            this.maxFlowRate = maxFlowRate;
            return this;
        }
    
        public TokenBucket avgFlowRate(int avgFlowRate) {
            this.avgFlowRate = avgFlowRate;
            return this;
        }
    
        private String stringCopy(String data, int copyNum) {
    
            StringBuilder sbuilder = new StringBuilder(data.length() * copyNum);
    
            for (int i = 0; i < copyNum; i++) {
                sbuilder.append(data);
            }
    
            return sbuilder.toString();
    
        }
    
        public static void main(String[] args) throws IOException,
                InterruptedException {
    
            tokenTest();
        }
    
        private static void arrayTest() {
            ArrayBlockingQueue<Integer> tokenQueue = new ArrayBlockingQueue<Integer>(
                    10);
            tokenQueue.offer(1);
            tokenQueue.offer(1);
            tokenQueue.offer(1);
            System.out.println(tokenQueue.size());
            System.out.println(tokenQueue.remainingCapacity());
        }
    
        private static void tokenTest() throws InterruptedException, IOException {
            TokenBucket tokenBucket = TokenBucket.newBuilder().avgFlowRate(512)
                    .maxFlowRate(1024).build();
    
            BufferedWriter bufferedWriter = new BufferedWriter(
                    new OutputStreamWriter(new FileOutputStream("D:/ds_test")));
            String data = "xxxx";// 四个字节
            for (int i = 1; i <= 1000; i++) {
    
                Random random = new Random();
                int i1 = random.nextInt(100);
                boolean tokens = tokenBucket.getTokens(tokenBucket.stringCopy(data,
                        i1).getBytes());
                TimeUnit.MILLISECONDS.sleep(100);
                if (tokens) {
                    bufferedWriter.write("token pass --- index:" + i1);
                    System.out.println("token pass --- index:" + i1);
                } else {
                    bufferedWriter.write("token rejuect --- index" + i1);
                    System.out.println("token rejuect --- index" + i1);
                }
    
                bufferedWriter.newLine();
                bufferedWriter.flush();
            }
    
            bufferedWriter.close();
        }
    
    }
    

    高并发系统限流中的漏桶算法和令牌桶算法,通过流量整形和速率限制提升稳定性

    在大数据量高并发访问时,经常会出现服务或接口面对暴涨的请求而不可用的情况,甚至引发连锁反映导致整个系统崩溃。此时你需要使用的技术手段之一就是限流,当请求达到一定的并发数或速率,就进行等待、排队、降级、拒绝服务等。在限流时,常见的两种算法是漏桶和令牌桶算法算法,本文即对相关内容进行重点介绍。

    一、漏桶和令牌桶算法的概念

    漏桶算法(Leaky Bucket):主要目的是控制数据注入到网络的速率,平滑网络上的突发流量。漏桶算法提供了一种机制,通过它,突发流量可以被整形以便为网络提供一个稳定的流量。漏桶算法的示意图如下:
    在这里插入图片描述请求先进入到漏桶里,漏桶以一定的速度出水,当水请求过大会直接溢出,可以看出漏桶算法能强行限制数据的传输速率。

    令牌桶算法(Token Bucket):是网络流量整形(Traffic Shaping)和速率限制(Rate Limiting)中最常使用的一种算法。典型情况下,令牌桶算法用来控制发送到网络上的数据的数目,并允许突发数据的发送。令牌桶算法示意图如下所示:
    在这里插入图片描述大小固定的令牌桶可自行以恒定的速率源源不断地产生令牌。如果令牌不被消耗,或者被消耗的速度小于产生的速度,令牌就会不断地增多,直到把桶填满。后面再产生的令牌就会从桶中溢出。最后桶中可以保存的最大令牌数永远不会超过桶的大小。

    二、两种算法的区别

    两者主要区别在于“漏桶算法”能够强行限制数据的传输速率,而“令牌桶算法”在能够限制数据的平均传输速率外,还允许某种程度的突发传输。在“令牌桶算法”中,只要令牌桶中存在令牌,那么就允许突发地传输数据直到达到用户配置的门限,所以它适合于具有突发特性的流量。

    三、使用Guava的RateLimiter进行限流控制

    Guava是google提供的java扩展类库,其中的限流工具类RateLimiter采用的就是令牌桶算法。RateLimiter 从概念上来讲,速率限制器会在可配置的速率下分配许可证,如果必要的话,每个acquire() 会阻塞当前线程直到许可证可用后获取该许可证,一旦获取到许可证,不需要再释放许可证。通俗的讲RateLimiter会按照一定的频率往桶里扔令牌,线程拿到令牌才能执行,比如你希望自己的应用程序QPS不要超过1000,那么RateLimiter设置1000的速率后,就会每秒往桶里扔1000个令牌。例如我们需要处理一个任务列表,但我们不希望每秒的任务提交超过两个,此时可以采用如下方式:
    在这里插入图片描述

    有一点很重要,那就是请求的许可数从来不会影响到请求本身的限制(调用acquire(1) 和调用acquire(1000) 将得到相同的限制效果,如果存在这样的调用的话),但会影响下一次请求的限制,也就是说,如果一个高开销的任务抵达一个空闲的RateLimiter,它会被马上许可,但是下一个请求会经历额外的限制,从而来偿付高开销任务。注意:RateLimiter 并不提供公平性的保证。

    四、使用Semphore进行并发流控

    Java 并发库的Semaphore 可以很轻松完成信号量控制,Semaphore可以控制某个资源可被同时访问的个数,通过 acquire() 获取一个许可,如果没有就等待,而 release() 释放一个许可。单个信号量的Semaphore对象可以实现互斥锁的功能,并且可以是由一个线程获得了“锁”,再由另一个线程释放“锁”,这可应用于死锁恢复的一些场合。下面的Demo中申明了一个只有5个许可的Semaphore,而有20个线程要访问这个资源,通过acquire()和release()获取和释放访问许可:
    在这里插入图片描述在这里插入图片描述最后:进行限流控制还可以有很多种方法,针对不同的场景各有优劣,例如通过AtomicLong计数器控制、使用MQ消息队列进行流量消峰等等。

    接口限流算法总结
    背景

    曾经在一个大神的博客里看到这样一句话:在开发高并发系统时,有三把利器用来保护系统:缓存、降级和限流。那么何为限流呢?顾名思义,限流就是限制流量,就像你宽带包了1个G的流量,用完了就没了。通过限流,我们可以很好地控制系统的qps,从而达到保护系统的目的。本篇文章将会介绍一下常用的限流算法以及他们各自的特点。
    算法介绍
    计数器法

    计 数器法是限流算法里最简单也是最容易实现的一种算法。比如我们规定,对于A接口来说,我们1分钟的访问次数不能超过100个。那么我们可以这么做:在一开 始的时候,我们可以设置一个计数器counter,每当一个请求过来的时候,counter就加1,如果counter的值大于100并且该请求与第一个 请求的间隔时间还在1分钟之内,那么说明请求数过多;如果该请求与第一个请求的间隔时间大于1分钟,且counter的值还在限流范围内,那么就重置 counter,具体算法的示意图如下:

    2016-09-01_20:31:28.jpg

    具体的伪代码如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22

    public class CounterDemo {
    public long timeStamp = getNowTime();
    public int reqCount = 0;
    public final int limit = 100; // 时间窗口内最大请求数
    public final long interval = 1000; // 时间窗口ms
    public boolean grant() {
    long now = getNowTime();
    if (now < timeStamp + interval) {
    // 在时间窗口内
    reqCount++;
    // 判断当前时间窗口内是否超过最大请求控制数
    return reqCount <= limit;
    }
    else {
    timeStamp = now;
    // 超时后重置
    reqCount = 1;
    return true;
    }
    }
    }

    这个算法虽然简单,但是有一个十分致命的问题,那就是临界问题,我们看下图:

    2016-09-01_20:35:21.jpg

    从上图中我们可以看到,假设有一个恶意用户,他在0:59时,瞬间发送了100个请求,并且1:00又瞬间发送了100个请求,那么其实这个用户在 1秒里面,瞬间发送了200个请求。我们刚才规定的是1分钟最多100个请求,也就是每秒钟最多1.7个请求,用户通过在时间窗口的重置节点处突发请求, 可以瞬间超过我们的速率限制。用户有可能通过算法的这个漏洞,瞬间压垮我们的应用。

    聪明的朋友可能已经看出来了,刚才的问题其实是因为我们统计的精度太低。那么如何很好地处理这个问题呢?或者说,如何将临界问题的影响降低呢?我们可以看下面的滑动窗口算法。
    滑动窗口

    滑动窗口,又称rolling window。为了解决这个问题,我们引入了滑动窗口算法。如果学过TCP网络协议的话,那么一定对滑动窗口这个名词不会陌生。下面这张图,很好地解释了滑动窗口算法:

    2016-09-01_20:42:46.jpg

    在上图中,整个红色的矩形框表示一个时间窗口,在我们的例子中,一个时间窗口就是一分钟。然后我们将时间窗口进行划分,比如图中,我们就将滑动窗口 划成了6格,所以每格代表的是10秒钟。每过10秒钟,我们的时间窗口就会往右滑动一格。每一个格子都有自己独立的计数器counter,比如当一个请求 在0:35秒的时候到达,那么0:30~0:39对应的counter就会加1。

    那么滑动窗口怎么解决刚才的临界问题的呢?我们可以看上图,0:59到达的100个请求会落在灰色的格子中,而1:00到达的请求会落在橘黄色的格 子中。当时间到达1:00时,我们的窗口会往右移动一格,那么此时时间窗口内的总请求数量一共是200个,超过了限定的100个,所以此时能够检测出来触 发了限流。

    我再来回顾一下刚才的计数器算法,我们可以发现,计数器算法其实就是滑动窗口算法。只是它没有对时间窗口做进一步地划分,所以只有1格。

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

    漏桶算法,又称leaky bucket。为了理解漏桶算法,我们看一下维基百科上的对于该算法的示意图:

    2016-09-02_09:57:32.jpg

    从图中我们可以看到,整个算法其实十分简单。首先,我们有一个固定容量的桶,有水流进来,也有水流出去。对于流进来的水来说,我们无法预计一共有多 少水会流进来,也无法预计水流的速度。但是对于流出去的水来说,这个桶可以固定水流出的速率。而且,当桶满了之后,多余的水将会溢出。

    我们将算法中的水换成实际应用中的请求,我们可以看到漏桶算法天生就限制了请求的速度。当使用了漏桶算法,我们可以保证接口会以一个常速速率来处理请求。所以漏桶算法天生不会出现临界问题。具体的伪代码实现如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22

    public class LeakyDemo {
    public long timeStamp = getNowTime();
    public int capacity; // 桶的容量
    public int rate; // 水漏出的速度
    public int water; // 当前水量(当前累积请求数)
    public boolean grant() {
    long now = getNowTime();
    water = max(0, water - (now - timeStamp) * rate); // 先执行漏水,计算剩余水量
    timeStamp = now;
    if ((water + 1) < capacity) {
    // 尝试加水,并且水还未满
    water += 1;
    return true;
    }
    else {
    // 水满,拒绝加水
    return false;
    }
    }
    }
    令牌桶算法

    令牌桶算法,又称token bucket。为了理解该算法,我们再来看一下维基百科上对该算法的示意图:

    2016-09-02_10:10:24.jpg

    从图中我们可以看到,令牌桶算法比漏桶算法稍显复杂。首先,我们有一个固定容量的桶,桶里存放着令牌(token)。桶一开始是空的,token以 一个固定的速率r往桶里填充,直到达到桶的容量,多余的令牌将会被丢弃。每当一个请求过来时,就会尝试从桶里移除一个令牌,如果没有令牌的话,请求无法通 过。

    具体的伪代码实现如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22

    public class TokenBucketDemo {
    public long timeStamp = getNowTime();
    public int capacity; // 桶的容量
    public int rate; // 令牌放入速度
    public int tokens; // 当前令牌数量
    public boolean grant() {
    long now = getNowTime();
    // 先添加令牌
    tokens = min(capacity, tokens + (now - timeStamp) * rate);
    timeStamp = now;
    if (tokens < 1) {
    // 若不到1个令牌,则拒绝
    return false;
    }
    else {
    // 还有令牌,领取令牌
    tokens -= 1;
    return true;
    }
    }
    }
    相关变种

    若仔细研究算法,我们会发现我们默认从桶里移除令牌是不需要耗费时间的。如果给移除令牌设置一个延时时间,那么实际上又采用了漏桶算法的思路。Google的guava库下的SmoothWarmingUp类就采用了这个思路。
    临界问题

    我 们再来考虑一下临界问题的场景。在0:59秒的时候,由于桶内积满了100个token,所以这100个请求可以瞬间通过。但是由于token是以较低的 速率填充的,所以在1:00的时候,桶内的token数量不可能达到100个,那么此时不可能再有100个请求通过。所以令牌桶算法可以很好地解决临界问 题。下图比较了计数器(左)和令牌桶算法(右)在临界点的速率变化。我们可以看到虽然令牌桶算法允许突发速率,但是下一个突发速率必须要等桶内有足够的 token后才能发生:

    2016-09-02_14:40:58.jpg
    总结
    计数器 VS 滑动窗口

    计数器算法是最简单的算法,可以看成是滑动窗口的低精度实现。滑动窗口由于需要存储多份的计数器(每一个格子存一份),所以滑动窗口在实现上需要更多的存储空间。也就是说,如果滑动窗口的精度越高,需要的存储空间就越大。
    漏桶算法 VS 令牌桶算法

    漏桶算法和令牌桶算法最明显的区别是令牌桶算法允许流量一定程度的突发。因为默认的令牌桶算法,取走token是不需要耗费时间的,也就是说,假设桶内有100个token时,那么可以瞬间允许100个请求通过。

    令牌桶算法由于实现简单,且允许某些流量的突发,对用户友好,所以被业界采用地较多。当然我们需要具体情况具体分析,只有最合适的算法,没有最优的算法。

    聊聊高并发系统之限流特技

    在开发高并发系统时有三把利器用来保护系统:缓存、降级和限流。缓存的目的是提升系统访问速度和增大系统能处理的容量,可谓是抗高并发流量的银弹;而降级是当服务出问题或者影响到核心流程的性能则需要暂时屏蔽掉,待高峰或者问题解决后再打开;而有些场景并不能用缓存和降级来解决,比如稀缺资源(秒杀、抢购)、写服务(如评论、下单)、频繁的复杂查询(评论的最后几页),因此需有一种手段来限制这些场景的并发/请求量,即限流。

    限流的目的是通过对并发访问/请求进行限速或者一个时间窗口内的的请求进行限速来保护系统,一旦达到限制速率则可以拒绝服务(定向到错误页或告知资源没有了)、排队或等待(比如秒杀、评论、下单)、降级(返回兜底数据或默认数据,如商品详情页库存默认有货)。

    一般开发高并发系统常见的限流有:限制总并发数(比如数据库连接池、线程池)、限制瞬时并发数(如nginx的limit_conn模块,用来限制瞬时并发连接数)、限制时间窗口内的平均速率(如Guava的RateLimiter、nginx的limit_req模块,限制每秒的平均速率);其他还有如限制远程接口调用速率、限制MQ的消费速率。另外还可以根据网络连接数、网络流量、CPU或内存负载等来限流。

    先有缓存这个银弹,后有限流来应对618、双十一高并发流量,在处理高并发问题上可以说是如虎添翼,不用担心瞬间流量导致系统挂掉或雪崩,最终做到有损服务而不是不服务;限流需要评估好,不可乱用,否则会正常流量出现一些奇怪的问题而导致用户抱怨。

    在实际应用时也不要太纠结算法问题,因为一些限流算法实现是一样的只是描述不一样;具体使用哪种限流技术还是要根据实际场景来选择,不要一味去找最佳模式,白猫黑猫能解决问题的就是好猫。

    因在实际工作中遇到过许多人来问如何进行限流,因此本文会详细介绍各种限流手段。那么接下来我们从限流算法、应用级限流、分布式限流、接入层限流来详细学习下限流技术手段。

    限流算法

    常见的限流算法有:令牌桶、漏桶。计数器也可以进行粗暴限流实现。

    令牌桶算法

    令牌桶算法是一个存放固定容量令牌的桶,按照固定速率往桶里添加令牌。令牌桶算法的描述如下:

    假设限制2r/s,则按照500毫秒的固定速率往桶中添加令牌;
    
    桶中最多存放b个令牌,当桶满时,新添加的令牌被丢弃或拒绝;
    
    当一个n个字节大小的数据包到达,将从桶中删除n个令牌,接着数据包被发送到网络上;
    
    如果桶中的令牌不足n个,则不会删除令牌,且该数据包将被限流(要么丢弃,要么缓冲区等待)。
    

    在这里插入图片描述漏桶算法

    漏桶作为计量工具(The Leaky Bucket Algorithm as a Meter)时,可以用于流量整形(Traffic Shaping)和流量控制(TrafficPolicing),漏桶算法的描述如下:

    一个固定容量的漏桶,按照常量固定速率流出水滴;
    
    如果桶是空的,则不需流出水滴;
    
    可以以任意速率流入水滴到漏桶;
    
    如果流入水滴超出了桶的容量,则流入的水滴溢出了(被丢弃),而漏桶容量是不变的。
    

    在这里插入图片描述令牌桶和漏桶对比:

    令牌桶是按照固定速率往桶中添加令牌,请求是否被处理需要看桶中令牌是否足够,当令牌数减为零时则拒绝新的请求;
    
    漏桶则是按照常量固定速率流出请求,流入请求速率任意,当流入的请求数累积到漏桶容量时,则新流入的请求被拒绝;
    
    令牌桶限制的是平均流入速率(允许突发请求,只要有令牌就可以处理,支持一次拿3个令牌,4个令牌),并允许一定程度突发流量;
    
    漏桶限制的是常量流出速率(即流出速率是一个固定常量值,比如都是1的速率流出,而不能一次是1,下次又是2),从而平滑突发流入速率;
    
    令牌桶允许一定程度的突发,而漏桶主要目的是平滑流入速率;
    
    两个算法实现可以一样,但是方向是相反的,对于相同的参数得到的限流效果是一样的。
    

    另外有时候我们还使用计数器来进行限流,主要用来限制总并发数,比如数据库连接池、线程池、秒杀的并发数;只要全局总请求数或者一定时间段的总请求数设定的阀值则进行限流,是简单粗暴的总数量限流,而不是平均速率限流。

    到此基本的算法就介绍完了,接下来我们首先看看应用级限流。

    应用级限流

    限流总并发/连接/请求数

    对于一个应用系统来说一定会有极限并发/请求数,即总有一个TPS/QPS阀值,如果超了阀值则系统就会不响应用户请求或响应的非常慢,因此我们最好进行过载保护,防止大量请求涌入击垮系统。

    如果你使用过Tomcat,其Connector 其中一种配置有如下几个参数:

    acceptCount:如果Tomcat的线程都忙于响应,新来的连接会进入队列排队,如果超出排队大小,则拒绝连接;

    maxConnections: 瞬时最大连接数,超出的会排队等待;

    maxThreads:Tomcat能启动用来处理请求的最大线程数,如果请求处理量一直远远大于最大线程数则可能会僵死。

    详细的配置请参考官方文档。另外如Mysql(如max_connections)、Redis(如tcp-backlog)都会有类似的限制连接数的配置。

    限流总资源数

    如果有的资源是稀缺资源(如数据库连接、线程),而且可能有多个系统都会去使用它,那么需要限制应用;可以使用池化技术来限制总资源数:连接池、线程池。比如分配给每个应用的数据库连接是100,那么本应用最多可以使用100个资源,超出了可以等待或者抛异常。

    限流某个接口的总并发/请求数

    如果接口可能会有突发访问情况,但又担心访问量太大造成崩溃,如抢购业务;这个时候就需要限制这个接口的总并发/请求数总请求数了;因为粒度比较细,可以为每个接口都设置相应的阀值。可以使用Java中的AtomicLong进行限流:

    try {
    if(atomic.incrementAndGet() > 限流数) {
    //拒绝请求
    }
    //处理请求
    } finally {
    atomic.decrementAndGet();
    }

    适合对业务无损的服务或者需要过载保护的服务进行限流,如抢购业务,超出了大小要么让用户排队,要么告诉用户没货了,对用户来说是可以接受的。而一些开放平台也会限制用户调用某个接口的试用请求量,也可以用这种计数器方式实现。这种方式也是简单粗暴的限流,没有平滑处理,需要根据实际情况选择使用;

    限流某个接口的时间窗请求数

    即一个时间窗口内的请求数,如想限制某个接口/服务每秒/每分钟/每天的请求数/调用量。如一些基础服务会被很多其他系统调用,比如商品详情页服务会调用基础商品服务调用,但是怕因为更新量比较大将基础服务打挂,这时我们要对每秒/每分钟的调用量进行限速;一种实现方式如下所示:

    LoadingCache<Long, AtomicLong> counter =
    CacheBuilder.newBuilder()
    .expireAfterWrite(2, TimeUnit.SECONDS)
    .build(new CacheLoader<Long, AtomicLong>() {
    @Override
    public AtomicLong load(Long seconds) throws Exception {
    return new AtomicLong(0);
    }
    });
    long limit = 1000;
    while(true) {
    //得到当前秒
    long currentSeconds = System.currentTimeMillis() / 1000;
    if(counter.get(currentSeconds).incrementAndGet() > limit) {
    System.out.println(“限流了:” + currentSeconds);
    continue;
    }
    //业务处理
    }

    我们使用Guava的Cache来存储计数器,过期时间设置为2秒(保证1秒内的计数器是有的),然后我们获取当前时间戳然后取秒数来作为KEY进行计数统计和限流,这种方式也是简单粗暴,刚才说的场景够用了。

    平滑限流某个接口的请求数

    之前的限流方式都不能很好地应对突发请求,即瞬间请求可能都被允许从而导致一些问题;因此在一些场景中需要对突发请求进行整形,整形为平均速率请求处理(比如5r/s,则每隔200毫秒处理一个请求,平滑了速率)。这个时候有两种算法满足我们的场景:令牌桶和漏桶算法。Guava框架提供了令牌桶算法实现,可直接拿来使用。

    Guava RateLimiter提供了令牌桶算法实现:平滑突发限流(SmoothBursty)和平滑预热限流(SmoothWarmingUp)实现。

    SmoothBursty

    RateLimiter limiter = RateLimiter.create(5);
    System.out.println(limiter.acquire());
    System.out.println(limiter.acquire());
    System.out.println(limiter.acquire());
    System.out.println(limiter.acquire());
    System.out.println(limiter.acquire());
    System.out.println(limiter.acquire());

    将得到类似如下的输出:

    0.0

    0.198239

    0.196083

    0.200609

    0.199599

    0.19961

    1、RateLimiter.create(5) 表示桶容量为5且每秒新增5个令牌,即每隔200毫秒新增一个令牌;

    2、limiter.acquire()表示消费一个令牌,如果当前桶中有足够令牌则成功(返回值为0),如果桶中没有令牌则暂停一段时间,比如发令牌间隔是200毫秒,则等待200毫秒后再去消费令牌(如上测试用例返回的为0.198239,差不多等待了200毫秒桶中才有令牌可用),这种实现将突发请求速率平均为了固定请求速率。

    再看一个突发示例:
    RateLimiter limiter = RateLimiter.create(5);
    System.out.println(limiter.acquire(5));
    System.out.println(limiter.acquire(1));
    System.out.println(limiter.acquire(1));

    将得到类似如下的输出:

    0.0

    0.98745

    0.183553

    0.199909

    limiter.acquire(5)表示桶的容量为5且每秒新增5个令牌,令牌桶算法允许一定程度的突发,所以可以一次性消费5个令牌,但接下来的limiter.acquire(1)将等待差不多1秒桶中才能有令牌,且接下来的请求也整形为固定速率了。
    RateLimiter limiter = RateLimiter.create(5);
    System.out.println(limiter.acquire(10));
    System.out.println(limiter.acquire(1));
    System.out.println(limiter.acquire(1));

    将得到类似如下的输出:

    0.0

    1.997428

    0.192273

    0.200616

    同上边的例子类似,第一秒突发了10个请求,令牌桶算法也允许了这种突发(允许消费未来的令牌),但接下来的limiter.acquire(1)将等待差不多2秒桶中才能有令牌,且接下来的请求也整形为固定速率了。

    接下来再看一个突发的例子:
    RateLimiter limiter = RateLimiter.create(2);
    System.out.println(limiter.acquire());
    Thread.sleep(2000L);
    System.out.println(limiter.acquire());
    System.out.println(limiter.acquire());
    System.out.println(limiter.acquire());
    System.out.println(limiter.acquire());
    System.out.println(limiter.acquire());

    将得到类似如下的输出:

    0.0

    0.0

    0.0

    0.0

    0.499876

    0.495799

    1、创建了一个桶容量为2且每秒新增2个令牌;

    2、首先调用limiter.acquire()消费一个令牌,此时令牌桶可以满足(返回值为0);

    3、然后线程暂停2秒,接下来的两个limiter.acquire()都能消费到令牌,第三个limiter.acquire()也同样消费到了令牌,到第四个时就需要等待500毫秒了。

    此处可以看到我们设置的桶容量为2(即允许的突发量),这是因为SmoothBursty中有一个参数:最大突发秒数(maxBurstSeconds)默认值是1s,突发量/桶容量=速率*maxBurstSeconds,所以本示例桶容量/突发量为2,例子中前两个是消费了之前积攒的突发量,而第三个开始就是正常计算的了。令牌桶算法允许将一段时间内没有消费的令牌暂存到令牌桶中,留待未来使用,并允许未来请求的这种突发。

    SmoothBursty通过平均速率和最后一次新增令牌的时间计算出下次新增令牌的时间的,另外需要一个桶暂存一段时间内没有使用的令牌(即可以突发的令牌数)。另外RateLimiter还提供了tryAcquire方法来进行无阻塞或可超时的令牌消费。

    因为SmoothBursty允许一定程度的突发,会有人担心如果允许这种突发,假设突然间来了很大的流量,那么系统很可能扛不住这种突发。因此需要一种平滑速率的限流工具,从而系统冷启动后慢慢的趋于平均固定速率(即刚开始速率小一些,然后慢慢趋于我们设置的固定速率)。Guava也提供了SmoothWarmingUp来实现这种需求,其可以认为是漏桶算法,但是在某些特殊场景又不太一样。

    SmoothWarmingUp创建方式:RateLimiter.create(doublepermitsPerSecond, long warmupPeriod, TimeUnit unit)

    permitsPerSecond表示每秒新增的令牌数,warmupPeriod表示在从冷启动速率过渡到平均速率的时间间隔。

    示例如下:
    RateLimiter limiter = RateLimiter.create(5, 1000, TimeUnit.MILLISECONDS);
    for(int i = 1; i < 5;i++) {
    System.out.println(limiter.acquire());
    }
    Thread.sleep(1000L);
    for(int i = 1; i < 5;i++) {
    System.out.println(limiter.acquire());
    }

    将得到类似如下的输出:

    0.0

    0.51767

    0.357814

    0.219992

    0.199984

    0.0

    0.360826

    0.220166

    0.199723

    0.199555

    速率是梯形上升速率的,也就是说冷启动时会以一个比较大的速率慢慢到平均速率;然后趋于平均速率(梯形下降到平均速率)。可以通过调节warmupPeriod参数实现一开始就是平滑固定速率。

    到此应用级限流的一些方法就介绍完了。假设将应用部署到多台机器,应用级限流方式只是单应用内的请求限流,不能进行全局限流。因此我们需要分布式限流和接入层限流来解决这个问题。

    分布式限流

    分布式限流最关键的是要将限流服务做成原子化,而解决方案可以使使用redis+lua或者nginx+lua技术进行实现,通过这两种技术可以实现的高并发和高性能。

    首先我们来使用redis+lua实现时间窗内某个接口的请求数限流,实现了该功能后可以改造为限流总并发/请求数和限制总资源数。Lua本身就是一种编程语言,也可以使用它实现复杂的令牌桶或漏桶算法。

    redis+lua实现中的lua脚本:
    local key = KEYS[1] --限流KEY(一秒一个)
    local limit = tonumber(ARGV[1]) --限流大小
    local current = tonumber(redis.call(“INCRBY”, key, “1”)) --请求数+1
    if current > limit then --如果超出限流大小
    return 0
    elseif current == 1 then --只有第一次访问需要设置2秒的过期时间
    redis.call(“expire”, key,“2”)
    end
    return 1

    如上操作因是在一个lua脚本中,又因Redis是单线程模型,因此是线程安全的。如上方式有一个缺点就是当达到限流大小后还是会递增的,可以改造成如下方式实现:
    local key = KEYS[1] --限流KEY(一秒一个)
    local limit = tonumber(ARGV[1]) --限流大小
    local current = tonumber(redis.call(‘get’, key) or “0”)
    if current + 1 > limit then --如果超出限流大小
    return 0
    else --请求数+1,并设置2秒过期
    redis.call(“INCRBY”, key,“1”)
    redis.call(“expire”, key,“2”)
    return 1
    end

    如下是Java中判断是否需要限流的代码:
    public static boolean acquire() throws Exception {
    String luaScript = Files.toString(new File(“limit.lua”), Charset.defaultCharset());
    Jedis jedis = new Jedis(“192.168.147.52”, 6379);
    String key = “ip:” + System.currentTimeMillis()/ 1000; //此处将当前时间戳取秒数
    Stringlimit = “3”; //限流大小
    return (Long)jedis.eval(luaScript,Lists.newArrayList(key), Lists.newArrayList(limit)) == 1;
    }

    因为Redis的限制(Lua中有写操作不能使用带随机性质的读操作,如TIME)不能在Redis Lua中使用TIME获取时间戳,因此只好从应用获取然后传入,在某些极端情况下(机器时钟不准的情况下),限流会存在一些小问题。

    使用Nginx+Lua实现的Lua脚本:
    local locks = require “resty.lock”
    local function acquire()
    local lock =locks:new(“locks”)
    local elapsed, err =lock:lock(“limit_key”) --互斥锁
    local limit_counter =ngx.shared.limit_counter --计数器
    local key = “ip:” …os.time()
    local limit = 5 --限流大小
    local current =limit_counter:get(key)

    if current ~= nil and current + 1> limit then --如果超出限流大小
        lock:unlock()
        return 0
    end
    if current == nil then
        limit_counter:set(key, 1, 1) --第一次需要设置过期时间,设置key的值为1,过期时间为1秒
    else
        limit_counter:incr(key, 1) --第二次开始加1即可
    end
    lock:unlock()
    return 1
    

    end
    ngx.print(acquire())

    展开全文
  • Token Bucket 令牌桶算法

    千次阅读 2018-10-16 23:12:51
    令牌桶算法是网络流量整形(Traffic Shaping)和速率限制(Rate Limiting)中最常使用的一种算法。典型情况下,令牌桶算法用来控制发送到网络上的数据的数目,并允许突发数据的发送。 令牌桶这种控制机制基于令牌桶...

    令牌桶算法是网络流量整形(Traffic Shaping)和速率限制(Rate Limiting)中最常使用的一种算法。典型情况下,令牌桶算法用来控制发送到网络上的数据的数目,并允许突发数据的发送。

    令牌桶这种控制机制基于令牌桶中是否存在令牌来指示什么时候可以发送流量。令牌桶中的每一个令牌都代表一个字节。如果令牌桶中存在令牌,则允许发送流量;而如果令牌桶中不存在令牌,则不允许发送流量。因此,如果突发门限被合理地配置并且令牌桶中有足够的令牌,那么流量就可以以峰值速率发送。

     

    令牌桶算法可以在概念上理解如下:

    • 若用户配置的平均发送速率为r,每1 / R 秒令牌都会添加到存储桶中。
    • 桶最多可以容纳b令牌。如果令牌在存储桶已满时到达,则将其丢弃。
    • n个字节的包(网络层PDU)到达时,
      • 如果存储桶中至少有n个令牌,则从存储桶中删除n个令牌,并将数据包发送到网络。
      • 如果可用的令牌少于n个,则不会从存储桶中删除令牌,并且该包在流量限制之外。



    该算法的实施者在平台上缺乏每次向桶中添加单个令牌所需的时钟分辨率 1 / R秒可能想要考虑另一种配方。鉴于能够每S毫秒更新令牌桶,每S毫秒增加一个令牌数=(R * S)/ 1000

    平均费率编辑]

    从长远来看,符合数据包的输出受令牌速率的限制, {\ displaystyle r}[R

    突发大小编辑]

    让 {\ displaystyle M}中号 是最大可能的传输速率,以字节/秒为单位。

    然后T _ {{\ text {max}}} = {\ begin {cases} b /(Mr)&{\ text {if}} r <M \\\ infty&{\ text {otherwise}} \ end {cases} } 是最大突发时间,即速率的时间 {\ displaystyle M}中号 充分利用。

    因此,最大突发大小 {\ displaystyle B _ {\ text {max}} = T _ {\ text {max}} * M}

     


    算法允许最长b个字节的突发,但从长期运行结果看,数据包的速率被限制成常量r。对于在流量限制外的数据包可以以不同的方式处理:

      它们可以被丢弃; 

      它们可以排放在队列中以便当令牌桶中累积了足够多的令牌时再传输; 

      它们可以继续发送,但需要做特殊标记,网络过载的时候将这些特殊标记的包丢弃。 

      注意:令牌桶算法不能与另外一种常见算法“漏桶算法leaky Bucket)”相混淆。这两种算法的主要区别在于“漏桶算法”能够强行限制数据的传输速率,而“令牌桶算法”在能够限制数据的平均传输数据外,还允许某种程度的突发传输。在“令牌桶算法”中,只要令牌桶中存在令牌,那么就允许突发地传输数据直到达到用户配置的门限,因此它适合于具有突发特性的流量。

    详解

    令牌桶原理

     

    QoS中的流量监管(Traffic Policing)就是对流量进行控制,通过监督进入网络端口的流量速率,对超出部分的流量进行“惩罚”(这个惩罚可以是丢弃、也可是延迟发送),使进入端口的流量被限制在一个合理的范围之内。例如可以限制HTTP报文不能占用超过50%的网络带宽,否则QoS流量监管功能可以选择丢弃报文,或重新配置报文的优先级

    QoS流量监管功能是采用令牌桶(Token-Bucket)机制进行的。这里的“令牌桶”是指网络设备的内部存储池,而“令牌”则是指以给定速率填充令牌桶的虚拟信息包。可以这么简单理解,“令牌桶”可以理解为一个水桶,而“令牌”则可以理解为通过一根水管流到水桶中的水。

    交换机在接收每个帧时都将添加一个令牌到令牌桶中,但这个令牌桶底部有一个孔,不断地按你指定作为平均通信速率(单位为b/s)的速度领出令牌(也就是从桶中删除令牌的意思)。相当于一个水桶的上边连接一根进水的水管,而下边又连接一根连接到用水的地方的出水管。在每次向令牌桶中添加新的令牌包时,交换机都会检查令牌桶中是否有足够容量(也就是在要向桶水加水前,先要检查是桶内否已满了),如果没有足够的空间,包将被标记为不符规定的包,这时在包上将发生指定监管器中规定的行为(丢弃或标记),就相当于如果当前水桶满了,但上边水管的水还是来了,这时要么就是让这些水白白流到桶外,要么把这些水用其它容器先装起来,等水桶中不再满水时再倒进去,供用户使用。整个令牌桶的基本工作原理可以用上图来表示

    令牌桶填满的时间长短是由令牌桶深度(也就是容量,单位为bit,类似于水桶的的深度)、令牌漏出速率(类似桶下边接的水管的水速)和超过平均速率的突发通信流(类似于上桶上边水管突发的急速水流)持续的时间三个方面共同决定的。 令牌桶的大小利用突发时长上限乘以点对点传输时的帧数限制得出(也就类似突发水流持续的时间*突发水流的流速)。如果突发时间比较短,令牌桶不会溢出,在通信流上不会发生行为。但是,如果突发时间比较长,并且速率比较高,令牌桶将溢出,这时将对突发过程中的帧采取相应的流监管策略行为(也就是在水桶满水后对溢出的水的处理方法)。

    在令牌桶处理包的行为方面,RFC中定义了两种令牌桶算法——单速率三色标记(single rate threecolor marker,srTCM)算法和双速率三色标记(two rate threecolor marker,trTCM)算法,其评估结果都是为包打上红、黄、绿三色标记(所以称为“三色标记”,有关这些颜色的具体含义将在具体算法中介绍)。QoS会根据包的颜色,设置包的丢弃优先级,其中单速率三色标记比较关心包尺寸的突发,而双速率三色标记则关注速率上的突发,两种算法都可工作于色盲模式和非色盲模式(具体在下面介绍)。下面分别介绍这两种算法原理。

    1. 单速率三色标记
    这里首先要理解“单速率”是什么意思,那就是算法中的两个令牌桶有同样的承诺信息速率(CIR),也就是具有相同平均访问速率。这两个令牌桶分别是正常使用的令牌桶(也就是下面将要说到的C桶)和超出令牌桶容量的突发令牌桶(也就是下面将要说到的E桶),可以理解为两个水桶,一个是正常使用的水桶,另一个是用来当正常使用的水桶满后装多余的水的水桶。下面具体解释单速率三色标记算法原理。

    单速率三色标记(srTCM)算法关注的是数据包的突发尺寸,数据包的色标记评估依据以下3个参数:承诺信息速率(CommittedInformation Rate,CIR)、承诺突发尺寸(Committed BurstSize,CBS)和超额突发尺寸(Excess Burst Size,EBS)。CIR是指向令牌桶中填充令牌的平均速率,即允许的通信流平均速度;CBS是指每次突发所允许的最大的流量尺寸,也相当于允许的最大取令牌的速率,等于桶的容量(最大时就是一个包就可以全部领取桶中的全部令牌)。EBS是指每次突发允许超出CBS的最大流量尺寸。CBS和EBS的单位都是bit(位)。

    单速率三色机制采用双桶结构:C桶和E桶(之所以用这两个字母来表示,为的就是与前面说的CBS和EBS两种速率的头个字母一致,便于描述),且两个令牌桶的CIR一样。C令牌桶中任何未用的令牌都被放入E令牌桶中,用做以后临时超过CIR的突发流量的令牌;另外,当C令牌桶满时,超出的令牌也都会放在E令牌桶中。

    Tc和Te分别表示C令牌桶和E令牌桶中的令牌数,也就是桶中当前的容量(单位也为bit),两桶的总容量分别为CBS和EBS,也就是对应前面介绍的承诺突发尺寸和超额突发尺寸,最初它们都是满的,即Tc和Te初始值分别等于CBS和EBS。正常情况下,不会使用第二个令牌桶(也就是E桶),而是把任何CBS(也就是C桶)中未使用的令牌都放入E桶中,只有当C令牌桶满后,后面来的令牌才放到E令牌桶中,为可能出现的突发数据提供信用令牌(也就是经过允许的令牌)。

    在这种单速率三色标记算法中,两个令牌桶中令牌的添加是按照相同的CIR速率进行的。即每隔1/CIR时间添加一个令牌。添加的顺序是先添加C桶再添加E桶,当两个令牌桶中的令牌都满时,再产生的令牌就会被丢弃。至于在发送数据包时,令牌的使用IEEE又定义了三种颜色(分别为红色、黄色和绿色)以及两种模式:色盲(color-blind)模式和感色(color-aware)模式,默认为色盲模式。三种颜色的功能与我们日常生活中的交通指示灯中的三种颜色类似,红色表示违规数据,直接丢弃,黄色表示数据包虽然违法,但不直接丢弃,而是延迟发送,绿争为合法数据包,直接发送。

    在色盲(color-blind)模式下是假设包都是没有经过“着色”处理的(不辨别包中原来标记的颜色),是根据包长度来确定包被标记的颜色。现假设到达的包长度为B(单位为bit)。若包长度B小于C桶中的令牌数Tc(也就是C桶中的令牌数足够该包发送所需),则包被标记为绿色,表示包符合要求,包发送后C桶中的令牌数Tc减少B。如果TcTe,标记为红色,表示是违反规定的包,直接丢弃,两令牌桶中的总令牌数都不减少。

    在感色(color-aware)模式下是假设包在此之前已经过“着色”处理(会辨别包中原来标记的颜色),如果包已被标记为绿色,或包长度BTe,则包被标记为红色,Tc和Te都不减少。

    2. 双速率三色算法

    这里同样首先要稿清楚“双速率”是什么意思,它是指该算法中两个令牌桶中的CIR速率不同,存在两个令牌填充速率。

    IETF的双速率三色标记(trTCM)算法主要是根据四种流量参数来评估:CIR、CBS、峰值信息速率(Peak InformationRate,PIR),峰值突发尺寸(Peak Burst Size,PBS)。CIR和CBS参数与单速率三色算法中的含义相同,PIR就是允许的最大突发信息传输速率,当然它的值肯定不会小于CIR的;PBS是允许的最大突发信息尺寸,它的值也不会小于CBS。

    与单速率三色标记算法不同,双速率三色标记算法中的两个令牌桶是C桶和P桶(不是C桶和E桶),但它们的令牌填充速率是不同的,C桶填充速率为CIR,P桶为PIR;两桶的容量分别为CBS和PBS(之所以用C桶和P桶表示也是基于方便描述,因为表示不同速率的参数与对应桶的容量参数相同,第一个字母对应为C,或者P)。用Tc和Tp表示两桶中的令牌数目,初始状态时两桶是满的,即Tc和Tp初始值分别等于CBS和PBS。

    双速率三色标记算法关注的是速率的突发,但它不像单速率三色标记算法那样把第一个桶中未使用的令牌放到第二个桶中,而是使用两个独立的令牌桶。第一个令牌桶为PIR,大小为PBS,第二个令牌桶为CIR,大小为CBS。数据的测量是先比较PIR,然后再比较CIR。也就是在双速率三色标记中,首先判断的是数据发送速率是否符合规定的突发要求,而不是正常情况下的色标方法。

    双速率三色标记算法也有色盲模式和感色模式两种。

    在色盲模式下,当包速率大于PIR,此时未超过Tp+Tc部分的包会分别从P桶和C桶中获取令牌,而且从P桶中获取令牌的部分包被标记为黄色,从C桶中获取令牌的部分包被标记为绿色,超过Tp+Tc部分无法得到令牌的包被标记为红色;当包速率小于PIR,而大于CIR时,包可以得到令牌,但超过Tc部分的包将从P桶中获取令牌,此时这部分包都被标记为黄色,而从C桶中获取令牌的包被标记为绿色;当包速率小于CIR时,包所需令牌数不会超过Tc,只需从C桶中获取令牌,包被标记为绿色。

    在感色模式下,如果包已被标记为红色,或者超过Tp+Tc部分无法得到令牌的包,被标记为红色;如果标记为黄色,或者超过Tc但未超过Tp部分包记为黄色;如果包被标记为绿,或者未超过Tc部分包,被标记为绿色。
     

    参考维基百科与互动百科与https://blog.csdn.net/laoj1228/article/details/53809334

    展开全文
  • 工作中对外提供的API 接口设计都要考虑限流,如果不考虑限流,会成系统的连锁反应,轻者响应缓慢,重者系统宕机,整个业务线崩溃,如何应对这种情况呢,我们可以对请求进行引流或者直接拒绝等操作,保持系统的可用性...
  • 漏桶算法和令牌桶算法

    万次阅读 2016-11-13 22:23:26
    一、问题描述  某天A君突然发现自己的接口请求量突然涨到之前的10倍,没多久该接口几乎不可使用,并引发连锁反应导致整个系统崩溃。如何应对这种情况呢?生活给了我们答案:比如老式电闸都安装了保险丝,一旦有...
  • 令牌桶算法总结

    千次阅读 2018-11-02 16:56:30
    昨天CodeReview的时候看到同时使用RateLimiter这个类用作QPS访问限制.学习一下这个类. RateLimiter是Guava的concurrent包下的一个用于限制访问频率的类. 1.限流 ...每个API接口都是有访问上限的,当访问频率或者...
  • 漏桶算法和令牌桶算法的区别

    千次阅读 2019-07-10 10:31:36
    漏桶算法与令牌桶算法在表面看起来类似,很容易将两者混淆。但事实上,这两者具有截然不同的特性,且为不同的目的而使用。漏桶算法与令牌桶算法的区别在于:l漏桶算法能够强行限制数据的传输速率。l令牌桶算法能够在...
  • 令牌桶算法限流

    万次阅读 2016-04-23 21:36:37
    今天观看QCon大会讲述了阿里线上管控体系,其中主要使用了令牌桶算法来实现限流的目的。表示非常好奇,故此学习一下什么是令牌桶算法。 1. 简介 令牌桶算法最初来源于计算机网络。在网络传输数据时,为了防止网络...
  • 架构方案(5) 漏桶算法&令牌桶算法

    万次阅读 2019-05-01 17:18:58
    背景 每一个对外提供的API接口都是需要做流量控制的,不然会导致系统直接崩溃。很简单的例子,和保险...既然要限流,就得提到限流算法了,一般有漏桶算法和令牌桶算法两种限流算法。 漏桶算法 漏桶算法(Leaky Bucke...
  • Java漏桶算法和令牌桶算法

    千次阅读 2018-09-06 18:17:09
    https://blog.csdn.net/charleslei/article/details/53152883
  • 在大数据量高并发访问时,...在限流时,常见的两种算法是漏桶和令牌桶算法算法,本文即对相关内容进行重点介绍。一、漏桶和令牌桶算法的概念漏桶算法(Leaky Bucket):主要目的是控制数据注入到网络的速率,平滑网络上
  • QoS令牌桶工作原理

    万次阅读 2012-04-24 10:11:18
    那就是QoS的令牌桶机制了。下面是在笔者刚刚出版的《Cisco/H3C交换机高级配置与管理技术手册》一书中,经过笔者充分理解后的全面诠释,大家看一下是否可以理解。http://book.360buy.com/10959197.html 6.3.3 QoS...
  • 流量整形通常使用缓冲区和令牌桶来完成,当报文的发送速度过快时,首先在缓冲区进行缓存,在令牌桶的控制下再均匀地发送这些被缓冲的文。 流量整形的核心算法有以下两种,具体采用的技术为GTS(Generic Traffic ...
  • QoS技术中令牌桶算法实现方式比较

    万次阅读 2014-11-20 12:26:21
    [摘要] 令牌桶算法是目前IP QoS中最常采用的一种流量测量方法,广泛应用于约定访问速率技术、通用流量整形技术以及物理接口总速率限制等技术中。IETF RFC 建议规范了单速率三色标记和双速率三色标记两种令牌桶...
  • 高并发之限流算法

    万次阅读 2020-10-21 10:19:11
    限流算法 在我们的实际的生产当中存在这样的业务场景:短时间有大量的请求涌入造成了系统的崩溃。针对这种问题我们会采用一种服务降级的方式来保证核心服务可以正常运行。 一般来说服务降级分为两种: 故障降级:当...
  • qos令牌桶(Token Bucket)算法解析

    万次阅读 2014-03-05 10:55:27
    QoS中的流量监管(Traffic Policing)就是对流量进行控制,通过监督进入网络端口的流量速率,对超出部分的流量进行“惩罚”(这个惩罚可以是丢弃、也可是延迟发送),使... QoS流量监管功能是采用令牌桶(Token-Bucket
  • 令牌桶算法实现限流

    千次阅读 2017-08-24 15:20:10
    参考:http://blog.didispace.com/spring-boot-request-limit/
  • QoS技术中令牌桶算法实现

    千次阅读 2009-08-12 23:42:00
    QoS技术中令牌桶算法实现方式比较前序:令牌桶算法比较麻烦,但是请注意,在IE考试里整形和管制的概念以及在实际生活中所使用的限速都是基于这一算法.所以很有必要搞搞清楚!!!!!今天我发得我的心得,这里暂时先不涉及在...
  • 令牌桶和漏桶

    千次阅读 2016-06-02 16:11:41
    令牌桶(Token Bucket)和漏桶(leaky bucket)是 最常用的两种限流的算法
1 2 3 4 5 ... 20
收藏数 6,080
精华内容 2,432
关键字:

令牌桶算法