前言

要做一个限流实现，对新建，并发，吞吐等流量数据进行限制。在此之前，知道Spring是有些中间件能够实现限流的，比如Hystrix ，Sentinel，RateLimiter这些的。但是这些是已经实现的SDK了，只管使用倒是简单，对于里面具体的实现原理就是不清楚了。正好看看有些常用的限流算法吧

算法

固定窗口（Fixed Window）

原理

固定窗口限流算法的核心思想是将时间划分为固定长度的窗口（例如：每分钟、每秒等），在一个窗口内，如果请求数达到或超过预定的限制（比如每分钟最多允许 1000 次请求），则拒绝后续请求。当窗口结束时，计数器会被重置，新的窗口开始。

工作流程

  1. 每个请求到来时，记录当前时间并计算当前所属的窗口。
  2. 在每个窗口内，记录请求次数。
  3. 如果请求次数超过阈值，拒绝该请求。
  4. 每当一个窗口结束，计数器会被重置。

优点

  • 实现简单，容易理解。

缺点

  • 会产生“突发”请求的情况：如果很多请求集中在窗口的开始部分，可能会导致流量瞬间过载，因为窗口内的请求数没有进行平滑控制。

算法实现

  1. 设定每个窗口的时间长度（如 1 秒、1 分钟等）和最大请求数（如每秒最多允许 100 个请求）。
  2. 每当请求到来时，检查当前时间和上一个请求的时间是否超过了窗口时长。如果超过了，则重新开始计数；否则，判断当前请求是否超出了限制。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package main

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

// 定义一个结构体来存储限流器的状态
type FixedWindowLimiter struct {
	maxRequests int           // 每个窗口允许的最大请求数
	windowSize  time.Duration // 窗口大小，单位为时间，如1秒
	count       int           // 当前窗口内的请求数
	lastReset   time.Time     // 上次窗口重置的时间
	mu          sync.Mutex    // 用于保护并发访问
}

// 创建一个新的FixedWindowLimiter实例
func NewFixedWindowLimiter(maxRequests int, windowSize time.Duration) *FixedWindowLimiter {
	return &FixedWindowLimiter{
		maxRequests: maxRequests,
		windowSize:  windowSize,
		count:       0,
		lastReset:   time.Now(),
	}
}

// 判断是否允许当前请求
func (limiter *FixedWindowLimiter) Allow() bool {
	limiter.mu.Lock()
	defer limiter.mu.Unlock()

	// 获取当前时间
	now := time.Now()

	// 如果当前时间已经超过了窗口的最大时长，重置计数器
	if now.Sub(limiter.lastReset) >= limiter.windowSize {
		limiter.lastReset = now
		limiter.count = 0
	}

	// 如果当前请求数小于最大请求数，则允许请求
	if limiter.count < limiter.maxRequests {
		limiter.count++
		return true
	}

	// 超过了最大请求数，拒绝请求
	return false
}

func main() {
	// 创建一个限流器，每秒最多允许 5 次请求
	limiter := NewFixedWindowLimiter(5, time.Second)

	// 模拟 10 个请求
	for i := 0; i < 10; i++ {
		if limiter.Allow() {
			fmt.Printf("Request %d: Allowed\n", i+1)
		} else {
			fmt.Printf("Request %d: Denied\n", i+1)
		}
		// 为了模拟请求间隔，可以休眠 100 毫秒
		time.Sleep(100 * time.Millisecond)
	}
}

总结

  • 固定窗口算法适用于流量控制简单的场景，但由于其窗口内请求数的集中性，可能会出现突发流量问题。
  • Go 实现的这个例子展示了如何基于时间窗口来限制请求，适合简单的限流需求。对于更高效和复杂的流量控制，可能需要考虑滑动窗口或令牌桶等算法。

滑动窗口

原理

滑动窗口限流算法是对固定窗口算法的改进，解决了固定窗口的“突发流量”问题。与固定窗口不同，滑动窗口的时间窗口是不断滑动的，窗口内的请求数是动态变化的。

工作原理

  • 时间窗口不再是固定的，而是通过滑动窗口来控制流量。
  • 每当请求到来时，会在时间线上记录请求的时间戳，然后计算当前请求是否超出了当前窗口的请求限制。
  • 窗口内的请求数是在一个滑动的时间区间内进行统计的。

优点

  • 避免了固定窗口产生的流量集中问题，能平滑流量的波动。

缺点

  • 实现相对复杂，需要对请求时间进行记录和管理。

算法实现

  • 使用一个数据结构（如队列、双向链表等）记录请求的时间戳。
  • 每当一个请求到来时，检查队列中记录的时间戳是否在有效的时间窗口内。如果超出了时间窗口，删除超时的请求。
  • 如果队列中的请求数超过了最大请求数，则拒绝请求；否则，允许请求。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package main

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

type SlidingWindowLimiter struct {
	maxRequests int           // 每个窗口内最大请求数
	windowSize  time.Duration // 滑动窗口的时间大小
	requests    []time.Time   // 存储请求的时间戳
	mu          sync.Mutex    // 用于保护并发访问
}

// 创建一个新的SlidingWindowLimiter实例
func NewSlidingWindowLimiter(maxRequests int, windowSize time.Duration) *SlidingWindowLimiter {
	return &SlidingWindowLimiter{
		maxRequests: maxRequests,
		windowSize:  windowSize,
		requests:    []time.Time{},
	}
}

// 判断是否允许当前请求
func (limiter *SlidingWindowLimiter) Allow() bool {
	limiter.mu.Lock()
	defer limiter.mu.Unlock()

	// 获取当前时间
	now := time.Now()

	// 移除超出窗口时间的请求
	threshold := now.Add(-limiter.windowSize)
	var validRequests []time.Time
	for _, t := range limiter.requests {
		if t.After(threshold) {
			validRequests = append(validRequests, t)
		}
	}

	// 更新请求队列
	limiter.requests = validRequests

	// 如果请求数小于最大请求数，则允许请求
	if len(limiter.requests) < limiter.maxRequests {
		limiter.requests = append(limiter.requests, now) // 将当前请求的时间戳加入队列
		return true
	}

	// 超过了最大请求数，拒绝请求
	return false
}

func main() {
	// 创建一个限流器，每秒最多允许 5 次请求
	limiter := NewSlidingWindowLimiter(5, time.Second)

	// 模拟 10 个请求
	for i := 0; i < 10; i++ {
		if limiter.Allow() {
			fmt.Printf("Request %d: Allowed\n", i+1)
		} else {
			fmt.Printf("Request %d: Denied\n", i+1)
		}
		// 为了模拟请求间隔，可以休眠 100 毫秒
		time.Sleep(100 * time.Millisecond)
	}
}

总结

  • 滑动窗口算法相较于固定窗口，它能够平滑地控制流量，并且避免了固定窗口可能产生的请求冲击问题。
  • 通过维护一个请求时间戳队列，滑动窗口算法可以动态地调整时间窗口的大小，确保在给定时间范围内的请求数不会超过预定阈值。
  • 在 Go 实现中，我们使用了时间戳队列来记录每个请求的时间，并在每个请求到来时检查是否可以加入队列。

漏桶算法

原理

漏桶算法是一种常见的流量控制算法，模拟漏水桶的行为来处理流量。它的核心思想是：无论流量到来有多快，系统都会以恒定的速率进行处理。如果流量过快，桶满了，就会丢弃多余的请求。

  • 漏桶：可以理解为一个桶，水不断流入桶中，但水只能以固定的速度从桶底漏出。
  • 如果水流入的速度超过桶漏水的速度，桶就会被填满，超过容量的水就会被丢弃。
  • 这样，漏桶算法可以平滑地控制流量输出，避免系统因为瞬时请求过多而过载。

工作流程

  1. 请求被加入到一个桶中（表示流入漏桶）。
  2. 桶内的水（请求）会以固定的速度漏出（请求被处理）。
  3. 如果水流入的速度大于漏水的速度，桶就会充满，当请求超过桶的容量时，超出部分将被丢弃或拒绝。
  4. 如果桶未满，请求被接受并继续漏出。

优点

  • 平滑流量：能够平滑处理流量，无论请求是突发还是平稳，都可以维持稳定的处理速度。
  • 简单：漏桶算法简单、易于理解，适用于需要按固定速率处理请求的场景。

缺点

  • 丢失请求：如果桶满了，新请求会被丢弃，可能导致部分请求无法被处理。
  • 不能处理突发流量：当请求流量波动较大时，算法会丢失大量请求。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package main

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

type LeakyBucketLimiter struct {
	capacity   int           // 漏桶的容量
	waterLevel int           // 当前水位（请求数量）
	drainRate  time.Duration // 漏桶的排水速率（每秒多少请求）
	lastDrain  time.Time     // 上次排水的时间
	mu         sync.Mutex    // 用于保护并发访问
}

// 创建一个新的 LeakyBucketLimiter 实例
func NewLeakyBucketLimiter(capacity int, drainRate time.Duration) *LeakyBucketLimiter {
	return &LeakyBucketLimiter{
		capacity:  capacity,
		waterLevel: 0,
		drainRate: drainRate,
		lastDrain: time.Now(),
	}
}

// 判断是否允许当前请求
func (limiter *LeakyBucketLimiter) Allow() bool {
	limiter.mu.Lock()
	defer limiter.mu.Unlock()

	// 获取当前时间
	now := time.Now()

	// 计算自上次排水以来应该漏掉多少水
	elapsed := now.Sub(limiter.lastDrain)
	drainedWater := int(elapsed / limiter.drainRate)

	// 更新当前水位，不能超过桶的容量
	limiter.waterLevel -= drainedWater
	if limiter.waterLevel < 0 {
		limiter.waterLevel = 0
	}

	// 如果当前水位小于容量，允许请求，并将水位增加
	if limiter.waterLevel < limiter.capacity {
		limiter.waterLevel++
		limiter.lastDrain = now
		return true
	}

	// 如果水位已经达到容量，拒绝请求
	return false
}

func main() {
	// 创建一个漏桶限流器，容量为 5，漏水速率为每秒 1 个请求
	limiter := NewLeakyBucketLimiter(5, time.Second)

	// 模拟 10 个请求
	for i := 0; i < 10; i++ {
		if limiter.Allow() {
			fmt.Printf("Request %d: Allowed\n", i+1)
		} else {
			fmt.Printf("Request %d: Denied\n", i+1)
		}
		// 为了模拟请求间隔，可以休眠 500 毫秒
		time.Sleep(500 * time.Millisecond)
	}
}

总结

  • 漏桶算法通过模拟桶漏水的方式，能够平滑地控制请求流量，确保处理速度是恒定的，不会因为流量突发而影响系统。
  • 它适用于需要平稳处理请求的场景，比如数据流、请求速率控制等。
  • Go 实现中，我们使用了排水速率来控制请求的处理速率，并使用 time.Time 来计算自上次排水以来的时间间隔，从而确定是否允许新的请求。

漏桶算法的关键是平滑流量，但可能会丢弃超出容量的请求，因此它适用于流量平稳，但对于流量波动较大的场景可能不太适用。

令牌桶算法

原理

令牌桶算法是控制流量的一种方法，允许突发流量（也就是瞬时的流量超过正常限制），但会通过令牌的生成速率来平滑流量，保持整体的流量稳定。

  • 令牌桶：我们可以把令牌桶看作是一个容器，令牌按照固定的速率加入桶中。
  • 每当一个请求到来时，它需要从桶中获取一个令牌才能被处理。如果桶中有令牌，请求就被处理并从桶中取走一个令牌；如果没有令牌，请求就会被拒绝或者延迟。
  • 令牌桶有一个容量限制，超出容量的令牌会被丢弃，保证桶不会超载。

关键点：

  • 令牌是按照固定的速率（比如每秒 1 个令牌）生成的。
  • 令牌桶有最大容量，当桶满时，新的令牌会被丢弃。
  • 当请求到来时，如果桶中有令牌，取出一个令牌并处理请求。如果没有令牌，拒绝或延迟请求。

优点

  • 支持突发流量：如果请求量瞬时增加，只要桶中有足够的令牌，就可以处理。
  • 灵活：能够平滑地控制流量，同时允许在短时间内处理更多的请求。

缺点

  • 可能会丢失请求：如果请求在桶中没有令牌且令牌桶满了，超出的请求可能会被丢弃。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
package main

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

type TokenBucketLimiter struct {
	capacity   int           // 令牌桶的容量
	tokens     int           // 当前令牌数量
	rate       time.Duration // 令牌生成速率（每个令牌的生成时间间隔）
	lastRefill time.Time     // 上次生成令牌的时间
	mu         sync.Mutex    // 用于保护并发访问
}

// 创建一个新的 TokenBucketLimiter 实例
func NewTokenBucketLimiter(capacity int, rate time.Duration) *TokenBucketLimiter {
	return &TokenBucketLimiter{
		capacity:   capacity,
		tokens:     capacity, // 初始化令牌桶为满
		rate:       rate,
		lastRefill: time.Now(),
	}
}

// 判断是否允许当前请求
func (limiter *TokenBucketLimiter) Allow() bool {
	limiter.mu.Lock()
	defer limiter.mu.Unlock()

	// 获取当前时间
	now := time.Now()

	// 计算自上次令牌生成以来的时间差
	elapsed := now.Sub(limiter.lastRefill)

	// 计算新生成的令牌数量
	newTokens := int(elapsed / limiter.rate)
	if newTokens > 0 {
		// 如果生成的令牌超过容量，令牌桶最多只能存储指定容量的令牌
		limiter.tokens += newTokens
		if limiter.tokens > limiter.capacity {
			limiter.tokens = limiter.capacity
		}
		// 更新上次生成令牌的时间
		limiter.lastRefill = now
	}

	// 如果令牌桶中有令牌，允许请求并消耗一个令牌
	if limiter.tokens > 0 {
		limiter.tokens--
		return true
	}

	// 否则拒绝请求
	return false
}

func main() {
	// 创建一个令牌桶限流器，容量为 5，令牌生成速率为每秒 1 个令牌
	limiter := NewTokenBucketLimiter(5, time.Second)

	// 模拟 10 个请求
	for i := 0; i < 10; i++ {
		if limiter.Allow() {
			fmt.Printf("Request %d: Allowed\n", i+1)
		} else {
			fmt.Printf("Request %d: Denied\n", i+1)
		}
		// 为了模拟请求间隔，可以休眠 500 毫秒
		time.Sleep(500 * time.Millisecond)
	}
}

总结

  • 令牌桶算法能够支持流量的平滑控制，同时允许系统在短时间内处理突发流量，尤其适用于需要灵活流量控制的场景。
  • Go 实现中，我们使用了定时器生成令牌，并根据生成速率更新桶中的令牌数量。
  • 令牌桶算法的优势在于它能够灵活地处理突发流量，控制系统的负载，避免请求过多导致系统崩溃。

这种算法对于网络请求限流、流量控制等场景非常适用，比如 API 请求限流、下载流量控制等。

区分

**令牌桶（Token Bucket）和漏桶（Leaky Bucket）**确实有很多相似之处，它们都是流量控制算法，目的是为了限制请求速率。然而，它们在处理突发流量、流量平滑性和算法设计上有明显的不同。下面是它们之间的主要区别：

  1. 基本原理的区别
  • 漏桶算法：
    • 漏桶的输出速率是恒定的。无论输入流量如何变化，水（请求）都会以恒定的速度从桶中漏出。
    • 如果水流得太快，超过了漏水的速率，那么多余的水就会溢出（丢弃请求）。
    • 它要求请求必须保持均匀、稳定的速率。如果请求速率太快，就会被丢弃。
  • 令牌桶算法：
    • 令牌桶的输出速率是灵活的，允许短时间内的突发流量。令牌按固定速率生成，但桶的输出是灵活的，只要桶中有令牌，流量就可以按最大速率处理。
    • 如果请求超速，它会在短时间内允许大量请求（突发流量），但不会丢弃请求，只会延迟或积压请求，直到令牌重新生成。
    • 它允许灵活的速率控制，能够处理突发流量。
  1. 流量控制的平滑性
  • 漏桶算法：
    • 处理流量时更加“严格”和平滑，因为它只允许以固定速率处理请求。如果请求来得太快，超出的部分会被丢弃（无法处理的流量会被丢弃）。
    • 它的核心在于始终保持一个恒定的输出速率。
  • 令牌桶算法：
    • 处理流量时更“灵活”和弹性。令牌桶可以存储一定量的令牌，允许系统在短时间内处理突发流量。只要桶中有令牌，流量就会被处理。
    • 它允许一定程度的流量突发，流量会积压在桶中，并随着时间的推移被处理。
  1. 突发流量的处理
  • 漏桶算法：
    • 不支持突发流量。因为无论请求多少，都会被限制在固定的速率范围内。任何超过速率的流量都会被丢弃。
    • 例如，如果桶的排水速率为每秒 1 个请求，但 2 个请求同时到来，第二个请求会被丢弃。
  • 令牌桶算法：
    • 支持突发流量。如果请求超过生成速率，令牌桶会积攒令牌，当有大量请求来时，令牌会被消耗，允许短时间内的流量“突发”。
    • 例如，如果桶中积攒了 5 个令牌（因为桶慢慢生成令牌），那么可以一次性处理 5 个请求，而不会丢弃它们。
  1. 算法实现方式
  • 漏桶算法：
    • 通常使用一个固定大小的队列或缓冲区（桶），水的流入速率不可控（来自外部请求的速率），而流出的速率是固定的。
    • 如果桶已经满了，新的请求会被丢弃。
  • 令牌桶算法：
    • 使用一个桶来存储令牌，令牌按照固定速率生成。每当请求到达时，从桶中取一个令牌（如果桶中有令牌），如果没有令牌则拒绝请求或者等待令牌生成。
    • 如果桶满了，多余的令牌会丢弃

总结

单纯是算法层面的东西，中间件里面的具体实现，以及协议栈中是如何实现流量控制的，后文再说吧。

博主越来越懒了，七月都没更新了，后面才补上的了。中间是发生了一些搞笑的事情，抽象的事情太多了。