搜索引擎分布式系统思考实践

1.引言

搜索引擎在数据量逐步扩大之后，分布式搜索是必经之路。搜索引擎的分布式除了要考虑数据分片之外，更重要还需要考虑数据的有状态以及各组件的状态流转。在这里分享一下基于ZK设计分布式搜索引擎的一些经验和思考落地情况，包含了从单机版本到分布式版本的演进。

2.分布式系统

分布式系统（distributed system）是一个硬件或软件组件分布在不同的网络计算机上，彼此之间仅仅通过消息传递进行通信和协调的系统。当单机系统在请求量或者数据量无法承载的时候，需要考虑对系统进行合理的分布式改造和部署。

CAP（Consistency Availability Partition tolerance）定理是大家熟知的概念，这三个指标是不可能同时做到的，所以在实际应用中，我们需要我们总是需要针对当前的业务进行取舍，比如在核心数据库领域为了数据强一致性那么我们可能妥协一部分可用性，而在大流量的服务上可能会优先可用性，而在Search的搜索和推荐的应用场景中我们应该优先选择可用性，来优先保证性能，而在强一致性上妥协，只需要保证最终一致性即可。

3.分布式系统面临的挑战

构建一个完整的分布式系统需要解决如下几个重要的问题：

• 可靠的节点状态感知

在分布式系统中异常来自很多情况，包括服务器硬件不可用导致的崩溃，系统出现严重异常崩溃退出，网络不稳定带来的链接异常和不稳定、服务负载过高出现的假死等各种异常状态。

• 数据更新的可靠性

搜索服务作为有状态的服务，需要索引大量的数据，同时更为重要的是索引数据不仅每时每刻都在写入，而且需要保证天级别或者小时级别的全量数据更新，对于一个在线服务，又要保证检索的稳定性。形象比喻为高速上换车轮不为过。

4.Search分布式总体结构

Search分布式总体包括了几大组件：

1. shard(核心检索逻辑和索引分片)
2. searcher(检索和请求分发)
3. indexbuild(离线索引构建)
4. search-client(服务发现客户端)

Search分布式框架：

5.shard模块

Search的shard模块是整个搜索引擎的核心部分，其主要的功能包含了每个独立的检索单元，主要的框架模块包含以下部分：

5.1 索引

Search的索引包含多种种类，每种种类数据结构不一样当前已有的内部索引有正排索引、倒排索引、Term索引、Tf的索引、向量索引等多种索引形式。

• 正排索引​

Search的正排索引存放了从引擎内每个主键ID到每条doc完整数据的映射，索引的结构是一个Hashmap结构,每个Key是主键ID的Hash值，value是指向每个完整doc的指针。引擎内部使用两个Hashmap,第一个是主键ID到唯一的docid映射另一个是docid到完整doc的指针映射。

倒排索引

倒排索引本质上是记录Key到每个doc的映射，在检索中需要保证倒排链有高效的读写能力，读能力利于高效进行复杂的检索语法操作，比如AND、OR、NOT等复杂的操作。同时倒排链的数据结构还需要高效的写能力，在引擎检索的同时需要将实时数据写入到引擎，不可避免的需要修改倒排链，所以高效的写能力也比较关键。

数组

使用数组来作为索引的结构，好处是读很快，逻辑操作也快，cache友好，但是写操作不行，只能用于离线固定的数据，不写入增量的方式。

跳表(SkipList)

跳表的数据结构是对链表的一种折中，读写性能都算中规中矩，CPU的cache性能比较差，记录单个docid使用的空间比较多，需要两个指针外加一个整型。

Bitmap

Bitmap类型是使用位来表示二值信息，Bitmap的位数来作为Key值，搜索引擎倒排索引结构比较适合Bitmap这种数据结构，同时Bitmap的结构对CPU的cache友好，读和写操作很快，但是因为Bitmap是记录了所有Key的状态，包括Bitmap是0的，导致空间可能浪费严重。

Roaring Bitmap

RoaringBitmap是带有一定压缩功能的Bitmap结构，在既保留了Bitmap的随机读写的性能外，合理对Bitmap中1和0的稠密程度做了处理，减少了存储空间，综合性能比较优。

倒排索引的数据结构每个都有各自的适用场景和数据，总体来说看RoaringBitmap的综合性能较好一些。ES搜索引擎(Elasticsearch)中对这几种倒排索引有一个详细的测试，感兴趣的同学可以针对每个测试下看一下各自的测试结果。

Term索引

Term的索引主要用来存放每个字段分词完的每个Term，因为Term数量非常大，如果按照普通的存放会有大量的空间浪费，同时搜索引擎需要前缀搜索，所以Term词的存放需要满足前缀查询。Search的Term词存放使用的数据结构是FST(Finite-State Transducer)数据结构,对应的详细论文地址,FST的数据结构要比前缀查询树Trie树更加的节省空间，查询效率两者相比基本一致。

向量索引

向量索引内部是一种特殊的倒排索引，根据不同的近似向量查询算法，产出不一样的索引，针对矢量量化算法而言，训练后的向量索引会先聚类成一定数量的倒排索引，每个聚类结果形成一个codeID，倒排是对应这个聚类下的向量。所以向量索引是一类特殊的倒排索引。

5.2 查询排序

查询模块是Search核心的功能模块，包括了检索的众多核心业务逻辑，其中包括自研的分词器MusicWs、analysis词性分析模块、语法解析和逻辑查找模块、Search排序框架以及缓存模块等各部分模块。

6.searcher模块

searcher模块是Search核心部分，shard模块的上游，主要的功能包含了对请求的分片和Merge以及对数据的重排序等功能。searcher的整体结构如下：

6.1 查询路由

• Route模块

Route模块主要功能是对请求的原始Query进行横向切分，Route会根据在ZK路径中保存的分片信息来对请求进行分片，比如请求中会带最大召回截断fulllimit，R oute会根据fulllimit的值同时根据分片个数进行分配，然后分发到各个shard节点上去。

• Merge模块

Merge模块是对shard的数据回包进行处理聚合和处理，对各个shard模块回包数据进行处理和聚合。

6.2 排序框架

searcher中排序框架，主要是对全局的最后结果进行重新的排序，比如歌曲中会对最终的歌曲检索统一进行打分，每个shard将对应的歌曲归一化分数上传给searcher模块，最终将分数进行统一的排序。同时，排序框架支持自定义开发的打分器和排序插件。

7.Search客户端和服务发现机制

Search的服务发现机制是沟通各个服务之间的核心模块，除了保证正常的RPC数据调用外，还要保证服务异常时候流量正常的切换的调度。Search服务发现功能模块：

Search的服务发现包含两部分，服务端和客户端，通过ZK来交互，ZK上存放了每个集群的机器IP和端口，客户端来监听该路径的变化，当任意列表中IP删除后，ZK回调客户端来感知，客户端将流量从该台机器切走。同时客户端和服务端之间存在心跳，用于服务端服务卡死等异常情况下流量切流。

8.Search分布式节点的设计

带有状态的分布式系统最复杂的莫过于对于异常的处理了，包括数据的更新和节点异常的处理，对于Search来言数据的更新会导致节点的上下线，包括状态的变化，而集群的扩缩容会导致各个节点剧烈变化带来异常，同时某个节点出了问题，也需要集群智能进行处理和路由，所以前期必须设计一套可靠的处理机制。

8.1 各个节点的设计

shard和searcher的节点是整个Search系统中的重中之重，首选需要设计一个合理的层次结构来组件整体的分布式系统。

1. 上图是shard节点在ZK中的路径分布，按照集群名应用名逐层分布，在路径的末尾节点存放的是每个shard的自己的分片信息，第一位是总的分片，第二位是第几个分片的ID，该路径下注册的是所有shard的集群IP和端口列表。searcher服务通过监听这个路径来获取当前分发的具体分片数，已经对应的分片ID。
2. 当需要扩容的时候，新的节点服务更新完数据后将自己的对应IP和端口注册到新的节点上，随着老的分片机器逐步更新数据到新的分片中，对应的老的节点中分片集群IP越来越少，最后逐步全部迁移到新的节点中。这是完成了扩容，同理缩容的时候shard节点反向操作完成缩容。

8.2 shard节点和searcher节点的请求设计

在shard的节点设计中没有进行区分主副本，各个副本之前都是有请求流量，之所以这么考虑是因为提高机器利用率，只是简单副本价值不大，所以所有副本权重平衡全部接流量。

部署的时候，每一行是一个完整的数据集合，也是整体的一个最小请求行。而每一列是相同的数据集合，没有主从之分，任何一个节点上面都有流量。当其中一个节点出了问题，比如节点崩溃，进程退出，在崩溃的时候shard端内部机制会在崩溃前主动进行下线，那么searcher会将流量自动分发到剩余的shard列节点中。

9.Search分布式数据流的设计

Search是有状态的检索服务，会有一直写入的实时数据也有每天或者每小时更新的离线数据到引擎中，数据的可靠更新非常重要，对于分布式而言，各个分片的产出更新和实时数据的写入都是非常重要的一环。

1. 引擎分为实时和离线，在引擎的构建系统中会根据中台中设置的总分片数来对原始数据进行平均分片，分片逻辑是根据每条数据的主键ID取Hash然后同余，然后给构建系统进行构建索引，最后构建完的索引统一放在Search的HDFS路径下。
2. 实时数据通过Kafka汇总后，各个shard分片会统一消费Kafka中的数据，然后根据数据中的主键ID进行Hash后同余判断是不是自己所在的分片最后判断是否写入自己所在的索引。
3. 对于一致性的处理，因为同一个shard分片中的多个副本中的消费速度不同，理论上只能保证同一个分片中多个副本的最终一致性，即存在某一个时刻有一个数据最先到一个分片中那一瞬间优先检索出来，而同样的搜索词可能在其他分片中检索不出来，不过这种情况几乎会感知不到，因为多个副本的消费速度都是在每秒处理几万到十万级别的数据，也就是说Search增量写入能力单条都在1ms以下，除非出现其中一个节点网络问题或者磁盘异常情况会出现写入出现问题，最终出现某些节点数据检索异常，不过这些异常都会通过报警及时报警，进行节点处理。

10.总结

本篇文章主要是对搜索引擎分布式的设计和落地做了总结，主要的几个重要部分是，如何设计一套有状态的分布式系统，其中最主要的核心部分是如何对各个节点的状态变化做处理，以及合理的对数据进行分片和处理。其中ZK的路径节点设计，自动扩缩容的实现，客户端的服务发现，状态感知功能，都是其中核心部分。