需求
Twitter是最大的社交网络服务之一，用户可以在其中共享照片、新闻和基于文本的消息。在本章中，我们将设计一个可以存储和搜索用户推文的服务。类似的问题：推特搜索。
难度：中等
1.什么是Twitter搜索？
Twitter用户可以随时更新他们的状态。每个状态（称为tweet）都由纯文本组成，我们的目标是设计一个允许搜索所有用户推特
的系统。
2.系统的要求和目标
•假设Twitter拥有15亿用户，每天有8亿活跃用户。
•推特平均每天收到4亿条推特。
•推文的平均大小为300字节。
•假设每天有5亿次搜索。
•搜索查询将由多个与和/或组合的词组成。我们需要设计一个能够高效存储和查询推文的系统。
3.容量估计和限制
存储容量：由于我们每天有4亿条新推文，每条推文平均为300字节，因此我们需要的总存储量为：
400M * 300 => 120GB/day
每秒总存储空间：
120GB / 24hours / 3600sec ~= 1.38MB/second
4.系统API
我们可以使用SOAP或RESTAPI来公开我们服务的功能；以下可能是搜索API的定义：
代码语言：txt复制
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_标记（字符串）：此标记将在结果集中指定应返回的页面。
返回结果: (JSON)
包含与搜索查询匹配的tweet列表信息的JSON。每个结果条目可以有用户ID&姓名、推文文本、推文ID、创建时间、喜欢的数量等。5.高级设计在高层，我们需要将所有状态存储在数据库中，还需要建立一个索引来跟踪哪个单词出现在哪个tweet中。这个索引将帮助我们快速找到用户试图搜索的推文。
5.高级设计
在高层，我们需要将所有状态存储在数据库中，还需要建立一个索引来跟踪哪个单词出现在哪个tweet中。这个索引将帮助我们快速找到用户试图搜索的推文。
Twitter搜索的高级设计
6.详细部件设计
1.存储：
我们每天需要存储120GB的新数据。考虑到如此巨大的数据量，我们需要提出一种数据分区方案，将数据有效地分布到多个服务器上。如果我们计划未来五年，我们将需要以下存储：
120GB * 365days * 5years ~= 200TB
如果我们不想在任何时候都超过80%的存储空间，我们大约需要250TB的总存储空间。让我们假设我们想要保留所有tweet的额外副本以实现容错；那么我们的总数呢,
存储需求将为500TB。如果我们假设一台现代服务器可以存储多达4TB的数据，我们将需要125台这样的服务器来保存未来五年所需的所有数据。
让我们从一个简单的设计开始，我们将tweet存储在一个MySQL数据库中。我们可以假设我们将tweets存储在一个表中，该表有两列：TweetID和TweetText。假设我们根据TweetID对数据进行分区。如果我们的TweetID在系统范围内是唯一的，那么我们可以定义一个哈希函数，该函数可以将TweetID映射到一个存储服务器，在那里我们可以存储该tweet对象。
我们如何创建系统范围内唯一的TweetID？
如果我们每天都能收到4亿条新推，那么五年内我们预计会收到多少推特对象？
400M * 365 days * 5 years => 730 billion
这意味着我们需要一个5字节的数字来唯一地标识TweetID。假设我们有一个服务，它可以在需要存储对象时生成唯一的TweetID（这里讨论的TweetID与设计Twitter时讨论的TweetID类似）。我们可以将TweetID提供给hash函数，以找到存储服务器并将tweet对象存储在那里。
2.索引：
我们的索引应该是什么样子？因为我们的tweet查询将由单词组成，所以让我们构建一个索引来告诉我们哪个单词来自哪个tweet对象。让我们先估计一下我们的指数会有多大。如果我们想为所有的英语单词和一些著名的名词（如人名、城市名等）建立一个索引，如果我们假设我们有大约30万个英语单词和20万个名词，那么我们的索引中总共有50万个单词。让我们假设一个单词的平均长度是五个字符。如果我们将索引保存在内存中，则需要2.5MB内存来存储所有单词：
500K * 5 => 2.5 MB
让我们假设我们希望将过去两年的所有推文的索引保存在内存中。由于我们将在5年内获得730B条推文，因此两年内我们将获得292B条推文。
假设每个TweetID都有5个字节，我们需要多少内存来存储所有TweetID？
292B * 5 => 1460 GB
因此，我们的索引就像一个大型分布式哈希表，其中“key”是单词，“value”是包含该单词的所有tweet的tweetid列表。假设每条推文中平均有40个单词，由于我们不会为介词和其他小词（如“the”、“an”、“and”等）编制索引，我们假设每条推文中大约有15个单词需要编制索引。这意味着每个TweetID将在我们的索引中存储15次。因此，我们需要存储索引的总内存：
(1460 * 15) 2.5MB ~= 21 TB
假设一台高端服务器有144GB内存，我们需要152台这样的服务器来保存索引。我们可以基于两个标准对数据进行分片：
- 基于单词的切分：
在建立索引的同时，我们将迭代一条tweet的所有单词，并计算每个单词的哈希值，以找到将对其进行索引的服务器。要查找包含特定单词的所有tweet，我们必须只查询包含该单词的服务器。
这种方法有几个问题：
1.如果一个词变得热门怎么办？然后在保存该单词的服务器上会有很多查询。这种高负载将影响我们服务的性能。
2.随着时间的推移，与其他单词相比，一些单词最终可能会存储大量的tweetid，因此，在tweet增长的同时保持单词的均匀分布是相当棘手的。
要从这些情况中恢复，我们要么重新划分数据，要么使用一致性哈希。
- 基于tweet对象的切分：
存储时，我们将TweetID传递给我们的散列函数，以查找服务器并索引该服务器上tweet的所有单词。在查询特定单词时，我们必须查询所有服务器，每个服务器将返回一组TweetID。集中式服务器将聚合这些结果以将其返回给用户。
7.容错性
当索引服务器死亡时会发生什么？
- 我们可以为每台服务器提供一个辅助副本，如果主服务器死亡，它可以在故障切换后接管控制权。主服务器和辅助服务器都将具有相同的索引副本。
如果主服务器和辅助服务器同时死亡怎么办？
- 我们必须分配一个新服务器并在其上重建相同的索引。我们怎么能做到呢？我们不知道此服务器上保存了哪些文字/推文。如果我们使用“基于tweet对象的切分”，暴力解决方案将是迭代整个数据库，并使用我们的哈希函数过滤tweetid，以找出将存储在此服务器上的所有必需tweet。这将是低效的，而且在这段时间内也是如此
- 当服务器被重建时，我们将无法提供来自它的任何查询，因此丢失了一些用户应该看到的tweet。
我们如何有效地检索tweets和索引服务器之间的映射？
- 我们必须建立一个反向索引，将所有TweetID映射到他们的索引服务器。我们的索引生成器服务器可以保存此信息。我们需要构建一个哈希表，其中“key”是索引服务器编号，“value”是一个哈希集，包含保存在该索引服务器上的所有tweetid。注意，我们将所有tweetid保存在一个HashSet中；这将使我们能够从索引中快速添加/删除推文。因此，现在，每当索引服务器需要重建自身时，它可以简单地向索引构建器服务器请求它需要存储的所有tweet，然后获取这些tweet以构建索引。这种方法肯定会很快。我们还应该有一个用于容错的Index Builder服务器的副本。
8.隐藏物
为了处理热门推文，我们可以在数据库前面引入缓存。我们可以使用Memcached，它可以在内存中存储所有此类热门推文。应用服务器在访问后端数据库之前，可以快速检查缓存中是否有该tweet。根据客户端的使用模式，我们可以调整需要多少缓存服务器。对于缓存逐出策略，最近最少使用（LRU）似乎适合我们的系统。
9.负载平衡
我们可以在系统中的两个位置添加负载平衡层
1）在客户端和应用服务器之间，
2）在应用服务器和后端服务器之间。最初，可以采用简单的循环方法；在后端服务器之间平均分配传入请求的。此LB易于实现，不会引入任何开销。这种方法的另一个好处是LB将使死机服务器停止轮换，并停止向其发送任何流量。循环LB的一个问题是它不会考虑服务器负载。如果服务器过载或速度较慢，LB不会停止向该服务器发送新请求。为了解决这个问题，可以放置一个更智能的LB解决方案，定期向后端服务器查询负载，并根据负载调整流量。
10.排名
如果我们想按社交图距离、流行度、相关性等对搜索结果进行排名，那又如何？
让我们假设我们想根据受欢迎程度对tweet进行排名，比如一条tweet得到多少喜欢或评论等。在这种情况下，我们的排名算法可以计算一个“受欢迎程度数字”（基于喜欢的数量等），并将其与索引一起存储。在将结果返回到聚合器服务器之前，每个分区都可以根据这个流行数字对结果进行排序。聚合器服务器组合所有这些结果，根据受欢迎程度对它们进行排序，并将排名靠前的结果发送给用户。
参考资料
grok_system_design_interview.pdf
