高可用之限流 08-leaky bucket漏桶算法

限流系列

开源组件 rate-limit: 限流

高可用之限流-01-入门介绍

高可用之限流-02-如何设计限流框架

高可用之限流-03-Semaphore 信号量做限流

高可用之限流-04-fixed window 固定窗口

高可用之限流-05-slide window 滑动窗口

高可用之限流-06-slide window 滑动窗口 sentinel 源码

高可用之限流-07-token bucket 令牌桶算法

高可用之限流 08-leaky bucket漏桶算法

高可用之限流 09-guava RateLimiter 入门使用简介 & 源码分析

漏桶算法

漏桶算法，又称 leaky bucket。

为了理解漏桶算法，我们看一下对于该算法的示意图：

从图中我们可以看到，整个算法其实十分简单。首先，我们有一个固定容量的桶，有水流进来，也有水流出去。

对于流进来的水来说，我们无法预计一共有多少水会流进来，也无法预计水流的速度。但是对于流出去的水来说，这个桶可以固定水流出的速率。而且，当桶满了之后，多余的水将会溢出。

我们将算法中的水换成实际应用中的请求，我们可以看到漏桶算法天生就限制了请求的速度。当使用了漏桶算法，我们可以保证接口会以一个常速速率来处理请求。

所以漏桶算法天生不会出现临界问题。

漏桶算法可以粗略的认为就是注水漏水过程，往桶中以一定速率流出水，以任意速率流入水，当水超过桶流量则丢弃，因为桶容量是不变的，保证了整体的速率。

java 实现

/** Copyright (c)  2018. houbinbin Inc.* rate-acquire All rights reserved.*/package com.github.houbb.rate.limit.core.core.impl;import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.rate.limit.core.core.ILimitContext;
import org.apiguardian.api.API;/*** 漏桶算法** @author houbinbin* Created by bbhou on 2017/9/20.* @since 0.0.7*/
@API(status = API.Status.EXPERIMENTAL)
public class LimitLeakyBucket extends LimitAdaptor {private static final Log LOG = LogFactory.getLog(LimitLeakyBucket.class);/*** 令牌的发放速率* <p>* 每一秒发放多少。** @since 0.0.6*/private final long rate;/*** 容量* <p>* 后期暴露为可以配置** @since 0.0.6*/private final long capacity;/*** 水量** @since 0.0.6*/private volatile long water;/*** 上一次的更新时间** @since 0.0.6*/private volatile long lastUpdateTime;/*** 构造器** @param context 上下文* @since 0.0.4*/public LimitLeakyBucket(final ILimitContext context) {// 暂不考虑特殊输入，比如 1s 令牌少于1 的场景long intervalSeconds = context.timeUnit().toSeconds(context.interval());this.rate = context.count() / intervalSeconds;// 8 的数据this.capacity = this.rate * 8;// 这里可以慢慢的加，初始化设置为0// 这样就有一个 warmUp 的过程this.water = 0;this.lastUpdateTime = System.currentTimeMillis();}/*** 获取锁** （1）未满加水：通过代码 water +=1进行不停加水的动作。* （2）漏水：通过时间差来计算漏水量。* （3）剩余水量：总水量-漏水量。** @since 0.0.5*/@Overridepublic synchronized boolean acquire() {long now = System.currentTimeMillis();// 先执行漏水，计算剩余水量long durationMs = now - lastUpdateTime;long leakyWater = (long) (durationMs * 1.0 * rate / 1000);LOG.debug("[Limit] leaky water is " + leakyWater);water = Math.max(0, water - leakyWater);// 这里应该加一个判断，如果漏水量较小，直接返回。避免开始时，大量流量通过if(leakyWater < 1) {LOG.debug("[Limit] leaky water is too small!");return false;}if ((water + 1) < capacity) {// 尝试加水,并且水还未满water++;lastUpdateTime = now;return true;} else {// 水满，拒绝加水LOG.debug("[Limit] leaky water is has been full!");return false;}}}

和令牌桶核心的不同，是出的速度实际上是固定的。

不会像令牌同时可以消费多个的情况。

当水桶满时，和令牌满是类似的，直接返回 false。

测试

public class LimitLeakyBucketTest {private static final Log LOG = LogFactory.getLog(LimitTokenBucket.class);/*** 2S 内最多运行 5 次* @since 0.0.5*/private static final ILimit LIMIT = LimitBs.newInstance().interval(1).count(5).limit(LimitLeakyBucket.class).build();static class LimitRunnable implements Runnable {@Overridepublic void run() {for(int i = 0; i < 6; i++) {while (!LIMIT.acquire()) {// 等待令牌TimeUtil.sleep(100);}LOG.info("{}-{}", Thread.currentThread().getName(), i);}}}public static void main(String[] args) {new Thread(new LimitRunnable()).start();}}

日志

23:55:54.911 [Thread-1] INFO  com.github.houbb.rate.limit.core.core.impl.LimitTokenBucket - Thread-1-0
23:55:55.113 [Thread-1] INFO  com.github.houbb.rate.limit.core.core.impl.LimitTokenBucket - Thread-1-1
23:55:55.313 [Thread-1] INFO  com.github.houbb.rate.limit.core.core.impl.LimitTokenBucket - Thread-1-2
23:55:55.513 [Thread-1] INFO  com.github.houbb.rate.limit.core.core.impl.LimitTokenBucket - Thread-1-3
23:55:55.713 [Thread-1] INFO  com.github.houbb.rate.limit.core.core.impl.LimitTokenBucket - Thread-1-4
23:55:55.913 [Thread-1] INFO  com.github.houbb.rate.limit.core.core.impl.LimitTokenBucket - Thread-1-5