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ī)上，彼此之間僅僅通過消息傳遞進(jìn)行通信和協(xié)調(diào)的系統(tǒng)。當(dāng)單機(jī)系統(tǒng)在請求量或者數(shù)據(jù)量無法承載的時(shí)候，需要考慮對系統(tǒng)進(jìn)行合理的分布式改造和部署。

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

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

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

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

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

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

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

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

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

1. shard(核心檢索邏輯和索引分片)
2. searcher(檢索和請求分發(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的映射，在檢索中需要保證倒排鏈有高效的讀寫能力，讀能力利于高效進(jìn)行復(fù)雜的檢索語法操作，比如AND、OR、NOT等復(fù)雜的操作。同時(shí)倒排鏈的數(shù)據(jù)結(jié)構(gòu)還需要高效的寫能力，在引擎檢索的同時(shí)需要將實(shí)時(shí)數(shù)據(jù)寫入到引擎，不可避免的需要修改倒排鏈，所以高效的寫能力也比較關(guān)鍵。

數(shù)組

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

跳表(SkipList)

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

Bitmap

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

Roaring Bitmap

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

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

Term索引

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

向量索引

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

5.2 查詢排序

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

6.searcher模塊

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

6.1 查詢路由

• Route模塊

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

• Merge模塊

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

6.2 排序框架

searcher中排序框架，主要是對全局的最后結(jié)果進(jìn)行重新的排序，比如歌曲中會對最終的歌曲檢索統(tǒng)一進(jìn)行打分，每個(gè)shard將對應(yīng)的歌曲歸一化分?jǐn)?shù)上傳給searcher模塊，最終將分?jǐn)?shù)進(jìn)行統(tǒng)一的排序。同時(shí)，排序框架支持自定義開發(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ù)端和客戶端，通過ZK來交互，ZK上存放了每個(gè)集群的機(jī)器IP和端口，客戶端來監(jiān)聽該路徑的變化，當(dāng)任意列表中IP刪除后，ZK回調(diào)客戶端來感知，客戶端將流量從該臺機(jī)器切走。同時(shí)客戶端和服務(wù)端之間存在心跳，用于服務(wù)端服務(wù)卡死等異常情況下流量切流。

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

帶有狀態(tài)的分布式系統(tǒng)最復(fù)雜的莫過于對于異常的處理了，包括數(shù)據(jù)的更新和節(jié)點(diǎn)異常的處理，對于Search來言數(shù)據(jù)的更新會導(dǎo)致節(jié)點(diǎn)的上下線，包括狀態(tài)的變化，而集群的擴(kuò)縮容會導(dǎo)致各個(gè)節(jié)點(diǎn)劇烈變化帶來異常，同時(shí)某個(gè)節(jié)點(diǎ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)來組件整體的分布式系統(tǒng)。

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

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

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

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

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

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

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

10.總結(jié)

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