令牌桶算法-常用

[TOC] ### 令牌桶算法 系统会维护一个令牌（`token`）桶，以一个恒定的速度往桶里放入令牌（`token`），这时如果有请求进来想要被处理，则需要先从桶里获取一个令牌（`token`），当桶里没有令牌（`token`）可取时，则该请求将被拒绝服务。令牌桶算法通过控制桶的容量、发放令牌的速率，来达到对请求的限制 

Redis + Lua

``` Lua脚本大致逻辑如下： -- 获取调用脚本时传入的第一个key值（用作限流的 key） local key = KEYS[1] -- 获取调用脚本时传入的第一个参数值（限流大小） local limit = tonumber(ARGV[1]) -- 获取当前流量大小 local curentLimit = tonumber(redis.call('get', key) or "0") -- 是否超出限流 if curentLimit + 1 > limit then -- 返回(拒绝) return 0 else -- 没有超出 value + 1 redis.call("INCRBY", key, 1) -- 设置过期时间 redis.call("EXPIRE", key, 2) -- 返回(放行) return 1 end ```

main.go

``` package main import ( "fmt" "sync" "time" ) type TokenBucket struct { rate int64 //固定的token放入速率, r/s capacity int64 //桶的容量 tokens int64 //桶中当前token数量 lastTokenSec int64 //桶上次放token的时间戳 s lock sync.Mutex } func (l *TokenBucket) Allow() bool { l.lock.Lock() defer l.lock.Unlock() now := time.Now().Unix() l.tokens = l.tokens + (now-l.lastTokenSec)*l.rate // 补充令牌 if l.tokens > l.capacity { l.tokens = l.capacity } l.lastTokenSec = now if l.tokens > 0 { // 还有令牌，领取令牌 l.tokens-- return true } else { // 没有令牌,则拒绝 return false } } func (l *TokenBucket) Set(rate, capacity int64) { l.rate = rate l.capacity = capacity l.tokens = 0 l.lastTokenSec = time.Now().Unix() } func main() { var bucket TokenBucket bucket.Set(10,100) for i:=0; i<100000; i++ { if bucket.Allow() { fmt.Printf("%+v s,i=%d\n", i/100,i ) }else if i%100==0 { fmt.Printf("%+v s\n", i/100 ) } time.Sleep(1*time.Millisecond) } } ```

**优点**: - 令牌桶算法则能够满足这些具有突发特性的流量 - 漏桶算法与令牌桶算法可以结合起来为网络流量提供更大的控制