背景和⽬的
Rate limiting is used to control the amount of incoming and outgoing traffic to or from a network。
限流需要解决的问题本质：
1. 未知和已知的⽭盾。互联⽹流量有⼀定的突发和未知性，系统⾃⼰的处理能⼒是已知的。
2. 需求和资源的⽭盾。需求可能是集中发⽣的，资源⼀般情况下是稳定的。
3. 公平和安全的⽭盾。流量处理⽅式是公平对待的，但其中部分流量有可能是恶意(或者不友好)的，为了安全和效率考虑是需要限制的。
4 交付和全局的⽭盾。分布式环境下，服务拓扑⽐较复杂，上游的最⼤努⼒交付和全局稳定性考虑是需要平衡的。
常⻅算法
1. 固定窗⼝(FixedWindow)
1.1 基本原理：通过时间段来定义窗⼝，在该时间段中的请求进⾏add操作，超限直接拒绝。
1.2 现实举例：
▪ 旅游景点国庆限流，⼀个⾃然⽇允许多少游客进⼊。
▪ 银⾏密码输错三次锁定，得第⼆天进⾏尝试。
1.3 优势：符合⼈类思维，好理解。两个窗⼝相互独⽴，新的请求进⼊⼀个新的窗⼝⼤概率会满⾜，不会形成饥饿效应，实现简单，快速解决问题。
1.4 劣势：窗⼝临界点可能会出现双倍流量，规则⽐较简单，容易被攻击者利⽤。
1.5 实现⽅式：
type LocalWindow struct {
// The start boundary (timestamp in nanoseconds) of the window.
// [start, start + size)
start int64
// The total count of events happened in the window.
count int64
}
func (l *FixedWindowLimiter) Acquire() bool {
l.mu.Lock()
defer l.mu.Unlock()
now := time.Now()
newCurrStart := now.Truncate(l.interval)
if newCurrStart != l.window.Start() {
l.window.Reset(newCurrStart, 0)
}
if l.window.Count()+1 > int64(l.limit) {
return false
}
l.window.AddCount(1)
return true
}
2. 滑动窗⼝(SlidingWidow)
2.1 基本原理：按请求时间计算出当前窗⼝和前⼀个窗⼝，该时间点滑动⼀个窗⼝⼤⼩得到统计开始的时间点，然后按⽐例计算请求总数后add操作，如果超限拒绝，否则当前窗⼝计数更新。
2.2 现实举例：北京买房从现在起倒推60个⽉连续社保
2.3 优势：⽐较好地解决固定窗⼝交界的双倍流量问题，限流准确率和性能都不错，也不太会有饥饿问题。
2.4 劣势：恶劣情况下突发流量也是有问题的，精确性⼀般。如果要提⾼精确性就要记录log或者维护很多个⼩窗⼝，这个成本会提⾼。
2.5 实现⽅式：
func (lim *Limiter) AllowN(now time.Time, n int64) bool {
lim.mu.Lock()
defer lim.mu.Unlock()
lim.advance(now)
elapsed := now.Sub(lim.curr.Start())
weight := float64(lim.size-elapsed) / float64(lim.size)
count := int64(weight*float64(lim.prev.Count())) + lim.curr.Count()
// Trigger the possible sync behaviour.
defer lim.curr.Sync(now)
if count+n > lim.limit {
return false
}
lim.curr.AddCount(n)
return true
}
// advance updates the current/previous windows resulting from the passage of
time.
func (lim *Limiter) advance(now time.Time) {
// Calculate the start boundary of the expected current-window.
newCurrStart := now.Truncate(lim.size)
diffSize := newCurrStart.Sub(lim.curr.Start()) / lim.size
if diffSize >= 1 {
// The current-window is at least one-window-size behind the expected one.
newPrevCount := int64(0)
if diffSize == 1 {
// The new previous-window will overlap with the old current-window,
// so it inherits the count.
//
// Note that the count here may be not accurate, since it is only a
// SNAPSHOT of the current-window's count, which in itself tends to
// be inaccurate due to the asynchronous nature of the sync behaviour.
newPrevCount = lim.curr.Count()
}
lim.prev.Reset(newCurrStart.Add(-lim.size), newPrevCount)
// The new current-window always has zero count.
lim.curr.Reset(newCurrStart, 0)
}
}
3. 漏桶(LeakyBucket)
3.1 基本原理：所有请求都进⼊⼀个特定容量的桶，桶的流出速度是恒定的，如果桶满则抛弃，满⾜FIFO特性。
3.2 现实举例：旅游景点检票处效率恒定，如果检不过来，⼤家都要排队，假设排队没地⽅排了，那么就只能放弃了。
3.3 优势：输出速率⼀定，能接受突发输⼊流量，但需要排队处理。桶的⼤⼩和速率是⼀定的，所以资源是可以充分利⽤的。
3.4 劣势：容易出现饥饿问题，并且时效性没有保证，突发流量没法很快流出。
3.5 实现⽅式：
type limiter struct {
sync.Mutex
last time.Time //上⼀个请求流出时间
sleepFor time.Duration // 需要等待的时⻓
perRequest time.Duration // 每个请求处理时⻓
maxSlack time.Duration // 突发流量控制阈值
clock Clock
}
// Take blocks to ensure that the time spent between multiple
// Take calls is on average time.Second/rate.
func (t *limiter) Take() time.Time {
t.Lock()
defer t.Unlock()
now := t.clock.Now()
// If this is our first request, then we allow it.
if t.last.IsZero() {
t.last = now
return t.last
}
// sleepFor calculates how much time we should sleep based on
// the perRequest budget and how long the last request took.
// Since the request may take longer than the budget, this number
// can get negative, and is summed across requests.
t.sleepFor += t.perRequest - now.Sub(t.last)
// We shouldn't allow sleepFor to get too negative, since it would mean that
// a service that slowed down a lot for a short period of time would get
// a much higher RPS following that.
if t.sleepFor < t.maxSlack {
t.sleepFor = t.maxSlack
}
// If sleepFor is positive, then we should sleep now.
if t.sleepFor > 0 {
t.clock.Sleep(t.sleepFor)
t.last = now.Add(t.sleepFor)
t.sleepFor = 0
} else {
t.last = now
}
return t.last
}
4. 令牌桶(TokenBucket)
4.1 基本原理：特定速率往⼀个特定容量的桶⾥放⼊令牌，如果桶满，令牌丢弃，所有请求进⼊桶中拿令牌，拿不到令牌丢弃。
4.2 现实举例：旅游景点不控制检票速度(假设是光速)，⽽控制放票速度，有票的⼈直接就可以进。
4.3 优势：可以⽀持突发流量，灵活性⽐较好。
4.4 劣势：实现稍显复杂。
4.5 实现⽅式
type qpsLimiter struct {
limit int32
tokens int32
interval time.Duration
once int32
ticker *time.Ticker
}
// 这⾥允许⼀些误差，直接Store，可以换来更好的性能，也解决了⼤并发情况之下CAS不上的问题 by
chengguozhu
func (l *qpsLimiter) updateToken() {
var v int32
v = atomic.LoadInt32(&l.tokens)
if v < 0 {
v = atomic.LoadInt32(&l.once)
} else if v+atomic.LoadInt32(&l.once) > atomic.LoadInt32(&l.limit) {
v = atomic.LoadInt32(&l.limit)
} else {
v = v + atomic.LoadInt32(&l.once)
}
atomic.StoreInt32(&l.tokens, v)
}
5. 分布式限流
5.1 思路：⽤分布式⽅式实现相关算法，redis替代本地内存，算法逻辑可通过lua来实现。
常⻅场景使⽤
1.下游流量保护，sleep⼤法，leaky_bucket
爬⾍频控，临时通过redis固定窗⼝控制单个IP的访问频率
短信频控(24⼩时最多发送N条)，记录每个⽤⼾的发送记录，滑动窗⼝判断是否满⾜条件
秒杀、活动等常⻅突发流量，进⾏令牌桶控制
稳定性保障重试导致有可能短期流量放⼤，防⽌雪崩，进⾏熔断限流
业务限流，流量打散，⽐如秒杀场景前端进⾏倒计时限制，提前预约保证流量可预知，也能⼤幅减少⽆效流量。
7. TCP流速控制滑动窗⼝,Nginx限流leaky_bucket,linuxtc流量控制token_bucket
欢迎添加笔者weixin：mingyuan_2018
参考链接
https://github.com/uber-go/ratelimitleaky_bucket
