将搜索索引延迟缩短至一秒

搜索系统的关键指标之一是索引延迟，即新信息在搜索索引中可用所需的时间。此度量很重要，因为它决定了新结果显示的速度。并不是所有的搜索系统都需要快速更新内容。例如，在仓库库存系统中，每天更新一次搜索索引可能是可以接受的。就像Twitter--人们不断地在寻找“发生了什么”的答案--实时搜索是必须的。

直到2019年年中，Twitter搜索系统的索引延迟都在15秒左右。它足够快，可以为基于相关性的产品功能提供动力，比如根据相关性发布推文的排名主页时间线(Rating Home Timeline)。由于确定一条推文的相关性是基于其参与度等因素，因此即时索引的需要较少。然而，需要低得多的索引延迟的用例不能由我们的搜索基础设施提供支持。例如，我们不能使用相同的搜索系统来检索个人个人资料页面的Twets，在该页面中，人们通常希望看到他们的Tweet在发布时出现。

创建推文时，某些字段(与每条推文关联的信息位)不可用。例如，完全解析的网址通常比缩短的网址(如http://t.co/foo.)提供更好的排名信号。然而，解析新的URL需要时间，而且我们的旧系统要求我们同时为Tweet的所有字段建立索引，因此我们需要等待所有这些延迟的字段变为可用。

Twitter应用程序中的大多数功能会优先处理最新的相关Tweet。因此，我们按照创建Tweet的时间对索引进行排序。如果我们的系统接收到严格有序的事件，这将很容易做到。但是，因为我们的搜索系统与Tweet创建分离，所以搜索系统不一定按时间顺序接收Tweet。为了克服这一限制，我们在摄取管道中添加了一个缓冲区，该缓冲区将所有传入的Tweet存储几秒钟，并在将它们发送到索引系统之前严格按照创建时间的递增顺序对它们进行排序。

克服这些限制需要对我们的摄取管道和索引系统进行重大改变，但我们相信这些结果是值得的。tweet现在可以在创建后一秒内进行搜索，这使得我们可以支持具有严格实时要求的产品功能，例如实时对话或个人资料页面。让我们仔细看看我们是如何做到这一点的。

几乎所有搜索系统的核心都是一种称为倒排索引的数据结构。倒排索引旨在快速回答诸如哪些文档中包含单词cat？"；这样的问题。它通过保存从词条到帖子列表的映射来做到这一点。术语通常是一个单词，但有时也是一个连接词、短语或数字。公告列表是包含术语的文档标识符(或文档ID)的列表。发布列表通常包括额外的信息，如术语在文档中出现的位置，或者用于提高排名算法相关性的有效负载。1个。

Twitter的搜索系统每秒处理数十万个查询，其中大多数涉及搜索数千个项目的帖子列表，这使得我们在帖子列表中迭代的速度成为有效服务查询的关键因素。例如，考虑有多少Tweet包含单词“the”。

我们使用Lucene作为我们的核心索引技术。在标准Lucene中，索引被细分为称为段的块，文档ID是Java整数。为特定片段中索引的第一个文档分配ID 0，并按顺序分配新的文档ID。在搜索段时，搜索从段中最低的文档ID开始，然后继续到段中的最高ID。

为了支持我们首先搜索最新Tweet的要求，我们与标准Lucene不同，从高到低分配文档ID：一个片段中的第一个文档被分配一个最大ID(取决于我们希望Lucene片段有多大)，每个新文档获得一个较小的文档ID。这允许我们遍历文档，这样我们就可以首先检索最新的Tweet，并在检查客户指定的命中数之后终止查询。这一决定对于减少评估搜索查询所需的时间至关重要，因此对于让我们扩展到极高的请求率也是至关重要的。

当我们使用传入Tweet的排序流时，很容易分配文档ID：片段中的第一个Tweet将获得片段大小减1的ID，第二个Tweet将获得片段大小减2的ID，依此类推，直到我们获得文档ID 0。但是，如果在创建Tweet时未对传入流进行排序，则此文档ID分配方案不起作用。为了消除排序带来的延迟，我们需要想出一个新的方案。

在新的文档ID分配方案中，根据创建时间为每个Tweet分配一个文档ID。我们需要将文档ID放入31位空间，因为Lucene使用正Java整数作为文档ID。每个文档ID在一个段内都是唯一的，我们的段通常在大约12小时内是可写的。我们决定分配27位来存储毫秒粒度的时间戳，这足以让一个数据段持续37小时多一点。我们使用最后四位作为具有相同时间戳的Tweet数量的计数器。这意味着如果我们收到超过2 4(16)条具有相同毫秒时间戳的Tweet，那么其中一些将被分配一个稍微有些不正确的文档ID。在实践中，这种情况极为罕见，我们认为这种缺点是可以接受的，因为当Tweet延迟超过15秒时，我们经常会在旧系统中遇到类似的情况，这也会导致分配无序的文档ID。

在过去的八年里，Twitter的搜索系统使用仅限预端的展开链表作为支持张贴列表的数据结构。这使我们避免了为每个值存储指针的开销，并且极大地提高了遍历张贴列表的速度，因为它是缓存友好的。(展开的链表是每个链接有多个值的链表-维基百科上有很好的描述。)。

在我们的旧实现中，链表一开始只有一个值，每次列表需要增长时，我们都会分配指数级更大的节点。

搜索器线程将从链表中最近添加的项开始，并跟随指针直到到达列表的末尾。写入者只会将新项目添加到列表的开头，方法是在现有数组中添加新帖子，或者创建新块并将新帖子添加到新块。在添加项目并正确设置链接之后，编写器将自动更新其指向链表新头部的指针。搜索者将看到新指针或旧指针，但绝不会看到无效指针。

该列表是预置的，因此我们不需要在内部重写指针，还因为将项目添加到一组帖子的中间需要复制、减慢写入者的速度并需要复杂的簿记(如跟踪哪些块是最新的、哪些块已过时但仍被搜索者使用，以及哪些块可以安全地用于新的帖子)。它还可以很好地与我们的旧文档ID分配方案配合使用，因为它保证了公告列表始终按文档ID排序。

这些链表在不使用任何锁的情况下支持单个编写器和许多搜索器，这对我们的系统至关重要：我们的每个CPU核心都有一个搜索器，每个服务器有几十个核，每次需要添加新文档时锁定所有搜索器的成本将高得令人望而却步。前缀到链表也非常快(发布列表大小为O(1))，因为它只需要跟随单个指针、分配新元素和更新指针。

你可以在Twitter上找到更多关于我们在Earlybird：实时搜索中使用的展开链表方法的详细信息。

链表数据结构多年来一直很好地服务于我们的系统：它很容易理解，而且非常高效。不幸的是，该方案只有在传入的Twets被严格排序的情况下才有效，因为您不能将新文档插入到列表的中间。

为了支持这一新需求，我们使用了一种新的数据结构：跳过列表。跳过列表支持O(Logn)查找和插入到排序的集合或映射中，并且相对容易适应以支持并发性。

跳过列表有多个级别，每个级别都将元素存储在链接列表中。最低级别包含所有元素，下一个最高级别包含这些元素的一部分，依此类推，直到我们达到只包含几个元素的最高级别。如果元素存储在级别N，则它也存储在所有级别1、2、…。较高级别中的每个元素都包含到较低级别中的等效元素的链接。要查找给定的元素，您可以从最高级别开始，沿着该链表阅读，直到找到一个大于您要查找的元素的元素。此时，您将下降一级，并开始检查填充更密集的链表中的元素。

当我们添加元素时，我们总是将其添加到最底层。如果我们将元素添加到N级，我们会随机决定以20%的概率将元素添加到N+1级，然后递归地继续，直到我们不再随机决定将元素添加到下一个更高的级别。这为我们在每个更高级别提供了五分之一的元素。我们发现1：5的比率是内存使用和速度之间的一个很好的折衷。

我们可以在单个平面数组中实现跳跃列表，其中每个“指针”只是跳跃列表数组的索引，如下所示：

注意，跳过列表的每个级别都以特殊的“级别结束”值结束，该值通知搜索过程在该级别的跳过列表中没有更高的值。

我们的跳跃列表实现有几个值得注意的优化，以减少每个张贴列表中使用的内存量，提高搜索和索引速度，并支持并发读写。

首先，我们的跳过列表总是将元素添加到分配池的末尾。我们使用它来实现文档原子性，如下所述。当添加新元素时，我们首先在池的末尾分配元素，然后更新跳过列表最低级别的指针以包括该项目。通常，这是跳过列表的“头”指针，但如果它的文档ID比跳过列表的头大，我们将进一步向下遍历跳过列表，并将帖子插入到正确的位置。我们有时还会重写跳过列表结构的较高级别中的指针。我们将该值添加到跳过列表的第二级的可能性为五分之一，将其添加到第三级的可能性为25%，依此类推。这就是我们如何确保每个级别具有其下级别密度的五分之一，以及我们如何实现对数访问时间。

其次，当我们在跳过列表中搜索元素时，我们跟踪跳过列表级别的下降，并将其保存为搜索手指。然后，如果我们稍后需要查找文档ID大于或等于给定值的下一张贴子(假设我们要查找的值高于找到的原始值)，我们可以从手指给出的指针开始搜索。这将我们的查找时间从O(Logn)(其中n是发布列表中的元素数量)更改为O(Logd)，其中d是发布列表中介于第一个值和第二个值之间的元素数量。这一点很关键，因为搜索引擎中最常见和最昂贵的查询之一是合取，这在很大程度上依赖于此操作。

第三，我们的搜索系统中的许多数据结构将它们的所有数据存储在一个原语数组中，以消除JVM存储指向对象的指针所带来的开销，并避免让许多活动对象在老一代中存活的成本，这可能会使垃圾收集周期花费更多的时间。这使得编写数据结构更具挑战性，因为数组中的每个值都是无类型的-它可能是指针、位置、有效负载，或者在竞争条件下完全乱码。使用另一种语言的类或结构等编程语言级别的功能将使理解和修改这些数据结构变得容易得多，因此我们热切期待OpenJDK的项目Valhara的结果。

第四，我们只为跳过列表的每个级别分配一个指针。在典型的跳跃列表中，节点将具有一个值、指向列表中下一个最大元素的指针和指向跳跃列表较低级别的指针。这意味着分配到第二级的新值将需要用于两个值和四个指针的空间。我们通过总是连续分配跳过列表塔来避免这种情况。每个K级指针将只指向其他K级指针，因此要提取与K级指针P相关联的值，您可以读取P-K处的值。一旦到达一个值大于您要搜索的节点的节点，您就可以返回到上一个节点，只需从指针中减去1即可向下返回一个级别。这样，我们只需消耗值和两个指针的空间，就可以将值分配到第二级。它还减少了我们需要花费在跟踪指针上的时间，因为指向塔的指针很可能与该塔中较低的指针位于同一缓存行上。

在特定节点而不是数组中的元素之间使用链表的一个缺点是，与展开的链表或B树相比，跳过列表对缓存的友好性要差得多-每个单个元素访问都需要追逐一个指针，这通常会导致缓存未命中。这增加了遍历单个帖子列表所需的时间，特别是非常密集的帖子列表。然而，树结构和对数访问时间实际上提高了访问稀疏文档(合取和短语查询)的查询的速度，并允许我们达到与展开的链表几乎相同的平均查询计算速度。

在任何数据存储和检索系统中，确保操作自动进行是很重要的。在搜索系统中，这意味着文档中的所有术语要么都已编入索引，要么都没有编入索引。否则，如果一个使用Twitter的人搜索否定词，例如，过滤器：图像狗和热狗，而我们正在将图片注释添加到“狗”的帖子列表中，但没有将其添加到“热门”帖子列表中，那么这个人可能会看到一张烤香肠三明治的照片，而不是一只可爱的狗。

当使用顺序文档ID并避免更新时，很容易跟踪哪些文档对搜索者可见。搜索器线程从标记最小可见文档ID的原子变量中读取，并跳过任何小于该文档ID的文档标识符。

由于索引系统的更改，我们不再需要我们的摄取管道有一个缓冲区来对所有传入的Tweet进行排序。这对于减少我们的索引延迟来说是一大胜利，但是我们仍然有等待某些字段变得可用而导致的延迟。

我们注意到，我们希望索引的大多数Tweet数据在创建Tweet后立即可用，而我们的客户端通常不需要延迟字段中的数据立即出现在索引中。因此，我们决定我们的摄取管道不应该等待这些延迟字段中的数据变为可用。相反，它可以在Tweet发布后立即将大部分Tweet数据发送到我们的索引系统，然后在其余数据可用时发送另一个更新。

这种方法允许我们消除摄取管道中的最终人为延迟，代价是非常新的Tweet没有完整的数据。由于大多数搜索用例仅依赖于立即可用的字段，我们认为这是可以接受的代价。

推出如此重大的变化并非易事。首先，我们的摄取管道变得更加复杂，因为我们从完全同步的管道切换到具有同步和异步部件的管道。其次，更改索引服务器中的核心数据结构会带来引入单元测试中几乎不可能检测到的模糊错误的风险。第三，很难预测返回更新的推文是否会违反客户代码中的任何假设。

我们决定测试新的摄取管道的最好方法(除了编写许多新的测试之外)是将其与旧的摄取管道一起部署。这意味着在推广期间，我们有两份完整的索引数据副本。此策略允许我们逐步迁移到新的摄取管道，同时，如果出现问题，我们可以轻松地切换回旧的数据流。

我们还设置了索引服务器的临时集群，该集群尽可能接近地镜像我们的生产环境，并开始将我们的一小部分生产请求发送到除了生产服务器之外的这些服务器(一种称为暗读的技术)。这允许我们使用真实的生产流量和负载，以及新旧的Tweet数据流，对核心索引数据结构的更改进行压力测试。一旦我们确信新的数据结构按预期工作，我们就重用这个临时集群来测试新摄取管道生成的数据的正确性。我们建立了这个集群来索引由新的摄取管道产生的数据，并比较对生产的响应。这样做会暴露出一些细微的错误，这些错误只会影响黑暗的流量。一旦我们修复了它们，我们就可以将更改部署到生产中了。

因为我们不知道我们的客户在他们的代码中做了什么假设，所以我们采取了保守的方法。我们向索引服务器添加了代码，使其不为过去15秒内发布的任何Tweet提供服务(我们的初始索引延迟)，并逐步推出了索引端的所有更改。一旦我们确信索引更改按预期工作，我们就删除了旧的摄取管道。我们与客户进行了核对，看看最近的推文是否会导致任何问题，以及。

..