限流之漏桶算法实现

漏桶算法把发请求的动作比作成注水到桶中，处理请求的过程可以比喻为漏桶漏水。

往桶中以任意速率流入水，以一定速率流出水，当水超过桶流量则丢弃，因为桶容量是不变的，保证了整体的速率。

本质就是：通过一个缓冲区将不平滑的流量”整形”成平滑的（高于均值的流量暂存下来补足到低于均值的时期），以此最大化计算处理资源的利用率。

漏桶限流解决了计数器限流模式下流量突刺的问题，当服务器处理完请求后，只要能从漏桶中流出请求则能继续处理，不会造成长时间等待拒绝请求。

缺点

程序本身的处理能力是会被干扰的，是会变化的。所以，你可以预估某一个阶段内的平均值、中位数，但无法预估具体某一个时刻的程序处理能力。

因此，必然会使用相对悲观的标准去作为阈值，防止程序超负荷。

始终恒定的处理速率有时候并不一定是好事情，对于突发的请求洪峰，在保证服务安全的前提下，应该尽最大努力去响应，这个时候漏桶算法显得有些呆滞。

漏桶满后此时大量请求到来，由于服务器已扩容可以满足请求处理，但是漏桶会拒绝大量请求，导致无法应对突发流量问题。

实现思路

• 队列实现：准备一个队列用来保存请求，然后我们定期从队列中拿请求来执行。
• 延迟计算：
  • 请求时计算上次到本次时间间隔漏掉的流量 water
  • 使用一个变量 Balance 记录漏桶的空余量（包含漏掉的 water）
  • Balance 如果有空余就可以放行此次请求并减少 1

Golang 实现

基于时间延迟计算的思路实现：

package main
 
import (
    "fmt"
    "sync"
    "time"
)
 
// BucketLimiter 定义漏桶算法struct
type BucketLimiter struct {
    Lck      *sync.Mutex // 锁
    Rate     float64     //最大速率限制，每秒请求个数
    Balance  float64     //漏桶的余量
    Cap      float64     //漏桶的最大容量限制
    LastTime time.Time   //上次检查的时间
}
 
// NewBucketLimiter 初始化BucketLimiter
func NewBucketLimiter(rate int, cap int) *BucketLimiter {
    return &BucketLimiter{
        Lck:      new(sync.Mutex),
        Rate:     float64(rate),
        Balance:  float64(cap),
        Cap:      float64(cap),
        LastTime: time.Now(),
    }
}
 
// leakyBucket 漏桶算法实现
func (r *BucketLimiter) leakyBucket() bool {
    ok := false
    r.Lck.Lock()
    defer r.Lck.Unlock()
    now := time.Now()
    dur := now.Sub(r.LastTime).Seconds() //当前时间与上一次检查时间差
    r.LastTime = now
    
    // 计算该时间间隔新流出的水
    water := dur * r.Rate // 计算这段时间内漏桶流出水的流量water
    r.Balance += water    // 漏桶流出 water 容量的水，自然漏桶的余量多出 water
    if r.Balance > r.Cap {
        r.Balance = r.Cap
    }
    
    if r.Balance >= 1 { // 漏桶余量足够容下当前的请求
        r.Balance -= 1
        ok = true
    }
    return ok
}
 
func main() {
    // 初始化 限制每秒2个请求 漏洞容量为5
    r := NewBucketLimiter(2, 5)
    for i := 0; i < 20; i++ {
        ok := r.leakyBucket()
        if ok {
            fmt.Println("pass ", i)
        } else {
            fmt.Println("limit ", i)
        }
        time.Sleep(100 * time.Millisecond)
    }
}

引用

1. 分布式限流：基于 Redis 实现
2. 分布式系统关注点——限流该怎么做？
3. 分布式系统限流算法分析与实现