限流算法 | 飞奔的蜗牛

                    
                                限流
                            
                                高访问
                            
                                系统设计
                            
                    发布日期:  
                    2025-04-11
                
                    文章字数:  
                    1.5k
                
                    阅读时长:  
                    5 分
                
限流算法（Rate Limiting Algorithm）用于控制系统中请求的速率，以防止资源被过度消耗、保护系统免受高流量冲击以及确保服务的公平性和稳定性。常见的限流算法包括以下几种：
1. 固定窗口计数器（Fixed Window Counter）原理：
• 将时间划分为固定大小的窗口（如每分钟、每小时）。
• 在每个窗口内统计请求次数。
• 当请求次数超过阈值时，拒绝后续的请求。
优点：
• 实现简单，易于理解。
缺点：
• 可能出现“边界问题”，即在窗口切换时允许突发流量。例如，在窗口边界处可能允许两倍于阈值的请求。
示例：
假设阈值为每分钟100个请求，窗口大小为1分钟。在00:00-00:01窗口内已经处理了100个请求，此时00:01窗口开始，可能再次接受100个请求，导致两分钟内瞬间处理200个请求。
2. 滑动窗口计数器（Sliding Window Counter）原理：
• 将时间划分为更小的子窗口（如每秒一个子窗口）。
• 维护一个滑动时间窗口内的请求计数。
• 随着时间的推移，移除过期的子窗口数据，添加新的子窗口数据。
优点：
• 相比固定窗口，滑动窗口能更平滑地控制请求速率，减少边界问题。
缺点：
• 实现相对复杂，需要维护多个子窗口的数据。
示例：
假设阈值为每分钟100个请求，划分为60个1秒的子窗口。滑动窗口包含最近60秒的子窗口数据，总和不超过100。
3. 滑动窗口日志（Sliding Window Log）原理：
• 记录每个请求的时间戳。
• 当新的请求到来时，移除时间窗口之外的旧记录。
• 统计窗口内的请求数量是否超过阈值。
优点：
• 精确控制请求速率，适用于需要严格限流的场景。
缺点：
• 随着时间推移，日志记录会不断增加，占用大量存储空间，影响性能。
示例：
维护一个请求时间戳的列表，每次请求到来时，删除超过1分钟的记录，然后统计剩余记录的数量。
4. 令牌桶（Token Bucket）原理：
• 系统以固定速率向桶中添加令牌。
• 每个请求需要消耗一个令牌才能被处理。
• 如果桶中没有足够的令牌，请求被拒绝或等待。
优点：
• 允许一定程度的突发流量，因为桶中可以积累令牌。
• 平滑处理请求，适用于需要控制平均速率和突发流量的场景。
缺点：
• 需要维护令牌桶的状态，实现相对复杂。
示例：
桶的容量为100个令牌，每秒添加10个令牌。如果短时间内有大量请求，只要桶中有足够的令牌，这些请求都可以被处理。
5. 漏桶（Leaky Bucket）原理：
• 请求作为水滴进入漏桶，漏桶以固定速率“漏水”（处理请求）。
• 如果漏桶满了，新的请求被拒绝或等待。
优点：
• 强制请求以固定速率处理，避免突发流量对系统的影响。
• 适用于需要严格控制请求处理速率的场景。
缺点：
• 不允许突发流量，可能导致请求延迟增加。
示例：
漏桶的处理速率为每秒10个请求。如果短时间内有超过10个请求到达，超出的请求会被丢弃或在队列中等待处理。
6. 漏桶与令牌桶的对比

特性
令牌桶 (Token Bucket)
漏桶 (Leaky Bucket)

流量控制
允许突发流量
平滑流量，不允许突发

处理方式
消耗令牌
固定速率处理请求

适用场景
需要允许一定突发流量的场景
需要严格控制请求处理速率的场景

实现复杂度
相对简单
相对复杂

7. 分布式限流在分布式系统中，单机限流算法无法满足需求，需要采用分布式限流策略。常见的方法包括：
• 集中式存储：使用Redis等集中式存储来维护全局的限流状态，如令牌桶的当前令牌数。
• 分布式算法：如基于一致性哈希的本地限流结合全局协调，或者使用分布式锁来同步限流状态。
• 分布式限流框架：如Google的Rate Limiter、Envoy的限流模块等。
8. 实际应用中的选择• 简单场景：如果系统规模较小，可以使用固定窗口计数器或滑动窗口计数器。
• 需要平滑处理突发流量：令牌桶是一个不错的选择。
• 严格控制请求速率：漏桶更适合。
• 分布式环境：需要采用基于集中存储或分布式算法的限流方案。
9. 示例代码（令牌桶算法，Python）import time
import threading

class TokenBucket:
    def __init__(self, capacity, refill_rate):
        self.capacity = capacity    # 桶的容量
        self.tokens = capacity      # 当前令牌数
        self.refill_rate = refill_rate  # 每秒填充的令牌数
        self.last_refill_time = time.time()
        self.lock = threading.Lock()

    def refill(self):
        now = time.time()
        tokens_to_add = (now - self.last_refill_time) * self.refill_rate
        with self.lock:
            self.tokens = min(self.capacity, self.tokens + tokens_to_add)
            self.last_refill_time = now

    def consume(self, tokens=1):
        with self.lock:
            self.refill()
            if self.tokens >= tokens:
                self.tokens -= tokens
                return True
            return False

# 使用示例
bucket = TokenBucket(capacity=100, refill_rate=10)  # 每秒添加10个令牌，桶容量为100

def handle_request():
    if bucket.consume():
        print("请求被处理")
    else:
        print("请求被限流")

# 模拟并发请求
threads = []
for _ in range(120):
    t = threading.Thread(target=handle_request)
    threads.append(t)
    t.start()

for t in threads:
    t.join()
10. 总结限流算法的选择取决于具体的应用场景和需求。在实际应用中，可能需要结合多种算法的优点，或者采用更高级的分布式限流策略来应对复杂的流量控制需求。

                        文章作者:
                    
                    Crazy Boy
                
                        文章链接:
                    
                    https://crazy-boy.com/posts/rate-limiting-algorithm.html
                
                        版权声明:
                    
                    本博客所有文章除特別声明外，均采用
                    CC BY 4.0
                    许可协议。转载请注明来源
                    Crazy Boy
                    !
                
                                    限流
                                
                                    高访问
                                
赏感谢赞赏哦~支付宝
微 信

        评 论
    
                 上一篇

                          熔断机制（Circuit Breaker）详解
                        
                            熔断机制是一种容错设计模式，用于防止系统在异常情况下持续恶化，避免级联故障。它类似于电路中的保险丝，在电流过大时自动断开，保护电路安全。

1. 熔断机制的核心原理熔断机制通常有三种状态：

Closed（关闭状态）• 正常工作，请求正常处
                        
                            2025-04-11
                        
                                    系统设计
                                
                        熔断机制
                    
                下一篇 
            
                          基于Redis的实时排行榜系统设计与实现
                        
                            一、核心设计原理1.1 架构设计采用Redis ZSET+数据库双存储方案：

Redis ZSET：存储组合分数实现实时排序（时间复杂度O(logN)）
数据库：持久化原始数据
分布式锁：保证数据一致性

1.2 同分排序算法组合分数公式
                        
                                2025-02-21
                            
                                    系统设计
                                
                        Redis
                    
                        PHP
                    
                        排行榜
                    
                                限流
                            
                                高访问
                            
                                系统设计
                            
                    发布日期:  
                    2025-04-11
                
                    文章字数:  
                    1.5k
                
                    阅读时长:  
                    5 分
                
限流算法（Rate Limiting Algorithm）用于控制系统中请求的速率，以防止资源被过度消耗、保护系统免受高流量冲击以及确保服务的公平性和稳定性。常见的限流算法包括以下几种：
1. 固定窗口计数器（Fixed Window Counter）原理：
• 将时间划分为固定大小的窗口（如每分钟、每小时）。
• 在每个窗口内统计请求次数。
• 当请求次数超过阈值时，拒绝后续的请求。
优点：
• 实现简单，易于理解。
缺点：
• 可能出现“边界问题”，即在窗口切换时允许突发流量。例如，在窗口边界处可能允许两倍于阈值的请求。
示例：
假设阈值为每分钟100个请求，窗口大小为1分钟。在00:00-00:01窗口内已经处理了100个请求，此时00:01窗口开始，可能再次接受100个请求，导致两分钟内瞬间处理200个请求。
2. 滑动窗口计数器（Sliding Window Counter）原理：
• 将时间划分为更小的子窗口（如每秒一个子窗口）。
• 维护一个滑动时间窗口内的请求计数。
• 随着时间的推移，移除过期的子窗口数据，添加新的子窗口数据。
优点：
• 相比固定窗口，滑动窗口能更平滑地控制请求速率，减少边界问题。
缺点：
• 实现相对复杂，需要维护多个子窗口的数据。
示例：
假设阈值为每分钟100个请求，划分为60个1秒的子窗口。滑动窗口包含最近60秒的子窗口数据，总和不超过100。
3. 滑动窗口日志（Sliding Window Log）原理：
• 记录每个请求的时间戳。
• 当新的请求到来时，移除时间窗口之外的旧记录。
• 统计窗口内的请求数量是否超过阈值。
优点：
• 精确控制请求速率，适用于需要严格限流的场景。
缺点：
• 随着时间推移，日志记录会不断增加，占用大量存储空间，影响性能。
示例：
维护一个请求时间戳的列表，每次请求到来时，删除超过1分钟的记录，然后统计剩余记录的数量。
4. 令牌桶（Token Bucket）原理：
• 系统以固定速率向桶中添加令牌。
• 每个请求需要消耗一个令牌才能被处理。
• 如果桶中没有足够的令牌，请求被拒绝或等待。
优点：
• 允许一定程度的突发流量，因为桶中可以积累令牌。
• 平滑处理请求，适用于需要控制平均速率和突发流量的场景。
缺点：
• 需要维护令牌桶的状态，实现相对复杂。
示例：
桶的容量为100个令牌，每秒添加10个令牌。如果短时间内有大量请求，只要桶中有足够的令牌，这些请求都可以被处理。
5. 漏桶（Leaky Bucket）原理：
• 请求作为水滴进入漏桶，漏桶以固定速率“漏水”（处理请求）。
• 如果漏桶满了，新的请求被拒绝或等待。
优点：
• 强制请求以固定速率处理，避免突发流量对系统的影响。
• 适用于需要严格控制请求处理速率的场景。
缺点：
• 不允许突发流量，可能导致请求延迟增加。
示例：
漏桶的处理速率为每秒10个请求。如果短时间内有超过10个请求到达，超出的请求会被丢弃或在队列中等待处理。
6. 漏桶与令牌桶的对比

特性
令牌桶 (Token Bucket)
漏桶 (Leaky Bucket)

流量控制
允许突发流量
平滑流量，不允许突发

处理方式
消耗令牌
固定速率处理请求

适用场景
需要允许一定突发流量的场景
需要严格控制请求处理速率的场景

实现复杂度
相对简单
相对复杂

7. 分布式限流在分布式系统中，单机限流算法无法满足需求，需要采用分布式限流策略。常见的方法包括：
• 集中式存储：使用Redis等集中式存储来维护全局的限流状态，如令牌桶的当前令牌数。
• 分布式算法：如基于一致性哈希的本地限流结合全局协调，或者使用分布式锁来同步限流状态。
• 分布式限流框架：如Google的Rate Limiter、Envoy的限流模块等。
8. 实际应用中的选择• 简单场景：如果系统规模较小，可以使用固定窗口计数器或滑动窗口计数器。
• 需要平滑处理突发流量：令牌桶是一个不错的选择。
• 严格控制请求速率：漏桶更适合。
• 分布式环境：需要采用基于集中存储或分布式算法的限流方案。
9. 示例代码（令牌桶算法，Python）import time
import threading

class TokenBucket:
    def __init__(self, capacity, refill_rate):
        self.capacity = capacity    # 桶的容量
        self.tokens = capacity      # 当前令牌数
        self.refill_rate = refill_rate  # 每秒填充的令牌数
        self.last_refill_time = time.time()
        self.lock = threading.Lock()

    def refill(self):
        now = time.time()
        tokens_to_add = (now - self.last_refill_time) * self.refill_rate
        with self.lock:
            self.tokens = min(self.capacity, self.tokens + tokens_to_add)
            self.last_refill_time = now

    def consume(self, tokens=1):
        with self.lock:
            self.refill()
            if self.tokens >= tokens:
                self.tokens -= tokens
                return True
            return False

# 使用示例
bucket = TokenBucket(capacity=100, refill_rate=10)  # 每秒添加10个令牌，桶容量为100

def handle_request():
    if bucket.consume():
        print("请求被处理")
    else:
        print("请求被限流")

# 模拟并发请求
threads = []
for _ in range(120):
    t = threading.Thread(target=handle_request)
    threads.append(t)
    t.start()

for t in threads:
    t.join()
10. 总结限流算法的选择取决于具体的应用场景和需求。在实际应用中，可能需要结合多种算法的优点，或者采用更高级的分布式限流策略来应对复杂的流量控制需求。

                        文章作者:
                    
                    Crazy Boy
                
                        文章链接:
                    
                    https://crazy-boy.com/posts/rate-limiting-algorithm.html
                
                        版权声明:
                    
                    本博客所有文章除特別声明外，均采用
                    CC BY 4.0
                    许可协议。转载请注明来源
                    Crazy Boy
                    !
                
                                    限流
                                
                                    高访问
                                
赏感谢赞赏哦~支付宝
微 信

        评 论
    
                 上一篇

                          熔断机制（Circuit Breaker）详解
                        
                            熔断机制是一种容错设计模式，用于防止系统在异常情况下持续恶化，避免级联故障。它类似于电路中的保险丝，在电流过大时自动断开，保护电路安全。

1. 熔断机制的核心原理熔断机制通常有三种状态：

Closed（关闭状态）• 正常工作，请求正常处
                        
                            2025-04-11
                        
                                    系统设计
                                
                        熔断机制
                    
                下一篇 
            
                          基于Redis的实时排行榜系统设计与实现
                        
                            一、核心设计原理1.1 架构设计采用Redis ZSET+数据库双存储方案：

Redis ZSET：存储组合分数实现实时排序（时间复杂度O(logN)）
数据库：持久化原始数据
分布式锁：保证数据一致性

1.2 同分排序算法组合分数公式
                        
                                2025-02-21
                            
                                    系统设计
                                
                        Redis
                    
                        PHP
                    
                        排行榜
                    
                  目录
            
                  目录
            
        hexo
特性	令牌桶 (Token Bucket)	漏桶 (Leaky Bucket)
流量控制	允许突发流量	平滑流量，不允许突发
处理方式	消耗令牌	固定速率处理请求
适用场景	需要允许一定突发流量的场景	需要严格控制请求处理速率的场景
实现复杂度	相对简单	相对复杂