一文掌握常见的限流算法：计数器、漏桶、令牌桶等

限流（Rate Limiting），又称流量控制，是一种在系统遭遇高并发或大流量请求时，通过限制新请求对系统的访问，来保障系统稳定性的关键技术。然而，限流机制会导致部分用户请求无法及时处理甚至被拒绝，这无疑会对用户体验造成影响。因此，在实际应用中，需要在确保系统稳定运行与维护良好用户体验之间找到平衡。

常见的限流算法涵盖 固定窗口计数器算法、 滑动窗口计数器算法、 漏桶算法、 令牌桶算法、 基于用户的限流 以及 动态限流 等。其中，固定窗口计数器算法与滑动窗口计数器算法均属于计数器算法类别。

接下来，本文将对这些算法进行逐一详细介绍，并附上对应的 Go 语言代码示例，助力你更好地理解与实践。

1. 固定窗口计数器算法

固定窗口计数器算法是计数器算法家族中的一员。该算法通过对请求进行计数，以此限制固定时间窗口内的请求数量。每个时间窗口起始时，计数器都会被重置，然后开始统计该时间限制内的请求次数。

• 优点：算法实现逻辑简单，易于理解和上手。
• 缺点：在窗口边界处容易引发突发流量，可能导致大量请求在窗口切换瞬间集中涌入系统 。

以一个接口为例，假设其 1 秒内最多允许 100 次请求。初始时，设置计数器 count=0，每收到一个请求，count 就加 1。在这 1 秒内，当 count<=100 时，请求能够正常访问接口；若 count>100，后续请求将被拒绝。当 1 秒时间结束，count 会被重置为 0，开启新一轮的计数。

固定窗口计数器算法存在明显弊端，其一为“突刺现象”。比如在 1 秒的时间周期里，若 100 个请求都在前 100 毫秒内抵达，那么后续 900 毫秒内的所有请求都会被拒绝，而此时系统实际上处于空闲状态，造成资源浪费。其二是“临界问题”，当 100 个请求集中在当前 1 秒的后 100 毫秒到达，紧接着下一个 1 秒的前 100 毫秒又有 100 个请求到来，这就意味着系统需要在短短 200 毫秒内处理 200 个请求，这显然与我们期望的限流效果相悖。

基于此，我们自然会思考缩小时间窗口范围。将原本单一的固定窗口拆分为多个小窗口，这种改进思路便催生出了滑动窗口算法。

Go代码示例：

package main

import (
    "sync"
    "time"
)

type FixedWindowCounter struct {
    mu        sync.Mutex
    requestCount int
    limit     int
    window    time.Duration
    resetTime time.Time
}

func NewFixedWindowCounter(limit int, window time.Duration) *FixedWindowCounter {
    return &FixedWindowCounter{
        limit: limit,
        window: window,
        resetTime: time.Now(),
    }
}

func (fw *FixedWindowCounter) Allow() bool {
    fw.mu.Lock()
    defer fw.mu.Unlock()

    now := time.Now()
    if now.Sub(fw.resetTime) >= fw.window {
        fw.requestCount = 0
        fw.resetTime = now
    }

    if fw.requestCount < fw.limit {
        fw.requestCount++
        return true
    }
    return false
}

2. 滑动窗口计数器算法

滑动窗口计数器算法属于计数器算法中的一种。滑动窗口的思想是将固定窗口拆成更多个小窗口，随着时间的推移，窗口不断的滑动，统计也在不断的变化。窗口拆分的越多，滑动就会越平滑，统计就会越精确，所消耗的资源就会越多。滑动窗口如果只拆为1个窗口，就退化为固定窗口。

• 优点：比固定窗口算法更平滑，减少请求的突发性。
• 缺点：实现较复杂。

Go代码示例：

package main

import (
    "container/list"
    "sync"
    "time"
)

type SlidingWindowCounter struct {
    mu        sync.Mutex
    events    *list.List
    limit     int
    window    time.Duration
}

func NewSlidingWindowCounter(limit int, window time.Duration) *SlidingWindowCounter {
    return &SlidingWindowCounter{
        events: list.New(),
        limit: limit,
        window: window,
    }
}

func (sw *SlidingWindowCounter) Allow() bool {
    sw.mu.Lock()
    defer sw.mu.Unlock()

    now := time.Now()
    // 清理过期的事件
    for sw.events.Len() > 0 {
        if sw.events.Front().Value.(time.Time).Add(sw.window).Before(now) {
            sw.events.Remove(sw.events.Front())
        } else {
            break
        }
    }

    if sw.events.Len() < sw.limit {
        sw.events.PushBack(now)
        return true
    }

    return false
}

3. 漏桶算法

漏桶算法通过一个固定速率的漏桶完成请求，任何超出桶容量的请求将被拒绝。请求以固定速率从桶中出桶。

• 优点：能够平滑处理流量，避免突发请求。
• 缺点：如果桶满了，则请求会被立即拒绝。

漏桶算法的思想是将请求先放到一个桶中，然后像滴水一样不断的从中取出请求执行，桶满则溢，后面的请求会被拒绝。当漏斗满了，多余的水就被直接丢弃了。

漏桶算法的特点是流入速度不确定，但是流出速度是确定的，漏桶可以很平滑，均衡的处理请求，但是无法应对短暂的突发流量。

Go代码示例：

package main

import (
    "sync"
    "time"
)

type LeakyBucket struct {
    mu        sync.Mutex
    capacity  int
    available int
    rate      time.Duration
    lastTime  time.Time
}

func NewLeakyBucket(capacity int, rate time.Duration) *LeakyBucket {
    return &LeakyBucket{
        capacity:  capacity,
        available: capacity,
        rate:      rate,
        lastTime:  time.Now(),
    }
}

func (lb *LeakyBucket) Allow() bool {
    lb.mu.Lock()
    defer lb.mu.Unlock()

    now := time.Now()
    elapsed := now.Sub(lb.lastTime)

    // 更新可用令牌
    lb.available += int(elapsed / lb.rate)
    if lb.available > lb.capacity {
        lb.available = lb.capacity
    }
    lb.lastTime = now

    if lb.available > 0 {
        lb.available--
        return true
    }

    return false
}

4. 令牌桶算法

令牌桶算法的思想是不断的生成令牌放到一个桶中，请求到来时到桶中申请令牌，申请得到就执行，申请不到就拒绝。如果桶中的令牌满了，新生成的令牌也会丢弃。

• 优点：允许突发流量，控制能力更强。
• 缺点：稍微复杂。

与漏桶不同的是，令牌桶是流入速度确定（生成令牌的速度），流出速度不确定，所以它不像漏桶一样可以均衡的处理请求，但是由于有令牌桶这个缓冲，一旦有突增的流量，令牌桶里已有的令牌可以短暂的应对突发流量。

由于流出速度是不限制的，此时桶中已有的令牌都可以被申请到，请求一下子就会到我们的服务，给系统带来一定的压力，所以桶的大小需要合适，不宜过大。

举个例子：令牌桶的大小是 1000，每秒放 100 个令牌，经过一段时间后，请求有空闲时，桶里的令牌就会积压，最终保存了满 1000 个令牌，由于某刻流量突增，有 1000 个请求到来，此时能申请到 1000 个令牌，所有请求都会放行，最终达到我们的系统，如果令牌桶过大，系统可能会承受不了这波请求。

令牌桶算法可以说是对漏桶算法的改进。漏桶算法能限制请求的速率。而令牌桶算法在限制请求速率的同时还允许一定程度的突发调用。

过程如下：

一直放令牌，如果令牌桶达到上限则丢弃令牌，假设每秒放 10 个，可以应对一定程度的流量激增，如此时令牌桶有 100 个令牌，突然发生 200 次调用，则此时最开始的 100 次请求可以正常调用，后续的请求才会以 10个/s 的速率来调用。

Go代码示例：

package main

import (
    "sync"
    "time"
)

type TokenBucket struct {
    mu       sync.Mutex
    capacity int
    tokens   int
    rate     time.Duration
    lastTime time.Time
}

func NewTokenBucket(capacity int, rate time.Duration) *TokenBucket {
    return &TokenBucket{
        capacity: capacity,
        tokens:   capacity,
        rate:     rate,
        lastTime: time.Now(),
    }
}

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

    now := time.Now()
    elapsed := now.Sub(tb.lastTime)

    // 计算可用令牌数
    tb.tokens += int(elapsed / tb.rate)
    if tb.tokens > tb.capacity {
        tb.tokens = tb.capacity
    }
    tb.lastTime = now

    if tb.tokens > 0 {
        tb.tokens--
        return true
    }

    return false
}

5. 基于用户的限流

基于用户的限流策略允许对不同用户设置不同的请求频率限制。可以使用上述任意算法作为基础，根据用户身份进行控制。

Go代码示例：

package main

import (
    "sync"
    "time"
)

type UserRateLimiter struct {
    mu         sync.Mutex
    userLimits map[string]int
    userCounts map[string]int
    limit      int
    window     time.Duration
    resetTime  map[string]time.Time
}

func NewUserRateLimiter(limit int, window time.Duration) *UserRateLimiter {
    return &UserRateLimiter{
        userLimits: make(map[string]int),
        userCounts: make(map[string]int),
        limit:      limit,
        window:     window,
        resetTime:  make(map[string]time.Time),
    }
}

func (url *UserRateLimiter) Allow(userId string) bool {
    url.mu.Lock()
    defer url.mu.Unlock()

    now := time.Now()
    if _, exists := url.resetTime[userId]; !exists {
        url.resetTime[userId] = now
    }

    if now.Sub(url.resetTime[userId]) >= url.window {
        url.userCounts[userId] = 0
        url.resetTime[userId] = now
    }

    if url.userCounts[userId] < url.limit {
        url.userCounts[userId]++
        return true
    }

    return false
}

6. 动态限流

动态限流算法根据系统的实时性能和负载情况动态调整限流策略。具体实现可以结合上述算法，尤其是令牌桶算法。

Go代码示例：

package main

import (
    "sync"
    "time"
)

type DynamicRateLimiter struct {
    mu         sync.Mutex
    currentRate int
    maxRate    int
    minRate    int
    rateChange time.Duration
    lastChange time.Time
}

func NewDynamicRateLimiter(maxRate, minRate int, rateChange time.Duration) *DynamicRateLimiter {
    return &DynamicRateLimiter{
        currentRate: maxRate,
        maxRate:     maxRate,
        minRate:     minRate,
        rateChange:  rateChange,
        lastChange:  time.Now(),
    }
}

func (dr *DynamicRateLimiter) AdjustRate(load int) {
    dr.mu.Lock()
    defer dr.mu.Unlock()

    now := time.Now()
    if now.Sub(dr.lastChange) < dr.rateChange {
        return
    }

    if load > dr.currentRate {
        dr.currentRate--
        if dr.currentRate < dr.minRate {
            dr.currentRate = dr.minRate
        }
    } else {
        dr.currentRate++
        if dr.currentRate > dr.maxRate {
            dr.currentRate = dr.maxRate
        }
    }

    dr.lastChange = now
}

func (dr *DynamicRateLimiter) Allow() bool {
    // 这里可以使用任意一种算法实现，根据dr.currentRate来限制请求
    // 简单示例，返回 true 表示请求被允许
    return true
}

总结

尽管限流算法在实现上各有不同，但它们的核心目标是确保系统在高并发情况下能够高效、稳定地运行。选择合适的限流算法需要根据具体业务需求、流量特征及系统架构来进行相应评估。如需深入了解某种算法或是具体应用，欢迎随时询问！