设计 Facebook 的 feed与设计 Facebook 搜索与此为同一类型问题。

第一步：简述用例与约束条件

搜集需求与问题的范围。 提出问题来明确用例与约束条件。 讨论假设。

我们将在没有面试官明确说明问题的情况下，自己定义一些用例以及限制条件。

用例

我们将把问题限定在仅处理以下用例的范围中

用户发布了一篇推特服务将推特推送给关注者，给他们发送消息通知与邮件用户浏览用户时间轴（用户最近的活动）用户浏览主页时间轴（用户关注的人最近的活动）用户搜索关键词服务需要有高可用性

不在用例范围内的有

服务向 Firehose 与其它流数据接口推送推特服务根据用户的”是否可见“选项排除推特 隐藏未关注者的 @回复关心”隐藏转发“设置数据分析

限制条件与假设

提出假设

普遍情况

网络流量不是均匀分布的发布推特的速度需要足够快速 除非有上百万的关注者，否则将推特推送给粉丝的速度要足够快1 亿个活跃用户每天新发布 5 亿条推特，每月新发布 150 亿条推特 平均每条推特需要推送给 5 个人每天需要进行 50 亿次推送每月需要进行 1500 亿次推送每月需要处理 2500 亿次读取请求每月需要处理 100 亿次搜索

时间轴功能

浏览时间轴需要足够快推特的读取负载要大于写入负载 需要为推特的快速读取进行优化存入推特是高写入负载功能

搜索功能

搜索速度需要足够快搜索是高负载读取功能

计算用量

如果你需要进行粗略的用量计算，请向你的面试官说明。

每条推特的大小：tweet_id- 8 字节user_id- 32 字节text- 140 字节media- 平均 10 KB总计： 大约 10 KB每月产生新推特的内容为 150 TB 每条推特 10 KB * 每天 5 亿条推特 * 每月 30 天3 年产生新推特的内容为 5.4 PB每秒需要处理 10 万次读取请求 每个月需要处理 2500 亿次请求 * (每秒 400 次请求 / 每月 10 亿次请求)每秒发布 6000 条推特 每月发布 150 亿条推特 * (每秒 400 次请求 / 每月 10 次请求)每秒推送 6 万条推特 每月推送 1500 亿条推特 * (每秒 400 次请求 / 每月 10 亿次请求)每秒 4000 次搜索请求

便利换算指南：

每个月有 250 万秒每秒一个请求 = 每个月 250 万次请求每秒 40 个请求 = 每个月 1 亿次请求每秒 400 个请求 = 每个月 10 亿次请求

第二步：概要设计

列出所有重要组件以规划概要设计。

第三步：设计核心组件

深入每个核心组件的细节。

用例：用户发表了一篇推特

我们可以将用户自己发表的推特存储在关系数据库中。我们也可以讨论一下究竟是用 SQL 还是用 NoSQL。

构建用户主页时间轴（查看关注用户的活动）以及推送推特是件麻烦事。将特推传播给所有关注者（每秒约递送 6 万条推特）这一操作有可能会使传统的关系数据库超负载。因此，我们可以使用NoSQL 数据库或内存数据库之类的更快的数据存储方式。从内存读取 1 MB 连续数据大约要花 250 微秒，而从 SSD 读取同样大小的数据要花费 4 倍的时间，从机械硬盘读取需要花费 80 倍以上的时间。1

我们可以将照片、视频之类的媒体存储于对象存储中。

客户端向应用反向代理的Web 服务器发送一条推特Web 服务器将请求转发给写 API服务器写 API服务器将推特使用SQL 数据库存储于用户时间轴中写 API调用消息输出服务，进行以下操作： 查询用户 图 服务找到存储于内存缓存中的此用户的粉丝将推特存储于内存缓存中的此用户的粉丝的主页时间轴中 O(n) 复杂度操作： 1000 名粉丝 = 1000 次查找与插入将特推存储在搜索索引服务中，以加快搜索将媒体存储于对象存储中使用通知服务向粉丝发送推送： 使用队列异步推送通知

向你的面试官告知你准备写多少代码。

如果我们用 Redis 作为内存缓存，那可以用 Redis 原生的 list 作为其数据结构。结构如下：

tweet n+2 tweet n+1 tweet n| 8 bytes 8 bytes 1 byte | 8 bytes 8 bytes 1 byte | 8 bytes 8 bytes 1 byte || tweet_id user_id meta | tweet_id user_id meta | tweet_id user_id meta |

新发布的推特将被存储在对应用户（关注且活跃的用户）的主页时间轴的内存缓存中。

我们可以调用一个公共的REST API：

$ curl -X POST --data '{ "user_id": "123", "auth_token": "ABC123", \"status": "hello world!", "media_ids": "ABC987" }' \/api/v1/tweet

返回：

{"created_at": "Wed Sep 05 00:37:15 +0000 ","status": "hello world!","tweet_id": "987","user_id": "123",...}

而对于服务器内部的通信，我们可以使用RPC。

用例：用户浏览主页时间轴

客户端向Web 服务器发起一次读取主页时间轴的请求Web 服务器将请求转发给读取 API服务器读取 API服务器调用时间轴服务进行以下操作： 从内存缓存读取时间轴数据，其中包括推特 id 与用户 id - O(1)通过multiget向推特信息服务进行查询，以获取相关 id 推特的额外信息 - O(n)通过 muiltiget 向用户信息服务进行查询，以获取相关 id 用户的额外信息 - O(n)

REST API：

$ curl /api/v1/home_timeline?user_id=123

返回：

{"user_id": "456","tweet_id": "123","status": "foo"},{"user_id": "789","tweet_id": "456","status": "bar"},{"user_id": "789","tweet_id": "579","status": "baz"},

用例：用户浏览用户时间轴

客户端向Web 服务器发起获得用户时间线的请求Web 服务器将请求转发给读取 API服务器读取 API从SQL 数据库中取出用户的时间轴

REST API 与前面的主页时间轴类似，区别只在于取出的推特是由用户自己发送而不是关注人发送。

用例：用户搜索关键词

客户端将搜索请求发给Web 服务器Web 服务器将请求转发给搜索 API服务器搜索 API调用搜索服务进行以下操作： 对输入进行转换与分词，弄明白需要搜索什么东西 移除标点等额外内容将文本打散为词组修正拼写错误规范字母大小写将查询转换为布尔操作查询搜索集群（例如Lucene）检索结果： 对集群内的所有服务器进行查询，将有结果的查询进行发散聚合（Scatter gathers）合并取到的条目，进行评分与排序，最终返回结果

REST API：

$ curl /api/v1/search?query=hello+world

返回结果与前面的主页时间轴类似，只不过返回的是符合查询条件的推特。

第四步：架构扩展

根据限制条件，找到并解决瓶颈。

重要提示：不要从最初设计直接跳到最终设计中！

现在你要 1)基准测试、负载测试。2)分析、描述性能瓶颈。3) 在解决瓶颈问题的同时，评估替代方案、权衡利弊。4) 重复以上步骤。请阅读「设计一个系统，并将其扩大到为数以百万计的 AWS 用户服务」来了解如何逐步扩大初始设计。

讨论初始设计可能遇到的瓶颈及相关解决方案是很重要的。例如加上一个配置多台Web 服务器的负载均衡器是否能够解决问题？CDN呢？主从复制呢？它们各自的替代方案和需要权衡的利弊又有什么呢？

我们将会介绍一些组件来完成设计，并解决架构扩张问题。内置的负载均衡器将不做讨论以节省篇幅。

为了避免重复讨论，请参考系统设计主题索引相关部分来了解其要点、方案的权衡取舍以及可选的替代方案。

DNS负载均衡器水平拓展反向代理（web 服务器）API 服务（应用层）缓存关系型数据库管理系统 (RDBMS)SQL 故障主从切换主从复制一致性模式可用性模式

消息输出服务有可能成为性能瓶颈。那些有着百万数量关注着的用户可能发一条推特就需要好几分钟才能完成消息输出进程。这有可能使 @回复 这种推特时出现竞争条件，因此需要根据服务时间对此推特进行重排序来降低影响。

我们还可以避免从高关注量的用户输出推特。相反，我们可以通过搜索来找到高关注量用户的推特，并将搜索结果与用户的主页时间轴合并，再根据时间对其进行排序。

此外，还可以通过以下内容进行优化：

仅为每个主页时间轴在内存缓存中存储数百条推特仅在内存缓存中存储活动用户的主页时间轴 如果某个用户在过去 30 天都没有产生活动，那我们可以使用SQL 数据库重新构建他的时间轴 使用用户 图 服务来查询并确定用户关注的人从SQL 数据库中取出推特，并将它们存入内存缓存仅在推特信息服务中存储一个月的推特仅在用户信息服务中存储活动用户的信息搜索集群需要将推特保留在内存中，以降低延迟

我们还可以考虑优化SQL 数据库来解决一些瓶颈问题。

内存缓存能减小一些数据库的负载，靠SQL Read 副本已经足够处理缓存未命中情况。我们还可以考虑使用一些额外的 SQL 性能拓展技术。

高容量的写入将淹没单个的SQL 写主从模式，因此需要更多的拓展技术。

联合分片非规范化SQL 调优

我们也可以考虑将一些数据移至NoSQL 数据库。

其它要点

是否深入这些额外的主题，取决于你的问题范围和剩下的时间。

NoSQL

键-值存储文档类型存储列型存储图数据库SQL vs NoSQL

缓存

在哪缓存 客户端缓存CDN 缓存Web 服务器缓存数据库缓存应用缓存什么需要缓存 数据库查询级别的缓存对象级别的缓存何时更新缓存 缓存模式直写模式回写模式刷新

异步与微服务

消息队列任务队列背压微服务

通信

可权衡选择的方案： 与客户端的外部通信 -使用 REST 作为 HTTP API服务器内部通信 -RPC服务发现

安全性

请参阅「安全」一章。

延迟数值

请参阅「每个程序员都应该知道的延迟数」。

持续探讨

持续进行基准测试并监控你的系统，以解决他们提出的瓶颈问题。架构拓展是一个迭代的过程。

架构设计

如上图

题解：/donnemartin/system-design-primer/blob/master/README-zh-Hans.md#%E7%B3%BB%E7%BB%9F%E8%AE%BE%E8%AE%A1%E7%9A%84%E9%9D%A2%E8%AF%95%E9%A2%98%E5%92%8C%E8%A7%A3%E7%AD%94

leetcode单机版本题目

/INGNIGHT/article/details/105500650

1.单机版本中，userid_followerids需要记录用户关注了哪些人。userid_tweeids每个人发布的tweetid，这个是基于时间线的排序链表

2.如果想获得，用户关注人时间线的tewwtid

（1）userid_followerids获得，关注了哪些人（对比架构设计中的图数据库User Grapth Service）

（2）从userid_tweeids获得这边的tweetid，按照时间排序（SQL，存储每个人的tweetid）

（3）不同之处，是架构设计中，因为性能原因，需要缓存好，每个人关注人的tweetid

附录

/thread-10587-1-1.html

/thread-177-1-1.html

ppt地址：/s/1pJP2fij#list/path=%2F