面试题：微服务架构下服务限流的常用算法有哪些及如何实现

Question

在微服务架构中，服务限流是保障系统稳定运行的重要手段。请阐述常见的服务限流算法，如令牌桶算法、漏桶算法，并说明在代码层面如何基于其中一种算法实现简单的服务限流功能，可选择你熟悉的编程语言。

Answer 1

常见服务限流算法

1. 令牌桶算法
   • 原理：系统以固定速率生成令牌放入桶中，请求到达时尝试从桶中获取令牌。如果桶中有足够令牌，则请求被允许通过；若桶中无令牌，则请求被限流。
   • 优点：允许一定程度的突发流量，只要桶中有令牌，就可以处理突发请求。
   • 缺点：实现相对复杂，需要维护令牌桶状态。
2. 漏桶算法
   • 原理：请求像水流一样先进入漏桶，漏桶以固定速率处理请求流出。如果请求进入速度过快，漏桶满了之后多余的请求将被丢弃。
   • 优点：能有效平滑流量，处理流量比较稳定。
   • 缺点：无法处理突发流量，即使系统有足够资源处理突发请求，也会按固定速率处理。

基于令牌桶算法的代码实现（Python 示例）

import time


class TokenBucket:
    def __init__(self, capacity, rate):
        self.capacity = capacity
        self.rate = rate
        self.tokens = capacity
        self.last_update = time.time()

    def get_token(self):
        now = time.time()
        # 计算从上次更新到现在生成的令牌数
        self.tokens = min(self.capacity, self.tokens + (now - self.last_update) * self.rate)
        self.last_update = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False


# 使用示例
bucket = TokenBucket(100, 20)  # 桶容量100，每秒生成20个令牌
for _ in range(200):
    if bucket.get_token():
        print("请求通过")
    else:
        print("请求被限流")
    time.sleep(0.1)

在上述代码中，TokenBucket 类实现了令牌桶算法。__init__ 方法初始化桶的容量和令牌生成速率。get_token 方法在每次请求时调用，先根据时间差计算新生成的令牌数，然后判断是否有足够令牌来处理请求。如果有则返回 True 表示请求通过，否则返回 False 表示请求被限流。