1.引言

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

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

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

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

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

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

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

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

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

搜索服務(wù)作為有狀態(tài)的服務(wù)，需要索引大量的數(shù)據(jù)，同時更為重要的是索引數(shù)據(jù)不僅每時每刻都在寫入，而且需要保證天級別或者小時級別的全量數(shù)據(jù)更新，對于一個在線服務(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模塊是整個搜索引擎的核心部分，其主要的功能包含了每個獨立的檢索單元，主要的框架模塊包含以下部分：

5.1 索引

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

• 正排索引?

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

倒排索引

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

數(shù)組

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

跳表(SkipList)

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

Bitmap

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

Roaring Bitmap

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

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

Term索引

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

向量索引

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

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進行橫向切分，Route會根據(jù)在ZK路徑中保存的分片信息來對請求進行分片，比如請求中會帶最大召回截斷fulllimit，R oute會根據(jù)fulllimit的值同時根據(jù)分片個數(shù)進行分配，然后分發(fā)到各個shard節(jié)點上去。

• Merge模塊

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

6.2 排序框架

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

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

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

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

8.Search分布式節(jié)點的設(shè)計

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

8.1 各個節(jié)點的設(shè)計

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

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

8.2 shard節(jié)點和searcher節(jié)點的請求設(shè)計

在shard的節(jié)點設(shè)計中沒有進行區(qū)分主副本，各個副本之前都是有請求流量，之所以這么考慮是因為提高機器利用率，只是簡單副本價值不大，所以所有副本權(quán)重平衡全部接流量。

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

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

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

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

10.總結(jié)

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