10个软件系统设计问题

【译文】原文地址

文章原创自Educative联合创始人Fahim ul Haq。
作为在Microsoft和Facebook工作10多年的高级软件工程师和面试官，作者与很多解决了系统设计问题的候选人共事。开发者常面临系统设计问题的挣扎，因为系统设计通常比较开放，需要一些特别重要的思维而不像代码面试那样。

伴随着系统设计问题的发展，一些系统设计问题在各顶级技术公司面试中还是很流行。今天我们探索10个在面试中最常被问到的系统设计问题。

• 1. 设计一个聊天服务
• 2. 设计一个打车服务
• 3. 设计一个URL简化服务
• 4. 设计一个社交媒体服务
• 5. 设计一个社交留言板服务
• 6. 设计一个文件存储服务
• 7. 设计一个视频流服务
• 8. 设计一个API限流器
• 9. 设计一个就近搜索服务
• 10. 设计一个预输入服务
      任何系统设计问题回答小贴士：

• 开始一个设计问题先表达你所知道的：先列出系统所需的特性，常规碰到的问题以及系统将处理的流量。在列举的过程中，让面试官看到你的规划能力和修正你在设计解决方案时出现的任何误解。

• 描述任何取舍点：每个系统设计的选型时很关键的。在每个决策点上，列出至少一个优点和缺点。

• 与面试官确认细节：大多数系统设计问题都是有意模糊的。让面试官阐明问题，以展示你对系统设计问题的看法和所需掌握的内容。

• 讨论最新的技术：总结每个问题时概述系统设计问题能否使用机器学习来完善。这能说明你不仅仅只准备当前的问题还考虑了将来的解决方案。

  

1. 设计一个全球聊天服务类似Facebook聊天或WhatsApp

对于这个问题，你需要设计一个服务，用户可以通过网络相互聊天。聊天可以一对一的或者是群聊。消息只能在所参与的聊天中可见。

必要特性：

• 消息必须通过互联网发送和接收。
• 服务必须支持一对一聊天和群聊天
• 消息必须存储供后续查看
• 用户可以发送文本，还可以发送图片和视频
• 消息发送过程需加密
• 消息查看必须在尽可能少的延迟范围

常见问题

• 如果网络无法连接将怎么处理？是否需要在网络恢复后再发送？
• 如何加密和解密而不增加延时
• 用户如何接收通知
• 消息是从设备拉去还是推送到服务器上？

可用的工具

• 将数据库分表：user(有用户ID和联系方式)，一个聊天表(有聊天ID和参与者ID列表)和消息表（具有聊天ID的引用）
• 使用websocket全双工连接设备和服务器

• 使用推送来通知用户即使掉线

  

2. 设计一个打车服务类似Uber或者Lyft

这个问题要求你创建一个共享打车服务，将打车用户匹配到附近的司机。用户可以输入目的地和发送当前位置，并且司机能够在几秒内接到打车通知。App然后跟踪司机和用户当前位置之间的一条路径。

必要特性

• 系统必须跟踪用户和司机的当前位置
• 行驶过程中司机和用户都必须能接收路途更新
• 必须支持多数用户在不同地点打车并且可扩展
• 司机和用户必须能和服务端保持连接

常见问题

• 在高峰期如何保持低延时？
• 司机和用户怎么匹配？计算每个司机欧几里得距离是低效的。
• 司机和用户断连怎么处理？
• 如何存储缓存定位数据？

可用工具

• 使用S2Geometry库进行定位分割成单元计量。在同一个定位单元里只计算司机和用户的距离。
• 使用分布式存储来存放所有用户的定位，每个用户的定位数据控制在1KB。
• 如果定位停止，设备将继续显示原先地位直到重连成功。

• 推送匹配给司机允许一段缓冲时间。如果司机拒绝，再推送给另一个司机。

  

3. 设计一个URL简化服务类似TinyURL或bit.ly

这个问题要求你创建一个程序缩减长URL类似TinyURL或bit.ly。这些程序以长URL为输入生成唯一简短的URL。也可以反过来，传入简短URL返回源长URL。

必要特性

• 返回一个简短URL
• 必须保存源长URL
• 生成的短URL必须能链接到源长URL
• 简短URL可重定向
• 必须支持自定义间短URLs
• 同时支持多个请求

常规问题

• 如果两个用户输入相同的自定义URL，怎么处理？
• 用户超出预期数量怎么处理？
• 数据库如何管理存储空间？

可用工具

• 使用哈希来关联源URL和新生产URLs
• 使用REST API来负载均衡大流量以及处理前后端通信
• 使用多线程来处理并发请求
• 使用NoSQL数据库来存储源URL（存储的URL之间没有关联）

4. 设计一个大型社交媒体服务类似Facebook、Twitter或者Instagram

对于这个问题，你需要设计一个社交软件可供大量用户使用类似Instagram。用户可以查看新闻推送以及关注的帖子，可以推荐用户喜欢的内容。

必要特性

• 健壮的新闻推送和推荐系统
• 用户可以发布公开帖子
• 其他用户可以评论以及订阅帖子
• 必须能很好的适应大客户流量并发
• 系统必须高可用

常规问题

• 大V用户和普通用户怎么处理？
• 系统如何根据年龄来权重帖子？和新的帖子比，老帖子看的人更少。
• 节点读写比例是多少？存在读请求比较多或写请求比较多的情况么？
• 如何增加可靠性？系统如何更新？如果节点失败怎么处理？
• 如何高效地存储帖子和图片？

有待考虑的工具

• 使用滚动更新和冗余节点来增加可用性
• 使用训练的机器学习算法来推荐帖子
• 建数据库schema将名人和普通用户分开存储

• 使用社交图来深度跟踪用户习惯

  

5. 设计一个社交网络和留言板类似Quora、Reddit或HackerNews

对于这个问题，需要设计一个类似论坛系统，用户可以提问题和发链接。其他用户可以查阅和对问题进行评论。问题有标签代表主题，用户可以选择标签来看对应主题的问题。根据用户关注的主题或关联主题对非常流行的问题提供动态推送。

必要特性

• 用户必须能创建公开帖子和打标签
• 帖子能够根据标签来排序
• 其他用户可以实时发表评论
• 数据库必须存储每个贴（观看、点赞统计等）
• 必须支持大流量查看和创建新贴

常规问题

• 该应用仅支持web吗？
• 用户上传的图片/链接存储在哪？
• 系统如何关联标签？多少未关注标签需要显示？
• 帖子如何在服务器上分布存储？

有待考虑工具

• 使用SQL数据库映射关系型数据（用户有帖子，帖子有评论/链接，各类有关联的帖子等）
• 使用多线程和负载均衡来支持大流量
• 使用分片来切分系统。将共同的标签或同类的帖子存放在同一服务器中。

• 使用机器学习和自然语言处理来找到标签的关联性。

  

6. 设计一个全球文件存储&共享服务，类似Dropbox、Google Drive或Google Photos

针对这个问题，你需要创建同步、跨平台存储系统类似Dropbox。用户可以存储文件和图片以及通过其他设备来访问这些文件和图片。

必要特性

• 用户能通过web对文件进行增删改查
• 老版本文件支持回退
• 文件更新需要在多个设备同步

常规问题

• 文件存储在哪里？
• 更新如何处理？需要重新上传整个文件么？
• 小更新需要整个文件更新吗？
• 两个用户处理同一个文件更新怎么处理？

有待考虑的工具

• 将文件分割成多个组块。只更新变更的组块而不是整个文件。
• 使用亚马逊S3云储存来处理内部数据库

• 客户端与服务端保持长连接来检查是否有同步更新

  

7. 设计一个全球视频流服务类似YouTube或Netflix

关于这个问题要求你创建一个在线视频流服务类似Youtube。该服务能够保存和传输大量的视频数据。还能够存储统计信息（观看数，喜欢和查看数等）以及用户提交的评论。您的解决方案必须支持高并发可扩展。

必要特性

• 可通过web上传视频
• 用户可以通过互联网顺畅接收视频流
• 视频统计数据需存储和被访问
• 评论需要存储并和视频一起显示
• 支持多用户大流量

常规问题

• 在不同的网络环境下视频流如何确保顺畅？
• 网路断连的话服务怎么应对（缓存、降低质量等）？
• 视频如何存储？

值得考虑的工具

• 使用云技术来存储和传输视频数据
• 使用机器学习来推荐新视频内容

• 防止连接延迟导致的停顿。用户先看前面一点的内容而不是实时的。

  

8. 设计一个API限流器类似Firebase或Github

关于这个问题，你将创建一个API限流器来限制一段时间内一个API服务调用的数量防止过载。面试官可以对这个问题的要求不同，从单机到整个分布式网络。

必要特性

• 设备在一个小时内限制10个请求
• 限流器必须通知用户请求被限制
• 根据规模来合理限制

常规问题

• 系统如何衡量每个小时到请求量？如果一个用户在1:20发起10个请求在2:10又发起10个请求，尽管时间变动但在一个时间窗口发送了20个请求。
• 如何设计从单机到分布式系统？

有待考虑到工具

• 使用时间滑动窗口避免每小时到重制

• 保存计数器整数而不是请求本身来节省空间

  

9. 设计一个就近服务搜索服务类似Yelp或就近位置/朋友

这个问题，你将设计一个就近服务器存储和发布位置距离比如饭馆。用户可以根据距离或名气搜索就近场所。数据库必须存储全球500万个位置数据具有低延时功能。

必要特性

• 保存500万条定位数据
• 定位必须唯一可以区分并且有对应数据比如服务质量和时间
• 查询结果必须最低延迟
• 用户必须能通过距离和质量来搜索

常规问题

• 这么多的位置信息怎么存储？
• 如何实现快速查询？
• 系统如何处理不同的流行密度？严格的经纬度可能会造成不同的响应
• 如何优化经常的搜索位置

有待考虑的工具

• 使用关系型数据库来存储定位列表和相关数据
• 使用缓存来存储常被访问的有名位置
• 使用分片来对区域进行切分

• 根据动态网格搜索位置。如果一个单元内有500个位置，就将这个网格分成4个单元。重复分割直到只需要搜索少于500个位置。

  

10. 设计一个搜索引擎输入提示服务类似Type-Ahead

这个服务将完成部分查询并显示5个推荐来完成完整查询。具有实时的适应高查询内容并将推荐给其他用户。比如，“SeaHawks赢了Super Bowl队“这个事件发送了就会被及时推荐。

必要特性

• 服务能够根据常见查询来匹配部分查询
• 小的拼写错误能够被修正例如“dgo->dog"
• 根据查询推荐5个最有可能匹配的
• 根据输入的变化更新查询

常规问题

• 错误拼写的修正准确率怎么保证
• 在不造成延时的情况下如何更新选择？
• 如何决策最有可能的完整查询？是否适应用户的搜索？
• 如何用户输入太快怎么处理？在用户输入完才显示推荐么？

有待考虑的工具

• 使用自然语言处理机器学习算法来预测接下来的特征。
• 使用Markov Chains来排序最有可能的查询
• 每小时/每天更新机器学习算法，而不是实时更新来减少负担。