漏桶算法

小鱼儿 2022-03-09 09:40 215阅读 0赞

近期在研究Jaeger，Jaeger中有一种采集策略是速率限制类型，内部使用的是漏桶算法，在这里研究了下Jaeger漏桶算法的实现原理，自己仿照其实现了一个rateLimiter，并进行了相关测试，下面是主要实现。

*  lck：lck是互斥锁，主要用来防止并发情况下产生错误。
 *  rate：速率，即接口每秒限制多少个请求。在这里也就是水滴从漏桶中流出的速度，同时也是余量增加的速度。
 *  balance：漏桶的空闲余量，会随着漏桶滴水逐渐变大；如果将请求添加到漏桶中，会逐渐变小。当请求到来时，如果余量不足1，那么表明不能容下当前的请求，当前的请求会被拒绝。
 *  limit：漏桶的最大容量。
 *  lastTime：上次调用Check函数的时间。用于计算时间差dur，然后计算这段时间漏桶流出的水w，增加的余量=流出的水量w=时间\*速率=dur\*rate。

rateLimiter实现代码：

package ratelimiter
    
    import (
    	"sync"
    	"time"
    )
    
    type rateLimiter struct {
    	lck      *sync.Mutex
    	rate     float64   //最大速率限制
    	balance  float64   //漏桶的余量
    	limit    float64   //漏桶的最大容量限制
    	lastTime time.Time //上次检查的时间
    }
    
    func NewRateLimiter(limitPerSecond int, balance int) *rateLimiter {
    	return &rateLimiter{
    		lck:      new(sync.Mutex),
    		rate:     float64(limitPerSecond),
    		balance:  float64(balance),
    		limit:    float64(balance),
    		lastTime: time.Now(),
    	}
    }
    
    func (r *rateLimiter) Check() bool {
    	ok := false
    	r.lck.Lock()
    	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.limit {
    		r.balance = r.limit
    	}
    	if r.balance >= 1 { //漏桶余量足够容下当前的请求
    		r.balance -= 1
    		ok = true
    	}
    	r.lck.Unlock()
    	return ok
    }

单元测试代码：

package ratelimiter
    
    import (
    	"fmt"
    	"testing"
    	"time"
    )
    
    func TestRateLimiter_Check(t *testing.T) {
    	limiter := NewRateLimiter(10, 1)
    	start := time.Now()
    	count := 0
    	for i := 0; i < 1e3; i++ {
    		if limiter.Check() {
    			fmt.Println(i)
    			count++
    		}
    		time.Sleep(time.Millisecond)
    	}
    	fmt.Println("count:", count)
    	fmt.Println(time.Now().Sub(start).Seconds())
    }

测试结果：**每秒限制10个，1.3秒接受了13个请求，加上一开始填满桶的一个，共14个。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpeXVubG9uZzQx_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpeXVubG9uZzQx_size_16_color_FFFFFF_t_70]: /images/20220309/9ee03552f5794e539397357ebf36c72b.png