专业书籍精读 · System Design Interview 卷一 · 第 4 章
System Design Interview: An Insider's Guide · Vol 1 · Ch 4 · Alex Xu · 2020
网上很多服务都会给你一个「用量上限」：这个软件的免费版一天只让你转 5 次文件，那个网站不让你一分钟连发二十条评论。这一章讲的就是这个上限背后的那个小零件——限流器：一个坐在大门口的检票员，规定「每人每分钟最多进几次」，超了就把人拦在门外。
你大概以为这道门是用来防坏人的。其实它拦下来的，多半是好人。更准确地说，是好人写错的一段程序——某个客户的软件里有个循环忘了停，一秒钟朝你发几千次请求；他自己不知道，也没恶意，可效果和攻击一模一样。限流器真正的日常工作，是不让一个人的失手，变成所有人的事故。
没有这道门，一切按「先到先得」运转：谁喊得响谁被服务。听着公平，实际很残酷——一个失控的程序几秒内就能把服务的处理能力全部吃光，剩下成千上万个规规矩矩的用户，同时被挡在外面。还有一笔更直接的账：很多服务背后要调别人家的收费接口，按次算钱，一个转不停的循环一夜就能烧光一个月的预算。
① 发糖法（令牌桶）。门口摆一个碗，每秒往碗里放 2 颗糖，碗最多装 40 颗。想进门，先从碗里拿一颗；碗空了就进不去。妙处在于：你安静了一阵子，碗里就攒满了糖，这时候可以一口气进 40 个人——它容得下短时间的一阵猛冲，但拉长了看，平均还是每秒 2 个。
② 排队法（漏桶）。门口只放一条队，无论外面涌来多少人，里面永远每秒放 2 个进去，一个不多。好处是里面的节奏永远平稳；代价是队伍一旦被挤满，后来的人连队都排不上，直接被劝走。
③ 整点清零法（固定窗口）。门卫拿个计数器，每到整分钟清零，这一分钟数满 5 个就不放了。最省事，但有个漏洞：如果 5 个人在 0 分 55 秒挤进来，另外 5 个在 1 分 05 秒又进来，那么这中间的短短十几秒里，实际上进去了 10 个——是规定的两倍。
④ 往回看一分钟（滑动窗口）。把「这一分钟」改成「从现在往回数的一分钟」，整点漏洞就补上了。代价是门卫得记住每个人进门的时刻，人一多这本账就又厚又贵。折中办法是不记流水账，只把上一分钟的人数按重叠比例折算一部分进来——不完全准，但便宜得多。
想给用户留一点「偶尔手快」的余地，用发糖法；要求下游节奏绝对平稳，用排队法；只想快速上一个粗糙的挡板，整点清零法半小时就写完了。
诚实说一句代价：这道门自己也可能出问题——它坏了，是该把所有人都放进去，还是把所有人都挡在外面？这个问题没有标准答案，但每个上线限流的团队都必须先想清楚。
限流器是门口的检票员，防的主要不是坏人，是一个人的失手拖垮所有人。四种守门姿势：发糖（容得下突发）、排队（节奏平稳）、整点清零（省事但边界漏水）、往回看一分钟（准但贵）。选哪种，取决于你愿不愿意容忍突发。
想进到具体算法、量级和示意图？ → 切到精读版
你以为限流器（rate limiter）是一堵「防攻击的墙」，其实它是一份容量的分配合同——它要回答的第一个问题不是「怎么挡住坏人」，而是「当资源不够分时，先饿死谁」。这一章的价值也不在那五个算法本身：算法是死的，真正难的是三件事——限多少、在哪一层限、以及怎么让几十台无状态的限流器对同一个计数器数得对。
INCR（计数加一并返回新值）就是原子的。429 Too Many Requests，服务端用它告诉客户端「你被限流了」。这是卷一 Part II「系统案例」的开篇。Ch1 给零件、Ch2 给尺子、Ch3 给顺序，Ch4 是这三样第一次合起来用——而且题目故意选得很小：一个限流器没有复杂业务，四十分钟能从需求聊到分布式竞态，正适合当范本。往后看，Ch5 的一致性哈希会回答本章留下的尾巴（限流状态怎么分到多台机器上），Ch10 的通知系统、Ch9 的爬虫都会再次用到限流。对应到现实：任何对外开放的 API（Stripe、GitHub、Twitter 的接口都有明码标价的配额），以及微服务之间的过载保护。
原书开门见山给了三个理由：防止资源被吃干（不限流，少数几个调用方就能占满整个服务的处理能力，其余人集体不可用）；省钱（很多请求背后要调按次计费的第三方接口——信用查询、支付、健康档案，限流是给账单封顶的第一道闸）；防止服务器过载（把机器人和异常用户挡在门外）。Twitter 限制每 3 小时最多发 300 条推文，Google Docs 的接口默认每用户每 60 秒最多 300 次读请求——这些数字不是随便定的，是「一个人最多能占多少公共资源」的明码标价。
不解决会怎样？算一笔具体的账：一个 API 平时稳定在 5,000 QPS，某个客户的重试逻辑写错了——失败就立刻重发、不退避——他那一侧的错误在几秒内滚成 50,000 QPS 打进来。数据库连接池被占满，剩下 99% 的正常客户一起收到 503。压垮系统的不是攻击，是一段没写退避的循环。
原书在「明确设计范围」这一步列出的条件值得原样记住，它们直接决定了后面的取舍：准确挡住超额请求；延迟要低（它在每个请求的关键路径上）；少占内存；支持分布式（多台限流器共享同一份配额）；给被拒的用户清楚提示；高容错——限流器自己出问题时，不能把整个系统一起拖下水。最后一条最容易被忽略，也最要命。
原书给了三个位置，并直接否掉了第一个。客户端限流不可靠——代码可以被改、请求可以被伪造，把配额交给调用方自己管等于没管。服务端限流放在业务代码里，上下文最全，但每个服务都要重新实现一遍。中间件限流把这一层抽出来单独坐在客户端和业务服务之间——微服务架构里这个位置通常就是 API 网关：它本来就要做鉴权、SSL 卸载、IP 白名单，顺手把限流一起做了最自然。
怎么选？原书的判据很务实：先看现有技术栈支不支持、要的算法这一层能不能实现；已经上了微服务、已经有网关在做鉴权，那就在网关上加；打算自建就要认清「造一个限流服务是要花时间的」——第三方网关是拿钱换时间。
一个能装 b 个令牌的桶，系统按固定速率往里放令牌，放满就不再放。每个请求进来先取走一个令牌，取得到就放行，取不到就丢弃。两个参数：桶容量（决定最大突发量）和填充速率（决定长期平均速率）。
关键直觉在这句：桶里攒下的令牌，就是你允许的突发额度。一个客户安静了 20 秒，桶就攒满了，他可以在下一秒一口气打出 40 个请求——但只要拉长时间看，他的平均速率永远被填充速率牢牢锁住。这正是绝大多数公开 API 想要的行为：用户偶尔手快没关系，别一直快就行。
桶怎么分？原书列了三种粒度，各有各的用途：按 API 端点各一个桶（发帖比读帖珍贵，配额自然不同）；按 IP 各一个桶（用于未登录的匿名流量）；全局一个桶（例如整个系统最多扛 10,000 QPS，这是保护自己的最后一道闸）。真实系统往往三层叠着用。
漏桶用一个先进先出队列实现：请求到达时，队列没满就入队、满了就丢弃；另一头以恒定速率从队列取出请求去处理。两个参数：队列大小和流出速率。
它和令牌桶的差别一句话说清：令牌桶管「你能不能进来」，漏桶管「里面的处理节奏」。令牌桶允许一次冲进来 40 个然后同时处理；漏桶无论外面怎么涌，里面永远每秒 2 个。所以当下游吞吐固定、经不起冲击（一台老数据库、一个按并发计费的第三方接口）时，漏桶更合适。
代价原书写得很直白：一阵突发会把队列塞满旧请求，这些旧请求处理不过来，后面刚到的、可能更有价值的新请求就会被拒——队列变成了一个「优先服务过期数据」的装置，而用户那头看到的是等了 8 秒才回来的响应。
固定窗口计数器最直观：把时间切成整分钟（或整小时），每个窗口配一个计数器，请求来了加一，加到阈值就拒绝，到下一个窗口清零。省内存、好理解、易实现。
它的毛病出在边界上，原书给的例子极其清楚：阈值 5 次/分钟，如果有 5 个请求落在 2:00:30–2:01:00、另外 5 个落在 2:01:00–2:01:30，那么在 2:00:30–2:01:30 这个滚动的一分钟里，实际放进去了 10 次，正好是配额的两倍。攻击者只要把流量对准整点两侧，就能稳定拿到双倍额度。
滑动窗口日志把这个洞堵死：不按整点分桶，而是把每个请求的时间戳记下来（通常用 Redis 的有序集合 sorted set）。新请求到达时先删掉窗口起点之前的旧时间戳，再把当前时间戳加进去，剩下的条数没超阈值就放行。任意滚动窗口内都不会超额，这是唯一真正精确的算法。代价很扎眼：内存和请求数成正比——而且原书特别点出，请求即使被拒，它的时间戳仍留在集合里。对一个正在被刷的接口来说，这个性质相当危险：内存恰好在最不该涨的时候跟着涨。
滑动窗口计数器是二者的混血，也是工程上最常用的折中：只保留前一个和当前两个窗口的计数，按重叠比例折算——当前窗口计数 + 前一窗口计数 × 重叠比例。原书的例子：阈值 7 次/分钟，前一分钟来了 7 次、当前分钟已来 5 次，此刻处在当前窗口的 30% 处，折算值 = 5 + 7 × 70% = 9.7，向下取整为 9，大于 7，拒绝。
它省内存（每个 key 只存两个数），也能抹平尖峰，但它是个近似：公式默认前一个窗口里的请求均匀分布，而真实流量从来不均匀。这个近似有多不准？下面 Cloudflare 给了实测数字。
单机限流是道送分题，一上多机就变味。原书点出的两个问题，才是这一章真正的深挖点。
竞态条件。朴素实现是「读计数 → 加一 → 写回」三步。两个请求几乎同时到达：都读到 3，都算出 4，都写回 4——来了两个请求，计数只涨了一。高并发下这种丢失持续发生，阈值形同虚设。解法见下面表 3，这里只强调一句：加锁是最直觉但最差的那个——原书直言它会显著拖慢系统，而限流器恰恰坐在每个请求的关键路径上。
同步问题。限流器要水平扩展就得无状态；可同一客户端的请求会被负载均衡打到不同的限流器上，各自记各自的账，配额自然超发。原书明确否掉了粘性会话这个偷懒方案——「既不可扩展也不灵活」：机器一挂，绑在它上面的状态全丢；扩缩容时流量重新分配，配额会突然错乱。正确答案是把状态挪进集中式存储（Redis），让所有限流器读写同一份计数。
限流规则通常写成磁盘上的配置文件，由后台 worker 定期拉取、放进缓存供中间件读取（原书样例格式取自 Lyft 开源的限流组件：一条规则声明「域 = 认证、键 = 登录、每分钟 5 次」）。这样调阈值不用改代码、不用重启。
请求被拒时返回 429 Too Many Requests；业务允许延后处理的话，也可以把请求丢进队列稍后再执行。更重要的是三个响应头——限流器和调用方之间的契约：X-Ratelimit-Limit（配额多少）、X-Ratelimit-Remaining（还剩几次）、X-Ratelimit-Retry-After（多久后可再来）。没有它们，客户端只能靠撞墙发现自己被限了；有了它们，规矩的客户端会主动减速。
监控要盯两件事：规则是不是太严（大量正常请求被误杀），以及算法在突发下是不是失效——闪购期间正常用户被大面积拒绝，就说明该换成令牌桶了。
表 1 · 五种限流算法：精度、内存与突发容忍度的三角
| 算法 | 怎么工作 | 内存 | 容突发 | 主要代价 | 适合 |
|---|---|---|---|---|---|
| 令牌桶 | 按速率补令牌，请求取一个 | 每 key 两个数，极省 | 是（攒多少放多少） | 桶容量 + 填充速率两个参数不好调 | 公开 API 的默认选择 |
| 漏桶 | FIFO 队列 + 恒定流出 | 队列长度封顶，省 | 否 | 突发会用旧请求塞满队列，新请求被拒、延迟被拉长 | 下游吞吐固定、要求平稳 |
| 固定窗口 | 整点分桶计数，到点清零 | 最省 | 否 | 边界能漏进 2 倍配额 | 粗糙的挡板；配额按自然周期结算的场景 |
| 滑动窗口日志 | 存每个请求的时间戳，按窗口清理 | 最贵，与请求数成正比；被拒的请求也占内存 | 否 | 被刷时内存跟着涨，正好在最不该涨的时候 | 配额必须一次都不能超（计费、合规） |
| 滑动窗口计数器 | 当前窗口 + 前一窗口 × 重叠比例 | 每 key 两个数，省 | 部分（尖峰被抹平） | 是近似：假设前一窗口内均匀分布 | 大规模通用场景，精度要求不极端 |
表 2 · 这道门装在哪一层
| 位置 | 能拿到什么 | 代价 / 风险 | 结论 |
|---|---|---|---|
| 客户端 | 零服务端开销，能提前避免无谓请求 | 可被伪造、可被绕过，配额交给对方自己管 | 只能当「善意提示」，不能当防线 |
| 服务端应用内 | 完整业务上下文（哪个用户、哪个资源、多贵） | 每个服务重复实现一遍；配额分散、难统一调 | 需要按业务语义精细限流时用 |
| 中间件 / API 网关 | 统一入口，顺带鉴权与 IP 白名单；业务无感知 | 多一跳延迟；网关自身成为关键路径 | 微服务下的默认答案 |
| 网络层（如 iptables） | 在 IP 层就把包丢掉，开销最低 | 看不见用户身份，只能按 IP；NAT 后面会误伤 | 抗量级冲击的补充手段，不能替代应用层 |
表 3 · 分布式下解竞态的四种做法
| 做法 | 正确性 | 延迟代价 | 说明 |
|---|---|---|---|
| 分布式锁 | 正确 | 最高——每个请求多一轮加锁解锁 | 原书直接点名它「会显著拖慢系统」；限流器在关键路径上，最不该选 |
原子自增（INCR） | 正确 | 一次往返，亚毫秒 | 固定窗口的标准解；配合 EXPIRE 让计数到点自动消失 |
| Lua 脚本 | 正确 | 一次往返 | 把「判断 + 写入」打包成一次原子执行，复杂算法（令牌桶）也能一步做完 |
| 有序集合（sorted set） | 正确且精确 | 一次往返，但内存随请求数涨 | 滑动窗口日志的天然载体：按时间戳区间删旧、统计条数一步到位 |
还有一组书末点到、但值得单独拎出来的选择：硬限流 vs 软限流。硬限流是「一次都不许超」；软限流允许在短时间内小幅越线。计费和合规场景必须硬限流，用户体验场景往往软一点更好——为了 1% 的越线把用户挡在门外，通常不划算。
限流器几乎是每个后端工程师迟早都要碰、却很少有人第一次就做对的组件。做对它意味着三件事同时成立：算法接得住业务的流量形状、状态在多机之间数得对、它自己坏掉时不会带走整个系统。今天你用的每个公开 API 背后都有它——而各家的选择相当不一样，这恰恰说明「没有最优算法，只有匹配的算法」。
4 亿 次请求上，只有 0.003% 被错误放行或错误限流——用一个数字证明了「近似算法在真实流量下足够好」。Cloudflare「How we built rate limiting capable of scaling to millions of domains」, 2017 ↗40 次、以每秒 2 次回填，超限返回 429 并附 Retry-After——「漏桶适合要求平稳出口的场景」的一份逐字可查的实例。Shopify Dev Docs「REST Admin API rate limits」↗10,000 次/秒、突发容量 5,000 次——「填充速率定长期平均、桶容量定突发上限」在这两个数字上一目了然。AWS 文档「Throttle requests to your REST APIs」↗5,000 次，超限返回 403 或 429，并用 x-ratelimit-remaining 随时告知余量——「用响应头把配额变成契约」的现成范本。GitHub Docs「Rate limits for the REST API」↗Retry-After 只是最低要求，真正需要的是指数退避 + 随机抖动。原书提到了退避与客户端缓存，但「重试同步化」这个二阶效应值得单独警惕。① 一句话：限流器不是防攻击的墙，是资源不够时决定先饿死谁的分配合同；它日常拦下的多是失控的重试循环，不是攻击者。
② 三个理由：防 DoS 式的资源饥饿、给按次计费的第三方调用封顶、防服务器过载。设计要求里最容易忘的一条是：限流器自己出问题时不能拖垮整个系统。
③ 位置三选一：客户端不可信、服务端应用内上下文最全、中间件 / API 网关是微服务下的默认答案。
④ 令牌桶：桶容量定突发上限、填充速率定长期平均；唯一天然容得下突发的算法，Stripe 与 AWS API Gateway 都用它。
⑤ 漏桶：FIFO 队列 + 恒定流出，出口平稳但不容突发，突发会用旧请求塞满队列；Shopify 用它。
⑥ 固定窗口最省事，但整点两侧能漏进 2 倍配额；滑动窗口日志最精确也最贵（被拒的请求也占内存）；滑动窗口计数器是折中，Cloudflare 实测误判率仅 0.003%。
⑦ 分布式两大坑：竞态（读—改—写丢计数，用原子自增 / Lua 脚本解，别用锁）和同步（别用粘性会话，把状态放进集中式 Redis）。
⑧ 契约要给全：429 + X-Ratelimit-Limit / -Remaining / -Retry-After；规则存配置、后台拉取，改阈值不用发版。面试里最值钱的一句是说清你选这个算法是因为业务允不允许突发，而不是背出五个算法的名字。