技术面试的系统设计题（一）

本文为课程翻译和学习笔记，课程地址System Design for Tech Interviews。
关于课后题，这儿就不公布答案了。应该还是比较简单的。

什么是系统设计题

在面试的时候，面试官经常会让我们设计一些系统，比如：

• 设计一个像bit.ly一样的URL缩短服务。
• 你将如何实现谷歌搜索？
• 设计一个C/S应用程序，允许人们互相下棋。
• 如何将关系存储在Facebook这样的社交网络中呢？并实现一个当用户的朋友喜欢与他们一样的东西时，用户会收到通知的功能。

这些问题起初似乎很吓人。毕竟，我们怎么可能在20-30分钟内设计出Google搜索。

这些问题的关键点是讨论解题的过程。对面试官来说重要的是你解决问题的过程。这种讨论的典型结果是一个高层次的架构，从而在有限制的情况下解决这个问题。也许面试官会选择一个或多个他们想讨论的系统瓶颈和其他常见问题来更加具体地询问你。

请记住，没有一个标准的正确的答案。系统可以用不同的方式建立。重要的是能够证明你的想法。

最后，请记住，根据面试官的目标，关于同一个系统设计问题的讨论可能会有不同的方向。他们可能愿意看到你如何创建一个涵盖系统各个方面的高层架构。也可能，他们会更关注一些特定的领域并深入研究。无论如何，你应该有一个如何处理不同情况的策略。

第一步：限制与用例

就像算法设计一样，系统设计问题的细节也很可能会被弱化。考虑关于URL缩短服务的问题（“设计一个像bit.ly的URL缩短服务”）。题目的信息非常少，如果不知道更多限制和要求，是不可能设计一个合适的解决方案。事实上，面试官并不会一开始就告诉你所有的信息，很多人都忘记了这一点，并立即开始设计解决方案。

对任何系统设计问题你应该做的第一件事是明确系统的限制，并确定系统需要满足哪些用例。花几分钟询问你的面试官，并统一系统的规模。我们在讨论算法设计时所讨论的许多相同的规则也适用于此处。

通常情况下，面试者希望看到的是你能收集到关于问题的要求，并设计一个能很好地覆盖这些要求的解决方案。永远不要假设面试官没有明确说明的事情。

例如，缩短网址的服务可能只能为几千个用户提供服务，但每个用户都可以共享数百万个网址。这可能意味着要处理数百万次缩短网址。该服务可能需要提供有关每个缩短的URL的统计信息（这会增加需要处理的数据大小），或者根本不需要统计信息。

您还需要考虑预期会发生的用例，您的系统将根据预期的目标进行设计。

用例

1. 缩短：将一个url转化为缩短的url
2. 重定向：得到一个缩短的url，跳转到原url
3. 用户自己设计一个缩短的url
4. CAP中，取高可用性

限制

一般来说，大部分限制是来自于数据规模的限制。比如每分钟的数据量，访问人数等等。
如果你去问面试官，他可能直接给你数据，比如，我们每秒要处理400个请求；或者，他会说一些更笼统的信息让你去估计，比如，这个网站不是top 3但是却是top 10的。

在估算的时候，一定要注意合理。通常而言，用二八定律是一个非常重要的准则。

• 系统每个月需要处理的数据是$100\times 10^6$
  
  • 推特一个月产生$15\times 10^9$的推文
  • 每个月需要进行缩短的新URL只占了10%，总计$1.5\times 10^9$
  • TOP3以下的缩短URL网站只处理了20%的数据，也就是$300\times 10^6$的数据
  • 我们的系统，需要处理$100\times 10^6$的数据
  • 5年之内会产生$6\times 10^9$条URL，占用空间3TB；hash表占用空间36GB
    
    • 每个缩短的URL占用500 bytes和6 bytes的hash

• 系统需要处理的请求是每个月$1\times 10^9$

  • 考虑URL的寿命，平均为1~2周，这儿可以假设10天
  • 每天有一个请求
  • $100\ mln \times 10\ days \times 1\ click/day = 1\ bln$
  • 请求的分类：10%是进行缩短，90%是进行重定向
    
    • 每秒有400+的请求，40是进行缩短，360是进行重定向

• 每秒需要写入的新数据：$40\times (500 + 6) = 20\ K$

• 每秒需要读取的数据：$360\times 506=180\ K$

关于这些限制的估计，人为主观因素有较大影响，不过在面试的时候除非估计得特别离谱，面试官一般不太会纠结于这方面，基本按照二八原则来估计就行了。

具体的估算过程见下图。

第二步：抽象设计

一旦你确定了你要设计的系统，你应该描述一个高层次的抽象设计。这步的目标是概述您的架构将需要的所有重要组件，而不是深入到抽象设计的某个方面，或者，直接一部分一部分来设计。

你可以告诉面试官，你想这样做，并画出你的想法的简单图表。勾画您的主要组件和它们之间的连接，在面试官面前证明你的想法，并试图解决每一个约束和用例。

如果你这样做，面试官会很快也很轻易地给你反馈。

通常，这种高级设计是人们已经开发的众所周知的技术的组合，比如，缓存，数据库读写分离等等。你必须确保你熟悉那里的东西，并且能够流畅地使用这些知识。这个地方就需要大家去多看书或者技术博客了。

值得注意的是，如果您的设计不能改满足面试官的要求，如，面试官要求高度的一致性约束，而您只能做到基本一致性，这是绝对不允许的。

1. 应用服务层
   
   • shortening server
     
     • 可以简单地解释一下是如何实现的：使用hash，查看URL是否已经存在于存储中，若是没有，则进行hash和存储
   • redirection server
2. 数据存储层
   
   • 用于存储hash$\rightarrow$url的映射关系
   • 不必提到具体的数据库或者其他的细节，可以大致说明，它的运行方式像一个非常大的缓存系统：存储新的映射关系，通过key得到value。
3. 设计hash方式
   
   • 结合一些著名的hash算法，如，md5
   • 结合随机数，并将结果转化为base62编码，base62编码非常适用于tiny URL
   • 取前6 bytes
   • hashed_ulr = convert_to_base62(md5(origin_value+random_salt))[:6]

第三部：理解瓶颈所在

考虑到问题的限制，您的高层设计有可能会有一个或多个瓶颈。这其实非常好。没有人能够一步到位地设计一个能够直接处理世界上所有负载的系统。我们希望的是这个系统具有可扩展性，以便您能够使用一些标准的工具和技术来改进它。

现在你有了高层次的设计，开始思考它有什么瓶颈。也许你的系统需要一个负载平衡器和许多机器来处理用户请求。也许需要存储的数据量太大了，系统应该使用分布式的数据库。这样做有什么缺点？分布式数据库是否太慢，是否需要一些内存中的缓存？

这些只是为了使您的解决方案完整而必须回答的问题的示例。面试官可能会希望在一个特定的方向上进行讨论。那么，也许你不需要解决所有的瓶颈问题，而是更深入地讨论一个特定的领域。无论如何，您需要能够之处系统的弱点，并能够解决这些问题。

请记住，通常每个解决方案都是某种权衡：改善一些方面会导致其他方面的恶化。然而，重要的是要能够谈论这些权衡，并根据所定义的约束和用例来衡量它们对系统的影响。

1. 应用服务层
   
   • 缩短操作，每秒处理20k的数据，包输入输出和一个简单的hash操作。这明显不是瓶颈所在。
   • 重定向操作，每秒处理180k的数据，包括输入输出。这明显不是瓶颈所在。
2. 数据存储层
   
   • 如何准确地得到key的value，我们的数据有5TB，所以系统不可能线性扫描整个数据集。

总结

当你和面试官就上面的问题达成一致，你可以深入到某些方面的细节。