1.引言

搜索引擎在數(shù)據(jù)量逐步擴(kuò)大之后，分布式搜索是必經(jīng)之路。搜索引擎的分布式除了要考慮數(shù)據(jù)分片之外，更重要還需要考慮數(shù)據(jù)的有狀態(tài)以及各組件的狀態(tài)流轉(zhuǎn)。在這里分享一下基于ZK設(shè)計(jì)分布式搜索引擎的一些經(jīng)驗(yàn)和思考落地情況，包含了從單機(jī)版本到分布式版本的演進(jìn)。

2.分布式系統(tǒng)

分布式系統(tǒng)（distributed system）是一個(gè)硬件或軟件組件分布在不同的網(wǎng)絡(luò)計(jì)算機(jī)上，彼此之間僅僅通過(guò)消息傳遞進(jìn)行通信和協(xié)調(diào)的系統(tǒng)。當(dāng)單機(jī)系統(tǒng)在請(qǐng)求量或者數(shù)據(jù)量無(wú)法承載的時(shí)候，需要考慮對(duì)系統(tǒng)進(jìn)行合理的分布式改造和部署。

CAP（Consistency Availability Partition tolerance）定理是大家熟知的概念，這三個(gè)指標(biāo)是不可能同時(shí)做到的，所以在實(shí)際應(yīng)用中，我們需要我們總是需要針對(duì)當(dāng)前的業(yè)務(wù)進(jìn)行取舍，比如在核心數(shù)據(jù)庫(kù)領(lǐng)域?yàn)榱藬?shù)據(jù)強(qiáng)一致性那么我們可能妥協(xié)一部分可用性，而在大流量的服務(wù)上可能會(huì)優(yōu)先可用性，而在Search的搜索和推薦的應(yīng)用場(chǎng)景中我們應(yīng)該優(yōu)先選擇可用性，來(lái)優(yōu)先保證性能，而在強(qiáng)一致性上妥協(xié)，只需要保證最終一致性即可。

3.分布式系統(tǒng)面臨的挑戰(zhàn)

構(gòu)建一個(gè)完整的分布式系統(tǒng)需要解決如下幾個(gè)重要的問(wèn)題：

• 可靠的節(jié)點(diǎn)狀態(tài)感知

在分布式系統(tǒng)中異常來(lái)自很多情況，包括服務(wù)器硬件不可用導(dǎo)致的崩潰，系統(tǒng)出現(xiàn)嚴(yán)重異常崩潰退出，網(wǎng)絡(luò)不穩(wěn)定帶來(lái)的鏈接異常和不穩(wěn)定、服務(wù)負(fù)載過(guò)高出現(xiàn)的假死等各種異常狀態(tài)。

• 數(shù)據(jù)更新的可靠性

搜索服務(wù)作為有狀態(tài)的服務(wù)，需要索引大量的數(shù)據(jù)，同時(shí)更為重要的是索引數(shù)據(jù)不僅每時(shí)每刻都在寫(xiě)入，而且需要保證天級(jí)別或者小時(shí)級(jí)別的全量數(shù)據(jù)更新，對(duì)于一個(gè)在線服務(wù)，又要保證檢索的穩(wěn)定性。形象比喻為高速上換車輪不為過(guò)。

4.Search分布式總體結(jié)構(gòu)

Search分布式總體包括了幾大組件：

1. shard(核心檢索邏輯和索引分片)
2. searcher(檢索和請(qǐng)求分發(fā))
3. indexbuild(離線索引構(gòu)建)
4. search-client(服務(wù)發(fā)現(xiàn)客戶端)

Search分布式框架：

5.shard模塊

Search的shard模塊是整個(gè)搜索引擎的核心部分，其主要的功能包含了每個(gè)獨(dú)立的檢索單元，主要的框架模塊包含以下部分：

5.1 索引

Search的索引包含多種種類，每種種類數(shù)據(jù)結(jié)構(gòu)不一樣當(dāng)前已有的內(nèi)部索引有正排索引、倒排索引、Term索引、Tf的索引、向量索引等多種索引形式。

• 正排索引?

Search的正排索引存放了從引擎內(nèi)每個(gè)主鍵ID到每條doc完整數(shù)據(jù)的映射，索引的結(jié)構(gòu)是一個(gè)Hashmap結(jié)構(gòu),每個(gè)Key是主鍵ID的Hash值，value是指向每個(gè)完整doc的指針。引擎內(nèi)部使用兩個(gè)Hashmap,第一個(gè)是主鍵ID到唯一的docid映射另一個(gè)是docid到完整doc的指針映射。

倒排索引

倒排索引本質(zhì)上是記錄Key到每個(gè)doc的映射，在檢索中需要保證倒排鏈有高效的讀寫(xiě)能力，讀能力利于高效進(jìn)行復(fù)雜的檢索語(yǔ)法操作，比如AND、OR、NOT等復(fù)雜的操作。同時(shí)倒排鏈的數(shù)據(jù)結(jié)構(gòu)還需要高效的寫(xiě)能力，在引擎檢索的同時(shí)需要將實(shí)時(shí)數(shù)據(jù)寫(xiě)入到引擎，不可避免的需要修改倒排鏈，所以高效的寫(xiě)能力也比較關(guān)鍵。

數(shù)組

使用數(shù)組來(lái)作為索引的結(jié)構(gòu)，好處是讀很快，邏輯操作也快，cache友好，但是寫(xiě)操作不行，只能用于離線固定的數(shù)據(jù)，不寫(xiě)入增量的方式。

跳表(SkipList)

跳表的數(shù)據(jù)結(jié)構(gòu)是對(duì)鏈表的一種折中，讀寫(xiě)性能都算中規(guī)中矩，CPU的cache性能比較差，記錄單個(gè)docid使用的空間比較多，需要兩個(gè)指針外加一個(gè)整型。

Bitmap

Bitmap類型是使用位來(lái)表示二值信息，Bitmap的位數(shù)來(lái)作為Key值，搜索引擎倒排索引結(jié)構(gòu)比較適合Bitmap這種數(shù)據(jù)結(jié)構(gòu)，同時(shí)Bitmap的結(jié)構(gòu)對(duì)CPU的cache友好，讀和寫(xiě)操作很快，但是因?yàn)锽itmap是記錄了所有Key的狀態(tài)，包括Bitmap是0的，導(dǎo)致空間可能浪費(fèi)嚴(yán)重。

Roaring Bitmap

RoaringBitmap是帶有一定壓縮功能的Bitmap結(jié)構(gòu)，在既保留了Bitmap的隨機(jī)讀寫(xiě)的性能外，合理對(duì)Bitmap中1和0的稠密程度做了處理，減少了存儲(chǔ)空間，綜合性能比較優(yōu)。

倒排索引的數(shù)據(jù)結(jié)構(gòu)每個(gè)都有各自的適用場(chǎng)景和數(shù)據(jù)，總體來(lái)說(shuō)看RoaringBitmap的綜合性能較好一些。ES搜索引擎(Elasticsearch)中對(duì)這幾種倒排索引有一個(gè)詳細(xì)的測(cè)試，感興趣的同學(xué)可以針對(duì)每個(gè)測(cè)試下看一下各自的測(cè)試結(jié)果。

Term索引

Term的索引主要用來(lái)存放每個(gè)字段分詞完的每個(gè)Term，因?yàn)門(mén)erm數(shù)量非常大，如果按照普通的存放會(huì)有大量的空間浪費(fèi)，同時(shí)搜索引擎需要前綴搜索，所以Term詞的存放需要滿足前綴查詢。Search的Term詞存放使用的數(shù)據(jù)結(jié)構(gòu)是FST(Finite-State Transducer)數(shù)據(jù)結(jié)構(gòu),對(duì)應(yīng)的詳細(xì)論文地址,FST的數(shù)據(jù)結(jié)構(gòu)要比前綴查詢樹(shù)Trie樹(shù)更加的節(jié)省空間，查詢效率兩者相比基本一致。

向量索引

向量索引內(nèi)部是一種特殊的倒排索引，根據(jù)不同的近似向量查詢算法，產(chǎn)出不一樣的索引，針對(duì)矢量量化算法而言，訓(xùn)練后的向量索引會(huì)先聚類成一定數(shù)量的倒排索引，每個(gè)聚類結(jié)果形成一個(gè)codeID，倒排是對(duì)應(yīng)這個(gè)聚類下的向量。所以向量索引是一類特殊的倒排索引。

5.2 查詢排序

查詢模塊是Search核心的功能模塊，包括了檢索的眾多核心業(yè)務(wù)邏輯，其中包括自研的分詞器MusicWs、analysis詞性分析模塊、語(yǔ)法解析和邏輯查找模塊、Search排序框架以及緩存模塊等各部分模塊。

6.searcher模塊

searcher模塊是Search核心部分，shard模塊的上游，主要的功能包含了對(duì)請(qǐng)求的分片和Merge以及對(duì)數(shù)據(jù)的重排序等功能。searcher的整體結(jié)構(gòu)如下：

6.1 查詢路由

• Route模塊

Route模塊主要功能是對(duì)請(qǐng)求的原始Query進(jìn)行橫向切分，Route會(huì)根據(jù)在ZK路徑中保存的分片信息來(lái)對(duì)請(qǐng)求進(jìn)行分片，比如請(qǐng)求中會(huì)帶最大召回截?cái)鄁ulllimit，R oute會(huì)根據(jù)fulllimit的值同時(shí)根據(jù)分片個(gè)數(shù)進(jìn)行分配，然后分發(fā)到各個(gè)shard節(jié)點(diǎn)上去。

• Merge模塊

Merge模塊是對(duì)shard的數(shù)據(jù)回包進(jìn)行處理聚合和處理，對(duì)各個(gè)shard模塊回包數(shù)據(jù)進(jìn)行處理和聚合。

6.2 排序框架

searcher中排序框架，主要是對(duì)全局的最后結(jié)果進(jìn)行重新的排序，比如歌曲中會(huì)對(duì)最終的歌曲檢索統(tǒng)一進(jìn)行打分，每個(gè)shard將對(duì)應(yīng)的歌曲歸一化分?jǐn)?shù)上傳給searcher模塊，最終將分?jǐn)?shù)進(jìn)行統(tǒng)一的排序。同時(shí)，排序框架支持自定義開(kāi)發(fā)的打分器和排序插件。

7.Search客戶端和服務(wù)發(fā)現(xiàn)機(jī)制

Search的服務(wù)發(fā)現(xiàn)機(jī)制是溝通各個(gè)服務(wù)之間的核心模塊，除了保證正常的RPC數(shù)據(jù)調(diào)用外，還要保證服務(wù)異常時(shí)候流量正常的切換的調(diào)度。Search服務(wù)發(fā)現(xiàn)功能模塊：

Search的服務(wù)發(fā)現(xiàn)包含兩部分，服務(wù)端和客戶端，通過(guò)ZK來(lái)交互，ZK上存放了每個(gè)集群的機(jī)器IP和端口，客戶端來(lái)監(jiān)聽(tīng)該路徑的變化，當(dāng)任意列表中IP刪除后，ZK回調(diào)客戶端來(lái)感知，客戶端將流量從該臺(tái)機(jī)器切走。同時(shí)客戶端和服務(wù)端之間存在心跳，用于服務(wù)端服務(wù)卡死等異常情況下流量切流。

8.Search分布式節(jié)點(diǎn)的設(shè)計(jì)

帶有狀態(tài)的分布式系統(tǒng)最復(fù)雜的莫過(guò)于對(duì)于異常的處理了，包括數(shù)據(jù)的更新和節(jié)點(diǎn)異常的處理，對(duì)于Search來(lái)言數(shù)據(jù)的更新會(huì)導(dǎo)致節(jié)點(diǎn)的上下線，包括狀態(tài)的變化，而集群的擴(kuò)縮容會(huì)導(dǎo)致各個(gè)節(jié)點(diǎn)劇烈變化帶來(lái)異常，同時(shí)某個(gè)節(jié)點(diǎn)出了問(wèn)題，也需要集群智能進(jìn)行處理和路由，所以前期必須設(shè)計(jì)一套可靠的處理機(jī)制。

8.1 各個(gè)節(jié)點(diǎn)的設(shè)計(jì)

shard和searcher的節(jié)點(diǎn)是整個(gè)Search系統(tǒng)中的重中之重，首選需要設(shè)計(jì)一個(gè)合理的層次結(jié)構(gòu)來(lái)組件整體的分布式系統(tǒng)。

1. 上圖是shard節(jié)點(diǎn)在ZK中的路徑分布，按照集群名應(yīng)用名逐層分布，在路徑的末尾節(jié)點(diǎn)存放的是每個(gè)shard的自己的分片信息，第一位是總的分片，第二位是第幾個(gè)分片的ID，該路徑下注冊(cè)的是所有shard的集群IP和端口列表。searcher服務(wù)通過(guò)監(jiān)聽(tīng)這個(gè)路徑來(lái)獲取當(dāng)前分發(fā)的具體分片數(shù)，已經(jīng)對(duì)應(yīng)的分片ID。
2. 當(dāng)需要擴(kuò)容的時(shí)候，新的節(jié)點(diǎn)服務(wù)更新完數(shù)據(jù)后將自己的對(duì)應(yīng)IP和端口注冊(cè)到新的節(jié)點(diǎn)上，隨著老的分片機(jī)器逐步更新數(shù)據(jù)到新的分片中，對(duì)應(yīng)的老的節(jié)點(diǎn)中分片集群IP越來(lái)越少，最后逐步全部遷移到新的節(jié)點(diǎn)中。這是完成了擴(kuò)容，同理縮容的時(shí)候shard節(jié)點(diǎn)反向操作完成縮容。

8.2 shard節(jié)點(diǎn)和searcher節(jié)點(diǎn)的請(qǐng)求設(shè)計(jì)

在shard的節(jié)點(diǎn)設(shè)計(jì)中沒(méi)有進(jìn)行區(qū)分主副本，各個(gè)副本之前都是有請(qǐng)求流量，之所以這么考慮是因?yàn)樘岣邫C(jī)器利用率，只是簡(jiǎn)單副本價(jià)值不大，所以所有副本權(quán)重平衡全部接流量。

部署的時(shí)候，每一行是一個(gè)完整的數(shù)據(jù)集合，也是整體的一個(gè)最小請(qǐng)求行。而每一列是相同的數(shù)據(jù)集合，沒(méi)有主從之分，任何一個(gè)節(jié)點(diǎn)上面都有流量。當(dāng)其中一個(gè)節(jié)點(diǎn)出了問(wèn)題，比如節(jié)點(diǎn)崩潰，進(jìn)程退出，在崩潰的時(shí)候shard端內(nèi)部機(jī)制會(huì)在崩潰前主動(dòng)進(jìn)行下線，那么searcher會(huì)將流量自動(dòng)分發(fā)到剩余的shard列節(jié)點(diǎn)中。

9.Search分布式數(shù)據(jù)流的設(shè)計(jì)

Search是有狀態(tài)的檢索服務(wù)，會(huì)有一直寫(xiě)入的實(shí)時(shí)數(shù)據(jù)也有每天或者每小時(shí)更新的離線數(shù)據(jù)到引擎中，數(shù)據(jù)的可靠更新非常重要，對(duì)于分布式而言，各個(gè)分片的產(chǎn)出更新和實(shí)時(shí)數(shù)據(jù)的寫(xiě)入都是非常重要的一環(huán)。

1. 引擎分為實(shí)時(shí)和離線，在引擎的構(gòu)建系統(tǒng)中會(huì)根據(jù)中臺(tái)中設(shè)置的總分片數(shù)來(lái)對(duì)原始數(shù)據(jù)進(jìn)行平均分片，分片邏輯是根據(jù)每條數(shù)據(jù)的主鍵ID取Hash然后同余，然后給構(gòu)建系統(tǒng)進(jìn)行構(gòu)建索引，最后構(gòu)建完的索引統(tǒng)一放在Search的HDFS路徑下。
2. 實(shí)時(shí)數(shù)據(jù)通過(guò)Kafka匯總后，各個(gè)shard分片會(huì)統(tǒng)一消費(fèi)Kafka中的數(shù)據(jù)，然后根據(jù)數(shù)據(jù)中的主鍵ID進(jìn)行Hash后同余判斷是不是自己所在的分片最后判斷是否寫(xiě)入自己所在的索引。
3. 對(duì)于一致性的處理，因?yàn)橥粋€(gè)shard分片中的多個(gè)副本中的消費(fèi)速度不同，理論上只能保證同一個(gè)分片中多個(gè)副本的最終一致性，即存在某一個(gè)時(shí)刻有一個(gè)數(shù)據(jù)最先到一個(gè)分片中那一瞬間優(yōu)先檢索出來(lái)，而同樣的搜索詞可能在其他分片中檢索不出來(lái)，不過(guò)這種情況幾乎會(huì)感知不到，因?yàn)槎鄠€(gè)副本的消費(fèi)速度都是在每秒處理幾萬(wàn)到十萬(wàn)級(jí)別的數(shù)據(jù)，也就是說(shuō)Search增量寫(xiě)入能力單條都在1ms以下，除非出現(xiàn)其中一個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)問(wèn)題或者磁盤(pán)異常情況會(huì)出現(xiàn)寫(xiě)入出現(xiàn)問(wèn)題，最終出現(xiàn)某些節(jié)點(diǎn)數(shù)據(jù)檢索異常，不過(guò)這些異常都會(huì)通過(guò)報(bào)警及時(shí)報(bào)警，進(jìn)行節(jié)點(diǎn)處理。

10.總結(jié)

本篇文章主要是對(duì)搜索引擎分布式的設(shè)計(jì)和落地做了總結(jié)，主要的幾個(gè)重要部分是，如何設(shè)計(jì)一套有狀態(tài)的分布式系統(tǒng)，其中最主要的核心部分是如何對(duì)各個(gè)節(jié)點(diǎn)的狀態(tài)變化做處理，以及合理的對(duì)數(shù)據(jù)進(jìn)行分片和處理。其中ZK的路徑節(jié)點(diǎn)設(shè)計(jì)，自動(dòng)擴(kuò)縮容的實(shí)現(xiàn)，客戶端的服務(wù)發(fā)現(xiàn)，狀態(tài)感知功能，都是其中核心部分。