尹笑蓉 朱承宇 趙斌 張召

摘要：區(qū)塊鏈系統(tǒng)采用全復制的數據存儲機制，為每個節(jié)點保留整個區(qū)塊鏈的完整副本，系統(tǒng)擴展性差. 同時由于區(qū)塊鏈系統(tǒng)中拜占庭節(jié)點的存在，導致傳統(tǒng)分布式系統(tǒng)中使用的分片方案不能被直接應用于區(qū) 塊鏈系統(tǒng)中.本文結合糾刪碼和拜占庭容錯算法，使每個區(qū)塊的存儲消耗由O（n）降到0（1），增強了系統(tǒng)的 可擴展性.本文還提出了對區(qū)塊數據進行劃分的方法，在降低存儲冗余的同時減小對查詢效率的影響.提 出了無需網絡通信的編碼塊存儲方法，降低了系統(tǒng)存儲和通信開銷.還提出了區(qū)塊鏈節(jié)點加入和退出的動 態(tài)重編碼方法，既保證系統(tǒng)的穩(wěn)定性，又降低了系統(tǒng)重編碼開銷.最后，在開源區(qū)塊鏈系統(tǒng)CITA上實現， 并通過充分的實驗，證明系統(tǒng)可擴展性、可用性和存儲效率提升.

關鍵詞：區(qū)塊鏈;糾刪碼;拜占庭容錯;存儲可擴展性

中圖分類號：TP302?????? 文獻標志碼：A DOI： 10.3969/j.issn.1000-5641.2021.05.005

Erasure code partition storage based on the CITA blockchain

YIN Furong1， ZHU Chengyu1， ZHAO Bin2， ZHANG Zhao1

（X. School of Data Science and Engineering， East China Normal University， Shanghai 200062， China;

2. School of Computer and Electronic Information/School of Artificial Intelligence，

Nanjing Normal University， Nanjing 210023， China）

Abstract： Blockchain system adopts full replication data storage mechanism， which retains a complete copy of the whole block chain for each node. The scalability of the system is poor. Due to the existence of Byzantine nodes in the blockchain system， the shard scheme used in the traditional distributed system cannot be directly applied in the blockchain system. In this paper， the storage consumption of each block is reduced from O（n） to O（1） by combining erasure code and Byzantine fault-tolerant algorithm， and the scalability of the system is enhanced. This paper proposes a method to partition block data， which can reduce the storage redundancy and affect the query efficiency less. A coding block storage method without network communication is proposed to reduce the system storage and communication overhead. In addition， a dynamic recoding method for entry and exit of blockchain nodes is proposed， which not only ensures the reliability of the system， but also reduces the system recoding overhead. Finally， the system is implemented on the open source blockchain system CITA， and through sufficient experiments， it is proved that the system has improved scalability， availability and storage efficiency.

Keywords： blockchain; erasure code; Byzantine fault tolerance; storage scalability

收稿日期：2021-08-07

基金項目：國家自然科學基金（U1811264，U1911203， 6197215（2）

通信作者：張召，女，教授，博士生導師，研究方向為區(qū)塊鏈系統(tǒng)研發(fā)、海量數據管理與分析

E-mail： zhzhang@dase.ecnu.edu.cn

0引 言

區(qū)塊鏈是一種分布式、去中心化、無需信任的數據庫系統(tǒng)，正在被越來越廣泛地應用于金融管 理、銀行、保險等領域.在區(qū)塊鏈網絡中，每個節(jié)點都需要遵守基于密碼學的規(guī)則，每筆交易都需要與 網絡中的其他節(jié)點達成共識，不需要任何第三方機構背書，降低了運行成本.

隨著區(qū)塊鏈系統(tǒng)規(guī)模的不斷擴大，全復制的方法已經不能適應海量數據的增長需求.全復制存儲 機制中數據量隨節(jié)點數量增加線性增長，整個系統(tǒng)需要投入巨大的存儲空間來保存區(qū)塊，在有N個參與者的情況下，每個塊的總體存儲消耗為O（N）.目前，逐步提高的交易吞吐率導致存儲成為了整個區(qū) 塊鏈擴展的瓶頸.研究者一直在尋找一種高效的區(qū)塊鏈擴容方案.

為了緩解區(qū)塊鏈系統(tǒng)的存儲擴展性問題，業(yè)界提出了許多方案.如只在客戶端保留區(qū)塊頭部，在 全節(jié)點保留著完整區(qū)塊的輕量級客戶端[1-21.其雖然減輕了客戶端的存儲壓力，但每個全節(jié)點仍保留所 有區(qū)塊數據的完整副本.閃電網絡收集多個微支付，最終僅將余額信息上傳到區(qū)塊鏈網絡上，其雖 然減輕了每個節(jié)點的存儲壓力，但沒有從根本上解決區(qū)塊數據全復制的問題.分片技術[4-5]將區(qū)塊鏈網 絡分成多個組，每個組存儲系統(tǒng)中的部分數據，但在同一組內，仍采取了全復制的存儲方式.

糾刪碼是一種數據保護方法，最初被用于解決網絡傳輸中的丟包問題，后被推廣到存儲領域，可 提高存儲的可靠性.本文繼承BFT （Byzantine Fault Tolerance，拜占庭容錯）協(xié)議的假設，實現了一 種基于糾刪碼的區(qū)塊鏈系統(tǒng)，即在有n個節(jié)點的系統(tǒng)中，最多有/=「?]個節(jié)點是能夠入侵甚至破 壞整個網絡的拜占庭節(jié)點.為了保證基于糾刪碼的系統(tǒng)在有/個節(jié)點發(fā)生故障時仍能正常運行，須保 證糾刪碼編碼后的冗余塊個數不小于/，同時為降低冗余度，令冗余塊個數為/.與全復制的存儲方式 相比，本文實現的方法可以降低數據存儲的冗余度，且不降低數據的可靠性.

本文的主要貢獻如下：

（1）設計了糾刪碼編碼前原始區(qū)塊數據劃分的方法.采用區(qū)塊區(qū)間劃分的方法對一個區(qū)塊區(qū)間內 的區(qū)塊進行劃分，使得進行編碼塊存儲時，一個區(qū)塊的信息只存在于一個節(jié)點中;

（2）設計了無需節(jié)點間通信的編碼塊存儲方法.利用區(qū)塊頭部的共識節(jié)點公鑰地址列表全局一致 的特性，在不需要節(jié)點通信的情況下，每個節(jié)點只保留一個對應的編碼塊，全網擁有所有編碼塊的完 整信息;

（3）設計了依據節(jié)點的加入和退出動態(tài)同步編碼的方法.通過動態(tài)同步編碼，解決節(jié)點加入和退 出引起的系統(tǒng)存儲消耗和容錯能力下降的問題;

（4）在開源區(qū)塊鏈系統(tǒng)CITA （https：//citahub.com/）上實現了以上設計.

1 相關工作

糾刪碼（Erasure Code）[6-7]是一種可以在存儲系統(tǒng)和通信系統(tǒng)中實現高可用性和高可靠性的前向 錯誤糾正技術.在網絡傳輸中，其主要用于丟包恢復;在存儲系統(tǒng)中，其主要應用于提高存儲的可靠 性.與多副本的冗余復制方式相比，糾刪碼技術能夠在保證數據可靠性的基礎上降低數據存儲的冗 余度.

CITA是一個開源的企業(yè)級聯(lián)盟區(qū)塊鏈.CITA采用BFT共識算法，當系統(tǒng)中有1/3的節(jié)點作惡 的情況下，仍能正常工作.其采用全復制的冗余存儲方式，每個節(jié)點存儲整個區(qū)塊鏈的完整副本.CITA 對自身的共識機制和底層邏輯進行了深度優(yōu)化.

隨著區(qū)塊鏈系統(tǒng)應用的領域越來越廣泛，區(qū)塊鏈系統(tǒng)存儲帶來的存儲擴展性差，對服務器節(jié)點存 儲性能要求高的問題漸漸地顯露出來，這造成了區(qū)塊鏈技術落地困難和存儲成本高的問題.國內外針

對區(qū)塊鏈的存儲問題做了許多研究.總體而言，雖然眾多的模型各有特色，但它們都有許多不足之處， 如賈大宇等[8]的模型對數據進行不平均存儲，導致系統(tǒng)的去中心化水平降低，Dai等[9]只是提出了一 個框架，并沒有形成完整的編碼方案，而Xu等[10]設計的方法不適用于交易吞吐量較高的應用.

目前，糾刪碼在分布式系統(tǒng)中的應用已比較成熟，但由于區(qū)塊鏈系統(tǒng)中拜占庭節(jié)點的存在，不能 將其移植到區(qū)塊鏈中.將糾刪碼技術應用于區(qū)塊鏈存儲系統(tǒng)優(yōu)化的研究較少，Perard等[11]在區(qū)塊鏈系 統(tǒng)中存儲能力較弱的節(jié)點上使用糾刪碼，雖在一定程度上降低了區(qū)塊鏈的存儲消耗，但導致系統(tǒng)去中 心化水平降低.同時，其并未處理拜占庭節(jié)點的錯誤信息，系統(tǒng)的穩(wěn)定性較差. Qi等[12]的研究將糾刪 碼和拜占庭容錯算法相結合，不僅降低了區(qū)塊鏈系統(tǒng)的存儲消耗，更使系統(tǒng)數據可靠性得到保障，但 其編碼、查詢效率較低，在實際應用中延遲較高.

2?????? 基于糾刪碼的區(qū)塊鏈分片存儲方法設計

2.1系統(tǒng)架構

本系統(tǒng)是一個基于糾刪碼分片存儲的區(qū)塊鏈系統(tǒng).每個用戶通過客戶端將交易發(fā)送到系統(tǒng)，并暫 存在交易池中.每隔一段時間，交易池中的交易被打包成一個區(qū)塊，在節(jié)點之間對其進行共識，然后緩 存在系統(tǒng)中，最后經過糾刪碼編碼，分布存儲在系統(tǒng)的節(jié)點上.系統(tǒng)框架如圖1所示，3個主要組成部 分為：糾刪碼模塊、查詢模塊和動態(tài)重編碼模塊.

2.1.1糾刪碼模塊

糾刪碼模塊包括編碼器和解碼器兩個子模塊.區(qū)塊緩存中的區(qū)塊序列，經過區(qū)塊區(qū)間劃分，形成 原始數據塊，通過編碼器編碼，形成糾刪碼編碼塊.每個節(jié)點根據自身在共識列表中的位置，存儲對應 的編碼塊，丟棄其余塊.系統(tǒng)并不是在一個節(jié)點上將區(qū)塊編碼成數據塊，然后將它們分派給其他節(jié)點， 而是在每個節(jié)點上獨立編碼，無需節(jié)點間網絡通信.所有的節(jié)點都遵循相同的編碼規(guī)則，每個塊的可 用性得到了保證.解碼器可以通過底層網絡從其他節(jié)點獲取編碼塊，利用糾刪碼解碼對原始數據塊進 行恢復.

2.1.2 查詢模塊

查詢模塊接收來自客戶端的查詢請求，并進行響應.當查詢模塊處理查詢區(qū)塊B的請求時，有三

種不同的情況：

（1）如果區(qū)塊B存儲在本地，查詢模塊在沒有任何網絡通信的情況下將它返回客戶端;

（2）如果目標節(jié)點^⑶是正確的，則查詢模塊可以從^⑶中獲取區(qū)塊B ;

（3）如果目標節(jié)點M （B）是拜占庭節(jié)點，則查詢模塊必須通過糾刪碼模塊中的解碼器恢復區(qū)塊B . 最終，查詢模塊將驗證來自其他節(jié)點的所有數據，避免通過解碼恢復不正確的塊數據.

2.1.3???????? 動態(tài)重編碼模塊

當節(jié)點加入或退出系統(tǒng)時，動態(tài)重編碼模塊開始工作.為了在確保數據可用性的同時減少冗余， 歷史數據可能需要被重新編碼.在進行重編碼時，需要通過糾刪碼模塊中的解碼器，從其他節(jié)點獲取 數據.為了減少重編碼開銷，采用動態(tài)重編碼策略，當冗余度達到閾值時，對歷史數據進行重新編碼. 此外，在刪除舊編碼塊之前，每個節(jié)點都要確保其余的塊已經完成了重新編碼，以保證塊的可用性.

2.2區(qū)塊區(qū)間劃分方法

本文提出對區(qū)塊區(qū)間進行劃分形成糾刪碼數據塊的方法，區(qū)塊區(qū)間是區(qū)塊鏈中一段連續(xù)的區(qū)塊 序列，將區(qū)塊區(qū)間作為糾刪碼編碼的基本單位具有兩個優(yōu)點：首先，在生成多個區(qū)塊后對區(qū)塊區(qū)間進 行編碼，而非每產生一個區(qū)塊進行一次編碼，可降低糾刪碼編碼開銷;其次，避免了請求區(qū)塊信息時， 向多個節(jié)點請求數據的問題，可降低網絡資源的消耗.該方法中區(qū)塊區(qū)間的大小用連續(xù)區(qū)塊的數量來 表示，如圖2所示區(qū)塊區(qū)間，其大小為10.

為了保證每個區(qū)塊或交易的查詢最多只涉及一次網絡通信或糾刪碼解碼，需要使每個區(qū)塊僅存 于一個糾刪碼數據塊中.同時，糾刪碼編碼算法要求輸入的&個數據塊的長度相等.所以，在對區(qū)塊區(qū) 間進行劃分時，需保證：（1）每個區(qū)塊只能被分配到一個數據塊中;（2） —個區(qū)塊區(qū)間內的區(qū)塊需盡可能 平均地分配到各個數據塊中.由以上兩個條件，可以將每個數據塊中區(qū)塊數量s的計算公式總結為下 式（1）：

其中n為區(qū)塊區(qū)間的大小，k為糾刪碼編碼所需的數據塊數量，n%k為n對k求余.

通過以上劃分方法得到數據塊，在長度較短的數據塊后補充冗余數據，使得k個數據塊的長度相 等.經過糾刪碼編碼，生成m個糾刪碼冗余塊，與數據塊一起組成k + rn個編碼塊.

以上區(qū)塊劃分及糾刪碼編碼過程采用的算法詳見算法1.算法1的時間復雜度為O （n）.算法1通 過循環(huán)檢查新生區(qū)塊的數量判斷是否達到輸入的區(qū)間大小標準（第1行），滿足條件后根據式（1）處理 得到數據塊（第2-5行），經過數據預處理使得數據塊達到編碼要求（第6、7行），通過編碼得到編碼塊 結果（第8、9行）.該算法實時監(jiān)測區(qū)塊數量變化，滿足條件后對一個區(qū)間中的區(qū)塊進行編碼，不需要 每個區(qū)塊編碼一次，采用批處理的思想，可以提高編碼的效率.數據預處理階段可以通過開辟新線程， 增加系統(tǒng)并行性，進一步提高編碼效率.

算法1區(qū)塊區(qū)間劃分編碼算法

輸入：包含^個區(qū)塊的區(qū)塊區(qū)間，數據塊數量^ ，冗余塊數量m 輸出：fc + m個編碼塊

1：????? While新生成的區(qū)塊數量大于等于n

2：????? If n%k == 0

3：????? 將n個區(qū)塊平均分配到個數據塊中

4：????? Else

5：????? 前n%fc個數據塊每個存n/fc+ 1個區(qū)塊，其他每個數據塊存n/fc個區(qū)塊

6：????? End if

7：????? 獲得長度最長的數據塊長度maxl

8：????? 在其余數據塊后補“ 0”，使數據塊長度達到一致maxl

9：????? 將fc個數據塊作為糾刪碼的輸人進行編碼

10：?? 得到fc + m個編碼塊

11：?? End while

采用以上算法，當區(qū)塊區(qū)間大小n = 10 ，數據塊數量fc = 3 ，冗余塊數量m = 1時，區(qū)塊劃分及糾 刪碼編碼結果如圖3所示.

2.3無需網絡通信的編碼塊存儲方法

為降低系統(tǒng)的冗余度，經過糾刪碼編碼后，每個節(jié)點僅保存一個編碼塊，可將其他編碼塊刪除.這 需要與其他節(jié)點達成共識，才能保證每個節(jié)點保存的區(qū)塊不同，同時保證系統(tǒng)中保存著所有的編碼塊 信息.然而，區(qū)塊鏈系統(tǒng)運行在一個不可靠的環(huán)境中，網絡通信會增加系統(tǒng)的不穩(wěn)定性，還會導致系統(tǒng) 的吞吐率降低.為了解決上述問題，本文利用每個節(jié)點上相同區(qū)塊的共識節(jié)點公鑰列表具有一致性的 特性，設計了一種無需網絡通信的編碼塊存儲方法.如圖4所示，對原始數據進行劃分并編碼之后，根 據本節(jié)點公鑰地址在所有節(jié)點公鑰地址序列中的位置，保存對應于本節(jié)點的編碼塊，并刪除其余編碼 塊.由于公鑰地址有序序列在所有節(jié)點上都是一致的，所以節(jié)點間不需要網絡通信就可以僅保存自己 所對應的編碼塊，同時保證系統(tǒng)中包含所有編碼塊的信息.

CITA采用鍵值數據庫存儲數據，在存儲編碼塊時，為能夠在請求區(qū)塊時從數據庫中查詢到其所 在的編碼塊，需增加一個表來存儲區(qū)塊高度與編碼塊編號的映射關系.該方式會增大系統(tǒng)的存儲消耗， 并增加查詢的響應延遲.為了在查詢時快速利用區(qū)塊高度得到其所在的編碼塊，本文根據計算每個數 據塊中區(qū)塊數量的式（1），對編碼塊的編號進行定義.將編碼塊編號以文本形式表示，它由兩部分組 成，第一部分標識該編碼塊所處的區(qū)塊區(qū)間&第二部分標識該編碼塊處于該區(qū)塊區(qū)間的第D個數據 塊，兩部分用下劃線連接，表示為^_乃.如圖4所示，高度為4的區(qū)塊位于區(qū)塊0?9所對應的區(qū)塊區(qū) 間，其區(qū)塊區(qū)間^ = 0，又因其在該區(qū)間的第D = 1個數據塊，故高度為4的區(qū)塊所對應的編碼塊編號 為 0—1.0_2 0_3

當用戶向系統(tǒng)查詢區(qū)塊時，可以通過區(qū)塊高度計算得到其所處的區(qū)塊區(qū)間和數據塊號，進而得到 其所對應編碼塊的編號.由區(qū)塊高度計算編碼塊編號的算法詳見算法2.算法2的時間復雜度為O （1）.

算法2編碼塊編號計算算法

輸入：區(qū)塊高度＼區(qū)塊區(qū)間大小^，數據塊個數&，冗余塊個數爪 輸出：編碼塊編號S_D

1：????? S = h/n

2：????? If n%k == 0

3：????? D = （h°%n） /（n/k）

4：????? Else if h°%n < （n/k +（1） * （n%k）

5：????? D = （h%n） /（n/k + （1）

6：????? Else

7：????? D = n%k + （h%n — （n/k + 1 ）*（ n%k）） /（n/k）

8：????? End if

9：????? Return S_D

假設系統(tǒng)對前10個區(qū)塊的編碼結果如圖5所示，節(jié)點0接收到客戶端對于區(qū)塊3的請求，即區(qū)塊 高度為3，由上述計算方法，得到S = 0（3/10 = 0），D = 0（3%10）/4 = 0），即S_D = 0_0.節(jié)點0讀取 共識節(jié)點公鑰地址有序序列，比對本地公鑰地址在有序序列中的位置，若節(jié)點0上不存儲0_0編碼塊， 則向公鑰地址有序序列中的第D個節(jié)點（節(jié)點（3）發(fā)出對編碼塊0_0的請求.節(jié)點0將從節(jié)點3得到的 區(qū)塊數據返回給客戶端.

2.4動態(tài)重編碼方法

區(qū)塊鏈是一種分布式賬本，賬本數據的一致性依賴多個節(jié)點的共同維護.新機構加入時，需為其 搭建一個新的節(jié)點，并將其加入區(qū)塊鏈系統(tǒng);原有機構退出時，需將該節(jié)點從系統(tǒng)中刪除.為了應對區(qū) 塊鏈系統(tǒng)中節(jié)點加入或退出造成的重編碼時間消耗過大的問題，本文提出了動態(tài)重編碼的方法.

CITA區(qū)塊鏈系統(tǒng)中存在不參與區(qū)塊共識的普通節(jié)點.普通節(jié)點的加入或退出不會影響區(qū)塊的共 識進程.普通節(jié)點加入后只需要提供查詢功能即可，不需要保存編碼塊.為了在不保存編碼塊的情況 下保證普通節(jié)點的查詢功能，普通節(jié)點需要同步共識節(jié)點的編碼塊索引.當用戶向普通節(jié)點發(fā)起查詢 請求時，普通節(jié)點根據從共識節(jié)點處同步的索引，向對應的共識節(jié)點發(fā)起請求，實現查詢功能.

共識節(jié)點的加入與區(qū)塊的共識同步進行，如圖6所示.在生成一個區(qū)塊區(qū)間時，新的共識節(jié)點加 入會導致共識節(jié)點列表的變化，該區(qū)塊區(qū)間的前6個區(qū)塊的共識節(jié)點為{N0， N1， N2， N3}，而后4個區(qū) 塊的共識節(jié)點為{N0， N1， N2， N3， N4}.這導致對該區(qū)塊區(qū)間中的區(qū)塊進行糾刪碼編碼后，存儲編碼塊的共識節(jié)點列表可以是{N0， N1， N2， N3}，也可以是{N0， N1， N2， N3， N4}.為了統(tǒng)一存儲該區(qū)塊區(qū)間的共識節(jié)點列表，對區(qū)塊區(qū)間共識節(jié)點列表做如下定義：區(qū)塊區(qū)間最后一個區(qū)塊的共識節(jié)點列表為此 區(qū)塊區(qū)間的共識節(jié)點列表.由此可得存儲10?19區(qū)塊區(qū)間編碼塊的共識節(jié)點列表為{N0， N1， N2， N3， N4}.

共識節(jié)點加入后，系統(tǒng)中共識節(jié)點的數量會發(fā)生變化.CITA區(qū)塊鏈系統(tǒng)保證系統(tǒng)中共識節(jié)點數 #和拜占庭節(jié)點數P的數量關系為：N>3F+ 1，即（N-（1）/3.當系統(tǒng)中共識節(jié)點數量變?yōu)?N + 1時，系統(tǒng)所能容忍的拜占庭節(jié)點的數量變?yōu)镕'，F'滿足F'>F.若保持原來的編碼參數不變， 系統(tǒng)只能在F個節(jié)點作惡時恢復丟失的數據.此時若系統(tǒng)中有F'個節(jié)點作惡，且F' > F，則不能保證 可以通過糾刪碼解碼將原始數據恢復出來，從而不能保證系統(tǒng)的數據可用性.共識節(jié)點從系統(tǒng)中退出 時也面臨相同的情況.為了解決上述問題，需要在新的共識節(jié)點加入時，對歷史數據進行重新編碼.

本文提出了動態(tài)糾刪碼重編碼算法，即在保證系統(tǒng)中所有區(qū)塊可恢復的情況下，不在節(jié)點加入或 退出時立刻對歷史數據進行重新編碼，而是根據節(jié)點加入或退出后，系統(tǒng)所容忍拜占庭節(jié)點數量是否 增多或減少，來動態(tài)地對歷史數據進行重新編碼.采用此方法可以降低重編碼帶來的系統(tǒng)開銷，提高 系統(tǒng)的效率.動態(tài)重編碼算法詳見算法3.算法3的時間復雜度為0（1）.算法3的第4-7行和第 9-12行分別對節(jié)點增加和刪除的情況進行處理，由公式F=「（N-（1）/3]可得拜占庭節(jié)點數量，如果 節(jié)點數量的增加沒有使拜占庭節(jié)點數量發(fā)生變化，或節(jié)點數量的減少恰好可以使拜占庭節(jié)點數量減 少相同的個數，則原來的編碼模式可以保證系統(tǒng)的穩(wěn)定性.由于并不是每次節(jié)點增刪都會導致拜占庭 節(jié)點數量的變化，采用動態(tài)重編碼的方法可以減少重編碼的開銷.

算法3動態(tài)重編碼算法

輸入：歷史共識節(jié)點數量I ，新共識節(jié)點數量新區(qū)塊區(qū)間，歷史編碼塊數據 輸出：編碼結果

1：????? F'=「（，—（1）/3LF=「（N — （1）/3]

2：對新的區(qū)塊區(qū)間，采用^共識節(jié)點列表進行糾刪碼編碼 3：? If N; >N

4：????? If F' == F

5：????? 新節(jié)點保存歷史編碼塊索引

6：????? Else

7：????? 采用N'共識節(jié)點列表，對歷史編碼塊數據進行重編碼

8：????? End? if

9：????? Else if??????? N?????

10：?? If F' =???????? F — 1

11：?? 不處理歷史數據

12：?? Else

13：?? 采用N'共識節(jié)點列表，對歷史編碼塊數據進行重編碼

14：?? End if

15：?? End if

16：保存編碼結果

3實驗與評價

3.1實驗環(huán)境和配置

（1）實驗環(huán)境

本文實驗在以下實驗環(huán)境中進行，其中操作系統(tǒng)為Ubuntu18.04，配置AMD Ryzen 5 3550H （4核8線程，主頻2.1 GHz，加速頻率3.7 GHz）處理器，內存大小為16 GB，硬盤大小為512 G.本文 設計的算法使用Rust程序設計語言在0.25.2版本的CITA上實現.

（2）參數配置

實驗測試的節(jié)點數量為4，糾刪碼編碼的數據塊數量為3，冗余塊數量為1.

3.2實驗結果與分析

本文的實驗評價主要參考4個指標：存儲消耗、編碼性能、響應延遲和穩(wěn)定性.

3.2.1存儲消耗

存儲消耗的評估分為兩部分，首先，為了證明糾刪碼編碼的存儲方式能降低系統(tǒng)的存儲消耗，將 糾刪碼編碼存儲與全復制存儲相比，評價糾刪碼編碼存儲在空間占用方面的優(yōu)化效果，其中全復制的 存儲系統(tǒng)中存儲消耗與節(jié)點數成正比;其次，調整編碼區(qū)間的大小，評估糾刪碼編碼區(qū)塊區(qū)間大小對 每個區(qū)塊存儲消耗的影響，由此結論可根據需求調整區(qū)塊區(qū)間的大小，降低存儲消耗.

（1）全復制的存儲方式與糾刪碼的存儲方式的存儲消耗對比

區(qū)塊區(qū)間的大小固定為10，區(qū)塊大小固定為80 kB，節(jié)點數量從4到15變化.如圖7所示，展示了 在不同節(jié)點設置下存儲每個塊的平均存儲消耗.對于全復制的存儲方式（all），由于每個節(jié)點都需要保存區(qū)塊鏈的完整副本，每個區(qū)塊的平均存儲容量隨著節(jié)點數量的增加而線性增加.對于糾刪碼的存儲 方式（ec），隨著節(jié)點的增加，每個區(qū)塊的平均存儲容量產生輕微的波動，且總是小于所有區(qū)塊大小的 2倍.全復制存儲每個區(qū)塊的存儲消耗與糾刪碼存儲每個區(qū)塊的存儲消耗的比值（%）隨著節(jié)點的數量 增加而線性增加.

由以上實驗分析得出，隨著節(jié)點數量的增加，糾刪碼存儲方式與全復制方式相比表現出更加明顯 的存儲性能優(yōu)勢，糾刪碼的存儲方式在有多個節(jié)點的區(qū)塊鏈系統(tǒng)中具有更高的應用價值.同時，采用 糾刪碼的存儲方式，系統(tǒng)的存儲壓力不會因為節(jié)點數量的變化而發(fā)生大幅度的變化，無須因為節(jié)點的 增加調整系統(tǒng)存儲配置，降低了系統(tǒng)維護工作量.

（2）糾刪碼編碼區(qū)塊區(qū)間大小對每個區(qū)塊存儲消耗的影響

糾刪碼區(qū)塊區(qū)間的大小會在一定程度上影響每個區(qū)塊的平均存儲容量，固定系統(tǒng)中的節(jié)點數為4， 固定區(qū)塊的大小為80 kB，區(qū)塊區(qū)間在10?21間變化.圖8所顯示的是每個區(qū)塊的平均存儲消耗與 區(qū)塊區(qū)間大小的關系.

如圖8實線所示，每個區(qū)塊的存儲消耗會隨區(qū)塊區(qū)間的變化產生周期性波動，這與本文設計的數 據塊劃分策略有關.當區(qū)塊區(qū)間大小s= 10時，數據塊的劃分模式為（4，3，（3），其中4個區(qū)塊形成一個 編碼塊，剩余的6個區(qū)塊，每3個生成一個編碼塊，最終在較短的編碼塊后補0，然后進行糾刪碼編碼 運算，得到冗余塊的大小應約等于4個區(qū)塊形成的編碼塊的大小，最終編碼塊的模式可表示為 （4， 3， 3， （4）.每個區(qū)塊的平均存儲消耗為（4 +3+ 3 +（4）/10 = 1.4 .同理可以得到其他區(qū)塊區(qū)間大小所對 應的每個區(qū)塊的存儲消耗.在一個區(qū)塊區(qū)間變化周期中，當編碼塊的模式為沁，，，…，O0時（a為每個 糾刪碼編碼塊中區(qū)塊數量的近似值），每個區(qū)塊的平均存儲消耗最低;當編碼塊的模式為（a+1，a， a，…，a + （1）時，每個區(qū)塊的平均存儲消耗最高.

如圖8趨勢線所示，在保持節(jié)點數量為4不變的情況下，雖然隨著區(qū)塊區(qū)間的增大，每個區(qū)塊的 平均存儲消耗總體呈下降的趨勢，但實線所示折線具有周期性，適當調整區(qū)塊區(qū)間大小可使糾刪碼的存儲方式的優(yōu)勢達到最大值，并不需要盲目增大區(qū)塊區(qū)間來提高存儲效率.

3.2.2編碼性能

全復制的存儲系統(tǒng)存儲一個區(qū)塊的延遲約為2 ms，糾刪碼存儲的編碼操作會造成編碼延遲，本小 節(jié)首先對編碼延遲做了測試.其次，對于降低編碼延遲的區(qū)塊區(qū)間劃分編碼算法，對比區(qū)塊區(qū)間劃分 與單個區(qū)塊劃分編碼方法所需編碼時間，評估其優(yōu)化效果.最后，綜合評價區(qū)塊區(qū)間劃分編碼算法中 的參數區(qū)塊區(qū)間大小對整體編碼延遲的影響和對單個區(qū)塊編碼延遲的影響.在實際應用中可通過調 整區(qū)塊區(qū)間大小，降低編碼延遲.

（1）編碼延遲

在進行區(qū)塊存儲時，與全復制的存儲方式相比，糾刪碼的存儲方式需要時間進行糾刪碼的編碼. CITA系統(tǒng)中，保存一個區(qū)塊需要約2 ms，當糾刪碼區(qū)塊區(qū)間為12時，一次糾刪碼編碼需要約20 ms， 平均到每個區(qū)塊上為1.6 ms.由以上數據，可以總結得出，使用基于糾刪碼的存儲方式，在存儲時消耗 的時間約為全復制存儲方式的1.8倍.相對于糾刪碼編碼存儲方式帶來的從O （n）到O （1）的存儲空間 優(yōu)化而言，糾刪碼編碼造成的時間開銷是可以接受的.

（2）區(qū)塊區(qū)間劃分與單個區(qū)塊劃分編碼方法所需編碼時間對比

確定區(qū)塊大小為80 kB，節(jié)點數量為4，區(qū)塊區(qū)間的大小為12?30，對比使用兩種方法編碼一個 區(qū)塊區(qū)間內的區(qū)塊所消耗的時間.實驗結果如圖9所示，采用區(qū)塊區(qū)間劃分的方法進行編碼能夠節(jié)省 編碼的時間，且隨著區(qū)塊區(qū)間的增大，采用區(qū)塊區(qū)間編碼的優(yōu)勢也隨之增大，在區(qū)塊區(qū)間大小為30時， 采用區(qū)塊區(qū)間編碼的方法節(jié)省了近45%的編碼時間.獲得編碼性能提升的主要原因為區(qū)塊區(qū)間劃分 的方法采用了批處理思想，減小了每次編碼預處理及編碼器啟動時間在總編碼時間中的占比.

（3）區(qū)塊區(qū)間大小對編碼延遲的影響

如圖10所示，隨著區(qū)塊區(qū)間的增大，每個區(qū)間的編碼時間也隨之增大.

但將該區(qū)間的編碼時間平均到區(qū)塊區(qū)間內的每個區(qū)塊上，得到每個區(qū)塊的平均編碼時間與區(qū)塊區(qū)間大小關系如圖ii所示，隨著區(qū)塊區(qū)間的增大，區(qū)塊的平均編碼時間呈下降趨勢.增大區(qū)塊區(qū)間的 大小，可以降低每個區(qū)塊的平均編碼時間，但區(qū)塊區(qū)間的增大會使得一次編碼的時間增長，在具體使 用過程中，可以根據需求調整糾刪碼編碼區(qū)塊區(qū)間大小.

3.2.3響應延遲

在采用糾刪碼存儲方式的系統(tǒng)中，每個節(jié)點上只保存部分區(qū)塊的信息，當所需區(qū)塊不存在所請求 的節(jié)點上或系統(tǒng)中的節(jié)點發(fā)生故障時，需要利用網絡傳輸和糾刪碼的解碼功能將原始數據恢復出來， 數據的恢復操作會造成響應延遲.采用全復制存儲方式的CITA系統(tǒng)，由于沒有節(jié)點間通信，用戶查 詢請求的響應延遲約為1.35 ms.

采用糾刪碼存儲方式后，查詢存在本地節(jié)點的區(qū)塊，響應延遲約為9.5 ms，查詢存在其他節(jié)點的區(qū)塊，響應延遲約為44.05 ms.雖然與全復制的存儲方式相比，由于區(qū)塊數據的提取和節(jié)點間的通信， 響應延遲有所增加，但44 ms的延遲時間不會影響用戶的使用體驗.若不采用算法1而是采用對每個 區(qū)塊進行編碼存儲的方法，則向某個節(jié)點請求一個區(qū)塊得到響應所需的時間約為70 ms，約為采用算 法1響應延遲的7倍.

若查詢時發(fā)現某編碼塊丟失，采用糾刪碼解碼方式恢復數據，再返回給用戶，響應延遲約為238 ms. 用戶會感受到輕微的卡頓，但如果系統(tǒng)運行在一個較可靠的環(huán)境中，節(jié)點發(fā)生故障的概率將大大降低， 從而很少需要進行解碼恢復，不會影響用戶的使用體驗.

3.2.4穩(wěn)定性

系統(tǒng)的穩(wěn)定性體現了系統(tǒng)應對外界干擾和故障的能力，采用全復制存儲方式的系統(tǒng)能夠容忍小 于等于?的拜占庭節(jié)點數.采用糾刪碼存儲方式的系統(tǒng)穩(wěn)定性以功能測試的形式，通過模擬系統(tǒng)故 障情況進行.首先，從系統(tǒng)外部將存儲的數據塊從數據庫中刪除，模擬數據丟失的情況.其次，通過命 令行指令強制節(jié)點掉線，模擬系統(tǒng)中的拜占庭節(jié)點.在以上兩組模擬功能測試中，糾刪碼的解碼恢復 功能都能正常運行，系統(tǒng)能夠在發(fā)生故障時，通過糾刪碼解碼恢復功能給出準確的查詢結果，系統(tǒng)能 夠容忍小于等于^的拜占庭節(jié)點數，沒有因糾刪碼的加入降低系統(tǒng)的穩(wěn)定性.

4結論

本文將糾刪碼與拜占庭容錯算法相結合，在滿足系統(tǒng)容錯率的基礎上，降低了區(qū)塊存儲的冗余度. 本文提出了原始區(qū)塊數據劃分的方法，提高了區(qū)塊查詢的速度，提出了無需節(jié)點間通信的存儲編碼塊 方法，減少了節(jié)點間的通信開銷.提出了根據節(jié)點的加入和刪除動態(tài)同步編碼的方法，降低了歷史數 據重編碼的系統(tǒng)消耗.最后，通過實驗測試，驗證了系統(tǒng)的可用性和效率提升.

本文的方法將系統(tǒng)的存儲空間復雜度由O（n）降低到O（1），但不可避免因糾刪碼編碼解碼造成的 時間消耗，在后續(xù)的工作中將重視糾刪碼的編碼和解碼效率的優(yōu)化.

[參考文獻]

[1]CASTRO M， LISKOV B. Practical byzantine fault tolerance [C]//Proceedings of the Third Symposium on Operating Systems Design and Implementation. 1999： 173-186.

[2]WOOD G. Ethereum： A secure decentralised generalised transaction ledger [J]. Ethereum Project Yellow Paper， 2014， 151： 1-32.

[3] BURCHERT C， DECHER C， WATTENHOFER R. Scalable funding of bitcoin micropayment channel networks [J]. Royal Society Open Science， 2018， 5（8）： 180089.

[4]DANG H， DINH T T A， LOGHIN D， et al. Towards scaling blockchain systems via sharding [C]// Proceedings of the 2019 International Conference on Management of Data. 2019： 123-140.

[5] AL-BASSAM M， SONNINO A， BANO S， et al. Chainspace： A sharded smart contracts platform [EB/OL]. （2017-08-1（2） [2021-07-05]. http：//arXiv.org/pdf/1708.03778.pdf.

[6] REED I S， SOLOMON G. Polynomial codes over certain finite fields [J]. Journal of the Society for Industrial & Applied Mathematics， 1960， 8（2）： 300-304.

[7]LIN W K， CHIU D M， LEE Y B. Erasure code replication revisited [C]//Proceedings of the Fourth International Conference on Peer- to-Peer Computing. IEEE， 2004： 90-97.

[8]賈大宇，信俊昌，王之瓊，等.區(qū)塊鍵的存儲容量可擴展模型[J].計算機科學與探索，2018， 12（4）： 525-535.

[9] DAI M， ZHANG S， WANG H， et al. A Low Storage Room Requirement Framework for Distributed Ledger in Blockchain [J]. IEEE Access， 2018（6）： 22970-22975.

[10]XU Y， HUANG Y. Segment blockchain： A size reduced storage mechanism for blockchain. IEEE Access， 2020（8）： 17434-17441.

[11]PERARD D， LACAN J， BACHY Y， et al. Erasure code-based low storage blockchain node [C]//2018 IEEE International Conference on Internet of Things and IEEE Green Computing and Communications and IEEE Cyber， Physical and Social Computing and IEEE Smart Data. IEEE， 2018： 1622-1627.

[12]QI X， ZHANG Z， JIN C， et al. BFT-Store： Storage partition for permissioned blockchain via erasure coding [C]// 2020 IEEE 36th International Conference on Data Engineering. IEEE， 2020： 1926-1929.

（責任編輯：林晶）