最近開發(fā)的搜索引擎中，需要對索引進(jìn)行分片。根據(jù)項(xiàng)目的需求，我們提供了兩種分片方式。過程博客記錄一下。

創(chuàng)新互聯(lián)建站從2013年開始，先為清徐等服務(wù)建站，清徐等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為清徐企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

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，對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)是需要對所有數(shù)據(jù)進(jìn)行重新排列，如果數(shù)據(jù)量很大，可能會非常耗時(shí)。

當(dāng)然，由于項(xiàng)目數(shù)據(jù)增長是不可預(yù)測性，我們沒有選擇上面增片方式，而是選擇了另外一種增片的方式。

動態(tài)分片

結(jié)合Hash算法和二叉樹的原理，進(jìn)行動態(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í)，該分片會分拆分為兩個(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尋找對應(yīng)的分片來梳理一下思路，還是上面的例子，

需要保存一行數(shù)據(jù)，_id為0001000000123，_id的HashCode為1571574097，對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對10求余(1571574097 % 10)為7,則數(shù)據(jù)保存在shard_2_7。

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

分析一下分片尋找原理：

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

   
   

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

3. 如果分片沒有子分片，則數(shù)據(jù)保存在該分片；

   
   

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

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

shard_1分裂為shard_1_1和shard_1_6。

數(shù)據(jù)一致性

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

方法一，使用悲觀鎖。

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

    優(yōu)點(diǎn)：邏輯簡單粗暴，開發(fā)難度低。

    缺點(diǎn)：鎖的時(shí)間太長可能會導(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í)會鎖定分片，鎖定時(shí)間比較短暫，影響服務(wù)調(diào)用方幾乎不受影響。

    缺點(diǎn)：開發(fā)難度大，需要開發(fā)一套事務(wù)日志和日志恢復(fù)操作接口。但是底層lucene存儲已經(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í)，需要按照一定的順序存入，否則可能會導(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)用場景需求。

名稱欄目：lucene動態(tài)分片簡介-創(chuàng)新互聯(lián)
當(dāng)前網(wǎng)址：http://m.newbst.com/article30/hjsso.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、響應(yīng)式網(wǎng)站、全網(wǎng)營銷推廣、定制開發(fā)、網(wǎng)站策劃、網(wǎng)站設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)