system-design-primer

本文集文档发布于灏天文库

设计推特时间轴与搜索功能

文档摘要

设计推特时间轴与搜索功能 注意：这个文档中的链接会直接指向系统设计主题索引中的有关部分，以避免重复的内容。你可以参考链接的相关内容，来了解其总的要点、方案的权衡取舍以及可选的替代方案。 设计 Facebook 的 feed 与设计 Facebook 搜索与此为同一类型问题。 第一步：简述用例与约束条件 搜集需求与问题的范围。 提出问题来明确用例与约束条件。 讨论假设。 我们将在没有面试官明确说明问题的情况下，自己定义一些用例以及限制条件。

设计推特时间轴与搜索功能

注意：这个文档中的链接会直接指向系统设计主题索引中的有关部分，以避免重复的内容。你可以参考链接的相关内容，来了解其总的要点、方案的权衡取舍以及可选的替代方案。

设计 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 亿次请求

第二步：概要设计

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

Imgur

第三步：设计核心组件

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

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

我们可以将用户自己发表的推特存储在关系数据库中。我们也可以讨论一下究竟是用 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" }' \
    https://twitter.com/api/v1/tweet
​

返回：

{
    "created_at": "Wed Sep 05 00:37:15 +0000 2012",
    "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 https://twitter.com/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 https://twitter.com/api/v1/search?query=hello+world
​

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

第四步：架构扩展

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

Imgur

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

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

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

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

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

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

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

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

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

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

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

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

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

其它要点

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

NoSQL

缓存

异步与微服务

通信

安全性

请参阅「安全」一章。

延迟数值

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

持续探讨

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

Note: This document links directly to relevant areas found in the system design topics to avoid duplication. Refer to the linked content for general talking points, tradeoffs, and alternatives.

Design the Facebook feed and Design Facebook search are similar questions.

Step 1: Outline use cases and constraints

Gather requirements and scope the problem.
Ask questions to clarify use cases and constraints.
Discuss assumptions.

Without an interviewer to address clarifying questions, we'll define some use cases and constraints.

Use cases

We'll scope the problem to handle only the following use cases

  • User posts a tweet
    • Service pushes tweets to followers, sending push notifications and emails
  • User views the user timeline (activity from the user)
  • User views the home timeline (activity from people the user is following)
  • User searches keywords
  • Service has high availability

Out of scope

  • Service pushes tweets to the Twitter Firehose and other streams
  • Service strips out tweets based on users' visibility settings
    • Hide @reply if the user is not also following the person being replied to
    • Respect 'hide retweets' setting
  • Analytics

Constraints and assumptions

State assumptions

General

  • Traffic is not evenly distributed
  • Posting a tweet should be fast
    • Fanning out a tweet to all of your followers should be fast, unless you have millions of followers
  • 100 million active users
  • 500 million tweets per day or 15 billion tweets per month
    • Each tweet averages a fanout of 10 deliveries
    • 5 billion total tweets delivered on fanout per day
    • 150 billion tweets delivered on fanout per month
  • 250 billion read requests per month
  • 10 billion searches per month

Timeline

  • Viewing the timeline should be fast
  • Twitter is more read heavy than write heavy
    • Optimize for fast reads of tweets
  • Ingesting tweets is write heavy

Search

  • Searching should be fast
  • Search is read-heavy

Calculate usage

Clarify with your interviewer if you should run back-of-the-envelope usage calculations.

  • Size per tweet:
    • tweet_id - 8 bytes
    • user_id - 32 bytes
    • text - 140 bytes
    • media - 10 KB average
    • Total: ~10 KB
  • 150 TB of new tweet content per month
    • 10 KB per tweet * 500 million tweets per day * 30 days per month
    • 5.4 PB of new tweet content in 3 years
  • 100 thousand read requests per second
    • 250 billion read requests per month * (400 requests per second / 1 billion requests per month)
  • 6,000 tweets per second
    • 15 billion tweets per month * (400 requests per second / 1 billion requests per month)
  • 60 thousand tweets delivered on fanout per second
    • 150 billion tweets delivered on fanout per month * (400 requests per second / 1 billion requests per month)
  • 4,000 search requests per second
    • 10 billion searches per month * (400 requests per second / 1 billion requests per month)

Handy conversion guide:

  • 2.5 million seconds per month
  • 1 request per second = 2.5 million requests per month
  • 40 requests per second = 100 million requests per month
  • 400 requests per second = 1 billion requests per month

Step 2: Create a high level design

Outline a high level design with all important components.

Imgur

Step 3: Design core components

Dive into details for each core component.

Use case: User posts a tweet

We could store the user's own tweets to populate the user timeline (activity from the user) in a relational database. We should discuss the use cases and tradeoffs between choosing SQL or NoSQL.

Delivering tweets and building the home timeline (activity from people the user is following) is trickier. Fanning out tweets to all followers (60 thousand tweets delivered on fanout per second) will overload a traditional relational database. We'll probably want to choose a data store with fast writes such as a NoSQL database or Memory Cache. Reading 1 MB sequentially from memory takes about 250 microseconds, while reading from SSD takes 4x and from disk takes 80x longer.1

We could store media such as photos or videos on an Object Store.

  • The Client posts a tweet to the Web Server, running as a reverse proxy
  • The Web Server forwards the request to the Write API server
  • The Write API stores the tweet in the user's timeline on a SQL database
  • The Write API contacts the Fan Out Service, which does the following:
    • Queries the User Graph Service to find the user's followers stored in the Memory Cache
    • Stores the tweet in the home timeline of the user's followers in a Memory Cache
      • O(n) operation: 1,000 followers = 1,000 lookups and inserts
    • Stores the tweet in the Search Index Service to enable fast searching
    • Stores media in the Object Store
    • Uses the Notification Service to send out push notifications to followers:
      • Uses a Queue (not pictured) to asynchronously send out notifications

Clarify with your interviewer how much code you are expected to write.

If our Memory Cache is Redis, we could use a native Redis list with the following structure:

           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   |
​

The new tweet would be placed in the Memory Cache, which populates the user's home timeline (activity from people the user is following).

We'll use a public REST API:

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

Response:

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

For internal communications, we could use Remote Procedure Calls.

Use case: User views the home timeline

  • The Client posts a home timeline request to the Web Server
  • The Web Server forwards the request to the Read API server
  • The Read API server contacts the Timeline Service, which does the following:
    • Gets the timeline data stored in the Memory Cache, containing tweet ids and user ids - O(1)
    • Queries the Tweet Info Service with a multiget to obtain additional info about the tweet ids - O(n)
    • Queries the User Info Service with a multiget to obtain additional info about the user ids - O(n)

REST API:

$ curl https://twitter.com/api/v1/home_timeline?user_id=123
​

Response:

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

Use case: User views the user timeline

  • The Client posts a user timeline request to the Web Server
  • The Web Server forwards the request to the Read API server
  • The Read API retrieves the user timeline from the SQL Database

The REST API would be similar to the home timeline, except all tweets would come from the user as opposed to the people the user is following.

Use case: User searches keywords

  • The Client sends a search request to the Web Server
  • The Web Server forwards the request to the Search API server
  • The Search API contacts the Search Service, which does the following:
    • Parses/tokenizes the input query, determining what needs to be searched
      • Removes markup
      • Breaks up the text into terms
      • Fixes typos
      • Normalizes capitalization
      • Converts the query to use boolean operations
    • Queries the Search Cluster (ie Lucene) for the results:
      • Scatter gathers each server in the cluster to determine if there are any results for the query
      • Merges, ranks, sorts, and returns the results

REST API:

$ curl https://twitter.com/api/v1/search?query=hello+world
​

The response would be similar to that of the home timeline, except for tweets matching the given query.

Step 4: Scale the design

Identify and address bottlenecks, given the constraints.

Imgur

Important: Do not simply jump right into the final design from the initial design!

State you would 1) Benchmark/Load Test, 2) Profile for bottlenecks 3) address bottlenecks while evaluating alternatives and trade-offs, and 4) repeat. See Design a system that scales to millions of users on AWS as a sample on how to iteratively scale the initial design.

It's important to discuss what bottlenecks you might encounter with the initial design and how you might address each of them. For example, what issues are addressed by adding a Load Balancer with multiple Web Servers? CDN? Master-Slave Replicas? What are the alternatives and Trade-Offs for each?

We'll introduce some components to complete the design and to address scalability issues. Internal load balancers are not shown to reduce clutter.

To avoid repeating discussions, refer to the following system design topics for main talking points, tradeoffs, and alternatives:

The Fanout Service is a potential bottleneck. Twitter users with millions of followers could take several minutes to have their tweets go through the fanout process. This could lead to race conditions with @replies to the tweet, which we could mitigate by re-ordering the tweets at serve time.

We could also avoid fanning out tweets from highly-followed users. Instead, we could search to find tweets for highly-followed users, merge the search results with the user's home timeline results, then re-order the tweets at serve time.

Additional optimizations include:

  • Keep only several hundred tweets for each home timeline in the Memory Cache
  • Keep only active users' home timeline info in the Memory Cache
    • If a user was not previously active in the past 30 days, we could rebuild the timeline from the SQL Database
      • Query the User Graph Service to determine who the user is following
      • Get the tweets from the SQL Database and add them to the Memory Cache
  • Store only a month of tweets in the Tweet Info Service
  • Store only active users in the User Info Service
  • The Search Cluster would likely need to keep the tweets in memory to keep latency low

We'll also want to address the bottleneck with the SQL Database.

Although the Memory Cache should reduce the load on the database, it is unlikely the SQL Read Replicas alone would be enough to handle the cache misses. We'll probably need to employ additional SQL scaling patterns.

The high volume of writes would overwhelm a single SQL Write Master-Slave, also pointing to a need for additional scaling techniques.

We should also consider moving some data to a NoSQL Database.

Additional talking points

Additional topics to dive into, depending on the problem scope and time remaining.

NoSQL

Caching

Asynchronism and microservices

Communications

Security

Refer to the security section.

Latency numbers

See Latency numbers every programmer should know.

Ongoing

  • Continue benchmarking and monitoring your system to address bottlenecks as they come up
  • Scaling is an iterative process
作者与出处
原作者： donnemartin
来源：donnemartin
许可证：CC BY 4.0
整理： 灏天文库整理
由灏天文库结构化整理，提供目录导航、全文检索与在线阅读，便于系统化学习
发布者: 作者: donnemartin 转发
评论区 (0)
U
0/500