Design Instagram

同学们不要死记硬背答案，而是体会一下一步步破题的过程。因为面试流程不唯一，真正碰到这道题的时候面试官的 follow-up 会不一样，大家还是要注重积累，本文试图尽量触及足够的广度，但也无法保证面面俱到。

先扩展一下这道题，这本质是道 New Feed 题，Design Facebook, Design Instagram, Design Twitter 都是一回事，不要被马甲迷惑。

想要直接看答案总结的可以跳到本文末尾，有完整的系统设计图。

那现在我们这就开始按照资深面试官眼中的系统设计中的流程来答题。

1. 理解需求 - Requirement Exploration

下面是一段虚拟的对话。

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 call out.

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.5 s, Highly available, Highly reliable

2. 资源估算 - Back of the Envelope Calculation

说到这里，我们粗浅地了解了一下需求，还没有对 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)

提示两点。

• 注意整个过程中受试者在主导这个需求探索的过程，面试官对受试者给出的需求和数字做确认并少量给出受试者不知道的关键信息（比如 DAU 800M)。不要让面试官做过多的单方面灌输信息。

• 关于数字的计算少数情况下因为时间关系，面试官会让你跳过。如果算得不利索的话，建议跟面试官确认一下。相信这个小学数学对大家都不难，我的小技巧是365*24就算作10000就好，数量级对就行。

3. 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 的缺点是不是可以接受。

4. 数据结构与存储

4.1 数据库的设计

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

• Post Table (post id as sharding key)

POST ID

USER ID

IMAGE URL

CREATE TIME

• User Table (user id as sharding key)

USER ID

USER NAME

PROFILE PHOTO URL

JOIN TIME

• Feed Table (user id as sharding key, create time as secondary index)

USER ID

AUTHOR NAME

PHOTO URL

CREATE TIME

1) 这里 create time 是必须的，在返回 Feed 过程中我们需要按照这个排序。因为我们用了 async worker 来写 feed table, 我们无法保证先写进来的一定就是create time 更早的照片。2) 选用 user id 做 sharding key，使用 create time 来做 secondary index. 3) 使用 author name & photo URL 而不是 author id & photo id 避免了与其他表在读取时进行 JOIN。

• Follow Table

USER ID

FOLLOWER ID

或

USER ID

FOLLOWING ID

这边要说明 Trade off：

Push 方案里我们总是拿 user id 去找他被谁 follow 了，而 pull方案里我们总是拿 user id 去找他 follow 了谁。当然我们也可以两种都存来做一个 hybrid approach，下面会提到。

4.2 存储系统

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

4.2.1 缓存 (Cache)

• 数据库的缓存 - Redis, Memcached 我们可以在 Feed Table 之前加一个缓存，在每一次有 Feed 用户请求的时候，可以预加载比 Feed 请求多几倍的数据，这样在用户请求下一页或几页的时候直接从缓存中读取。这个缓存可以使用 LRU 作为 eviction policy。

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

4.2.2 数据库 (Database)

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

4.2.3 文件系统 (File Storage)

HDFS or Amazon S3 是可以考虑的分布式的文件系统。

5. 核心子服务设计

我们来细化 Feed Service 的架构。

前面我们发现了 Push 带来的 Celebrity Fan-out 的问题。我们就在这个阶段提出 Hybrid approach . 简单来说，我们用一张新的 post table 去专门存超过一定 Follower 数量的 celebrity post，然后每次取 Feed 就直接从这张比较小的表里去找 celebrity 的 post，然后与 Feed table 合并排序。上述的方案会让我们的系统中包含两个 Post table，一个是 celebrity post，另一个是 non-celebrity post。一种更简化的方案是仍将所有的 Post 合并到一张Post table，但使用一个新的列，is_celebrity_post 来加以区分，在分片时，我们可以用这一列作为分片的依据之一。

注意这边 celebrity post 我们就不写到 Feed table 里了，顺便解决了每次 celebrity post 时，async worker 的负载大大增加的问题，使其更稳定。

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

6. 接口设计

GET /v1/feed?count={count}&last_timestamp={timestamp}

现在我们思考一下 Feed API 这边写的 count 和 last timestamp 是什么用意呢？

答案是分页 (Pagination)。每一次 getFeed，我们不可能把所有的该用户的 F eed 一股脑的发回去，我们必须分成一段一段地发。那么问题来了，怎么才能取回第二页呢？

最直接的想法是在 getFeed 中发一个 page id 和 page count，告诉服务器我想从第几页开始取，每页是几张照片。这个做法是不对的，因为用户的 Feed 是会增长的，如果取第一页和第二页之间有了新的 post, 那返回的图片的 index 就会错位。

正确做法是传 last timestamp 和 page count，这样就解决了错位的问题。

POST /v1/images

以上 API 用于把图片本身上传到服务器端，换取一个 URL，S3 提供类似的功能。

POST /v1/posts
{
    "image_url": image_url,
    "description": "hello world"
}

以上 API 用于把 Post 上传到服务器端，包括图片链接以及文字介绍。将图片本身的上传和 Post 的上传分开允许我们在产品逻辑里将两者的发送时间分开（照片可以在文字介绍还没编写好之前就上传），另一方面允许我们更好地复用服务，特别是前者，图片上传服务可以被很多别的 API 利用。

这里没有将 User ID 放在 API 的输入当中是考虑我们不会去以他人名义发送照片或者取得他人的信息流，所以两个 API 可以默认用户是当前被 Authenticated 的用户，实现上可以从 Auth Token 里拿，而不必从 API 中拿。

7. 扩展性，容错性，延迟要求

我们来进一步按照以上四点来进一步优化我们的设计以满足我们在第一节中收集的需求 - Low Latency, High Reliability 和 High Availability.

7.1 扩展性 (Scalability)

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

• High-level diagram 中的 Load Balancer

• 存储系统里的缓存，数据库和文件系统

• 核心子服务 Feed Service 设计中的 Hybrid approach

• 接口设计中的分页 (Pagination)

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

7.2 容错性 (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 只需给它补上丢失的数据即可。这样不仅备份了数据，而且降低了每台机器接受请求的压力。

7.3 延迟要求 (Latency)

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

8. 监控和警报

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

• 服务QPS

• 服务延迟

• 服务可用性 (Availability)

• Async worker load

• 系统缓存命中率

• CDN 缓存命中率

• 数据库使用比例

• 文件系统使用比例

9. 专题 deep dive

9.1 数据分片 (Sharding)

这道题面试官可以找到很多角度去深挖，这里就提一个比较常见的考点。问题是这样的 - Instagram 的 Feed Table 数据量单机无法承受的时候，你会怎样 Scale up?

最直接的想法是，对于每个 user id 做 hashing，分别放在不同的机器上。这样说答对了一半，面试官会跟进，问这样会不会造成有的机器很满，有的很空，如果某些机器又满了怎么办？

要解决这个问题的机制比较复杂，Cassandra 的设计给我们提供了很好的设计思路，我们可以使用 Consistent Hashing 的 Hash Ring 来解决 node re-distribution 的问题。

10. 总结

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

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