?

面向主從區塊鏈的多級索引構建方法

2024-03-23 08:04王俊陸張桂月杜立寬陳廷偉
計算機研究與發展 2024年3期
關鍵詞:主鏈分片主從

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

(遼寧大學信息學院 沈陽 110036)

區塊鏈通過塊鏈式數據結構存儲并驗證數據,輔以密碼學[1-2]方法保證數據傳輸和訪問的安全性,具有高可信[3]、可回溯、去中心化[4]等特點,能夠很好地解決數據存儲對第三方的信任問題[5].隨著區塊鏈技術的發展以及各行業數據規模的累計,傳統的單鏈結構區塊鏈系統已經無法滿足愈發復雜的領域應用場景,主從區塊鏈(master-slave blockchain,MSBC)結構,如星火鏈、COSMOS 等,開始受到領域專家學者的關注,并逐步在教育、醫療、安全[6]等領域廣泛應用[7-10].主從區塊鏈通常包括主鏈和從屬鏈2 部分,分別由主區塊和從屬區塊組成,每個主區塊有且只有一個從屬鏈.各個主區塊和從屬區塊之間分別通過前一個主區塊和從屬區塊的哈希值相連,主區塊與從屬鏈通過唯一的哈希值進行映射.

主從區塊鏈結構可以應對復雜分類場景的應用.如金融領域中,采用主從區塊鏈構建面向金融活動的企業區塊鏈系統,主鏈中存儲金融企業屬性信息,對應的從屬鏈存儲其交易事件、金融活動等數據,通過區塊鏈的共識機制[11-12]保證數據不可篡改.

隨著領域數據規模的不斷增大,主從區塊鏈系統存在的查詢效率低、溯源時間長等問題[13-14]愈發嚴重.而現有區塊鏈索引方法多只適用于單一鏈結構,且查詢效率和索引構建時間均較差.因此,如何針對主從區塊鏈建立高效、可動態維護的索引結構,成為領域研究的熱點和難點.

針對上述問題,本文提出一種面向主從區塊鏈的多級索引構建方法(multi-level index construction method for master-slave blockchain,MSMLI).主要貢獻有4 個方面:

1)綜合節點負載、節點信用和網絡質量構建權重矩陣,提出一種基于權重矩陣的區塊鏈分片算法(weighted matrix-based blockchain sharding algorithm,WMBS),基于主鏈特征實現主從區塊鏈結構的動態分片;

2)在此基礎上,針對現有區塊鏈索引不適用于主從鏈結構的問題,提出基于跳躍一致性哈希的主鏈索引構建算法(master chain index construction algorithm based on jump consistent Hash,JHMI),通過主鏈的節點關鍵值與索引槽位映射,實現主鏈信息的高效查詢;

3)結合區塊鏈的數據特點,提出基于改進布隆過濾器的從屬鏈索引構建算法(construction algorithm for subordinate chain indexes based on improved Bloom filters,IBF),優化基于列的選擇函數,并給出索引查詢方法;

4)在不同約束條件和數據集上與現有方法進行對比實驗,驗證本文所提方法的有效性.

1 相關工作

目前,許多學者對于區塊鏈的索引構建問題進行了深入研究,取得了一定研究成果.

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

2 基于主從結構的區塊鏈分片方法

為實現主從區塊鏈結構的高效索引構建和查詢處理,基于主鏈特征對整個主從區塊鏈分片,并對各個分片賦予權重,據此構建整個主從區塊鏈結構的分片權重矩陣;基于權重矩陣確定分片中的節點數目,為主鏈和從屬區塊鏈構建索引提供支撐.

2.1 權重矩陣構建

設主從區塊鏈的節點數目為x,主從區塊鏈分為y(y?x)個分片,第i個分片為fi(i=0,1,…,y-1),各個分片權重為 ωi.分片權重由節點負載、節點信用、網絡質量3 個維度的權重決定,其中節點信用和網絡質量與分片權重呈正相關,節點負載與分片權重呈負相關,各項維度的權重由實驗效果最佳的比例決定.在進行分片權重計算前,由于上述3 個維度的單位不統一,因此需進行歸一化處理.節點負載的歸一化公式為

節點信用和網絡質量的歸一化公式為

第i個分片的權重為 ωi,計算公式為

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

2.2 基于權重矩陣確定片內節點數目

基于2.1 節的權重矩陣,確定各個分片內的節點數目.首先,對矩陣中的分片權重進行線性歸一化處理.其次,對歸一化后的所有分片權重按照比例離散,設離散比例權重值區間為[1,Q].最終獲得分片比例權重Q-1,即該分片將對應Q-1 個節點.

線性歸一化后的分片權重的公式為

其中的ωmin為所有分片權重 ωi中的最小值,ωmax為最大值.

基于2.1 節的權重矩陣的構建過程,提出了一種基于權重矩陣的區塊鏈分片算法WMBS,其通過跳躍搜索(jump search,JPS)算法快速進行區塊鏈分片與節點的映射,實現了主從區塊鏈結構的分片.WMBS 將節點關鍵值key、隨機數r和權重矩陣作為輸入,基于JPS 使節點與分片逐一映射.key在節點加入區塊鏈時創立,為32 b 節點關鍵值,其由8 b 的分片地址碼和24 b 的節點隨機碼組成,是節點的唯一標識;r是一個在[0,1]區間內均勻分布的隨機數,由線性同余隨機數發生器生成.WMBS 算法如算法1所示.

算法1.WMBS 算法.

算法2.JPS 算法.

3 多級索引構建方法

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

圖1 多級索引構建示意圖Fig.1 Multi-level index construction schematic

如圖1 所示,在主鏈中,通過JHMI 建立1 級索引.在從屬鏈中,引入IBF 建立2 級索引,2 級索引通過節點關鍵值進行關聯.當查詢發生時,首先在主鏈索引中檢索節點關鍵值,得到查詢結果后,基于該結果在從屬鏈索引中通過節點關鍵值獲得元素信息.

3.1 基于跳躍一致性哈希的主鏈索引構建

基于主鏈存儲的數據特點,本文引入跳躍一致性哈希算法,提出JHMI,實現主鏈索引的快速構建.首先,根據各主鏈分片上的節點數量確定索引的槽位數量;其次,根據主鏈存儲數據的哈希值確定各個節點關鍵值;最后,輸入節點關鍵值和索引槽位數量,輸出主鏈索引.

當分片中節點數量發生變化時,節點在索引中發生跳躍變化,部分節點重新映射.設產生跳躍變化的哈希映射函數為ch(key,num_buckets),key為節點關鍵值,num_buckets為槽位數量,可得:1)num_buckets= 1 時,只有1 個槽位,所有key都映射到1 個槽位中,即ch(key,num_buckets) = 0,所有節點都劃分在0 號槽位;2)num_buckets= 2 時,有1/2 的節點在ch(key,num_buckets) = 0,有K/ 2 個key重新映射即ch(key,num_buckets) = 1,跳躍到1 號槽位;3)當槽位數從n變為n+1 時,有n/(n+1) 的節點所在的槽位保持不變,即ch(key,num_buckets) =n-1,有1/(n+1)個key需要重新映射,即ch(key,num_buckets) =n.

設b為節點上一次跳變的結果,j為發生跳變前最后一次槽位擴充時槽位的數量,當分片內節點數量發生變化時,節點重新映射的示意圖如圖2 所示.

圖2 節點重新映射圖Fig.2 Diagram of node remapping

由圖2 可知,對于任意的i∈[b+1,j-1],增加節點數量且沒有發生跳變的概率為

在[0,1]區間取一個均勻分布的隨機數r,由式(5)可得,當r<(b+1)/r時,節點就會跳變成j,則i的上界為(b+1)/r.由于對任意的i都有j≥i,則j=floor((b+1)/r).JHMI 算法如算法3 所示.

算法3.JHMI 算法.

輸入:節點關鍵值key,槽位數量num_buckets和空主鏈索引s;

3.2 基于改進布隆過濾器的從屬鏈索引構建

從屬鏈存儲的數據具有規模大、多源異構的特點,因此,在從屬鏈索引構建過程中,本文重構布隆過濾器數據結構,提出IBF 算法.

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

在完成索引數據結構構建后,將所有位點初始化為0,對每個主區塊對應的從屬鏈構建索引,具體有3 個步驟:

1)使用選擇列的函數,先將元素映射到對應列,該元素將在對應列的位點;

2)通過K個哈希運算函數獲得位點;

3)將對應位點置為1.

其中,步驟1 中的列選擇函數產生了額外的計算開銷,為降低計算開銷,將優化哈希函數,從屬鏈上存儲的交易哈希值是交易經過SHA256 哈希函數運算得到的,因此優化步驟1 的選擇列函數為以SHA256 哈希函數為基礎,通過取模運算得到選擇列的函數.步驟1 中的選擇列函數可表示為

步驟2 中的K個哈希函數由K個按位與運算組成,可表示為

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

算法4.IBF_Construction 算法.

輸入:從屬鏈元素集合V′,元素v,改進布隆過濾器數組長度k和通用布隆過濾器數組長度k′;

輸出:元素位點p和選擇列q.

在構建完從屬鏈的索引后,提出一種根據從屬鏈上節點關鍵值和選擇列函數的基于改進布隆過濾器的從屬鏈索引查詢算法,如算法5 所示.

算法5.IBF_Query 算法.

輸入:查詢元素v,改進布隆過濾器中的元素V;

輸出:判斷結果.

4 實 驗

本文實驗環境為16 臺4 TB 存儲空間,128 GB RAM,16 核24 線程i9-12900KS CPU 的服務器集群,服務器之間通過高速局域網通信,每臺服務器均部署Ubuntu 18.04 操作系統.實驗采用2 個不同的數據集進行實驗驗證:數據集1 為公共以太坊網絡中的前3 000 000 個區塊,數據集1 中有15 362 853 筆交易;數據集2 為Lognormal 人工數據集,Lognormal 數據集按照對數正態分布,以均值為0、方差為2 的方式采樣了500 萬條不重復的數據.本節將從索引構建時間、查詢時間、內存消耗3 個方面驗證MSMLI 的高效性和低內存的優點.

4.1 分片權重比例選擇

在分片準備階段將通過服務器構建10 個分片,1 個服務器構建1 個節點并將節點分配到對應分片.分片中的節點容量設置為500 個節點.對比節點數目設為100,200,300,400 時,分片權重的3 個維度節點負載、節點信用、網絡質量的比例分別設置為3∶3∶4,4∶3∶3,5∶2∶3 三種情況.實驗結果如圖3所示.

圖3 分片權重比例Fig.3 Shard weight ratio

由圖3 可知,在節點數量相同時,情況1 的實驗效果最好,且隨著節點負載維度的比例增大時,分片時間增加.隨著節點數量的增多,情況2 和情況3 的時間明顯增加,而情況1 的時間增幅不大,維持在5s左右.因此,本文將按照主區塊鏈對區塊鏈分片時節點負載、節點信用、網絡質量的分片權重為3∶3∶4的比例進行.

4.2 索引構建時間對比

為在索引構建時間方面驗證本文提出的MSMLI方法的高效性,將分別對比改進區塊鏈結構的EBTree方法和引入神經網絡的Dabble 模型方法.EBTree 方法中的內部節點的能力設置為128,葉節點的能力設置為 16.Dabble 模型中的K=100,MSMLI 方法的1 個分片中的節點數設置為100.在本節實驗中,將分為3 種具體情況討論.

如表1 所示,使用2 個不同規模的數據集將MSMLI 方法與EBTree,Dabble 這2 種方法進行索引構建時間對比.索引構建時間對比實驗結果如圖4、圖5 所示.

Table 1 Index Construction Time Comparison表1 索引構建時間對比

圖4 數據集1 上索引構建時間對比Fig.4 Index construction time comparison on dataset 1

圖5 數據集2 上索引構建時間對比Fig.5 Index construction time comparison on dataset 2

由圖4、圖5 可知,隨著數據量的增大,MSMLI方法與現有方法對比,在索引構建時間方面優化了約9.28%,其中Dabble 方法訓練神經網絡模型需要約15 s,因此,MSMLI 方法大大優于Dabble 方法.

4.3 查詢時間對比

在本節實驗中,首先將索引和數據加載進內存,為測試MSMLI 方法的查詢性能,將使用不同規模數據集和查詢條件對比查詢響應時間.

4.3.1 大規模數據集查詢響應時間對比

使用大規模數據集,數據集1 為公共以太坊網絡中的前3 000 000 個區塊.對比EBTree 方法和Dabble方法在主區塊數目為50 萬、100 萬、150 萬、200 萬、250 萬、300 萬,從屬區塊數目為1 000 時的查詢響應時間,實驗結果如圖6 所示.

圖6 大規模數據集索引查詢時間對比Fig.6 Index query time comparison of large-scale dataset

由圖6 可知,在大規模數據集上MSMLI 方法與現有方法對比,在索引構建時間方面優化了約13.44%,區塊數量增大時EBTree 方法優勢更明顯.

4.3.2 小規模數據集查詢響應時間對比

使用小規模數據集,數據集2 為Lognormal 人工數據集,其中具有500 萬條數據,總大小約24 MB.對比EBTree 方法和Dabble 方法在主區塊存儲10 萬、20萬、30 萬、40 萬、50 萬條數據,以及從屬區塊存儲1 000條數據時的查詢響應時間,實驗結果如圖7 所示.

圖7 小規模數據集索引查詢時間對比Fig.7 Index query time comparison of small-scale dataset

由圖7 可知,在小規模數據集上MSMLI 方法與現有方法對比,在查詢時間方面優化了約10.71%.實驗結果表明MSMLI 方法在數據量大時查詢性能更好.

4.4 內存消耗對比

MSMLI 方法在分片階段構建的權重矩陣幾乎不占用內存,主鏈基于跳躍一致性哈希算法構建索引,跳躍一致性哈希對比經典的一致性哈希幾乎沒有額外內存消耗.因此MSMLI 方法中的內存開銷主要考慮從屬區塊鏈的索引構建.IBF 的假陽性設置為0.013 7,lq=64b.EBTree 方法改寫區塊鏈結構,內存消耗主要為區塊數據.MSMLI 方法與Dabble 方法的對比實驗結果如表2 所示.

Table 2 Memory Consumption Comparison表2 內存消耗對比

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

5 結 論

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

作者貢獻聲明:王俊陸提出了算法思路和實驗方案;張桂月負責完成實驗并撰寫論文;杜立寬參與了審稿專家提出的關于查詢實驗部分的修改工作并補充了重要的參考文獻;李素參與了審稿專家提出的關于文章具體內容上的修改工作,補充了文章框架和內容;陳廷偉提出指導意見并修改論文.

猜你喜歡
主鏈分片主從
上下分片與詞的時空佈局
分片光滑邊值問題的再生核方法
CDN存量MP4視頻播放優化方法
WDC主鏈正式啟動創世區塊已誕生
基于模糊二分查找的幀分片算法設計與實現
FANUC系統PROFIBUS主從功能應用
有機化合物命名易錯題直擊
“烷烴”的五字命名方針
基于主從控制的微電網平滑切換控制策略研究
基于飛行試驗數據的仿真模型主從一體化檢驗
91香蕉高清国产线观看免费-97夜夜澡人人爽人人喊a-99久久久无码国产精品9-国产亚洲日韩欧美综合