限流技术在Go语言项目中用于控制资源访问频率，确保系统的稳定性与高可用性。

核心算法包括下面三种实现方式

漏桶算法：请求进入桶内，按固定速率流出，桶满时丢弃请求，适用于平滑处理场景。

令牌桶算法：定期向桶中添加令牌，请求需消耗令牌才能处理，适用于允许突发流量的场景。

滑动窗口算法：将时间划分为多个小片段统计请求数，避免突发流量问题，确保更精确的限流效果。

01.限流

0、概述

• 在Go语言的项目中，**限流（Rate Limiting）**是一种用于控制资源访问频率的技术
• 限流的目标是限制单位时间内对资源的访问次数，以确保系统的稳定性和高可用性

1、漏桶算法

1）概述

• 原理

  • 漏桶算法的核心思想是将请求放入一个“桶”中
  • 桶中的水会以固定的速率流出，流出的速率代表系统能处理的请求速率
  • 如果桶满了，则新的请求会被丢弃

• 实现步骤：

  • 请求进入时，尝试将请求放入“桶”中

  • 如果桶满了，直接拒绝请求

  • 桶中的请求会以固定速率流出，流出的速率可以理解为处理请求的速率

• 特点：

  • 适用于平滑处理请求的场景，输出请求速率相对稳定。

  • 如果突发流量太大，超出桶容量的请求会被丢弃。

2）实现

package main

import (
	"fmt"
	"time"
)

// LeakyBucket 结构体定义了桶的容量、泄漏速率、当前令牌数和上次请求的时间
type LeakyBucket struct {
	capacity int           // 桶的最大容量（允许的最大请求数）
	rate     time.Duration // 处理请求的时间间隔（泄漏速率）
	tokens   int           // 当前可用的令牌数（可以处理的请求数）
	lastTime time.Time     // 上次处理请求的时间
}

// NewLeakyBucket 创建并初始化一个新的 LeakyBucket
func NewLeakyBucket(capacity int, rate time.Duration) *LeakyBucket {
	return &LeakyBucket{
		capacity: capacity,      // 设置桶的最大容量
		rate:     rate,          // 设置请求处理的速率
		tokens:   capacity,      // 初始时，桶内有最大数量的令牌
		lastTime: time.Now(),    // 记录当前的时间
	}
}

// Allow 方法判断是否允许新的请求通过
func (b *LeakyBucket) Allow() bool {
	now := time.Now()
	// 根据时间流逝计算需要添加的令牌数
	elapsed := now.Sub(b.lastTime)
	b.tokens += int(elapsed / b.rate)  // 根据流逝的时间添加令牌
	if b.tokens > b.capacity {         // 如果令牌超过桶的容量，重置为最大容量
		b.tokens = b.capacity
	}
	b.lastTime = now                   // 更新上次请求的时间

	if b.tokens > 0 {
		b.tokens--                     // 有令牌时，允许请求并消耗一个令牌
		return true
	}
	return false                        // 没有令牌时，拒绝请求
}

func main() {
	bucket := NewLeakyBucket(10, time.Second)  // 创建一个容量为10、速率为每秒处理1个请求的桶
	for i := 0; i < 20; i++ {
		if bucket.Allow() {
			fmt.Println("Request", i, "is allowed")  // 请求被允许
		} else {
			fmt.Println("Request", i, "is denied")   // 请求被拒绝
		}
		time.Sleep(100 * time.Millisecond)           // 每100毫秒发起一次请求
	}
}

2、令牌桶算法

1）概述

• 原理：

  • 令牌桶算法的核心思想是系统会按照固定速率往桶中加入令牌，只有持有令牌的请求才能被处理
  • 如果桶中没有令牌，请求会被拒绝
  • 令牌的生产速率决定了系统允许的处理速率

• 实现步骤：

  • 定期往桶中添加令牌，最多添加到桶的容量上限
  • 每次请求到来时，尝试从桶中取出一个令牌，取到令牌则请求被处理，否则请求被拒绝。
  • 如果桶中没有足够的令牌，直接拒绝请求。

• 特点：

  • 适用于允许突发流量但希望整体速率受限的场景。

  • 能够处理突发流量，因为令牌桶可以积攒一定数量的令牌。

2）实现

package main

import (
	"fmt"
	"time"
)

// TokenBucket 结构体定义了令牌桶的容量、当前令牌数量、生成令牌的速率和上次生成令牌的时间
type TokenBucket struct {
	capacity  int           // 桶的最大容量（最大令牌数）
	tokens    int           // 当前桶中剩余的令牌数
	rate      time.Duration // 生成令牌的速率（间隔时间）
	lastToken time.Time     // 上次生成令牌的时间
}

// NewTokenBucket 初始化一个新的 TokenBucket
func NewTokenBucket(capacity int, rate time.Duration) *TokenBucket {
	return &TokenBucket{
		capacity:  capacity,     // 设置桶的容量
		tokens:    capacity,     // 初始时，桶中令牌数量为最大容量
		rate:      rate,         // 设置生成令牌的速率
		lastToken: time.Now(),   // 记录当前时间作为上次生成令牌的时间
	}
}

// Allow 方法用于判断当前请求是否被允许
func (b *TokenBucket) Allow() bool {
	now := time.Now()
	// 计算从上次生成令牌到现在经过的时间
	elapsed := now.Sub(b.lastToken)
	// 根据经过的时间计算新生成的令牌数量
	newTokens := int(elapsed / b.rate)
	if newTokens > 0 {
		b.tokens += newTokens               // 添加新生成的令牌
		if b.tokens > b.capacity {          // 如果令牌数超过桶的容量，则重置为最大容量
			b.tokens = b.capacity
		}
		b.lastToken = now                   // 更新上次生成令牌的时间
	}

	if b.tokens > 0 {                       // 如果桶中有令牌
		b.tokens--                          // 消耗一个令牌
		return true                         // 允许请求
	}
	return false                            // 否则拒绝请求
}

func main() {
	bucket := NewTokenBucket(10, time.Second)  // 创建一个容量为10、速率为每秒生成1个令牌的桶
	for i := 0; i < 20; i++ {
		if bucket.Allow() {
			fmt.Println("Request", i, "is allowed")  // 请求被允许
		} else {
			fmt.Println("Request", i, "is denied")   // 请求被拒绝
		}
		time.Sleep(100 * time.Millisecond)           // 每100毫秒发起一次请求
	}
}

3、 滑动窗口

• 滑动窗口（Sliding Window）是一种优化的限流算法，它改进了固定窗口限流的缺陷

• 使得流量控制更加平滑，避免了在窗口边界处出现的突发流量问题

1）概述

• 滑动窗口限流的核心思想是对一段时间内的请求进行限制，而不是严格按照固定时间窗口

• 与固定窗口计数器不同，滑动窗口通过在窗口内部细分更小的时间段来计算请求数量，确保限流更加精确和平滑

• 步骤：

  • ① 将时间分为多个较小的时间片段（窗口）。

  • ② 每当有请求到来时，系统会计算当前时间窗口以及前几个时间窗口内的总请求数。

  • ③ 如果总请求数超过了预设的阈值，新的请求会被拒绝。

  • ④ 随着时间的推移，旧的时间片段会逐渐过期，窗口不断滑动。

• 滑动窗口 vs. 其他限流算法

• 与固定窗口相比：
  • 滑动窗口可以避免请求在时间段边界突增的问题，使流量更加平滑
• 与漏桶和令牌桶相比：
  • 漏桶算法和令牌桶算法也能控制流量平滑性
  • 但滑动窗口更适合在需要精确统计一段时间内请求数的场景中使用

2）实现

• 桶的划分：
  • 滑动窗口通过将总窗口分为若干个较小的时间段（ bucketCount），每个时间段会独立计数请求数
• 过期处理：
  • 在每次请求到来时，会判断当前时间段是否已过期
  • 如果过期则清零，确保只统计当前滑动窗口范围内的请求数量
• 平滑限流：
  • 滑动窗口避免了固定窗口算法在时间段边界产生的流量突发问题
  • 通过分段计数和实时更新，可以实现对请求流量的更精细控制

package main

import (
	"fmt"
	"sync"
	"time"
)

// SlidingWindowLimiter 实现了滑动窗口限流器，用于限制在某段时间内的请求数
type SlidingWindowLimiter struct {
	limit       int           // 每个窗口允许的最大请求数
	windowSize  time.Duration // 窗口的总时间大小
	bucketCount int           // 将窗口分成的子时间段数量（即多少个“桶”）
	buckets     []int         // 保存每个桶内的请求数
	mu          sync.Mutex    // 用于多线程并发控制的互斥锁
	lastTime    time.Time     // 记录上次请求处理的时间
}

// NewSlidingWindowLimiter 初始化一个滑动窗口限流器实例
// limit: 窗口内允许的最大请求数
// windowSize: 窗口的总时间大小
// bucketCount: 将窗口分成多少个子时间段（桶）
func NewSlidingWindowLimiter(limit int, windowSize time.Duration, bucketCount int) *SlidingWindowLimiter {
	return &SlidingWindowLimiter{
		limit:       limit,
		windowSize:  windowSize,
		bucketCount: bucketCount,
		buckets:     make([]int, bucketCount), // 初始化桶数组
		lastTime:    time.Now(),               // 设置当前时间为初始时间
	}
}

// getCurrentBucket 获取当前时间对应的桶的索引
// 通过计算当前时间在滑动窗口中的位置来确定落在哪个桶里
func (l *SlidingWindowLimiter) getCurrentBucket() int {
	now := time.Now()
	interval := l.windowSize / time.Duration(l.bucketCount)   // 每个桶的时间间隔
	return int(now.UnixNano()/int64(interval)) % l.bucketCount // 计算当前时间对应的桶索引
}

// Allow 判断是否允许请求
// 检查当前滑动窗口内的请求总数是否超过限制
func (l *SlidingWindowLimiter) Allow() bool {
	l.mu.Lock()         // 锁住，防止并发冲突
	defer l.mu.Unlock() // 函数结束时解锁

	// 获取当前时间和当前桶
	now := time.Now()
	interval := l.windowSize / time.Duration(l.bucketCount)
	currentBucket := l.getCurrentBucket()

	// 如果当前桶超过了时间间隔，重置桶值
	elapsed := now.Sub(l.lastTime)
	if elapsed > interval {
		l.buckets[currentBucket] = 0
	}

	// 计算当前滑动窗口内的所有请求总数
	totalRequests := 0
	for _, count := range l.buckets {
		totalRequests += count
	}

	// 如果请求数在限制以内，允许请求并记录到当前桶中
	if totalRequests < l.limit {
		l.buckets[currentBucket]++ // 该桶的请求数+1
		l.lastTime = now           // 更新处理时间
		return true                // 请求通过
	}
	return false // 请求被拒绝
}

func main() {
	// 初始化限流器，允许每秒5个请求，将窗口分成10个子时间段
	limiter := NewSlidingWindowLimiter(5, time.Second, 10)

	// 模拟 20 个请求，每隔 100 毫秒发起一次
	for i := 0; i < 20; i++ {
		if limiter.Allow() {
			fmt.Println("Request", i, "is allowed") // 请求通过
		} else {
			fmt.Println("Request", i, "is denied")  // 请求被拒绝
		}
		time.Sleep(100 * time.Millisecond) // 间隔 100 毫秒发送下一个请求
	}
}