【长文干货】8大步骤详解设计Instagram

这篇文章延续我上一篇地里的文章 资深面试官眼里的系统设计面试 中提到的系统设计的八个步骤，用设计instagram为例进一步详解了八大步骤的打开方式。

这是一道老题了，也是一道高频题。同学们不要死记硬背答案，而是体会一下一步步破题的过程。因为面试流程不唯一，真正碰到这道题的时候面试官的follow-up会不一样，大家还是要注重积累，本文也无法面面俱到。

先扩展一下这道题，这是道New Feed题，Design Facebook, Design Instagram, Design Twitter都是一回事，不要被马甲迷惑。
想要直接看答案总结的可以跳到文章最后，有完整的系统设计图。废话说完，我们这就来按照前一篇文章的步骤来答题。

理解需求


下面是一段虚拟的对话。

Interviewer: Today we are going to have a system design interview. Our goal is to design Instagram. You don't have to cover everything. We can drill into specific topic when we get there. Are you familiar with Instagram?

Interviewee: Ya, I use it all the time. It's photo sharing app. Before we start, can we take a step back? What's the purpose of this “Instagram” we are building? Are we trying to compete with the real thing?

Interviewer: Let's imagine that Instagram doesn't exist yet and people don't have a good app to share photos broadly.

Interviewee: Good to know. What features do we want to cover? I think we have two basic features - upload a photo, get a feed from followers and follow/unfollow . Sounds good?

Interviewer: Cool, that's a good list. Let's focus on the first two for the sake of time.

Interviewee: How about latency? I think this would be an important requirement too. I assume we want to have minimal latency - probably less than 0.5 second for loading feed.

Interviewer: That's a good callout.

Interviewee: OK. (write on whiteboard). So functional requirement is to support 1) uploading photo and 2) retrieve feed from followers. Non-functional requirement is 1) Feed retrieve latency of less than half a second, 2) highly available. 3) highly reliable (data never lost). Non-requirement is follow & unfollow.

Interviewer: Makes sense.

Interviewee: Do we need to consider feed ranking?

Interviewer: Let's skip that for simplicity sake. Let's assume feed is ranked in reverse chronological order. Basically latest photo on top.

Interviewee: Sounds good.

从这段对话里受试者进行了以下三步。

• 询问系统的商业目的 - 在没有Instagram的世界里重新造一个，让大家可以分享照片。
• 询问功能性需求 - 能上传能看News feed, 新照片排前面，用户体验要流畅。
• 询问非功能性需求 - Feed Latency <0.5s, Highly available, Highly reliable
  

资源估算
说到这里，我们粗浅地了解了一下需求，还没有对non-functional requirement进行量化和细化，这就需要我们进一步做资源估算。
继续我们虚拟的对话。

Interviewee: I assume there are a lot of people want to use this service. Shall we assume the scale of the service is similar to the real one?


Interviewer: Yes. Let's assume daily active user is 800M.

Interviewee: How often do people upload?

Interviewer: Let's assume people post every 10 days.

Interviewee: Assuming daily active user makes 10 requests a day and post every 10 days. I think we can calculate the read/write QPS. (Write on whiteboard) I think read QPS is 800 * 1000 * 1000 * 10 / (3600 * 24), roughly 90k QPS and write QPS is 1/100th of that which is 900 QPS. Don’t think this will fit on one machine. (Laugh)

Interviewer: No, it won't.

Interviewee: We will need a lot of storage here. Majority would be to store photos. Assuming we store all photos for 5 years and a photo is 1M, we will need 800 * 1000 * 1000 * 365 * 5 * 1M / 10 = 146000 TB = 146 PB. It will take one or multiple data centers to hold.

Interviewer: Sounds good. Let's proceed with a high level design.

我们进一步地对非功能性需求进行量化和细化。

• Feed Latency <0.5s
• Support 800M DAU
• Highly available (while supporting read 90k QPS, write 900 QPS)
• Highly reliable (while storing ~146PB data)
  

提示两点。

• 注意整个过程中Interviewee在主导这个需求探索的过程，interviewer对interviewee给出的需求和数字做确认并少量给出受试者不知道的关键信息（比如DAU 800M)。不要让面试官做过多的单方面灌输信息。
• 关于数字的计算少数情况下因为时间关系，面试官会让你跳过。如果算得不利索的话，建议跟面试官确认一下。相信这个小学数学对大家都不难，我的小技巧是365*24就算作10000就好，数量级对就行。
  

High-level Diagram
了解需求之后，我们可以开始画一个简单的图来说明我们的核心服务是如何构建的。

在上图中，我们并没有过多考虑Scalability，而是提出一个小流量下可行的方案。在画图过程中，我们需要考虑的核心问题是Push vs Pull. 上图中提出的是Push的方案。我们一边画图，一边就可以跟面试官提出这个Trade-off. 我们提出我们意识到这是一个Read-heavy application.

• Push好处是Latency低，符合之前定义的Latency < 0.5s的要求。
• Push坏处是Fanout过程中耗时更长（因为一个人可以被很多人follow，比如celebrity)，能保证数据的eventual consistency，但不能保证最新照片及时进Feed. 当然这里可以提专门为celebrity的优化， 后面核心子服务会提到。
  

可以跟面试官确认Push的坏处是不是可以接受。

数据结构与存储
数据库的设计
以下设计偏向于非纯key-value store的存储方案。如果想选用key-value store，如redis, 以下表的设计可以酌情做一些调整。

• Post Table (post id as primary key）- post id，user id，image url，create time
• User Table (user id as primary key) - user id, user name, profile photo url, join time
• Feed Table (user id as primary key) - user id, post id, create time; 提两点，1） 这里create time是必须的，在返回Feed过程中我们需要按照这个排序。因为我们用了async worker来写feed table, 我们无法保证先写进来的一定就是create time更早的照片。2） 选用user id做primary key优于post id，也可以考虑用 user id 加上create time 来做 composite key.
• Follow Table - user id, follower id 或 user id, following id; 这边要说明Trade off - Push方案里我们总是拿user id去找他被谁follow了，而pull方案里我们总是拿user id去找他follow了谁。当然我们也可以两种都存来做一个hybrid approach，下面会提到。
  

存储系统
缓存, 数据库和文件系统分别用什么？
缓存 (Cache)

• 数据库的缓存 - Redis, MemCached
• 文件系统的缓存 - CDN. 想象一个有很多粉丝的明星发的照片会被很多人看到，我们是不是需要每一次都从文件系统里拿呢？显然不行。对于大文件的缓存我们需要把文件提前部署到世界各地的CDN上，这样需要访问时就能第一时间从最近的CDN拿到数据。
  

数据库 (Database)

• Cassandra, MySQL ... SQL vs NoSQL? 这是个仁者见仁，智者见智的问题。我们至少要意识到这是read-heavy application。SQL这边有MySQL，做key-value store性能很好，noSQL有Cassandra, read-heavy, write heavy都可以，保证eventual consistency.
  

文件系统 (File Storage)

• HDFS or Amazon S3是可以考虑的分布式的数据系统。
  

核心子服务设计
我们来细化Feed Service的架构。
前面我们发现了Push带来的Celebrity Fanout的问题。我们就在这个阶段提出Hybrid approach. 简单来说，我们用一张新的post table去专门存超过一定Follower数量的celebrity的post，然后每次取Feed就直接从这张比较小的表里去找celebrity的post，然后与Feed table合并排序。注意这边celebrity的post我们就不写到Feed table里了，顺便解决了每次celebrity post，async worker的load大大增加的问题，使其更稳定。

这里值得讨论一个细节，我们能不能定一个Follower数量的限制，这样是不是就不用专门用一张新的post table去存了呢？其实不然，因为用户的Follower数量是会波动的，如果用户正好在那条线上，会造成fanout时有时无的情况。当然，我们建了新的celebrity post table也会带来问题，就是如果有了新人一下子变很火，我们怎么把他们加入这个我们认定的celebrity的行列。方法很简单，其中一种是从普通的post table去backfill celebrity post table，另一边从Feed table里去除他们的post.


接口设计
我们来写Read和Write两个API。

• Read - getFeed(user_id, page_count, last_timestamp)
• write - uploadPost(user_id, photo, description...)
  

uploadPost相对直接，getFeed却有很多讲究。现在我们思考一下这边写的page count和last timestamp是什么用意呢？
答案是分页(Pagination)。每一次getFeed，我们不可能把所有的该用户的Feed一股脑的发回去，我们必须分成一段一段地发。那么问题来了，怎么才能取回第二页呢？
最直接的想法是在getFeed中发一个page id和page count，告诉服务器我想从第几页开始取，每页是几张照片。这个做法是不对的，因为用户的Feed是会增长的，如果取第一页和第二页之间有了新的post, 那返回的图片的index就会错位。
正确做法是传last timestamp和page count，这样就解决了错位的问题。


扩展性 (Scalability)，容错性，延迟要求
我们来进一步按照以上三点来进一步优化我们的设计以满足我们在理解需求中提到的Low Latency, High Reliability 和 High Availability.

扩展性 (Scalability)
Scability 讨论在数据量和访问量增大的情况下，我们如何应对。这里我们梳理一下之前为了 Scalability 所作的选择。

• High-level diagram 中的 Load Balancer
• 存储系统里的缓存，数据库和文件系统
• 核心子服务 Feed Service 设计中的 Hybrid approach
• 接口设计中的分页 (Pagination)
  

以上这些设计让我们可以通过加机器的方法来应对与日俱增的数据量和访问量。

容错性 (Fault-tolerance)
要构建一个在服务器众多的服务，我们难免会碰到硬件和软件的不稳定性。面对这些难以预测的问题，我们怎么才能让用户感受到一致并且理想的体验呢？那就是提高容错性。
提高容错性的目标是两点。

• 无单点故障 (No single point of failure)
• Fail gracefully
  

我们在这题的情景下分别检视每个系统组件，看看如何达到以上目标。

• Post Service 和 Feed Service 需要有多台服务器由 Load Balancer 去分配请求，当某台机器出现有问题的时候，请求会被发送到别的机器上，造成服务的延迟增加而不是无服务的状态。
• 缓存需要有多台服务器，如果一台出现问题，其他的缓存仍能正常工作，使得这样数据库访问有限地增加。问题缓存重启后，我们失去了该缓存的数据，只能慢慢恢复，然而一段时间后数据库访问会回到原来状态。
• 数据库和文件系统需要有备份，我们是无法容忍数据丢失的。常见的方法有Master-slave replication, Master承担“写”请求，slave承担“读”请求，Master的数据在满足eventual consistency的条件下备份到slave上。Master如果出现问题，一台Slave会被promote成Master。Slave因为有多台并且承担一样的任务，其中一台重启的时候，Master只需给它补上丢失的数据即可。这样不仅备份了数据，而且降低了每台机器接受请求的压力。
  

延迟要求 (Latency)
在前面的High-level Diagram章节中，我们在讨论push vs pull的时候选择push的核心论点是这个服务是read-heavy并且延迟必须足够低。在此后采取hybrid approach的优化后，系统延迟仍会低于pull。

监控和警报
监控核心指标并设立警报。实际系统里的指标远不止以下，这里举一些重要的。

• 服务QPS
• 服务延迟
• 服务可用性 (Availability)
• Async worker load
• 系统缓存命中率
• CDN缓存命中率
• 数据库使用比例
• 文件系统使用比例
  

专题 deep dive
数据分片 (Sharding)
这道题面试官可以找到很多角度去深挖，这里就提一个比较常见的考点。问题是这样的 - Instagram的Feed Table数据量单机无法承受的时候，你会怎样Scale up?
最直接的想法是，对于每个user id做hashing，分别放在不同的机器上。这样说答对了一半，面试官会跟进，问这样会不会造成有的机器很满，有的很空，如果某些机器又满了怎么办？
要解决这个问题的机制比较复杂，Cassandra的设计给我们提供了很好的设计思路，我们可以使用 Consistent Hashing 的 Hash Ring 来解决 node redistrubtion 的问题。


总结
在面试的过程中，我们一边思考，一边改进我们的系统。最终的系统大概是这样的。

我们回顾一下最初写下的需求，看一下是不是都满足了。最后再跟面试官确认一次。


到这里这道题就算是解完了，能看到这里的也算是真爱了，作为纯原创内容，我连写带画前后准备了两周时间，希望能给前一篇文章里留言的小伙伴一个交代。
希望大家能给点大米，让我有动力继续往下写。欢迎大家对讲的不清楚的或是有错误的提出批评指正，也欢迎大家提出其他系统设计方面想看的内容。

关于 feedtable， 选用 user id 做primary key是不是不对？ primary key 是唯一标识 一个row的，至少得是(user_id, post_id) pair做primary key吧

jackyzhang 发表于 2020-1-31 06:34
"选用user id做primary key优于post id"  -> 因为使用的时候是用uid做key?

对，按照use pattern来考虑key的选择

楼主您好，谢谢您的讲解。
文章中关于post的photo的关系，好像是1:1，但是一般一个post是有多张图片的，也就是说post和photo的关系是1:N (1<=N<=9)。而且我刚才在browser中使用了下Instagram，一个post下的不同图片的url是不一样的。这里是不是需要另外一个table存post和photo的对应的关系。或者直接在post 这个table中存一个类型为List的photo_links field?

"选用user id做primary key优于post id"  -> 因为使用的时候是用uid做key?

楼主大好人，图文并茂，写得非常好！

支持楼主，真的大好人

很不错的文章，作者很用心

非常赞！！

"我们可以使用 Consistent Hashing 的 Hash Ring 来解决 node redistrubtion 的问题。" 楼主可否详细讲一下这句话是什么意思？谢谢