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的路徑節點設計，自動擴縮容的實現，客戶端的服務發現，狀態感知功能，都是其中核心部分。