精华内容
下载资源
问答
  • 令牌桶

    2019-12-18 22:56:14
    令牌桶算法 在网络中传输数据时,为了防止网络拥塞,需限制流出网络的流量,使流量以比较均匀的速度向外发送。所以限流措施是必不可少的,其中最常见的一种限流方式就是 "令牌桶算法". 令牌桶算法是网络流量整形和...

    令牌桶算法

      在网络中传输数据时,为了防止网络拥塞,需限制流出网络的流量,使流量以比较均匀的速度向外发送。所以限流措施是必不可少的,其中最常见的一种限流方式就是 "令牌桶算法".
    	令牌桶算法是网络流量整形和速率限制中的一种常见的算法。它是用来控制发送到网络上的数据数目,并允许突发数据的发送。
    	令牌桶可以源源不断产生令牌,当高并发的请求想要访问系统时,必须先在令牌桶中取出一个令牌。由于请求的数量会大于令牌产生的数量,这时令牌会不断的增多,直到把桶填满。后面再产生的令牌就会从桶中溢出。最后桶中可以保存的最大令牌数永远不会超过桶的大小。从而达到限流的作用。
    

    总结

    	简单来说,令牌桶就像现实中的安检一样,每到过节或者旅游季的时候,车站的人口流量处于高峰状态。当这些高流量进入安检时,会一个一个按照一定顺序进入,从而达到限流的作用。
    
    展开全文
  • redis令牌桶AOP实现令牌桶介绍说明实现思路@RateLimiterAopRedisRateLimiterAspectRedisLimitUtils应用 令牌桶介绍 令牌桶百度百科 令牌桶算法的基本过程如下: 假如用户配置的平均发送速率为r,则每隔1/r秒一个...

    令牌桶介绍

    令牌桶百度百科
    在这里插入图片描述

    令牌桶算法的基本过程如下:
    假如用户配置的平均发送速率为r,则每隔1/r秒一个令牌被加入到桶中;
    假设桶最多可以存发b个令牌。如果令牌到达时令牌桶已经满了,那么这个令牌会被丢弃;
    当一个n个字节的数据包到达时,就从令牌桶中删除n个令牌,并且数据包被发送到网络;
    如果令牌桶中少于n个令牌,那么不会删除令牌,并且认为这个数据包在流量限制之外;
    算法允许最长b个字节的突发,但从长期运行结果看,数据包的速率被限制成常量r。对于在流量限制外的数据包可以以不同的方式处理:
    它们可以被丢弃;
    它们可以排放在队列中以便当令牌桶中累积了足够多的令牌时再传输;
    它们可以继续发送,但需要做特殊标记,网络过载的时候将这些特殊标记的包丢弃。
    注意:令牌桶算法不能与另外一种常见算法“漏桶算法(Leaky Bucket)”相混淆。这两种算法的主要区别在于“漏桶算法”能够强行限制数据的传输速率,而“令牌桶算法”在能够限制数据的平均传输速率外,还允许某种程度的突发传输。在“令牌桶算法”中,只要令牌桶中存在令牌,那么就允许突发地传输数据直到达到用户配置的门限,因此它适合于具有突发特性的流量。

    说明

    写这个实现的过程,一直想通过java代码的方式去实现令牌桶,发现必须要写分布式锁去累加令牌,想想,与其写分布式锁然后在java代码里计算累加令牌值,不如直接写lua脚本去实现令牌的功能。

    实现思路

    在令牌桶中有两种方式去累加 job递增令牌任务、处理时进行计算累加令牌
    在实现中采用计算累加令牌
    公式: 上次累加时间 = key设置的过期时间 - 剩余的过期时间
    流程图

    @RateLimiterAop

    令牌桶注解定义

    
    import org.springframework.core.annotation.AliasFor;
    import java.lang.annotation.Documented;
    import java.lang.annotation.ElementType;
    import java.lang.annotation.Retention;
    import java.lang.annotation.RetentionPolicy;
    import java.lang.annotation.Target;
    import java.util.concurrent.TimeUnit;
    
    /**
     * @author Zl
     * @date 2019/8/7
     * @since
     */
    @Target(ElementType.METHOD)
    @Retention(RetentionPolicy.RUNTIME)
    @Documented
    public @interface RateLimiterAop {
    
        /**
         * 桶容量 默认为1
         * @return
         */
        long capacity() default 1;
    
        /**
         * 间隔时间 按时间单位换算
         * @return
         */
        long intervalTime() default 1000;
    
        /**
         * 时间单位 默认为毫秒
         *
         * @return
         */
        TimeUnit timeUnit() default TimeUnit.MILLISECONDS;
    
        /**
         * springEl表达式
         * key为空时 method.getName
         *
         * @return
         */
        String key() default "";
    
        /**
         * 异常i18n编码定义
         *
         * @return
         */
        @AliasFor("errorCode")
        String value();
    
        @AliasFor("value")
        String errorCode() default "";
    
        /**
         * 定义作用域
         * 为空时取class.getName
         *
         * @return
         */
        String scopeName() default "";
    
    }
    
    

    RedisRateLimiterAspect

    redis令牌桶切面处理

    import RateLimiterAop;
    import ExceptionHandler;
    import RedisLimitUtils;
    import lombok.extern.slf4j.Slf4j;
    import org.apache.commons.lang3.StringUtils;
    import org.aspectj.lang.ProceedingJoinPoint;
    import org.aspectj.lang.annotation.Around;
    import org.aspectj.lang.annotation.Aspect;
    import org.aspectj.lang.annotation.Pointcut;
    import org.aspectj.lang.reflect.MethodSignature;
    import org.springframework.beans.factory.annotation.Autowired;
    import org.springframework.expression.EvaluationContext;
    import org.springframework.expression.ExpressionParser;
    import org.springframework.expression.spel.standard.SpelExpressionParser;
    import org.springframework.expression.spel.support.StandardEvaluationContext;
    import org.springframework.stereotype.Component;
    
    import java.lang.reflect.Method;
    import java.util.concurrent.TimeUnit;
    
    /**
     * @author Zl
     * @date 2019/8/7
     * @since
     */
    @Slf4j
    @Aspect
    @Component
    public class RedisRateLimiterAspect {
    
        private ExpressionParser parser = new SpelExpressionParser();
    
        @Autowired
        private RedisLimitUtils redisLimitUtils;
    
        @Pointcut("@annotation(com.ztesoft.zsmart.nros.base.annotation.RateLimiterAop)")
        public void pointCut() {
        }
    
        @Around("pointCut()")
        public Object around(ProceedingJoinPoint point) throws Throwable {
            MethodSignature signature = (MethodSignature) point.getSignature();
            Method method = signature.getMethod();
            String className = point.getTarget().getClass().getName();
            Object[] args = point.getArgs();
            String[] paramNames = signature.getParameterNames();
            EvaluationContext context = new StandardEvaluationContext();
            for (int i = 0; i < args.length; i++) {
                context.setVariable(paramNames[i], args[i]);
            }
            RateLimiterAop limiterAop = method.getAnnotation(RateLimiterAop.class);
            TimeUnit timeUnit = limiterAop.timeUnit();
            //桶容量
            long capacity = limiterAop.capacity();
            //间隔时间(速率) 毫秒
            long intervalTime = timeUnit.toMillis(limiterAop.intervalTime());
            //业务i18n异常编码
            String errorCode = limiterAop.value();
            //key为空时锁方法,否则按SpringEl表达式取值
            String key = StringUtils.isEmpty(limiterAop.key()) ? method.getName() : parser.parseExpression(limiterAop.key()).getValue
                    (context, String.class);
            //作用域为空时取className
            String limiterAopName = StringUtils.isEmpty(limiterAop.scopeName()) ? className : limiterAop.scopeName();
            //构造redisKey
            String redisKey = limiterAopName + "#" + key;
            //设置过期时间为间隔时间*容量*5
            if(redisLimitUtils.limitHandler(redisKey, capacity, intervalTime, intervalTime * capacity * 5L)){
                log.info("获取令牌成功!class={},method={},key={}", className, method, redisKey);
                //执行方法
                return point.proceed();
            }
            log.info("获取令牌失败,class={},method={},key={}", className, method, redisKey);
            //失败处理逻辑
            ExceptionHandler.publish(errorCode);
            return null;
        }
    
    }
    

    RedisLimitUtils

    与redis的交互域 主要处理逻辑由lua脚本实现

    import lombok.extern.slf4j.Slf4j;
    import org.springframework.beans.factory.annotation.Autowired;
    import org.springframework.data.redis.connection.RedisConnection;
    import org.springframework.data.redis.connection.ReturnType;
    import org.springframework.data.redis.core.RedisTemplate;
    import org.springframework.data.redis.core.script.DefaultRedisScript;
    import org.springframework.stereotype.Component;
    
    import java.util.Optional;
    import java.util.concurrent.TimeUnit;
    
    /**
     * redis 分布式锁Utils
     *
     * @author Zl
     * @date 2019/8/2
     * @since
     */
    @Slf4j
    @Component
    public class RedisLimitUtils {
    
        private static final DefaultRedisScript<String> LIMIT_LUA;
        private static final String LIMIT_HEARD = "limit:";
    
        static {
            StringBuilder sb = new StringBuilder();
            sb.append("local key = KEYS[1] ");
            sb.append("local capacity = tonumber(ARGV[1]) ");
            sb.append("local intervalTime = tonumber(ARGV[2]) ");
            sb.append("local expireTime = tonumber(ARGV[3]) ");
            sb.append("local ttlTime = redis.call(\"pttl\",key) ");
            //计算时差需要累加的令牌数量
            sb.append("local sum = math.floor((expireTime - ttlTime) / intervalTime) ");
            sb.append("if sum > 0 then ");
            //累加令牌 超过桶容量时直接set为容量值 会自动进行初始化 要求间隔时间一点要小于过期时间的的1/2
            sb.append("    if redis.call(\"incrby\",key,sum) > capacity then ");
            sb.append("        redis.call(\"set\",key,capacity) ");
            sb.append("    end ");
            //重新写入过期时间 避免重复计算
            sb.append("    redis.call(\"pexpire\",key,expireTime) ");
            sb.append("end ");
            //进行decr令牌
            sb.append("if redis.call(\"decr\",key) >= 0 ");
            sb.append("        then ");
            sb.append("    return 1 ");
            sb.append("else ");
            //失败回滚令牌
            sb.append("    redis.call(\"incr\",key) ");
            sb.append("    return 0 ");
            sb.append("end ");
            DefaultRedisScript<String> script = new DefaultRedisScript<>();
            script.setScriptText(sb.toString());
            LIMIT_LUA = script;
        }
    
        @Autowired
        private RedisTemplate<String, Long> redisTemplate;
    
    
        /**
         * 获取上次填入桶时间与过期时间的差值
         * now - 设置的过期时间 - ttl的时间 = 上次设置的时间
         *
         * @return
         */
        public boolean limitHandler(String key, Long capacity, Long intervalTime, Long expireTime) {
            try {
                Object execute = redisTemplate.execute(
                        (RedisConnection connection) -> connection.eval(
                                LIMIT_LUA.getScriptAsString().getBytes(),
                                ReturnType.INTEGER,
                                1,
                                buildLimitKey(key).getBytes(),
                                capacity.toString().getBytes(),
                                intervalTime.toString().getBytes(),
                                expireTime.toString().getBytes())
                );
                return execute.equals(1L);
            } catch (Exception e) {
                log.error("limitHandler occured an exception", e);
            }
            return false;
        }
    
        private String buildLimitKey(String key) {
            return LIMIT_HEARD + key;
        }
    
    }
    

    应用

        /**
         * 此方法限制每秒生产一个令牌,桶容量为1
         */
        @DistributedLock(value = "*CENTER-100001",capacity = 1,intervalTime = 1,timeUnit = TimeUnit.SECONDS)
        public void test(){}
    

    在aop的应用大值与博客中的redis分布式锁aop实现一致,所以不做过多的应用实例。如果可以,帮忙看一下分布式锁aop实现啦,感激。
    链接地址:redis应用aop分布式锁

    展开全文
  • 令牌桶资料

    2015-09-09 18:19:20
    令牌桶资料,交换机小学期实验所需的令牌桶资料
  • go令牌桶

    2020-10-30 12:43:36
    令牌桶 原理 令牌桶按固定的速率往桶里放入令牌,并且只要能从桶里取出令牌就能通过,令牌桶支持突发流量的快速处理。对于从桶里取不到令牌的场景,我们可以选择等待也可以直接拒绝并返回。对于从桶里取不到令牌的...

    令牌桶

    原理
    令牌桶按固定的速率往桶里放入令牌,并且只要能从桶里取出令牌就能通过,令牌桶支持突发流量的快速处理。对于从桶里取不到令牌的场景,我们可以选择等待也可以直接拒绝并返回。对于从桶里取不到令牌的场景,我们可以选择等待也可以直接拒绝并返回。

    对于令牌桶的Go语言实现,可以参照github.com/juju/ratelimit库。

    创建令牌桶的方法:

    // 创建指定填充速率和容量大小的令牌桶
    func NewBucket(fillInterval time.Duration, capacity int64) *Bucket
    // 创建指定填充速率、容量大小和每次填充的令牌数的令牌桶
    func NewBucketWithQuantum(fillInterval time.Duration, capacity, quantum int64) *Bucket
    // 创建填充速度为指定速率和容量大小的令牌桶
    // NewBucketWithRate(0.1, 200) 表示每秒填充20个令牌
    func NewBucketWithRate(rate float64, capacity int64) *Bucket
    

    取出令牌的方法如下:

    // 取token(非阻塞)
    func (tb *Bucket) Take(count int64) time.Duration
    func (tb *Bucket) TakeAvailable(count int64) int64
    
    // 最多等maxWait时间取token
    func (tb *Bucket) TakeMaxDuration(count int64, maxWait time.Duration) (time.Duration, bool)
    
    // 取token(阻塞)
    func (tb *Bucket) Wait(count int64)
    func (tb *Bucket) WaitMaxDuration(count int64, maxWait time.Duration) bool
    

    虽说是令牌桶,但是我们没有必要真的去生成令牌放到桶里,我们只需要每次来取令牌的时候计算一下,当前是否有足够的令牌就可以了,具体的计算方式可以总结为下面的公式:

    当前令牌数 = 上一次剩余的令牌数 + (本次取令牌的时刻-上一次取令牌的时刻)/放置令牌的时间间隔 * 每次放置的令牌数
    github.com/juju/ratelimit这个库中关于令牌数计算的源代码如下:

    func (tb *Bucket) currentTick(now time.Time) int64 {
    	return int64(now.Sub(tb.startTime) / tb.fillInterval)
    }
    func (tb *Bucket) adjustavailableTokens(tick int64) {
    	if tb.availableTokens >= tb.capacity {
    		return
    	}
    	tb.availableTokens += (tick - tb.latestTick) * tb.quantum
    	if tb.availableTokens > tb.capacity {
    		tb.availableTokens = tb.capacity
    	}
    	tb.latestTick = tick
    	return
    }
    

    获取令牌的TakeAvailable()函数关键部分的源代码如下:

    func (tb *Bucket) takeAvailable(now time.Time, count int64) int64 {
    	if count <= 0 {
    		return 0
    	}
    	tb.adjustavailableTokens(tb.currentTick(now))
    	if tb.availableTokens <= 0 {
    		return 0
    	}
    	if count > tb.availableTokens {
    		count = tb.availableTokens
    	}
    	tb.availableTokens -= count
    	return count
    }
    

    gin框架中使用限流中间件

    在gin框架构建的项目中,我们可以将限流组件定义成中间件。

    这里使用令牌桶作为限流策略,编写一个限流中间件如下:

    func RateLimitMiddleware(fillInterval time.Duration, cap int64) func(c *gin.Context) {
    	bucket := ratelimit.NewBucket(fillInterval, cap)
    	return func(c *gin.Context) {
    		// 如果取不到令牌就中断本次请求返回 rate limit...
    		if bucket.TakeAvailable(1) < 1 {
    			c.String(http.StatusOK, "rate limit...")
    			c.Abort()
    			return
    		}
    		c.Next()
    	}
    }
    

    对于该限流中间件的注册位置,我们可以按照不同的限流策略将其注册到不同的位置,例如:

    1 如果要对全站限流就可以注册成全局的中间件。
    2 如果是某一组路由需要限流,那么就只需将该限流中间件注册到对应的路由组即可。

    展开全文
  • 令牌桶算法

    2019-07-26 15:53:18
    令牌桶算法: 1.名词解释 令牌:可以理解为一次性的门禁卡 产生令牌:以恒定的速率产生令牌放入桶中 消耗令牌:每一次请求都会消耗桶中的令牌,大的数据包需要的令牌多一些,小的数据包需要的令牌少一些 令牌桶...

    令牌桶算法:

    1.名词解释

    令牌:可以理解为一次性的门禁卡

    产生令牌:以恒定的速率产生令牌放入桶中

    消耗令牌:每一次请求都会消耗桶中的令牌,大的数据包需要的令牌多一些,小的数据包需要的令牌少一些

    令牌桶大小:令牌桶的容量

    2.场景

    1. 当请求消耗令牌的速率持续小于产生令牌的速率时,令牌桶在一定时间就会变满,此时新产生的令牌就无效,不放入令牌桶
    2. 当请求消耗令牌的速率大于令牌产生的速率时,此时就会消耗令牌桶中的存货(第一种情况也会消耗,但是会及时补充,所以就可以理解为不消耗)来保持现在的请求速率,当令牌桶存货消耗为空时,请求速率就被限制为令牌的产生速率。

    3.优点

    在限流的情况下,偶尔的高流量(请求很多)是不可避免的,多余的请求只有被丢弃。

    令牌桶算法有效解决了这一问题,有了令牌桶做缓冲,偶尔的高流量(请求很多)并不会被直接丢弃

    展开全文
  • 令牌桶Java实现

    2017-05-05 13:19:58
    令牌桶 Java 源码 不限制桶大小
  • 令牌桶实现逻辑

    2021-05-19 09:15:31
    1. 设置令牌桶容量、令牌桶放入令牌的时间间隔、最后一次放入令牌的时间 2. 当令牌桶中有令牌余量时接收请求,没有令牌时拦截请求,每次收到请求时更新令牌桶数量 3. 请求时时间与最后一个令牌时间比较做时间差,...
  • ratelimit-锈率限制的令牌桶速率限制器提供了一个令牌桶速率限制器,该令牌桶速率限制器可以由单个线程使用,或者跨t ratelimit共享。锈率限制的令牌桶速率限制器提供了一个令牌桶速率限制器,该令牌桶速率限制器...
  • 一、漏桶和令牌桶介绍 二、Redis+lua脚本 + 令牌桶算法 实现限流控制 1、自定义一个注解,用来给限流的方法标注 2、编写lua脚本 3、读取lua脚本 4、创建拦截器拦截带有该注解的方法 5、在WebConfig中注册这个...
  • 漏桶算法与令牌桶算法漏桶算法令牌桶算法区别RateLimiter信号量 转载:本文转载自 linkedkeeper.com (文/张松然) 漏桶算法 漏桶算法:水(请求)先进入到漏桶里,漏桶以一定速度出水,当水流(请求)过大时会直接...
  • 令牌桶和漏桶

    2021-03-11 10:22:56
    令牌桶 令牌桶就是规定一个固定大小的资源池,比如规定一个有100个苹果的数组, 那么请求过来时先去从这个数组中拿取苹果,拿到了就可以放行,没拿到就 直接拒绝服务,同时有一个生产者在匀速往数组里放苹果,超过100就放...
  • 7. 令牌桶

    2021-02-03 21:13:17
    1. 令牌桶分类 2. 单速令牌桶参数 3. 单速单桶双色 4. 单速双桶三色 5. 双速率令牌桶参数 6. 双速双桶三色 7. 单速双桶与双速双桶的区别
  • java实现令牌桶限流

    2020-09-11 08:59:33
    限流是对某一时间窗口内的请求数进行限制,保持...常用的限流算法有令牌桶和和漏桶,而Google开源项目Guava中的RateLimiter使用的就是令牌桶控制算法。 在开发高并发系统时有三把利器用来保护系统:缓存、降级和限流
  • redis令牌桶限流

    千次阅读 多人点赞 2020-06-26 20:38:55
    令牌桶算法 :能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。 漏桶算法+令牌桶算法 :为网络流量提供高效地控制。 可以说: 令牌桶算法:能够保证自身系统的流量均匀; 漏桶算法:保证被调用系统...
  • 令牌桶限流

    2020-04-26 09:33:02
    令牌桶和漏桶算法的区别 漏桶算法和令牌桶算法都能够限制数据的传输速率,而令牌桶算法还能允许一定程度的突发传输,只要桶中存在令牌,就可以突发的传输数据直到用户配置的上限,因此它适合于具有突发特性的流量,...
  • 令牌桶生成令牌“It used to be that designers made an object and walked away. Today the emphasis must shift to designing the entire lifecycle.” “过去,设计师制造了一个物体然后走开了。 今天,重点必须...
  • Qos令牌桶技术原理

    2021-01-04 12:44:48
    令牌桶概述 配合软件队列使用。 单位是Byte而不是报文的个数,如果一个报文所需的Byte数超过了所剩余的令牌个数,就无法发送,也就是说一个令牌对应一个Byte。 令牌桶可以看作是一个存放一定数量令牌的容器。系统按...
  • 令牌桶限速C++实现

    2021-06-05 15:58:34
    由于业务需求,要对总流量进行限速,做了一个C++版本的实现,基本满足业务要求。有需要的同学自行进行优化。 a. 按特定的速率向令牌桶投放令牌 ...消费者查看令牌桶的令牌,令牌充足消费相应数量的令牌,令牌不足丢弃相
  • go令牌桶算法

    2020-06-12 09:19:50
    go令牌桶算法 // 定义令牌桶结构 type tokenBucket struct { timestamp time.Time // 当前时间戳 capacity float64 // 桶的容量(存放令牌的最大量) rate float64// 令牌放入速度 tokens float64 // 当前令牌...
  • 令牌桶限流总结

    千次阅读 2020-07-31 16:57:06
    令牌桶限流总结一、引入二、令牌桶和漏桶算法区别三、Guava中RateLimiter用法及源码分析1、Google的令牌桶RateLimiter用法2、RateLimiter源码简单分析: 一、引入 限流 是对某一时间窗口内的请求数进行限制,保证...
  • Token Bucket 令牌桶算法

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

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,208
精华内容 883
关键字:

令牌桶