基于CITA區(qū)塊鏈的糾刪碼分片存儲(chǔ)實(shí)現(xiàn)

尹笑蓉 朱承宇 趙斌 張召

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

關(guān)鍵詞：區(qū)塊鏈;糾刪碼;拜占庭容錯(cuò);存儲(chǔ)可擴(kuò)展性

中圖分類(lèi)號(hào)：TP302?????? 文獻(xiàn)標(biāo)志碼：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

基金項(xiàng)目：國(guó)家自然科學(xué)基金（U1811264，U1911203， 6197215（2）

通信作者：張召，女，教授，博士生導(dǎo)師，研究方向?yàn)閰^(qū)塊鏈系統(tǒng)研發(fā)、海量數(shù)據(jù)管理與分析

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

0引 言

區(qū)塊鏈?zhǔn)且环N分布式、去中心化、無(wú)需信任的數(shù)據(jù)庫(kù)系統(tǒng)，正在被越來(lái)越廣泛地應(yīng)用于金融管 理、銀行、保險(xiǎn)等領(lǐng)域.在區(qū)塊鏈網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都需要遵守基于密碼學(xué)的規(guī)則，每筆交易都需要與 網(wǎng)絡(luò)中的其他節(jié)點(diǎn)達(dá)成共識(shí)，不需要任何第三方機(jī)構(gòu)背書(shū)，降低了運(yùn)行成本.

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

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

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

本文的主要貢獻(xiàn)如下：

（1）設(shè)計(jì)了糾刪碼編碼前原始區(qū)塊數(shù)據(jù)劃分的方法.采用區(qū)塊區(qū)間劃分的方法對(duì)一個(gè)區(qū)塊區(qū)間內(nèi) 的區(qū)塊進(jìn)行劃分，使得進(jìn)行編碼塊存儲(chǔ)時(shí)，一個(gè)區(qū)塊的信息只存在于一個(gè)節(jié)點(diǎn)中;

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

（3）設(shè)計(jì)了依據(jù)節(jié)點(diǎn)的加入和退出動(dòng)態(tài)同步編碼的方法.通過(guò)動(dòng)態(tài)同步編碼，解決節(jié)點(diǎn)加入和退 出引起的系統(tǒng)存儲(chǔ)消耗和容錯(cuò)能力下降的問(wèn)題;

（4）在開(kāi)源區(qū)塊鏈系統(tǒng)CITA （https：//citahub.com/）上實(shí)現(xiàn)了以上設(shè)計(jì).

1 相關(guān)工作

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

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

隨著區(qū)塊鏈系統(tǒng)應(yīng)用的領(lǐng)域越來(lái)越廣泛，區(qū)塊鏈系統(tǒng)存儲(chǔ)帶來(lái)的存儲(chǔ)擴(kuò)展性差，對(duì)服務(wù)器節(jié)點(diǎn)存 儲(chǔ)性能要求高的問(wèn)題漸漸地顯露出來(lái)，這造成了區(qū)塊鏈技術(shù)落地困難和存儲(chǔ)成本高的問(wèn)題.國(guó)內(nèi)外針

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

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

2?????? 基于糾刪碼的區(qū)塊鏈分片存儲(chǔ)方法設(shè)計(jì)

2.1系統(tǒng)架構(gòu)

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

2.1.1糾刪碼模塊

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

2.1.2 查詢(xún)模塊

查詢(xún)模塊接收來(lái)自客戶(hù)端的查詢(xún)請(qǐng)求，并進(jìn)行響應(yīng).當(dāng)查詢(xún)模塊處理查詢(xún)區(qū)塊B的請(qǐng)求時(shí)，有三

種不同的情況：

（1）如果區(qū)塊B存儲(chǔ)在本地，查詢(xún)模塊在沒(méi)有任何網(wǎng)絡(luò)通信的情況下將它返回客戶(hù)端;

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

（3）如果目標(biāo)節(jié)點(diǎn)M （B）是拜占庭節(jié)點(diǎn)，則查詢(xún)模塊必須通過(guò)糾刪碼模塊中的解碼器恢復(fù)區(qū)塊B . 最終，查詢(xún)模塊將驗(yàn)證來(lái)自其他節(jié)點(diǎn)的所有數(shù)據(jù)，避免通過(guò)解碼恢復(fù)不正確的塊數(shù)據(jù).

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

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

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

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

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

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

通過(guò)以上劃分方法得到數(shù)據(jù)塊，在長(zhǎng)度較短的數(shù)據(jù)塊后補(bǔ)充冗余數(shù)據(jù)，使得k個(gè)數(shù)據(jù)塊的長(zhǎng)度相 等.經(jīng)過(guò)糾刪碼編碼，生成m個(gè)糾刪碼冗余塊，與數(shù)據(jù)塊一起組成k + rn個(gè)編碼塊.

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

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

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

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

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

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

4：????? Else

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

6：????? End if

7：????? 獲得長(zhǎng)度最長(zhǎng)的數(shù)據(jù)塊長(zhǎng)度maxl

8：????? 在其余數(shù)據(jù)塊后補(bǔ)“ 0”，使數(shù)據(jù)塊長(zhǎng)度達(dá)到一致maxl

9：????? 將fc個(gè)數(shù)據(jù)塊作為糾刪碼的輸人進(jìn)行編碼

10：?? 得到fc + m個(gè)編碼塊

11：?? End while

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

2.3無(wú)需網(wǎng)絡(luò)通信的編碼塊存儲(chǔ)方法

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

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

當(dāng)用戶(hù)向系統(tǒng)查詢(xún)區(qū)塊時(shí)，可以通過(guò)區(qū)塊高度計(jì)算得到其所處的區(qū)塊區(qū)間和數(shù)據(jù)塊號(hào)，進(jìn)而得到 其所對(duì)應(yīng)編碼塊的編號(hào).由區(qū)塊高度計(jì)算編碼塊編號(hào)的算法詳見(jiàn)算法2.算法2的時(shí)間復(fù)雜度為O （1）.

算法2編碼塊編號(hào)計(jì)算算法

輸入：區(qū)塊高度＼區(qū)塊區(qū)間大小^，數(shù)據(jù)塊個(gè)數(shù)&，冗余塊個(gè)數(shù)爪 輸出：編碼塊編號(hào)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

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

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

區(qū)塊鏈?zhǔn)且环N分布式賬本，賬本數(shù)據(jù)的一致性依賴(lài)多個(gè)節(jié)點(diǎn)的共同維護(hù).新機(jī)構(gòu)加入時(shí)，需為其 搭建一個(gè)新的節(jié)點(diǎn)，并將其加入?yún)^(qū)塊鏈系統(tǒng);原有機(jī)構(gòu)退出時(shí)，需將該節(jié)點(diǎn)從系統(tǒng)中刪除.為了應(yīng)對(duì)區(qū) 塊鏈系統(tǒng)中節(jié)點(diǎn)加入或退出造成的重編碼時(shí)間消耗過(guò)大的問(wèn)題，本文提出了動(dòng)態(tài)重編碼的方法.

CITA區(qū)塊鏈系統(tǒng)中存在不參與區(qū)塊共識(shí)的普通節(jié)點(diǎn).普通節(jié)點(diǎn)的加入或退出不會(huì)影響區(qū)塊的共 識(shí)進(jìn)程.普通節(jié)點(diǎn)加入后只需要提供查詢(xún)功能即可，不需要保存編碼塊.為了在不保存編碼塊的情況 下保證普通節(jié)點(diǎn)的查詢(xún)功能，普通節(jié)點(diǎn)需要同步共識(shí)節(jié)點(diǎn)的編碼塊索引.當(dāng)用戶(hù)向普通節(jié)點(diǎn)發(fā)起查詢(xún) 請(qǐng)求時(shí)，普通節(jié)點(diǎn)根據(jù)從共識(shí)節(jié)點(diǎn)處同步的索引，向?qū)?yīng)的共識(shí)節(jié)點(diǎn)發(fā)起請(qǐng)求，實(shí)現(xiàn)查詢(xún)功能.

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

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

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

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

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

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

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

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

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

6：????? Else

7：????? 采用N'共識(shí)節(jié)點(diǎn)列表，對(duì)歷史編碼塊數(shù)據(jù)進(jìn)行重編碼

8：????? End? if

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

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

11：?? 不處理歷史數(shù)據(jù)

12：?? Else

13：?? 采用N'共識(shí)節(jié)點(diǎn)列表，對(duì)歷史編碼塊數(shù)據(jù)進(jìn)行重編碼

14：?? End if

15：?? End if

16：保存編碼結(jié)果

3實(shí)驗(yàn)與評(píng)價(jià)

3.1實(shí)驗(yàn)環(huán)境和配置

（1）實(shí)驗(yàn)環(huán)境

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

（2）參數(shù)配置

實(shí)驗(yàn)測(cè)試的節(jié)點(diǎn)數(shù)量為4，糾刪碼編碼的數(shù)據(jù)塊數(shù)量為3，冗余塊數(shù)量為1.

3.2實(shí)驗(yàn)結(jié)果與分析

本文的實(shí)驗(yàn)評(píng)價(jià)主要參考4個(gè)指標(biāo)：存儲(chǔ)消耗、編碼性能、響應(yīng)延遲和穩(wěn)定性.

3.2.1存儲(chǔ)消耗

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

（1）全復(fù)制的存儲(chǔ)方式與糾刪碼的存儲(chǔ)方式的存儲(chǔ)消耗對(duì)比

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

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

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

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

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

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

3.2.2編碼性能

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

（1）編碼延遲

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

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

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

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

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

但將該區(qū)間的編碼時(shí)間平均到區(qū)塊區(qū)間內(nèi)的每個(gè)區(qū)塊上，得到每個(gè)區(qū)塊的平均編碼時(shí)間與區(qū)塊區(qū)間大小關(guān)系如圖ii所示，隨著區(qū)塊區(qū)間的增大，區(qū)塊的平均編碼時(shí)間呈下降趨勢(shì).增大區(qū)塊區(qū)間的 大小，可以降低每個(gè)區(qū)塊的平均編碼時(shí)間，但區(qū)塊區(qū)間的增大會(huì)使得一次編碼的時(shí)間增長(zhǎng)，在具體使 用過(guò)程中，可以根據(jù)需求調(diào)整糾刪碼編碼區(qū)塊區(qū)間大小.

3.2.3響應(yīng)延遲

在采用糾刪碼存儲(chǔ)方式的系統(tǒng)中，每個(gè)節(jié)點(diǎn)上只保存部分區(qū)塊的信息，當(dāng)所需區(qū)塊不存在所請(qǐng)求 的節(jié)點(diǎn)上或系統(tǒng)中的節(jié)點(diǎn)發(fā)生故障時(shí)，需要利用網(wǎng)絡(luò)傳輸和糾刪碼的解碼功能將原始數(shù)據(jù)恢復(fù)出來(lái)， 數(shù)據(jù)的恢復(fù)操作會(huì)造成響應(yīng)延遲.采用全復(fù)制存儲(chǔ)方式的CITA系統(tǒng)，由于沒(méi)有節(jié)點(diǎn)間通信，用戶(hù)查 詢(xún)請(qǐng)求的響應(yīng)延遲約為1.35 ms.

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

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

3.2.4穩(wěn)定性

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

4結(jié)論

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

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

[參考文獻(xiàn)]

[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ū)塊鍵的存儲(chǔ)容量可擴(kuò)展模型[J].計(jì)算機(jī)科學(xué)與探索，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.

（責(zé)任編輯：林晶）