系统设计面试题 - 设计 Twitter 时间线和搜索 (或者

引用：
系统设计入门

设计 Twitter 时间线和搜索 (或者 Facebook feed 和搜索)

解答

第一步：通过讨论，明确限制及用例，确定Scope

支持的用例：

• 用户发一条tweet
  • 系统将该tweet推送给该用户的followers，并发送通知
• 用户查看自己的user timeline
• 用户查看别人的home timeline（follow 的人）
• 用户通过关键词搜索
• 系统高可用 high availability

不支持的用例：

• 系统不支持将该tweet推送给第三方系统，例如Firehose。
• 系统不支持隐藏tweet功能。
• 系统不支持统计Analytics功能。

Constraints and assumptions：

• 访问不均匀
• 发送及推送tweet要快
• 100 million 用户
• 平均每个用户有 10 个 followers
• 每天 500 million 新tweet，乘以10，等于每天 5 billion 个推送，每秒60,000次
• 每月 15 billion 写请求 = 500 million * 30，每秒6,000次
• 每月 250 billion 读请求，每秒100,000次
• 每月 10 billion 搜索请求，每秒4次

计算规模：
对于每一个tweet：

• tweet_id：8 bytes
• user_id：32 bytes
• text：140 bytes
• media：10 KB average
• 总共： ~10 KB

对于每一个月：

• 新tweet内容：150 TB = 10 KB * 500 million * 30
• 三年：~5.4 PB = 150 TB * 36

第二步：高层次设计

设计 Twitter 时间线和搜索 (或者 Facebook feed 和搜索)

第三步：设计核心组件

Tweet基本信息存储在关系型数据库MySQL中。
Tweet包含的图片及视频等内容存储在 Object Store 中，可以是 Amazon S3，或者文档型的NoSQL，例如 MongoDB。

对于Write API：设计为一个REST API

• 将Tweet基本信息存储在关系型数据库MySQL中。
• 图片及视频等内容存储在 Object Store 中。
• 使用 Fan Out Service：
  • 使用 User Graph Service 来查询该用户的followers，随后在Memory Cache中更新对应每一个follower的home timeline。
  • 使用Search Service来存储这个tweet，用来支持快速查询。
  • 使用Notification Service来推送给该用户的followers。

使用Redis作为Memory Cache，并使用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   |

对于Read API：设计为一个REST API

• 使用Tweet Info读取tweet详细信息。
• 使用User Info读取user详细信息。
• 从 Memory Cache 中读取 user timeline 和 home timeline，找不到，则查询数据库。

对于Search API：设计为一个REST API

• 解析输入字符串：
  • 去除标记 markup
  • 分词
  • Fix 输入错误 typo
  • 规范化大小写
• 使用Search Service进行搜索。包括结果的 merges, ranks, sorts 等等。

第四步：扩展设计

设计 Twitter 时间线和搜索 (或者 Facebook feed 和搜索)

• 为了服务不同区域的用户，加快访问的速度，使用CDN加速，并缓存静态内容，例如图片，视频等等。
• 为了同时响应更多请求，对服务器水平扩展，并使用Load Balancer做负载均衡。
• 由于是读多写少，可以采用主从复制的数据库模式。主库同时负责读取和写入操作，并复制写入到一个或多个从库中，从库只负责读操作。

其他一些优化思想：

• Memory Cache 只保留活跃用户（最近30天上线过）的timeline，且只保留最近的100条tweet。
• Tweet Info Service 只保留最近一个月的Tweet。
• User Info Service 只保留活跃用户的信息。