lucene動態分片簡介

最近開發的搜索引擎中，需要對索引進行分片。根據項目的需求，我們提供了兩種分片方式。過程博客記錄一下。

Hash算法

原理很簡單，通過行鍵（_id）的Hash值確定所在的分片，然后再進行操作。

舉個栗（例）子，現在有個索引，初始化5個分片，分別為shard0， shard1， shard2， shard3， shard4。
現在需要保存一行數據，_id為0001000000123，_id的HashCode為1571574097，對5求余（1571574097 % 5）為2，從而確定數據應該保存在shard2。下面是一個簡單的圖解：

Hash算法分片實現非常簡單，計算過程只需要知道分片數量即可完成定位。但也正因為分片數量是算法的一部分，修改分片數量的代價也非常昂貴。

有一種解決方案是重新排列，比如從M個分片切增加到N個分片，先將每個分片切分為N個小分片，然后再將所有小分片合并為大分片。從網絡上復制了一張圖解說明，

這種方式的優點是，可以任意設定新的分片數量。缺點是需要對所有數據進行重新排列，如果數據量很大，可能會非常耗時。

當然，由于項目數據增長是不可預測性，我們沒有選擇上面增片方式，而是選擇了另外一種增片的方式。

動態分片

結合Hash算法和二叉樹的原理，進行動態增加分片。

首先，Hash算法與之前一樣，搜索創建時，可以設置一個初始化的分片數量，例如初始化5個分片，分別為shard_0， shard_1， shard_2， shard_3， shard_4。添加數據時，通過_id的Hash值確定數據需要保存到哪個分片。不同的是，我們設置了每個分片的最大行數，當某個分片的數量達到最大行數時，該分片會分拆分為兩個小的分片，并且作為當前分片的子分片。

例如，設置分片最大行數為1000萬，當shard_2超過1000萬時，分裂為兩個子分片shard_2_2和shard_2_7。如果shard_2_2數據繼續增長到1000萬，則分裂子分片shard_2_2_2和shard_2_2_12。

從示例中可以看出，分裂并不是毫無規則，假設分片的初始數量為m，k表示二叉樹深度，則分片n的分裂規則為

shard_n 分裂為 shard_n_n和shard_n_(n + m * 1)

shard_n_n 分裂為 shard_n_n_n和shard_n_n_(n + m * 2)

shard_n_(n + m * 1) 分裂為 shard_n_(n + m * 1)_(n + m * 1) 和 shard_n_(n + m * 1)_(n + m * 1 + m * 2)

...

上面的公式看起來很復雜，我們使用圖解來說明分裂過程

如果還沒有明白，我們可以通過_id尋找對應的分片來梳理一下思路，還是上面的例子，

需要保存一行數據，_id為0001000000123，_id的HashCode為1571574097，對5求余（1571574097 % 5）為2，從而確定數據應該保存在shard_2。

shard_2已經分裂為shard_2_2和shard_2_7兩個子分片了，這一層的基數為10（基數=初始化分片數量*層數），我們將1571574097對10求余(1571574097 % 10)為7,則數據保存在shard_2_7。

shard_2_7沒有子分片，說明該分片沒有分裂，直接保存在該分片即可。

分析一下分片尋找原理：

1. 按照hash算法找到分片；
   

2. 如果分片有子分片，則從子分片中查找；

3. 如果分片沒有子分片，則數據保存在該分片；
   

再來分析一下分片分裂規則，為什么shard_1會分裂為shard_1_1和shard_1_6？

原因很簡單，shard_1表示id的hash值對5取余后值為1，如果shard_1分裂為2份，則第2層的基數10=上一層基數*2，即5 * 2。對5取余值為1，那么對10取余結果只會是1和6，因此

shard_1分裂為shard_1_1和shard_1_6。

數據一致性

動態分片是在使用過程中自動分片，分片過程會非常長，經過測試，索引32列500萬行的分裂為兩個子分片，耗時245秒。分裂過程如果原始數據發生修改，這些修改可能會丟失。因此，在分裂過程中需要一定的措施保障數據安全性。

方法一，使用悲觀鎖。

    分裂前對鎖定分片不能再修改，直到分裂完成后才能再修改。

    優點：邏輯簡單粗暴，開發難度低。

    缺點：鎖的時間太長可能會導致調用服務方產生大量的異常請求。

方法二，使用事務日志。

    分裂前創建事務日志，當前shard所有新增、修改和刪除操作都寫入事務日志。分裂完成后，鎖定分片和子分片，從事務日志中恢復數據到子分片，然后解鎖。

    優點：只有在創建事務日志和恢復數據時會鎖定分片，鎖定時間比較短暫，影響服務調用方幾乎不受影響。

    缺點：開發難度大，需要開發一套事務日志和日志恢復操作接口。但是底層lucene存儲已經有一套事務日志接口和實現，該缺點幾乎可以忽略。

行鍵遞增分片

    如果保存數據的行鍵整體上是遞增的，例如，行鍵是000000001,000000002,000000003,...這種格式，可以按行鍵進行分片。這種分片實現方式比較簡單，

    1. 創建索引時設置一個初始化分片；

    2. 添加數據過程中，并且記錄分片行鍵最小值minId和最大值maxId；

    3. 當分片數據量超過設置的最大值是，創建一個新的分片，新增的數據保存在該分片；

    4. 更新數據時，通過與每個分片的minId和maxId比較，確定所在的分片。

行鍵遞增分片與Hash算法分片比較：

    1.行鍵遞增分片方式實現更簡單，開發成本更低；

    2.行鍵遞增分片通過minId和maxId定位分片，如果每個分片信息中需要記錄分片的minId和maxId；

    3.行鍵遞增分片存入數據時，需要按照一定的順序存入，否則可能會導致數據傾斜；

    4.行鍵遞增分片按需添加分片，只需要設置每個分片的最大行數，沒有分裂過程；

    5.行鍵遞增分片大量的壓力集中在最新的分片上，Hash算法分片壓力分散到各個分片，理論上Hash算法分片可以支持更高的吞吐量。