微信搜索引擎中索引的分布式演进

一、引言

提起分布式，不少人能很清晰的阐述 paxos、CAP 等理论，但我们在遇到一个具体的分布式问题时，很少有人能知道如何做出一个“好”的设计。对于当前的很多分布式数据系统，包括开源的 HBase、ElasticSearch 等，我们一般只知其然，很少能够知其所以然。因为几乎所有的分布式数据系统，都会根据自身情况，对实际场景做一些假设，有所舍取，这种多样性也增加了我们的理解难度。

笔者从业八年，先后从事过分布式存储系统、搜索系统的开发和设计。本文将通过搜一搜场景下的搜索引擎的分布式演化，阐述分布式数据系统在设计中的权衡，希望能给各位读者带来一点启发和帮助。这里假设读者已了解常用的分布式以及搜索的基本理论，具体细节不再冗述。

二、背景

先来看一下维基对搜索引擎的定义：搜索引擎是一种信息检索系统，旨在协助搜索存储在计算机系统中的信息。大家最熟悉的商业搜索系统莫过于 baidu、google，而 ElasticSearch （ES）是迄今为止最为成功的开源搜索引擎。在搜索引擎中，通常会采用倒排索引，用以提升检索性能。

相比商业系统，ES 更注重易用性，采用了对等架构，每个数据节点既处理写入请求，又处理检索请求。所以 ES 更适用于对搜索性能并不敏感的业务，在最经典 ELK 中，ES 就用于日志搜索分析。在成熟的商业系统中，对检索性能稳定性要求比较苛刻，数据写入时需要尽可能少的影响搜索性能，所以更多情况下会将资源消耗比较大的建索引部分拆分到离线来做。

笔者所在的微信搜一搜中，搜索引擎也分为在线离线两部分，离线用于创建索引，在线用于检索。事实上，包括百度在内的大多数企业级搜索系统都采用了这类分离的架构。下图为项目初期的搜一搜索引管理架构：

如上图所示，文档在写入 Indexer 后，由 Indexer 离线创建并管理索引。Searcher 从 Indexer 拉取已建完索引，提供在线检索服务，Searcher 模块中不同节点的索引数据完全一致，互为镜像。Indexer 同步承担了索引管理功能，为无法扩容的单点。对于千万级文档中小业务来说，如果对数据流可靠性要求不苛刻，这里尚能运行良好。但随着文档量越来越大，Indexer 和 searcher 在性能、可扩展性和容错等方面的问题凸显，这种简单架构已经无法满足需求，亟需引入分布式管理。

三、数据分片

分布式解决问题的核心方式是将大任务分解成小任务，分别运行在不同节点上，以加速任务处理。对数据来说也类似，我们可以对数据进行切分，切分后的数据称为分片，不同分片分散到各个节点各自处理。业界对分片的叫法五花八门，在 ES 和 MongoDB 中叫 shard，在 HBase 中叫 region，在 Bigtable 中叫 tablet，另外还有 vnode，vbucket 等称呼。本文将沿用 ES 的叫法，如无特别提示，shard 即指分片。这里需要区分的一个概念是分片和副本，分片是对数据的切分，副本是对分片的拷贝。如果要求更高的读取性能，通常需要增加副本数，如果数据量快速上涨，则可能需要更多的分片。另外一个非常容易与分片（shard）混淆的概念是分区（partition），二者有时甚至会直接混用。不过一般来说分片是横向切分，多数按 key 划分；而分区通常更像是一种纵向切分，比如按时间划分。key 相同的文档先后进入系统，一定会属于一个分片，但可能被划分到多个分区中。

在对数据进行分片时，一个关键点是不同分片间需要尽量避免数据倾斜。分片的拆分方式大致有两种，一种是按 key 的字母序划分，另一种是通过对 key 进行 hash 后取余的方式来划分。Hash 的方式用的更多一些，只要 hash 算法足够均匀，就可以避免数据倾斜问题，在 MongoDB 中用的 MD5 和 Redis 中用的 CRC16 都是分散性非常好的算法。通常情况下，分片都会作为数据管理和迁移的最小单位，分片和副本要求能均匀并分散的划分到不同的节点。在扩容或缩容节点时，数据需要在节点间的重新再分配，即再均衡过程。再均衡过程中，多数系统都要求尽可能少的影响读写性能，再均衡后也需要分片在节点间尽量均匀和分散。

应对再均衡需求，分布式中常见做法有三类：

1. 固定分片个数：分片数在系统初始时选定，数据量增加时，单个分片的数据量相应增加。新扩容节点时，迁移部分分片到新节点，缩容时，反向迁移。这种方式简单，易操作，ES 就采用了该方式。但其也有相应的缺点：对数据量涨幅或降幅比较大的系统，初始搭建时很难确定合适的分片数。

2. 动态分片数：当分片中的数据的增长到一定值时，就会拆分分片；如果分片中数据量过少，则会进行分片合并。在 Hbase 中，单个 region 的大小默认是 10G，过大则会触发拆分。相比上述固定分片的方式，这种方式主要优点是分片数可以自动适配数据量，不再有初始选择分片数的烦恼。但在系统初始导入数据时，会由于分区的多次拆分而严重影响读写性能。所以在 Hbase 和 MongoDB 中，均允许配置一组初始分区，来规避该问题。由于这种分片方式更复杂，部分系统还会提供人工干预的措施。

3. 按节点数分片：上述两种分片方式，均与节点无关，扩容时通过迁移分片来均衡。还有一种分片方式比上述两种更广为人知——一致性哈希：每个节点对应固定数量的分片，如果需要扩容节点，则同时增加相应的分区数，通过数据在分区之间的迁移来达到均衡。实际使用中，一致性哈希常常需要会引入 vnode，来避免数据倾斜。由于对迁移不如上述两种方式友好，所以该方式在数据系统中的应用不广泛。

固定分片的方式相比是最为常用的，但如上所述，在系统初始搭建时，需要选择远大于节点数的分片数，为后续扩容预留空间。在 ES 中，每个分片都是一个依赖 Lucene 的独立引擎，负责数据的存储和检索。这限制了其在初始搭建时的分片数选择，因为过多的分片数会使得请求量放大，从而导致性能的急剧下降。针对该问题，存储系统 Ceph 有个很好的解决方案：其分片为逻辑概念，每台数据节点都可以承载多个逻辑分片，所以可以在初始阶段就选择较大的分片数。相比 ES，Ceph 可以这么做的主要秘诀是：存储系统的数据分片并不需要一个独立的引擎做支撑。

在微信搜一搜中，数据写入与在线检索分离，写入更类似 Ceph，可以按逻辑分区进行划分。这就允许我们在系统初始就选定一个较大的分区数，解决分片数难以确定问题。上图展示了分片与节点的映射关系，当文档写入时，通过 hash 取余的方式，打散到各分片中。新扩容节点 3 时，分片 5 从原来所属的节点 2 迁移至节点 3，通过分片迁移使得其在节点中的分布依旧均衡。

四、分布式系统设计中的考量

在需要划分分片的数据系统中，一般都需要选出一个 Leader 来管理各个分片，这就涉及到选主问题。在数据的读写过程中，需要查找相应的分片，所以要管理路由信息。当节点故障时，需要通过迁移分片来重新分配数据，这就要求 Leader 能实时监控节点状态。主分片与副分片之间通常需要复制数据，这又涉及一致性等问题。下面将会详细阐述微信搜一搜中应对上述问题所作出的选型和考量。

1. 选主问题

对于比较复杂的协调或者事务场景，分布式系统中通常会选出一个 Leader 来进行管理，这主要是因为单机的处理，远比分布式处理要简单。分布式中必须需要考虑的可靠、可信、乱序、延迟等问题，在单机中几乎不存在。比如大名鼎鼎的共识算法 Paxos，通常用来解决选主问题，这如果放到单机，将是不值一提的任务。

Leader 的选举通常有两类方式：

1. 依赖 ZK 或 etcd 等协调服务系统：这是最为常见的方式，其缺点就是需要多维护一套 ZK 系统。但相比带来的复杂度，多数情况下，这个维护成本通常更愿意被接受。

2. 自行选主：在无共享架构（shared nothing）系统中，为了易用和维护性，系统会自行在节点间利用多数派来选主。这种方式常见于开源系统，比如 ES、MongoDB 和 Ceph 等。另外，在部分网络系统（InfiniBand）中，为了在网络分区后，仍然能在两个分区分别提供服务，也会自行实现选主。显然，这种方式更为复杂，在不同系统中自行选主的实现方式各有差异，异常和容错方面的考量点也不尽相同，各有取舍。

在微信有相对成熟的自研 chubby，维护成本比较低，所以在搜一搜中，我们选择了更为简单的方式 1。依赖 chubby 选出 Leader 后，由 Leader 来管理分片到节点的映射，尤其是上述再均衡的过程中的分片重分配。分片映射关系通过 chubby 进行持久化，只有在扩缩容时才会进行变更。如果 Leader 故障，follower 通过 chubby 抢锁重新选主，新 Leader 接管分片映射后提供服务。

2. 在线检索

在检索时，用户请求需发送给全部的分片，分别进行召回，召回的结果在合并后返回。为了提升在线吞吐，每个分片需要增加多个副本，所有副本均提供检索服务。在分片和副本的管理中，一个常见的做法是将不同主分片和副分片均匀且分散的分到不同节点，通过多机并发提升在线性能，在 ES、Ceph、Redis 等系统中，均采用该方式。但在商业场景下，用户请求量变化波动会非常大，比如表情搜索在节假日的请求量往往会上涨好几倍。在上述分片划分方式下，这种请求量大幅波动的场景会导致一个问题：当请求量突然上涨时，需要同比增加副分片数，但这时扩容节点后，如果还需要做到主副分片均匀且分散的分布的话，就需要迁移相应分片到新节点，而迁移本身对资源消耗比较大，又会影响到在线性能。

应对上述的请求大幅波动，微信内普遍采用了 Svrkit 框架。Svrkit 框架是一种非常经典的微服务架构，系统按模块来划分，每个模块都是一个服务。同一模块会在多个节点部署进程，不同节点互为镜像。请求量上涨时，迅速扩容节点，通过部署更多镜像来应对。如果节点异常导致请求失败，上游通过换机重试来避免最终失败，从而保证可用性。但对 Searcher 来说，索引量比较大时，单个镜像中不能装载全部索引，这就需要将索引拆分到不同节点。在 Svrkit 中提供了一种 byset 模式，允许同一模块划分多个分组（Set），各自加载一部分索引。每个分组都有各自的多个镜像提供服务，上游在下发请求时，需要从所有分组进行召回，合并返回。如果遇到上述的请求量上涨时，每个分组各自扩容镜像即可。

如图所示，在线检索的 Searcher 模块，采用了 byset 模式，划分成多个分组。上述分片到节点的映射，也相应的变成了分片到分组的映射，映射的管理由 Leader 来负责。当文档量上涨时，通过扩容分组来容纳；请求量上涨时，各组分别扩容，增加节点数来应对。得益于离线建索引的架构，新扩容的节点只需要从离线拉取数据，整个过程不影响现有服务。在扩缩分组时，部分分片要迁移到新分组中，这时需要注意的是只有在新分组上线提供服务后，才能下线旧分组中的已迁移分片。

在 ES 中，主分片会均匀分散到各节点，这时 Leader 还需要同时管理请求路由。而在 byset 中，路由按分组划分，整个检索过程中，Leader 并不参与，是什么原因使得这里可以做到如此简洁呢？天下没有免费的午餐，这里的简化也不例外。ES 中，如果有 Searcher 的节点数据无法同步时，会通过 Leader 从路由中剔除该节点，所以不会造成数据缺失。但在 Svrkit 的 byset 路由中，Leader 并未参与，如果有 Searcher 节点的数据异常，则无法通过路由的方式及时剔除异常节点。这类数据缺失的代价可谓不菲，能否有其他方式减少该问题的发生呢？如果异常节点与 Leader 之间的通信正常，Leader 可以通知该异常 Searcher 拒绝服务，由上游重试到其他节点来保证正确召回。但如果网络异常导致通信失败，Searcher 无法知道自己数据不完整时，这里就会出现上述数据缺失问题了。所以这里的简化其实隐含的一个假设：如果 Leader 与某 Searcher 通信中断，则客户端也无法访问该 Searcher 节点。在同一数据中心的局域网内，通过交换机堆叠等措施，可以做到全链路无网络单点设备，减少这种网络分区风险。这种场景下，该假设不成立的概率其实非常低，远小于人工操作失误和软件 bug 带来的问题。其实 Svrkit 框架下的 byset 路由模块都隐含了该假设，最常用的 KV 系统就依赖 byset 路由，其稳定性已经过了实践检验，所以当前场景下做出该假设是可行的。

3. 文档写入

文档写入后，首先需要存储，就涉及用共享存储（shared disk）架构，还是无共享架构（shared nothing）的问题。这个决定不难做出，在微信中已经有自研的 WFS（类似 HDFS）、WBT（类似 Hbase）和 WQ（类似 Kafka）已被广泛使用。显然，用共享存储能极大简化工作，实际上在商业搜索中，几乎都依赖了其他存储组件。

由于分片数固定，哈希方式已约定，所以文档在写入时，可以提前计算出其所在的分片，按分片写入依赖 WBT 和 WQ 的数据平台。在建索引时，Processor 模块从数据平台扫描文档，在预处理完成后返回给 Indexer，Indexer 负责索引建立，并落地到 WFS。

4. 节点管理

在线 Searcher 模块中不同的分组，需要加载不同分片的数据及控制上线顺序；Indexer 的不同的节点，需分别负责不同分片的索引建立；在实时流中，Processor 会提前按分组聚合分片，所以也需要感知分片到分组的映射。基于以上原因，Leader 需要感知各个模块中节点的详细状态，在扩缩容或节点故障时，及时作出调整。

常用的节点发现方式是依赖 ZK，通过目录监听来实现，这也是 ZK 作为服务协调者主要用法之一。如果在搜索引擎中采用 ZK 的方案，在监控和与其他模块交互等方面的工作要多很多，所以并不可取。微信的 SvrKit 框架中，会在所有节点部署相同的路由配置文件来实现模块路由，路由变更由运维人员操作，需全局更新配置文件。这里，Leader 可以从路由配置中查找到所有正在提供服务的工作节点信息，如果能依赖路由配置，Leader 发现节点的过程就变的很简单了，新节点加入时通过路由文件就可以找到对应的 Leader。但单纯依赖路由配置还有两个问题：

1. 工作节点当前的状态无法被及时感知，比如节点正在启动，磁盘故障等。

2. 在扩缩容时，新扩 Searcher 节点只有正常提供服务后，配置才能被重新下发给 Leader，但新节点在提供服务前就需要知道分片信息，以便进行数据同步。

Leader 如果需要感知工作节点的当前状态，一个常见的做法就是通过心跳。工作节点定期通过心跳给 Leader 上报自身的情况，Leader 将工作节点所需的分片映射、索引任务等信息带回给工作节点。如果结合路由配置和心跳，这里是否能解决上面的问题呢？针对问题 1，心跳可以携带节点信息，包括启动、异常等状态供 Leader 决策。针对问题 2，即使节点不在路由中，Leader 也可以在心跳中将加载索引任务带回给 Searcher 节点，新节点完成数据加载后，提供在线服务。所以，这里结合路由配置和心跳的方式是可行的。不过心跳也有失效的可能，利用心跳来检测节点状态本身并不完全可靠。比如在工作节点的心跳处理线程有死锁、挂死、CPU 繁忙等异常时，可能会有误检；在异常网络时，比如大包比小包更易丢失的场景下，会导致漏检，利用心跳的方式来收集信息，也就意味着需要能容忍上述各类异常。

上图展示了 Leader 利用路由和心跳来收集 Searcher 和 Indexer 中各进程状态的过程。通过心跳，Leader 能感知各进程当前状态，并利用路由配置来判断是否为新扩容节点等信息。Leader 在心跳包的回执中，同步给 Indexer 下发创建索引任务，给 Searcher 下发相应的加载索引任务。感知节点状态还允许 Leader 及时处理节点故障，比如在 Indexer 故障时，Leader 会通过心跳超时检测到，这时需回收给其分配的索引任务，换 Indexer 重做。

5. 事务、一致性和数据复制

事务是数据库中的概念，通常称作符合 ACID 要求。由于 ACID 过于苛刻，在单机场景下利用锁等方式尚可实现，但在分布式场景下就非常难了。目前各数据库的分布式实现都是弱化后的 ACDI。搜索系统中的数据流，一般都不涉及事务，但各类操控类的操作，比如扩容、缩容、回滚等都有一定的事务要求。不过控制类的操作，几乎都是非常低频的操作，其本身不涉及性能问题，所以经常在 Leader 或 Master 中以单机的方式执行。

存储界的一位架构师大牛曾经总结过一条非常实用的经验：控制流一定要跟数据流分离。这里的主要原因是二者的需求不同：控制操作通常由运维人员发起，非常低频，允许失败后重试，但对事务性有一定的要求；而数据流往往对性能或可靠性的要求更高，但相应会在其他方面做一些折让，通常是在一致性及可用性上有条件的降低要求。在部分要求强一致性的系统中，会在节点故障时临时牺牲可用性，Leader 变更路由后才恢复。将复杂控制逻辑剥离的做法通常使得数据流更可靠，比如 Chubby 或 Leader 故障导致短期无 Leader 的情况下，并不影响数据流的正常执行。ClickHouse 是控制流分离的一个反例，其写操作需要经过 ZK 传递，大大限制写性能。不过作为 OLAP 中的佼佼者，其更关注在线查询性能，而对写操作有更高的容忍度。

在分布式中，另一个经常被提及的问题是数据复制。在单数据中心，业界普遍采用的是单主节点复制，比如 ES、Ceph、Redis 等都是该方式。在主分片和副分片的数据同步时，多数系统采用了同步复制的方式来保证一致性。不同业务在一致性方面的需求不同，这就衍生出很多让人眼花缭乱的名词：最终一致性、因果一致性、读写一致性、会话一致性、单调一致性等等。这种折让虽然为业务带来灵活性，但也加剧了分布式系统的难度。在一致性上折让最大的系统莫过于 Redis 集群了，其为了性能直接采用了异步复制，相当于放弃了一致性保证，这是使用者所诟病的一个点。与单主复制对应的是多主复制，主要用于超大型、跨数据中心时的复制，通常采用异步的方式。多主复制只在几个有超大型数据的商业帝国才会用到，多数业务并不涉及，这里暂不讨论。最后一种复制方式是无主复制，该方式用的相对较少，最经典的是 DynamoDB。无主复制中，多由客户端对所有数据节点发起读写请求，根据 Quorum 多数派，来决定最新的值。这种方式在节点异常时，其实很难判断数据顺序，而且读放大比较严重，所以并不流行。在搜一搜中，Searcher 模块同一分组内并无主节点，不同节点之间不会进行数据同步，而是从 WFS 中拉取。这种做法更接近无主复制，其索引上线（相当于写入）由 Leader 控制，为较低频操作。搜索业务通常对一致性的要求都非常宽松，一般只要求尽可能达到单调读的一致性，这里通过将同一用户的请求路由到同一节点上来实现。

6. 搜索引擎系统架构

通过对上述问题的权衡，搜一搜的分布式架构演变为如下模样：

Leader 依赖 Chubby 选举，为整个搜索引擎的大脑，负责管理分片映射、节点状态及路由。Searcher 模块提供了在线的召回服务，用户在发起搜索时，通过 broker 将请求下发至 Searcher 的全部分组，对结果 Merge 后返回。整个搜索过程 Leader 并不参与，实现控制流和搜索数据流的分离。Leader 通过心跳与 Searcher 中各节点进行交互，收集各个节点状态，通知各节点加载相应索引数据，并利用路由配置识别非集群节点和正在扩容中的节点。

文档数据写入时，先通过 hash 取余的方式确定所属分片，按分片写入数据平台中的 WBT（类似 HBase）和 WQ（类似 Kafka）。这里所选的分片数，一般远大于 Searcher 的分组数，确保在扩容分组时依旧能均匀分布。索引的创建、上线和退场的管理由 Leader 负责，Indexer 依据 Leader 的指示，从 Processor 拉取文档，创建索引，落地到 wfs。由于搜索业务对一致性的要求比较宽松，Searcher 中同分组的不同节点之间，并不进行索引同步，各节点各自从 WFS 拉取对应分组的索引进行加载。

五、索引管理

在大数据处理中，常见的架构有两种：Lambda 和 Kappa；在 Lambda 架构中，数据处理分为两部分：批处理和流式处理。而在 Kappa 架构中，只有流式处理，避免了在实时数据处理系统上再“粘”一个离线数据处理系统。这两种架构其实各有优缺点，Lamda 架构更稳定，但需要维护两套系统，批处理和实时处理要保证一致比较困难。Kappa 架构更易维护，但其数据边界不明确，需要复杂的异常处理，有数据丢失风险。

在搜一搜场景中，我们对文档的可靠性要求比较苛刻，尤其是账号系统（公众号等），数据丢失很容易引发相应产商的投诉。另外，部分特征需要批量计算产出，这就有定期批量更新的需求，所以这里自然选用了 Lamda 架构。当新数据进来时，经由实时流进入搜索系统；当特征定期更新时，则需等待批量索引重建才能更新到线上。

上图为剔除处理逻辑后的数据流示意图，文档通过 WQ（类似 Kafka）接入后，分别进入用于批量处理的 WBT（类似 HBase）和用于实时流的 WQ。批量计算出的特征，直接写入 WBT，通过定期全量重建索引的方式上线；新增、删除或更新的文档，流经实时流 WQ，直接进入搜索系统。由于文档异步接入且索引在离线建立，所以准确的讲这里应该叫近实时流。在 ES 中，作为存储系统，读写操作是实时的，但其提供的搜索服务也需要提前建索引，也属于近实时的。

1. 全量索引更新

全量索引重建为定期任务，indexer 从 WBT 扫描全部文档重建索引，通过 WFS 推送至 Searcher。由于 Searcher 提前划分了分组，所以 Indexer 也需要按分组建索引，每次扫描时，只扫描对应分组的分片即可。对 Searcher 中的每个节点来说，每次召回相当于在索引中查找 TopK 的过程，如果每个节点只有一个索引，其检索资源利用率是最高的，实际上多数商业搜索中也是这么做的。但是，这也带来一个问题：在索引更新时需要预留一倍的资源进行热替换。为了避免这种资源浪费，一种常用的方式是在对节点进行索引更新时，先停止服务，索引更新完成后重新上线该节点。如果业务数据足够大，近实时流和全量索引属于不同的 Searcher 模块，再加上仔细选择上线时机的话，停服对在线的影响其实可控，是较好的选择。

在微信搜一搜场景中，引擎需要支持几十上百业务，尤其是对文档数较少的账号系统来说，同时维护两个 Searcher 模块的运维成本比较高，所以依旧选择了不停服的方案。但不停服的时候，如何避免索引替换时新旧两份数据带来的资源占用呢？针对该问题，一个很自然的解决方案是对节点内的索引数据进行切分，即 Searcher 节点内的索引切分为多个库，每个库依次替换，这样只需多预留一个库的资源即可。为了与实时流区分，这里姑且称作全量库。这里的一个难点是全量库替换时，要求新库能覆盖旧库的全部数据，以保证数据完整性。如果新旧库包含相同的分片，则可解决该问题，所以分片到分组的映射，又演化为分片到全量库的映射。

如上图，分片会映射到不同全量库中，新扩容分组时，全量库的个数也相应增加。全量索引重建的请求由运维人员或定时器发起，作为控制操作发送给 Leader。Leader 负责生成管理全量库的建库、加载、退场等任务，Indexer 收到建库任务后，拉取对应的分片数据，建库完成后在 WFS 保存。Leader 收到 Indexer 的建库任务完成后，通知 Searcher 中对应分组的节点进行库数据加载及下线对应的旧库。

索引的每次全量重建完都会形成一轮完整的索引，这类似于存储系统中的快照。不过这里并不“快”，建库过程中的拉取数据并不是一个瞬时操作，所以在判断其覆盖的近实时流范围时，只能按起始拉取时间来判断。已完成的索引数据，会在 WFS 中保存多个轮次，这为索引回滚提供了条件。如果当前轮次的数据异常，Leader 支持运维人员选择一轮已上过线的索引，进行快速回滚，来消除错误数据带来的影响。

2. 近实时流更新

近实时流的实现，通常要求对写友好，所以这里需要从大名鼎鼎的 LSM（Log-Structured Merge-Tree）说起。犹如其名，LSM 最初确实是用于日志文件系统的，其主要思想是：增量数据在内存中先排序，超过阈值时落地文件，文件是不可修改的，新的增量重新生成新文件，这就将数据随机写入变成了顺序写。但这同时也导致数据在多次更新时，会在不同文件中有一定的冗余，这种冗余在随后的文件逐级合并时清除。LevelDB 是最为经典的 LSM 范例，其提供了按 Key 查询的能力，鉴于其简洁和优雅的代码设计，已经成为 LSM 学习标杆。在搜索引擎中，Lucene 也符合 LSM 思想，与 LevelDB 不同的是，其在内存中的索引更复杂，并不是简单按 key 排序，而是按倒排建立索引。另一个不同点是文件合并时的策略，LevelDB 是按 Level 由小到大合并，而 Lucene 中是按文件大小合并。按文件大小合并策略相比更为灵活、高效，采用该策略的另一个经典系统是 HBase。

LSM 其实是通过牺牲部分读性能，换取最大化的写。这种方式也有相应的缺点：出于资源的限制，往往无法将数据合并到 1 个文件中，这也使得部分冗余数据无法被消除。另外，在文件合并时，需要大量的 IO 和 CPU 资源，这会抢占在线读写资源，带来一定的性能波动。不过，以上问题在离线创建索引的搜索系统中并不存在：

1. 索引在离线创建，在建索引时并不太关注资源抢占问题；

2. 由于有全量索引更新流程，这相当于数据重整过程。过旧的近实时流的文件会被覆盖而下线，所以并不需要担心数据冗余问题。

然而，这里还有一个问题没有解决：LSM 主要是为单节点准备的，但 Indexer 为无状态模块，不同的合并任务可能属于不同节点，这里还能适用么？其实 Indexer 建完索引后，会在 WFS 中持久化，这里只是将本地的 IO 变换成 WFS 的 IO 操作。由于没有读操作，多节点分布并无不妥，建库任务由 Leader 统一管理，也免除了多机之间同步的烦恼。

上图为某分组中近实时流库的快照示意图，其中下面的 Refresh 库相当于 LSM 内存中累积的数据，Level 库类似 LSM 中落地后的文件。新增数据，首先会进入 Refresh 库，只有 Refresh 库的数据到达一定阈值，才会转换成 Level_0 的库。如果数据写入速度较低，Refresh 库在时间阈值（5 秒）到期后也会落地上线，以便新数据能被及时检索到；上图中“库 91” 为已上线（绿色表示）的 Refresh 库，新的数据会进入“库 92”，”库 92”可以完全覆盖“库 91”的数据，如果“库 92”中的数据达到阈值后，会转换为 Level_0 的“库 9”。

在 Level 库中，由低向高合并，高 Level 的库一旦上线（绿色表示），则会同步下线掉其已覆盖的低 Level 库（灰色表示）。如果忽略删除操作带来的波动，这里每个 Level 中，不同的库中文档数几乎一致，其大小也接近，所以不存在按大小还是按 Level 合并策略的选择。整个近实时流是按照时间顺序排列的，当全量索引重建完成并上线后，会同步下线其覆盖的近实时流库（红色表示）。图中黄色部分，表示正在建索引中的库，比如近实时流“库 7|8”，正在对“库 7”和“库 8”进行合并重建。

通常情况下，LSM 的合并都在每个分片中各自进行，比如 Lucene 就属于 ES 的一个分片。但我们的场景下，分片数往往设置一个比较大的值，按分片管理将会给在线带来非常多的库，同时也给 Leader 带来较大的压力。由于在线 Searcher 按分组来加载索引，这就为分片聚合提供了可能。这里采用了按分组管理的方式，即 Indexer 会拉取归属于某个分组的全部分片的增量数据来创建索引。索引完成后，由 Leader 通知对应分组的 Searcher 进行加载，完成上线。不过这里也相应有一个缺点是，近实时流只能按分组被全量索引覆盖下线时，不能按分片来进行，造成少量的数据冗余。在系统开启近实时流后，Leader 会自动生成相应的任务，下发给 Indexer，数据流并不经过 Leader，整个过程也无需人工参与。

由于 lambda 架构有效的平衡了数据可靠性和时效性，为多数商业系统所采用。但在搜一搜中，引擎需要支持几十上百业务，这也放大了 lamda 架构的问题：每个业务都需要维护一个全量索引和近实时流两套系统，维护成本比较高。即便有 Leader 来做任务管理，文档预处理、模块维护等仍需要各业务各自参与开发。再加上 Svrkit 本身微服务的特性，更适用于 RPC 模式的流式处理，所以这里在实现时更偏向于 Kappa 架构。默认情况下，用于预处理的 Processor 和 负责索引建立的 Indexer 模块并未区分全量和近实时流。

在超大型搜索业务中，上述混合架构往往无法支撑，全量索引处理需要从流式处理中真正拆分，独自进行批处理。在百亿到千亿文档的大型 Web 搜索系统中，往往还需要进行冷热数据分离。包括时新数据在内的热数据，要求每次都能正常检索，但冷数据由于排序靠后而得不到曝光，对响应时长和召回率的容忍度都要更高。与上述按文档分片后的 DAAT（document at a time）检索模式不同，冷数据通常会采用成本更低的 TAAT（term at a time）模式。

另外，冷热分离后，数据的冷热迁移也是一个需要关注的点，往往根据业务需求来订制。这类超大业务目前只在几个商业巨头中用到，已经超出本文的范围和笔者的经验，如有读者对这部分感兴趣，可以一起交流。

六、结语

本文详细阐述了微信搜一搜中索引管理的分布式设计中的选型和取舍。其中涉及的多个分布式经典问题，都是在数据系统的设计中要仔细权衡的。许多非常好的知名开源系统都可以给我们提供很多思路和经验。另外，本文还阐述了在离线建索引架构下，索引管理过程中的选型和设计，这部分对采用读写分离架构的数据系统有较多的参考意义。由于选题比较大，限于笔者能力，错误在所难免，还望各位读者不吝指出。

头图：Unsplash

作者：白乾

原文：https://mp.weixin.qq.com/s/npfvrchu411KDsI6hQn-nw

原文：微信搜索引擎中索引的分布式演进

来源：云加社区 - 微信公众号 [ID：QcloudCommunity]

转载：著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。