在Microsoft和Facebook担任高级软件工程师和面试官的10年中，我与数百名申请人一起工作，因为他们解决了不同的系统设计问题。
开发人员倾向于解决SDI问题，因为它们是如此开放，并且通常需要一种在其他编码面试挑战中没有实践的批判性思维。
尽管SDI问题随着时间而变化，但其中一些问题在各种顶级公司的访谈中仍然很受欢迎。
今天，我们将探讨最常见的10个系统设计面试问题，每个问题中必须解决的常见问题以及一些可以帮助您完成此任务的工具。
有关任何SDI问题的提示
通过陈述您所知道的问题来开始每个问题：列出系统的所有必需功能，此类系统可能遇到的常见问题以及系统希望处理的流量。列出过程使面试官可以在开始解决方案之前查看您的计划技能并纠正任何可能的误解。
叙述任何权衡：每个系统设计选择都很重要。在每个决策点，至少列出该选择的正面和负面影响。
请您的面试官澄清：大多数系统设计问题是故意含糊的。提出澄清问题，向面试官展示您如何看待问题以及对系统需求的了解。
讨论新兴技术：在每个问题的结尾都概述了系统如何以及在何处可以从机器学习中受益。这将表明您不仅为当前的解决方案做好了准备，而且还为将来的解决方案做好了准备。
1.设计一个全球聊天服务，例如Facebook Messenger或WhatsApp
对于这个问题，您将设计一种服务，允许用户通过Internet彼此聊天。对话可以是一对一的对话，也可以是与许多成员进行的群聊。对话中包含的消息只能访问这些消息。
必备功能：
- 消息必须通过互联网发送和接收。
- 服务必须支持一对一和群聊。
- 消息应存储以供以后查看。
- 用户应该能够发送图片和视频以及短信。
- 邮件在传输过程中应被加密。
- 消息应该以最小的延迟可见。
常见问题：
- 如果在没有互联网连接的情况下发送邮件会怎样?恢复连接后是否发送?
- 如何在不增加延迟的情况下加密和解密消息?
- 用户如何接收通知?
- 是将消息从设备中拉出(如果服务器正在等待发送消息，服务器会定期提示设备)还是将消息推送到服务器(设备会提示服务器有消息要发送)?
需要考虑的工具：
- 将数据库模式分为多个表：用户表(具有用户ID和联系人)，聊天表(具有聊天ID和参与的用户ID列表)和消息表(过去的消息带有对聊天ID的引用)。
- 使用WebSocket在设备和服务器之间进行双向连接。
- 使用推式通知来通知成员，即使他们处于脱机状态。
2. 设计类似Uber或Lyft的拼车服务
该问题要求您创建一种将用户与附近驾驶员匹配的乘车共享服务。用户可以输入目的地并发送其当前位置，并在几秒钟内通知附近的驾驶员。
然后，该应用程序会跟踪驾驶员和用户当前位置之间的路线，然后再跟踪从用户位置到目的地的路线。
必备功能：
- 系统必须跟踪所有用户和驱动程序的当前位置。
- 在运输过程中，用户和驾驶员必须接收更新的旅行信息。
- 必须在此过程中的各个阶段支持成千上万的用户，并相应地扩展规模。
- 驱动程序和用户必须始终连接到服务器。
常见问题：
- 您如何在繁忙时段保持较低的延迟?
- 驱动程序如何与用户配对?迭代所有驾驶员以找到欧几里得距离将是低效的。
- 如果驱动程序或用户失去连接会怎样?
- 您如何存储所有缓存的位置数据?
需要考虑的工具：
- 使用S2Geometry库将位置拆分为单元格。仅使用与用户位于同一单元格中的驾驶员来计算驾驶员距离。
- 使用分布式存储来存储所有用户的位置，每个用户的位置数据大约只有1Kb。
- 如果位置数据暂停，则设备在等待重新连接时会继续报告其先前的位置。
- 提示最近的驾驶员出行后，请留一个缓冲区。如果他们拒绝，请转到下一个驱动程序。
3. 设计URL短服务，例如TinyURL或 bit.ly
这个问题要求您创建一个程序来缩短长网址，例如TinyURL或bit.ly。这些程序采用一个长URL并生成一个新的唯一的短URL。他们还可以输入缩短的URL并返回原始的完整URL。
必备功能：
- 返回比原始网址短的网址
- 必须存储原始URL
- 新生成的URL必须能够链接到存储的原始URL
- 缩短的网址应允许重定向
- 必须支持自定义短网址
- 必须一次支持许多请求
常见问题：
- 如果两个用户输入相同的自定义URL，该怎么办?
- 如果用户数量超出预期怎么办?
- 数据库如何调节存储空间?
需要考虑的工具：
- 使用哈希链接原始和新URL
- 使用REST API负载均衡高流量并处理前端客户端通信
- 使用多线程一次处理多个请求
- 使用NoSQL数据库存储原始URL(存储的URL之间没有关系)
4. 设计一个大众社交媒体服务，例如Facebook，Twitter或Instagram
对于这个问题，您将设计一个供Instagram之类的十万用户使用的社交媒体服务。用户应该能够查看带有跟随者帖子的新闻提要，并建议用户喜欢的新内容。
采访者通常希望听到您深入讨论新闻源。
必备功能：
- 强大的新闻源和推荐系统
- 用户可以发表公开帖子
- 其他用户可以评论或顶帖子
- 必须一次舒适地容纳许多用户
- 系统必须高度可用
常见问题：
- 知名用户将拥有数百万个关注者，与普通用户相比，他们将如何处理?
- 系统如何按年龄分配体重?与新帖子相比，旧帖子的浏览可能性较小。
- 节点read与write集中节点的比率是多少?是否可能会有更多的读取请求(用户正在查看帖子)或写入请求(用户正在创建帖子)?
- 您如何增加可用性?系统如何更新?如果节点发生故障会怎样?
- 您如何有效地存储帖子和图像?
需要考虑的工具：
- 使用滚动更新和副本节点来最大化可用性。
- 使用训练有素的机器学习算法来推荐帖子。
- 创建一个数据库架构，分别存储名人和用户。
- 使用社交图谱进一步追踪以下习惯
5. 设计一个社交网络和留言板服务，例如Quora，Reddit或HackerNews
对于这个问题，您将设计一个类似于论坛的系统，用户可以在其中发布问题和链接。
其他用户可以查看和评论问题。问题具有代表其主题的标签，用户可以跟随标签查看有关特定主题的问题。用户有一个新闻源，该新闻源从其关注的标签和相关主题中突出显示了常见问题。
必备功能：
- 用户必须能够创建公共帖子并应用标签
- 帖子必须按标签排序
- 其他用户必须能够实时发布评论。
- 数据库必须在每个帖子上存储数据(观看次数，赞等)
- 新闻源必须显示来自跟随标签的帖子以及用户希望的其他标签的帖子。
- 必须支持高流量的观众和新帖子。
常见问题：
- 我们的产品仅需要在网络上运行吗?
- 用户上传的图像/链接存储在哪里?
- 系统将如何确定相关标签?供稿中显示多少个来自未关注标签的帖子?
- 如何在服务器网络上分配帖子?
需要考虑的工具：
- 使用SQL数据库映射关系数据(用户有帖子，帖子有评论/喜欢，类别有相关的帖子，等等)
- 使用多线程和负载平衡器层可帮助支持更高的流量。
- 使用分片来破坏系统。考虑按类别分片以将相同标签的帖子存储在一台计算机中。
- 使用机器学习和自然语言处理来查找标签之间的关系之间的相关性
6. 设计全局文件存储和共享服务，例如Dropbox，Google云端硬盘或Google相册
对于这个问题，您将创建一个同步的跨平台存储系统，例如Dropbox。用户可以存储文件和照片并从其他设备访问它们。
必备功能：
- 用户应该能够通过网络保存/删除/更新/共享文件
- 旧版本的文档应保存以进行回滚
- 文件更新应在多个设备上同步
常见问题：
- 文件存储在哪里?
- 您如何处理更新?您是否再次重新上传整个文件?
- 小更新需要完整的文件更新吗?
- 系统如何处理两个用户同时更新文档?
需要考虑的工具：
- 使用分块将文件分成多个部分。更新仅重新上传该部分，而不是整个文件。
- 使用像Amazon S3这样的云存储来处理内部数据库。
- 使客户端不断与服务器核对以确保应用并发更新。
7. 设计全球视频流服务，例如YouTube或Netflix
这个问题要求您创建在线视频流服务，例如YouTube。该服务将存储和传输数百PB的视频数据。它还必须存储统计信息(观看次数，喜欢次数，观看次数等)，并允许用户发表评论。
您的解决方案必须具有可扩展性，以支持成千上万的并发用户。
必备功能：
- 视频应该可以通过网络上传
- 用户应通过互联网收到不间断的流
- 视频统计信息应该存储并可以访问每个视频。
- 评论必须保存并与视频一起显示给其他网友评论
- 应该支持几千个用户的高流量
常见问题：
- 您的服务将如何确保各种互联网质量上的流畅视频流?
- 您的服务如何应对流速度的突然下降(缓冲，质量下降等)?
- 视频如何存储?
需要考虑的工具：
- 使用云技术来存储和传输视频数据。
- 使用机器学习来建议新的视频内容。
- 防止因连接不一致而造成的卡顿现象。用户查看了片刻之前的数据，而不是输入数据。
8. 为Firebase或Github等网站设计API速率限制器
对于这个问题，您将创建一个API速率限制器，以限制服务在给定时间段内可以接收的API调用次数，以避免过载。
采访者可以从一台机器到整个分布式网络，以各种规模提出要求。
必备功能：
- 设备每小时限制为10个请求
- 如果他们的请求被阻止，则限制器必须通知用户。
- 必须处理适合其规模的流量。
常见问题：
- 您的系统如何衡量每小时的请求?如果用户在1:20发出10个请求，然后在2:10发出另外10个请求，那么尽管小时数有所变化，他们还是在同一1小时窗口中发出了20个请求。
- 分布式系统的设计与本地系统有何不同?
需要考虑的工具：
- 使用滑动时间窗口以避免每小时重置一次。
- 保存一个计数器整数而不是请求本身以节省空间。
9. 设计一个类似Yelp或附近的地方/朋友的接近服务器
对于最后一个问题，您将设计一个邻近服务器，用于存储并报告到餐厅等地方的距离。用户可以按距离或受欢迎程度搜索附近的地点。该数据库必须存储全球5亿个位置的数据，但延迟低。
必备功能：
- 存储多达5亿个位置。
- 位置必须唯一标识，并具有相应的数据，例如质量检查和服务时间。
- 搜索必须以最小的延迟返回结果。
- 用户必须能够按距离或质量搜索结果。
常见问题：
- 您如何存储这么多的位置数据?
- 您如何获得快速搜索结果?
- 您的系统如何处理不同的人口密度?刚性的纬度/经度网格将导致基于密度的变化响应。
- 我们如何优化常用搜索位置?
需要考虑的工具：
- 使用关系数据库存储位置列表和相关数据。
- 使用缓存存储最受欢迎位置的数据。
- 使用分片可按区域拆分数据。
- 在某个动态网格内搜索位置。如果单个单元格中有500个以上的位置，请将网格划分为4个较小的单元格。重复直到您只需要搜索少于500个位置。
10. 设计与搜索引擎相关的服务，例如Type-Ahead
该服务将部分完成搜索查询，并显示5条建议以完成查询。它应该实时适应高度搜索的内容，并向其他用户建议。
例如，将在事件发生后的几分钟内建议“海鹰队赢得超级碗”。
必备功能：
- 该服务应将部分查询与流行查询匹配。
- 较小的拼写错误应予以纠正，例如“ dgo→dog”
- 应该根据查询猜出5个最可能的选项
- 结果应在编写查询时更新
常见问题：
- 您对拼写错误的纠正能力有多强?
- 如何更新选择而不引起延迟?
- 您如何确定最可能完成的查询?它适应用户的搜索吗?
- 如果用户快速键入该怎么办?建议是否仅在完成后才会显示?
需要考虑的工具：
- 使用自然语言处理机器学习算法来预测下一个字符。
- 使用马尔可夫链对排名最高的查询概率进行排名。
- 每小时或每天(而不是实时)更新ML算法，以减轻负担。
接下来要学什么
这些问题应有助于您理解在系统设计面试中将要解决的问题类型。练习解决和解释此类问题是准备下一次面试的最有效方法。
本文翻译自The Educative Team的文章《Top 10 System Design Interview Questions》。
