令牌桶和漏桶算法的区别

本文主要是介绍令牌桶和漏桶算法的区别，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

令牌桶和漏桶算法的区别

概述
结论
详细
- 令牌桶代码实现
- 漏桶算法代码实现

概述

令牌桶算法和漏桶算法常用作限流器。从使用的角度，而不是算法实现的角度，两种算法其实只向我们暴露一个方法IsLimit，无入参，出参是布尔类型，代表是否限流。

令牌桶算法：有一个固定容量的桶，以恒定速率向桶里面添加令牌，我们可以从桶里面每次取出一个令牌。当取的很频繁时，就可能桶中没有令牌可取，此时被限流。

漏桶算法：有一个固定容量的桶，里面装了水，桶底部有洞，水以恒定速率向外流出，我们可以向桶里加水。当加水动作很频繁时，超过流出速度，桶里的水会满，此时被限流。

可以结合后面的代码来理解两种算法

结论

作为限流器，从使用方面，令牌桶和漏桶算法没有区别，两者均需要初始化桶容量和速率，都会以固定速率往桶里加令牌或漏水。
实现原理方面：

令牌桶算法中，如果从桶中拿不到令牌，即桶空了，被限流
漏桶算法中，如果桶满，则被限流

两者唯一的区别，在于使用方面。漏桶算法可以实现为一个带容量的消息队列，分别有生产者和消费者，生产者向桶中加水，消费者从桶中取水（漏水），由于消费者以固定速率取水，所以有“流量整形”的味道。在这种场景，水有了特殊的含义，不仅仅是一个计数器。且有独特的消费者。
令牌桶算法中的令牌数量，一般仅作为简单的计数器。

详细

对于令牌桶算法以固定速率生成令牌，或者是漏桶算法以固定速率漏水，具体实现，一方面可以通过独立线程去做“加令牌”或“漏水”操作，另一方面可以“惰性”操作，即记录上一次操作的时间，仅当取令牌或添水时，才计算这个时间段本应该“生成多少令牌”或“漏多少水”。

令牌桶代码实现

package mainimport ("fmt""time"
)type TokenBucket struct {capacity  inttokens    intrate      intlastToken time.Time
}func NewTokenBucket(capacity, rate int) *TokenBucket {return &TokenBucket{capacity:  capacity,tokens:    capacity,rate:      rate,lastToken: time.Now(),}
}func (tb *TokenBucket) AllowRequest() bool {now := time.Now()tb.tokens += int(now.Sub(tb.lastToken).Seconds()) * tb.rateif tb.tokens > tb.capacity {tb.tokens = tb.capacity}tb.lastToken = nowif tb.tokens > 0 {tb.tokens--return true}return false
}func main() {tb := NewTokenBucket(10, 1)for i := 0; i < 15; i++ {if tb.AllowRequest() {fmt.Println("Request", i, "allowed")} else {fmt.Println("Request", i, "blocked")}time.Sleep(time.Second)}
}

漏桶算法代码实现

package mainimport ("fmt""time"
)type LeakyBucket struct {capacity  intwater     intrate      intlastLeak  time.Time
}func NewLeakyBucket(capacity, rate int) *LeakyBucket {return &LeakyBucket{capacity: capacity,water:    0,rate:     rate,lastLeak: time.Now(),}
}func (lb *LeakyBucket) AllowRequest() bool {now := time.Now()elapsed := int(now.Sub(lb.lastLeak).Seconds())lb.water -= elapsed * lb.rateif lb.water < 0 {lb.water = 0}lb.lastLeak = nowif lb.water < lb.capacity {lb.water++return true}return false
}func main() {lb := NewLeakyBucket(10, 1)for i := 0; i < 15; i++ {if lb.AllowRequest() {fmt.Println("Request", i, "allowed")} else {fmt.Println("Request", i, "blocked")}time.Sleep(time.Second)}
}