非理性繁荣!

通过建筑面试

9月27日2016.申请下面谈

我最难忘的一次面试开始于一个完全出乎意料的问题:“你对微积分的记忆力如何?”我笑着说,已经有好几年了,而且我已经很不练习了。尽管如此,我们还是花了一个小时做微积分,我把它炸得很惨。

很多人对“建筑面试”也有类似的疑虑,这是我最喜欢的互联网行业有经验的求职者的面试之一,我决定写我的算法来解决这些问题。


在跳之前,几个典型的建筑面试问题的例子:

  • 为Facebook设计架构,推特,超级或Foursquare。
  • 绘制您选择的基本Web应用程序。
  • 设计一个可靠的网站,类似于报纸的网站。
  • 设计一个可伸缩的API来驱动手机游戏。

从这个起点开始,面试官会给你更多的限制来解决(“你的数据库开始超载了”),或者让你想想你的系统会遇到的扩展问题,以及如何解决它们(“嗯,首先,我认为我们会用完了处理传入请求的工人”)。


这类访谈的基本算法是:

  1. 绘制当前设计的图表。
  2. 在设计中应用一个新的约束。
  3. 确定由该约束创建的瓶颈。
  4. 更新设计以解决瓶颈。

这可能不足以帮助你在下一次建筑面试中取得好成绩,所以这篇文章的其余部分将通过一个简单的基础知识来绘制建筑图,然后深入研究特定约束造成的瓶颈。

图解法

关于技术图表最重要的一点是,它更像是一门艺术而不是科学。只要你一直做一些合理的事情,你会没事的。

在面试中,你几乎总是在白板上写字,但如果你发现自己在电脑上画图表,我是它的超级粉丝Omnigraffle.尽管它并不便宜,但我认为它是一项有价值的投资(除了绘制图表外,我还用它绘制线框图)。

我们来举几个例子。

左边是一台运行web服务器和数据库的服务器,在右边有两个服务器:一个运行Web服务器,另一个运行数据库。

用两个进程表示一个服务器,用一个进程表示两个服务器。

很少有惯例,但通常服务器是盒子,流程是盒子,数据库或其他存储机制是柱面。不过,把所有东西都放在盒子里是完全没有问题的。服务器通常以服务器类型和唯一编号命名,例如frontend01frontend02对于这类的第一个和第二个服务器前端.在您的示例中添加更多的服务器时,编号是有帮助的。代表1作为01非常武断,但是有一点“气味”这意味着您以前已经为拥有9台以上服务器的服务器组命名过服务器(您绝对可以编写一些非常合理的论证,说明以这种方式命名服务器是一个坏主意,这更像是一种常见的实践,而不是最佳实践)。

接下来,让我们展示两个数据中心,从代表互联网的神秘云获取流量。

向两个数据中心发送流量的internet图。

互联网,奇怪的约定,始终表示为云。如果有移动设备连接到应用程序,通常你会展示移动设备,与互联网划清界限,然后继续上面的操作(对于网站也是一样)。

数据中心或区域是物理上共享的服务器组,并且通常被描述为围绕许多服务器的一个大框(就像服务器中的进程被描述为服务器中的框一样,一般来说,认为数据中心对于服务器就像服务器对于流程一样是合理的)。

正如在应用程序层的服务器,当它使图表太混乱时,我经常画线。就我个人而言,我认为图表应该更有效而不是准确,如果这两个概念发生冲突。

总结一下:很多盒子,几行,尽可能简单。现在,继续解决问题!

图中,约束,解决,重复

现在,我们开始深入其中。对于每一个分段,我们将显示一个开始图,再加上一笔合同,诊断约束意味着什么,然后为约束创建一个更新的图表求解。有很多,许多可能的限制,所以我们不能涵盖所有这些,但希望我们能看到他们中足够多的人给出一个想法。

Web服务器过载

你在一台服务器上运行你的博客,这是一个运行在MySQL上的简单Python web应用程序。

突然间,你的服务器“超载”,你是做什么的?好吧,首先要弄清楚这是什么意思。以下是一些可能的意思(大概是喜欢的顺序):

  1. 你没有足够的工人来处理并发负载,
  2. 内存不足,无法运行其工作负载,
  3. 没有足够的CPU来快速运行它的工作负载,
  4. 磁盘快用完了IOPs,
  5. 不够文件描述符,
  6. 网络带宽不足。

你应该问面试官是哪一个问题导致了超负荷工作,但是如果他们让你预测发生了什么,可能是上面提到的一种。让我们考虑一下每种方法的垂直和水平缩放策略(垂直缩放可以增加给定硬件集上的吞吐量,也许通过增加更多的内存或更快的cpu,而水平扩展就是添加更多的服务器)。


许多,可能最多,服务器使用线程进行并发。这意味着如果有10个线程,就可以处理10个并发请求。以下如果你的平均请求需要250毫秒,10个线程上的最大吞吐量是每秒40个请求。到目前为止,服务器最常见的第一个伸缩性问题是当前工作负载有太多的传入请求。

最简单的解决方案是添加更多的工作线程,与Serv02比。有更多的线程server01.

限制是每一个额外的线程消耗更多的内存和CPU。在某种程度上,在很大程度上取决于你的具体过程,由于内存压力,您无法添加更多的线程。你的服务器也有可能在线程间共享资源,这样每增加一个线程,速度就会变慢,即使它没有成为内存或cpu约束。

如果在CPU受限之前内存受限,另一个很好的选择是使用非阻塞网络服务器依靠异步IO.非阻塞实现将您的服务器从每个并发请求只有一个线程解耦,这意味着你可以运行很多,单个服务器上的许多并发请求(也许,10000个并发请求!).

一旦您用尽了上述选项来处理给定服务器上的更多请求,接下来的步骤可能会将您的单个服务器拆分为几个专门的服务器(可能是a服务器服务器的角色数据库Db服务器的角色)把网络服务器放在负载均衡器.

负载均衡器将平衡跨web服务器的传入请求,每个线程都有自己的线程来处理并发请求。(负载均衡器依赖于非阻塞IO,并且高度优化,所以它们的并发限制通常不是一个限制因素。)您没有进行设置,所以您可以或多或少地无限期地添加越来越多的内容。服务器节点来增加您的并发性。(通常这时你的数据库会崩溃,(见下文)

通过负载均衡器水平伸缩是所有主机级问题的水平解决方案,如果你在运行a无状态服务.(如果服务的任何实例能够处理任何请求,则服务是无状态的;如果需要同一台服务器继续处理给定页面或用户的所有请求,它不是无状态的)。

如果你记得一件事,它使用一个负载平衡器水平伸缩,并跳转到数据库部分,但是,我们还将深入研究垂直伸缩对于单个服务器的其他常见伸缩挑战。


下一个,最常见的场景是内存耗尽(可能是由于线程太多)。在垂直缩放方面,您可以向服务器添加更多的RAM,或者花一些时间来减少内存使用。

如果您的数据太大,无法装入给定的服务器,并且所有数据都需要同时装入内存,然后你就可以碎片)的数据,使每个服务器都有一个数据子集,更新负载平衡器,将给定碎片的流量引导到正确的服务器。

我们将在下面的数据库一节中进一步讨论这类解决方案,但另一种选择是将更少的数据加载到内存中,而将大部分数据存储在磁盘上。这意味着读取或写入数据将会更慢,但是,您的存储容量将显著增加(1TB SSD很常见,但是web服务器拥有超过128GB的RAM仍然很少见)。

对于读取繁重的工作负载,将所有内容保存在磁盘和内存之间的折衷方法是加载“热集”(经常访问的部分)将数据存储到内存中,并将其他内容保存在磁盘上(报纸可能将今天的文章保存在内存中,但将它们的历史存档保存在磁盘上,以便偶尔对旧新闻感兴趣的读者使用)。


CPU耗尽与RAM耗尽非常相似,有几个有趣的方面。

CPU争用严重的服务器会以降级的方式工作,而内存不足的服务器往往会非常明显地失败(当软件请求更多的内存而得不到时,它会崩溃,而Linux则不完全友好伯父杀手这将自动杀死进程使用太多的内存)。

在很多情况下,你做的合法的工作占用了太多的CPU,您将能够以更具CPU效率的语言(如使用C扩展的python或ruby)依赖库,simplejson这是一个很好的例子,您可能已经在使用)。生产部署将20-40%的CPU时间用于序列化和反序列化并不罕见杰森,简单地切换使用的JSON库就可以带来巨大的提升!

如果您已经在使用性能库,您可以用更高性能的语言(如go)重写部分代码,c++或Java,但是重写软件的决定充满了灾难。


在一个工作负载中,您正在写入一堆数据(甚至只是一个淫秽的日志)或从磁盘读取一堆数据(可能是因为您的内存太多了)。然后你就会经常用光IOPS.IOPS是磁盘每秒可执行的读或写操作数。

您可以通过在内存中缓存或缓冲内存中的写操作,然后定期将它们刷新到磁盘,从而减少对磁盘的读写频率。

或者,您可以购买更多或不同的磁盘。磁盘很有趣,因为您使用的磁盘类型非常重要:旋转磁盘(SATA更大,慢速磁盘SAS速度更快,较小的磁盘)最大不超过200 IOPS,但是低端ssd可以执行5000次IOPS,最好的可以执行超过100,000次IOPS。(甚至还有更高端的设备融合术它们可以以高昂的成本发挥更大的作用。)

很常见的情况是,web服务器运行廉价的SATA驱动器,数据库机器运行更昂贵的ssd。


对于具有高并发性的工作负载,例如,您用于解决的非阻塞服务受到服务器上线程数的限制,你最终会遇到的一个令人兴奋的问题是用光了文件描述符.

几乎每个人都有一个伟大的文件描述符相关的灾难故事,但好消息是,它只是一个值,你需要改变你的操作系统配置,然后你就可以更明智地回到你的一天。(操作系统为文件描述符设置低得令人困惑的默认值,但平均来看,这些天他们设定的违约越来越合理,所以你可能永远不会遇到这种情况。)


最后,如果您的应用程序带宽非常密集—也许您的假设应用程序执行流媒体视频—那么在某个时候,您的带宽将开始耗尽网络接口控制器或网卡。现在大多数服务器都有1GBs nic,但如果您需要,升级到10Gbs网卡是相当划算的,而大多数工作负载都没有。


好了,这就完成了扩展单个web服务器的选项!除了许多垂直扩展服务器的策略外,负载平衡器是目前为止我们最好的工具。

接下来,让我们看看您的服务器根本没有过载的情况,但反应非常缓慢。

应用程序就会慢下来

这一节,假设你在运行一个API,它接受一个URL并返回一个格式良好的,易于阅读的版本的页面(一些东西像这样)。你的初始设置很简单,使用负载平衡器,一些Web服务器和数据库。

突然间,用户开始抱怨应用程序变慢了。人类可以感知到超过100到200毫秒的延迟,所以理想情况下,你希望你的页面加载时间少于200ms,由于某些原因,现在加载应用程序需要1.5秒。

你怎么解决这个问题?

处理每个性能问题的第一步是仿形)。在许多情况下,剖析并不能让你立刻明白你需要修复什么,但它几乎总是会给你一个面包屑。你跟着面包屑,直到你分析出另一种成分,它会给你另一种面包屑,你继续追逐。

在这种情况下,第一个问题很可能是读取数据库的速度变慢了。如果用户经常使用相同的url调用您的API,下一步就是添加一个像这样的缓存复述,Memcached.

现在,对于所有API调用,您将检查:

  1. 要查看数据是否在缓存中,如果存在,则使用缓存中的数据,
  2. 如果数据在数据库中,如果是,你会将数据写入缓存,然后返回给用户,
  3. 否则你会爬上网站然后写进数据库,然后是缓存,然后返回给用户。

只要用户继续爬行几乎相同的url,你的api应该再快一次。


另一个常见的情况是,应用程序变得越来越慢,因为它做的太多了!也许每个传入的请求都从缓存中检索一些数据,但它也在你的数据库中写了一些分析,并向磁盘写入一些日志。您配置您的服务器,然后发现它花费了大部分时间来编写分析数据。

解决这个问题的一个好方法是在不会影响用户的地方运行慢速代码。在某些语言中,这很简单,只需将响应返回给用户,然后进行分析写操作,但许多框架都让这一点变得异常棘手。

在这些情况下,一个消息队列异步工作者是您的朋友。(一些示例消息队列是RabbitMQAmazon简易排队服务

(注意,我已经用代表许多服务器的方框替换了已命名的服务器,很多缓存箱,等等。我这样做是为了降低图表的整体复杂性,尽量保持简单。图表重构通常很有用!一种混合方法是有一个服务器框,然后在这个框中显示多个服务器,但是只从包含框中画线,允许您更明确地指示给定角色中的许多服务器,而不必绘制太多重叠的行。)

当一个请求到达你的服务器时,大部分工作都是同步进行的,但是在消息队列中安排一个任务(通常是,很快,取决于您使用的后端,它会有所不同,但极有可能小于50 ms,这将允许您的工作进程将任务出列并稍后处理,无需用户等待它完成(换句话说,异步)。


最后,有时延迟与应用程序无关,但是,这是因为您的用户远离您的服务器。从美国东海岸向西穿越大约需要70毫秒,从东海岸到欧洲,因此,从西海岸到欧洲旅行很容易超过160毫秒。

通常,解决这个问题最实用的方法是使用aCDN,它就像一个地理分布的缓存,允许普通请求从本地缓存获得服务,这些缓存与用户的距离仅为10或20毫秒,而不是在全球范围内传输。(AWS云面前,急剧,EdgeCastAkamai是一些常见的CDNs例子。)

更大的公司或那些有特殊需求的公司——通常需要高带宽,比如视频流——有时会创建点的存在或者pop,它们的作用类似CDNs,但更容易定制,但随着越来越多的公司在亚马逊开始和保留,这种情况越来越少见,谷歌或微软云。

重复一点,CDNs通常只适用于您的内容是静态的或者可以定期重新生成的情况,这是一个报纸网站为登出用户的情况,如果你的某个内容子集非常受欢迎,以至于很多人都想在一分钟左右的时间内看到相同的内容(承认一分钟是任意长度的时间,您可以缓存内容,无论您想要多长时间)。(这显然忽略了SSL终止的延迟优势,这篇文章很好地涵盖了哪些内容

如果您需要减少对用户的延迟,并且您的工作负载不能使使用cdn有效,然后你必须运行多个数据中心,其中每一个都有您的所有数据,或者为路由到它的用户提供所有必要的数据。

(如果你想知道或者可能被问到哪种机制为你选择了正确的数据中心,一般来说就是选播域名系统,这是非常漂亮的,如果你能在面试中恰当地提到它,肯定会得到一些加分。)

运行多个数据中心往往相当复杂,这取决于您如何做,作为一个主题,超出了本文所涵盖的范围。相对较小比例的公司运行多个数据中心(或在多个地区运行,以实现云计算的同等功能)。几乎所有人都会做一些相当习惯的事情。

也就是说,设计一个支持多个数据中心的系统与扩展数据库非常相似,这恰好是下一部分。

数据库是超载

假设您正在实现一个简单的reddit版本,用户提交和评论。

暂时一切都好,但是如果读取太多,数据库就会受到CPU的限制。如果你使用的是像MySQL或PostgreSQL这样的SQL数据库,最简单的修复方法是添加与主副本具有相同数据但只支持读取的副本(这里的术语略有不同,随着主要和次要或主要和复制变得越来越普遍,较老的文档和系统倾向于将它们称为主文档和从文档,不过,尽管这种用法多年来一直是默认用法,而且在当今也很常见,但它正逐渐失宠。

您的写负载仍然必须跨每个服务器(主服务器或副本)应用,所以副本不会给你任何额外的写带宽,但是每个读取都可以针对任何服务器进行(在复制延迟的约束下,只有当你想在写完数据后马上读取数据时,在这种情况下,你可能不得不强制“写后读”从主数据库读取的操作,但是您仍然可以允许所有其他读操作转到任何复制副本)。所以你可以横向扩展读取很长一段时间(在某个时候,你最终会被限制在可用带宽上添加更多的复制,但许多数据库允许您将复制从一个副本链接到另一个副本,从理论上讲,这将允许你或多或少地无限扩展)。

如果你写得太多,你的解决方案最终会有点不同。而不是复制,相反,你需要依靠分片):分割数据,使每个数据库服务器只包含一个子集,然后有一个机制(通常只是应用程序中的一些代码),可以正确地为给定的操作选择正确的碎片。

因为这允许每个服务器只执行写操作的一个子集,您可以水平扩展以处理或多或少的写负载。实际上,人们不喜欢分片,因为您不能再对所有数据执行操作(例如,计算所有提交的职位),相反,您必须独立地对每个碎片执行操作,并自己找出如何组合结果。

如果您的服务器正在耗尽IOPS或磁盘空间,切分也是最好的解决方案。在某种意义上,分片是有状态服务的负载平衡。

分片操作起来也很复杂,你会花很多时间来维护正确碎片路径的机制,还要花更多的时间来解决如何重新平衡切分,以防止一个切分变得太大,以至于无法处理所有路由到它的写入。

如果你有大量的读和写,然后,绝对可以将复制和分片结合起来,如上所示。


虽然复制和分片是架构面试中最常见的两种扩展解决方案,还有一些值得一提的:

批处理当您的数据库有太多的写操作时很有用,但无论出于什么原因,您都不希望开始分片数据库。特别是像analytics这样的用例,它在一分钟内跟踪给定页面的访问量,批处理可以使您从每秒10,000次写入变为每分钟一次写入(尽管您必须将批处理后的数据存储在某个地方,可能在消息队列中,甚至在应用程序的内存中)。

最后,我在这里要提到的最后一个策略是使用另一种数据库,特别是NoSQL默认情况下,像Cassandra这样的数据库旨在将写和读分散到许多服务器上,而不是必须实现自己的自定义切分工具。NoSQL服务器的典型缺点是,由于每个切分只有一个数据子集,所以它们减少了一组可以有效执行的操作。

如果你想更深入地了解NoSQL,我的建议是阅读那些相当平易近人的书籍发电机的论文这将为您提供概念和词汇表,使您能够深入讨论适合使用NoSQL数据库的场景。

结束的想法

这比预期的要长一些,尤其是当我写这篇文章的时候,我真正想到的是这是一种多么奇怪的采访。从本质上来说,这是一个测试,看看人们是否能给人留下他们以前构建过大型或复杂系统的印象。

奇怪的是,这种面试形式很好地再现了共同设计一个系统或向新同事解释现有系统如何工作的真实体验。只要我们把它用在有合适背景的候选人身上,在一家互联网公司或一家使用与互联网公司相同技术的公司工作多年,我认为这是一个有用的工具。

如果不是这种格式,您如何了解某人的系统设计经验?