2025-07-01代码1 分钟

限流算法

为什么限流，因为单一用户占用过多资源导致其他用户的服务质量。好处：

防止资源耗尽
降低服务器托管成本
提供针对 DDos 的基本保护

1. 令牌桶

桶中保存固定数量的令牌
令牌以固定速率添加到存储桶中
收到请求
- 如果令牌可用，则会将其从存储桶中删除并允许请求。
- 如果没有可用的令牌，则请求将被拒绝或延迟。
如果令牌可用，则允许偶尔进行短暂的突发

type TokenBucket struct {
	mu         sync.Mutex    // 保护并发访问
	capacity   int           // 桶的最大容量
	tokens     float64       // 当前可用令牌数量（可以是小数，表示部分令牌）
	refillRate float64       // 每秒补充的令牌数
	lastTime   time.Time     // 上次补充令牌的时间
}

func (b *TokenBucket) Allow() bool {
	b.mu.Lock()
	defer b.mu.Unlock()

	now := time.Now()
	elapsed := now.Sub(b.lastTime).Seconds()

	// 根据时间流逝计算应该补充多少令牌
	b.tokens += elapsed * b.refillRate
	if b.tokens > float64(b.capacity) {
		b.tokens = float64(b.capacity)
	}
	b.lastTime = now

	// 如果有足够的令牌，消费一个令牌并允许请求
	if b.tokens >= 1 {
		b.tokens -= 1
		return true
	}
	// 否则拒绝
	return false
}

2. 漏桶

将其视为以固定速率泄漏的桶
传入请求将添加到漏桶中
请求将以恒定速率（泄漏）处理
如果新请求到达时存储已满，则很久丢弃该请求
平滑连拍;以稳定的速率输出请求

type LeakyBucket struct {
	mu        sync.Mutex      // 并发保护
	capacity  int             // 桶的最大容量（允许排队的请求数）
	interval  time.Duration   // 出水间隔时间（比如每100ms漏一个请求）
	lastLeak  time.Time       // 上次出水时间
	queueSize int             // 当前排队中的请求数量
}

// 这里应该还有一个方法是，将漏桶的请求发送处理
// 但是为了统一就是这样写了
func (b *LeakyBucket) Allow() bool {
	b.mu.Lock()
	defer b.mu.Unlock()

	now := time.Now()
	elapsed := now.Sub(b.lastLeak)

	// 计算漏掉了多少请求
	leaked := int(elapsed / b.interval)
	if leaked > 0 {
		// 移除排队请求
		if leaked > b.queueSize {
			b.queueSize = 0
		} else {
			b.queueSize -= leaked
		}
		b.lastLeak = now
	}

	// 如果还没超出桶的容量，允许请求并加入队列
	if b.queueSize < b.capacity {
		b.queueSize++
		return true
	}
	// 否则拒绝
	return false
}

3. 固定窗口计数器

时间被划分为固定大小的窗口
计数器跟踪当前窗口中每个客户端/IP 的请求数
如果计数超过限制，则进一步的请求将被拒绝，直到下一个窗口
简单高效，但允许在结束/开始时出现突发流量峰值

type FixedWindowLimiter struct {
	mu         sync.Mutex       // 用于并发安全
	limit      int              // 每个时间窗口允许的最大请求数
	windowSize time.Duration    // 时间窗口大小（例如1秒）
	counter    int              // 当前窗口内的请求计数
	windowTime time.Time        // 当前窗口开始的时间
}

func (l *FixedWindowLimiter) Allow() bool {
	l.mu.Lock()
	defer l.mu.Unlock()

	now := time.Now()

	// 如果当前时间已超出窗口范围，重置窗口
	if now.Sub(l.windowTime) > l.windowSize {
		l.windowTime = now
		l.counter = 0
	}

	// 计数未超过上限，允许请求
	if l.counter < l.limit {
		l.counter++
		return true
	}
	// 达到上限，拒绝请求
	return false
}

4. 推拉窗计数器

保留每个请求的时间戳日志
当收到请求是，将检查日志以计算在过去 x 秒内发出的请求数
如果低于限制，则允许并记录请求，否则，它将被拒绝

type SlidingWindowLog struct {
	mu       sync.Mutex       // 并发安全
	limit    int              // 在窗口期内允许的最大请求数
	window   time.Duration    // 滑动窗口大小
	requests []time.Time      // 记录请求时间戳的切片
}

func (l *SlidingWindowLog) Allow() bool {
	l.mu.Lock()
	defer l.mu.Unlock()

	now := time.Now()
	threshold := now.Add(-l.window)

	// 移除窗口外的旧请求记录
	filtered := []time.Time{}
	for _, t := range l.requests {
		if t.After(threshold) {
			filtered = append(filtered, t)
		}
	}
	l.requests = filtered

	// 如果请求数未达到限制，记录当前时间并允许请求
	if len(l.requests) < l.limit {
		l.requests = append(l.requests, now)
		return true
	}
	// 否则拒绝
	return false
}

0 条

1. 令牌桶

2. 漏桶

3. 固定窗口计数器

4. 推拉窗计数器

评论