[TOC]
什么是TWITTER搜索
Twitter用户可以随时更新其状态。 每个状态都由纯文本组成，我们的目标是设计一个允许搜索所有用户状态的系统。
要求
我们假设Twitter拥有15亿用户，每日活跃用户达8亿。
每个用户每天会搜索5次，每次平均打个9字符。
QPS = 800M59 = 12 b/100K = 120K
平均而言，Twitter每天都会获得4亿次状态更新。
状态的平均大小为300字节。
我们假设每天将有500M搜索。
搜索查询将包含多个与AND / OR组合的单词。
容量估计
存储容量：由于我们每天有4亿个新状态，每个状态平均为300字节，因此我们需要的总存储量为：
400M * 300 => 112GB /天
每秒总存储量：
112GB / 86400秒〜= 1.3MB /秒
系统API
1 | search(api_dev_key, search_terms, maximum_results_to_return, sort, page_token) |
api_dev_key（string）：已注册帐户的API开发人员密钥。 除其他外，这将用于根据用户分配的配额限制用户。
search_terms（string）：包含搜索词的字符串。
maximum_results_to_return（number）：要返回的状态消息数。
sort（number）：可选排序模式：最新的第一个（0 - 默认），最匹配（1），最喜欢（2）。
page_token（string）：此标记将指定应返回的结果集中的页面。
高层设计
image.png
但从搜索服务考虑。如下所示
image.png
TRIE 数 检索TOP n
image.png
存储
DATA COLLECTION SERVICE，根据用户搜索的LOG，用WORD CNT，转换到BIG TABLE 的一张表，分别是哪些词，频率
image.png
随后QUERY Service,可以根据这个表来建TRIE树。同时序列化到磁盘。
优化
减少响应时间的措施有：
我们可以对用户搜索过的就缓存在浏览器端。随后我们可以预测用户下一步大概率搜索的字母，一起返回并缓存。
image.png
如果字典树一台机器太大存不下的话呢？
image.png
如何减少LOG的大小呢
没1000/1 存一次，因为我们需要的相对大小。
所以这样可以节约1/1000的存储量。
细节设计
1.存储：我们每天需要存储112GB的新数据。鉴于这些大量数据，我们需要提出一种数据分区方案，将其有效地分发到多个服务器上。如果我们计划未来五年，我们将需要以下存储：
112GB * 365天* 5 => 200 TB
如果我们永远不想超过80％，我们需要240TB。假设我们想要保留容错的所有状态的额外副本，那么我们的总存储要求将是480 TB。如果我们假设现代服务器可以存储多达4TB的数据，那么我们将需要120个这样的服务器来保存未来五年所需的所有数据。
让我们从一个简单的设计开始，我们将状态存储在MySQL数据库中。我们可以假设将状态存储在具有两列StatusID和StatusText的表中。假设我们基于StatusID对数据进行分区。如果我们的StatusID在系统范围内是唯一的，我们可以定义一个哈希函数，它可以将StatusID映射到存储服务器，我们可以存储该状态对象。
我们如何创建系统范围内唯一的StatusID？如果我们每天获得4亿个新状态，那么我们可以在五年内获得多少个状态对象？
400M * 365天* 5年=> 7300亿
这意味着我们需要一个五个字节的数字来唯一地标识StatusID。假设我们有一个服务可以在需要存储对象时生成唯一的StatusID（我们将在后面详细讨论）。我们可以将StatusID提供给我们的哈希函数来查找存储服务器并将状态对象存储在那里。
2.索引：因为我们的状态查询将由单词组成，所以，让我们构建哪个单词来自哪个状态对象的索引。我们首先估计一下我们的索引有多大。如果我们想为所有英文单词和一些着名名词建立一个索引，如人名，城市名称等，如果我们假设我们有大约300K英语单词和200K名词，那么我们将有500k总单词指数。我们假设一个单词的平均长度是五个字符。如果我们将索引保留在内存中，我们需要2.5MB内存来存储所有单词：
500K * 5 => 2.5 MB
让我们假设我们希望仅在过去两年内将索引保留在所有状态对象的内存中。由于我们将在5年内获得730B状态对象，这将在两年内为我们提供292B状态消息。鉴于此，每个StatusID将是5个字节，我们需要多少内存来存储所有StatusID？
292B * 5 => 1460 GB
所以我们的索引就像一个大的分布式哈希表，其中’key’是单词，’value’将是包含该单词的所有那些状态对象的StatusID列表。假设平均每个状态我们有40个单词，因为我们不会将介词和其他小词如“the”，“an”，“和”等编入索引，我们假设每个状态中我们将有大约15个单词需要编入索引。这意味着每个StatusID将在我们的索引中存储15次。所以总内存需要存储我们的索引：
（1460 * 15）+ 2.5MB~ = 21 TB
假设一个高端服务器有144GB的内存，我们需要152个这样的服务器来保存我们的索引。
我们可以根据两个标准对数据进行分片：
基于单词的分片：在构建索引时，我们将遍历状态的所有单词并计算每个单词的散列以找到将被索引的服务器。要查找包含特定单词的所有状态，我们仅需查询包含该单词的服务器。
我们对这种方法有几个问题：
如果一个词变热怎么办？持有该单词的服务器上会有很多查询。这种高负载会影响我们的服务性能。
随着时间的推移，一些单词最终可能会存储大量的StatusID，因此，在状态增长的同时保持单词的均匀分布是非常困难的。
要从这些情况中恢复，我们必须重新分配数据或使用Consistent Hashing。
基于状态对象的分片：在存储时，我们将StatusID传递给我们的哈希函数以查找服务器并索引该服务器上状态的所有单词。 在查询特定单词时，我们必须查询所有服务器，每个服务器将返回一组StatusID。 集中式服务器将聚合这些结果以将其返回给用户。
image.png
容错
索引服务器死机时会发生什么？我们可以拥有每个服务器的备份服务器，如果主服务器死亡，它可以顶上。
如果主服务器和辅助服务器同时死亡怎么办？我们必须分配一个新服务器并在其上重建相同的索引。我们不知道此服务器上保留了哪些字/状态。如果我们使用“基于STATUS ID进行分片”，那么强力解决方案就是遍历整个数据库并使用我们的哈希函数过滤StatusID，以找出将存储在此服务器上的所有必需状态。这将是低效的，并且在重建服务器期间，我们将无法从中提供任何查询。
我们如何有效地检索状态和索引服务器之间的映射？我们必须构建一个反向索引，将所有StatusID映射到它们的索引服务器。我们的Index-Builder服务器可以保存此信息。我们需要构建一个Hashtable，其中’key’将是索引服务器编号，’value’将是一个HashSet，其中包含保存在该索引服务器上的所有StatusID。请注意，我们将所有StatusID保留在HashSet中，这将使我们能够快速添加/删除索引中的状态。所以现在只要索引服务器必须自己重建，它就可以简单地向Index-Builder服务器询问它需要存储的所有状态，然后获取这些状态来构建索引。这种方法肯定会非常快。我们还应该有一个Index-Builder服务器的副本用于容错。
排序
如果我们想按社交图距离，流行度，相关性等对搜索结果进行排名
假设我们想要对流行度的状态进行排名，例如，状态有多少喜欢或评论，等等。在这种情况下，我们的排名算法可以计算“人气数量”（基于喜欢的数量等），以及 用索引存储它。 在将结果返回到聚合器服务器之前，每个分区都可以根据此流行度数对结果进行排序。 聚合器服务器组合所有这些结果，根据流行度数对它们进行排序，并将最佳结果发送给用户。
作者：西部小笼包
链接：https://www.jianshu.com/p/66884fb9353c
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。