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

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

區(qū)塊鏈通過塊鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)存儲(chǔ)并驗(yàn)證數(shù)據(jù)，輔以密碼學(xué)[1-2]方法保證數(shù)據(jù)傳輸和訪問的安全性，具有高可信[3]、可回溯、去中心化[4]等特點(diǎn)，能夠很好地解決數(shù)據(jù)存儲(chǔ)對(duì)第三方的信任問題[5].隨著區(qū)塊鏈技術(shù)的發(fā)展以及各行業(yè)數(shù)據(jù)規(guī)模的累計(jì)，傳統(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ū)塊組成，每個(gè)主區(qū)塊有且只有一個(gè)從屬鏈.各個(gè)主區(qū)塊和從屬區(qū)塊之間分別通過前一個(gè)主區(qū)塊和從屬區(qū)塊的哈希值相連，主區(qū)塊與從屬鏈通過唯一的哈希值進(jìn)行映射.

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

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

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

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)的動(dòng)態(tài)分片；

2）在此基礎(chǔ)上，針對(duì)現(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)行對(duì)比實(shí)驗(yàn)，驗(yàn)證本文所提方法的有效性.

1 相關(guān)工作

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

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

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

為實(shí)現(xiàn)主從區(qū)塊鏈結(jié)構(gòu)的高效索引構(gòu)建和查詢處理，基于主鏈特征對(duì)整個(gè)主從區(qū)塊鏈分片，并對(duì)各個(gè)分片賦予權(quán)重，據(jù)此構(gòu)建整個(gè)主從區(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)個(gè)分片，第i個(gè)分片為fi(i=0,1,…,y-1)，各個(gè)分片權(quán)重為 ωi.分片權(quán)重由節(jié)點(diǎn)負(fù)載、節(jié)點(diǎn)信用、網(wǎng)絡(luò)質(zhì)量3 個(gè)維度的權(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)重計(jì)算前，由于上述3 個(gè)維度的單位不統(tǒng)一，因此需進(jìn)行歸一化處理.節(jié)點(diǎn)負(fù)載的歸一化公式為

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

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

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

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

基于2.1 節(jié)的權(quán)重矩陣，確定各個(gè)分片內(nèi)的節(jié)點(diǎn)數(shù)目.首先，對(duì)矩陣中的分片權(quán)重進(jìn)行線性歸一化處理.其次，對(duì)歸一化后的所有分片權(quán)重按照比例離散，設(shè)離散比例權(quán)重值區(qū)間為[1,Q].最終獲得分片比例權(quán)重Q－1，即該分片將對(duì)應(yīng)Q－1 個(gè)節(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ū)塊鏈時(shí)創(chuàng)立，為32 b 節(jié)點(diǎn)關(guān)鍵值，其由8 b 的分片地址碼和24 b 的節(jié)點(diǎn)隨機(jī)碼組成，是節(jié)點(diǎn)的唯一標(biāo)識(shí)；r是一個(gè)在[0,1]區(qū)間內(nèi)均勻分布的隨機(jī)數(shù)，由線性同余隨機(jī)數(shù)發(fā)生器生成.WMBS 算法如算法1所示.

算法1.WMBS 算法.

算法2.JPS 算法.

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

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

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

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

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

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

當(dāng)分片中節(jié)點(diǎn)數(shù)量發(fā)生變化時(shí)，節(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 時(shí)，只有1 個(gè)槽位，所有key都映射到1 個(gè)槽位中，即ch（key,num_buckets） = 0，所有節(jié)點(diǎn)都劃分在0 號(hào)槽位；2）num_buckets= 2 時(shí)，有1/2 的節(jié)點(diǎn)在ch（key,num_buckets） = 0，有K/ 2 個(gè)key重新映射即ch（key,num_buckets） = 1，跳躍到1 號(hào)槽位；3）當(dāng)槽位數(shù)從n變?yōu)閚+1 時(shí)，有n/（n＋1） 的節(jié)點(diǎn)所在的槽位保持不變，即ch（key,num_buckets） =n-1，有1/（n+1）個(gè)key需要重新映射，即ch（key,num_buckets） =n.

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

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

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

在[0,1]區(qū)間取一個(gè)均勻分布的隨機(jī)數(shù)r，由式（5）可得，當(dāng)r＜(b+1)/r時(shí)，節(jié)點(diǎn)就會(huì)跳變成j，則i的上界為(b+1)/r.由于對(duì)任意的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)建

從屬鏈存儲(chǔ)的數(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個(gè)哈希函數(shù)為Hash（key），其中，key為節(jié)點(diǎn)關(guān)鍵值，設(shè)一個(gè)改進(jìn)布隆過濾器中可以存儲(chǔ)的元素長度為len，則len計(jì)算結(jié)果為

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

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

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

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

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

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

式（7）中的v為布隆過濾器中的元素，qv為進(jìn)行列選擇后獲得的列號(hào).在獲得元素所在列后，確定該元素在構(gòu)建和查詢時(shí)都將被限制在對(duì)應(yīng)列.式（8）中為在獲得列號(hào)后在該列中通過K次式（8）的運(yùn)算獲得的行號(hào)，即對(duì)應(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 算法.

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

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

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

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

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

在分片準(zhǔn)備階段將通過服務(wù)器構(gòu)建10 個(gè)分片，1 個(gè)服務(wù)器構(gòu)建1 個(gè)節(jié)點(diǎn)并將節(jié)點(diǎn)分配到對(duì)應(yīng)分片.分片中的節(jié)點(diǎn)容量設(shè)置為500 個(gè)節(jié)點(diǎn).對(duì)比節(jié)點(diǎn)數(shù)目設(shè)為100，200，300，400 時(shí)，分片權(quán)重的3 個(gè)維度節(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ù)量相同時(shí)，情況1 的實(shí)驗(yàn)效果最好，且隨著節(jié)點(diǎn)負(fù)載維度的比例增大時(shí)，分片時(shí)間增加.隨著節(jié)點(diǎn)數(shù)量的增多，情況2 和情況3 的時(shí)間明顯增加，而情況1 的時(shí)間增幅不大，維持在5s左右.因此，本文將按照主區(qū)塊鏈對(duì)區(qū)塊鏈分片時(shí)節(jié)點(diǎn)負(fù)載、節(jié)點(diǎn)信用、網(wǎng)絡(luò)質(zhì)量的分片權(quán)重為3∶3∶4的比例進(jìn)行.

4.2 索引構(gòu)建時(shí)間對(duì)比

為在索引構(gòu)建時(shí)間方面驗(yàn)證本文提出的MSMLI方法的高效性，將分別對(duì)比改進(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 個(gè)分片中的節(jié)點(diǎn)數(shù)設(shè)置為100.在本節(jié)實(shí)驗(yàn)中，將分為3 種具體情況討論.

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

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

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

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

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

4.3 查詢時(shí)間對(duì)比

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

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

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

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

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

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

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

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

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

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

MSMLI 方法在分片階段構(gòu)建的權(quán)重矩陣幾乎不占用內(nèi)存，主鏈基于跳躍一致性哈希算法構(gòu)建索引，跳躍一致性哈希對(duì)比經(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 方法的對(duì)比實(shí)驗(yàn)結(jié)果如表2 所示.

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

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

5 結(jié) 論

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