面试题目分析
Interview Problem Analysis
    │
    ├─ 是否涉及"限流"、"节流"、"API Gateway"、"防止滥用"？
    │   Does it involve "rate limiting", "throttling", "API Gateway", "prevent abuse"?
    │   │
    │   ├─ YES → Rate Limiting 系统
    │   │   └─ 继续判断具体需求...
    │   │
    │   └─ NO → 可能是其他类型
    │
    ├─ 限流粒度？
    │   Rate Limiting Granularity?
    │   │
    │   ├─ 用户级别 → 按 user_id 限流
    │   │   User-level → Rate limit by user_id
    │   ├─ IP 级别 → 按 IP 地址限流
    │   │   IP-level → Rate limit by IP address
    │   └─ API 级别 → 按 API endpoint 限流
    │       API-level → Rate limit by API endpoint
    │
    ├─ 分布式需求？
    │   Distributed Requirements?
    │   │
    │   ├─ 单机限流 → 内存计数器
    │   │   Single machine → In-memory counter
    │   └─ 分布式限流 → Redis/分布式存储
    │       Distributed → Redis/distributed storage
    │
    └─ 精确性要求？
        Accuracy Requirements?
        │
        ├─ 精确限流 → 滑动窗口日志
        │   Exact → Sliding window log
        └─ 近似限流 → 固定窗口/令牌桶
            Approximate → Fixed window/token bucket

输入：API 请求
Input: API Requests
- HTTP requests
- RPC calls
- 任何需要限制的请求
  Any requests that need limiting

输出：允许或拒绝
Output: Allow or Deny
- 200 OK (允许)
- 429 Too Many Requests (拒绝)
- Rate limit headers

关键挑战：
Key Challenges:
- 精确计数（避免漏网）
  Accurate counting (avoid leaks)
- 分布式一致性（多服务器）
  Distributed consistency (multiple servers)
- 低延迟（不影响正常请求）
  Low latency (don't affect normal requests)
- 内存效率（大规模用户）
  Memory efficiency (large scale users)

API Request
    ↓
Rate Limiter (In-Memory)
    ├─→ Counter/Token Bucket
    └─→ Decision Logic
    ↓
Allow/Deny Response

API Request
    ↓
Load Balancer
    ↓
API Server
    ↓
Rate Limiter Service
    ├─→ Redis (Distributed Counter)
    └─→ Rate Limit Rules
    ↓
Allow/Deny Response

原理：
Principle:
- 将时间分成固定窗口（如 1 分钟）
  Divide time into fixed windows (e.g., 1 minute)
- 每个窗口维护一个计数器
  Maintain a counter for each window
- 超过限制则拒绝
  Reject if exceeds limit

优点：
Advantages:
- 实现简单
  Simple implementation
- 内存效率高
  Memory efficient

缺点：
Disadvantages:
- 窗口边界可能突发（2x limit）
  Window boundaries may have bursts (2x limit)
- 不够精确
  Not very accurate

示例：
Example:
Limit: 100 requests/minute
Window 1 (0:00-0:59): 100 requests
Window 2 (1:00-1:59): 100 requests
At 0:59 and 1:00, can send 200 requests in 2 seconds!

原理：
Principle:
- 记录每个请求的时间戳
  Record timestamp of each request
- 维护一个时间窗口内的请求列表
  Maintain list of requests within time window
- 超过限制则拒绝
  Reject if exceeds limit

优点：
Advantages:
- 精确限流
  Accurate rate limiting
- 不会突发
  No bursts

缺点：
Disadvantages:
- 内存消耗大（存储所有时间戳）
  High memory consumption (store all timestamps)
- 实现复杂
  Complex implementation

原理：
Principle:
- 结合固定窗口和滑动窗口
  Combine fixed window and sliding window
- 使用多个固定窗口，加权计算
  Use multiple fixed windows, weighted calculation

优点：
Advantages:
- 相对精确
  Relatively accurate
- 内存效率较高
  Relatively memory efficient

缺点：
Disadvantages:
- 实现较复杂
  More complex implementation
- 仍可能有小误差
  May still have small errors

原理：
Principle:
- 桶中有固定数量的令牌
  Bucket has fixed number of tokens
- 按固定速率补充令牌
  Refill tokens at fixed rate
- 请求消耗令牌，无令牌则拒绝
  Requests consume tokens, reject if no tokens

优点：
Advantages:
- 允许突发（桶满时）
  Allows bursts (when bucket is full)
- 平滑限流
  Smooth rate limiting

缺点：
Disadvantages:
- 实现较复杂
  More complex implementation
- 需要维护令牌状态
  Need to maintain token state

原理：
Principle:
- 请求进入桶（队列）
  Requests enter bucket (queue)
- 按固定速率处理请求
  Process requests at fixed rate
- 桶满则拒绝
  Reject if bucket is full

优点：
Advantages:
- 输出速率恒定
  Constant output rate
- 平滑流量
  Smooth traffic

缺点：
Disadvantages:
- 不允许突发
  Doesn't allow bursts
- 可能增加延迟
  May increase latency

挑战：
Challenges:
- 多服务器同时更新
  Multiple servers updating simultaneously
- Redis 故障处理
  Redis failure handling

解决方案：
Solutions:
1. 使用 Redis 原子操作
   Use Redis atomic operations
2. 使用 Lua 脚本保证原子性
   Use Lua scripts for atomicity
3. Redis 故障降级（本地限流）
   Redis failure fallback (local rate limiting)

适用场景：
Use Cases:
- 防止单个用户滥用
  Prevent single user abuse
- 公平使用资源
  Fair resource usage

实现：
Implementation:
Key: "rate_limit:user:{user_id}"

适用场景：
Use Cases:
- 防止 DDoS 攻击
  Prevent DDoS attacks
- 匿名用户限流
  Rate limit anonymous users

实现：
Implementation:
Key: "rate_limit:ip:{ip_address}"

适用场景：
Use Cases:
- 保护特定 API
  Protect specific APIs
- 不同 API 不同限制
  Different limits for different APIs

实现：
Implementation:
Key: "rate_limit:api:{api_path}"

适用场景：
Use Cases:
- 多层次保护
  Multi-level protection
- 精细控制
  Fine-grained control

实现：
Implementation:
- 用户级别 + API 级别
  User-level + API-level
- 全局限制 + 用户限制
  Global limit + user limit

精确性要求高 + 内存充足
High accuracy + sufficient memory
→ Sliding Window Log

允许近似 + 内存受限
Allow approximation + memory constrained
→ Fixed Window Counter

需要允许突发
Need to allow bursts
→ Token Bucket

需要平滑输出
Need smooth output
→ Leaky Bucket

平衡选择
Balanced choice
→ Sliding Window Counter

1. Rate Limiter Service
   - 接收请求
     Receive requests
   - 检查限流规则
     Check rate limit rules
   - 返回允许/拒绝
     Return allow/deny

2. Storage (Redis)
   - 存储计数器
     Store counters
   - 维护时间窗口
     Maintain time windows

1. 识别题目类型
   Identify problem type
   "这是一个限流系统设计问题"
   "This is a rate limiting system design problem"

2. 明确核心需求
   Clarify core requirements
   "需要限制 [用户/IP/API] 的请求速率"
   "Need to limit request rate for [user/IP/API]"

3. 询问关键参数
   Ask key parameters
   - 限流粒度
     Rate limiting granularity
   - 限流规则（数量、时间窗口）
     Rate limit rules (count, time window)
   - 分布式需求
     Distributed requirements

1. 先问精确性要求
   Ask accuracy requirements first
   "是否需要精确限流，还是可以接受近似？"
   "Need exact rate limiting or can accept approximation?"

2. 根据需求选择算法
   Select algorithm based on requirements
   - 精确 → Sliding Window Log
   - 近似 → Fixed Window / Token Bucket
   - 突发 → Token Bucket
   - 平滑 → Leaky Bucket

3. 讨论权衡
   Discuss trade-offs
   "精确性 vs 内存，性能 vs 准确性"
   "Accuracy vs memory, performance vs accuracy"

"这是一个限流系统设计问题。
"This is a rate limiting system design problem.

核心需求是：
Core requirements:
1. 限制 [用户/IP/API] 的请求速率
   Limit request rate for [user/IP/API]
2. 支持 [精确/近似] 限流
   Support [exact/approximate] rate limiting
3. [单机/分布式] 部署
   [Single machine/Distributed] deployment

让我先澄清几个关键问题：
Let me clarify a few key questions:
- 限流粒度是什么？（用户/IP/API）
  What's the rate limiting granularity? (user/IP/API)
- 限流规则是什么？（如 100 requests/minute）
  What are the rate limit rules? (e.g., 100 requests/minute)
- 是否需要精确限流？
  Do we need exact rate limiting?"

"根据需求，我选择 [算法名称]：
"Based on requirements, I choose [algorithm name]:

原因：
Reasons:
1. [精确性/内存效率/允许突发] 要求
   [Accuracy/Memory efficiency/Allow bursts] requirement
2. [单机/分布式] 部署场景
   [Single machine/Distributed] deployment scenario
3. [低延迟/高吞吐] 性能需求
   [Low latency/High throughput] performance needs

实现方式：
Implementation:
- 使用 [Redis/内存] 存储计数器
  Use [Redis/memory] to store counters
- [固定窗口/滑动窗口/令牌桶] 算法
  [Fixed window/Sliding window/Token bucket] algorithm
- [原子操作/Lua 脚本] 保证一致性
  [Atomic operations/Lua scripts] for consistency"