需求

让我们设计一个类似Twitter的社交网络服务。该服务的用户将能够发布推文、关注他人以及喜爱的推文。

难度：中等

1.什么是Twitter？

Twitter是一种在线社交网络服务，用户可以发布和阅读140个字符的短消息，称为“推文”。注册用户可以发布和阅读推文，但未注册的用户只能阅读推文。用户通过其网站界面、短信或移动应用程序访问Twitter。

2.系统的要求和目标

我们将设计一个更简单的Twitter版本，并满足以下要求：

功能要求

1.用户应该能够发布新的推文。

2.用户应该能够跟随其他用户。

3.用户应该能够将推文标记为收藏夹。

4.该服务应该能够创建和显示用户的时间线，包括来自用户跟随的所有人。

5.推文可以包含照片和视频。

非功能性需求

1.我们的服务需要高度可用。

2.系统可接受的时间线生成延迟为200ms。

3.一致性可能会受到影响（为了可用性）；如果用户没有看到某个用户的tweet，但是，它本身应该是可用的。

扩展要求

1.搜索推文。

2.回复推特。

3.趋势主题–当前热门主题/搜索。

4.标记其他用户。

5.推特通知。

6.跟随谁？建议？

7.什么时刻，时间点。

3.容量估计和限制

假设我们有10亿用户，每天有2亿活跃用户（DAU）。还假设我们每天有1亿条新推，平均每个用户跟踪200人。

• 每天有多少人喜欢？

如果每个用户平均每天收藏5条推文，我们将拥有：

2亿(=200M) DAU * 5条收藏夹=>1GB条收藏夹

• 我们的系统将生成多少条推文？

让我们假设一个用户平均每天访问他们的时间轴两次，并访问其他五个人的页面。在每个页面上，如果用户看到20条推文，那么我们的系统将生成28GB/天的推文总浏览量：

2亿(=200M) DAU *（（2+5）*20条推文）=>28B/天

• 存储量估计？

假设每条tweet有140个字符，我们需要两个字节来存储一个字符而无需压缩。假设我们需要30个字节来存储每条tweet的元数据（比如ID、时间戳、用户ID等等）。我们需要的总存储空间：

1亿(=100M）DAU *（280+30）字节=>30GB/天

• 我们五年的存储需求是什么？我们需要多少存储空间来存储用户的数据、信息、收藏夹？

1亿(=100M）DAU *（280+30）字节 * (5 * 365天) => 54.75TB/天

并非所有推文都有媒体，让我们假设平均每五条推文有一张照片，每十条推文有一段视频。我们还假设平均一张照片是200KB，一段视频是2MB。这将使我们每天拥有24TB的新媒体。

（100M/5照片*200KB）+（100M/10视频*2MB）~=24TB/天

• 带宽估计由于总入口数为24TB/天，这将转化为290MB/秒。

记住，我们每天有28B条推特。我们必须显示每条推文的照片（如果有照片的话），但我们假设用户在他们的时间线中每看三次视频。因此，总出口将为：

（28B * 280 bytes) / 86400s of text => 93MB/s
+ (28B/5 * 200KB ) / 86400s of photos => 13GB/S + (28B/10/3 * 2MB ) / 86400s of Videos => 22GB/s

Total ~= 35GB/s

4.系统API设计

一旦我们确定了需求，定义系统API总是一个好主意。这应该明确说明系统的期望值。

我们可以使用SOAP或RESTAPI来公开服务的功能。以下可能是发布新tweet的API的定义：

tweet(api_dev_key, tweet_data, tweet_location, user_location, media_ids,
maximum_results_to_return)

参数设计

api_dev_key（string）：注册帐户的api开发者密钥。除其他外，这将用于根据分配的配额限制用户。
tweet_dat（string）：tweet的文本，通常最多140个字符。
tweet_location（string）：此tweet所指的可选位置（经度、纬度）。用户位置（字符串）：添加tweet的用户的可选位置（经度、纬度）。
media_ids（number []）：与推特关联的媒体ID的可选列表。（所有媒体照片、视频等需要单独上传）。

Returns: (string)

成功的帖子将返回访问该推文的URL。否则，将返回相应的HTTP错误。

5.高级系统设计

我们需要一个能够高效存储所有新推文的系统，100M/86400s=>1150条推文/秒，读取28B/86400s=>325K条推文/秒。从需求中可以清楚地看出，这将是一个重读系统。

在较高的层次上，我们需要多个应用程序服务器来为所有这些请求提供服务，前面有负载平衡器用于流量分布。在后端，我们需要一个高效的数据库来存储所有新的推文，并支持大量的读取。我们还需要一些文件存储来存储照片和视频。

尽管我们预计每天的写负载为1亿，读负载为280亿推特。这意味着我们的系统平均每秒将收到约1160条新推文和325K读取请求。这种流量在一天中的分布将是不均匀的，但在高峰时间，我们预计每秒至少有几千个写请求和大约一百万个读请求。在设计系统架构时，我们应该牢记这一点。

6.数据库模式

我们需要存储关于用户、他们的推文、他们最喜欢的推文以及他们关注的人的数据。

要在SQL和NoSQL数据库之间选择以存储上述模式，请参阅设计Instagram下的“数据库模式”。

7.数据分片

由于我们每天都有大量的新tweet，而且我们的读取负载也非常高，因此我们需要将数据分发到多台机器上，以便我们能够高效地读取/写入数据。我们有很多选择来分享我们的数据；让我们一个接一个地看一下：

基于UserID的分片：

我们可以尝试将用户的所有数据存储在一台服务器上。在存储时，我们可以将用户ID传递给哈希函数，该函数将用户映射到数据库服务器，在那里我们将存储用户的所有推文、收藏夹、关注等。在查询用户的推文/关注/收藏夹时，我们可以问哈希函数在哪里可以找到用户的数据，然后从那里读取数据。这种方法有两个问题：

1.如果用户变热怎么办？服务器上可能会有很多查询容纳用户。这种高负载将影响我们服务的性能。

2.随着时间的推移，与其他用户相比，一些用户最终可能会存储大量tweet或拥有大量的关注。保持不断增长的用户数据的均匀分布是相当困难的。

要从这些情况中恢复，我们必须重新分区/重新分发数据或使用一致的哈希。

基于TweetID的切分：

我们的散列函数将把每个TweetID映射到一个随机服务器，我们将在那里存储该Tweet。要搜索tweets，我们必须查询所有服务器，每个服务器将返回一组tweets。集中式服务器将聚合这些结果以将其返回给用户。让我们看看时间线生成示例；以下是我们的系统生成用户时间线必须执行的步骤数：

1.我们的应用程序（app）服务器将找到用户跟踪的所有人。

2.App server将向所有数据库服务器发送查询，以查找这些人的推文。

3.每个数据库服务器将找到每个用户的tweet，按最近情况对它们进行排序，并返回顶部

推特。

4.App server将合并所有结果并再次对其排序，以将最重要的结果返回给用户。

这种方法解决了热用户的问题，但与按用户ID进行切分不同，我们必须查询所有数据库分区以查找用户的tweet，这可能会导致更高的延迟。

我们可以通过在数据库服务器前面引入缓存来存储热tweet，从而进一步提高性能。

基于Tweet创建时间的切分：

基于创建时间存储Tweet将使我们能够快速获取所有最热门的Tweet，并且我们只需要查询一小部分服务器。这里的问题是流量负载不会被分配，例如，在写的时候，所有新的tweet都将被发送到一个服务器，而其余的服务器将处于空闲状态。类似地，在读取时，与保存旧数据的服务器相比，保存最新数据的服务器将具有非常高的负载。

如果我们可以在tweed创建时间内结合切分和Tweet创建时间呢？

如果我们不单独存储tweet创建时间并使用TweetID来反映这一点，我们可以从这两种方法中获益。通过这种方式，可以很快找到最新的推文。为此，我们必须使每个TweetID在我们的系统中都是唯一的，并且每个TweetID也应该包含一个时间戳。

我们可以用大纪元来做这个。假设我们的TweetID将有两部分：第一部分将代表历元秒，第二部分将是一个自动递增序列。因此，要创建一个新的TweetID，我们可以使用当前的纪元时间并在其上附加一个自动递增的数字。我们可以从这个TweetID中找出碎片号并将其存储在那里。

我们的TweetID有多大？假设我们的大纪元时间从今天开始，我们需要多少位来存储未来50年的秒数？

86400 sec/day * 365 (days a year) * 50 (years) => 1.6B

我们需要31位来存储这个数字。因为我们平均预期每秒有1150条新推，我们可以分配17位来存储自动递增序列；这将使我们的TweetID长48位。因此，每秒钟我们都可以存储（2^17=>130K）条新推文。我们可以每秒重置自动递增序列。为了容错和更好的性能，我们可以有两个数据库服务器为我们生成自动递增密钥，一个生成偶数密钥，另一个生成奇数密钥。

如果我们假设当前的历元秒数为“1483228800”，我们的TweetID将如下所示：

1483228800 000001

1483228800 000002

1483228800 000003

1483228800 000004 ...

如果我们将TweetID设置为64位（8字节）长，我们可以轻松地将tweet存储100年，也可以将其存储为毫秒。

在上述方法中，我们仍然需要查询所有服务器以生成时间线，但我们的读取（和写入）速度将大大加快。

1.由于我们没有任何辅助索引（在创建时），这将减少写入延迟。

2.在阅读时，我们不需要过滤创建时间，因为我们的主键有纪元时间包括在内。

8.缓存

我们可以为数据库服务器引入缓存来缓存热门推文和用户。我们可以使用像Memcache这样的现成解决方案来存储整个tweet对象。在访问数据库之前，应用服务器可以快速检查缓存是否有所需的tweet。根据客户端的使用模式，我们可以确定需要多少缓存服务器。

• 哪种缓存替换策略最适合我们的需要？

当缓存已满，并且我们希望用更新/更热的tweet替换tweet时，我们将如何选择？对于我们的系统来说，最近最少使用（LRU）是一个合理的策略。根据这项政策，我们首先放弃最近浏览次数最少的tweet。

• 我们如何拥有更智能的缓存？

如果我们遵循80-20规则，即20%的推文产生80%的阅读流量，这意味着某些推文非常受欢迎，大多数人都会阅读它们。这意味着我们可以尝试缓存来自每个碎片的每日读取量的20%。

• 如果我们缓存最新的数据呢？

我们的服务可以从这种方法中受益。比方说，如果80%的用户只看到过去三天的推文；我们可以尝试缓存过去三天的所有推文。假设我们有专门的缓存服务器，缓存过去三天所有用户的所有推文。如上所述，我们每天都会收到1亿条新推文或30GB的新数据（没有照片和视频）。如果我们想存储过去三天的所有推文，我们将需要少于100GB的内存。这些数据可以很容易地放入一台服务器，但我们应该将其复制到多台服务器上，以分配所有读取流量，从而减少缓存服务器上的负载。因此，每当我们生成一个用户的时间线时，我们都可以询问缓存服务器是否有该用户最近的所有推文。如果是，我们可以简单地从缓存返回所有数据。如果缓存中没有足够的tweet，我们必须查询后端服务器以获取数据。在类似的设计中，我们可以尝试缓存过去三天的照片和视频。

我们的缓存就像一个哈希表，其中“key”是“OwnerID”，而“value”是一个双链接列表，其中包含该用户在过去三天内发出的所有推文。因为我们想首先检索最新的数据，所以我们总是可以在链接列表的开头插入新的tweet，这意味着所有较旧的tweet都将位于链接列表的末尾附近。因此，我们可以从尾部删除tweet，为新tweet腾出空间。

9、时间轴生成

关于时间线生成的详细讨论，暂不做重要讨论

10、复制和容错

由于我们的系统是重读的，我们可以为每个DB分区提供多个辅助数据库服务器。辅助服务器将仅用于读取流量。所有写入操作将首先进入主服务器，然后复制到辅助服务器。此方案还将为我们提供容错能力，因为无论何时主服务器发生故障，我们都可以故障切换到辅助服务器。

11、负载平衡

我们可以在系统的三个位置添加负载平衡层：

1）客户端和应用服务器之间；

2）应用服务器和数据库复制服务器之间；

3）聚合服务器和缓存服务器之间。

最初，可以采用简单的循环方法；在服务器之间平均分配传入请求的。此LB易于实现，不会引入任何开销。这种方法的另一个好处是，如果服务器死机，LB将使其退出循环，并停止向其发送任何流量。循环LB的一个问题是它不会占用服务器，考虑到。如果服务器过载或速度较慢，LB不会停止向该服务器发送新请求。为了解决这个问题，可以放置一个更智能的LB解决方案，定期查询后端服务器的负载，并根据负载调整流量。

12、监控

拥有监控系统的能力至关重要。我们应该不断地收集数据，以便及时了解系统的运行情况。我们可以收集以下指标/计数器，以了解我们服务的性能：

1.每天/秒新增推文，每日峰值是多少？

2.Timeline delivery stats，我们的服务每天/每秒发送多少条推文。3.用户看到的刷新时间线的平均延迟。

通过监视这些计数器，我们将了解是否需要更多的复制、负载平衡或缓存。

13、扩展要求

我们如何提供物料？

从某人关注的人那里获取所有最新推文，并按时间对其进行合并/排序。使用分页来获取/显示推文。只从所有关注的人那里获取前N条推文。这取决于客户端的视口，因为在移动设备上，与Web客户端相比，我们显示的tweet更少。我们还可以缓存下一条热门推文以加快速度。或者，我们可以预生成进料以提高效率；

Retweet：对于数据库中的每个Tweet对象，我们可以存储原始Tweet的ID，而不存储此Retweet对象上的任何内容。

趋势主题：我们可以在最近N秒内缓存最频繁出现的hashtag或搜索查询，并在每M秒后不断更新它们。我们可以根据推特、搜索查询、转发或喜欢的频率对趋势主题进行排名。我们可以对展示给更多人的主题给予更多的重视。

跟随谁？如何提出建议？

此功能将提高用户参与度。我们可以推荐某人的朋友。我们可以下两到三层楼去找名人，征求他们的意见。我们可以优先考虑拥有更多追随者的人。

由于在任何时候都只能提出一些建议，所以使用机器学习（ML）来洗牌和重新排序。ML信号可能包括最近跟随人数增加的人、普通跟随者（如果其他人跟随该用户）、普通位置或兴趣等。

时刻：获取过去1或2小时内不同网站的头条新闻，找出相关推文，对它们进行优先级排序，使用ML–监督学习或聚类对它们进行分类（新闻、支持、金融、娱乐等）。然后我们可以在瞬间将这些文章显示为趋势主题。

搜索：搜索包括索引、排名和检索推文。

参考资料

grok_system_design_interview.pdf