feed系统

这是一道老题了&＃xff0c;也是一道高频题&＃xff0c;今天就用这道题来给资深面试官眼中的系统设计一文中答题流程做一个实例。

如果你想跟罗辑一起更深入地学习系统设计&＃xff0c;有兴趣的同学报名参加爱思备受好评的系统设计集训营以及系统设计模拟面试服务&＃xff0c;由作者本人为同学们教学&＃xff0c;力求给大家带来最深入的系统设计高频题讲解以及最针对面试实战的技巧解析&＃xff0c;帮助同学们举一反三&＃xff0c;高效准备面试。

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

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

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

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

1. 理解需求 - Requirement Exploration

下面是一段虚拟的对话。

面试官&＃xff1a;今天我们进行系统设计面试。我们的目标是设计 Instagram。您不必涵盖所有内容。当我们到达那里时&＃xff0c;我们可以深入研究特定的主题。你熟悉 Instagram 吗&＃xff1f;

受访者&＃xff1a;是的&＃xff0c;我一直在用它。这是照片分享应用。在我们开始之前&＃xff0c;我们可以退后一步吗&＃xff1f;我们正在建立的这个“Instagram”的目的是什么&＃xff1f;我们是否试图与真实的事物竞争&＃xff1f;

采访者&＃xff1a;让我们想象一下&＃xff0c;Instagram 还不存在&＃xff0c;人们没有一个好的应用程序来广泛分享照片。

受访者&＃xff1a;很高兴知道。我们想要涵盖哪些功能&＃xff1f;我认为我们有两个基本功能 - 上传照片、从关注者那里获取供稿以及关注/取消关注。听起来不错&＃xff1f;

采访者&＃xff1a;酷&＃xff0c;这是一个很好的清单。为了时间&＃xff0c;让我们关注前两个。

受访者&＃xff1a;延迟呢&＃xff1f;我认为这也是一个重要的要求。我假设我们希望有最小的延迟 - 加载提要可能少于 0.5 秒。

采访者&＃xff1a;这是一个很好的呼吁。

受访者&＃xff1a;好的。&＃xff08;写在白板上&＃xff09;。所以功能要求是支持 1&＃xff09;上传照片和 2&＃xff09;从关注者那里检索提要。非功能性要求是 1) Feed 检索延迟小于半秒&＃xff0c;2) 高度可用。3&＃xff09;高度可靠&＃xff08;数据永不丢失&＃xff09;。非要求是关注和取消关注。

采访者&＃xff1a;有道理。

受访者&＃xff1a;我们需要考虑饲料排名吗&＃xff1f;

采访者&＃xff1a;为了简单起见&＃xff0c;我们跳过这个。假设提要按时间倒序排列。基本上是最新的照片在上面。

受访者&＃xff1a;听起来不错。

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

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

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

说到这里&＃xff0c;我们粗浅地了解了一下需求&＃xff0c;还没有对 non-functional requirement 进行量化和细化&＃xff0c;这就需要我们进一步做资源估算。

继续我们虚拟的对话。

受访者&＃xff1a;我想有很多人想使用这项服务。我们是否应该假设服务的规模与真实的相似&＃xff1f;

采访者&＃xff1a;是的。假设每日活跃用户为 800M。

受访者&＃xff1a;人们多久上传一次&＃xff1f;

采访者&＃xff1a;我们假设人们每 10 天发布一次。

受访者&＃xff1a;假设每日活跃用户每天发出 10 个请求&＃xff0c;每 10 天发布一次。我认为我们可以计算读/写 QPS。&＃xff08;写在白板上&＃xff09;我认为读取 QPS 是 800 * 1000 * 1000 * 10 / (3600 * 24)&＃xff0c;大约 90k QPS&＃xff0c;写入 QPS 是 900 QPS 的 1/100。不要认为这适合一台机器。&＃xff08;笑&＃xff09;

采访者&＃xff1a;不&＃xff0c;不会。

受访者&＃xff1a;我们这里需要大量的存储空间。大多数是存储照片。假设我们将所有照片存储 5 年并且一张照片是 1M&＃xff0c;我们将需要 800 * 1000 * 1000 * 365 * 5 * 1M / 10 &＃61; 146000 TB &＃61; 146 PB。它需要一个或多个数据中心来维持。

采访者&＃xff1a;听起来不错。让我们继续进行高级设计。

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

• 进纸延迟 <0.5s
• 支持800M DAU
• 高可用&＃xff08;同时支持读取 90k QPS&＃xff0c;写入 900 QPS&＃xff09;
• 高度可靠&＃xff08;同时存储约 146PB 数据&＃xff09;

提示两点。

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

3. 高层图

了解需求之后&＃xff0c;我们可以开始画一个简单的图来说明我们的核心服务是如何构建的。

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

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

可以跟面试官确认 Push 的缺点是不是可以接受。

4. 数据结构与存储

4.1 数据库的设计

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

• Post Table (post id 作为分片键)

• 用户表&＃xff08;用户 id 作为分片键&＃xff09;

• Feed Table&＃xff08;用户id作为分片键&＃xff0c;创建时间作为二级索引&＃xff09;

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

• 跟随表

或

这边要说明 Trade off&＃xff1a;

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

4.2 存储系统

缓存, 数据库和文件系统分别用什么&＃xff1f;

4.2.1 缓存 (Cache)

• 数据库的缓存 - Redis, Memcached 我们可以在 Feed Table 之前加一个缓存&＃xff0c;在每一次有 Feed 用户请求的时候&＃xff0c;可以预加载比 Feed 请求多几倍的数据&＃xff0c;这样在用户请求下一页或几页的时候直接从缓存中读取。这个缓存可以使用 LRU 作为 eviction policy。
• 文件系统的缓存 - CDN. 想象一个有很多粉丝的明星发的照片会被很多人看到&＃xff0c;我们是不是需要每一次都从文件系统里拿呢&＃xff1f;显然不行。对于大文件的缓存我们需要把文件提前部署到世界各地的 CDN 上&＃xff0c;这样需要访问时就能第一时间从最近的 CDN 拿到数据。

4.2.2 数据库 (Database)

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

4.2.3 文件系统 (File Storage)

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

5. 核心子服务设计

我们来细化 Feed Service 的架构。

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

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

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

6. 接口设计

GET /v1/feed?count&＃61;{count}&last_timestamp&＃61;{timestamp}


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

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

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

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

POST /v1/images


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

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


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

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

7. 扩展性&＃xff0c;容错性&＃xff0c;延迟要求

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

7.1 扩展性 (Scalability)

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

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

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

7.2 容错性 (Fault-tolerance)

要构建一个在服务器众多的服务&＃xff0c;我们难免会碰到硬件和软件的不稳定性。面对这些难以预测的问题&＃xff0c;我们怎么才能让用户感受到一致并且理想的体验呢&＃xff1f;那就是提高容错性。

提高容错性的目标是两点。

• 无单点故障 (No single point of failure)
• 优雅地失败

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

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

7.3 延迟要求 (Latency)

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

8. 监控和警报

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

• 服务QPS
• 服务延迟
• 服务可用性 (Availability)
• 异步工作负载
• 系统缓存命中率
• CDN 缓存命中率
• 数据库使用比例
• 文件系统使用比例

9. 专题 deep dive

9.1 数据分片 (Sharding)

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

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

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

10. 总结

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

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

Instagram 系统设计题解