面向主從區(qū)塊鏈的多級索引構(gòu)建方法

王俊陸 張桂月 杜立寬 李 素 陳廷偉

（遼寧大學(xué)信息學(xué)院 沈陽 110036）

區(qū)塊鏈通過塊鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)存儲并驗(yàn)證數(shù)據(jù)，輔以密碼學(xué)[1-2]方法保證數(shù)據(jù)傳輸和訪問的安全性，具有高可信[3]、可回溯、去中心化[4]等特點(diǎn)，能夠很好地解決數(shù)據(jù)存儲對第三方的信任問題[5].隨著區(qū)塊鏈技術(shù)的發(fā)展以及各行業(yè)數(shù)據(jù)規(guī)模的累計，傳統(tǒng)的單鏈結(jié)構(gòu)區(qū)塊鏈系統(tǒng)已經(jīng)無法滿足愈發(fā)復(fù)雜的領(lǐng)域應(yīng)用場景，主從區(qū)塊鏈（master-slave blockchain，MSBC）結(jié)構(gòu)，如星火鏈、COSMOS 等，開始受到領(lǐng)域?qū)＜覍W(xué)者的關(guān)注，并逐步在教育、醫(yī)療、安全[6]等領(lǐng)域廣泛應(yīng)用[7-10].主從區(qū)塊鏈通常包括主鏈和從屬鏈2 部分，分別由主區(qū)塊和從屬區(qū)塊組成，每個主區(qū)塊有且只有一個從屬鏈.各個主區(qū)塊和從屬區(qū)塊之間分別通過前一個主區(qū)塊和從屬區(qū)塊的哈希值相連，主區(qū)塊與從屬鏈通過唯一的哈希值進(jìn)行映射.

主從區(qū)塊鏈結(jié)構(gòu)可以應(yīng)對復(fù)雜分類場景的應(yīng)用.如金融領(lǐng)域中，采用主從區(qū)塊鏈構(gòu)建面向金融活動的企業(yè)區(qū)塊鏈系統(tǒng)，主鏈中存儲金融企業(yè)屬性信息，對應(yīng)的從屬鏈存儲其交易事件、金融活動等數(shù)據(jù)，通過區(qū)塊鏈的共識機(jī)制[11-12]保證數(shù)據(jù)不可篡改.

隨著領(lǐng)域數(shù)據(jù)規(guī)模的不斷增大，主從區(qū)塊鏈系統(tǒng)存在的查詢效率低、溯源時間長等問題[13-14]愈發(fā)嚴(yán)重.而現(xiàn)有區(qū)塊鏈索引方法多只適用于單一鏈結(jié)構(gòu)，且查詢效率和索引構(gòu)建時間均較差.因此，如何針對主從區(qū)塊鏈建立高效、可動態(tài)維護(hù)的索引結(jié)構(gòu)，成為領(lǐng)域研究的熱點(diǎn)和難點(diǎn).

針對上述問題，本文提出一種面向主從區(qū)塊鏈的多級索引構(gòu)建方法（multi-level index construction method for master-slave blockchain，MSMLI）.主要貢獻(xiàn)有4 個方面：

1）綜合節(jié)點(diǎn)負(fù)載、節(jié)點(diǎn)信用和網(wǎng)絡(luò)質(zhì)量構(gòu)建權(quán)重矩陣，提出一種基于權(quán)重矩陣的區(qū)塊鏈分片算法（weighted matrix-based blockchain sharding algorithm，WMBS），基于主鏈特征實(shí)現(xiàn)主從區(qū)塊鏈結(jié)構(gòu)的動態(tài)分片；

2）在此基礎(chǔ)上，針對現(xiàn)有區(qū)塊鏈索引不適用于主從鏈結(jié)構(gòu)的問題，提出基于跳躍一致性哈希的主鏈索引構(gòu)建算法（master chain index construction algorithm based on jump consistent Hash，JHMI），通過主鏈的節(jié)點(diǎn)關(guān)鍵值與索引槽位映射，實(shí)現(xiàn)主鏈信息的高效查詢；

3）結(jié)合區(qū)塊鏈的數(shù)據(jù)特點(diǎn)，提出基于改進(jìn)布隆過濾器的從屬鏈索引構(gòu)建算法（construction algorithm for subordinate chain indexes based on improved Bloom filters，IBF），優(yōu)化基于列的選擇函數(shù)，并給出索引查詢方法；

4）在不同約束條件和數(shù)據(jù)集上與現(xiàn)有方法進(jìn)行對比實(shí)驗(yàn)，驗(yàn)證本文所提方法的有效性.

1 相關(guān)工作

目前，許多學(xué)者對于區(qū)塊鏈的索引構(gòu)建問題進(jìn)行了深入研究，取得了一定研究成果.

文獻(xiàn)[15]提出一種多維內(nèi)存讀取優(yōu)化的索引方法Flood，通過聯(lián)合優(yōu)化索引結(jié)構(gòu)和數(shù)據(jù)存儲布局，自動適應(yīng)特定的數(shù)據(jù)集和工作負(fù)載.但是該方法無法檢測到查詢分布何時發(fā)生了足夠大的變化，需要定期評估當(dāng)前布局的查詢成本對不同的工作負(fù)載完全重建索引.文獻(xiàn)[16] 提出一種基于B 級樹的索引方法EBTree，支持對以太坊區(qū)塊鏈數(shù)據(jù)的實(shí)時top-k、范圍、等價搜索，但是該方法的索引節(jié)點(diǎn)均在Level DB 中單獨(dú)存儲，且查詢效率受節(jié)點(diǎn)大小影響較大.文獻(xiàn)[17] 提出一種單通道學(xué)習(xí)索引RS（radix spline）方法，可以在排序數(shù)據(jù)的單次傳遞中構(gòu)建，且只需要2 個數(shù)據(jù)集，對大多數(shù)數(shù)據(jù)集友好，但是該方法會隨著數(shù)據(jù)集的增長降低性能.文獻(xiàn)[18]提出一種基于子鏈賬戶交易鏈的索引方法SCATC，將交易鏈劃分為子鏈并在每個子鏈的最后一個區(qū)塊的賬戶分支節(jié)點(diǎn)上添加哈希指針連接每個子鏈，通過指針將遍歷交易鏈的查詢模式轉(zhuǎn)化為子鏈查詢來減少計算開銷，但是該方法僅對較長賬戶交易鏈的查詢效率有所改善且只針對明文狀態(tài)下的查詢優(yōu)化，無法保證數(shù)據(jù)隱私性.文獻(xiàn)[19]提出一種用于大時間序列數(shù)據(jù)的可擴(kuò)展分布式索引方法ChainLink，設(shè)計了一個2 層分布式索引結(jié)構(gòu)，使用單通道簽名對數(shù)據(jù)進(jìn)行散列，利用分區(qū)級數(shù)據(jù)重組來實(shí)現(xiàn)查詢操作，但是該方法需要在本地對數(shù)據(jù)重組，無法保障數(shù)據(jù)安全性.文獻(xiàn)[20]提出一種基于中間層的可擴(kuò)展學(xué)習(xí)索引模型Dabble，使用K-means 聚類算法，根據(jù)數(shù)據(jù)分布將數(shù)據(jù)集劃分為K個區(qū)域并分別使用神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)和訓(xùn)練，通過神經(jīng)網(wǎng)絡(luò)模型預(yù)測數(shù)據(jù)位置，但是該方法在數(shù)據(jù)集更新時需要重新訓(xùn)練模型，時效性較差，并且K值對模型的準(zhǔn)確性影響較大.

2 基于主從結(jié)構(gòu)的區(qū)塊鏈分片方法

為實(shí)現(xiàn)主從區(qū)塊鏈結(jié)構(gòu)的高效索引構(gòu)建和查詢處理，基于主鏈特征對整個主從區(qū)塊鏈分片，并對各個分片賦予權(quán)重，據(jù)此構(gòu)建整個主從區(qū)塊鏈結(jié)構(gòu)的分片權(quán)重矩陣；基于權(quán)重矩陣確定分片中的節(jié)點(diǎn)數(shù)目，為主鏈和從屬區(qū)塊鏈構(gòu)建索引提供支撐.

2.1 權(quán)重矩陣構(gòu)建

設(shè)主從區(qū)塊鏈的節(jié)點(diǎn)數(shù)目為x，主從區(qū)塊鏈分為y(y?x)個分片，第i個分片為fi(i=0,1,…,y-1)，各個分片權(quán)重為 ωi.分片權(quán)重由節(jié)點(diǎn)負(fù)載、節(jié)點(diǎn)信用、網(wǎng)絡(luò)質(zhì)量3 個維度的權(quán)重決定，其中節(jié)點(diǎn)信用和網(wǎng)絡(luò)質(zhì)量與分片權(quán)重呈正相關(guān)，節(jié)點(diǎn)負(fù)載與分片權(quán)重呈負(fù)相關(guān)，各項(xiàng)維度的權(quán)重由實(shí)驗(yàn)效果最佳的比例決定.在進(jìn)行分片權(quán)重計算前，由于上述3 個維度的單位不統(tǒng)一，因此需進(jìn)行歸一化處理.節(jié)點(diǎn)負(fù)載的歸一化公式為

節(jié)點(diǎn)信用和網(wǎng)絡(luò)質(zhì)量的歸一化公式為

第i個分片的權(quán)重為 ωi，計算公式為

設(shè)2 維權(quán)重矩陣M的各個元素由分片權(quán)重組成，獲得各個分片的權(quán)重后，使用各個分片權(quán)重 ωi構(gòu)建2維權(quán)重矩陣Mp×q（其中p≤，q≤+1，p，q為整數(shù)）.對于任意一個分片f，都有M[f/p][f%q]=ωf，矩陣中為空的元素置為0.

2.2 基于權(quán)重矩陣確定片內(nèi)節(jié)點(diǎn)數(shù)目

基于2.1 節(jié)的權(quán)重矩陣，確定各個分片內(nèi)的節(jié)點(diǎn)數(shù)目.首先，對矩陣中的分片權(quán)重進(jìn)行線性歸一化處理.其次，對歸一化后的所有分片權(quán)重按照比例離散，設(shè)離散比例權(quán)重值區(qū)間為[1,Q].最終獲得分片比例權(quán)重Q－1，即該分片將對應(yīng)Q－1 個節(jié)點(diǎn).

線性歸一化后的分片權(quán)重的公式為

其中的ωmin為所有分片權(quán)重 ωi中的最小值，ωmax為最大值.

基于2.1 節(jié)的權(quán)重矩陣的構(gòu)建過程，提出了一種基于權(quán)重矩陣的區(qū)塊鏈分片算法WMBS，其通過跳躍搜索（jump search，JPS）算法快速進(jìn)行區(qū)塊鏈分片與節(jié)點(diǎn)的映射，實(shí)現(xiàn)了主從區(qū)塊鏈結(jié)構(gòu)的分片.WMBS 將節(jié)點(diǎn)關(guān)鍵值key、隨機(jī)數(shù)r和權(quán)重矩陣作為輸入，基于JPS 使節(jié)點(diǎn)與分片逐一映射.key在節(jié)點(diǎn)加入?yún)^(qū)塊鏈時創(chuàng)立，為32 b 節(jié)點(diǎn)關(guān)鍵值，其由8 b 的分片地址碼和24 b 的節(jié)點(diǎn)隨機(jī)碼組成，是節(jié)點(diǎn)的唯一標(biāo)識；r是一個在[0,1]區(qū)間內(nèi)均勻分布的隨機(jī)數(shù)，由線性同余隨機(jī)數(shù)發(fā)生器生成.WMBS 算法如算法1所示.

算法1.WMBS 算法.

算法2.JPS 算法.

3 多級索引構(gòu)建方法

由于主從區(qū)塊鏈結(jié)構(gòu)的主鏈和從屬鏈存儲的數(shù)據(jù)規(guī)模和信息類型均不同，通過WMBS 算法分片后，本文提出一種面向主從區(qū)塊鏈的多級索引構(gòu)建方法（MSMLI），以滿足主鏈和從屬鏈的查詢需求.多級索引構(gòu)建示意圖如圖1 所示.

圖1 多級索引構(gòu)建示意圖Fig.1 Multi-level index construction schematic

如圖1 所示，在主鏈中，通過JHMI 建立1 級索引.在從屬鏈中，引入IBF 建立2 級索引，2 級索引通過節(jié)點(diǎn)關(guān)鍵值進(jìn)行關(guān)聯(lián).當(dāng)查詢發(fā)生時，首先在主鏈索引中檢索節(jié)點(diǎn)關(guān)鍵值，得到查詢結(jié)果后，基于該結(jié)果在從屬鏈索引中通過節(jié)點(diǎn)關(guān)鍵值獲得元素信息.

3.1 基于跳躍一致性哈希的主鏈索引構(gòu)建

基于主鏈存儲的數(shù)據(jù)特點(diǎn)，本文引入跳躍一致性哈希算法，提出JHMI，實(shí)現(xiàn)主鏈索引的快速構(gòu)建.首先，根據(jù)各主鏈分片上的節(jié)點(diǎn)數(shù)量確定索引的槽位數(shù)量；其次，根據(jù)主鏈存儲數(shù)據(jù)的哈希值確定各個節(jié)點(diǎn)關(guān)鍵值；最后，輸入節(jié)點(diǎn)關(guān)鍵值和索引槽位數(shù)量，輸出主鏈索引.

當(dāng)分片中節(jié)點(diǎn)數(shù)量發(fā)生變化時，節(jié)點(diǎn)在索引中發(fā)生跳躍變化，部分節(jié)點(diǎn)重新映射.設(shè)產(chǎn)生跳躍變化的哈希映射函數(shù)為ch（key,num_buckets），key為節(jié)點(diǎn)關(guān)鍵值，num_buckets為槽位數(shù)量，可得：1）num_buckets= 1 時，只有1 個槽位，所有key都映射到1 個槽位中，即ch（key,num_buckets） = 0，所有節(jié)點(diǎn)都劃分在0 號槽位；2）num_buckets= 2 時，有1/2 的節(jié)點(diǎn)在ch（key,num_buckets） = 0，有K/ 2 個key重新映射即ch（key,num_buckets） = 1，跳躍到1 號槽位；3）當(dāng)槽位數(shù)從n變?yōu)閚+1 時，有n/（n＋1） 的節(jié)點(diǎn)所在的槽位保持不變，即ch（key,num_buckets） =n-1，有1/（n+1）個key需要重新映射，即ch（key,num_buckets） =n.

設(shè)b為節(jié)點(diǎn)上一次跳變的結(jié)果，j為發(fā)生跳變前最后一次槽位擴(kuò)充時槽位的數(shù)量，當(dāng)分片內(nèi)節(jié)點(diǎn)數(shù)量發(fā)生變化時，節(jié)點(diǎn)重新映射的示意圖如圖2 所示.

圖2 節(jié)點(diǎn)重新映射圖Fig.2 Diagram of node remapping

由圖2 可知，對于任意的i∈[b+1,j-1]，增加節(jié)點(diǎn)數(shù)量且沒有發(fā)生跳變的概率為

在[0,1]區(qū)間取一個均勻分布的隨機(jī)數(shù)r，由式（5）可得，當(dāng)r＜(b+1)/r時，節(jié)點(diǎn)就會跳變成j，則i的上界為(b+1)/r.由于對任意的i都有j≥i，則j=floor((b+1)/r).JHMI 算法如算法3 所示.

算法3.JHMI 算法.

輸入：節(jié)點(diǎn)關(guān)鍵值key，槽位數(shù)量num_buckets和空主鏈索引s；

3.2 基于改進(jìn)布隆過濾器的從屬鏈索引構(gòu)建

從屬鏈存儲的數(shù)據(jù)具有規(guī)模大、多源異構(gòu)的特點(diǎn)，因此，在從屬鏈索引構(gòu)建過程中，本文重構(gòu)布隆過濾器數(shù)據(jù)結(jié)構(gòu)，提出IBF 算法.

首先構(gòu)建基于改進(jìn)布隆過濾器的從屬鏈索引的數(shù)據(jù)結(jié)構(gòu)為2 維數(shù)組A[p][q]，其中p=2n（n為正整數(shù)），q中的數(shù)據(jù)長度為lq，設(shè)lq=32/64 b，其取值由CPU 中通用寄存器的緩存行長度決定，以減少內(nèi)存訪問，提高查詢性能.設(shè)改進(jìn)布隆過濾器的K個哈希函數(shù)為Hash（key），其中，key為節(jié)點(diǎn)關(guān)鍵值，設(shè)一個改進(jìn)布隆過濾器中可以存儲的元素長度為len，則len計算結(jié)果為

在完成索引數(shù)據(jù)結(jié)構(gòu)構(gòu)建后，將所有位點(diǎn)初始化為0，對每個主區(qū)塊對應(yīng)的從屬鏈構(gòu)建索引，具體有3 個步驟：

1）使用選擇列的函數(shù)，先將元素映射到對應(yīng)列，該元素將在對應(yīng)列的位點(diǎn)；

2）通過K個哈希運(yùn)算函數(shù)獲得位點(diǎn)；

3）將對應(yīng)位點(diǎn)置為1.

其中，步驟1 中的列選擇函數(shù)產(chǎn)生了額外的計算開銷，為降低計算開銷，將優(yōu)化哈希函數(shù)，從屬鏈上存儲的交易哈希值是交易經(jīng)過SHA256 哈希函數(shù)運(yùn)算得到的，因此優(yōu)化步驟1 的選擇列函數(shù)為以SHA256 哈希函數(shù)為基礎(chǔ)，通過取模運(yùn)算得到選擇列的函數(shù).步驟1 中的選擇列函數(shù)可表示為

步驟2 中的K個哈希函數(shù)由K個按位與運(yùn)算組成，可表示為

式（7）中的v為布隆過濾器中的元素，qv為進(jìn)行列選擇后獲得的列號.在獲得元素所在列后，確定該元素在構(gòu)建和查詢時都將被限制在對應(yīng)列.式（8）中為在獲得列號后在該列中通過K次式（8）的運(yùn)算獲得的行號，即對應(yīng)位點(diǎn)，k′為在通用布隆過濾器中的數(shù)組長度.基于改進(jìn)布隆過濾器的從屬鏈索引構(gòu)建算法如算法4 所示.

算法4.IBF_Construction 算法.

輸入：從屬鏈元素集合V′，元素v，改進(jìn)布隆過濾器數(shù)組長度k和通用布隆過濾器數(shù)組長度k′；

輸出：元素位點(diǎn)p和選擇列q.

在構(gòu)建完從屬鏈的索引后，提出一種根據(jù)從屬鏈上節(jié)點(diǎn)關(guān)鍵值和選擇列函數(shù)的基于改進(jìn)布隆過濾器的從屬鏈索引查詢算法，如算法5 所示.

算法5.IBF_Query 算法.

輸入：查詢元素v，改進(jìn)布隆過濾器中的元素V；

輸出：判斷結(jié)果.

4 實(shí) 驗(yàn)

本文實(shí)驗(yàn)環(huán)境為16 臺4 TB 存儲空間，128 GB RAM，16 核24 線程i9-12900KS CPU 的服務(wù)器集群，服務(wù)器之間通過高速局域網(wǎng)通信，每臺服務(wù)器均部署Ubuntu 18.04 操作系統(tǒng).實(shí)驗(yàn)采用2 個不同的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證：數(shù)據(jù)集1 為公共以太坊網(wǎng)絡(luò)中的前3 000 000 個區(qū)塊，數(shù)據(jù)集1 中有15 362 853 筆交易；數(shù)據(jù)集2 為Lognormal 人工數(shù)據(jù)集，Lognormal 數(shù)據(jù)集按照對數(shù)正態(tài)分布，以均值為0、方差為2 的方式采樣了500 萬條不重復(fù)的數(shù)據(jù).本節(jié)將從索引構(gòu)建時間、查詢時間、內(nèi)存消耗3 個方面驗(yàn)證MSMLI 的高效性和低內(nèi)存的優(yōu)點(diǎn).

4.1 分片權(quán)重比例選擇

在分片準(zhǔn)備階段將通過服務(wù)器構(gòu)建10 個分片，1 個服務(wù)器構(gòu)建1 個節(jié)點(diǎn)并將節(jié)點(diǎn)分配到對應(yīng)分片.分片中的節(jié)點(diǎn)容量設(shè)置為500 個節(jié)點(diǎn).對比節(jié)點(diǎn)數(shù)目設(shè)為100，200，300，400 時，分片權(quán)重的3 個維度節(jié)點(diǎn)負(fù)載、節(jié)點(diǎn)信用、網(wǎng)絡(luò)質(zhì)量的比例分別設(shè)置為3∶3∶4，4∶3∶3，5∶2∶3 三種情況.實(shí)驗(yàn)結(jié)果如圖3所示.

圖3 分片權(quán)重比例Fig.3 Shard weight ratio

由圖3 可知，在節(jié)點(diǎn)數(shù)量相同時，情況1 的實(shí)驗(yàn)效果最好，且隨著節(jié)點(diǎn)負(fù)載維度的比例增大時，分片時間增加.隨著節(jié)點(diǎn)數(shù)量的增多，情況2 和情況3 的時間明顯增加，而情況1 的時間增幅不大，維持在5s左右.因此，本文將按照主區(qū)塊鏈對區(qū)塊鏈分片時節(jié)點(diǎn)負(fù)載、節(jié)點(diǎn)信用、網(wǎng)絡(luò)質(zhì)量的分片權(quán)重為3∶3∶4的比例進(jìn)行.

4.2 索引構(gòu)建時間對比

為在索引構(gòu)建時間方面驗(yàn)證本文提出的MSMLI方法的高效性，將分別對比改進(jìn)區(qū)塊鏈結(jié)構(gòu)的EBTree方法和引入神經(jīng)網(wǎng)絡(luò)的Dabble 模型方法.EBTree 方法中的內(nèi)部節(jié)點(diǎn)的能力設(shè)置為128，葉節(jié)點(diǎn)的能力設(shè)置為 16.Dabble 模型中的K=100，MSMLI 方法的1 個分片中的節(jié)點(diǎn)數(shù)設(shè)置為100.在本節(jié)實(shí)驗(yàn)中，將分為3 種具體情況討論.

如表1 所示，使用2 個不同規(guī)模的數(shù)據(jù)集將MSMLI 方法與EBTree，Dabble 這2 種方法進(jìn)行索引構(gòu)建時間對比.索引構(gòu)建時間對比實(shí)驗(yàn)結(jié)果如圖4、圖5 所示.

Table 1 Index Construction Time Comparison表1 索引構(gòu)建時間對比

圖4 數(shù)據(jù)集1 上索引構(gòu)建時間對比Fig.4 Index construction time comparison on dataset 1

圖5 數(shù)據(jù)集2 上索引構(gòu)建時間對比Fig.5 Index construction time comparison on dataset 2

由圖4、圖5 可知，隨著數(shù)據(jù)量的增大，MSMLI方法與現(xiàn)有方法對比，在索引構(gòu)建時間方面優(yōu)化了約9.28%，其中Dabble 方法訓(xùn)練神經(jīng)網(wǎng)絡(luò)模型需要約15 s，因此，MSMLI 方法大大優(yōu)于Dabble 方法.

4.3 查詢時間對比

在本節(jié)實(shí)驗(yàn)中，首先將索引和數(shù)據(jù)加載進(jìn)內(nèi)存，為測試MSMLI 方法的查詢性能，將使用不同規(guī)模數(shù)據(jù)集和查詢條件對比查詢響應(yīng)時間.

4.3.1 大規(guī)模數(shù)據(jù)集查詢響應(yīng)時間對比

使用大規(guī)模數(shù)據(jù)集，數(shù)據(jù)集1 為公共以太坊網(wǎng)絡(luò)中的前3 000 000 個區(qū)塊.對比EBTree 方法和Dabble方法在主區(qū)塊數(shù)目為50 萬、100 萬、150 萬、200 萬、250 萬、300 萬，從屬區(qū)塊數(shù)目為1 000 時的查詢響應(yīng)時間，實(shí)驗(yàn)結(jié)果如圖6 所示.

圖6 大規(guī)模數(shù)據(jù)集索引查詢時間對比Fig.6 Index query time comparison of large-scale dataset

由圖6 可知，在大規(guī)模數(shù)據(jù)集上MSMLI 方法與現(xiàn)有方法對比，在索引構(gòu)建時間方面優(yōu)化了約13.44%，區(qū)塊數(shù)量增大時EBTree 方法優(yōu)勢更明顯.

4.3.2 小規(guī)模數(shù)據(jù)集查詢響應(yīng)時間對比

使用小規(guī)模數(shù)據(jù)集，數(shù)據(jù)集2 為Lognormal 人工數(shù)據(jù)集，其中具有500 萬條數(shù)據(jù)，總大小約24 MB.對比EBTree 方法和Dabble 方法在主區(qū)塊存儲10 萬、20萬、30 萬、40 萬、50 萬條數(shù)據(jù)，以及從屬區(qū)塊存儲1 000條數(shù)據(jù)時的查詢響應(yīng)時間，實(shí)驗(yàn)結(jié)果如圖7 所示.

圖7 小規(guī)模數(shù)據(jù)集索引查詢時間對比Fig.7 Index query time comparison of small-scale dataset

由圖7 可知，在小規(guī)模數(shù)據(jù)集上MSMLI 方法與現(xiàn)有方法對比，在查詢時間方面優(yōu)化了約10.71%.實(shí)驗(yàn)結(jié)果表明MSMLI 方法在數(shù)據(jù)量大時查詢性能更好.

4.4 內(nèi)存消耗對比

MSMLI 方法在分片階段構(gòu)建的權(quán)重矩陣幾乎不占用內(nèi)存，主鏈基于跳躍一致性哈希算法構(gòu)建索引，跳躍一致性哈希對比經(jīng)典的一致性哈希幾乎沒有額外內(nèi)存消耗.因此MSMLI 方法中的內(nèi)存開銷主要考慮從屬區(qū)塊鏈的索引構(gòu)建.IBF 的假陽性設(shè)置為0.013 7，lq=64b.EBTree 方法改寫區(qū)塊鏈結(jié)構(gòu)，內(nèi)存消耗主要為區(qū)塊數(shù)據(jù).MSMLI 方法與Dabble 方法的對比實(shí)驗(yàn)結(jié)果如表2 所示.

Table 2 Memory Consumption Comparison表2 內(nèi)存消耗對比

由表2 可知，Lognormal 數(shù)據(jù)集占用內(nèi)存24 MB；Dabble 方法占用內(nèi)存4 KB；對于MSMLI 方法，IBF 在保證假陽性可允許范圍內(nèi)仍僅占用內(nèi)存約2.048 KB，即使將IBF 與BF 在相同假陽性要求下仍能保持相同數(shù)量級.

5 結(jié) 論

隨著區(qū)塊鏈技術(shù)的廣泛應(yīng)用，傳統(tǒng)單鏈結(jié)構(gòu)已逐漸無法滿足日益增長的領(lǐng)域數(shù)據(jù)存儲需求，主從區(qū)塊鏈開始廣泛應(yīng)用于金融、教育、安全等領(lǐng)域.針對現(xiàn)有主從區(qū)塊鏈系統(tǒng)查詢效率低、溯源時間長的問題，本文提出一種面向主從區(qū)塊鏈的多級索引構(gòu)建方法（MSMLI）.該方法首先將整個主從區(qū)塊鏈結(jié)構(gòu)按照主鏈將結(jié)構(gòu)進(jìn)行分片，并采用權(quán)重矩陣提高分片可維護(hù)性，為索引構(gòu)建提供支持；在此基礎(chǔ)上，針對主鏈和從屬鏈數(shù)據(jù)規(guī)模不同的特征，提出基于跳躍一致性哈希的索引構(gòu)建方法（JHMI），以及基于改進(jìn)布隆過濾器的從屬鏈索引構(gòu)建方法（IBF），提高主從區(qū)塊鏈查詢效率.實(shí)驗(yàn)結(jié)果表明，本文提出的MSMLI 方法對比現(xiàn)有方法，在構(gòu)建時間、查詢效率、內(nèi)存占用方面具有很大優(yōu)勢，為主從區(qū)塊鏈的快速檢索提供了一條有效途徑.

作者貢獻(xiàn)聲明：王俊陸提出了算法思路和實(shí)驗(yàn)方案；張桂月負(fù)責(zé)完成實(shí)驗(yàn)并撰寫論文；杜立寬參與了審稿專家提出的關(guān)于查詢實(shí)驗(yàn)部分的修改工作并補(bǔ)充了重要的參考文獻(xiàn)；李素參與了審稿專家提出的關(guān)于文章具體內(nèi)容上的修改工作，補(bǔ)充了文章框架和內(nèi)容；陳廷偉提出指導(dǎo)意見并修改論文.