在开发高并发系统时，为了保证系统的高可用和稳定性，常见的有以下几种策略：
- 缓存：提升系统访问速度，增大系统处理容量
- 降级：资源是有限的，但请求可以看成是无限的，当流量高峰的时候，我们可以适当的延迟处理一些非核心业务，甚至不处理，把资源让给核心业务，待高峰期过后或故障解决后再打开。
- 熔断：当某些服务不可用的时候或者达到某个阀值，例如5s内调用失败20次，我们可以选择不调用该服务，直接返回，等该服务恢复后重新调用
- 限流：通过对并发（或者一定时间窗口内）请求进行限速来保护系统，一旦达到限制速率则拒绝服务（定向到错误页或告知资源没有了）、排队等待（比如秒杀、评论、下单）、降级（返回兜底数据或默认数据）
一般来说，限流的常用处理手段有：
- 计数器
- 滑动窗口
- 漏桶
- 令牌桶
计数器
计数器是一种比较简单粗暴的限流算法：
在一段时间间隔内，对请求进行计数，与阀值进行比较判断是否需要限流，一旦到了时间临界点，将计数器清零。
type LimitRate struct {
rate int //阀值
begin time.Time //计数开始时间
cycle time.Duration //计数周期
count int //收到的请求数
lock sync.Mutex //锁
}
func (limit *LimitRate) Allow() bool {
limit.lock.Lock()
defer limit.lock.Unlock()
// 判断收到请求数是否达到阀值
if limit.count == limit.rate-1 {
now := time.Now()
// 达到阀值后，判断是否是请求周期内
if now.Sub(limit.begin) >= limit.cycle {
limit.Reset(now)
return true
}
return false
} else {
limit.count++
return true
}
}
func (limit *LimitRate) Set(rate int, cycle time.Duration) {
limit.rate = rate
limit.begin = time.Now()
limit.cycle = cycle
limit.count = 0
}
func (limit *LimitRate) Reset(begin time.Time) {
limit.begin = begin
limit.count = 0
}
计数器算法存在“时间临界点”缺陷。比如每一分钟限制100个请求，可以在00:00:00-00:00:58秒里面都没有请求，在00:00:59瞬间发送100个请求，这个对于算法来是允许的，然后在00:01:00再次发送100个请求，意味着在短短1s内发送了200个请求，如果量更大呢，系统可能会承受不住瞬间流量，导致系统崩溃。（如下图所示）
滑动窗口
针对计数器算法的缺陷，滑动窗口做了优化，将时间进行划片，并随着时间流逝，进行移动，固定数量可以移动固定的格子，进行计数并判断阀值。
格子的具体数量影响滑动窗口算法的精度，时间片的概念其实不能根本解决临界点的问题。
原理和计数器类似，不做进一步引申
漏桶
描述如下：
1、一个固定容量的漏桶，按照固定速率流出水滴
2、如果桶是空的，没有水滴流出
3、水滴以任意速率的流速入桶
4、如果水超过桶的容量，则溢出（请求被丢弃）
通俗的讲，我们有一个固定容量的桶，有水流入，也有水流出。对于流进来的水（请求）来说，我们无法预计一共会有多少水流进来，也无法估计流入水的速度。但是对于流出去的水来说，我们这个桶是可以按照固定流出的速率。从而达到流量控制的效果。
// 漏桶
// 一个固定大小的桶，请求按照固定的速率流出
// 如果桶是空的，不需要流出请求
// 请求数大于桶的容量，则抛弃多余请求
type LeakyBucket struct {
rate float64 // 每秒固定流出速率
capacity float64 // 桶的容量
water float64 // 当前桶中请求量
lastLeakMs int64 // 桶上次漏水微秒数
lock sync.Mutex // 锁
}
func (leaky *LeakyBucket) Allow() bool {
leaky.lock.Lock()
defer leaky.lock.Unlock()
now := time.Now().UnixNano() / 1e6
// 计算剩余水量,两次执行时间中需要漏掉的水
leakyWater := leaky.water - (float64(now-leaky.lastLeakMs) * leaky.rate / 1000)
leaky.water = math.Max(0, leakyWater)
leaky.lastLeakMs = now
if leaky.water+1 <= leaky.capacity {
leaky.water++
return true
} else {
return false
}
}
func (leaky *LeakyBucket) Set(rate, capacity float64) {
leaky.rate = rate
leaky.capacity = capacity
leaky.water = 0
leaky.lastLeakMs = time.Now().UnixNano() / 1e6
}
令牌桶
由于漏桶的出水的速率是恒定的，如果爆发了大流量的话，将会有大量的请求被丢弃（溢出），为了解决这个问题，令牌桶进行了算法改进，算法描述如下：
1、有一个固定容量的桶，桶一开始是空的。
2、以固定的速率向桶内填充令牌，到达桶的容量后，多余令牌将被丢弃。
3、每一个请求过来，就会尝试从令牌桶中移除一个令牌，如果没有令牌，请求无法通过。
在正常请求下，桶中会积累一定量的令牌，这就使这个算法支持一定程度的大流量访问。也就是说，如果桶中有100个令牌，那就可以瞬时允许100个请求通过。从这点来说，对用户比较友好，因此业内大部分用的是该算法。
当然，不管是令牌桶拿不到令牌被拒绝还是漏桶满了被抛弃，都是为了保证大部分流量的正常访问，牺牲少部分流量，这个是合理的。
type TokenBucket struct {
rate int64 //固定的token放入速率, r/s
capacity int64 //桶的容量
tokens int64 //桶中当前token数量
lastTokenSec int64 //桶上次放token的时间戳 s
lock sync.Mutex
}
func (bucket *TokenBucket) Allow() bool {
bucket.lock.Lock()
defer bucket.lock.Unlock()
now := time.Now().Unix()
bucket.tokens = bucket.tokens + (now-bucket.lastTokenSec)*bucket.rate // 先添加令牌
if bucket.tokens > bucket.capacity {
bucket.tokens = bucket.capacity
}
bucket.lastTokenSec = now
if bucket.tokens > 0 {
// 还有令牌，领取令牌
bucket.tokens--
return true
} else {
// 没有令牌,则拒绝
return false
}
}
func (bucket *TokenBucket) Set(rate, cap int64) {
bucket.rate = rate
bucket.capacity = cap
bucket.tokens = 0
bucket.lastTokenSec = time.Now().Unix()
}
引申
不同的限流算法没有所谓的谁比谁更优，主要还是看具体业务情况，比如令牌桶我们更多的是用于保护自身，而漏桶的限制流速则可以用于保护他人。
注：资料收集，侵权请联系
