結(jié)合社區(qū)發(fā)現(xiàn)和局部恢復(fù)碼的區(qū)塊鏈擴(kuò)容研究

姜承揚(yáng)，龐 俊，2，賈大宇，于明鶴，信俊昌，劉 晨

1.武漢科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，武漢 430070

2.智能信息處理與實(shí)時(shí)工業(yè)系統(tǒng)湖北省重點(diǎn)實(shí)驗(yàn)室，武漢 430070

3.東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 110169

4.東北大學(xué) 軟件學(xué)院，沈陽(yáng) 110169

近年來(lái)，區(qū)塊鏈技術(shù)快速興起，推動(dòng)了諸多行業(yè)的發(fā)展?，F(xiàn)有區(qū)塊鏈系統(tǒng)全節(jié)點(diǎn)必須存儲(chǔ)一份完整的區(qū)塊鏈賬本，雖然保障了數(shù)據(jù)安全，但不能滿足數(shù)據(jù)快速增長(zhǎng)的需求。區(qū)塊鏈存儲(chǔ)擴(kuò)容成為當(dāng)前區(qū)塊鏈領(lǐng)域的研究熱點(diǎn)之一。

目前已有許多研究提出了不同的區(qū)塊鏈存儲(chǔ)擴(kuò)容方案，根據(jù)數(shù)據(jù)是否存儲(chǔ)在區(qū)塊鏈上可分為兩類：鏈下方案[1-2]和鏈上方案[3-8]。鏈下方案將完整賬本數(shù)據(jù)存儲(chǔ)在第三方系統(tǒng)，區(qū)塊鏈上只保存少量的非數(shù)據(jù)信息。雖然降低了存儲(chǔ)開(kāi)銷，但提高了系統(tǒng)的中心化程度。因此許多研究工作采用鏈上方案[3-6]：利用分片技術(shù)，使區(qū)塊鏈網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)只需存儲(chǔ)完整賬本的一部分，從而降低節(jié)點(diǎn)的存儲(chǔ)壓力。但存在部分節(jié)點(diǎn)出故障可能導(dǎo)致數(shù)據(jù)丟失的問(wèn)題。因此文獻(xiàn)[7-8]使用RS（Reed-Solomon）糾刪碼[9]，在保證數(shù)據(jù)可恢復(fù)的前提下，降低系統(tǒng)存儲(chǔ)開(kāi)銷。但該方案在恢復(fù)數(shù)據(jù)時(shí)需從其他節(jié)點(diǎn)獲取較多的數(shù)據(jù)，帶來(lái)較大的網(wǎng)絡(luò)開(kāi)銷。并且未考慮節(jié)點(diǎn)之間的傳輸速度對(duì)數(shù)據(jù)請(qǐng)求效率的影響。若請(qǐng)求節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的傳輸速度較慢，則會(huì)增加跨節(jié)點(diǎn)請(qǐng)求區(qū)塊所花費(fèi)的時(shí)間。

本文首先針對(duì)現(xiàn)有方案數(shù)據(jù)請(qǐng)求效率不夠高的問(wèn)題，改進(jìn)文獻(xiàn)[10]中提出的能夠發(fā)現(xiàn)穩(wěn)定非重疊社區(qū)的社區(qū)發(fā)現(xiàn)算法，并將其擴(kuò)展到區(qū)塊鏈，實(shí)現(xiàn)區(qū)塊鏈節(jié)點(diǎn)分組，降低跨節(jié)點(diǎn)請(qǐng)求區(qū)塊的響應(yīng)時(shí)間。其大致流程如下：首先獲取區(qū)塊鏈網(wǎng)絡(luò)中各節(jié)點(diǎn)間的傳輸速度作為連接邊權(quán)重，然后對(duì)網(wǎng)絡(luò)進(jìn)行劃分，使得各分組內(nèi)部的平均連接速度盡可能大，從而降低組內(nèi)節(jié)點(diǎn)間互相傳輸數(shù)據(jù)的時(shí)間開(kāi)銷。

其次，針對(duì)現(xiàn)有方案數(shù)據(jù)恢復(fù)網(wǎng)絡(luò)開(kāi)銷較大的問(wèn)題，本文采用局部恢復(fù)碼[11（]local reconstruction codes，LRC）技術(shù)，減少了數(shù)據(jù)恢復(fù)時(shí)需要從其他節(jié)點(diǎn)獲取的數(shù)據(jù)。其基本思想是：將原始數(shù)據(jù)分為若干個(gè)集合，并為每個(gè)集合構(gòu)造局部編碼塊；對(duì)于單點(diǎn)故障，LRC碼只需要同一集合的數(shù)據(jù)塊和局部編碼塊即可實(shí)現(xiàn)數(shù)據(jù)恢復(fù)。

最后基于上述工作，提出了一種區(qū)塊鏈存儲(chǔ)擴(kuò)容方案：首先基于改進(jìn)的社區(qū)發(fā)現(xiàn)方法將區(qū)塊鏈劃分為組內(nèi)平均連接速度較大的多個(gè)分組；然后在每個(gè)分組內(nèi)使用LRC碼對(duì)區(qū)塊進(jìn)行編碼，獲取編碼塊和數(shù)據(jù)塊；最后將這些塊存儲(chǔ)到不同節(jié)點(diǎn)上（由一個(gè)分組的所有節(jié)點(diǎn)共同維護(hù)一份完整的賬本）。本文的主要貢獻(xiàn)如下：

（1）提出了一種基于改進(jìn)社區(qū)發(fā)現(xiàn)的節(jié)點(diǎn)分組方法。

（2）采用局部恢復(fù)碼技術(shù)，減少區(qū)塊恢復(fù)時(shí)所需的外部數(shù)據(jù)，從而降低了網(wǎng)絡(luò)開(kāi)銷。并提出了一種基于上述兩項(xiàng)工作的區(qū)塊鏈存儲(chǔ)擴(kuò)容方案。

（3）大量實(shí)驗(yàn)結(jié)果表明：與目前最佳方法相比，本文提出的存儲(chǔ)擴(kuò)容方案，在保持存儲(chǔ)開(kāi)銷和容錯(cuò)能力的基礎(chǔ)上，降低了區(qū)塊鏈節(jié)點(diǎn)請(qǐng)求非本地區(qū)塊的耗時(shí)。

1 相關(guān)工作

1.1 區(qū)塊鏈存儲(chǔ)擴(kuò)容

區(qū)塊鏈存儲(chǔ)擴(kuò)容方向已有大量研究成果，根據(jù)數(shù)據(jù)是否存儲(chǔ)在區(qū)塊鏈上可分為兩大類：鏈下存儲(chǔ)方案和鏈上存儲(chǔ)方案。第一類方案將區(qū)塊數(shù)據(jù)存儲(chǔ)在鏈下存儲(chǔ)系統(tǒng)，區(qū)塊鏈上僅存儲(chǔ)索引信息、驗(yàn)證信息及其他非數(shù)據(jù)信息。第二類方案只需要每個(gè)節(jié)點(diǎn)根據(jù)一定的規(guī)則存儲(chǔ)一部分賬本（多個(gè)節(jié)點(diǎn)共同維護(hù)一份賬本）。

1.1.1 鏈下方案

典型的鏈下存儲(chǔ)方案主要包括GEM2-Tree[1]和vChain[2]。GEM2-Tree將賬本存儲(chǔ)在云服務(wù)器中，基于MB-Tree和SMB-Tree驗(yàn)證查詢結(jié)果，并支持范圍查詢。vChain利用塊內(nèi)索引和塊間索引進(jìn)一步提高了驗(yàn)證計(jì)算的效率，并支持布爾范圍查詢。

這類方法不但能降低區(qū)塊鏈的存儲(chǔ)開(kāi)銷，一般還能支持較復(fù)雜的查詢操作。但存在3個(gè)問(wèn)題：（1）提高了系統(tǒng)中心化程度，降低了安全性；（2）賬本數(shù)據(jù)存儲(chǔ)于第三方服務(wù)器，存在隱私泄漏的隱患；（3）第三方服務(wù)器增大了經(jīng)濟(jì)成本[12]。因此本文并未采用鏈下方案。

1.1.2 鏈上方案

鏈上存儲(chǔ)方案的基本思想是：若干個(gè)節(jié)點(diǎn)共同維護(hù)一份完整的區(qū)塊鏈賬本，每個(gè)節(jié)點(diǎn)只存儲(chǔ)部分賬本數(shù)據(jù)[13]。典型代表方案包括CUB[3]、PocketChain[6]和BFTstore[8]等。鏈上方案根據(jù)使用技術(shù)的不同，又可分為基于分片的鏈上方案和基于編碼的鏈上方案兩類。

基于分片的鏈上方案：數(shù)據(jù)庫(kù)領(lǐng)域常采用分片技術(shù)將數(shù)據(jù)庫(kù)分割成多個(gè)劃分，分別存儲(chǔ)到不同的服務(wù)器中?；诜制逆溕洗鎯?chǔ)方案使用了類似的原理。例如CUB方案[3]根據(jù)每個(gè)節(jié)點(diǎn)的存儲(chǔ)容量分配一部分賬本數(shù)據(jù)，保證賬本在一個(gè)“共識(shí)單元”內(nèi)被完整存儲(chǔ)，并將經(jīng)常訪問(wèn)的區(qū)塊優(yōu)先存儲(chǔ)到對(duì)應(yīng)節(jié)點(diǎn)的存儲(chǔ)空間中。PocketChain[6]在公有鏈中運(yùn)用分片和無(wú)狀態(tài)客戶端，降低節(jié)點(diǎn)存儲(chǔ)需求的同時(shí)，有效地提升了系統(tǒng)的吞吐量。

雖然該類方法都能顯著降低存儲(chǔ)開(kāi)銷，但數(shù)據(jù)恢復(fù)能力較弱。若存儲(chǔ)著某一區(qū)塊的所有節(jié)點(diǎn)恰好都發(fā)生了故障，將導(dǎo)致數(shù)據(jù)永久丟失，降低了區(qū)塊鏈的安全性[14]。而基于編碼的鏈上方案擁有更好的容錯(cuò)能力，可以有效降低節(jié)點(diǎn)故障導(dǎo)致數(shù)據(jù)丟失的可能性。

基于編碼的鏈上方案：針對(duì)分片存儲(chǔ)的不足，有學(xué)者提出基于編碼存儲(chǔ)的方法，典型的編碼如糾刪碼。糾刪碼是分布式系統(tǒng)常用的數(shù)據(jù)容錯(cuò)技術(shù)，與傳統(tǒng)的多副本容錯(cuò)技術(shù)相比，具備更低的存儲(chǔ)開(kāi)銷和更好的數(shù)據(jù)恢復(fù)能力。因此本文采用了基于編碼的鏈上方案。

目前一些鏈上存儲(chǔ)方案使用了(n,m)-RS（簡(jiǎn)稱RS）糾刪碼[9]。Doriane等人[7]基于RS糾刪碼設(shè)計(jì)了一種LS（low storage）節(jié)點(diǎn)。LS節(jié)點(diǎn)將區(qū)塊切分為片段后進(jìn)行線性組合生成編碼片段并存儲(chǔ)。只需從其他節(jié)點(diǎn)獲取一定量的編碼片段，即可解碼恢復(fù)出原始區(qū)塊。Qi等人[8]提出了一種新的稱為BFT-store的區(qū)塊鏈存儲(chǔ)引擎，通過(guò)結(jié)合RS糾刪碼和BFT共識(shí)來(lái)提高存儲(chǔ)的可擴(kuò)展性。上述采用RS碼的鏈上存儲(chǔ)方案能有效地提升系統(tǒng)整體存儲(chǔ)性能，并擁有良好的數(shù)據(jù)恢復(fù)能力，但存在數(shù)據(jù)恢復(fù)網(wǎng)絡(luò)開(kāi)銷較大的問(wèn)題。使用RS碼的系統(tǒng)必須從各節(jié)點(diǎn)獲取至少n個(gè)塊才能恢復(fù)出原始數(shù)據(jù)，導(dǎo)致網(wǎng)絡(luò)開(kāi)銷較大[11]。(k,p,q)-LRC（簡(jiǎn)稱LRC）碼在單點(diǎn)故障時(shí)，僅需讀取同集合的數(shù)據(jù)塊和局部編碼塊即可實(shí)現(xiàn)恢復(fù)，比RS碼所需的數(shù)據(jù)更少，網(wǎng)絡(luò)開(kāi)銷也更小[11]。因此本文采用LRC碼代替RS碼。

此外，上述方案在分配數(shù)據(jù)時(shí)采用簡(jiǎn)單的隨機(jī)策略，可能導(dǎo)致獲取外部數(shù)據(jù)用時(shí)過(guò)長(zhǎng)。因?yàn)楣?jié)點(diǎn)向外部請(qǐng)求數(shù)據(jù)的效率會(huì)受節(jié)點(diǎn)間連接速度的影響。如果請(qǐng)求節(jié)點(diǎn)與存儲(chǔ)數(shù)據(jù)的目標(biāo)節(jié)點(diǎn)之間的連接速度更快，那么獲取數(shù)據(jù)的耗時(shí)將較短。反之，用時(shí)較長(zhǎng)。隨機(jī)分組并不能保證連接速度較快的節(jié)點(diǎn)分到一組。因此本文提出了一種基于社區(qū)發(fā)現(xiàn)的方法將連接速度較快的節(jié)點(diǎn)分到一組，縮短了跨節(jié)點(diǎn)請(qǐng)求區(qū)塊的響應(yīng)時(shí)間。

1.2 社區(qū)發(fā)現(xiàn)

2002年，Newman等人提出社區(qū)概念，以反映復(fù)雜網(wǎng)絡(luò)中數(shù)據(jù)的特征：社區(qū)內(nèi)節(jié)點(diǎn)連接緊密，與外部節(jié)點(diǎn)連接稀疏。社區(qū)發(fā)現(xiàn)就是尋找網(wǎng)絡(luò)中的固有社區(qū)劃分。目前，相關(guān)研究非常多，根據(jù)網(wǎng)絡(luò)是否加權(quán)，可分為在無(wú)權(quán)網(wǎng)絡(luò)中根據(jù)節(jié)點(diǎn)屬性來(lái)發(fā)現(xiàn)社區(qū)和在加權(quán)網(wǎng)絡(luò)上根據(jù)邊權(quán)重來(lái)發(fā)現(xiàn)社區(qū)兩類。因?yàn)閰^(qū)塊鏈網(wǎng)絡(luò)是加權(quán)的，所以與本文相關(guān)的是后一類，該類典型算法包括WGN[15]、Strength[16]和Lu等人[10]提出基于傳導(dǎo)性的社區(qū)發(fā)現(xiàn)算法等。與其他算法相比，Lu的算法能夠發(fā)現(xiàn)穩(wěn)定的非重疊社區(qū)，且性能更好，但其只用節(jié)點(diǎn)到社區(qū)的所有連接邊權(quán)重之和來(lái)反映節(jié)點(diǎn)與社區(qū)的聯(lián)系，而沒(méi)有考慮最大權(quán)重邊的影響。若直接應(yīng)用在區(qū)塊鏈中，無(wú)法獲得內(nèi)部平均連接速度較快的分組。因此本文對(duì)基于傳導(dǎo)性的社區(qū)發(fā)現(xiàn)算法[10]進(jìn)行改進(jìn)和擴(kuò)展，應(yīng)用到區(qū)塊鏈中，實(shí)現(xiàn)區(qū)塊鏈節(jié)點(diǎn)的分組。

2 存儲(chǔ)擴(kuò)容方案

本章提出了一種基于社區(qū)發(fā)現(xiàn)和局部恢復(fù)碼的區(qū)塊鏈存儲(chǔ)擴(kuò)容方案。

2.1 方案目標(biāo)

為解決區(qū)塊鏈系統(tǒng)存儲(chǔ)開(kāi)銷過(guò)高的問(wèn)題，并彌補(bǔ)現(xiàn)有方案的不足，本文提出的方案需要實(shí)現(xiàn)下列目標(biāo)：

（1）低冗余。單一節(jié)點(diǎn)無(wú)需在本地存儲(chǔ)完整的賬本，能通過(guò)網(wǎng)絡(luò)獲取賬本中的任意區(qū)塊。

（2）可恢復(fù)。在某些節(jié)點(diǎn)故障的情況下，可通過(guò)剩余節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行故障數(shù)據(jù)恢復(fù)。

（3）低時(shí)延。向外部節(jié)點(diǎn)獲取區(qū)塊的耗時(shí)要盡量短。

2.2 方案概述

方案概述如圖1所示。首先使用改進(jìn)的基于傳導(dǎo)性的社區(qū)發(fā)現(xiàn)算法，將區(qū)塊鏈網(wǎng)絡(luò)劃分為內(nèi)部平均連接速度較快的多個(gè)組，每個(gè)組分別維護(hù)一份賬本的副本；然后在每個(gè)組內(nèi)用LRC碼對(duì)區(qū)塊進(jìn)行編碼，組內(nèi)各節(jié)點(diǎn)分別存儲(chǔ)編碼后的部分賬本。存儲(chǔ)完成后，節(jié)點(diǎn)要獲取區(qū)塊數(shù)據(jù)，首先查詢?cè)搮^(qū)塊是否存儲(chǔ)在本地；若本地沒(méi)有，則優(yōu)先向存儲(chǔ)了該區(qū)塊的同組節(jié)點(diǎn)請(qǐng)求；若直接請(qǐng)求失敗，則需使用LRC碼解碼恢復(fù)該區(qū)塊。

圖1 擴(kuò)容方案概述Fig.1 Overview of expansion scheme

各節(jié)點(diǎn)內(nèi)部結(jié)構(gòu)如圖2所示。每個(gè)節(jié)點(diǎn)新增了4個(gè)功能模塊：store模塊、LRC模塊、communication模塊和分組模塊。store模塊負(fù)責(zé)存儲(chǔ)和管理區(qū)塊鏈數(shù)據(jù)，包括存儲(chǔ)原始區(qū)塊的賬本存儲(chǔ)域、存儲(chǔ)編碼塊數(shù)據(jù)的編碼塊存儲(chǔ)域和存儲(chǔ)通過(guò)外部請(qǐng)求獲得的區(qū)塊的緩存域。LRC模塊負(fù)責(zé)對(duì)區(qū)塊數(shù)據(jù)進(jìn)行編碼和解碼。communication模塊負(fù)責(zé)跨節(jié)點(diǎn)請(qǐng)求數(shù)據(jù)和響應(yīng)外部請(qǐng)求。分組模塊負(fù)責(zé)對(duì)區(qū)塊鏈網(wǎng)絡(luò)進(jìn)行節(jié)點(diǎn)分組。雖然每個(gè)節(jié)點(diǎn)都擁有分組模塊，但系統(tǒng)只選擇一個(gè)節(jié)點(diǎn)來(lái)調(diào)用該模塊進(jìn)行分組。

圖2 節(jié)點(diǎn)內(nèi)部結(jié)構(gòu)示意圖Fig.2 Diagram of node internal structure

下文分別介紹：基于社區(qū)發(fā)現(xiàn)的節(jié)點(diǎn)分組算法、基于局部恢復(fù)碼的區(qū)塊存儲(chǔ)方案和請(qǐng)求區(qū)塊的流程。

2.3 基于社區(qū)發(fā)現(xiàn)的節(jié)點(diǎn)分組算法

本節(jié)介紹改進(jìn)的社區(qū)發(fā)現(xiàn)算法，以及將其擴(kuò)展到區(qū)塊鏈，實(shí)現(xiàn)區(qū)塊鏈節(jié)點(diǎn)分組的具體過(guò)程。

現(xiàn)有的一些社區(qū)發(fā)現(xiàn)算法基于傳導(dǎo)性[10]來(lái)發(fā)現(xiàn)加權(quán)網(wǎng)絡(luò)中的社區(qū)，傳導(dǎo)性越低，社區(qū)內(nèi)部的聯(lián)系越緊密。傳導(dǎo)性的計(jì)算公式如公式（1）所示：

其中，cut(α,Gα)表示分組α所有切割邊（與分組相連但不屬于分組的邊）的權(quán)重之和，wα表示分組α的切割邊和其內(nèi)部連接邊的權(quán)重之和。

直接使用基于傳導(dǎo)性的社區(qū)發(fā)現(xiàn)算法不能滿足區(qū)塊鏈節(jié)點(diǎn)分組的需求。例如圖3中，若使用現(xiàn)有的算法，為使傳導(dǎo)性下降，節(jié)點(diǎn)f將加入分組α，但顯然節(jié)點(diǎn)f與分組β的連接速度更快。這是由于傳導(dǎo)性用所有連接邊權(quán)重之和來(lái)反映節(jié)點(diǎn)與分組的聯(lián)系，而區(qū)塊鏈所需的節(jié)點(diǎn)分組還應(yīng)考慮最大權(quán)重的影響。為得到內(nèi)部平均連接速度更快的分組，本文對(duì)基于傳導(dǎo)性的社區(qū)發(fā)現(xiàn)算法做出如下改進(jìn)：

（1）為了使最終的分組具有最小的傳導(dǎo)性，將網(wǎng)絡(luò)中所有相鄰的兩個(gè)節(jié)點(diǎn)分別組成臨時(shí)分組，并選擇其中傳導(dǎo)性最小的分組作為初始種子，然后選取符合條件的節(jié)點(diǎn)來(lái)逐步擴(kuò)展分組。

（2）將能否更大程度地降低分組的傳導(dǎo)性和該節(jié)點(diǎn)到分組的準(zhǔn)入系數(shù)是否小于1，作為是否允許節(jié)點(diǎn)加入分組的條件。準(zhǔn)入系數(shù)的計(jì)算公式如公式（2）所示：

其中，WnTα表示節(jié)點(diǎn)n到分組α的所有連接邊的權(quán)重，WnDTα表示節(jié)點(diǎn)n到分組α以外的所有連接邊的權(quán)重。圖3展示了分組的擴(kuò)展過(guò)程，對(duì)于由節(jié)點(diǎn)g、h、i構(gòu)成的分組β，其鄰接節(jié)點(diǎn)f加入分組β得到的臨時(shí)分組β″的傳導(dǎo)性，比節(jié)點(diǎn)j加入β得到的臨時(shí)分組β′的傳導(dǎo)性更小，且f到β″的準(zhǔn)入系數(shù)小于1，所以節(jié)點(diǎn)f加入分組構(gòu)成新的β。

圖3 分組擴(kuò)展過(guò)程Fig.3 Process of expanding group

然后將改進(jìn)的社區(qū)發(fā)現(xiàn)算法擴(kuò)展應(yīng)用到區(qū)塊鏈中。對(duì)于給定網(wǎng)絡(luò)，系統(tǒng)在啟動(dòng)后隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為leader執(zhí)行分組操作。leader節(jié)點(diǎn)首先收集各節(jié)點(diǎn)的連接情況構(gòu)成網(wǎng)絡(luò)圖，并將它們之間的連接速度作為節(jié)點(diǎn)連接邊的權(quán)重。然后使用改進(jìn)的基于傳導(dǎo)性的節(jié)點(diǎn)分組算法，劃分網(wǎng)絡(luò)得到節(jié)點(diǎn)分組。節(jié)點(diǎn)分組算法的偽代碼如算法1所示。

算法1節(jié)點(diǎn)分組算法

1.leader ask other nodes for connectivity and transfer rate to makeNetGraph

2.whileNetGraphis not null

3.2-group={G′,G″,G?,…}=findAll2-group(NetGraph)

4.Gi=MinConductance(2-group)

5.whileAdjacentGiis not null

6.n=findMaxReduceCon(Gi,AdjacentGi)

7.Gi′=Gi+n

8.if(Φ(Gi′)<Φ(Gi))&&?(Gi′,n)<1

9.Gi=Gi′

10.updateAdjacentGi

11.else

12.deletenfromAdjacentGi

13.deleteGifromNetGraph

14.leader sentG1,G2,…to corresponding node

算法第1行l(wèi)eader節(jié)點(diǎn)獲取區(qū)塊鏈網(wǎng)絡(luò)中各節(jié)點(diǎn)之間的連接，并將它們的數(shù)據(jù)傳輸速度作為連接邊的權(quán)重，構(gòu)造網(wǎng)絡(luò)圖NetGraph；第3、4行調(diào)用findAll2-group（）函數(shù)獲得NetGraph中所有由2個(gè)相鄰節(jié)點(diǎn)構(gòu)成的分組，然后調(diào)用MinConductance（）函數(shù)找出其中傳導(dǎo)性最小的，作為初始種子分組Gi；第6、7行遍歷Gi的鄰接節(jié)點(diǎn)，調(diào)用findMaxReduceCon（）函數(shù)找到其中能使分組的傳導(dǎo)性下降最多的節(jié)點(diǎn)n加入Gi，形成一個(gè)臨時(shí)的分組Gi′；第8~12行比較分組Gi′和原分組Gi的傳導(dǎo)性：如果Φ(Gi′)更小且n到Gi′的準(zhǔn)入系數(shù)小于1，則分組Gi′取代原分組成為新的Gi；第14行l(wèi)eader節(jié)點(diǎn)將分組結(jié)果發(fā)送給各個(gè)節(jié)點(diǎn)。

當(dāng)算法執(zhí)行結(jié)束，獲得的每個(gè)分組具有最小的傳導(dǎo)性，即分組的任意鄰接節(jié)點(diǎn)若加入分組，會(huì)降低該分組內(nèi)節(jié)點(diǎn)的平均連接速度。

2.4 基于局部恢復(fù)碼的區(qū)塊存儲(chǔ)

為了提高區(qū)塊鏈系統(tǒng)的整體存儲(chǔ)能力，本文采用LRC碼實(shí)現(xiàn)區(qū)塊存儲(chǔ)。其編碼過(guò)程如下所示：區(qū)塊鏈每個(gè)編碼周期開(kāi)始時(shí)，節(jié)點(diǎn)首先將本周期提交的新區(qū)塊按常規(guī)方式存儲(chǔ)到本地。當(dāng)新區(qū)塊的數(shù)量達(dá)到編碼所需的數(shù)量，則用LRC碼對(duì)新區(qū)塊進(jìn)行編碼，得到編碼塊和數(shù)據(jù)塊。然后各節(jié)點(diǎn)根據(jù)周期號(hào)和自身的節(jié)點(diǎn)號(hào)存儲(chǔ)相應(yīng)的塊，并刪除多余的塊，結(jié)束這一周期。圖4展示了一個(gè)編碼存儲(chǔ)過(guò)程的示例：對(duì)于含有7個(gè)節(jié)點(diǎn)的給定分組，使用（4，2，1）-LRC碼編碼區(qū)塊數(shù)據(jù)，然后存儲(chǔ)到不同節(jié)點(diǎn)。例如在周期2中，新生成了4個(gè)區(qū)塊B5~B8，用LRC碼編碼得到兩個(gè)局部編碼塊lc2-1（由B5和B6得到）、lc2-2（由B7和B8得到）和一個(gè)全局編碼塊gc2-1（由B5~B8得到）。然后節(jié)點(diǎn)a~g分別存儲(chǔ)不同的塊，周期2結(jié)束。具體算法偽代碼如算法2所示。

圖4 編碼存儲(chǔ)示例Fig.4 Example of encoding storage

算法2區(qū)塊存儲(chǔ)算法

輸入：當(dāng)前節(jié)點(diǎn)號(hào)n，新區(qū)塊號(hào)Bi，當(dāng)前周期號(hào)e，(k,p,q)-LRC碼

1.when get an ewblockBido

2.saveBiinto local ledger

3.ifBi==k×edo

4.usenandeto getSBNthrough calculation

5.ifSBNis block do

6.delete other block in{Bi-k,…,Bi}from ledger exceptSBN

7.else ifSBNis coding chunk do

8.{lci-1,…,lci-p,gci-1,…,gci-q}=use(k,p,q)-LRC to encode{Bi-k,…,Bi}

9.save SBN from{lci-1,…,lci-p;gci-1,…,gci-q}

10.delete block in{Bi-k,…,Bi}from ledger

11.e++

算法第2~4行將新區(qū)塊存入本地賬本，并判斷這一周期存儲(chǔ)的新區(qū)塊數(shù)量是否滿足編碼數(shù)量，若滿足則計(jì)算當(dāng)前節(jié)點(diǎn)在這一周期應(yīng)存儲(chǔ)的塊號(hào)SBN；第5、6行如果SBN對(duì)應(yīng)的是普通區(qū)塊，那么將這一周期存儲(chǔ)的其他新區(qū)塊從賬本中刪去，只保留SBN對(duì)應(yīng)的區(qū)塊；第7~10行如果SBN對(duì)應(yīng)編碼塊，那么使用(k,p,q)-LRC碼對(duì)這一周期存儲(chǔ)的新區(qū)塊進(jìn)行編碼，得到SBN對(duì)應(yīng)的編碼塊并存儲(chǔ)到本地，然后將本輪周期存儲(chǔ)的新區(qū)塊從本地賬本中刪除。

為了讓每個(gè)節(jié)點(diǎn)的存儲(chǔ)開(kāi)銷總體上相等，節(jié)點(diǎn)不固定存儲(chǔ)原始區(qū)塊或編碼塊。因?yàn)榫幋a塊的大小與編碼時(shí)所使用的最大原始區(qū)塊的大小相同，如果節(jié)點(diǎn)總是存儲(chǔ)編碼塊，其所需的空間一定比總存儲(chǔ)原始區(qū)塊的節(jié)點(diǎn)多。此外，為避免節(jié)點(diǎn)編碼壓力過(guò)大和分發(fā)編碼塊時(shí)可能導(dǎo)致的網(wǎng)絡(luò)阻塞，leader節(jié)點(diǎn)不負(fù)責(zé)編碼。

2.5 區(qū)塊請(qǐng)求

本節(jié)闡述擴(kuò)容方案中節(jié)點(diǎn)如何請(qǐng)求獲取區(qū)塊。由于本地沒(méi)有存儲(chǔ)完整賬本，因此節(jié)點(diǎn)有三種方式獲取區(qū)塊數(shù)據(jù)：從本地獲取、直接請(qǐng)求其他節(jié)點(diǎn)獲取和解碼恢復(fù)該區(qū)塊。節(jié)點(diǎn)請(qǐng)求某一區(qū)塊時(shí)，需要依次嘗試上述三種方式。請(qǐng)求區(qū)塊的具體流程如圖5所示。

圖5 區(qū)塊請(qǐng)求流程圖Fig.5 Flowchart of requesting blocks

流程圖中的各步驟均省略了對(duì)區(qū)塊的驗(yàn)證過(guò)程，在實(shí)際過(guò)程中節(jié)點(diǎn)會(huì)在獲取區(qū)塊后，用存儲(chǔ)在本地的區(qū)塊頭來(lái)驗(yàn)證區(qū)塊是否正確，從而過(guò)濾錯(cuò)誤區(qū)塊。

基于LRC碼的區(qū)塊恢復(fù)：當(dāng)節(jié)點(diǎn)必須通過(guò)解碼恢復(fù)區(qū)塊時(shí)，其向外部請(qǐng)求同周期區(qū)塊的策略會(huì)影響數(shù)據(jù)恢復(fù)的耗時(shí)和網(wǎng)絡(luò)開(kāi)銷。本文采用的LRC碼只需要局部塊，就可以實(shí)現(xiàn)單點(diǎn)故障的恢復(fù)。例如圖6中，節(jié)點(diǎn)a需要區(qū)塊B2，但無(wú)法從本地或節(jié)點(diǎn)b獲取該塊，所以必須通過(guò)解碼恢復(fù)B2。由于節(jié)點(diǎn)a自身存儲(chǔ)了B1，所以其在恢復(fù)B2時(shí)，只需向節(jié)點(diǎn)e請(qǐng)求局部編碼塊lc1-1，再使用LRC碼解碼即可恢復(fù)出B2。如果示例中使用的是（4，3）-RS碼，則節(jié)點(diǎn)a必須從其他節(jié)點(diǎn)獲取至少3個(gè)塊才能恢復(fù)B2，網(wǎng)絡(luò)開(kāi)銷更高。具體算法偽代碼如算法3所示。

圖6 解碼恢復(fù)示例Fig.6 Example of decoding for recovery

算法3區(qū)塊恢復(fù)算法

輸入：當(dāng)前節(jié)點(diǎn)號(hào)n，請(qǐng)求區(qū)塊號(hào)B，(k,p,q)-LRC碼

1.getepochofBthrough calculation

2.{local data chunks}and{local coding chunks}=ask other nodes for local chunks in the sameepochwithB

3.if number of local chunks==(k/p)+1

4.B=use(k,p,q)-LRC to decode{local data chunks}and{local coding chunks}

5.else

6.ask other nodes for{k chunks}in sameepochwithB

7.B=use(k,p,q)-LRC to decode{k chunks}

8.useBto update cache

算法第1、2行計(jì)算出區(qū)塊B所在的周期號(hào)epoch，并向同組的節(jié)點(diǎn)請(qǐng)求區(qū)塊B對(duì)應(yīng)的局部編碼塊和數(shù)據(jù)塊；第3~7行如果獲取到足夠的局部塊，那么使用(k,p,q)-LRC碼解碼局部塊得到區(qū)塊B，否則需要向其他節(jié)點(diǎn)請(qǐng)求k個(gè)與B同周期的塊來(lái)解碼出區(qū)塊B；第8行用區(qū)塊B更新緩存。

緩存替換策略：一些鏈上存儲(chǔ)方案采用了緩存來(lái)存儲(chǔ)頻繁使用的區(qū)塊。由于節(jié)點(diǎn)存儲(chǔ)容量有限，緩存需要經(jīng)常更新?，F(xiàn)有方案常用“最近最少使用”策略作為緩存替換策略。本文在每個(gè)節(jié)點(diǎn)上建立了緩存域，來(lái)降低請(qǐng)求區(qū)塊的時(shí)間，并綜合考慮區(qū)塊的使用頻繁度、獲取耗時(shí)制定了策略：每當(dāng)節(jié)點(diǎn)向外部請(qǐng)求獲取區(qū)塊后，若節(jié)點(diǎn)緩存域未滿，則將直接其加入；若緩存域已滿，則需要找到緩存域中所有比新區(qū)塊價(jià)值小的區(qū)塊，然后用新區(qū)塊替換其中價(jià)值最小的塊。緩存價(jià)值的計(jì)算公式如公式（3）所示：

其中，Ti表示獲取區(qū)塊i所需的時(shí)間；Fi表示節(jié)點(diǎn)對(duì)區(qū)塊i訪問(wèn)的頻繁程度值，即訪問(wèn)次數(shù)；D的初始值為0，每當(dāng)發(fā)生緩存替換后，更新D的值為被替換區(qū)塊的Vi值，每當(dāng)該區(qū)塊被訪問(wèn)后，D重置為0。

3 性能分析

本章在模擬數(shù)據(jù)集上進(jìn)行了大量實(shí)驗(yàn)，對(duì)比了本文提出的方案和baseline方法的存儲(chǔ)開(kāi)銷、區(qū)塊請(qǐng)求時(shí)延、區(qū)塊恢復(fù)的網(wǎng)絡(luò)開(kāi)銷和容錯(cuò)能力，驗(yàn)證了其保持了與最優(yōu)方案近似的存儲(chǔ)開(kāi)銷和相同的容錯(cuò)能力，還有效降低了跨節(jié)點(diǎn)請(qǐng)求區(qū)塊的時(shí)間。

3.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

本文在開(kāi)源區(qū)塊鏈平臺(tái)HyperledgerFabricv1.1上實(shí)現(xiàn)了提出的方案。所有實(shí)驗(yàn)都在一臺(tái)配備2.10 GHz 8核CPU，64 GB RAM和2 TB磁盤空間的機(jī)器上完成。利用VMware虛擬機(jī)建立24個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)分配2 GB內(nèi)存和20 GB硬盤，并安裝ubuntu18.04系統(tǒng)。

實(shí)驗(yàn)在模擬網(wǎng)絡(luò)環(huán)境下進(jìn)行，首先使用文獻(xiàn)[17]中提出的著名基準(zhǔn)測(cè)試框架生成加權(quán)網(wǎng)絡(luò)圖，然后根據(jù)網(wǎng)絡(luò)圖中的各連接邊的權(quán)重來(lái)設(shè)置區(qū)塊鏈網(wǎng)絡(luò)中各節(jié)點(diǎn)間的傳輸速度，從而模擬實(shí)際網(wǎng)絡(luò)情況。實(shí)驗(yàn)數(shù)據(jù)集為使用fabricSDK循環(huán)生成的模擬數(shù)據(jù)集，通過(guò)建立200個(gè)賬戶，讓它們隨機(jī)互相轉(zhuǎn)賬，產(chǎn)生100 000條交易，共2 000個(gè)區(qū)塊。

baseline方法：（1）fabric的存儲(chǔ)方案（簡(jiǎn)稱方案1）。（2）結(jié)合分片[3-6]和多副本的存儲(chǔ)方案（簡(jiǎn)稱方案2）。首先根據(jù)節(jié)點(diǎn)數(shù)量劃分完整賬本，然后為每一個(gè)分片構(gòu)造三個(gè)副本并隨機(jī)存儲(chǔ)于不同節(jié)點(diǎn)。（3）結(jié)合RS碼[7-8]和分組的區(qū)塊鏈存儲(chǔ)方案（簡(jiǎn)稱方案3）。將文獻(xiàn)[7-8]采用的降低存儲(chǔ)開(kāi)銷的RS碼擴(kuò)展后應(yīng)用于fabric平臺(tái)，并使用與本文提出方案一致的節(jié)點(diǎn)分組方法。

本文共提出了兩種存儲(chǔ)擴(kuò)容方案：第一種采用原始的基于社區(qū)發(fā)現(xiàn)[10]的節(jié)點(diǎn)分組方法和LRC碼的存儲(chǔ)方案（簡(jiǎn)稱方案4）；第二種采用本文改進(jìn)的基于社區(qū)發(fā)現(xiàn)的節(jié)點(diǎn)分組方法和LRC碼的存儲(chǔ)方案（簡(jiǎn)稱方案5）。其中LRC碼和RS碼的編碼塊數(shù)量設(shè)為相同。

3.2 存儲(chǔ)開(kāi)銷

本節(jié)主要評(píng)估區(qū)塊鏈的存儲(chǔ)開(kāi)銷，分別測(cè)試了方案5和三種對(duì)比方法存儲(chǔ)每個(gè)區(qū)塊的空間開(kāi)銷。沒(méi)有與方案4進(jìn)行比較，因?yàn)槠渑c方案5都采用LRC碼進(jìn)行存儲(chǔ)。實(shí)驗(yàn)時(shí)不設(shè)置故障節(jié)點(diǎn)，將數(shù)據(jù)集提交到區(qū)塊鏈，當(dāng)節(jié)點(diǎn)總數(shù)從6增加到24時(shí)，區(qū)塊的平均存儲(chǔ)開(kāi)銷如圖7所示。圖7可見(jiàn)：方案5每存儲(chǔ)一個(gè)區(qū)塊平均所需的存儲(chǔ)空間并不隨著節(jié)點(diǎn)數(shù)量的增加而明顯增長(zhǎng)，與方案2、3的結(jié)果類似。因?yàn)榉桨?和5都采用了糾刪碼來(lái)降低區(qū)塊鏈存儲(chǔ)開(kāi)銷，所以具有近似的變化趨勢(shì)，驗(yàn)證了本文提出的存儲(chǔ)擴(kuò)容方案保持了與目前最佳方案3近似的存儲(chǔ)開(kāi)銷。此外，因?yàn)橄到y(tǒng)中節(jié)點(diǎn)分組數(shù)量增加，且每個(gè)分組需要共同存儲(chǔ)一份賬本，所以方案3和5在節(jié)點(diǎn)數(shù)量為12時(shí)存儲(chǔ)開(kāi)銷增大。

圖7 區(qū)塊的平均存儲(chǔ)開(kāi)銷對(duì)比Fig.7 Comparison of average storage overhead perblock

3.3 區(qū)塊請(qǐng)求時(shí)延

本節(jié)主要評(píng)估本文方案和方案2和3從發(fā)起區(qū)塊請(qǐng)求到獲取目標(biāo)區(qū)塊所需的時(shí)間。沒(méi)有與方案1比較是因?yàn)閒abric的每個(gè)節(jié)點(diǎn)都有完整賬本，不需要向外部請(qǐng)求區(qū)塊。

首先從區(qū)塊鏈網(wǎng)絡(luò)中隨機(jī)選取1/6的節(jié)點(diǎn)作為實(shí)驗(yàn)節(jié)點(diǎn)，然后從剩余節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)中隨機(jī)選取50個(gè)區(qū)塊作為測(cè)試數(shù)據(jù)。接著讓系統(tǒng)正常運(yùn)行，然后在各個(gè)實(shí)驗(yàn)節(jié)點(diǎn)上請(qǐng)求測(cè)試數(shù)據(jù)并記錄花費(fèi)的時(shí)間。不同方案跨節(jié)點(diǎn)請(qǐng)求區(qū)塊的平均時(shí)延如圖8所示。

圖8 跨節(jié)點(diǎn)請(qǐng)求區(qū)塊時(shí)間對(duì)比Fig.8 Comparison of requesting blocks time across node

圖8可見(jiàn)：方案3~5獲取測(cè)試數(shù)據(jù)的耗時(shí)較短。因?yàn)閷?duì)區(qū)塊鏈網(wǎng)絡(luò)進(jìn)行了劃分，得到了內(nèi)部連接速度更快的節(jié)點(diǎn)分組，所以節(jié)點(diǎn)可以從組內(nèi)獲取區(qū)塊。方案3和5比方案4的時(shí)延要更短，因?yàn)榉桨?和5使用了改進(jìn)的節(jié)點(diǎn)分組方法，獲得的分組連接速度更快。此外，方案2中各節(jié)點(diǎn)存儲(chǔ)的區(qū)塊是隨機(jī)分配的，當(dāng)前節(jié)點(diǎn)所需的區(qū)塊可能存儲(chǔ)在網(wǎng)絡(luò)距離很遠(yuǎn)的節(jié)點(diǎn)上，所以平均響應(yīng)時(shí)間較長(zhǎng)。實(shí)驗(yàn)結(jié)果表明本文方案提出的基于社區(qū)發(fā)現(xiàn)的節(jié)點(diǎn)分組方法可有效減小跨節(jié)點(diǎn)請(qǐng)求區(qū)塊的時(shí)延。

3.4 區(qū)塊恢復(fù)的網(wǎng)絡(luò)開(kāi)銷

本節(jié)主要評(píng)估本文采用的LRC碼和現(xiàn)有最佳方案所使用的RS碼在區(qū)塊恢復(fù)時(shí)的網(wǎng)絡(luò)開(kāi)銷。由于區(qū)塊恢復(fù)時(shí)，向外部請(qǐng)求的數(shù)據(jù)越多，網(wǎng)絡(luò)開(kāi)銷就越大，區(qū)塊恢復(fù)時(shí)間也就越長(zhǎng)。因此分別測(cè)試了方案3和方案5恢復(fù)缺失區(qū)塊所需的平均時(shí)間。

首先讓系統(tǒng)正常啟動(dòng)，接著隨機(jī)關(guān)閉1/6的節(jié)點(diǎn)，來(lái)模擬故障的發(fā)生。然后從剩余節(jié)點(diǎn)中隨機(jī)選取一個(gè)節(jié)點(diǎn)，在該節(jié)點(diǎn)上請(qǐng)求故障節(jié)點(diǎn)所存儲(chǔ)的區(qū)塊，并記錄恢復(fù)區(qū)塊所花費(fèi)的時(shí)間。兩方案恢復(fù)缺失區(qū)塊的平均時(shí)間如圖9所示。

圖9可見(jiàn)：本文方案的平均恢復(fù)時(shí)間更短，這是因?yàn)長(zhǎng)RC碼最少只需要相應(yīng)的局部編碼塊和數(shù)據(jù)塊就可以恢復(fù)出所請(qǐng)求的區(qū)塊。實(shí)驗(yàn)結(jié)果表明，本文方案采用的LRC碼能降低數(shù)據(jù)恢復(fù)時(shí)的網(wǎng)絡(luò)開(kāi)銷。

圖9 區(qū)塊恢復(fù)時(shí)間對(duì)比Fig.9 Comparison of blocks reconstructing time

3.5 容錯(cuò)能力

在實(shí)際環(huán)境中，區(qū)塊鏈部分節(jié)點(diǎn)故障的情況是很常見(jiàn)的。因此本節(jié)分別計(jì)算了不同方案在部分節(jié)點(diǎn)故障時(shí)的數(shù)據(jù)完整性。當(dāng)網(wǎng)絡(luò)中1/5、1/4、1/3的節(jié)點(diǎn)故障時(shí)，不同方案能恢復(fù)出完整數(shù)據(jù)的可能性如表1所示。表中沒(méi)有比較方案1，因?yàn)楣?jié)點(diǎn)故障不會(huì)影響fabric的數(shù)據(jù)完整性；也沒(méi)有比較方案4，因?yàn)槠渑c方案5都基于LRC碼實(shí)現(xiàn)，它們具有相同的容錯(cuò)能力。

表1 容錯(cuò)能力對(duì)比Table 1 Comparison of fault tolerance

從表中可看出，方案3和方案5在設(shè)置的實(shí)驗(yàn)條件下均能夠恢復(fù)出所有的數(shù)據(jù)，而方案2在故障節(jié)點(diǎn)較多時(shí)，很容易發(fā)生數(shù)據(jù)丟失。因?yàn)閷?duì)于三副本技術(shù)，若存儲(chǔ)了某一區(qū)塊所有副本的節(jié)點(diǎn)恰好都發(fā)生了故障，這些數(shù)據(jù)將不再可達(dá)。而糾刪碼可以在一定限度內(nèi)利用剩余的數(shù)據(jù)恢復(fù)出原始的數(shù)據(jù)。因此，使用本文方案的區(qū)塊鏈系統(tǒng)具有較好的故障容錯(cuò)能力。

4 總結(jié)

本文首先對(duì)現(xiàn)有基于傳導(dǎo)性的社區(qū)發(fā)現(xiàn)算法進(jìn)行改進(jìn)，提出一種基于社區(qū)發(fā)現(xiàn)的區(qū)塊鏈節(jié)點(diǎn)分組方法，將連接速度較快的節(jié)點(diǎn)分為一組，降低了跨節(jié)點(diǎn)區(qū)塊請(qǐng)求的響應(yīng)時(shí)間。然后在上述工作基礎(chǔ)上，結(jié)合LRC碼技術(shù)，提出了一種新的區(qū)塊鏈存儲(chǔ)擴(kuò)容方案，使得每個(gè)節(jié)點(diǎn)只存儲(chǔ)部分編碼后的賬本，保證系統(tǒng)在降低存儲(chǔ)開(kāi)銷和網(wǎng)絡(luò)開(kāi)銷的同時(shí)擁有較好的數(shù)據(jù)恢復(fù)能力。大量實(shí)驗(yàn)結(jié)果表明，本文提出的擴(kuò)容方案與目前最優(yōu)方法相比，不僅保持了近似的存儲(chǔ)開(kāi)銷和相同的容錯(cuò)能力，還能提高跨節(jié)點(diǎn)區(qū)塊請(qǐng)求效率。未來(lái)可改進(jìn)基于LRC碼的存儲(chǔ)策略，提出開(kāi)銷更低、容錯(cuò)能力更好的編碼方案，進(jìn)一步減少節(jié)點(diǎn)的存儲(chǔ)空間。