概述
令牌桶算法和漏桶算法常用作限流器。从使用的角度，而不是算法实现的角度，两种算法其实只向我们暴露一个方法IsLimit，无入参，出参是布尔类型，代表是否限流。
令牌桶算法：有一个固定容量的桶，以恒定速率向桶里面添加令牌，我们可以从桶里面每次取出一个令牌。当取的很频繁时，就可能桶中没有令牌可取，此时被限流。
漏桶算法：有一个固定容量的桶，里面装了水，桶底部有洞，水以恒定速率向外流出，我们可以向桶里加水。当加水动作很频繁时，超过流出速度，桶里的水会满，此时被限流。
可以结合后面的代码来理解两种算法
结论
作为限流器，从使用方面，令牌桶和漏桶算法没有区别，两者均需要初始化桶容量和速率，都会以固定速率往桶里加令牌或漏水。
实现原理方面：
- 令牌桶算法中，如果从桶中拿不到令牌，即桶空了，被限流
- 漏桶算法中，如果桶满，则被限流
两者唯一的区别，在于使用方面。漏桶算法可以实现为一个带容量的消息队列，分别有生产者和消费者，生产者向桶中加水，消费者从桶中取水（漏水），由于消费者以固定速率取水，所以有“流量整形”的味道。在这种场景，水有了特殊的含义，不仅仅是一个计数器。且有独特的消费者。
令牌桶算法中的令牌数量，一般仅作为简单的计数器。
详细
对于令牌桶算法以固定速率生成令牌，或者是漏桶算法以固定速率漏水，具体实现，一方面可以通过独立线程去做“加令牌”或“漏水”操作，另一方面可以“惰性”操作，即记录上一次操作的时间，仅当取令牌或添水时，才计算这个时间段本应该“生成多少令牌”或“漏多少水”。
令牌桶代码实现
package main
import (
"fmt"
"time"
)
type TokenBucket struct {
capacity int
tokens int
rate int
lastToken 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.rate
if tb.tokens > tb.capacity {
tb.tokens = tb.capacity
}
tb.lastToken = now
if 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 main
import (
"fmt"
"time"
)
type LeakyBucket struct {
capacity int
water int
rate int
lastLeak 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.rate
if lb.water < 0 {
lb.water = 0
}
lb.lastLeak = now
if 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)
}
}
