Table of Contents

1. Algorithm
2. Review
   1. 简介
   2. 复习Paxos
      1. Paxos共识算法
      2. 实现状态机
      3. 动态Paxos
   3. 低成本Paxos
      1. 算法
      2. 低成本Paxos的正确性
   4. 结论
3. Tips
4. Share
   1. 概述
      1. 批量数据聚集和预处理流水
      2. 反转索引
      3. Earlybirds分片
      4. Earlybird根
      5. 面向未来

Algorithm

leetcode 673: https://leetcode.com/problems/number-of-longest-increasing-subsequence/

https://medium.com/@dreamume/leetcode-673-number-of-longest-increasing-subsequence-5d05faa85070

Review

Cheap Paxos

https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/web-dsn-submission.pdf

简介

状态机实现包含描述一个状态机系统把一系列客户命令作为输入，产生一系列状态和输出。状态机通过一系列服务器实现。它减少了实现分布式系统的问题，通过服务器来选择命令系列。系统可靠性需要所有的进程对系列中每个命令一致，尽管一些进程会故障。对异步系统，我们需要一致性被维持在任意数量非恶意（非拜占庭）故障情况下，当有足够的正常进程并能互相通讯的情况下就能保证进展。典型地Paxos算法是有效的、实用的算法满足这些要求。

考虑实现分布式系统的问题，如果只有一个进程工作，系统能取得进展。之前的算法，比如典型的Paxos，需要3个进程。需要两个进程来维持系统状态，但第3个进程能参与选择命令系列。下面的讨论显示第3个进程的必要性。假设系统只由两个进程实现，p和q，假设q故障了。则按照需求系统继续进展则p必须继续处理。假设p故障然后q修复了，则由q继续处理。但这明显是不可能的，因为q不知道当前系统的状态，因为它不知道p做了什么。于是有必要有第三个进程，例如，一个磁盘能访问p和q。

假设我们愿意弱化活跃需求，这样如果q故障然后在q修复之前p故障，则系统可暂停直到p修复。如果我们要求即使通讯失败也要保持一致性的话两个进程依然不行。一个进程不能区分另一个进程是进程故障还是通讯故障。如果每个进程继续操作系统则一致性丢失，系统不能允许每个进程因视另一个进程故障而独自运行。第3个进程是必要的。然而，第3个进程不需要参与选择命令系列。它需要替代另一个进程仅当p或q故障时，否则不做任何事。这样第3个进程可以是一个更小、更慢、成本更低的机器，或该进程主要处理其他任务。

本文建议存在一个方法实现一个容错系统，满足典型的Paxos一致性属性和弱活属性，仅使用两个主进程和一个辅助进程。本文描述简易的Paxos，该算法一般性的容忍F个进程故障及F + 1个主进程和F个辅助进程。该算法在一种“阿米巴”假设中维持活跃，工作主节点的子网络不会频繁变动。该假设描述如下。一个非故障进程维护系统状态的一些信息。当一个故障进程修复后，在有限时间内，它可以向其他进程重新请求来持有这些信息。有至少一个主进程有系统状态信息且F + 1个进程非故障并能互相通讯则可以维持活跃。一致性也能保持（假设无恶意故障）。

先前的两个相关工作貌似跟低成本Paxos有关。第一个是当主进程故障后用备用进程替代。经典的Paxos需要F + 1个工作进程来操作系统容错F个故障；另外的F个进程可以使用备份的。然而，跟低成本Paxos的辅助进程不同的是，备份需要有必要的计算能力来替代故障的主进程。第二个，使用动态量子算法维持数据库的多份拷贝。这些算法使见证进程不需要维护数据。然而，跟低成本Paxos不同的是，这些见证需要参与每一个操作。

两个适度的计算领域最新开发使低成本Paxos更加有用了。第一个，改进硬件和操作系统使计算机不易崩溃。弱活机制保证低成本Paxos依然能提供有效的可靠性。第二，广泛使用的计算机使它更像一个组织，有更多的机器循环利用来实现辅助进程。

可能有人认为低成本的计算机使低成本Paxos没有太大吸引力。然而，我们观察到跟40年前不同，人们不愿意使用额外的硬件来使系统更简单可靠，即使硬件变得非常便宜。

如下章节将审查Paxos，第3章节将描述低成本Paxos。再后面是结论。

复习Paxos

Paxos算法实现分布式状态机由lamport论文引入。我们考虑两个版本的Paxos。在基本版本中，我们命名为静态Paxos，服务器集合是固定的。另一个我们称为动态Paxos，使用状态机命令改变服务器集合。我们先考虑静态Paxos。

Paxos共识算法

为实现状态机式的分布式系统，系统的进程需要选择一系列命令。这将通过执行一系列共识算法的实例来实现。第i个实例选择序列中第i个命令。我们现在复习一下Paxos共识算法。

共识算法的目标是一系列进程同意某个值。这样方便处理共识问题为3类代理：提议者提议值，接受者选择一个提议值，学习者必须学习被选中的值。一个进程可作为多个代理。共识算法必须满足如下安全属性：

1. 不平凡性，只有提议值能被选中
2. 一致性，只有一个值能被选中
3. 保守性，只有选中的值能被学习

Paxos假设基于选择领导，安全性在没有领导或多个领导时也要被保证。但需要唯一的领导者来保证进展。提议者发送它们的提议给领导者。

共识算法假设预定义接受者集合为法定人数。对法定人数唯一的要求是任何两个法定人数必须有一个共同的接受者。Paxos同样假设一系列投票活动号，其值可以为自然数。投票活动号在潜在的领导者间分区，每个领导者有自己的不相交投票活动号集合。

共识算法有两个阶段，每阶段有两个子阶段。算法行为描述如下。算法在学习者和接受者之间发送消息，因为相同的进程可能扮演多个角色，它可以发送消息给自己。

1. 阶段1a(l, b)，领导者l选择从它的投票活动号码中选择一个号b，发送<”1a”, b>消息给接受者
2. 阶段1b(a, b)，当接受者a接收到一个从领导者l发送过来的<”1a”, b>消息，如果它没有接收到任何投票活动号大于b的消息，则它回应领导者l一个<”1b”, b, …>消息。如果a收到了大于投票活动号b的消息，则它发送一个回复给领导者l表示它将忽略<”1a”, b>消息（一旦收到这个消息，领导者l将执行一个1a(l, b’)阶段行为，其b’ > b，如果它依然相信它自己是一个领导者的话）。

3. 阶段2a(l, b)，如果领导者l接收到法定人数的接收者发送的<”1b”, b, …>消息，则它发送<”2a”, b, v>消息给接受者，根据”1b”消息的内容分别为：

   1. 值v被”1b”消息决定，或者
   2. 领导者l从收到的提议里任意选择一个值v

   该行为不能被不同的v值执行两次（b相同）

4. 阶段2b(a, b, v)，如果接受者a接收到一个<”2a”, b, v>消息，并且还没有接受到任何投票活动号大于b的消息，则它将发送一个<”2b”, b, v>消息给每个学习者
5. 学习(r, v, b)，如果学习者r收到法定人数接受者的<”2b”, b, v>消息，则它将学习该被选中的v值

在正常执行时，上述行为开始于领导者的阶段1a。然而，进程可能故障，消息可能丢失或乱序，一些进程可能同时认为它们是领导者，导致”1a”和”2a”消息从几个不同的投票活动中同时发出。尽管如此，算法维持它的安全属性，不平凡性，一致性和保守性（我们假设进程为非拜占庭故障，不会执行异常行为）。如果有一个工作进程相信它是领导者，并收到了一个提议，并能跟法定人数的接受者通讯，最终某个值会被选中。任意学习者只要能跟法定人数的接受者通讯则能学习到选中值。

我们允许故障进程重启，如果该进程故障但有稳定的存储。进程需要在存储中维护如下的信息：一个接受者必须保持两个投票活动号和一个提议值，领导者保持一个活动号（它执行阶段2a行为时的最大投票活动号）。

如描述所示，算法永不终止。领导者可以在任意时刻用一个新的投票活动号执行阶段1a行为。在应用程序中，某些时刻会有足够多的进程学习到选中值，之后进程可以遗忘所有算法的这些实例，移除存储中有关它的所有信息。

最后，我们有以下观察：

1. 我们可以以额外的消息延迟为代价保存消息，让一个不同的学习者当找到选中值时通知其他的学习者。发送”2b”消息的接受者只发给这些不同的学习者。在多数应用程序中，领导者的角色和不同的学习者执行在相同的进程。
2. 领导者可以只发送它的”1a”和”2a”消息给法定人数的接受者。当所有法定人数的接受者正常工作并能跟领导者和学习者通讯时，不需要不是法定人数的接受者做任何事。
3. 接受者不关心何值被选中。他们只是简单地响应”1a”和”2a”消息，并存储确保即使故障，只有一个值被选中。然而，如果接受者学习了选中值，它存储该值并删除之前存储的任何信息。如果接受者之后收到”1a”或”2a”消息，而不是执行它的阶段1b或阶段2b行为，它可以简单地通知领导者该选中值
4. 领导者可以在”2a”消息中发送一个v值的hash值给一些接受者。学习者收到法定人数的接受者发送的”2b”消息包含v值或其hash值时可以学习到该选中的v值，需要至少其中一个消息包含v值。然而，领导者可能收到”1b”消息并告诉它阶段2a行为中要用的v值的hash值但却不知道真正的v值。如果这种情况发生，领导者不能执行它的阶段2a行为直到它跟一些进程通讯并了解了v值。

实现状态机

在状态机方案中，服务器集合执行客户端提交的执行命令。简单来说，我们假设每个服务器存储选择的整个状态机命令序列。在很多应用程序中，服务器只保存最近的状态机状态的检查点和该检查点之后的命令。

在传统的Paxos算法中，客户机为提议者，每个服务器作为接受者，学习者和共识算法实例的潜在领导者。领导者接收客户机命令，给每个分配一个号，尝试获得被第i个Paxos共识算法选择的第i个命令。

为理解静态Paxos如何工作，假设当领导者故障时系统已工作一段时间。一个新的服务器l被选择为领导者。因为l是一个学习者，它应该知道大多数已被选择的命令。假设它知道命令1 - 134，138和139，即被共识算法实例1 - 134，138和139选择的命令（这样的断层是可能的因为多个共识算法实例能并行执行）。服务器l选择一个投票活动号b，它相信该号比之前的领导者的任意投票活动号大（选举算法也能被用来选择b）。它然后同时执行实例135 - 137的阶段1a(b, l)和所有共识算法大于139的实例，发送”1a”消息给所有服务器（一些消息发送给自己，因为领导者是从这些服务器中选择的）。它能在单个物理消息中发送无数个虚拟消息。

每个服务器同时执行阶段1b行为响应这些虚拟的”1a”消息，发送无穷多个虚拟”1b”消息给l。因为这些”1b”消息包含那些已被执行的实例行为，这些虚拟消息将只包含有限的信息填入实际的单个真实消息中。如果一个服务器知道了已被一些实例选中的命令，它将响应被选中的命令而不是该实例的”1b”消息。

假设，对这些消息来说，l学习到：

• 实例135选中的命令（一些服务器发送的替代实例135”1b”的消息）
• 它需要使用的命令v_137和v_140，作为实例137和140的阶段2a(l, b)行为的v值
• 实例136和所有大于140的实例，它使用在阶段2a(l, b)行为中选择使用的任意提议值v

领导者l然后做以下处理：

• 对实例137和140执行阶段2a(l, b)行为，使用接收到的”1b”消息指定的命令v_137和v_140
• 对实例136执行阶段2a(l, b)行为，使用命令v指定一个no-op状态机命令不进行任何操作
• 确保所有的服务器知道命令1-135, 138和139

如果多数服务器在工作，他们将执行实例136，137和140的阶段2b行为，所有服务器将学习共识算法所有1-140实例选中的命令。然而，在这些发生前，领导者l可以重置正常的操作。它设置它接收到的第一个客户端命令一个141号，执行实例141的阶段2a(l, b)，命令为值v。分配142给另一个客户端命令并执行阶段2a(l, b)，命令为值v，等等。

因为每个服务器都是一个学习者，学习一系列选中的命令。在大多数应用程序中，领导者作为一个不一样的学习者发送”2b”消息。一旦服务器学习到第i个命令，它会删除为第i个共识协议存储的其他所有信息。

当一个故障的服务器修复后，它需要追赶以使其知道所有被选中过的命令。理论上，新修复的服务器可以从一些工作服务器上获得信息。如果一个服务器只维护最近的命令和一个检查点状态，则修复服务器必须更新它的检测点。如果状态机维护一个巨大的状态，则应该只发送改变的那部分状态给修复服务器。

动态Paxos

我们描述的静态Paxos，接受者集合和法定人数是固定的，系统在有F个进程故障的情况下需要2F + 1个服务器来维持正常工作。例如，对静态Paxos，它让7台服务器容错3台故障。在很多系统中，达成想要的容错度最好的办法是重新配置系统用备用服务器替换故障服务器。当重新配置时，系统使用3个活动服务器和两个后备可以容错3个故障，故障服务器在另一个故障发生前可以用备用服务器替换故障服务器。重配置因此允许更少的服务器容错相同总数的故障，虽然不是同是故障的相同数（在大多数系统中，同时故障远比顺序故障少见）。

在动态Paxos中，接受者集合和法定人数由状态机决定。状态机命令可执行重配置。为解释如何做，先设状态k为执行命令k后状态机状态。对k <= 0，定义状态k为初始化状态。对一些固定常量α，我们设共识算法实例i的接受者和法定人数由状态ii - α决定。在执行实例i的任何行为之前，领导者会一直等待直到它知道了状态i - α。即领导者等待直到它知道命令号i - α的所有命令之后它才知它应该发送它的”2a”消息给Paxos共识算法实例i的哪些接受者。

一个简单例子，考虑一个系统有固定集合S个进程可作为服务器。设服务器集合当前执行的系统为G，法定人数包含G中多数进程。假设我们想要一个进程被定义为故障或G中多数进程认为其已修复。状态机的状态将包含布尔数组good，good[p, q]表示是否进程p相信进程q为非故障，p，q ∈ S。进程r会提供一个状态机命令改变good[r, s]值，当它相信进程s故障或被修复。这样的命令会设置good数组新值good’，且它会设置G的新值G’相当于所有进程q ∈ S，对多数进程p ∈ G，good’[p, q]为真（i命令引起的对G的改变将影响Pasox共识算法i + α开始的实例）。

实际上，决定什么时候重配置系统不是容易的事。替换未故障的服务器将引起系统服务器耗尽；但不替换故障的服务器将降低系统对更多故障的容忍性。我们可以使用一个更复杂的算法，来处理特殊的系统。这些算法可通过状态机实现。

低成本Paxos

算法

我们现在开发低成本Paxos作为动态Paxos的实例。我们推荐系统用F + 1个主进程和F个辅助进程。主进程作为分布式状态机实现里的服务器。辅助进程只在主进程故障时执行操作，主进程恢复后继续执行系统。

低成本Paxos的关键是观察2。在Paxos共识算法正常操作中，领导者只发送”2a”消息。但因观察2，这些消息需要发送给接受者法定人数，且只有它们会响应。因此，实现低成本Paxos，我们使用动态paxos来配置系统这样所有工作的主进程集合形成法定人数。这些进程持续工作，执行系统。如果其中一个故障，则只包含主进程的法定人数不能再成功选择命令。一个不同的法定人数，包含一个或多个辅助进程，开始(i)完成当故障发生时的Paxos共识算法实例的执行，且(ii)提议并选择必要的状态机命令来重配置系统。重配置移除故障的进程并修改法定人数集合，这样剩余的主进程形成法定人数。这些主进程可以重新执行系统，而辅助进程又变得空闲。

当所有进程的集合G作为接受者被状态机状态终止时，低成本Paxos使用动态Paxos。设M为包含G中所有主进程的子集，我们想要M成为法定人数。因法定人数的唯一需求是任意两个法定人数交集不为空，我们可以使M为法定人数且让其他法定人数包含G中多数进程且至少一个进程在M中（如果M只包含一个进程p，则法定人数可包含含p的任意集合）。我们要求G包含至少一个主进程 - 该条件满足重配置算法，因所有主进程故障意味着没有法定人数的工作进程，这样无状态机命令会被选择直到一个主进程修复（重配置算法不需要移除G中最后一个主工作进程）。

在正常操作中，M的进程执行Paxos共识算法实例的阶段2来选择状态机命令序列。它们可执行重配置命令来添加修复的主服务器到G和M。然而，如果一个主进程故障，则工作的法定人数不在只包含主进程。如下步骤会执行。

1. 如果故障进程为领导者，则一个新的领导者会在M中仍然正常工作的进程中被选举出来
2. 领导者会询问其他工作主进程来学习其知道的所有已选择的命令
3. 当主进程故障期间，领导者完成进展中的任何Paxos共识算法实例的执行，使用包含一个或多个辅助进程的法定人数。如果新领导者在步骤1中被选举出来，它将如2.2章节描述的那样对相关的共识算法实例选择一个新的投票活动号并初始化阶段1。如果老的领导者仍在工作，它将发送与主进程相同的”2a”消息给辅助进程
4. 在标准的动态Paxos中，工作进程提议和选择状态机命令序列来重配置系统这样故障的主进程从接受者集合G中移除
5. 领导者提议和获取已选中的状态机命令序列。设j为这些命令最后的命令号

步骤5之后，在步骤4选择的新接受者集合G将生效。意味着G中的主进程集合M组成了法定人数，这样它们可重新执行系统。然而，Paxos共识算法从故障中恢复的能力需要等待接受者在持久存储中维护好一些信息。在辅助进程需要的存储完成之前，它们需要暂时忘掉步骤3-5中保存的信息，继续参与共识算法的执行。它们会这样做直到工作主进程学习到这些实例的选中命令之后。因此，在系统重置正常执行之前，如下的步骤也会执行：

1. 领导者确保新的M中所有进程知道从命令号j（定义在步骤5）开始的所有命令
2. 领导者指导所有的辅助进程记录实例1到j的共识算法选择的命令到存储中，这些进程对任意其他实例不执行任何行为（它们不需要记录这些命令）。辅助进程然后从存储中擦除有关第j个共识算法实例的任何信息。

这些步骤描述了当主进程故障时会发生什么。一个完整的算法必须也能处理异常，例如，如果这些步骤在执行过程中领导者故障，或两个进程都认为自己是领导者且对哪些进程故障有不同的看法。但在这些步骤中执行的行为实现了动态Paxos。（步骤2到6简单地传播被选中命令的知识）精确定义这些行为跟普通的Paxos是一样的。唯一区别是一个辅助进程可能不能响应”1a”或”2a”消息，因它在步骤7中擦除了必要的信息。在这种情况下它必须忽略这些消息而不是像观察3那样响应这些命令（它可能报告给领导者为什么它忽略该消息，建议领导者询问一个主进程什么命令已被选中）。

辅助进程只在主进程故障时需要，这时它们需要参与一小部分Paxos共识算法实例的执行。共识算法需要它们把提议命令写入存储中。在一些应用程序中，这些命令可能非常大，写入存储可能花费时间较长。如果这样，我们可应用观察4和辅助进程接收并存储提议命令的hash。因每个法定人数包含一个主进程，一个学习者从法定人数那接收到”2b”消息必须接收至少一个包含了该命令而不是hash。然而，我们需要防止观察4提到的问题，进度被阻塞因领导者仅知道值的hash而不知道值本身。可通过领导者延迟发送带v值的hash的”2a”消息到任意辅助进程直到所有工作主进程了解了接收的”2a”消息包含v值。

在一般的动态Paxos中，我们不提交任何决定进程故障或修复的特殊算法。因重配置由状态机命令执行，任何算法都可以使用。实际上，低成本Paxos算法在决定是否一个主进程故障的问题上跟传统的动态Paxos算法很不一样。动态Paxos算法实现中，任意接受者多数集合组成一个法定人数，这样系统在服务器故障情况下能持续进展。在这种情况下，系统能够等待确保服务器确认故障后再重新配置。但低成本Paxos在主进程故障时会立即停止进展。更激进地是当故障时移除进程。虽然这些不同影响决定进程是否工作的细节，但它不改变基本的状态机算法。

我们假设所有进程集合（主进程加辅助进程）是固定的。重配置可用来改变进程集合。我们重配置接收者集合来移除故障主进程和添加已修复的主进程。额外的容错能力可通过用空闲辅助进程替换故障的辅助进程获得，跟普通的动态Paxos一样。重配置只能由主进程通过执行状态机命令的形式执行；辅助进程只需要定期通知主进程它仍然在工作状态。一个新安装的辅助进程需要在存储中记录它还没有执行Paxos共识算法实例的行为。

辅助进程作为一个接收者，而不是学习者，它不知道什么命令被选中。因此，如果重配置改变辅助进程集合，辅助进程不知道是否它是一个接收者。如观察O3所示，接收者只是简单地响应”1a”或”2a”消息。只有领导者和学习者（主进程），需要知道接收者集合和法定人数。

低成本Paxos的正确性

低成本Paxos使用Paxos共识算法来选择命令。它的安全属性跟共识算法的安全属性一致。特别地，两个不同的服务器不能拒绝对任意i轮中的第i个命令的值。

低成本Paxos的活跃属性也跟Paxos共识算法一致。然而，低成本Paxos实现了动态Paxos，活跃属性依赖于重配置如何精确地执行。例如，当重配置选择故障或不存在的进程作为接收者集合时，系统不会有进展。甚至，简单地能选择新命令不能确保进展。为能够执行第i个命令，服务器需要知道该i个命令及之前的所有命令。例如，当命令1被选中，但没有工作服务器知道该值时系统不能有进展。低成本Paxos还有额外的复杂性，辅助进程会遗忘普通Paxos用来从某个故障恢复所需要的信息。

为描述低成本Paxos满足的活跃属性，我们需要一些定义。我们称非故障进程集合为当它们所有都能工作且能在可接受的一段时间内互相通讯。定义命令号i为被记录的仅当一些辅助进程存储了i被选中这个信息（辅助进程在重配置过程的第7个步骤中记录了它，对j >= i，所有从j开始的命令已被选中）。命令号i为活跃的，仅当i还没有被记录，但共识算法的实例i已经发送了”2a”消息。我们定义主进程已更新仅当它知道了所有被记录的命令（如果辅助进程仅存储hash值，则如果一个主进程p已更新，它必须也要满足如下条件：对每个活跃命令i和每个共识算法实例i发送给辅助进程的”2a”消息，p必须已接收到它对应的”2a”消息）。

我们现在可以说明低成本Paxos满足活跃属性。在重配置过程的步骤6中，假设一些方法广播了选中命令的信息。我们假设这些信息在主进程中被交换，如果主进程p和q，p知道一个命令，{p, q}集合正常运行足够长时间，则q将学习到该命令。低成本Paxos满足的活跃属性可如下描述：

如果有非故障进程集合包含一个领导者，至少一个已更新的主进程，则对所有活跃命令号i，共识算法的实例i的法定人数可使系统保持进展。

我们可以认为非故障主进程集合为一种变形虫，当一个进程故障时它会撤出一只伪脚，当一个进程修复时添加一只。它需要时间来了解选中的命令信息来形成一个新的伪脚。如果变形虫移动太快，信息会被丢失因为在形成新的已修复进程之前进程可能故障。假设非故障进程总数（主加上辅助）很大，低成本Paxos保证系统将持续保持进展就像变形虫移动很缓慢以使信息不会丢失。

结论

低成本Paxos是Paxos算法的一种变种，对F + 1个主进程和F个辅助进程可以容忍F个故障且保持进展。跟之前的系统中使用的空闲进程不同，我们的辅助进程不需要做任何事除了在主进程故障的一个短暂时间。辅助进程因此不需要像主进程那样的强大处理能力和存储。使用辅助进程，低成本Paxos能使系统获得比使用相同主进程的其他算法更大的容错能力。

Tips

• 把精力放在更重要的事情上，提高效率
• 对知识结构进行分层，区别处理，并要形成体系化
• 对相关知识要形成深刻印象，不用刻意记忆也不会遗忘，用时自然会想起，最好（看一些经典的书的感受）
• 有些知识点不需记忆，有印象用时能快速搜索到即可

Share

https://blog.twitter.com/engineering/en_us/a/2014/building-a-complete-tweet-index.html

构建一个完整的tweet索引

目的：通过案例熟悉了解系统设计

今天，我们荣幸地宣布Twitter已索引自2006年以来的Tweet条目。

第一个Tweet条目还在八年以前，每天数千亿条Tweet描述了人们的经历和主要的历史事件。我们的搜索引擎在实时新闻和事件查询中表现优异，我们的搜索索引基础设施能对应上近期的强抽象。但我们的长期目标是让用户能够搜索发布的每一条Tweet。

新的基础设施提供复杂的搜索结果，整个TV和体育赛季、会议(#TEDGlobal)、工业讨论(#MobilePayments)，地点，商业和长期活跃的tashtag话题会话，比如日本地震，电子2012，苏格兰裁决，香港，弗格森等等。这些改变将在近期提供给用户。

在本编文章中，我们描述我们如何构建一个搜索服务有效地索引近万亿文档并服务查询平均延迟在100ms以内。

设计中最重要的因素如下：

• 模块化：Twitter已有一个实时索引（一个反转索引包含一个星期的Tweet）。我们共享代码并在这两种索引间测试，这样可以在更少的时间内创建一个清洁的系统。
• 可扩展性：全索引比实时索引大100倍，并已每周数十亿Tweet条目的速度增长。我们固定大小的实时索引集群扩展比较困难；增加容量需要重新分区并相应的操作成本。我们需要一个系统能平滑扩展。
• 有效的成本：我们的实时索引全存储在内存中来达到低延迟和快速更新。然而，使用相同的内存技术对全索引来说过于昂贵
• 简单的接口：为扩展性分区不可避免。但我们想要一个简单的接口隐藏分区细节，这样内部客户可把集群看作一个节点
• 迭代发展：索引每个Tweet的目标不可能在一个季度中达到。全索引基于之前的基础项目。在2012年，我们构建了一个大约二十亿top tweet的小历史索引，开发了一个离线数据簇和预处理流水线。2013年，我们因为规模扩展了索引，评估并调节SSD性能。2014年，我们构建了多层的全索引架构，主要工作在扩展性和操作性上

概述

系统包含4个主要部分：一个批量数据聚集和预处理流水线；一个反转索引构建器；Earlybird分片和Earlybird根。

批量数据聚集和预处理流水

实时索引的流水线每次处理一个个人的Tweets。相反的是，全索引使用批量处理流水线，每个批量是一天的Tweets。我们想要我们的离线批量处理任务与我们的实时流水线共享尽量多的代码，并且保持高效。

为此，我们打包相关实时代码进入Pig用户定义函数，这样我们可以在Pig任务中重使用它，并创建一个Hadoop任务的流水线来聚集数据和预处理Tweets。

该流水线如下：

• 吸引力聚集器：统计某天每个Tweet的吸引度。这些统计将作为给Tweet打分的输入
• 聚集器：按Tweet ID把多个数据源集合到一起
• 吸收器：执行不同类型的预处理 - 语言识别，token化，文字特征萃取，URL解决方案及更多
• 得分：基于特征的吸收萃取计算得分。对更小的历史索引，该得分决定哪个Tweet将被选中进索引
• 分区：用hash算法分割数据为更小的簇。最终的输出是存储到HDFS

该流水线设计为运行一天的Tweets。我们建立该流水线来增量运行每天的处理数据。有两个好处。它允许我们用新数据增量更新索引而不需要频繁完全重建。而每天的处理又完全独立，流水线可以在Hadoop上大量并行。这允许我们定期有效重建全索引（添加新的索引字段或改变token化）。

反转索引

每日数据聚集和预处理工作输出每一个Tweet一个记录。输出已token化，但未反转。所以我们下一步是创建一个单线程，状态无关的反转索引构建器，运行在Mesos上。

反转索引构建器包含如下组件：

1. 段分区：从相同分区分组多批量的日Tweet预处理数据到段
2. 段索引：反转每段的每条Tweet，构建反转索引并存储该索引到HDFS

这些反转索引构建器的优美之处在于它们非常简单。它们是单线程且状态无关，这些小的构建器可以在Mesos上大量并行（我们已经运行超过一千个并行构建器）。这些反转索引构建器可以通过ZooKeeper的锁相互协调，确保两个构建器不会构建相同的段。通过这种实现，我们在两天内重新构建了大约5百亿条Tweet（我们的瓶颈在Haddop命名节点）。

Earlybirds分片

反转索引构建器生成数百个反转索引段。这些段被分布到机器中称为Earlybird。因每个Earlybird机器服务整个Tweet素材的一小部分，我们不得不引入分片。

过去，我们使用hash分布段到不同的主机。这种方式对实时索引处理得很好，但仍需要一个大常量时间。然而，我们的全索引集群需要持续不断地增长。

对于简单的hash分区，扩展集群需要很多操作上的工作 - 随着hash分区数量的增长数据需要被打散。因此，我们创建了2维分区方案来分布索引段到服务的Earlybird。使用这种两维分片，我们可扩展我们的集群而不需要修改现存集群里的主机：

1. 时间分片：Tweet素材首先分割为多个时间层
2. Hash分区：每个时间层，数据根据hash函数划分为分区
3. Earlybird：在每个hash分区，数据进一步划分为簇称为段。段根据适配到每个Earlybird机器的数量组合起来
4. 节点：每个Earlybird机器被复制来增加服务能力和弹性

该设置使集群扩展简单：

1. 基于时间增长数据容量，我们将添加时间层。现存的时间层仍然不变。这样允许我们扩展集群
2. 增长服务能力（QPS），我们只要添加更多节点

这个设置允许我们避免增加hash分区，增加分区在集群在线状态下打散数据比较麻烦。

每个集群大数据的Earlybird机器传输数据成本较大。我们通过如下方法减少集群大小：

1. 压缩更多的段到每个Earlybird机器（减少hash分区数）
2. 增加每个Earlybird QPS（减少节点）

为了压缩更多的段到每个Earlybird，我们需要找到不同的存储媒介。内存太昂贵。插入大量内存到机器受DIMM插槽的限制。SSD比内存要便宜很多。SSD比普通主轴磁盘能提供更高的读写性能。

然而SSD比RAM还是要慢很多，从RAM切换到SSD，我们的Earlybird QPS容量收到显著影响。为增加服务容量，我们做了很多优化比如修改内核参数优化SSD性能，压缩多个DocValues段来减少SSD随机访问，直接加载经常访问段到进程等。这些优化细节不在本博客里描述。

Earlybird根

2维分片处理集群伸缩性和扩展性。然而，我们不想要API客户端不得不打散从hash分区和时间层的聚合来服务单个查询。为保持客户端API的简化，我们引入根来抽象全索引中层和分区的细节。

根执行两层的打散聚合如下图所示，合并搜索结果并统计。简单的API结果，它使客户端只链接一个单端。这种两层合并处理允许我们执行额外的优化，比如避免跟搜索查询无关的时间层的前向查询请求。

面向未来

现在，全索引的完全结果出现在Twitter移动客户端搜索结果的所有tab中。过一段时间，你会发现本次索引的更多的Tweets出现。

全索引是主要的架构投资及Twitter搜索和发现体验的持续改进，依然有更多激动地工作要做，比如内存优化。