10. 设计 Twitter 搜索
难度等级：中等
Twitter 是最大的社交网络服务之一，用户可以共享图像、新闻和基于文本的消息。这一章，我们将设计一个可以存储和搜索用户推文的服务。相似问题：推文搜索。
1. 什么是 Twitter 搜索？
Twitter 用户可以在任何时间更新他们的状态。每一条状态（称为推文）由纯文本组成，我们的目标是设计一个支持在所有的用户推文中搜索的系统。
2. 系统的要求和目标
我们假设 Twitter 有 150 亿总用户，8 亿日活用户。
Twitter 平均每天有 4 亿条推文。
平均每条推文的大小是 300 个字节。
我们假设每天将有 5 亿次搜索。
搜索查询语句将包含多个单词，和 AND/OR 结合。
我们需要设计一个可以高效存储和查询推文的系统。
3. 容量估算和限制条件
存储容量：由于我们每天有 4 亿条新推文，平均每条推文的大小是 300 个字节，我们需要的总存储是：
400M * 300 => 120GB/day
每秒的总存储：
120GB / 24hours / 3600sec ~= 1.38MB/second
4. 系统 API
我们可以使用 SOAP 或 REST API 将我们的服务的函数公开。以下为搜索的 API 的定义：
参数：
api_dev_key（string）：一个已注册的帐号的 API 开发者关键字。关键字将和其他字段一起根据用户分配的额度限制用户。 search_terms（string）：一个包含搜索项的字符串。 maximum_results_to_return（number）：返回的推文数量。 sort（number）：可选的排序模式：最近优先（0——默认）、最优匹配（1）、最多喜欢（2）。 page_token（string）：该标志表示结果集合中应该返回的页面。
返回：（JSON） 一个包含匹配查询语句的推文列表信息的 JSON 对象。每个结果想可以包含用户 ID 和名字、推文文本、推文 ID、创建时间、喜欢数量等。
5. 高阶设计
高阶角度，我们需要将所有的状态存入数据库，以及创建一个追踪每个单词在哪条推文中出现的索引。该索引可以帮助我们快速找到用户想搜索的推文。
6. 部件设计细节
1. 存储：我们需要每天存储 120GB 新数据。由于数据规模巨大，我们需要使用数据划分方案，高效地将数据分布到多台服务器上。如果我们为将来 5 年做计划，我们将需要的存储是：
120GB * 365days * 5years ~= 200TB
如果任何时候都不想超过总存储的 80%，我们大约需要 250TB 的总存储。我们假设需要存储所有推文的额外备份用于容错，则我们的总容量需求将是 500TB。如果我们假设一台现代服务器最多可以存储 4TB 的数据，我们将需要 125 台这样的服务器存储将来 5 年内所有需要的数据。
我们从一个明显简化的设计开始，将推文存在 MySQL 数据库中。我们可以假设我们将推文存在一张有两列的表中，两列分别是推文 ID 和推文文本。假设我们基于推文 ID 划分数据。如果推文 ID 是系统内唯一的，我们可以定义一个哈希函数，将推文 ID 映射到一台存储这条推文的存储服务器。
我们如何创建系统中唯一的推文 ID？如果我们每天接收 4 亿条新推文，我们在 5 年内可以预期多少个推文对象？
400M * 365 days * 5 years => 730 billion
这意味着我们需要使用 5 个字节的数字唯一地识别推文 ID。我们假设有一个服务可以在我们需要存储对象（这里讨论的推文 ID 和「设计 Twitter」中讨论的推文 ID 相似）的任何时候生成一个唯一的推文 ID。我们可以将推文 ID 传给哈希函数，找到存储服务器并将我们的推文对象存储在该服务器上。
2. 索引：我们的索引应该是什么样的？由于我们的推文查询由单词组成，我们建立的索引应该可以告诉我们哪个单词出现在哪个推文对象中。我们首先估算我们的索引有多大。如果我们想为所有的英语单词和一些著名的名词如人名、城市名等建立索引，以及如果我们假设有大约 30 万个英语单词和 20 万个名词，我们的索引中一共将有 50 万个单词。我们假设每个单词的平均长度是 5 个字符。如果我们将索引存储在内存中，我们需要 2.5MB 的内存存储所有的单词：
500K * 5 => 2.5 MB
我们假设只需要为过去 2 年的所有推文在内存中维护索引。由于我们在 5 年内将有 7300 亿条推文，在 2 年内将有 2920 亿条推文。已知每个推文 ID 的大小是 5 个字节，我们存储所有推文 ID 需要多少内存？
292B * 5 => 1460 GB
因此我们的索引将会像一个大型分布式哈希表，其中的关键字是单词，值是包含该单词的所有推文的推文 ID 列表。假设平均每条推文有 40 个单词，由于我们不需要索引介词和其他如 the、an、and 等小单词，我们假设每条推文中有大约 15 个单词需要被索引。这意味着每个推文 ID 将在我们的索引中存储 15 词。因此存储索引需要的总内存是：
(1460 * 15) + 2.5MB ~= 21 TB
假设一台高端服务器有 144GB 内存，我们需要 152 台这样的服务器存储我们的索引。
我们可以基于两个标准将我们的数据分片：
基于单词分片：当建立索引时，我们将遍历一条推文的全部单词并计算每个单词的哈希值以找到应该被索引的服务器。为了找到包含特定单词的全部推文，我们只需要在包含该单词的服务器上查询。
这个方法存在两个问题：
如果一个单词很热门怎么办？这台服务器上将会有大量包含该单词的查询。高负载将影响影响服务的性能。
随着时间的推移，一些单词可能比其他单词多存储很多推文 ID，因此，在推文持续增加的过程中维护单词的均匀分布是非常棘手的。
为了从上述状态中恢复，我们必须重新划分数据或者使用一致性哈希。
基于推文对象分片：存储时，我们将推文 ID 传递给哈希函数以找到服务器，并将推文中的所有单词在那台服务器上建立索引。当查询特定单词时，我们必须查询所有的服务器，每台服务器将返回一个推文 ID 的集合。一台中心化服务器将回合这些结果并将其返回给用户。
7. 容错
如果一台索引服务器宕机了怎么办？我们可以给每一台服务器安排一台二级备份服务器，当主服务器宕机时二级服务器可以在故障转移之后获得控制权。主服务器和二级服务器具有索引的相同备份。
如果主服务器和二级服务器同时宕机了怎么办？我们必须分配一台新服务器并在新服务器上重新建立相同的索引。我们如何做到？我们不知道这台服务器上存储了什么单词/推文。如果我们使用「基于推文对象分片」，暴力解决方法是遍历整个数据库并使用我们的哈希函数过滤推文 ID 以找到存储在这台服务器上的所有需要的推文。这个方法的效率低下，而且在重新建立服务器的时间内我们无法使用这台服务器处理任何查询，因此会丢失部分应该被用户看到的推文。
我们可以如何高效地获取推文和索引服务器之间的映射？我们必须建立一个反向索引，将所有的推文 ID 映射到对应的索引服务器。我们的索引建立服务器可以存储这些信息。我们需要建立一个哈希表，关键字是索引服务器数字，值是包含存储在这台索引服务器上的所有推文 ID 的的哈希集合。注意我们将所有的推文 ID 存入哈希集合，浙江允许我们快速在索引中添加/删除推文。此时，任何时候当一台索引服务器必须重新建立时，可以快速从索引建立服务器获得需要存储的所有推文，然后获取这些推文建立索引。这个方法的速度显然很快。我们也需要为索引建立服务器安排一台备份服务器用于容错。
8. 缓存
为了处理热门推文，我们可以在数据库前面引入缓存。我们可以使用 Memcached 将所有的热门推文存入内存。在应用服务器访问后端数据库之前，可以快速检查缓存中是否有该推文。基于客户端的使用模式，我们可以调整需要多少台缓存服务器。对于缓存删除策略，最近最少使用（LRU）对我们的系统适用。
9. 负载均衡
我们可以在系统中的 2 个位置增加负载均衡层：1. 在客户端和应用服务器之间；2. 在应用服务器和后端服务器之间。初始时，可以使用一个简单的轮询调度方法，将进入地请求平均地分布到各台后端服务器。这样地负载均衡实现简单，不会引入新的开销。该方法的另一个好处是负载均衡会将宕机的服务器移出轮询，停止向其发送任何流量。轮询调度负载均衡的一个问题是没有考虑服务器的负载。如果一台服务器负载过重或者速度过慢，负载均衡并不会停止向这台服务器发送新请求。为了处理这个问题，可以使用一个更智能的负载均衡解决方案，该方案周期性地查询后端服务器获取负载信息，并基于该信息调整流量。
10. 搜索结果排名
如果我们要将搜索结果根据社交图距离、流行程度、相关程度等指标排名，应该怎么做？
假设我们要将推文根据流行程度排名，如一条推文获得多少个喜欢、多少条评论等。这种情况下，我们的排名系统可以计算一个「流行程度数」（基于喜欢的数量等）并将其存储在索引中。每个分区可以在将结果返回给汇合服务器之前基于这个流行程度数将结果排序。汇合服务器组合所有的结果，基于流行程度数将结果排序，然后将最靠前的结果发送给用户。
Last updated
