令牌桶算法
代码地址
前言
在开发高并发系统时，有三把利器用来保护系统：缓存、降级和限流。本文围绕限流，讨论令牌桶相关算法。
背景
令牌桶算法最初来源于计算机网络。在网络传输数据时，为了防止网络拥塞，需限制流出网络的流量，使流量以比较均匀的速度向外发送。
令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。
流程 产生令牌：周期性的以一定速率往令牌桶中增加令牌。如果桶中的令牌数达到桶容量，丢弃多余令牌。消耗令牌：接受请求或输入数据时会消耗桶中的令牌。以请求或消息为单位时，可以一次消耗一个令牌。在网络传输中，消耗令牌的数量可以根据数据包的大小决定。是否通过：桶中的令牌 >= 所需令牌时，请求或者数据包通过，否者被限流。对于被限流的请求或者数据包，可以有不同的处理方式。（1、直接丢弃；2、进队列等待； 3、可以通过，但需要做特殊标记） 算法实现 package token_bucketimport (“fmt””sync””time”)type TokenBucket struct {cap int64avail int64timer *time.Tickermutex *sync.Mutex}func New(interval time.Duration, cap int64) *TokenBucket {if interval < 0 {panic(fmt.Sprintf(“interval %v < 0”, interval))}if cap < 0 {panic(fmt.Sprintf(“cap %v < 0”, cap))}tb := &TokenBucket{cap: cap,avail: cap,timer: time.NewTicker(interval),mutex: &sync.Mutex{},}go tb.daemon()return tb}func (tb *TokenBucket) Stop() {tb.timer.Stop()}func (tb *TokenBucket) Capability() int64 {return tb.cap}func (tb *TokenBucket) Available() int64 {tb.mutex.Lock()defer tb.mutex.Unlock()return tb.avail}func (tb *TokenBucket) TryTake(count int64) bool {if count <= 0 || count > tb.cap {return false}tb.mutex.Lock()defer tb.mutex.Unlock()if count <= tb.avail 美国高防vps {tb.avail -= countreturn true}return false}func (tb *TokenBucket) daemon() {for range tb.timer.C {tb.mutex.Lock()if tb.avail < tb.cap {tb.avail++}tb.mutex.Unlock()}} 总结
可以看出，代码很简单，算法也很简单，具体的使用例子可以看代码地址。
88715351
