写点什么

深入探索令牌桶限流的原理与实践

作者:袋鼠云数栈
  • 2024-05-30
    浙江
  • 本文字数:4750 字

    阅读完需:约 16 分钟

深入探索令牌桶限流的原理与实践

在当今的互联网时代,随着用户数量和请求量的不断增加,系统的性能和稳定性面临着巨大的挑战。限流算法作为保障系统稳定性的重要手段之一,被广泛应用于各种服务和应用中。限流的核心目的是对某一时间窗口内的请求数进行限制,保持系统的可用性和稳定性,防止因流量暴增而导致的系统运行缓慢或宕机。

常见限流算法对比

常见的限流算法有四种:


● 令牌桶算法(Token Bucket)


· 原理:令牌桶算法是一种基于令牌的限流算法,它维护一个固定容量的令牌桶,按照固定速率往桶中添加令牌,每当有请求到来时,消耗一个令牌,如果桶中没有足够的令牌,则拒绝该请求。


· 优点:平滑限流,可以应对突发流量;灵活控制流量速率。


· 缺点:对于突发流量,需要足够的令牌桶容量用来应对,否则可能会出现丢弃部分请求的情况。


● 漏桶算法(Leaky Bucket)


· 原理:漏桶算法是一种基于漏桶的限流算法,它维护一个固定容量的漏桶,按照固定速率漏水,当有请求到来时,漏桶中的水量增加,如果漏桶已满,则拒绝该请求。


· 优点:平滑限流,可以限制请求的处理速率。


· 缺点:对于突发流量,可能会出现短时的请求丢失。


● 计数器算法(Fixed Window)


· 原理:计数器算法是一种简单的限流算法,通过统计单位时间内的请求数量,当请求达到设定的阈值时,拒绝后续请求。


· 优点:简单易实现,对于固定流量场景适用。


· 缺点:无法处理突发流量,可能导致性能下降或服务不可用。


● 漏斗算法(Funnel Algorithm)


· 原理:漏斗算法是一种基于漏斗的限流算法,它模拟了一个漏斗的过程,请求进入漏斗后,根据漏斗的容量和速率来控制请求的处理速度。


· 优点:可以动态调整漏斗的容量和速率,适应不同的流量情况。


· 缺点:相对复杂,实现和调优难度较大。

令牌桶算法

在微服务架构中,Spring Cloud Gateway 作为服务网关,承担着流量管理和路由分发的关键角色。为了增强其限流能力,Spring Cloud Gateway 官方提供了 RequestRateLimiterGatewayFilterFactory 类,该类通过集成 Redis 和使用 Lua 脚本来实现高效的令牌桶限流策略


在众多限流算法中,令牌桶算法以其独特的优点和灵活性,成为了业界广泛采用的一种方案。数栈「数据服务平台DataAPI」基于 Spring Cloud 的已有限流能力,进一步进行了定制化的开发和优化。


上文简单介绍过,令牌桶算法是一种流量控制算法,用于限制单位时间内通过的请求数量,它能够平滑地限制请求速率,防止突发大量请求对系统造成过载。以下是令牌桶算法的基本原理和工作流程:


● 令桶牌


算法中的“令牌桶”类似于一个存放令牌的容器。在每个固定的时间间隔(例如每秒),系统会往令牌桶中添加一定数量的令牌。


● 请求处理


当一个请求到达时,系统会尝试从令牌桶中获取一个令牌。如果令牌桶中有足够的令牌,则系统允许处理该请求,并从令牌桶中取走一个令牌。如果令牌桶中没有足够的令牌,则系统拒绝该请求或者将其放入队列等待。


● 令牌生成


令牌桶中的令牌数量会受到限制,它不能无限制地增长。当令牌桶已经满了时,不会再继续产生新的令牌,多余的令牌会被丢弃。



通过上述工作流程,令牌桶算法可以实现对请求的流量控制,使得系统能够以稳定的速率处理请求。这种算法适合于需要限制请求速率的场景,如接口调用频率控制、网络流量控制等。

自定义限流

通过继承 AbstractRateLimiter 重写 isAllowed 方法实现自定义限流。



通过继承 AbstractGatewayFilterFactory 重写 apply 方法调用具体的限流方法。




isAllowed 方法分析:


@Override    @SuppressWarnings("unchecked")    public Mono<Response> isAllowed(String routeId, String id) {        // 初始化判断        if (!this.initialized.get()) {            throw new IllegalStateException("RedisRateLimiter is not initialized");        }
// How many requests per second do you want a user to be allowed to do? int replenishRate = 0;
// How much bursting do you want to allow? int burstCapacity = 0;
// How many tokens are requested per request? int requestedTokens = 1;
final RedisLimitDefinition limitDefinition;
if(LimitListRouteDefinitionLocator.ID_PREFIX.equals(routeId.split(ValidateRequestGlobalFilter.SPLIT)[0])){ limitDefinition = limitConfig.getLimitInfoMap().get(id); if (ObjectUtils.isEmpty(limitDefinition) ){ throw new IllegalArgumentException("No Configuration found for uri " + id); } replenishRate = limitDefinition.getReplenishRate();
// How much bursting do you want to allow? burstCapacity = limitDefinition.getBurstCapacity(); } else{ // 自定义逻辑,分为分钟级限流和秒级限流 String[] routeIdArr = routeId.split(ValidateRequestGlobalFilter.SEPARATOR); if(routeIdArr.length > 1){ replenishRate = Integer.parseInt(routeIdArr[0]); burstCapacity = replenishRate * 60; limitDefinition = new RedisLimitDefinition(replenishRate, replenishRate, null, null); requestedTokens = 60; } else{ replenishRate = Integer.parseInt(routeIdArr[0]); burstCapacity = replenishRate; limitDefinition = new RedisLimitDefinition(replenishRate, replenishRate, null, null); requestedTokens = 1; } }

try { List<String> keys = getKeys(id);
// The arguments to the LUA script. time() returns unixtime in seconds. List<String> scriptArgs = Arrays.asList(replenishRate + "", burstCapacity + "", Instant.now().getEpochSecond() + "", requestedTokens + ""); // allowed, tokens_left = redis.eval(SCRIPT, keys, args) // 调用lua脚本并返回结果 Flux<List<Long>> flux = this.reactiveStringRedisTemplate.execute(this.script, keys, scriptArgs); return flux.onErrorResume(throwable -> { if (log.isDebugEnabled()) { log.debug("Error calling rate limiter lua", throwable); } return Flux.just(Arrays.asList(1L, -1L)); }).reduce(new ArrayList<Long>(), (longs, l) -> { longs.addAll(l); return longs; }).map(results -> { boolean allowed = results.get(0) == 1L; Long tokensLeft = results.get(1);
Response response = new Response(allowed, getHeaders(limitDefinition, tokensLeft));
if (log.isDebugEnabled()) { log.debug("response: " + response); } return response; }); } catch (Exception e) { /* * We don't want a hard dependency on Redis to allow traffic. Make sure to set * an alert so you know if this is happening too much. Stripe's observed * failure rate is 0.01%. */ log.error("Error determining if user allowed from redis", e); } return Mono.just(new Response(true, getHeaders(limitDefinition, -1L))); }
复制代码

LUA 脚本

LUA 脚本是内置在数栈后端服务中的,位置如图所示:



接下来进行脚本代码分析:


-- 基于唯一id生成的token key和timestamp keylocal tokens_key = KEYS[1]local timestamp_key = KEYS[2]--redis.log(redis.LOG_WARNING, "tokens_key " .. tokens_key)
-- 对应的脚本入参,分别为-- 往令牌桶放置的速率,每秒n个local rate = tonumber(ARGV[1])-- 令牌桶最大容量local capacity = tonumber(ARGV[2])-- 当前时间戳,秒级local now = tonumber(ARGV[3])-- 每次请求消耗的令牌数量local requested = tonumber(ARGV[4])
-- 放满令牌桶是的时长local fill_time = capacity/rate-- redis key过期时间local ttl = math.floor(fill_time*2)
--redis.log(redis.LOG_WARNING, "rate " .. ARGV[1])--redis.log(redis.LOG_WARNING, "capacity " .. ARGV[2])--redis.log(redis.LOG_WARNING, "now " .. ARGV[3])--redis.log(redis.LOG_WARNING, "requested " .. ARGV[4])--redis.log(redis.LOG_WARNING, "filltime " .. fill_time)--redis.log(redis.LOG_WARNING, "ttl " .. ttl)
-- 这里对于last_tokens和last_refreshed的操作既是赋值也有初始化的作用-- 获取令牌桶的数量,如果为空,将令牌桶容量赋值local last_tokens = tonumber(redis.call("get", tokens_key))if last_tokens == nil then last_tokens = capacityend--redis.log(redis.LOG_WARNING, "last_tokens " .. last_tokens)-- 获取最后的更新时间戳,如果为空,设置为0local last_refreshed = tonumber(redis.call("get", timestamp_key))if last_refreshed == nil then last_refreshed = 0end--redis.log(redis.LOG_WARNING, "last_refreshed " .. last_refreshed)
-- 计算出上次到这次统计的时间间隔local delta = math.max(0, now-last_refreshed)-- 上次剩余的令牌数量+新生成的令牌,这个值不会大于令牌桶容量local filled_tokens = math.min(capacity, last_tokens+(delta*rate))-- 总剩余令牌是否能满足一次请求消耗的令牌local allowed = filled_tokens >= requestedlocal new_tokens = filled_tokens-- 请求是否允许通过的标志位local allowed_num = 0-- 满足的话将总数减去单次消耗的令牌记为当前桶容量,并重新放置到redis key中if allowed then new_tokens = filled_tokens - requested allowed_num = 1end
--redis.log(redis.LOG_WARNING, "delta " .. delta)--redis.log(redis.LOG_WARNING, "filled_tokens " .. filled_tokens)--redis.log(redis.LOG_WARNING, "allowed_num " .. allowed_num)--redis.log(redis.LOG_WARNING, "new_tokens " .. new_tokens)
if ttl > 0 then redis.call("setex", tokens_key, ttl, new_tokens) redis.call("setex", timestamp_key, ttl, now)end
-- return { allowed_num, new_tokens, capacity, filled_tokens, requested, new_tokens }return { allowed_num, new_tokens }
复制代码


模拟计算流程:



针对上述流程,由于设定的是每分钟允许三次请求,可以看到当桶内令牌满是只能通过三次请求。当桶内令牌空时,每隔 20 秒会生成刚好够一次请求的令牌数,实现对流量的平滑控制。


《行业指标体系白皮书》:https://www.dtstack.com/resources/1057?src=szsm


《数据治理行业实践白皮书》下载地址:https://www.dtstack.com/resources/1001?src=szsm


《数栈 V6.0 产品白皮书》下载地址:https://www.dtstack.com/resources/1004?src=szsm


想了解或咨询更多有关大数据产品、行业解决方案、客户案例的朋友,浏览袋鼠云官网:https://www.dtstack.com/?src=szinfoq

发布于: 4 小时前阅读数: 11
用户头像

还未添加个人签名 2021-05-06 加入

还未添加个人简介

评论

发布
暂无评论
深入探索令牌桶限流的原理与实践_大数据_袋鼠云数栈_InfoQ写作社区