最近開發(fā)的搜索引擎中，需要對(duì)索引進(jìn)行分片。根據(jù)項(xiàng)目的需求，我們提供了兩種分片方式。過程博客記錄一下。
Hash算法
原理很簡單，通過行鍵（_id）的Hash值確定所在的分片，然后再進(jìn)行操作。
舉個(gè)栗（例）子，現(xiàn)在有個(gè)索引，初始化5個(gè)分片，分別為shard0， shard1， shard2， shard3， shard4。
現(xiàn)在需要保存一行數(shù)據(jù)，_id為0001000000123，_id的HashCode為1571574097，對(duì)5求余（1571574097 % 5）為2，從而確定數(shù)據(jù)應(yīng)該保存在shard2。下面是一個(gè)簡單的圖解：
Hash算法分片實(shí)現(xiàn)非常簡單，計(jì)算過程只需要知道分片數(shù)量即可完成定位。但也正因?yàn)榉制瑪?shù)量是算法的一部分，修改分片數(shù)量的代價(jià)也非常昂貴。
有一種解決方案是重新排列，比如從M個(gè)分片切增加到N個(gè)分片，先將每個(gè)分片切分為N個(gè)小分片，然后再將所有小分片合并為大分片。從網(wǎng)絡(luò)上復(fù)制了一張圖解說明，
這種方式的優(yōu)點(diǎn)是，可以任意設(shè)定新的分片數(shù)量。缺點(diǎn)是需要對(duì)所有數(shù)據(jù)進(jìn)行重新排列，如果數(shù)據(jù)量很大，可能會(huì)非常耗時(shí)。
當(dāng)然，由于項(xiàng)目數(shù)據(jù)增長是不可預(yù)測性，我們沒有選擇上面增片方式，而是選擇了另外一種增片的方式。
動(dòng)態(tài)分片
結(jié)合Hash算法和二叉樹的原理，進(jìn)行動(dòng)態(tài)增加分片。
首先，Hash算法與之前一樣，搜索創(chuàng)建時(shí)，可以設(shè)置一個(gè)初始化的分片數(shù)量，例如初始化5個(gè)分片，分別為shard_0， shard_1， shard_2， shard_3， shard_4。添加數(shù)據(jù)時(shí)，通過_id的Hash值確定數(shù)據(jù)需要保存到哪個(gè)分片。不同的是，我們設(shè)置了每個(gè)分片的大行數(shù)，當(dāng)某個(gè)分片的數(shù)量達(dá)到大行數(shù)時(shí)，該分片會(huì)分拆分為兩個(gè)小的分片，并且作為當(dāng)前分片的子分片。
例如，設(shè)置分片大行數(shù)為1000萬，當(dāng)shard_2超過1000萬時(shí)，分裂為兩個(gè)子分片shard_2_2和shard_2_7。如果shard_2_2數(shù)據(jù)繼續(xù)增長到1000萬，則分裂子分片shard_2_2_2和shard_2_2_12。
從示例中可以看出，分裂并不是毫無規(guī)則，假設(shè)分片的初始數(shù)量為m，k表示二叉樹深度，則分片n的分裂規(guī)則為
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)
...
上面的公式看起來很復(fù)雜，我們使用圖解來說明分裂過程
如果還沒有明白，我們可以通過_id尋找對(duì)應(yīng)的分片來梳理一下思路，還是上面的例子，
需要保存一行數(shù)據(jù)，_id為0001000000123，_id的HashCode為1571574097，對(duì)5求余（1571574097 % 5）為2，從而確定數(shù)據(jù)應(yīng)該保存在shard_2。
shard_2已經(jīng)分裂為shard_2_2和shard_2_7兩個(gè)子分片了，這一層的基數(shù)為10（基數(shù)=初始化分片數(shù)量*層數(shù)），我們將1571574097對(duì)10求余(1571574097 % 10)為7,則數(shù)據(jù)保存在shard_2_7。
shard_2_7沒有子分片，說明該分片沒有分裂，直接保存在該分片即可。
分析一下分片尋找原理：
按照hash算法找到分片；
如果分片有子分片，則從子分片中查找；
如果分片沒有子分片，則數(shù)據(jù)保存在該分片；
再來分析一下分片分裂規(guī)則，為什么shard_1會(huì)分裂為shard_1_1和shard_1_6？
原因很簡單，shard_1表示id的hash值對(duì)5取余后值為1，如果shard_1分裂為2份，則第2層的基數(shù)10=上一層基數(shù)*2，即5 * 2。對(duì)5取余值為1，那么對(duì)10取余結(jié)果只會(huì)是1和6，因此
shard_1分裂為shard_1_1和shard_1_6。
數(shù)據(jù)一致性
動(dòng)態(tài)分片是在使用過程中自動(dòng)分片，分片過程會(huì)非常長，經(jīng)過測試，索引32列500萬行的分裂為兩個(gè)子分片，耗時(shí)245秒。分裂過程如果原始數(shù)據(jù)發(fā)生修改，這些修改可能會(huì)丟失。因此，在分裂過程中需要一定的措施保障數(shù)據(jù)安全性。
方法一，使用悲觀鎖。
分裂前對(duì)鎖定分片不能再修改，直到分裂完成后才能再修改。
優(yōu)點(diǎn)：邏輯簡單粗暴，開發(fā)難度低。
缺點(diǎn)：鎖的時(shí)間太長可能會(huì)導(dǎo)致調(diào)用服務(wù)方產(chǎn)生大量的異常請求。
方法二，使用事務(wù)日志。
分裂前創(chuàng)建事務(wù)日志，當(dāng)前shard所有新增、修改和刪除操作都寫入事務(wù)日志。分裂完成后，鎖定分片和子分片，從事務(wù)日志中恢復(fù)數(shù)據(jù)到子分片，然后解鎖。
優(yōu)點(diǎn)：只有在創(chuàng)建事務(wù)日志和恢復(fù)數(shù)據(jù)時(shí)會(huì)鎖定分片，鎖定時(shí)間比較短暫，影響服務(wù)調(diào)用方幾乎不受影響。
缺點(diǎn)：開發(fā)難度大，需要開發(fā)一套事務(wù)日志和日志恢復(fù)操作接口。但是底層lucene存儲(chǔ)已經(jīng)有一套事務(wù)日志接口和實(shí)現(xiàn)，該缺點(diǎn)幾乎可以忽略。
行鍵遞增分片
如果保存數(shù)據(jù)的行鍵整體上是遞增的，例如，行鍵是000000001,000000002,000000003,...這種格式，可以按行鍵進(jìn)行分片。這種分片實(shí)現(xiàn)方式比較簡單，
1. 創(chuàng)建索引時(shí)設(shè)置一個(gè)初始化分片；
2. 添加數(shù)據(jù)過程中，并且記錄分片行鍵最小值minId和大值maxId；
3. 當(dāng)分片數(shù)據(jù)量超過設(shè)置的大值是，創(chuàng)建一個(gè)新的分片，新增的數(shù)據(jù)保存在該分片；
4. 更新數(shù)據(jù)時(shí)，通過與每個(gè)分片的minId和maxId比較，確定所在的分片。
行鍵遞增分片與Hash算法分片比較：
1.行鍵遞增分片方式實(shí)現(xiàn)更簡單，開發(fā)成本更低；
2.行鍵遞增分片通過minId和maxId定位分片，如果每個(gè)分片信息中需要記錄分片的minId和maxId；
3.行鍵遞增分片存入數(shù)據(jù)時(shí)，需要按照一定的順序存入，否則可能會(huì)導(dǎo)致數(shù)據(jù)傾斜；
4.行鍵遞增分片按需添加分片，只需要設(shè)置每個(gè)分片的大行數(shù)，沒有分裂過程；
5.行鍵遞增分片大量的壓力集中在最新的分片上，Hash算法分片壓力分散到各個(gè)分片，理論上Hash算法分片可以支持更高的吞吐量。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
重慶分公司
重慶分公司
