前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >聊聊leaky bucket算法的实现

聊聊leaky bucket算法的实现

作者头像
code4it
发布2018-09-17 17:24:22
2.2K0
发布2018-09-17 17:24:22
举报
文章被收录于专栏:码匠的流水账

本文主要研究一下leaky bucket算法的实现

leaky bucket算法

  • bucket以一定速率滴水,相当于增加桶容量
  • bucket有其容量限制,请求过来时bucket满,则直接被抛弃
  • 请求到来时,如果bucket不满,则放入bucket,相当于放行

简单实现

代码语言:javascript
复制
public class LeakyBucket {

    private final long capacity;
    private final long leaksIntervalInMillis;

    private double used;
    private long lastLeakTimestamp;

    public LeakyBucket(long capacity, long leaksIntervalInMillis) {
        this.capacity = capacity;
        this.leaksIntervalInMillis = leaksIntervalInMillis;

        this.used = 0;
        this.lastLeakTimestamp = System.currentTimeMillis();
    }

    synchronized public boolean tryConsume(int drop) {
        leak();

        if (used + drop > capacity) {
           return false;
        }

        used = used + drop;
        return true;
    }

    private void leak() {
        long currentTimeMillis = System.currentTimeMillis();
        if (currentTimeMillis > lastLeakTimestamp) {
            long millisSinceLastLeak = currentTimeMillis - lastLeakTimestamp;
            long leaks = millisSinceLastLeak / leaksIntervalInMillis;
            if(leaks > 0){
                if(used <= leaks){
                    used = 0;
                }else{
                    used -= (int)leaks;
                }
                this.lastLeakTimestamp = currentTimeMillis;
            }
        }
    }
}
  • 这个实现设计了lastLeakTimestamp字段,用于计算时间差,以及在这个时间段内需要漏水的数量
  • 每次tryConsume的时候,方法内部首先调用leak,根据设定的速度以及时间差计算这个时间段需要漏水的数量,更新桶的当前使用量以及lastLeakTimestamp
  • 之后限流判断,就是判断used与请求的drop是否会超过桶容量,超出则限流,否则放入桶中,更新桶容量

小结

  • leaky bucket与token bucket算法相反,前者是漏水,后者是添加token
  • leaky bucket由于是漏水算法,所以不能像token bucket添加token那种可以累积,因此leaky bucket不能支持burst突发流量

doc

  • Leaky Bucket Algorithm
  • Leaky bucket algorithm for flow control
  • Computer Network | Leaky bucket algorithm
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-08-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 码匠的流水账 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • leaky bucket算法
  • 简单实现
  • 小结
  • doc
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档