基于區塊鏈的文件存儲碎片分配優化模型

梁婉瑩 朱佳 馬曉東 湯庸 梁熙龍 陳善軒

摘 要：為了改善原有碎片分配方案僅以節點響應效率為主而對節點分配次數、節點空間利用率、安全性能欠缺考慮的現狀，提出分布式文件存儲系統的碎片分配優化模型。優化模型由節點響應狀況檢測、大范圍節點數據完整性審計和包含剩余存儲空間大小、最近存儲碎片時間戳以及響應時間長短的綜合評估3方面構成。對其進行仿真實驗，對比原有方案，優化方案沒有出現節點傾斜現象，選取次數最大落差不超過95;節點效率得到了均衡，最大落差縮減至15%。優化方案提高了碎片分配的公平性、安全性和可靠性，實現了最優節點的自動化選擇。

關鍵詞：區塊鏈;文件存儲;碎片分配;數據完整性審計;聲譽評估

DOI： 10. 11907/rjdk.192543

開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP399

文獻標識碼：A

文章編號：1672-7800（2020）001-0216-05

0 引言

隨著現代計算機科學的發展，人們每天使用各種應用所產生的數據不斷增加。互聯網數據中心（ Internet D ataC enter，IDC）報告指出，2020年全球數據總量將達到440億TB，并以極快的速度持續增長[1]。在此背景下，數據存儲成本逐步提升，數據安全性也得不到有效保障。

為了更好地應對海量數據及文件存儲問題，人們提出了分布式存儲概念[2]。分布式存儲系統可將數據分散存儲在多臺獨立的設備上。它基于標準硬件和分布式架構，可進行EB級擴展，利用多臺服務器減輕單獨存儲負荷。如今，區塊鏈作為一種分布式數據結構，在文件存儲領域發展最為成熟[3]。在學術嘗試中，AFS（ Andrew File System）[4]較為成功且仍在使用;在商業嘗試中，部分分布式存儲系統依靠區塊鏈作為底層技術，搭建P2P[5]節點網絡，將已上傳的文件加密并根據文件分片規則切分成碎片，依靠bit-Torrent比特流文件分發協議[6]、Kademlia分布式哈希表DHT（ Disturbed Hash Table）[7]等規則，將碎片協調和分配到其它對等點上，以應對超大數量的文件存儲需求。

原有的分布式文件存儲系統以響應效率為主，可能導致不同碎片均存儲或大部分存儲在同一個節點內，信息極易被竊取，且用戶享用的存儲效率不一致;對空間分配問題考慮欠缺，利用率未達最優化;存儲節點的信用度模糊，降低了安全性能。

為解決原有碎片分配模型問題，本文在已有分布式文件存儲系統基礎上提出優化模型。模型包含響應狀況檢測、節點數據審計和綜合評估3方面，對存儲節點進行綜合測評，自動化選擇最適合的節點對碎片進行存儲。本文貢獻如下：①在節點綜合評估之前添加數據完整性審計，確保存儲范圍內節點的高信用度，優化模型在保證節點響應效率的同時，降低了數據被篡改的幾率;②在綜合評估中添加節點剩余存儲空間大小標準，以最壞分配算法提升了存儲空間利用率，降低了碎片空間出現幾率;③在綜合評估中添加最近存儲碎片時間戳，降低了碎片分配過分傾斜的可能性，使節點獲得存儲資格幾率相對均等。

1 區塊鏈綜述

區塊鏈最早于2008年在比特幣創始人中本聰（ Sa-toshi Nakamoto）[8]著作《比特幣：一種點對點式的電子現金系統》一文中以加密貨幣底層技術的身份面世。它實際上是一個由多方共同維護、去中心化的分布式數據庫，通過P2P網絡協議、非對稱加密[9]、共識機制等解決了交易雙方往來的信任問題。區塊鏈以鏈式數據結構為基礎，區塊為單位，根據時間順序將攜帶信息的新區塊插入到鏈的末尾。每個區塊包含哈希值、時間戳、隨機數、Merkle根等。

區塊鏈系統有6層結構，分別是數據層、網絡層、共識層、激勵層、合約層和應用層。數據層封裝相關數據加密技術（如SHA-1[10]、RSA[11]）以及底層數據區塊;網絡層包含分布式組網機制、數據傳播機制等;共識層主要包含各種共識算法[12];激勵層將經濟學知識融合到體系之中，包括發行和分配機制;合約層包含各類腳本或智能合約;應用層是面對實際的各種案例和應用場景[13]。

區塊鏈有3種模型，包括公有鏈、私有鏈以及聯盟鏈。公有鏈是指無用戶授權機制、全網公開的區塊鏈，任意節點均可查看完整的區塊數據;私有鏈是指集中于一家機構的網絡節點;聯盟鏈是指允許經過授權的節點加入網絡，可根據權限查看信息，常用于公司或機構的區塊鏈。公有鏈稱為非許可鏈，聯盟鏈和私有鏈統稱為許可鏈[14]。

2 預備知識

2.1 分布式哈希表技術

分布式哈希表技術（Distributed Hash Table，簡稱DHT）是一種分布式存儲方法。它將鍵（ kev）分散在不同節點上，并紀錄相應的查找方法。DHT不需要服務器，每個節點只需與其它部分節點相連，存儲一部分數據和路由信息，從而實現系統的尋址和存儲功能。它被廣泛應用于協調和維護元數據。分布式哈希表技術有Kademlia、Coral、S/Kademlia[15]等。

3.2 文件分片

文件分片是指將現有大文件分成一定大小的碎片，分別存放于P2P網絡的不同節點中，以達到更高效更安全的存儲效果[16]。當節點失效時，系統將利用數據冗余，即復制信息到多個節點的方法以提高數據訪問效率，增強容錯性[17]。

3.3 數據完整性審計

為了保證碎片不被篡改，在節點對碎片進行存儲的過程中，系統會對節點上的碎片進行數據完整性審計。數據完整性審計是指對已存儲的信息進行核對和驗證，包括碎片內容、簽名信息等。現有的數據完整性審計模型分別是基于Jules等[18]提出的數據可恢復性證明（Proofs Of Re-trievability，POR）模型和Atenises等[19]提出的數據持有性證明（ Provable Data Possession，PDP）模型。

3 問題描述

本文以Storj v3[20]為基礎，對其系統內部由工作身份證明、數據完整性審計系統、篩選以及偏好這4個子系統所組成的聲譽評估體系進行修補改進。

原有系統碎片分配流程如圖1所示。用戶節點puse，∈G在本地加密所需存儲文件，并將其上傳。上傳成功后，系統根據文件分片規則將文件切分為碎片，并使用Kademlia DHT對碎片進行分配。系統會對兩個節點pi、pj的160bit唯- ID值進行二進制異或運算（XOR），運算結果作為判斷節點之間距離d i，j的標準，以此找出距離用戶節點puse，最近的45個節點K={p1，p2，…，p45）并對其進行聲譽評估。

系統原有聲譽評估體系如下：Bridge要求附近的45個節點pn∈K均出示工作證明，并對額外少量未經審核的節點進行數據完整性審計。上述兩項評估有其中一項無法通過的節點則被淘汰，剩余節點p。∈Ki將接受綜合評估。綜合評估包括節點響應時間（吞吐量和延遲）、地理位置等。而后，剩余節點pn∈K1將按照聲譽評估標準（Reputa-tion）的分數高低進行排序，聲譽最高的節點將獲得碎片存放資格。

在上述方案中，可能出現如下問題：

（1）碎片多次存儲在同一個節點中，易出現信息泄露。來自同一文件的不同碎片均存儲或大部分存儲在同一個節點內，信息極易被節點擁有者所竊取，安全性能大大降低。此外，它還將導致各用戶節點存儲速率體驗感不一致，落差較大。

（2）存儲范圍內節點空間利用率未達最優化。存儲節點空間大小均由節點所有者決定，故并不一致。若使用原有方案進行碎片分配，可能導致節點最后剩余的空閑分區總和較大，造成資源浪費。這些不連續的空余分區，無法滿足對新碎片的存儲需要，使得存儲空間利用率無法達到最優。

（3）節點分配和數據審計分開工作，對節點的信用評價缺失。原有模型中的審計僅針對少量節點而并非全部。若節點在存儲過程中（下一次審計之前）破壞或篡改了碎片，系統仍舊可能會因為其極高的響應速率，大幾率地將碎片分配至該節點。方案保證了存儲效率和應答速度，卻喪失了碎片存儲安全保障。

4 碎片分配優化模型

為提升其安全性、公平性及統一性，本文提出區塊鏈文件存儲系統碎片分配優化模型。優化模型包括前期工作和3項評估工作，流程如圖2所示。

碎片分配優化模型前期工作包括用戶上傳加密文件并分片、尋找用戶節點附近的45個存儲節點兩項。由于前期工作與原有方案相同，在此不加以闡述。在前期工作完成后，系統將會對存儲范圍節點pn∈K進行以下3部分的檢測和評估，包括：響應狀況檢測、節點數據審計以及由節點剩余存儲空間大小、最近存儲碎片時間戳比較、響應時間長短3方面構成的綜合評估。

4.1 響應請求

在用戶上傳文件與文件分片等前期工作完成后，系統將對存儲范圍K={p1，p2，…，p45）內的45個節點發送響應回復請求，對節點的響應狀態進行檢查并紀錄每個節點的響應時間長短用以進行后續綜合評估。其中，節點響應時間，即節點響應1 000個此類請求所花費時間的平均值。響應狀態正常且響應時間小于9 000ms的節點則保留，其余節點淘汰。響應檢測后節點數目必定小于或等于響應檢測前的節點數目，故通過響應檢測的節點集為pn∈K1，K1（ K。

4.2 數據完整性審計

在響應檢測后，系統將進行針對大范圍節點的數據完整性審計，以確保每個存儲節點的信用度。系統對通過響應請求的節點pn∈K1進行數據完整性審計。審計結果包括正常和異常兩種情況。審計正常，即隨機抽取一段密文對其添加后綴，二次加密后得出的新密文之間無錯漏。這類正常節點pn∈K2將進入下一部分的節點質量綜合評估。審計異常包括審計不響應和審計錯誤兩種情況，不響應審計的節點將被放置在容器（ Containment）中，其后續只能對當前審計作出響應，直到審計通過或被取消存儲資格;審計錯誤的節點則將直接取消本次存儲資格，不參與后續綜合評估。

4.3 綜合評估

在數據審計后，系統將對剩余節點pn∈K2進行綜合評估。綜合評估包含節點剩余存儲空間大小、最近存儲碎片時間戳比較、響應時間長短3項標準，評估中3項標準權重依次為1：1：1，評估得分最高者將獲得存儲資格。

（1）節點剩余存儲空間大小。優化模型將使用最壞適應分配算法（Worst Fit）。最壞適應分配方法總是挑選一個最大的空閑區分割給碎片進行存儲，這樣可使剩下的空閑分區不至于太小，產生碎片的幾率最小。評分標準：對參與綜合評價的節點pn∈K2進行存儲空間從大到小的排序，剩余節點中存儲空間最大的節點評價分數為cardK2，中間節點依次降低，直至剩余存儲空間最小的節點評價分數為1。

（2）最近存儲碎片時間戳比較。系統將對每個節點添加時間戳（ Timestamp）紀錄，保存該節點最近一次存儲碎片的時間戳，可使最長時間沒進行碎片存儲的節點擁有優先權，令其不至于因為響應速度稍慢而降低搶奪存儲資格的能力，使得碎片分配能夠公平平均，各節點進行碎片存儲的機會保持相對公平均等。評分標準：對參與綜合評價的節點pn∈K2進行時間戳從小到大的排序，時間戳最小，即距離上一次進行碎片存儲時間最長的節點評價分數為cardK2，中間節點依次降低，時間戳最大，即距離上一次進行碎片存儲時間最短的節點評價分數為1。

（3）響應時間長短。系統將對每個節點的響應時間進行紀錄，以確保碎片存儲的速度和效率，為用戶提供優質網絡環境。評分標準：對參與綜合評價的節點p。∈K2進行響應時間從短到長的排序，響應時間長于9 000ms的節點可視為無效，將舍棄。響應時間最小的節點評價分數為cardK2，中間節點依次降低，響應時間最長的節點評價分數為1。

5 實驗

本文對碎片分配優化模型進行了仿真實驗，實驗算法均采用Java編程語言進行程序編寫，實驗環境為2.60CHzIntel（ R） Core i5-3230M CPU， 8.OOCB RAM，硬盤890GB，操作系統為Windows 10家庭版。

本文對原有方案進行如下實驗：新建節點類用模擬45個存儲范圍內的非新加入網絡節點，并為每個節點分配編號。其中，44個節點的響應狀態（正常/異常）和響應時間（ms）均隨機生成，其中一個節點情況交由人為調控，響應狀態控制為正常，響應時間維持在較快程度。本次實驗人工節點編號為26。實驗根據上述流程生成45個節點并置其于并行狀態，而后按原有聲譽評估標準進行1 000次最優節點選擇。實驗默認在每一次選擇中節點狀態均在小范圍內變化，可忽略不計，故狀態不再重新生成。實驗得出結果如表1所示。

同樣地，本文對優化方案也進行類似實驗。為了作出更好對比，節點編號及其響應時間不作更改，而最近一次存儲碎片時間戳（格林尼治時間）和存儲空間大小均由隨機數種子生成;人工節點的存儲空間維持在較大程度，時間戳隨機生成;人工節點編號仍為26。實驗生成上述45個節點并置其于并行狀態，而后按優化方案進行1 000次最優節點選擇。實驗默認在每一次選擇中節點狀態均在小范圍內變化，可忽略不計，故狀態不再重新生成。實驗得出結果如表2所示。

根據表1可知，人工節點p26被選擇次數最多，高達586次，被抽取的幾率高達58.6%;節點p21被選擇次數是隨機節點之首，但僅為29次，低于人工節點被選擇次數的20。當響應時間由200ms延長至2 700ms時，被選擇次數從586次降低到29次。由此可知，假設存儲范圍pn∈K內總有一個節點pnrtificial= pbes，維持在最優狀態，則每次分配的碎片都極大可能存儲在partificial上。

由表2可以看出，即使最優節點總是不更換，按照優化模型實施碎片分配也不會出現節點傾斜情況，即最優節點被選擇次數遠遠高出隨機節點的情況。相比之下，優化模型中各節點存儲碎片機會相對均等公平，落差較小，如圖7所示。各效率梯度節點的使用率相對平均，降低了用戶體驗的不一致性，如圖8所示。存儲節點所剩余空間較大，產生小碎片幾率降低。方案確保每次分配的節點都通過數據完整性審計，是完全高信用度的。方案綜合了多方面去評估存儲節點，力求得出該次分配的最適合節點。

區塊鏈文件存儲系統碎片分配優化模型既保留了對節點響應效率的高要求，同時還提升了安全性、公平性以及統一性。將針對大范圍節點的數據完整性審計加入到存儲節點選取流程中，確保了節點的高信用度。在綜合評估中添加節點剩余空間大小標準，使用最壞適應分配算法，減少碎片產生幾率，提升存儲空間利用率;添加最近存儲碎片時間戳比較，使得響應速度稍慢的節點也能擁有均等的碎片存儲機會，消除了碎片堆積同一節點現象，提高了數據安全性。由圖3、圖4可知，使用優化方案以后，節點之間被選擇次數維持在相對平均狀態，避免了兩極分化現象;各效率梯度節點的使用率相對平均，用戶的使用感得到大體上的統一。

6 結語

本文基于Storj區塊鏈文件存儲系統的聲譽評價體系，提出了碎片分配優化模型。該模型包括響應狀態測試和時間控制、數據完整性審計、存儲節點空間大小和最近存儲碎片時間戳等節點選擇標準，綜合多方面對存儲范圍內的節點進行評估，為碎片分配最合適的存儲節點。本文分別對原方案和優化方案進行仿真測試并對比，證實了優化方案在保證響應效率的同時，提高了數據安全性和可靠性，降低了碎片分配過分傾斜的可能性，最大程度上提升了存儲空間利用率。

參考文獻：

[1]

Cctime[ EB/OL]. http： //，vww.cctime.com， 2018.

[2] 朱琨.基于P2P的分布式存儲系統的研究與實現[D].成都：電子科技大學，2010.

[3]殷龍，王宏偉.基于IPFS的分布式數據共享系統的研究[J].物聯網技術，2016，6（6）：60-62.

[4]

HOWARD J H，KAZAR M L，MENEES S G，et al.Scale andperfor-mance in a distributed file system[ J]. ACM Transactions on ComputerSvstem（TOCS）， 1988，6（1）：51-81.

[5]周文莉，吳曉非.P2P技術綜述[J].計算機工程與設計，2006. 27（1）：76-79.

[6] 孔彬，徐良賢.BitTorrent原理分析及改進[J].計算機工程，2004，30（ sl）：257-259.

[7] 周皓，何克右，邵紅梅.基于Kademlia的P2P搜索技術的研究[J].電腦知識與技術，2009，5（1）：189-191.

[8]

NAKAMOTO S.Bitcoin：a peer-to-peer electronic cash system[ EB/OL]. https： //bitcoin.org/bitcoin.pdf.

[9]卓先德，趙菲，曾德明.非對稱加密技術研究[J].四川理工學院學報（自然科學版），2010.23（5）：562-569

[10] 張松敏，陶榮，于國華.安全散列算法SHA-l的研究[J].計算機安全，2010（ 10）：3-5.

[11] 陳傳波，祝中濤.RSA算法應用及實現細節[J].計算機工程與科學，2006.28（9）：13-15.

[12] 袁勇，倪曉春，曾帥，等，區塊鏈共識算法的發展現狀與展望[J].自動化學報，2018，44（ 11）：2011-2022.

[13] 袁勇，王1躍.區塊鏈技術發展現狀與展望[J].自動化學報，2016. 42（ 4）：481-494.

[14] 沈鑫，裴慶祺，劉雪峰.區塊鏈技術綜述[J].網絡與信息安全學報.2016（5）：1-12.

[15] BAUMGART I， MIES S. S/Kademlia：a practicable approach towardssecure kev-based routing [C]. International Conference on Parallel&Distributed Systems. 2007： 1-8.

[16] 張洪，路松峰，趙友橋，等.數據安全存儲的分片策略模型研究[J].計算機工程與應用，2012.48（18）：66-70.

[17]

JUELS A， JR B S K.PORs： proofs of retrievability for large files[C]. Acm Conference on Computer&Communications Security， 2007.

[18]

ATENIESE G，BURNS R. CURTMOLA R， et al.Provahle data pos-session at untrusted stores[C].Proceedings of the 2007 ACM Confer-ence on Computer and Communications Securitv， 2007： 598.

[19] 蘇迪，劉竹松.一種新型的Merkle哈希樹運輸局完整性審計方案[J].計算機工程與應用，2018.54（1）：70-76.

[20]

STORJ LABS.A decentralized cloud storage network framework [EB/OL]. https： //storj.io/， 2018.

（責任編輯：孫娟）

基金項目：國家自然科學基金廣東大數據中心項目重點項目（ U1811263）;國家自然科學基金面上項目（61772211）

作者簡介：梁婉瑩（1998-），女，華南師范大學計算機學院學生，研究方向為區塊鏈、人工智能;朱佳（1982-），男，華南師范大學計算機學院研究員、博士生導師，研究方向為機器學習、區塊鏈、數據分析、人工智能;馬曉東（1995-），女，華南師范大學計算機學院碩士研究生，研究方向為區塊鏈、人工智能;湯庸（1964-），男，華南師范大學計算機學院教授、博士生導師，研究方向為數據智能、人本計算與社交軟件、學者知識圖譜與教育大數據分析;梁熙龍（1995-），男，博士，中國科學院光學天文重點實驗室國家天文臺博士后，研究方向為大數據;陳善軒（1995-），男，華南師范大學計算機學院碩士研究生，研究方向為區塊鏈、人工智能、數據分析。