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

71次阅读

共计 4388 个字符,预计需要花费 11 分钟才能阅读完成。

1. 引言

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

2. 分布式系统

  • 分布式系统(distributed system)是一个硬件或软件组件散布在不同的网络计算机上,彼此之间仅仅通过消息传递进行通信和协调的零碎。当单机零碎在申请量或者数据量无奈承载的时候,须要思考对系统进行正当的分布式革新和部署。
  • CAP(Consistency Availability Partition tolerance)定理是大家熟知的概念,这三个指标是不可能同时做到的,所以在理论利用中,咱们须要咱们总是须要针对以后的业务进行取舍,比方在外围数据库畛域为了数据强一致性那么咱们可能斗争一部分可用性,而在大流量的服务上可能会优先可用性,而在 Search 的搜寻和举荐的利用场景中咱们应该优先选择可用性,来优先保障性能,而在强一致性上斗争,只须要保障最终一致性即可。

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

构建一个残缺的分布式系统须要解决如下几个重要的问题:

  • 牢靠的节点状态感知在分布式系统中异样来自很多状况,包含服务器硬件不可用导致的解体,零碎呈现重大异样解体退出,网络不稳固带来的链接异样和不稳固、服务负载过高呈现的假死等各种异样状态。
  • 数据更新的可靠性搜寻服务作为有状态的服务,须要索引大量的数据,同时更为重要的是索引数据不仅每时每刻都在写入,而且须要保障天级别或者小时级别的全量数据更新,对于一个在线服务,又要保障检索的稳定性。形象比喻为高速上换车轮不为过。

    4.Search 分布式总体构造

    Search 分布式总体包含了几大组件:

  • shard(外围检索逻辑和索引分片)
  • searcher(检索和申请散发)
  • indexbuild(离线索引构建)
  • 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,Route 会依据 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 的门路节点设计,主动扩缩容的实现,客户端的服务发现,状态感知性能,都是其中外围局部。

* 文 / 苏黎
@得物技术公众号

正文完
 0