18.08-限流算法

要点

限流有四种基本算法：固定窗口、滑动窗口、漏桶、令牌桶
固定窗口最简单但有边界突发问题——窗口切换瞬间可以收到 2 倍请求
滑动窗口解决了边界突发——但需要更多存储
漏桶平滑输出速率——适合处理下游系统的速率限制
令牌桶允许突发——适合 API 限流，用户体验更好
Worker 环境没有 Redis，限流计数用 KV（最终一致）或 Upstash Redis（原子操作）——高并发场景必须 Redis

1. 为什么需要限流

API 限流解决三个问题：

保护后端：防止突发流量压垮服务——数据库、第三方 API、LLM 都有处理能力上限
公平分配：多用户共享资源时，防止某个用户独占——按用户配额分配
成本控制：LLM 调用有 token 费用，限流防止成本失控

Worker 环境的限流有个特殊挑战——没有 Redis 的原子操作。KV 的 get + put 不是原子的，高并发下计数器会失准。后面会讲怎么解决。

2. 固定窗口计数器

原理

把时间切成固定窗口（比如每分钟），每个窗口内允许 N 次请求。窗口结束时计数器清零。

时间轴：|---窗口 1---|---窗口 2---|---窗口 3---|
计数：  |   7/10    |   3/10    |   9/10    |

实现

// 用 Redis（原子操作）
async function fixedWindowRedis(
  redis: Redis,
  key: string,
  limit: number,
  windowSeconds: number
): Promise<{ allowed: boolean; remaining: number }> {
  const window = Math.floor(Date.now() / 1000 / windowSeconds)
  const windowKey = `${key}:${window}`
 
  const count = await redis.incr(windowKey)
  if (count === 1) {
    await redis.expire(windowKey, windowSeconds)
  }
 
  return {
    allowed: count <= limit,
    remaining: Math.max(0, limit - count),
  }
}

边界突发问题

固定窗口有个严重缺陷——窗口切换瞬间可以收到 2 倍请求：

时间轴：   |--窗口 1--|--窗口 2--|--窗口 3--|
请求分布： 10     5 | 1     10 | 5     10
           ↑           ↑
        窗口 1 末尾   窗口 2 开头
        共 15 个请求（超过 10）

窗口 1 末尾 5 个 + 窗口 2 开头 10 个 = 15 个，超过了每分钟 10 个的限制。

3. 滑动窗口计数器

原理

不硬切窗口——看「过去 N 秒内」的请求数。用当前窗口 + 上一个窗口的加权值估算：

当前窗口：   |--过去 60 秒--|
             [上窗口 40%][当前窗口 60%]
总计数 = 上窗口计数 × 0.4 + 当前窗口计数

实现

async function slidingWindowRedis(
  redis: Redis,
  key: string,
  limit: number,
  windowSeconds: number
): Promise<{ allowed: boolean; remaining: number }> {
  const now = Date.now() / 1000
  const currentWindow = Math.floor(now / windowSeconds)
  const prevWindow = currentWindow - 1
 
  const [prevCount, currentCount] = await redis.mget(
    `${key}:${prevWindow}`,
    `${key}:${currentWindow}`
  )
 
  // 当前窗口在时间窗内的比例
  const elapsedInWindow = now % windowSeconds
  const weight = 1 - elapsedInWindow / windowSeconds
 
  const estimatedCount =
    (Number(prevCount) || 0) * weight + (Number(currentCount) || 0)
 
  if (estimatedCount >= limit) {
    return { allowed: false, remaining: 0 }
  }
 
  // 计数 +1
  const newCount = await redis.incr(`${key}:${currentWindow}`)
  if (newCount === 1) {
    await redis.expire(`${key}:${currentWindow}`, windowSeconds * 2)
  }
 
  return {
    allowed: true,
    remaining: Math.max(0, Math.floor(limit - estimatedCount - 1)),
  }
}

优缺点

解决了边界突发问题
比固定窗口精确
需要存两个窗口的计数（Redis 两个 key）
估算值不是精确值——但对于限流足够

4. 漏桶（Leaky Bucket）

原理

请求像水一样注入桶，桶以固定速率流出（处理）。桶满了就溢出（拒绝）。

请求 → [桶] → 固定速率流出
     ↑
   桶满了就拒绝

漏桶的特点是平滑输出——不管输入多快，输出速率恒定。

实现

async function leakyBucketRedis(
  redis: Redis,
  key: string,
  capacity: number,      // 桶容量
  ratePerSecond: number  // 流出速率
): Promise<{ allowed: boolean; retryAfter?: number }> {
  const now = Date.now() / 1000
  const bucketKey = `${key}:bucket`
 
  // 用 Lua 脚本保证原子性
  const lua = `
    local key = KEYS[1]
    local capacity = tonumber(ARGV[1])
    local rate = tonumber(ARGV[2])
    local now = tonumber(ARGV[3])
 
    local bucket = redis.call('hmget', key, 'level', 'last_time')
    local level = tonumber(bucket[1]) or 0
    local last_time = tonumber(bucket[2]) or now
 
    -- 计算漏出的水量
    local elapsed = now - last_time
    level = math.max(0, level - elapsed * rate)
 
    if level + 1 > capacity then
      return {0, (level + 1 - capacity) / rate}  -- 拒绝，返回等待时间
    end
 
    level = level + 1
    redis.call('hmset', key, 'level', level, 'last_time', now)
    redis.call('expire', key, 60)
    return {1}
  `
 
  const result = await redis.eval(lua, [bucketKey], [
    capacity,
    ratePerSecond,
    now,
  ])
 
  if (result[0] === 1) {
    return { allowed: true }
  } else {
    return { allowed: false, retryAfter: result[1] as number }
  }
}

适用场景

下游系统有严格的速率限制（比如数据库每秒只能处理 100 个写入）
需要平滑流量，防止突发
消息队列的消费者端——匀速消费

5. 令牌桶（Token Bucket）

原理

桶里以固定速率生成令牌。每个请求拿一个令牌——有令牌就通过，没令牌就拒绝。桶有容量上限，令牌可以积累。

         令牌生成 → [令牌桶] → 请求来就拿令牌
                   ↑
               桶满了就不再生成

令牌桶的特点是允许突发——如果积累了 N 个令牌，可以一次性处理 N 个请求。

实现

async function tokenBucketRedis(
  redis: Redis,
  key: string,
  capacity: number,      // 桶容量（最大积累令牌数）
  refillRate: number     // 每秒补充令牌数
): Promise<{ allowed: boolean; remaining: number; retryAfter?: number }> {
  const now = Date.now() / 1000
  const bucketKey = `${key}:tokens`
 
  const lua = `
    local key = KEYS[1]
    local capacity = tonumber(ARGV[1])
    local rate = tonumber(ARGV[2])
    local now = tonumber(ARGV[3])
 
    local bucket = redis.call('hmget', key, 'tokens', 'last_time')
    local tokens = tonumber(bucket[1]) or capacity
    local last_time = tonumber(bucket[2]) or now
 
    -- 计算新补充的令牌
    local elapsed = now - last_time
    tokens = math.min(capacity, tokens + elapsed * rate)
 
    if tokens < 1 then
      return {0, 0, (1 - tokens) / rate}  -- 拒绝，返回等待时间
    end
 
    tokens = tokens - 1
    redis.call('hmset', key, 'tokens', tokens, 'last_time', now)
    redis.call('expire', key, 60)
    return {1, math.floor(tokens)}
  `
 
  const result = await redis.eval(lua, [bucketKey], [
    capacity,
    refillRate,
    now,
  ])
 
  if (result[0] === 1) {
    return { allowed: true, remaining: result[1] as number }
  } else {
    return {
      allowed: false,
      remaining: 0,
      retryAfter: result[2] as number,
    }
  }
}

适用场景

API 限流——用户有配额（比如 1000 次/小时），可以突发用完再慢慢恢复
客户端限速——下载、上传时限制带宽
大多数 Web API——用户体验好，允许短时间高并发

6. 四种算法对比

算法	突发允许	平滑输出	实现复杂度	适用场景
固定窗口	❌（边界 2 倍）	❌	低	简单场景、粗略限流
滑动窗口	❌	❌	中	精确限流
漏桶	❌	✅	高	保护下游系统
令牌桶	✅	❌	中	API 限流、用户体验优先

选择建议：

Web API 限流：令牌桶——允许突发，用户体验好
下游保护：漏桶——平滑流量，保护脆弱系统
粗略限流：固定窗口——实现简单，够用
精确限流：滑动窗口——无边界问题

7. Worker 环境的限流实现

Worker 没有 Redis 是最大挑战——KV 的 get + put 不是原子操作。

7.1 用 KV 做固定窗口（有误差）

async function fixedWindowKV(
  kv: KVNamespace,
  key: string,
  limit: number,
  windowSeconds: number
): Promise<{ allowed: boolean; remaining: number }> {
  const window = Math.floor(Date.now() / 1000 / windowSeconds)
  const windowKey = `${key}:${window}`
 
  const current = parseInt((await kv.get(windowKey)) || '0')
 
  if (current >= limit) {
    return { allowed: false, remaining: 0 }
  }
 
  await kv.put(windowKey, String(current + 1), {
    expirationTtl: windowSeconds * 2,
  })
 
  return { allowed: true, remaining: limit - current - 1 }
}

高并发下会超出限制——两个请求同时读到 current = 99，都认为自己还能发，结果变成 101 个。

对于大多数业务来说，1-2% 的误差可以接受。如果需要严格限制，必须用 Redis。

7.2 用 Upstash Redis（严格限制）

用前面的 @upstash/redis 客户端 + Lua 脚本：

import { Redis } from '@upstash/redis/cloudflare'
 
const redis = Redis.fromEnv(env)
const result = await tokenBucketRedis(redis, `user:${userId}`, 1000, 1)
 
if (!result.allowed) {
  return c.json(
    { error: 'Rate limit exceeded', retryAfter: result.retryAfter },
    429
  )
}

7.3 用 Durable Objects 做限流

Durable Objects 提供单实例串行化——天然解决原子性问题：

// src/rate-limiter.ts
export class RateLimiter {
  private state: DurableObjectState
  private tokens = 1000
  private lastRefill = Date.now()
 
  constructor(state: DurableObjectState) {
    this.state = state
    this.state.blockConcurrencyWhile(async () => {
      const stored = await this.state.storage.get<number>('tokens')
      if (stored !== undefined) this.tokens = stored
    })
  }
 
  async fetch(request: Request) {
    this.refill()
 
    if (this.tokens < 1) {
      return new Response(JSON.stringify({ allowed: false }), {
        status: 429,
      })
    }
 
    this.tokens--
    await this.state.storage.put('tokens', this.tokens)
    return new Response(JSON.stringify({ allowed: true }))
  }
 
  private refill() {
    const now = Date.now()
    const elapsed = (now - this.lastRefill) / 1000
    this.tokens = Math.min(1000, this.tokens + elapsed * 1)  // 1 令牌/秒
    this.lastRefill = now
  }
}

每个用户一个 Durable Object 实例——所有请求串行化，计数绝对准确。

但 Durable Objects 的成本比普通 KV 高很多。只在「必须严格限制」的场景用。

8. Hono 中间件封装

把限流逻辑封装成 Hono 中间件：

// src/middleware/rate-limit.ts
import { Hono } from 'hono'
 
type RateLimitConfig = {
  limit: number
  windowSeconds: number
  keyFn: (c: Context) => string
}
 
export function rateLimit(config: RateLimitConfig) {
  return async (c: Context, next: Next) => {
    const key = config.keyFn(c)
    const result = await checkRateLimit(c.env, key, config)
 
    if (!result.allowed) {
      c.header('Retry-After', String(Math.ceil(result.retryAfter || config.windowSeconds)))
      c.header('X-RateLimit-Limit', String(config.limit))
      c.header('X-RateLimit-Remaining', '0')
      return c.json(
        { error: 'Rate limit exceeded' },
        429
      )
    }
 
    c.header('X-RateLimit-Limit', String(config.limit))
    c.header('X-RateLimit-Remaining', String(result.remaining))
    await next()
  }
}
 
// 使用
app.use('/api/*', rateLimit({
  limit: 100,
  windowSeconds: 60,
  keyFn: (c) => `user:${c.get('userId')}`,
}))

后面几篇会讲用户级、IP 级、模型调用级的具体限流策略。

9. 小结

限流四种基本算法：

固定窗口：最简单，有边界突发问题
滑动窗口：解决边界突发，需要存两个窗口
漏桶：平滑输出，保护下游
令牌桶：允许突发，适合 API 限流

Worker 环境的实现选择：

KV：简单但非原子，有 1-2% 误差
Upstash Redis：原子操作 + Lua 脚本，严格准确
Durable Objects：串行化保证准确，成本较高

选择建议：Web API 限流用令牌桶（KV 或 Redis 实现），下游保护用漏桶（Redis 实现），需要严格限制用 Durable Objects。

下一篇讲用户级限流——按 user_id/API key 限流、配额管理、分级配额、D1/KV 实现。