系统设计面试的行家指南（上）（2）

系统设计面试的行家指南（上）（1）https://developer.aliyun.com/article/1481931

百万用户及以上

扩展系统是一个迭代的过程。重复我们在这一章学到的东西可以让我们走得更远。要超越数百万用户，需要更多的微调和新策略。例如，您可能需要优化您的系统并将系统解耦到更小的服务。本章学习的所有技术应该为应对新的挑战提供一个良好的基础。在本章的结尾，我们总结了如何扩展我们的系统来支持数百万用户：

保持 web 层无状态

在每一层建立冗余

尽可能多地缓存数据

支持多个数据中心

在 CDN 中托管静态资产

通过分片扩展您的数据层

将层级划分为单独的服务

监控您的系统并使用自动化工具

祝贺你走到这一步！现在给自己一个鼓励。干得好！

参考资料

[1] Hypertext Transfer Protocol: https://en.wikipedia.org/wiki/Hypertext_Transfer_Protocol
[2] Should you go Beyond Relational Databases?:
https://blog.teamtreehouse.com/should-you-go-beyond-relational-databases
[3] Replication:  https://en.wikipedia.org/wiki/Replication_(computing)
[4] Multi-master replication:
https://en.wikipedia.org/wiki/Multi-master_replication
[5] NDB Cluster Replication: Multi-Master and Circular Replication: https://dev.mysql.com/doc/refman/5.7/en/mysql-cluster-replication-multi-master.html
[6] Caching Strategies and How to Choose the Right One:
https://codeahoy.com/2017/08/11/caching-strategies-and-how-to-choose-the-right-one/
[7] R. Nishtala, "Facebook, Scaling Memcache at," 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI ’13).
[8] Single point of failure: https://en.wikipedia.org/wiki/Single_point_of_failure
[9] Amazon CloudFront Dynamic Content Delivery:
https://aws.amazon.com/cloudfront/dynamic-content/
[10] Configure Sticky Sessions for Your Classic Load Balancer:
https://docs.aws.amazon.com/elasticloadbalancing/latest/classic/elb-sticky-sessions.html
[11] Active-Active for Multi-Regional Resiliency:
https://netflixtechblog.com/active-active-for-multi-regional-resiliency-c47719f6685b
[12] Amazon EC2 High Memory Instances:
https://aws.amazon.com/ec2/instance-types/high-memory/
[13] What it takes to run Stack Overflow:
http://nickcraver.com/blog/2013/11/22/what-it-takes-to-run-stack-overflow
[14] What The Heck Are You Actually Using NoSQL For:
http://highscalability.com/blog/2010/12/6/what-the-heck-are-you-actually-using-nosql-for.html

二、信封背面估计

在系统设计面试中，有时你会被要求使用粗略估计来估计系统容量或性能需求。根据谷歌高级研究员 Jeff Dean 的说法，“信封背面的计算是你使用思维实验和常见性能数字的组合来创建的估计，以获得满足你要求的设计的良好感觉”[1]。

您需要对可伸缩性基础有一个很好的认识，以便有效地进行预估。应该很好地理解以下概念：2 的幂，每个程序员都应该知道的延迟数字，以及可用性数字。

二的幂

虽然在处理分布式系统时，数据量会变得巨大，但计算都归结为基础。为了获得正确的计算结果，使用 2 的幂知道数据量单位是非常重要的。一个字节是 8 位的序列。一个 ASCII 字符使用一个字节的内存(8 位)。下表解释了数据量单位(表 2-1)。

每个程序员都应该知道的延迟数字

来自谷歌的迪恩博士揭示了 2010 年典型计算机操作的长度[1]。随着计算机变得更快更强大，一些数字已经过时了。然而，这些数字应该仍然能够让我们了解不同计算机操作的快慢。

注释

ns = 纳秒，s = 微秒，ms = 毫秒
1 纳秒 = 10^-9 秒
1 秒 = 10^-6 秒 = 1000 纳秒
1 毫秒 = 10^-3 秒 = 1000 秒 = 1000000 纳秒

一名谷歌软件工程师开发了一个工具来可视化迪安博士的数据。该工具还考虑了时间因素。图 2-1 显示了截至 2020 年的可视化延迟数字(图片来源：参考资料[3])。

通过分析图 2-1 中的数字，我们得到以下结论：

内存快但磁盘慢。

尽可能避免磁盘寻道。

简单压缩算法速度快。

如果可能的话，在通过互联网发送数据之前对其进行压缩。

数据中心通常在不同的区域，它们之间发送数据需要时间。

可用性数字

高可用性是指系统在期望的长时间内持续运行的能力。高可用性以百分比来衡量，100%意味着服务没有停机时间。大多数服务介于 99%和 100%之间。

服务水平协议(SLA)是服务提供商常用的术语。这是您(服务提供商)和您的客户之间的协议，该协议正式定义了您的服务将提供的正常运行时间水平。云提供商亚马逊[4]、谷歌[5]和微软[6]将其 SLA 设定为 99.9%或以上。正常运行时间传统上是以 9 来衡量的。九越多越好。如表 2-3 所示，9 的数量与预期的系统停机时间相关。

示例：估计 Twitter QPS 和存储需求

请注意，以下数字仅用于本练习，因为它们不是来自 Twitter 的真实数字。

假设：

3 亿月活跃用户。

50%的用户每天都使用 Twitter。

用户平均每天发布 2 条推文。

10%的推文包含媒体。

数据保存 5 年。

估计：

每秒查询(QPS)估计：

日活跃用户(DAU) = 3 亿 * 50% = 1.5 亿
推文 QPS = 1.5 亿 * 2 推文 / 24 小时 / 3600 秒 = ~3500
峰值 QPS = 2 * QPS = ~7000

我们在这里只估计媒体存储量。

平均推文大小：

推特 ID 64 字节
文本 140 字节
媒体 1 MB
媒体存储： 每天 1.5 亿 * 2 * 10% * 1mb = 30tb
5 年介质存储： 30 TB * 365 * 5 = ~55 PB

提示

信封背面的评估是关于整个过程的。解决问题比获得结果更重要。面试官可能会测试你解决问题的能力。以下是一些可以遵循的提示：

舍入和近似。面试时很难进行复杂的数学运算。比如99987 / 9.1是什么结果？没必要花宝贵的时间去解复杂的数学题。不期望精度。使用对你有利的整数和近似值。除法问题可以简化为：10 万 / 10。

写下你的假设。写下你的假设供以后参考是个好主意。

给你的单位贴上标签。你写下“5”，是指 5 KB 还是 5 MB？你可能会对此感到困惑。写下单位，因为“5 MB”有助于消除歧义。

常见的粗略估计：QPS、峰值 QPS、存储、缓存、服务器数量等。准备面试的时候可以练习一下这些计算。熟能生巧。

祝贺你走到这一步！现在给自己一个鼓励。干得好！

参考资料

[1] J. Dean.Google Pro Tip: Use Back-Of-The-Envelope-Calculations To Choose The Best Design:
http://highscalability.com/blog/2011/1/26/google-pro-tip-use-back-of-the-envelope-calculations-to-choo.html
[2] System design primer: https://github.com/donnemartin/system-design-primer
[3] Latency Numbers Every Programmer Should Know:
https://colin-scott.github.io/personal_website/research/interactive_latency.html
[4] Amazon Compute Service Level Agreement:
https://aws.amazon.com/compute/sla/
[5] Compute Engine Service Level Agreement (SLA):
https://cloud.google.com/compute/sla
[6] SLA summary for Azure services: https://azure.microsoft.com/en-us/support/legal/sla/summary/

三、系统设计面试的框架

你刚刚获得了梦寐以求的理想公司的现场面试机会。招聘协调员会给你发一份当天的日程表。浏览列表，你会感觉很好，直到你的目光落在这个面试环节——系统设计面试。

系统设计面试通常令人生畏。它可以像“设计一个知名产品 X？”。这些问题模棱两可，而且似乎过于宽泛。你的疲倦是可以理解的。毕竟，怎么可能有人在一个小时内设计出一款流行的产品，而这需要数百甚至数千名工程师来完成？

好消息是没人期望你这么做。现实世界的系统设计极其复杂。例如，谷歌搜索看似简单；然而，支撑这种简单性的技术数量确实令人吃惊。如果没有人期望你在一个小时内设计出一个真实世界的系统，那么系统设计面试有什么好处呢？

系统设计面试模拟现实生活中的问题解决，两名员工合作解决一个模糊的问题，并提出一个符合他们目标的解决方案。这个问题是开放式的，没有完美的答案。与你在设计过程中所做的工作相比，最终的设计没有那么重要。这允许你展示你的设计技巧，捍卫你的设计选择，并以建设性的方式回应反馈。

让我们把桌子翻过来，想想面试官走进会议室见你时脑子里在想什么。面试官的首要目标是准确评估你的能力。她最不希望的就是给出一个不确定的评价，因为会议进行得很糟糕，没有足够的信号。在系统设计面试中，面试官想要的是什么？

许多人认为系统设计面试是关于一个人的技术设计技能。远不止如此。一次有效的系统设计面试会给出一个人的合作能力、在压力下工作的能力以及建设性地解决歧义的能力的强烈信号。问出好问题的能力也是一项必备技能，许多面试官专门寻找这项技能。

一个好的面试官也会寻找危险信号。过度工程是许多工程师的真正疾病，因为他们喜欢设计的纯粹性，而忽视权衡。他们常常意识不到过度设计系统的复合成本，许多公司为这种无知付出了高昂的代价。你肯定不希望在系统设计面试中表现出这种倾向。其他危险信号包括心胸狭窄、固执等。

在本章中，我们将复习一些有用的技巧，并介绍一个简单有效的框架来解决系统设计面试问题。

有效系统设计面试的 4 步流程

每个系统设计面试都不一样。伟大的系统设计面试是开放式的，没有放之四海而皆准的解决方案。然而，每个系统设计面试都有一些步骤和共同点。

第一步——了解问题并确定设计范围

“老虎为什么要吼叫？”

教室后面突然伸出一只手。

“是的，吉米？”，老师回应道。

“因为他饿了”。

“非常好的吉米。”

在童年时代，吉米总是第一个回答班上的问题。每当老师提问时，教室里总有一个孩子爱试着回答这个问题，不管他是否知道答案。那是吉米。

吉米是个优等生。他以很快知道所有答案而自豪。在考试中，他通常是第一个做完题目的人。他是教师参加任何学术竞赛的首选。

不要像吉米一样。

在系统设计面试中，不假思索地快速给出答案不会给你加分。没有完全理解要求的回答是一个巨大的危险信号，因为面试不是一个琐事竞赛。没有正确的答案。

因此，不要马上给出解决方案。慢点。深入思考，提出问题，明确需求和假设。这是极其重要的。

作为工程师，我们喜欢解决难题，一头扎进最终的设计中；然而，这种方法很可能会导致您设计错误的系统。作为一名工程师，最重要的技能之一是提出正确的问题，做出适当的假设，并收集构建系统所需的所有信息。所以，不要害怕提问。

当你提问时，面试官要么直接回答你的问题，要么让你做出假设。如果是后者，在白板或纸上写下你的假设。你以后可能需要它们。

问什么样的问题？提出问题，了解确切的要求。这里有一个帮助你开始的问题列表：

我们要构建什么样的特性？

产品有多少用户？

公司预计扩大规模的速度有多快？3 个月、6 个月和一年后的预期规模是多少？

公司的技术栈是什么？您可以利用哪些现有服务来简化设计？

例子

如果你被要求设计一个新闻订阅系统，你会问一些有助于你阐明需求的问题。你和面试官之间的对话可能是这样的：

考生 :这是手机 app 吗？还是一个 web app？还是两者都有？

面试官 :都有。

候选人 :产品最重要的特点是什么？

面试官 :发帖和查看好友动态的能力。

候选人 : 新闻提要是按时间倒序排序还是按特定顺序排序？这种特殊的顺序意味着每个帖子被赋予不同的权重。例如，来自你亲密朋友的帖子比来自一个团体的帖子更重要。

面试官 : 为了简单起见，我们假设提要是按时间倒序排序的。

候选人 : 一个用户可以有多少好友？

面试官 : 5000

候选人 :车流量是多少？

面试官 :日活跃用户 1000 万(DAU)

候选：feed 可以包含图片、视频，或者只是文字？

面试官 :可以包含媒体文件，包括图片和视频。

以上是你可以问面试官的一些问题。理解需求和澄清歧义很重要

第二步——提出高水平的设计并获得认同

在这一步，我们的目标是开发一个高层次的设计，并与面试官就设计达成一致。在面试过程中与面试官合作是个好主意。

拿出最初的设计蓝图。寻求反馈。把你的面试官当成队友，一起努力。许多优秀的面试官喜欢交谈和参与。

在白板或纸上画出关键部件的方框图。这可能包括客户端(移动/web)、API、web 服务器、数据存储、缓存、CDN、消息队列等。

进行粗略计算，评估你的蓝图是否符合规模限制。大声思考。在深入调查之前，如果有必要的话，和面试官交流一下。

如果可能的话，浏览几个具体的用例。这将帮助您构建高层次的设计。用例也有可能帮助您发现您还没有考虑的边缘用例。

我们应该在这里包括 API 端点和数据库模式吗？这个要看问题。对于“设计谷歌搜索引擎”这样的大型设计问题来说，这有点太低级了。对于像为多人扑克游戏设计后端这样的问题，这是一个公平的游戏。与你的面试官交流。

例子

让我们用“设计一个新闻反馈系统”来演示如何进行高级设计。在这里 你不需要了解系统实际上是如何工作的。所有细节将在第十一章解释。

在高层次上，设计分为两个流程：提要发布和新闻提要构建。

Feed 发布：当用户发布帖子时，相应的数据被写入缓存/数据库，该帖子将被填充到好友的新闻 Feed 中。

新闻提要构建：新闻提要是通过按时间倒序聚合朋友的帖子来构建的。

图 3-1 和图 3-2 分别展示了提要发布和新闻提要构建流程的高级设计。

第三步——设计深潜

在这一步，你和你的面试官应该已经达到了以下目标：

商定总体目标和功能范围

勾画出总体设计的高层次蓝图

从你的面试官那里获得了关于高层设计的反馈

根据她的反馈，对深度探索中需要关注的领域有了一些初步想法

你应该和面试官一起确定架构中组件的优先级。值得强调的是，每次面试都是不同的。有时候，面试官可能会暗示她喜欢关注高层次的设计。有时，对于高级候选人面试，讨论可能是关于系统性能特征，可能集中在瓶颈和资源估计上。在大多数情况下，面试官可能希望你深入了解一些系统组件的细节。对于 URL shortener，深入研究将长 URL 转换成短 URL 的哈希函数设计是很有趣的。对于一个聊天系统来说，如何减少延迟和如何支持在线/离线状态是两个有趣的话题。

时间管理是必不可少的，因为人们很容易被无法展示你能力的微小细节冲昏头脑。你必须准备好向面试官展示的信号。尽量不要陷入不必要的细节。例如，在系统设计面试中详细讨论脸书 feed 排名的 EdgeRank 算法是不理想的，因为这会花费很多宝贵的时间，并且不能证明你设计可扩展系统的能力。

例子

至此，我们已经讨论了新闻订阅系统的高级设计，面试官对你的提议很满意。接下来，我们将研究两个最重要的用例：

1。订阅源发布

2。新闻提要检索

图 3-3 和图 3-4 显示了两个用例的详细设计，这将在第十一章中详细解释。

第四步——总结

在这最后一步，面试官可能会问你几个后续问题，或者给你讨论其他要点的自由。这里有几个方向可以遵循：

面试官可能希望你找出系统的瓶颈并讨论潜在的改进。永远不要说你的设计是完美的，没有什么可以改进的。总有需要改进的地方。这是一个展示你批判性思维并留下好的最终印象的好机会。

给面试官回顾一下你的设计可能会有帮助。如果你提出了一些解决方案，这一点尤为重要。在长时间的谈话后，刷新面试官的记忆会很有帮助。

错误案例(服务器故障、网络丢失等。)都是很有意思的话题。

运营问题值得一提。如何监控指标和错误日志？如何铺开系统？

如何处理下一个比例曲线也是一个有趣的话题。例如，如果您当前的设计支持 100 万用户，您需要做哪些更改来支持 1000 万用户？

如果你有更多的时间，提出你需要的其他改进。

作为总结，我们总结了一系列该做和不该做的事情。

Dos

总是要求澄清。不要假设你的假设是正确的。

理解问题的要求。

没有正确的答案，也没有最好的答案。旨在解决年轻初创公司问题的解决方案不同于拥有数百万用户的老牌公司。确保你理解这些要求。

让面试官知道你在想什么。和你的面试沟通。

如有可能，建议多种方法。

一旦你和面试官就蓝图达成一致，就要详细讨论每一部分。首先设计最关键的部件。

向面试官反映想法。一个好的面试官像队友一样和你一起工作。

永不放弃。

不要做

不要对典型的面试问题毫无准备。

在没有明确需求和假设的情况下，不要急于找到解决方案。

不要一开始就对单个组件进行过多的细节描述。首先给出概要设计，然后再向下钻取。

如果你卡住了，不要犹豫，寻求提示。

再次沟通。不要在沉默中思考。

不要以为一旦你给出了设计，你的面试就结束了。直到你的面试官说你结束了，你才算结束。尽早并经常寻求反馈。

每一步上的时间分配

系统设计面试问题通常非常宽泛，45 分钟或者一个小时都不足以涵盖整个设计。时间管理至关重要。每一步应该花多少时间？以下是在 45 分钟的面试中分配时间的粗略指南。请记住这是一个粗略的估计，实际的时间分布取决于问题的范围和面试官的要求。

第一步了解问题并确定设计范围：3 - 10 分钟

第二步提出高级设计并获得认同：10 - 15 分钟

第三步设计深潜：10 - 25 分钟

第四步包装：3 - 5 分钟

四、设计速率限制器

在网络系统中，速率限制器用于控制客户端或服务发送流量的速率。在 HTTP 世界中，速率限制器限制了在特定时间段内允许发送的客户端请求的数量。如果 API 请求计数超过速率限制器定义的阈值，所有超出的调用都会被阻塞。下面举几个例子：

一个用户每秒最多只能写 2 篇文章。

您每天最多可以从同一个 IP 地址创建 10 个账户。

同一台设备每周可申领奖励不超过 5 次。

本章要求你设计一个限速器。在开始设计之前，我们首先来看看使用 API 速率限制器的好处：

防止拒绝服务(DoS)攻击造成的资源饥饿[1]。几乎所有大型科技公司发布的 API 都实施了某种形式的速率限制。例如，Twitter 将推文数量限制为每 3 小时 300 条[2]。Google docs APIs 有如下默认限制：每用户每 60 秒 300 个读取请求[3]。速率限制器通过阻止过量呼叫来防止有意或无意的 DoS 攻击。

降低成本。限制过多的请求意味着更少的服务器和分配更多的资源给高优先级的 API。速率限制对于使用付费第三方 API 的公司来说极其重要。例如，您需要为以下外部 API 的每次调用付费：检查信用、付款、检索健康记录等。限制通话次数对降低成本至关重要。

防止服务器过载。为了减少服务器负载，速率限制器用于过滤掉由机器人或用户不当行为引起的过量请求。

第一步——了解问题并确定设计范围

速率限制可以使用不同的算法来实现，每种算法都有其优缺点。面试官和候选人之间的互动有助于澄清我们试图建立的限速器的类型。

候选 : 我们要设计什么样的限速器？是客户端速率限制器还是服务器端 API 速率限制器？

采访者 :好问题。我们关注服务器端 API 速率限制器。

候选人 : 速率限制器是否基于 IP、用户 ID 或其他属性来限制 API 请求？

采访者 :限速器应该足够灵活，以支持不同的节流规则。

候选 : 系统的规模是多少？是为创业公司打造，还是为用户基数大的大公司打造？

面试官 :系统必须能够处理大量的请求。

候选 : 系统会在分布式环境下工作吗？

面试官 :是的。

候选 : 速率限制器是一个独立的服务还是应该在应用程序代码中实现？

采访者 :这是你的设计决定。

候选 : 我们需要通知被节流的用户吗？

面试官 :是的。

要求

以下是对系统要求的总结：

准确限制过分的要求。

低潜伏期。速率限制器不应该减慢 HTTP 响应时间。

尽量少用内存。

分布式限速。速率限制器可以在多个服务器或进程之间共享。

异常处理。当用户的请求被限制时，向用户显示明确的异常。

容错性高。如果速率限制器出现任何问题(例如，缓存服务器离线)，不会影响整个系统。

第二步——提出高水平的设计并获得认同

让我们保持简单，使用基本的客户端和服务器模型进行通信。

限速器放哪里？

直观地说，你可以在客户端或服务器端实现速率限制器。

客户端实现。一般来说，客户端是一个不可靠的实施速率限制的地方，因为客户端请求很容易被恶意参与者伪造。此外，我们可能无法控制客户端的实现。

服务器端实现。图 4-1 显示了放置在服务器端的速率限制器。

除了客户端和服务器端的实现，还有另一种方法。我们没有在 API 服务器上设置速率限制器，而是创建了一个速率限制器中间件，来抑制对 API 的请求，如图 4-2 所示。

让我们用图 4-3 中的例子来说明速率限制在这个设计中是如何工作的。假设我们的 API 允许每秒 2 个请求，一个客户机在一秒钟内向服务器发送 3 个请求。前两个请求被路由到 API 服务器。然而，速率限制器中间件抑制了第三个请求，并返回一个 HTTP 状态代码 429。HTTP 429 响应状态代码表示用户发送了太多请求。

云微服务[4]已经变得非常流行，速率限制通常在一个名为 API gateway 的组件中实现。API gateway 是一种完全托管的服务，支持速率限制、SSL 终止、身份验证、IP 白名单、静态内容服务等。现在，我们只需要知道 API 网关是一个支持速率限制的中间件。

在设计速率限制器时，我们要问自己的一个重要问题是：应该在哪里实现速率限制器，在服务器端还是在网关中？没有绝对的答案。这取决于您公司当前的技术堆栈、工程资源、优先级、目标等。这里有几个通用的准则：

评估你目前的技术栈，比如编程语言、缓存服务等。确保您当前的编程语言能够有效地在服务器端实现速率限制。

确定适合您业务需求的速率限制算法。当你在服务器端实现一切时，你就完全控制了算法。但是，如果您使用第三方网关，您的选择可能会受到限制。

如果你已经使用了微服务架构，并且在设计中包含了 API 网关来执行认证、IP 白名单等。，您可以向 API 网关添加速率限制器。

自建费率 限制服务需要时间。如果您没有足够的工程资源来实现速率限制器，商业 API 网关是一个更好的选择。

限速算法

速率限制可以使用不同的算法来实现，每种算法都有明显的优缺点。尽管本章并不关注算法，但从高层次理解它们有助于选择合适的算法或算法组合来适应我们的用例。下面是流行算法的列表：

令牌桶

漏桶

固定窗口计数器

滑动窗口日志

推拉窗计数器

令牌桶算法

令牌桶算法广泛用于速率限制。简单易懂，互联网公司常用。Amazon [5]和 Stripe [6]都使用这种算法来抑制他们的 API 请求。

令牌桶算法工作如下：

令牌桶是具有预定义容量的容器。令牌以预设的速率定期放入桶中。一旦桶满了，就不再添加令牌。如图 4-4 所示，令牌桶容量为 4。加油员每秒钟往桶里放 2 个代币。一旦桶满了，额外的代币就会溢出。

每个请求消耗一个令牌。当请求到达时，我们检查桶中是否有足够的令牌。图 4-5 解释了它是如何工作的。

如果有足够的令牌，我们为每个请求取出一个令牌，请求通过。

如果没有足够的令牌，请求被丢弃。

图 4-6 说明了代币消费、 、 和速率限制逻辑是如何工作的。在此示例中，令牌桶大小为 4，再填充速率为每 1 分钟 4 次。

令牌桶算法采用两个参数：

桶大小：桶中允许的最大令牌数

充值率：每秒钟投入桶中的代币数量

我们需要多少桶？这是不同的，它取决于限速规则。这里有几个例子。

对于不同的 API 端点，通常需要有不同的桶。例如，如果允许用户每秒发 1 篇帖子，每天添加 150 个朋友，每秒 5 篇帖子，则每个用户需要 3 个桶。

如果我们需要根据 IP 地址限制请求，每个 IP 地址都需要一个桶。

如果系统允许每秒最多 10，000 个请求，那么让所有请求共享一个全局桶是有意义的。

优点：

该算法易于实现。

记忆高效。

令牌桶允许短时间的流量爆发。只要还有令牌，请求就可以通过。

缺点：

算法中的两个参数是桶大小和令牌再填充率。然而，对它们进行适当的调优可能是一个挑战。

漏桶算法

泄漏桶算法类似于令牌桶，只是请求以固定速率处理。它通常用先进先出(FIFO)队列来实现。算法工作如下：

当请求到达时，系统检查队列是否已满。如果未满，请求将被添加到队列中。

否则，请求被放弃。

请求被从队列中取出并定期处理。

图 4-7 解释了算法的工作原理。

漏桶算法取以下两个参数：

桶大小：等于队列大小。该队列以固定的速率保存要处理的请求。

流出率：它定义了以固定的速率可以处理多少个请求，通常以秒为单位。

电子商务公司 Shopify 使用漏桶进行限速[7]。

优点：

给定有限队列大小的内存效率。

请求以固定速率处理，因此适用于需要稳定流出速率的用例。

缺点：

突发流量用旧请求填满队列，如果不及时处理，最近的请求将受到速率限制。

算法中有两个参数。正确地调整它们可能不容易。

固定窗口计数器算法

固定窗口计数器算法工作如下：

该算法将时间轴分为固定大小的时间窗口，并为每个窗口分配一个计数器。

每个请求都使计数器加 1。

一旦计数器达到预定义的阈值，新的请求就会被丢弃，直到新的时间窗口开始。

让我们用一个具体的例子来看看它是如何工作的。在图 4-8 中，时间单位是 1 秒，系统允许每秒最多 3 次请求。在每个第二个窗口中，如果收到 3 个以上的请求，多余的请求将被丢弃，如图 4-8 所示。

此算法的一个主要问题是，时间窗口边缘的流量突发可能会导致超过允许配额的请求通过。考虑以下情况：

在图 4-9 中，系统允许每分钟最多 5 个请求，可用配额在人性化的整数分钟重置。如图所示，在 2:00:00 和 2:01:00 之间有五个请求，在 2:01:00 和 2:02:00 之间还有五个请求。对于 2:00:30 到 2:01:30 之间的一分钟窗口，有 10 个请求通过。这是允许请求的两倍。

优点：

记忆高效。

通俗易懂。

在单位时间窗口结束时重置可用配额适合某些用例。

缺点：

窗口边缘的流量峰值可能会导致超过允许配额的请求通过。

滑动窗口日志算法

如前所述，固定窗口计数器算法有一个主要问题：它允许更多的请求在窗口边缘通过。滑动窗口日志算法解决了这个问题。其工作原理如下：

该算法跟踪请求时间戳。时间戳数据通常保存在缓存中，例如 Redis 的排序集[8]。

当一个新的请求进来时，删除所有过时的时间戳。过时的时间戳被定义为比当前时间窗口的开始时间更早的时间戳。

将新请求的时间戳添加到日志中。

如果日志大小等于或小于允许的计数，则接受请求。否则，它被拒绝。

我们用一个如图 4-10 所示的例子来解释这个算法。

在本例中，速率限制器允许每分钟 2 个请求。通常，Linux 时间戳存储在日志中。然而，为了更好的可读性，在我们的例子中使用了人类可读的时间表示。

新请求在 1:00:01 到达时，日志为空。因此，请求被允许。

一个新请求在 1:00:30 到达，时间戳 1:00:30 被插入到日志中。插入后，日志大小为 2，不超过允许的计数。因此，请求被允许。

一个新请求在 1:00:50 到达，时间戳被插入到日志中。插入后，日志大小为 3，大于允许的大小 2。因此，即使时间戳保留在日志中，该请求也会被拒绝。

一个新的请求到达 1:01:40。范围[1:00:40, 1:01:40]内的请求在最新的时间范围内，但是在 1:00:40 之前发送的请求已经过时。从日志中删除了两个过期的时间戳：1:00:01 和 1:00:30。删除操作之后，日志大小变为 2；因此，请求被接受。

优点：

该算法实现的速率限制非常精确。在任何滚动窗口中，请求都不会超过速率限制。

缺点：

该算法消耗大量内存，因为即使请求被拒绝，其时间戳仍可能存储在内存中。

滑动窗口计数器算法

滑动窗口计数器算法是一种结合了固定窗口计数器和滑动窗口日志的混合方法。该算法可以通过两种不同的方法来实现。我们将在本节中解释一个实现，并在本节的最后为另一个实现提供参考。图 4-11 说明了这种算法是如何工作的。

假设速率限制器每分钟最多允许 7 个请求，前一分钟有 5 个请求，当前分钟有 3 个请求。对于在当前分钟到达 30%位置的新请求，使用以下公式计算滚动窗口中的请求数：

请求当前窗口 + 请求前一窗口 * 滚动窗口与前一窗口的重叠百分比

利用这个公式，我们得到 3 + 5 * 0.7% = 6.5 的请求。根据使用情况，该数字可以向上或向下取整。在我们的例子中，它被向下舍入到 6。

由于速率限制器允许每分钟最多 7 个请求，当前请求可以通过。但是，在再收到一个请求后，将达到限制。

由于篇幅限制，我们在这里不讨论其他实现。感兴趣的读者应该参考参考资料[9]。这个算法并不完美。它有利有弊。

优点

它平滑流量峰值，因为速率是基于前一窗口的平均速率。

记忆高效。

缺点

只对不那么严格的回望窗有效。这是实际速率的近似值，因为它假设前一个窗口中的请求是均匀分布的。然而，这个问题可能没有看起来那么糟糕。根据 Cloudflare [10]所做的实验，在 4 亿个请求中，只有 0.003%的请求被错误地允许或速率受限。

高层建筑

速率限制算法的基本思想很简单。在高层，我们需要一个计数器来跟踪从同一个用户、IP 地址等发出了多少请求。如果计数器大于限制值，则不允许请求。

我们应该把柜台放在哪里？由于磁盘访问缓慢，使用数据库不是一个好主意。选择内存缓存是因为它速度快，并且支持基于时间的过期策略。例如，Redis [11]是实现利率限制的一个流行选项。它是一个内存存储，提供两个命令：INCR 和过期。

INCR:存储的计数器加 1。

到期：设置计数器超时。如果超时，计数器将自动删除。

图 4-12 显示了速率限制的高级架构，其工作原理如下：

客户端向限速中间件发送请求。

限速中间件从 Redis 中相应的桶中取出计数器，检查是否达到限额。

如果达到限制，请求被拒绝。

如果没有达到限制，请求被发送到 API 服务器。同时，系统递增计数器并将其保存回 Redis。

第三步——设计深潜

图 4-12 中的高层设计没有回答以下问题：

限速规则是如何创建的？规则存储在哪里？

如何处理速率受限的请求？

在本节中，我们将首先回答有关速率限制规则的问题，然后讨论处理速率限制请求的策略。最后，我们将讨论分布式环境中的速率限制、详细设计、性能优化和监控。

限速规则

Lyft 开源了他们的限速组件[12]。我们将查看组件内部，并查看一些速率限制规则的示例：

域 : 消息传递

描述符 :

–按键-:-消息 _ 类型

价值 :营销

利率 _ 限额 :

单位 : 日

请求 _ 每单位 : 5

在上述示例中，系统被配置为每天最多允许 5 条营销消息。下面是另一个例子：

域名 : 认证

描述符 :

–键-:-auth _ type

值 :登录

利率 _ 限额 :

单位 :分钟

请求 _ 每单位 : 5

该规则显示，客户端不允许在 1 分钟内登录 5 次以上。规则通常写在配置文件中并保存在磁盘上。

超过速率限制

如果请求是速率受限的，API 会向客户端返回一个 HTTP 响应代码 429(请求太多)。根据用例的不同，我们可能会将速率受限的请求排入队列，以便稍后处理。例如，如果一些订单由于系统过载而受到费率限制，我们可能会将这些订单留待以后处理。

限速器标题

客户端如何知道它是否被节流？客户端如何知道在被节流之前允许的剩余请求的数量？答案就在 HTTP 响应头中。速率限制器向客户端返回以下 HTTP 报头：

X-Ratelimit-Remaining:窗口内允许请求的剩余数量。

X-Ratelimit-Limit: 表示客户在每个时间窗口内可以拨打多少个电话。

X-Ratelimit-Retry-After:等待的秒数，直到可以再次发出请求而不被限制。

当用户发送过多请求时，向客户端返回 429 过多请求错误和X-RateLimit-Retry-After报头。

详细设计

图 4-13 展示了系统的详细设计。

规则存储在磁盘上。工作人员经常从磁盘中提取规则，并将它们存储在缓存中。

当客户端向服务器发送请求时，请求首先被发送到限速器中间件。

限速器中间件从缓存中加载规则。它从 Redis 缓存中获取计数器和上次请求时间戳。基于该响应，速率限制器决定：

如果请求没有速率限制，则转发给 API 服务器。

如果请求是速率受限的，速率限制器向客户端返回 429 过多请求错误。与此同时，请求要么被丢弃，要么被转发到队列。

分布式环境中的限速器

构建一个在单一服务器环境中工作的速率限制器并不困难。然而，扩展系统以支持多个服务器和并发线程是另一回事。有两个挑战：

比赛条件

同步发布

比赛状态

如前所述，速率限制器在高层工作如下：

从 Redis 中读取 计数器 的值。

检查 ( 计数器+1)是否超过阈值。

如果不是，Redis 中的计数器值加 1。

如图 4-14 所示，竞争条件可能发生在高度并发的环境中。

假设 Redis 中的 计数器 的值为 3。如果两个请求同时读取 计数器 的值，在它们中的任何一个写回该值之前，每个请求都将把 计数器 加 1，并写回该值，而不检查另一个线程。两个请求(线程)都认为它们拥有正确的 计数器 值 4。然而，正确的 计数器的 值应该是 5。

锁是解决竞争状况的最明显的解决方案。但是，锁会显著降低系统速度。有两种策略常用来解决这个问题：Lua 脚本[13]和 Redis 中的有序集数据结构[8]。对这些策略感兴趣的读者，可以参考相应的参考资料[8] [13]。

同步发布

同步是分布式环境中需要考虑的另一个重要因素。为了支持数百万用户，一台限速服务器可能不足以处理流量。当使用多个速率限制器服务器时，需要同步。例如，在图 4-15 的左侧，客户端 1 向速率限制器 1 发送请求，客户端 2 向速率限制器 2 发送请求。由于 web 层是无状态的，客户端可以向不同的速率限制器发送请求，如图 4-15 右侧所示。如果没有同步发生，速率限制器 1 不包含关于客户端 2 的任何数据。因此，限速器不能正常工作。

一种可能的解决方案是使用粘性会话，允许客户端向同一个速率限制器发送流量。这种解决方案是不可取的，因为它既不可伸缩也不灵活。更好的方法是使用像 Redis 这样的集中式数据存储。设计如图 4-16 所示。

性能优化

性能优化是系统设计面试中的常见话题。我们将从两个方面进行改进。

首先，多数据中心设置对于速率限制器至关重要，因为对于远离数据中心的用户来说，延迟很高。大多数云服务提供商在世界各地建立了许多边缘服务器。例如，截至 20 20 年 5 月 20 日，Cloudflare 拥有 194 台地理位置分散的边缘服务器[14]。流量被自动路由到最近的边缘服务器，以减少延迟。

第二，用最终的一致性模型同步数据。如果您不清楚最终的一致性模型，请参考“第六章：设计键值存储”中的“一致性”一节

监控

实施限速器后，收集分析数据以检查限速器是否有效非常重要。首先，我们要确保：

限速算法有效。

限速规则有效。

例如，如果速率限制规则太严格，许多有效请求会被丢弃。在这种情况下，我们希望稍微放宽一些规则。在另一个例子中，我们注意到当流量突然增加时，如闪购，我们的限速器变得无效。在这种情况下，我们可以替换算法来支持突发流量。令牌桶很适合这里。

第四步——总结

在本章中，我们讨论了不同的速率限制算法及其优缺点。讨论的算法包括：

令牌桶

漏桶

固定窗口

滑动窗口日志

推拉窗计数器

然后，我们讨论了系统架构、分布式环境中的速率限制器、性能优化和监控。与任何系统设计面试问题类似，如果时间允许，您还可以提及其他话题：

硬 vs 软限速。

硬：请求数量不能超过阈值。

软：请求可以在短时间内超过阈值。

分级限速。在本章中，我们只讨论了应用层(HTTP:第 7 层)的速率限制。有可能在其他层应用速率限制。例如，您可以使用 Iptables [15] (IP:第 3 层)通过 IP 地址应用速率限制。注：开放系统互连模型(OSI 模型)有 7 层[16]:第 1 层：物理层，第 2 层：数据链路层，第 3 层：网络层，第 4 层：传输层，第 5 层：会话层，第 6 层：表示层，第 7 层：应用层。

避免被费率限制。用最佳实践设计您的客户端：

使用客户端缓存避免频繁的 API 调用。

了解限制，不要在短时间内发送太多请求。

包含捕捉异常或错误的代码，以便您的客户端能够从容地从异常中恢复。

添加足够的回退时间以重试逻辑。

祝贺你走到这一步！现在给自己一个鼓励。干得好！

参考资料

[1] Rate-limiting strategies and techniques: https://cloud.google.com/solutions/rate-limiting-strategies-techniques
[2] Twitter rate limits: https://developer.twitter.com/en/docs/basics/rate-limits
[3] Google docs usage limits: https://developers.google.com/docs/api/limits
[4] IBM microservices: https://www.ibm.com/cloud/learn/microservices
[5] Throttle API requests for better throughput:
https://docs.aws.amazon.com/apigateway/latest/developerguide/api-gateway-request-throttling.html
[6] Stripe rate limiters: https://stripe.com/blog/rate-limiters
[7] Shopify REST Admin API rate limits: https://help.shopify.com/en/api/reference/rest-admin-api-rate-limits
[8] Better Rate Limiting With Redis Sorted Sets: https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/
[9] System Design — Rate limiter and Data modelling: https://medium.com/@saisandeepmopuri/system-design-rate-limiter-and-data-modelling-9304b0d18250
[10] How we built rate limiting capable of scaling to millions of domains: https://blog.cloudflare.com/counting-things-a-lot-of-different-things/
[11] Redis website: https://redis.io/
[12] Lyft rate limiting: https://github.com/lyft/ratelimit
[13] Scaling your API with rate limiters: https://gist.github.com/ptarjan/e38f45f2dfe601419ca3af937fff574d#request-rate-limiter
[14] What is edge computing: https://www.cloudflare.com/learning/serverless/glossary/what-is-edge-computing/
[15] Rate Limit Requests with Iptables: https://blog.programster.org/rate-limit-requests-with-iptables
[16] OSI model: https://en.wikipedia.org/wiki/O

系统设计面试的行家指南（上）（3）https://developer.aliyun.com/article/1481933