ThinkerQAQ

NOTE

2.4 如何设计一个限流系统

1. 什么是限流 - 高并发系统的三大利器之一，限制访问速率（区别于Semaphore限制的是访问数量） - 技术层面的限流：服务A调用服务B，服务B为了防止请求量过大，限制访问速率 - 业务层面的限流：限制某人每天只能使用n次 2. 为什么需要限流 - 后端服务的处理能力是有限的，如果突发流量暴增

系统设计创建于 更新于 historical

这是历史学习笔记，可能存在过时或不完整的理解。

1. 什么是限流

  • 高并发系统的三大利器之一，限制访问速率（区别于Semaphore限制的是访问数量）
  • 技术层面的限流：服务A调用服务B，服务B为了防止请求量过大，限制访问速率
  • 业务层面的限流：限制某人每天只能使用n次

2. 为什么需要限流

  • 后端服务的处理能力是有限的，如果突发流量暴增，后端服务很容易就被打垮

3. 常用限流算法

3.1. 基于时间窗口的限流算法

3.1.1. 固定窗口（计数器）

3.1.1.1. 定义
  • 计数器的容量固定
    • 每来一个请求计数器+1，到达容量后拒绝后面的请求
  • 流入速率任意，流出速率任意
    • 每来一个请求就处理一个
3.1.1.2. 特点
  • 优点：
    • 易于实现；并且空间复杂度低
  • 缺点：
    • 临界突发流量问题
      • 假设限流为每分钟120，有一个恶意用户，他在0:59:59时，瞬间发送了120个请求；然后时间到了1:00:00，又瞬间发送了120个请求，那么应用在1秒里面需要处理恶意用户的的240个请求。

3.1.2. 滑动窗口

3.1.2.1. 定义
  • 相对于计数器的固定窗口，滑动窗口是把固定窗口分成多个格子，每次向后移动一小格
3.1.2.2. 特点
  • 优点：
    • 解决了临界突发流量问题
      • 假设限流为每分钟120，窗口分为60个，也就是每秒钟2个，有一个恶意用户，他在0:59:59时，瞬间发送了120个请求；然后时间到了1:00:00，又瞬间发送了120个请求，但是只有2个会被处理，那么应用在1秒里面需要处理恶意用户的的122个请求。
  • 缺点：
    • 实现较计数器复杂，并且要维护窗口空间复杂度高
    • 无法平滑流量
      • 假设限流为每分钟120，窗口分为60个，也就是每秒钟2个，我们希望系统也是以每秒钟2个的速度处理请求，有一个恶意用户，他在0:59:59时，瞬间发送了120个请求；那么应用在1秒里面需要处理恶意用户的的120个请求。

3.2. 漏桶算法

3.2.1. 定义

  • 桶的容量固定
    • 每来一个请求丢入桶中，如果请求量超过了桶的容量，那么丢弃多余的请求
  • 流入速率任意，流出速率恒定
    • 每来一个请求丢进任务队列中，写一个定时器隔一段时间取出请求执行
  • 本质上就是消息队列削峰

3.2.2. 特点

  • 优点：
    • 解决了临界突发流量问题
      • 假设限流为每分钟120，那么漏桶容量为120，有一个恶意用户，他在0:59:59时，瞬间发送了120个请求，这120个请求会缓存到漏桶中，然后会有一个后台线程在整秒时取出2个的速度取出请求处理；然后时间到了1:00:00，又瞬间发送了120个请求，但是只有2个会缓存到漏桶中，多余的拒绝，那么应用在1秒里面需要处理恶意用户的的2个请求。
    • 平滑流量。
      • 假设限流为每分钟120，那么漏桶容量为120，我们希望系统以每秒钟2个的速度处理请求，有一个恶意用户，他在0:59:59时，瞬间发送了120个请求，这120个请求会缓存到漏桶中，然后会有一个后台线程在整秒时取出2个请求处理，那么应用在1秒里面需要处理恶意用户的的2个请求。
  • 缺点：
    • 空间复杂度高。
    • 无法应对突发流量延迟问题
      • 假设限流为每分钟120，那么漏桶容量为120，我们希望系统最多以每秒钟10个的速度处理请求。在1:00:00有10个请求过来，那么10个都可以处理，但得缓存到漏桶中，后台线程在整秒时取出2个请求处理，那么10个请求中的最后2个得等到1:00:05才能处理

3.3. 令牌桶算法

3.3.1. 定义

  • 桶的容量固定
    • 每隔一段时间丢进一定数量的令牌，满了则丢弃多余的令牌
  • 流入速率恒定，流出速率任意
    • 每来一个请求先要在桶里获取一个令牌，没有的话拒绝服务

3.3.2. 特点

  • 优点
    • 解决了临界突发流量问题
      • 假设限流为每分钟120，令牌桶在整秒时生成2个，有一个恶意用户，他在0:59:59时，瞬间发送了120个请求，令牌只有2个那么只有2个可以处理，多余的拒绝；然后时间到了1:00:00，又瞬间发送了120个请求，令牌只有2个那么只有2个可以处理，多余的拒绝，那么应用在1秒里面需要处理恶意用户的的2个请求。
    • 平滑流量。不管请求的速度多快，我都是均速处理
      • 假设限流为每分钟120，令牌桶在整秒时生成2个，我们希望系统以每秒钟2个的速度处理请求，有一个恶意用户，他在0:59:59时，瞬间发送了120个请求，令牌只有2个那么只有2个可以处理，多余的拒绝，那么应用在1秒里面需要处理恶意用户的的2个请求。
    • 应对突发流量延迟问题
      • 假设限流为每分钟120，令牌桶在整秒时生成2个，我们希望系统最多以每秒钟10个的速度处理请求，那么令牌桶的容量为10。在0:59:54-1:00:00，没有请求过来，时间经过了6秒，那么令牌桶里可以存储min(6*2,10)=10个令牌，此时有10个请求过来，那么都可以处理，并且不会有延迟
  • 缺点：
    • 存储令牌和发放令牌实现略复杂

3.4. 对比

固定窗口 滑动窗口 漏桶算法 令牌桶算法
临界突发流量问题 用户通过在时间窗口的重置节点处突发请求，瞬时流量可能为2n 用户通过在时间窗口的重置节点处突发请求，瞬时流量可能为n+n/窗口数 无 无
流量颠簸问题 有 有 无。不管请求的速度多快，我都是均速处理 无
突发流量延迟问题 无 无 有。要缓存流量，所以会导致流量延迟增加，不适用低延迟场景 无。可以限制一个令牌的最大容量应对突发流量

4. 实现

4.1. Golang

4.1.1. 接口

type IRateLimiter interface {
	Set(reqCount int64) bool
	Get() int64
	Reset()
}

4.1.2. 计数器

package ratelimiter

import (
	"sync"
	"time"
)

type Counter struct {
	//interval秒内总共能处理的请求数为rate
	interval int64
	rate     int64
	// 计数器
	counter int64
	//上一次请求处理的时间
	lastTime int64
	lock     sync.Mutex
}

func NewCounter(rate int64, interval int64) *Counter {
	return &Counter{
		interval: interval,
		rate:     rate,
		lastTime: time.Now().Unix(),
	}
}

func (b *Counter) Set(reqCount int64) bool {
	b.lock.Lock()
	defer b.lock.Unlock()

	now := time.Now().Unix()
	if now > b.lastTime+b.interval {
		b.lastTime = now
		b.counter = 0
	}

	if b.counter+reqCount <= b.rate {
		b.counter += reqCount
		return true
	}
	return false
}

func (b *Counter) Get() int64 {
	b.lock.Lock()
	defer b.lock.Unlock()
	if b.lastTime+b.interval < time.Now().Unix() {
		return b.rate
	}
	return b.rate - b.counter
}

func (b *Counter) Reset() {
	b.lock.Lock()
	defer b.lock.Unlock()
	b.lastTime = time.Now().Unix()
	b.counter = 0
}

4.1.3. 漏桶

package ratelimiter

import (
	"sync"
	"time"
)

type LeakyBucket struct {
	//水流流出的速度
	rate int64
	//漏桶总水量（总共能处理的请求数）
	capacity int64
	//漏桶剩下的水量（剩余未处理请求数）
	remainCapacity int64
	//上一次请求处理的时间
	lastTime int64
	lock sync.Mutex
}

func NewLeakyBucket(rate int64, capacity int64) *LeakyBucket {
	return &LeakyBucket{rate: rate, capacity: capacity}
}

func (b *LeakyBucket) Set(reqCount int64) bool {
	b.lock.Lock()
	defer b.lock.Unlock()

	now := time.Now().Unix()

	processCount := (now - b.lastTime) * b.rate
	b.remainCapacity = Max(b.remainCapacity-processCount, 0)

	if b.remainCapacity + reqCount <= b.capacity {
		b.remainCapacity += reqCount
		b.lastTime = now
		return true
	}
	return false
}

func (b *LeakyBucket) Get() int64 {
	b.lock.Lock()
	defer b.lock.Unlock()
	return b.capacity - b.remainCapacity
}

func (b *LeakyBucket) Reset() {
	b.lock.Lock()
	defer b.lock.Unlock()
	b.lastTime = 0
	b.remainCapacity = b.capacity
}

func Max(data ...int64) int64 {
	max := data[0]
	for i := 1; i < len(data); i++ {
		if data[i] > max {
			max = data[i]
		}
	}
	return max
}

4.1.4. 令牌桶

package ratelimiter

import (
	"sync"
	"time"
)

type TokenBucket struct {
	//生成token的速度，单位s
	rate int64
	//token总量
	capacity int64
	//未使用的token量
	remainToken int64
	//上一次请求处理的时间，单位s
	lastTime int64
	lock     sync.Mutex
}

func (b *TokenBucket) Get() int64 {
	b.lock.Lock()
	defer b.lock.Unlock()
	return b.genToken(time.Now().Unix())
}

func (b *TokenBucket) Reset() {
	b.lock.Lock()
	defer b.lock.Unlock()
	b.lastTime = 0
	b.remainToken = 0
}

func NewTokenBucket(rate int64, capacity int64) *TokenBucket {
	return &TokenBucket{rate: rate, capacity: capacity}
}

func (b *TokenBucket) Set(reqCount int64) bool {
	b.lock.Lock()
	defer b.lock.Unlock()
	now := time.Now().Unix()

	b.remainToken = b.genToken(now)

	if b.remainToken >= reqCount {
		b.remainToken -= reqCount
		b.lastTime = now
		return true
	}
	return false
}

//更新token量
func (b *TokenBucket) genToken(now int64) int64 {
	generateToken := (now - b.lastTime) * b.rate
	return Min(b.remainToken+generateToken, b.capacity)
}

func Min(data ...int64) int64 {
	min := data[0]
	for i := 1; i < len(data); i++ {
		if data[i] < min {
			min = data[i]
		}
	}
	return min
}

4.2. Redis RateLimiter

Redis RateLimiter.md

4.3. Google Guava RateLimiter

RateLimiter.md（关联笔记尚未公开）

5. 参考