面向分片許可鏈的無協(xié)調(diào)者跨片交易處理

闕琦峰 陳之豪 張 召 楊艷琴 周傲英

1（區(qū)塊鏈數(shù)據(jù)管理教育部工程研究中心（華東師范大學(xué)）上海 200062）

2（華東師范大學(xué)數(shù)據(jù)科學(xué)與工程學(xué)院 上海 200062）

3（華東師范大學(xué)軟件工程學(xué)院 上海 200062）

（51205903035@stu.ecnu.edu.cn）

作為一個具有嚴(yán)格準(zhǔn)入機(jī)制的去中心化的分布式賬本，許可鏈經(jīng)常被應(yīng)用于企業(yè)間數(shù)據(jù)共享、管理、多方協(xié)作以及用戶隱私保護(hù)等場景.然而，與分布式數(shù)據(jù)庫相比，區(qū)塊鏈系統(tǒng)的吞吐率較低，擴(kuò)展性也有限，很難滿足現(xiàn)代產(chǎn)業(yè)對高頻交易的需求.為提高區(qū)塊鏈系統(tǒng)的吞吐率和擴(kuò)展性，一些將分片技術(shù)與區(qū)塊鏈相結(jié)合的方案被提出.已有的分片區(qū)塊鏈方案，如Elastico[1]和OmniLedger[2]，通常將整個網(wǎng)絡(luò)劃分為小的委員會（分片）.在理想情況下，每個交易僅訪問單個分片，分片可并行處理交易，以實現(xiàn)系統(tǒng)執(zhí)行性能成倍提高.但由于跨片交易的存在，實現(xiàn)這種理想情況很困難.跨片交易需要操作多個分片上的數(shù)據(jù)，這給系統(tǒng)設(shè)計帶來了挑戰(zhàn).一些工作，例如RapidChain[3]和Monoxide[4]，通過在UTXO 模型下提出了一種最終原子性技術(shù)來解決這個問題.后續(xù)的工作，如AHL[5]，Chainspace[6]和Byshard[7]，則通過賬戶模型的基于協(xié)調(diào)者的兩階段提交（two-phase commit,2PC）協(xié)議來處理這些交易.

目前，基于2PC 協(xié)議的跨片交易執(zhí)行需要涉及所有相關(guān)分片之間的多輪信息交互，并以阻塞的方式處理跨片交易.特別是在實際基于分片的系統(tǒng)中，超過96%的交易是跨片交易，跨片交易的執(zhí)行可能會因其性能不佳而導(dǎo)致區(qū)塊鏈吞吐量下降.本文進(jìn)行了實驗，展示了基于協(xié)調(diào)者的跨片交易執(zhí)行的效率，當(dāng)跨片交易率為30%時吞吐量減少了近67%，當(dāng)跨片交易率為90%時吞吐量減少了80%.此外，盡管區(qū)塊鏈能夠高效地處理低沖突負(fù)載，但在高沖突負(fù)載下性能會降低，這會進(jìn)一步放大跨片交易的影響.因此，對于以性能為主要目標(biāo)的許可鏈，優(yōu)化跨片交易的執(zhí)行是一個緊迫的需求，以支持廣泛的應(yīng)用.

基于以上分析，多輪交互、阻塞和沖突被認(rèn)為是制約跨片交易執(zhí)行性能的關(guān)鍵因素.在本文中，我們決定從2 個方面對這一過程進(jìn)行優(yōu)化：首先，通過降低跨片交易執(zhí)行期間的通信成本來提高效率；其次，通過容忍任意程度的沖突交易工作量來獲得性能優(yōu)勢，從而為整個系統(tǒng)的吞吐量做出貢獻(xiàn).綜上所述，本文的主要貢獻(xiàn)總結(jié)為3 個方面：

1）針對分片許可鏈場景，提出了一種無協(xié)調(diào)者的跨分片交易執(zhí)行方法，通過基于交易序列號的單向通信進(jìn)行處理，來提高跨片交易的執(zhí)行效率；設(shè)計低通信開銷的狀態(tài)傳輸策略，保證片間傳輸狀態(tài)數(shù)據(jù)的正確性.

2）針對高沖突負(fù)載場景，提出了一種抗沖突的跨片交易執(zhí)行優(yōu)化方案，結(jié)合交易重排序技術(shù)和跨片交易執(zhí)行技術(shù)，以提高系統(tǒng)在高沖突負(fù)載下交易執(zhí)行的效率，并優(yōu)化跨片交易執(zhí)行中的狀態(tài)傳輸，以縮短跨片交易響應(yīng)時間.

3）實現(xiàn)了一個集成上述技術(shù)的原型系統(tǒng)，并在不同的工作負(fù)載下進(jìn)行實驗，實驗結(jié)果表明該原型系統(tǒng)勝過其他協(xié)議的系統(tǒng).

1 相關(guān)工作

1.1 確定性執(zhí)行策略

傳統(tǒng)的數(shù)據(jù)庫領(lǐng)域中有許多關(guān)于確定性執(zhí)行的研究.BOMH[8]將并發(fā)控制與事務(wù)執(zhí)行解耦，通過類似于MVCC 方式對交易并發(fā)控制.在并發(fā)控制層維護(hù)一個多版本的鏈表，根據(jù)事務(wù)集的讀寫關(guān)系，直接確定事務(wù)執(zhí)行時可見的快照版本.在執(zhí)行層，事務(wù)尋找執(zhí)行所依賴的快照版本，并將執(zhí)行后的結(jié)果填入最新快照版本中.若事務(wù)執(zhí)行時發(fā)現(xiàn)了所依賴的快照版本尚未生成，則系統(tǒng)嘗試遞歸處理該事務(wù)，直到發(fā)現(xiàn)所需的快照版本.基于BOMH，PWV[9]對事務(wù)的讀可見進(jìn)行了進(jìn)一步的優(yōu)化.PWV 將一個事務(wù)分成多個子交易，并尋找這些子交易的提交節(jié)點(diǎn)，保證提交節(jié)點(diǎn)之前不會出現(xiàn)邏輯上的交易中止，這使得某些事務(wù)的寫集可以在其提交之前被其他事務(wù)看到，而無需等待被提交.

Calvin[10]則通過鎖機(jī)制來并發(fā)處理交易，主要分為排序?qū)印⒄{(diào)度層和存儲層.排序?qū)又饕?fù)責(zé)給事務(wù)分配序列號；調(diào)度層根據(jù)分配的序列號對事務(wù)進(jìn)行沖突檢測并上鎖，盡可能保證高效的事務(wù)并發(fā)效率；最后將執(zhí)行后的數(shù)據(jù)寫入存儲層.Calvin 在執(zhí)行事務(wù)前需要檢測其讀寫集，這給事務(wù)處理帶來了一些局限性.而Aria[11]提出了一種不需要預(yù)處理階段的確定性執(zhí)行策略.在執(zhí)行階段，Aria 基于相同快照并發(fā)執(zhí)行一批交易，并把寫集保存在本地.在提交階段，它根據(jù)交易序列號以確定的順序提交交易.此外，該工作還提出了一個優(yōu)化方案，旨在降低交易的中止率，獲取更高的系統(tǒng)吞吐.

總之，在確定性數(shù)據(jù)庫中，每個節(jié)點(diǎn)都會以確定的方式執(zhí)行同一組有序的事務(wù)，并將數(shù)據(jù)庫從相同的初始狀態(tài)轉(zhuǎn)換為相同的最終狀態(tài).每個事務(wù)在傳遞給節(jié)點(diǎn)之前都已被分配了一個序列值，基于這個序列值，不同的節(jié)點(diǎn)無需相互協(xié)調(diào)就能保持執(zhí)行結(jié)果的一致性.為了實現(xiàn)節(jié)點(diǎn)間的確定性的并發(fā)處理，主流的并發(fā)控制協(xié)議主要采用了有序鎖和交易依賴圖這2 種方法來保證確定性.

更重要的是，區(qū)塊鏈系統(tǒng)要求交易的執(zhí)行是確定的，因此數(shù)據(jù)庫的確定性執(zhí)行為區(qū)塊鏈的執(zhí)行優(yōu)化提供了參考.Dickerson 等人[12]將智能合約執(zhí)行與并發(fā)控制相結(jié)合，礦工節(jié)點(diǎn)通過軟件事務(wù)內(nèi)存（software transactional memory,STM）并行執(zhí)行智能合約.該方法與數(shù)據(jù)庫常用兩階段鎖原理類似，智能合約訪問一個狀態(tài)數(shù)據(jù)時，需要先獲得該狀態(tài)對應(yīng)的一個抽象鎖，并填寫好回退日志方便交易中止時回退，并最終將執(zhí)行順序以happen-before 圖的方式廣播給驗證者以驗證結(jié)果.在驗證階段，所有驗證節(jié)點(diǎn)根據(jù)礦工傳來的可串行化順序和happen-before 圖來獲得主節(jié)點(diǎn)中每一個交易獲得鎖的順序，以此作為驗證交易的順序.最終，驗證節(jié)點(diǎn)可以確定地并發(fā)執(zhí)行該任務(wù)，并檢測最終狀態(tài)是否與礦工節(jié)點(diǎn)一致.而在Anjana[13]的工作中，礦工節(jié)點(diǎn)采用并發(fā)度更高的OCC協(xié)議來處理交易，并根據(jù)執(zhí)行結(jié)果生成一個交易拓?fù)鋱D.驗證節(jié)點(diǎn)根據(jù)收到的交易和拓?fù)漤樞騺眚炞C交易，保證驗證的結(jié)果和礦工執(zhí)行結(jié)果相同.

MVTO[14]方案借鑒了BOMH 的思想，將一個事務(wù)切分成多個子交易，利用礦工節(jié)點(diǎn)生成的交易寫集來構(gòu)建記錄各個版本數(shù)據(jù)信息的鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)，即版本鏈.通過版本鏈，系統(tǒng)能夠并發(fā)地、確定性地重新驗證交易，從而提高了區(qū)塊鏈系統(tǒng)的驗證效率.PEEP[15]提出了一個針對許可區(qū)塊鏈系統(tǒng)的并行執(zhí)行引擎，該引擎允許交易在邏輯上并發(fā)執(zhí)行，并且在底層存儲層面也能并發(fā)更新存儲在狀態(tài)樹的葉子節(jié)點(diǎn)的狀態(tài)數(shù)據(jù)塊.

Jin 等人[16]提出了一個高效的智能合約執(zhí)行框架，即2PX.針對主節(jié)點(diǎn)執(zhí)行階段，2PX 提出了Batch OCC 協(xié)議，將數(shù)據(jù)庫中常用的樂觀并發(fā)控制協(xié)議應(yīng)用于智能合約處理的主階段中，賦予了礦工節(jié)點(diǎn)并發(fā)執(zhí)行交易的能力.主節(jié)點(diǎn)會在交易的讀階段結(jié)束后生成該輪交易的沖突圖.待執(zhí)行完區(qū)塊內(nèi)所有交易之后，主節(jié)點(diǎn)會生成一個反映交易依賴關(guān)系的拓?fù)鋱D，然后將其與新區(qū)塊一起廣播給驗證節(jié)點(diǎn).由于傳輸?shù)慕灰滓蕾噲D包含主節(jié)點(diǎn)執(zhí)行交易時讀入或?qū)懭氲木唧w數(shù)值，主節(jié)點(diǎn)根據(jù)圖切分算法將依賴圖切分成多個子圖以提高驗證節(jié)點(diǎn)的驗證效率.同時，該圖切分策略將傳輸代價更大的邊連接的交易節(jié)點(diǎn)放在同一個子圖中，極大程度地減少網(wǎng)絡(luò)傳輸?shù)拈_銷，進(jìn)一步提高了系統(tǒng)性能.

1.2 區(qū)塊鏈分片技術(shù)

區(qū)塊鏈分片技術(shù)通過將節(jié)點(diǎn)劃分為多個分片，來提高區(qū)塊鏈系統(tǒng)的吞吐量和處理速度.最早的基于公有鏈設(shè)計的分片系統(tǒng)Elastico[1]將整個網(wǎng)絡(luò)分為多個分片，要求所有節(jié)點(diǎn)計算PoW 的驗證字段，并且根據(jù)提交的結(jié)果決定該節(jié)點(diǎn)將被分配到的分片.這些分片之間相互獨(dú)立，可以并行地進(jìn)行交易處理，有效地提高了整個系統(tǒng)的吞吐量.由于每個分片的規(guī)模較小，分片內(nèi)部則運(yùn)行經(jīng)典的BFT 共識協(xié)議.因此，Elastico 系統(tǒng)的吞吐量可以隨著節(jié)點(diǎn)的增加而提升，近乎完成了線性擴(kuò)展；此外，其靈活的分片劃分規(guī)則避免了跨分片通信，降低了通信復(fù)雜度.但同時，頻繁的分片劃分仍然會造成較大的系統(tǒng)開銷，尤其是在復(fù)雜且龐大的業(yè)務(wù)場景下，其可能會成為主要的性能瓶頸.分片區(qū)塊鏈仍然需要更高效的方法來保證數(shù)據(jù)的一致性和處理跨片交易.

2018 年，OmniLedger[2]提出了一種跨新型的跨片交易原子提交協(xié)議Atomix，保證每個交易被完全提交或最終取消.Atomix 授權(quán)客戶端利用鎖機(jī)制來協(xié)調(diào)分片之間處理跨片交易，這使得分片之間無需直接通信，保持了簡單的分片工作邏輯.以UTXO 賬戶系統(tǒng)為例，第一階段，客戶端首先會生成一筆跨片交易，再將該交易發(fā)送給與其輸入相關(guān)的分片.每個相關(guān)分片檢測相關(guān)輸入是否合法，若檢測通過，則記錄輸出狀態(tài)，向客戶端返回處理結(jié)果.當(dāng)客戶端收到了所有分片的消息，該協(xié)議進(jìn)入第二階段，即將提交跨片交易請求傳送至相關(guān)分片.若任意一個相關(guān)分片取消了該筆交易，客戶端也會向相關(guān)分片返回撤銷交易的請求，以此來保證交易的一致性.但是，由于該協(xié)議由客戶端驅(qū)動，在處理跨片交易的過程中，客戶端被要求不能離線；同時，該協(xié)議的性能受限于客戶端本身的性能，容易陷入單點(diǎn)瓶頸問題.

因此，秉承“輕客戶端”的設(shè)計原則，AHL[5]則通過結(jié)合兩階段鎖（two-phase locking,2PL）和兩階段提交協(xié)議（two phase commit,2PC）來處理跨片交易.與Elastico 類似，AHL 通過對比節(jié)點(diǎn)生成的隨機(jī)數(shù)將整個網(wǎng)絡(luò)劃分為多個分片，分片內(nèi)部采用將TEE 與PBFT 算法相結(jié)合的共識協(xié)議，所有協(xié)議也都由該協(xié)議得出.在處理跨片交易時，選擇一個分片作為2PC協(xié)調(diào)者，稱其為參考分片.第一階段，參考分片向所有相關(guān)分片發(fā)送準(zhǔn)備請求，并收集所有分片的返回結(jié)果.第二階段，參考分片會根據(jù)上個階段投票結(jié)果來決定交易的提交或者中止，最后同樣地把處理結(jié)果返回給各個分片.

分片架構(gòu)Chainspace[6]通過分片之間新的分布式原子提交協(xié)議S-BAC，來處理跨片交易.該方法根據(jù)交易模擬執(zhí)行的結(jié)果標(biāo)記與其他交易的沖突，將沖突信息發(fā)送到相關(guān)分片，然后每個分片通過沖突信息解決交易之間的沖突關(guān)系，最后將交易執(zhí)行并提交至本地中.從協(xié)議實現(xiàn)的過程來看，S-BAC 協(xié)議結(jié)合了BFT 協(xié)議與2PC 協(xié)議的特點(diǎn)，能夠在拜占庭環(huán)境下保證片間交易的一致.但AHL 與Chainspace 都是針對單一系統(tǒng)設(shè)計的分片方法，它們無法靈活地適應(yīng)復(fù)雜的業(yè)務(wù)場景與多變的需求.

于是，Byshard[7]提出了一種彈性的分片系統(tǒng)框架，以支持更加靈活的數(shù)據(jù)管理.該框架基于2PC 和2PL 技術(shù)，設(shè)計了3 種跨片協(xié)調(diào)方法和4 種執(zhí)行方法，提供各種隔離級別的服務(wù)，能夠適用于在拜占庭環(huán)境下的分布式系統(tǒng).Byshard 通過結(jié)合其所設(shè)計的跨片協(xié)調(diào)方法和執(zhí)行方法，得到了18 種實用的協(xié)議，以滿足不同場景下對吞吐量、隔離級別、延遲和中止率等性能特征的需求.此外，該框架支持AHL 和Chainspace 等現(xiàn)有工作的實現(xiàn).

SharPer[17]是一個用于許可區(qū)塊鏈的分片架構(gòu)，不同于上述基于單一協(xié)調(diào)者的工作，它通過片間共識支持在CTF 和BTF 情況下的跨片交易確定性并發(fā)執(zhí)行.該工作解決了跨片交易可能出現(xiàn)的交易沖突、死鎖、主節(jié)點(diǎn)故障的問題.主節(jié)點(diǎn)收到客戶端傳來的交易后，將主節(jié)點(diǎn)在該筆交易設(shè)置一個序列號，廣播給所有的相關(guān)節(jié)點(diǎn).分片從節(jié)點(diǎn)接收主節(jié)點(diǎn)傳來的消息后，驗證序號和交易內(nèi)容，無需與該節(jié)點(diǎn)所在的分片共識，各個節(jié)點(diǎn)直接將決策結(jié)果返回主節(jié)點(diǎn).當(dāng)主節(jié)點(diǎn)收到并驗證來自每個分片的f+1 個“接受”消息后，向所有涉及交易的分片廣播“提交”消息.最后，主節(jié)點(diǎn)向客戶端返回結(jié)果，相關(guān)的分片收到消息后將本地交易提交.

跨分片共識協(xié)議被廣泛應(yīng)用來解決跨片交易執(zhí)行的問題，但同時也引入了大量的片間交互，延長了跨片交易的提交時間.因此，一些研究人員開始探索更高效的分片技術(shù).其中，基于UTXO 賬戶模型的RapidChain[3]提出了一種新的跨片交易處理機(jī)制.該機(jī)制首先將一筆多輸入、多輸出的跨片交易分解成多筆單進(jìn)、單出的子交易.由于這些子交易只有一個輸入和輸出，分片在處理相關(guān)子交易時只需驗證本地輸入是否有效，省去了分片之間互相驗證的開銷.該方法通過將交易重新劃分，有效地減少網(wǎng)絡(luò)開銷，提高跨片交易的處理效率.

Monoxide[4]是一種針對公有鏈場景的分片技術(shù)，它將節(jié)點(diǎn)按照網(wǎng)絡(luò)分布來劃分多個子網(wǎng)絡(luò)，并將每個用戶錢包地址的前k位映射到相應(yīng)的子網(wǎng)絡(luò).為了解決跨片交易問題，Monoxide 將一筆跨片交易拆分為許多內(nèi)部交易和中繼交易，其中內(nèi)部交易直接在片內(nèi)執(zhí)行，而中繼交易以異步的方式在其他分片執(zhí)行.具體地，當(dāng)處理一筆跨片轉(zhuǎn)賬交易時，轉(zhuǎn)賬賬戶所在的子網(wǎng)絡(luò)會在本分片共識并執(zhí)行該交易，然后該子網(wǎng)會生成一筆中繼交易并將其傳送至收款賬戶所在子網(wǎng)共識并執(zhí)行，這有效地保證了交易的最終原子性.這種方式避免了分片間互相驗證的開銷，使得跨片交易更加高效.

BrokerChain[18]引入了“市商賬戶”來協(xié)調(diào)處理跨片交易，以達(dá)到降低跨片交易延遲的目的.“市商賬戶”會以相同的賬戶地址被劃分至多個不同的分片.在處理跨片交易時，BrokerChain 會將該交易劃分為2 個與市商賬戶相關(guān)的片內(nèi)交易.由于一個市商賬戶在不同分片上都維護(hù)相同的地址，轉(zhuǎn)賬和收款賬戶僅需要與本分片內(nèi)的相同市商賬戶交互即可完成跨片交易的執(zhí)行.該方法能夠有效地降低執(zhí)行跨片交易的開銷，也緩解了分片負(fù)載不均衡的問題.

但是方法Monoxide 和BrokerChain 需要執(zhí)行來自跨片交易劃分的子交易，這會產(chǎn)生額外的執(zhí)行成本.后來，Pyramid[19]設(shè)計了一個層級化的分片系統(tǒng)，該分片系統(tǒng)允許一些復(fù)合分片維護(hù)多個分片存儲的數(shù)據(jù).如此，一些跨片交易可以在復(fù)合分片中轉(zhuǎn)換為片內(nèi)交易，并且可以在一輪交互中提交.總的來說，Pyramid 通過犧牲一定的存儲來極大程度地提高了系統(tǒng)性能.

2 無協(xié)調(diào)者的跨片交易執(zhí)行

傳統(tǒng)的分片區(qū)塊鏈的跨片交易處理方法會引入多輪片間通信來保證交易的原子性和一致性.以基于兩階段提交共識協(xié)議的分片區(qū)塊鏈系統(tǒng)為例，首先，系統(tǒng)會選出一個分片擔(dān)任共識協(xié)議中的協(xié)調(diào)者角色.在協(xié)調(diào)者分片的幫助下，系統(tǒng)可以通過2 輪通信來保證跨片交易在所有分片成功提交，但這會導(dǎo)致大量的網(wǎng)絡(luò)開銷和極高的交易延遲.其次，系統(tǒng)不僅需要花費(fèi)額外的資源去維護(hù)協(xié)調(diào)者分片，而且面臨協(xié)調(diào)者帶來的單點(diǎn)瓶頸問題.因此，為了解決上述問題，本節(jié)基于以太坊執(zhí)行范式，提出并詳細(xì)介紹了一種無需協(xié)調(diào)者的高效跨片交易執(zhí)行方法.

2.1 基本定義

本節(jié)介紹了本文執(zhí)行方法依托的分片系統(tǒng)架構(gòu)，并對跨片交易問題進(jìn)行了形式化的定義與描述.表1列出了本文出現(xiàn)的重要符號.

Table 1 Symbol Table表1 符號表

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

系統(tǒng)架構(gòu)如圖1 所示，其由2 類分片構(gòu)成，即由多個共識節(jié)點(diǎn)組成的共識分片與多個執(zhí)行節(jié)點(diǎn)組成的執(zhí)行分片構(gòu)成.共識分片負(fù)責(zé)接收客戶端發(fā)送的交易，共識打包并產(chǎn)生區(qū)塊，對交易進(jìn)行排序；當(dāng)共識分片生成共識區(qū)塊后，執(zhí)行分片從共識分片同步區(qū)塊，并按交易在區(qū)塊中的順序執(zhí)行區(qū)塊，觸發(fā)本分片內(nèi)部的狀態(tài)改變.同時，每個分片節(jié)點(diǎn)數(shù)量滿足3f+1 的條件，其中f表示容忍的拜占庭節(jié)點(diǎn)數(shù)量.

Fig.1 System architecture圖1 系統(tǒng)架構(gòu)

當(dāng)存在多個執(zhí)行分片時，需要對所有的狀態(tài)數(shù)據(jù)進(jìn)行分片，以實現(xiàn)將負(fù)載劃分到多個不同的執(zhí)行分片中.本系統(tǒng)需要將狀態(tài)數(shù)據(jù)均勻地劃分到不同的執(zhí)行分片中，保證同一個狀態(tài)的所有數(shù)據(jù)都被劃分到相同的分片.

2.1.2 跨片交易執(zhí)行

在分片區(qū)塊鏈系統(tǒng)中，交易可以根據(jù)其特點(diǎn)分為2 類：片內(nèi)交易和跨片交易.片內(nèi)交易不需要與其他分片進(jìn)行交互，僅涉及到本地數(shù)據(jù)的訪問和修改.而跨片交易需要修改或訪問不同的多個數(shù)據(jù)，相比片內(nèi)交易更加復(fù)雜，并且其原子性與一致性難以保證.由于分片之間維護(hù)的狀態(tài)數(shù)據(jù)不同，分片處理跨片交易的方式有明顯差異；具體來說，一筆跨片交易Ti與某一分片ESj的關(guān)系主要分為3 類：

1）Ti與W（Ti）中的狀態(tài)數(shù)據(jù)均不由分片ESj維護(hù)；

2）R（Ti）中有狀態(tài)數(shù)據(jù)由分片ESj維護(hù)，W（Ti）中無狀態(tài)數(shù)據(jù)由分片ESj維護(hù)；

3）W（Ti）中有狀態(tài)數(shù)據(jù)由分片ESj維護(hù)，R（Ti）中是否有狀態(tài)由分片ESj維護(hù)均可；

對于1），分片ESj在處理跨片交易Ti時，該筆交易與該分片所維護(hù)的狀態(tài)數(shù)據(jù)無關(guān)，因此無需處理該筆跨片交易，直接將其忽略即可.對于2），執(zhí)行交易Ti需要讀取分片ESj中的狀態(tài)數(shù)據(jù)，但不會修改該分片的狀態(tài)數(shù)據(jù)；由于分片ESj負(fù)責(zé)傳輸跨片交易讀取的狀態(tài)數(shù)據(jù)至其他分片，分片ESj也被稱為交易Ti的一個傳輸分片.對于3），交易Ti不僅需要從分片ESj讀取狀態(tài)數(shù)據(jù)，同時也要更新該分片的狀態(tài)數(shù)據(jù).因此，分片ESj是跨片交易Ti的一個更新分片.

由于數(shù)據(jù)分布在不同的分片，跨片交易Ti可能存在多個傳送分片和多個更新分片；一個分片可以既是Ti的更新分片又是傳輸分片.

2.2 基于排序鎖的跨片交易執(zhí)行方法

本節(jié)描述了跨片交易執(zhí)行方法處理跨片交易的細(xì)節(jié)，包括排序鎖的工作原理、跨片交易執(zhí)行流程以及拜占庭狀態(tài)傳輸方案，從而使整個系統(tǒng)具有高性能、可擴(kuò)展性和安全性.

2.2.1 排序鎖的工作原理

本文的跨片執(zhí)行方法是基于排序鎖機(jī)制實現(xiàn)的，該機(jī)制通過利用基于鎖定的并發(fā)控制來保證交易的原子性和可串行性，并通過以特定的交易鎖定順序來確保交易的隔離性.在區(qū)塊鏈系統(tǒng)中，排序鎖機(jī)制可以根據(jù)交易在區(qū)塊內(nèi)的序列號順序地鎖定交易.排序鎖機(jī)制有2 個重要的組件，分別是鎖管理器和線程調(diào)度器.前者負(fù)責(zé)按照有序的鎖方案向交易授予鎖；后者協(xié)調(diào)交易的執(zhí)行，如工作線程分配和管理.

具體來說，鎖管理器首先會根據(jù)先前預(yù)定的交易順序依次給交易加鎖，然后根據(jù)交易的讀寫集授予該交易當(dāng)前可用的鎖.每個交易對鎖的請求消息被保存在相應(yīng)的鎖的請求隊列中.如果一筆交易獲得了其執(zhí)行所需訪問的所有數(shù)據(jù)的鎖，它就能被送入線程調(diào)度器的緩存池中準(zhǔn)備開始執(zhí)行.當(dāng)一筆交易執(zhí)行結(jié)束時，鎖管理器會回收所有的鎖，并將它們授權(quán)給下一筆交易.線程調(diào)度器設(shè)置了多個工作線程并發(fā)地執(zhí)行交易，調(diào)度器將把緩沖區(qū)中的每個交易分配給一個空閑的工作線程來執(zhí)行.在執(zhí)行過程中，工作線程可能會因為某些原因中止一筆交易，但是這種行為被保證在所有節(jié)點(diǎn)中都是相同的.具體實現(xiàn)如圖2 所示.

Fig.2 An example of order lock mechanism圖2 排序鎖機(jī)制實例

在本方法中，每個節(jié)點(diǎn)都會按照共識階段確定的順序給交易加鎖，以保證每個節(jié)點(diǎn)執(zhí)行的順序是一致且唯一的.即使拜占庭節(jié)點(diǎn)以不一致的順序鎖定交易，系統(tǒng)也會通過容錯方法恢復(fù)正常，具體實現(xiàn)將在2.3 節(jié)中闡述.

2.2.2 跨片交易的執(zhí)行流程

本文提出的跨片交易執(zhí)行方法處理跨片交易T的流程有4 個：

1）將每個跨片交易Ti的傳輸分片和更新分片讀取Ti執(zhí)行時讀取的本地數(shù)據(jù)，發(fā)送至除自身以外的所有更新分片中；

2）若Ti沒有讀取到所有狀態(tài)數(shù)據(jù)，則Ti會被更新分片掛起，并等待傳輸分片發(fā)送遠(yuǎn)端狀態(tài)數(shù)據(jù)；

3）當(dāng)更新分片收集Ti所需的所有遠(yuǎn)端狀態(tài)數(shù)據(jù)之后，它會喚醒并執(zhí)行Ti，最后將執(zhí)行結(jié)果寫入本地數(shù)據(jù)中；

4）每個更新分片只寫入本地維護(hù)的數(shù)據(jù)，忽略Ti對其他更新分片的更新操作.

舉例來展示該跨片交易執(zhí)行方法的實現(xiàn)細(xì)節(jié).如圖3 所示，分片1 與T1、T2和T3這三筆交易的關(guān)系可以分別對應(yīng)本節(jié)中所描述的3 種情況.圖3 中分片1 維護(hù)Alice 的賬戶數(shù)據(jù)，分片2 則維護(hù)Bob 與Carl 的賬戶數(shù)據(jù).首先，T1的執(zhí)行邏輯是將Bob 的賬戶余額增加5，這筆交易只與維護(hù)Bob 賬戶數(shù)據(jù)的分片2 有關(guān)，所以分片1 無需執(zhí)行T1，自然地將該交易忽略，這符合2.1.2 節(jié)中所述的第1 類關(guān)系中描述的場景.對于T2，它需要判斷Alice 賬戶是否有余額，以此來確定是否在Carl 賬戶余額上增加5，此時分片1就會成為T2的一個傳輸分片，向Carl 賬戶所在的分片傳輸Alice 賬戶數(shù)據(jù)，這符合2.1.2 節(jié)中所述的第2類關(guān)系中描述的場景.最后在處理T3時，Alice 需要向Bob 轉(zhuǎn)賬5.由于該筆交易需要同時修改Alice 和Bob 的賬戶余額，這2 個分片分別將Alice 與Bob 的賬戶余額發(fā)送給對方，然后雙方都執(zhí)行該筆交易，并根據(jù)執(zhí)行的結(jié)果修改各自的賬戶余額，這符合2.1.2節(jié)中所述的第3 類關(guān)系中描述的場景.

Fig.3 The process of system transactions execution圖3 系統(tǒng)處理交易的流程

不難發(fā)現(xiàn)，該跨片執(zhí)行方法要求傳輸分片狀態(tài)數(shù)據(jù)傳輸至更新分片，這產(chǎn)生了一定的通信開銷.然而，對于執(zhí)行復(fù)雜邏輯的智能合約，狀態(tài)傳輸是不可避免的，即便在較為成熟的基于兩階段提交的跨片執(zhí)行方法中，協(xié)調(diào)者也需要將執(zhí)行需要的數(shù)據(jù)傳輸給參與者.與其他只支持簡單轉(zhuǎn)賬交易的分片系統(tǒng)不同，基于狀態(tài)傳輸?shù)膱?zhí)行方法可以適應(yīng)更廣泛的應(yīng)用場景，支持更復(fù)雜的邏輯判斷.

此外，本文采用的狀態(tài)數(shù)據(jù)傳輸是通過異步實現(xiàn)的，不會阻塞其他交易的執(zhí)行.因此，即便是個別分片不能及時處理其對應(yīng)的跨片交易，其他分片也會將該交易掛起并處理其他交易，不會嚴(yán)重影響系統(tǒng)處理交易的能力.

2.2.3 片間狀態(tài)傳輸

在處理跨片交易的過程中，傳輸分片需要將本地的最新狀態(tài)傳輸至更新分片上.與傳統(tǒng)分布式數(shù)據(jù)庫的數(shù)據(jù)傳輸有所不同，區(qū)塊鏈中的拜占庭節(jié)點(diǎn)不僅會發(fā)送錯誤的信息干擾系統(tǒng)正常運(yùn)行，而且會合謀欺騙正常節(jié)點(diǎn).具體表現(xiàn)為，一方面，拜占庭節(jié)點(diǎn)傳輸錯誤的狀態(tài)數(shù)據(jù)會影響其他節(jié)點(diǎn)的正常執(zhí)行，浪費(fèi)系統(tǒng)的計算資源；另一方面，由于傳輸分片和更新分片之間的惡意節(jié)點(diǎn)的數(shù)量是不對稱的，規(guī)模更大的分片可以篡改或隱藏真實的數(shù)據(jù)，達(dá)到劫持其他小規(guī)模分片執(zhí)行結(jié)果的效果.綜上所述，在區(qū)塊鏈系統(tǒng)中，基于節(jié)點(diǎn)對節(jié)點(diǎn)的數(shù)據(jù)傳輸方式是不安全的.

此外，盡管使用拜占庭廣播的方式傳輸狀態(tài)數(shù)據(jù)可以有效地保證系統(tǒng)安全性，但在大規(guī)模網(wǎng)絡(luò)中，數(shù)據(jù)廣播將占用大量帶寬資源和計算資源，導(dǎo)致網(wǎng)絡(luò)擁塞和性能下降.這與本研究設(shè)計的低通信開銷的跨片執(zhí)行方法的出發(fā)點(diǎn)相悖.

本研究基于雙射傳輸[20]設(shè)計一種拜占庭數(shù)據(jù)傳輸方案，具體實現(xiàn)如圖4 所示.該方案支持跨片狀態(tài)傳輸，并能夠以最小的消息傳輸代價完成傳輸，同時避免了廣播所帶來的巨大成本.我們將對最小狀態(tài)數(shù)據(jù)傳輸問題進(jìn)行形式化定義.

Fig.4 Inter-shard state transfer圖4 片間狀態(tài)傳輸

定義1.給定一些傳輸分片中的節(jié)點(diǎn)Nt和一些更新分片中的節(jié)點(diǎn)Nu，其中Nt中的節(jié)點(diǎn)將狀態(tài)數(shù)據(jù)傳輸給Nu中的不同節(jié)點(diǎn).給定傳輸節(jié)點(diǎn)數(shù)量|Nt|=nt，Nt能夠容忍ft個拜占庭節(jié)點(diǎn)；給定更新節(jié)點(diǎn)數(shù)量|Nu|=nu，Nu能夠容忍fu個拜占庭節(jié)點(diǎn).找到傳輸分片需要發(fā)送的狀態(tài)數(shù)據(jù)（簡稱消息）的最小數(shù)量m.

根據(jù)傳輸節(jié)點(diǎn)數(shù)量nt和更新節(jié)點(diǎn)數(shù)量nu的大小關(guān)系不同，需要傳輸消息的最小數(shù)量m的決定性條件也不同.當(dāng)nt≥nu時，必須確保至少有2ft+1 個不同傳輸節(jié)點(diǎn)傳輸消息；而當(dāng)nt

定理1.給定一些傳輸分片的節(jié)點(diǎn)Nt和更新分片的節(jié)點(diǎn)Nu.當(dāng)nt≥nu時，讓q=(2ft+1)/(nu-fu)和r=（2ft+1）mod（nu-fu）.消息傳輸?shù)淖钚?shù)量m定義為

定理2.給定一些傳輸分片的節(jié)點(diǎn)Nt和更新分片的節(jié)點(diǎn)Nu.當(dāng)nt

變量q是一個誠實的節(jié)點(diǎn)應(yīng)該接收或發(fā)送的最小消息數(shù)量.而變量r是需要接收或發(fā)送q+1 條消息的誠實節(jié)點(diǎn)數(shù)量.以下是這2 條定理的證明.

證明1.通過反證法證明m為最小消息傳輸數(shù)量.假設(shè)僅需要傳輸m'=m-1 條消息，就可以保證消息成功被更新分片接收.當(dāng)nt≥nu時，將Nu中的節(jié)點(diǎn)分為P1和P2兩部分，將收到消息數(shù)量最多的前fu個節(jié)點(diǎn)劃入P1中，其余的nu-fu個節(jié)點(diǎn)劃入P2中.其中，需要證明P1收 到的消息數(shù)量滿足mP1≥qfu+fusgnr，于是利用反證法，讓mP1=qfu+fusgnr-v，v≥1；則剩余的節(jié)點(diǎn)群P2只能收到mP2=m′-mP1=q（nu-fu）+r+v-1 條消息.

討論2 種情況：當(dāng)r=0 時，可以得到mP1=qfu-v0 時，有mP1=qfu+fu-v<（q+1）fu和mP2=q（nu-fu）+r+v-1 >q（nu-fu），這意味著在P1中至少存在一個最多收到q條消息的節(jié)點(diǎn)，在P2中至少存在一個收到了q+1 條消息的節(jié)點(diǎn).由此可知，在P2中至少存在一個節(jié)點(diǎn)，使其收到的消息數(shù)量比P1中某個節(jié)點(diǎn)更多，這與P1劃分規(guī)則相悖.因此，證明mP1≥qfu+fusgnr和mP2≤q（nu-fu）+r-1成立.

由于更新節(jié)點(diǎn)中誠實節(jié)點(diǎn)至少要收到2ft+1 條消息才能保證更新分片不會被傳輸分片欺騙，所以有q（nu-fu）+r=2ft+1 成立.最糟糕的情況是P1的節(jié)點(diǎn)全為拜占庭節(jié)點(diǎn)，在這種情況下只有P2的消息被有效接收.但是，結(jié)合等式q（nu-fu）+r=2ft+1，P2所收到的消息為mP2≤q（nu-fu）+r-1=2ft條，無法收到來自誠實節(jié)點(diǎn)的ft+1 條消息.因此，m′的假設(shè)是不成立的.證畢.

證明2.同理，當(dāng)nt

只有保證在更新分片中至少有fu+1 個節(jié)點(diǎn)收到ft+1 個傳輸節(jié)點(diǎn)的信息，更新分片才不會被惡意節(jié)點(diǎn)劫持，所以有q（nt-2ft）+r=fu+1 成立.結(jié)合此等式知道，mP2≤fu成立.這意味著，當(dāng)所有接收P2傳輸?shù)南⒌母鹿?jié)點(diǎn)都是拜占庭節(jié)點(diǎn)時，在P1中剩余的ft個誠實節(jié)點(diǎn)傳輸?shù)南⒖赡軣o法被更新分片有效地確認(rèn).證畢.

由于傳輸節(jié)點(diǎn)不能同時向同一個更新節(jié)點(diǎn)多次傳輸消息，在傳輸消息時，傳輸節(jié)點(diǎn)需要在消息上簽名，注明消息的來源.更新節(jié)點(diǎn)在接收消息時會對該消息進(jìn)行驗簽，以防止受到拜占庭環(huán)境中可能存在的消息重放攻擊.此外，該方案僅確保整個分片收到ft+1 條消息，這意味著單個節(jié)點(diǎn)仍有可能面臨收到偽造消息的風(fēng)險，本文在2.3 節(jié)中設(shè)計了一種區(qū)塊重構(gòu)方法，被攻擊的節(jié)點(diǎn)可以在區(qū)塊重構(gòu)時獲得正確的狀態(tài)數(shù)據(jù)，因此不需要在狀態(tài)傳輸?shù)倪^程中采用即時驗證策略來確認(rèn)正確的消息.

2.2.4 跨片交易執(zhí)行的實現(xiàn)

算法1 展示了本文提出的跨片交易執(zhí)行方法在處理交易時的細(xì)節(jié).代碼第1 行從交易隊列中獲取一筆交易來執(zhí)行.代碼第4 行通過判斷交易的讀集R（T）和寫集W（T）是否與本分片有關(guān)，從而決定是否忽略該筆交易.其余代碼詳細(xì)描述了傳輸分片的工作細(xì)節(jié)，首先，掃描交易的讀集和寫集，來判斷需要傳輸至更新分片的本地狀態(tài)數(shù)據(jù)；然后，再將這些狀態(tài)數(shù)據(jù)發(fā)送到相應(yīng)的更新分片.此外，當(dāng)節(jié)點(diǎn)檢測到該跨分片交易需要修改本地數(shù)據(jù)時，節(jié)點(diǎn)不僅需要從本地數(shù)據(jù)S讀取狀態(tài)數(shù)據(jù)，還需要從其他分片獲取遠(yuǎn)端數(shù)據(jù)RD（代碼第19 行）.如果一筆跨片交易成功讀取所需的全部狀態(tài)數(shù)據(jù)，系統(tǒng)開始執(zhí)行該筆交易，并把它送入線程協(xié)調(diào)器的緩存中等待工作線程的處理（代碼21 行）；否則將該交易掛起并處理其他交易，直到獲取到相應(yīng)的遠(yuǎn)端數(shù)據(jù).

算法1.跨片交易執(zhí)行算法Transaction Execution.

輸入：交易執(zhí)行隊列Txs，本地維護(hù)的狀態(tài)數(shù)據(jù)S，其他分片發(fā)送到本地的狀態(tài)數(shù)據(jù)RD.

2.3 存儲與數(shù)據(jù)恢復(fù)

在經(jīng)過共識協(xié)議產(chǎn)生區(qū)塊后，每個分片只需處理與其相關(guān)的交易，忽略其他分片中的交易.然而，這種情況下傳統(tǒng)的存儲方法存在3 個問題：1）共識協(xié)議生成的區(qū)塊包含所有的交易信息，不能直接被分片用作最終的存儲區(qū)塊結(jié)構(gòu).2）在每個節(jié)點(diǎn)獨(dú)立執(zhí)行交易的情況下，當(dāng)處理跨片交易時，節(jié)點(diǎn)獲取遠(yuǎn)端數(shù)據(jù)的正確性難以保證，可能影響系統(tǒng)數(shù)據(jù)的一致性.3）分片之間也缺乏同步手段，難以確定系統(tǒng)處理交易的總進(jìn)度.綜上所述，傳統(tǒng)的區(qū)塊存儲方案無法滿足分片區(qū)塊鏈場景下數(shù)據(jù)管理的需求，因此，需要設(shè)計一種區(qū)塊重構(gòu)與數(shù)據(jù)恢復(fù)機(jī)制，以解決這3個問題.

2.3.1 區(qū)塊重構(gòu)

每個執(zhí)行分片需要重新生成新的區(qū)塊結(jié)構(gòu)，特別是計算和存儲包含交易信息與狀態(tài)數(shù)據(jù)的MPT樹.每當(dāng)分片中的節(jié)點(diǎn)執(zhí)行一定數(shù)量的交易（例如，每執(zhí)行1 000 個交易），就將這些交易重新打包成一個新的區(qū)塊，然后廣播該區(qū)塊的塊號、狀態(tài)樹的根哈希、交易樹的根哈希以及從每個傳輸分片中得到的所有狀態(tài)數(shù)據(jù).當(dāng)每個節(jié)點(diǎn)收到新區(qū)塊的2f+1 條消息后，節(jié)點(diǎn)會驗證消息的有效性并將它們傳輸?shù)母Ｅc本地計算出的根哈希進(jìn)行對比.

通過比較2 個狀態(tài)樹和交易樹的根哈希，可以驗證它們是否相同，從而驗證不同節(jié)點(diǎn)之間區(qū)塊鏈狀態(tài)與塊內(nèi)交易信息的有效性和完整性是否一致.

當(dāng)確定f+1 條根哈希信息與本地生成的根哈希信息相同，節(jié)點(diǎn)確認(rèn)該區(qū)塊，并將區(qū)塊存儲在本地.由于上述的重構(gòu)區(qū)塊的確認(rèn)僅需要1 輪網(wǎng)絡(luò)通信，分片內(nèi)不需要執(zhí)行一個完整的PBFT 共識來驗證重構(gòu)區(qū)塊的正確性，大大減少了網(wǎng)絡(luò)開銷.當(dāng)共識協(xié)議的原始區(qū)塊內(nèi)的所有交易被分片獲取后，即可刪除該共識區(qū)塊，節(jié)省系統(tǒng)存儲開銷.該機(jī)制的工作流程如圖5 所示.

Fig.5 Workflow of block storage and reconfiguration圖5 區(qū)塊存儲與重構(gòu)的工作流程

2.3.2 數(shù)據(jù)恢復(fù)

如果任何節(jié)點(diǎn)發(fā)現(xiàn)其生成的重構(gòu)區(qū)塊的根哈希與確認(rèn)的區(qū)塊不同，這意味著該節(jié)點(diǎn)很可能遭受到了拜占庭傳輸節(jié)點(diǎn)的惡意攻擊.舉例來說，拜占庭節(jié)點(diǎn)可能會向更新節(jié)點(diǎn)發(fā)送錯誤的讀集，導(dǎo)致不同節(jié)點(diǎn)在執(zhí)行相同的跨片交易時視圖不一致.為了確保系統(tǒng)一致性，執(zhí)行節(jié)點(diǎn)需要重新執(zhí)行特定的交易集，以達(dá)到正確和一致的結(jié)果.此外，重新執(zhí)行的順序應(yīng)該遵循共識協(xié)議確認(rèn)的順序.

在區(qū)塊重構(gòu)階段，需要在節(jié)點(diǎn)之間廣播生成的重構(gòu)區(qū)塊以及一些相關(guān)信息，其中包括處理跨片交易時收到的狀態(tài)數(shù)據(jù)集合.遭受到攻擊的節(jié)點(diǎn)能夠在該階段收到正確的狀態(tài)數(shù)據(jù)集合，這些數(shù)據(jù)的正確性是被傳輸分片中ft+1 個節(jié)點(diǎn)簽名保證的.如果某個節(jié)點(diǎn)發(fā)現(xiàn)有節(jié)點(diǎn)故意提供錯誤的狀態(tài)數(shù)據(jù)，它可以從其他節(jié)點(diǎn)發(fā)送來的區(qū)塊確認(rèn)信息中獲取足夠多的正確狀態(tài)數(shù)據(jù)來進(jìn)行正確的驗證和執(zhí)行.

盡管交易重復(fù)執(zhí)行會給系統(tǒng)帶來額外的計算開銷，但本文認(rèn)為該開銷是可以接受的.首先，在許可鏈中，由于節(jié)點(diǎn)是經(jīng)過認(rèn)證和授權(quán)的，節(jié)點(diǎn)之間的信任程度較高，產(chǎn)生拜占庭節(jié)點(diǎn)的概率較低.其次，如果投票結(jié)果表明某個節(jié)點(diǎn)故意提供了錯誤的狀態(tài)數(shù)據(jù)，那么該節(jié)點(diǎn)可能會面臨一定的懲罰，比如將其標(biāo)記為不誠實節(jié)點(diǎn)并拒絕它所傳輸?shù)臓顟B(tài)數(shù)據(jù)，進(jìn)一步優(yōu)化網(wǎng)絡(luò)的安全性.最后，在真實場景中，交易的依賴性通常不會太復(fù)雜，只有少部分交易會訪問同一個狀態(tài)數(shù)據(jù)，因此交易重做的代價較低.綜上所述，數(shù)據(jù)恢復(fù)的開銷與風(fēng)險是可以接受的.

2.4 安全性分析

根據(jù)區(qū)塊鏈的特性，系統(tǒng)中各個分片通過共識協(xié)議達(dá)成一致，以確定需要處理的交易集.然而，在交易執(zhí)行過程中，可能會發(fā)生異常中止，這會破壞交易的一致性.除了拜占庭節(jié)點(diǎn)的惡意中止，本節(jié)將總結(jié)、分析和處理交易的其它異常中止.

交易異常中止可分為2 種：1）由崩潰故障引起的中止；2）不符合執(zhí)行條件引起的中止.在情況1）下，由于共識區(qū)塊依舊保留著異常中止的交易信息與序列號，崩潰的節(jié)點(diǎn)只需要在恢復(fù)時根據(jù)交易序列號重新獲取在共識區(qū)塊內(nèi)未提交的交易信息，并重新執(zhí)行.而在情況2）中，如圖6 所示，共識區(qū)塊內(nèi)包含2 筆跨片交易.2 個分片不僅都需要更新狀態(tài)，而且需要相互傳輸狀態(tài)數(shù)據(jù).如果其中一個更新分片中的跨片交易（如T4）被中止，那么所有更新分片中的這個交易都將被中止.這是因為2 個分片看到的狀態(tài)數(shù)據(jù)是相同的，操作邏輯也是相同的，因此最終執(zhí)行結(jié)果必然相同.

Fig.6 The transactions abort圖6 交易異常中止

此外，如果在處理跨分片交易時存在惡意節(jié)點(diǎn)故意保持沉默，這可能導(dǎo)致一些更新節(jié)點(diǎn)無法收到執(zhí)行交易所需的狀態(tài)數(shù)據(jù).為應(yīng)對這種情況，更新節(jié)點(diǎn)可以主動向同一分片中的其他節(jié)點(diǎn)請求狀態(tài)數(shù)據(jù).因此，本節(jié)提出的方法可以在所有情況下保證跨分片交易的一致性.

3 抗沖突的跨片交易執(zhí)行優(yōu)化方案

第2 節(jié)提出的無協(xié)調(diào)者的跨片交易執(zhí)行方法顯著地提高了跨片交易處理的效率，令分片區(qū)塊鏈系統(tǒng)在面對大量跨片交易時依然保持良好的性能.盡管區(qū)塊鏈能夠容忍低沖突的工作負(fù)載，但在面對高沖突的場景時，大量的沖突交易（包括跨片交易）會因網(wǎng)絡(luò)擁堵或計算資源不足而被阻塞，進(jìn)而影響系統(tǒng)吞吐量，延長跨片交易的響應(yīng)時間.此外，如果跨片交易長時間未能被成功提交，相關(guān)分片將中止該交易，這需要額外引入多輪通信協(xié)議來保證交易一致性，造成資源浪費(fèi)和高昂的通信代價.

現(xiàn)今，一些工作利用交易重排序技術(shù)來提高系統(tǒng)在高沖突負(fù)載下的性能.然而，這些方法仍然存在一些局限，無法直接應(yīng)用于排序鎖機(jī)制.首先，這些重排序算法主要是針對EOV 范式系統(tǒng)中高交易中止率的問題提出的，目的是通過改變交易提交順序，找到最小中止交易集合，從而提升系統(tǒng)的交易處理性能.其次，由于這類重排序操作發(fā)生在排序階段之前，所以它們無需考慮交易排序的限制，這與需要全局序的排序鎖機(jī)制相矛盾.最后，重排序算法是針對單機(jī)節(jié)點(diǎn)實現(xiàn)的優(yōu)化算法，尚未考慮跨片交易執(zhí)行時狀態(tài)傳輸對系統(tǒng)交易處理性能的影響，以及跨片交易執(zhí)行開銷要遠(yuǎn)大于片內(nèi)交易的情況.

因此，本節(jié)對第2 節(jié)提出的跨片交易執(zhí)行方法進(jìn)行優(yōu)化，通過將交易重排序策略與跨片執(zhí)行方法相結(jié)合，提高執(zhí)行方法的抗沖突能力.與傳統(tǒng)重排序方案不同，本節(jié)提出的策略主要通過提高執(zhí)行并發(fā)度來提升系統(tǒng)性能，它不僅可以通過重排序方案獲得多個支持高并發(fā)執(zhí)行的交易子集，而且也針對跨片交易執(zhí)行場景進(jìn)一步優(yōu)化，提高了跨片交易傳輸?shù)男剩@著降低了跨片交易的延遲.

3.1 基于排序鎖機(jī)制的交易重排序

本文提出的跨片執(zhí)行方法是通過排序鎖機(jī)制對塊內(nèi)交易進(jìn)行并發(fā)控制.排序鎖機(jī)制雖然賦予了交易一定程度的并行處理能力，但在高沖突負(fù)載下，跨片交易的執(zhí)行效率仍然會被嚴(yán)重影響.因此，本文研究對排序鎖機(jī)制進(jìn)行了優(yōu)化，設(shè)計了一個交易重排序方案，以提高系統(tǒng)在處理高沖突負(fù)載時的表現(xiàn).同時，優(yōu)化后的并發(fā)處理方法具有通用性，跨片交易和片內(nèi)交易執(zhí)行都可以從該方案中受益.本文將結(jié)合一個具體的例子來介紹重排序方案的工作原理和執(zhí)行細(xì)節(jié)，交易用例以及交易之間的沖突關(guān)系參見表2和圖7.

Fig.7 Conflict graph圖7 沖突圖

Table 2 Transaction Table表2 交易集表

本節(jié)提出的交易重排序策略主要是通過交易子集劃分算法來解決低交易并發(fā)度和單一鎖管理器串行加鎖的問題.交易子集劃分算法基于讀集和寫集之間的沖突關(guān)系，動態(tài)將需要執(zhí)行的一批交易劃分為多個子集內(nèi)部不存在沖突的交易子集.由于任何一個交易子集中的交易互不沖突，它們可以并行地執(zhí)行，從而最大限度地提高交易的并發(fā)執(zhí)行性能.此外，該算法還實現(xiàn)了對交易子集內(nèi)部所有交易的并行無沖突加鎖，消除了排序鎖機(jī)制的單點(diǎn)性能瓶頸.算法2 詳細(xì)描述了如何將一批交易通過交易重排序機(jī)制劃分為多個交易子集.

算法2.交易子集劃分算法TransactionsPartition.

輸入：帶有交易序號的交易隊列Btxs；

輸出：互不沖突的交易子集集合TSS.

代碼第1 行初始化了輸出的交易子集的集合.代碼2～16 行將交易劃分為內(nèi)部互不沖突的交易子集，其中子集標(biāo)號較小的具有更高的執(zhí)行優(yōu)先級.具體而言，代碼第3 行從交易隊列中取出一筆交易進(jìn)行處理，第4 行確定交易子集的數(shù)量.代碼5～11 行判斷所處理的交易是否與當(dāng)前交易子集內(nèi)的交易存在沖突.若不存在沖突，則將該交易并入該子集中；否則繼續(xù)檢索下一個子集.如果遍歷所有子集后發(fā)現(xiàn)該筆交易與所有子集都存在沖突情況，則初始化一個只包含該筆交易的子集，并將其標(biāo)號賦值為n+1.

圖8 展示了應(yīng)用交易子集劃分算法來劃分交易的一個例子，T1～T6是同一個區(qū)塊內(nèi)的6 筆交易.根據(jù)交易序號從小到大遍歷所有的交易讀寫集，并把它們分為多個集合內(nèi)無沖突的交易子集.對于第1 筆交易T1,根據(jù)此策略，初始化過后的TSS沒有一個交易子集，于是將生成第1 個交易子集S1并將T1并入S1；然后，對于第2 筆交易T2，它的讀寫集與T1存在沖突，因此無法將其放入子集S1，而是將其放入新生成的第2 個交易子集S2；對于第3 筆交易T3，該策略根據(jù)子集下標(biāo)從小到大尋找與T3不沖突的集合，可知S1中的交易均和T3無沖突，于是將T3放入交易子集S1中.同理，T4將被放入新生成的交易子集S3中，T5并入S1中，T6并入S2中.最終，本算法可以獲得S1={T1,T3,T5}，S2={T2,T6}和S3={T4}這3 個交易子集.

Fig.8 Transaction partition with reorder scheme and transactions execution圖8 重排序方案的交易劃分與交易執(zhí)行

盡管同一個交易子集中的交易可以并行加鎖，但不同子集之間的加鎖操作必須按照一定的順序進(jìn)行.具體而言，標(biāo)號較小的交易子集需要優(yōu)先于標(biāo)號較大的交易子集進(jìn)行加鎖操作.結(jié)合圖8 用例，對于S1中的3 筆交易，多個線程可以并行地對它們進(jìn)行加鎖操作，因為它們之間不存在任何依賴關(guān)系；而對于S2中的交易，由于它們依賴于S1中的交易，必須等待S1中的所有交易均被鎖定后，才能進(jìn)行加鎖操作.最后，這批交易的執(zhí)行結(jié)果等價于串行執(zhí)行結(jié)果T1→T3→T5→T2→T6→T4.

算法3.沖突檢測函數(shù)HasConflict算法.

輸入：一筆交易T，一個交易子集S；

輸出：一個布爾值Bool.

函數(shù)HasConflict用于檢測一筆交易是否與一個交易子集存在沖突，輸入包括一筆交易T和一個交易子集S，輸出為代表兩者沖突結(jié)果的布爾值Bool.該函數(shù)首先將交易T寫集W（T）與交易子集S的R（S）和W（S）進(jìn)行比較，判斷該筆交易是否與集合S中的任何一個交易存在“讀寫”沖突或“寫寫”沖突.再者，由于“讀讀”操作之間不存在沖突，在處理該交易的讀集時，該函數(shù)僅會判斷交易T的讀集R（T）與交易子集S的寫集W（S）的沖突情況，即判斷該交易是否可能讀到集合S中交易所修改的數(shù)據(jù).根據(jù)這2 輪檢測的結(jié)果，該算法會決定是否將該交易并入交易子集S中.具體來說，接圖8 所示的例子，當(dāng)T4嘗試加入交易子集S1={T1,T3}時，T4的寫集中的b與S1中T3的讀集產(chǎn)生沖突，因而無法并入S1.

3.2 針對跨片交易的重排序優(yōu)化策略

3.1 節(jié)提出的交易重排序策略有效地提升了交易的執(zhí)行并發(fā)度，從而增強(qiáng)了跨片交易執(zhí)行方法的抗沖突能力.但是，這種策略忽視了交易重排序?qū)缙灰讏?zhí)行的影響.在執(zhí)行跨片交易時，每個更新分片需要等待傳輸分片傳輸?shù)臓顟B(tài)數(shù)據(jù)，而影響狀態(tài)數(shù)據(jù)傳輸效率的原因有2 個方面：一方面，由于每個分片執(zhí)行的交易集不同，處理同一筆跨片交易的時間點(diǎn)也會有差異.如果貿(mào)然地通過重排序策略將某筆跨片交易的執(zhí)行順序排在與之沖突的片內(nèi)交易之后，那么與該筆跨片交易相關(guān)的狀態(tài)數(shù)據(jù)必須等到與之沖突的片內(nèi)交易全部執(zhí)行完畢后才能傳輸，這嚴(yán)重影響了其他更新分片的交易處理性能.甚至，跨片交易可能因為長期得不到狀態(tài)數(shù)據(jù)而需要重新執(zhí)行，這無疑會極大地浪費(fèi)計算資源.另一方面，為了保證數(shù)據(jù)的一致性，傳統(tǒng)的排序鎖機(jī)制僅在跨片交易執(zhí)行階段以交易為單位進(jìn)行狀態(tài)數(shù)據(jù)交換，以確保一筆跨片交易在相同的視圖下執(zhí)行.如此細(xì)粒度的狀態(tài)傳輸會導(dǎo)致分片之間頻繁地進(jìn)行信息交互，從而造成繁重的網(wǎng)絡(luò)開銷.同時，該機(jī)制也無法有效地利用帶寬優(yōu)勢來處理跨片交易.正如圖8 中的例子所示，交易子集S2中的跨片交易T2所需的狀態(tài)數(shù)據(jù)a需要等待S1中的片內(nèi)交易T1執(zhí)行完畢.同時，執(zhí)行T2與T5這2 筆跨片交易也伴隨著等量次數(shù)的片間數(shù)據(jù)交換.

針對這2 個方面的挑戰(zhàn)，本節(jié)將進(jìn)一步優(yōu)化交易重排序策略，消除跨片交易對片內(nèi)交易的依賴，提高狀態(tài)數(shù)據(jù)的傳輸效率.首先，在鎖管理器遍歷交易時，該優(yōu)化方法會對跨片交易和片內(nèi)交易區(qū)別處理.對于跨片交易，只需要確保它不與交易子集中的其它交易發(fā)生沖突即可將其并入該子集，處理方法與算法2 如出一轍.而對于片內(nèi)交易，該算法不僅需要檢測與當(dāng)前遍歷的交易子集的沖突，還需要檢測比當(dāng)前交易子集優(yōu)先級更高的子集中的跨片交易的沖突，以消除與跨片交易的“讀寫”和“寫寫”依賴.最后，在交易子集劃分完成之后，本策略將部分跨片交易所需的且不會被片內(nèi)交易修改的狀態(tài)數(shù)據(jù)批量傳輸至更新節(jié)點(diǎn).通過這種方式，傳輸分片可以更高效地將狀態(tài)數(shù)據(jù)傳輸?shù)矫總€更新分片，降低分片之間狀態(tài)傳輸?shù)念l率，大幅度縮短跨片交易的響應(yīng)時間.

算法4 詳細(xì)描述了如何將一批片內(nèi)交易放入已存在的無沖突交易子集中，同時保證每一筆跨片交易都不會產(chǎn)生對片內(nèi)交易的依賴.然后，輸出一個包含片內(nèi)交易與跨片交易的交易子集集合.算法4 與算法2 主要有2 處不同：1）片內(nèi)交易T先從下標(biāo)更大的交易子集開始遍歷.如果算法4 從下標(biāo)較小的交易子集開始遍歷，檢測到交易T與某個交易子集Sj沒有發(fā)生沖突，算法4 無法確定T與Sk（ji）中.2）算法4 在判斷交易T與交易子集是否沖突時，需要檢測子集中與之產(chǎn)生沖突的交易類型.如果T與跨片交易產(chǎn)生沖突，則算法4 的處理方式與算法2 相同，直接中止遍歷并將交易T并入對應(yīng)的交易子集中.當(dāng)T與片內(nèi)交易產(chǎn)生沖突時，算法4 會繼續(xù)向前遍歷，直到遍歷完所有子集或遇到與其沖突的交易才會停止，這保證了算法4 產(chǎn)生的交易子集數(shù)量盡可能少，最大程度提升執(zhí)行的并發(fā)度.

算法4.優(yōu)化交易子集劃分算法TransactionsPatitionByType.

輸入：交易子集集合TSS，帶有交易序號的交易隊列Itxs；

輸出：插入片內(nèi)交易的交易子集集合TSS.

代碼5～10 行展示了片內(nèi)交易尋找適合并入的交易子集的過程.每次檢測到該子集與交易T無沖突時，算法4 都會更新并入的子集下標(biāo)n.由于采用自后向前遍歷方法，所選擇的并入子集的優(yōu)先級隨著遍歷的進(jìn)行而逐漸提高.當(dāng)一輪交易子集的遍歷完成后，代碼16～20 行將交易T并入先前選出的最適合的子集Sn中.如果下標(biāo)n代表的交易子集不存在，則會新生成一個包含交易T的交易子集.

最后，算法4 獲得了一個包含片內(nèi)交易與跨片交易的交易子集集合TSS.由于不存在跨片交易對片內(nèi)交易的數(shù)據(jù)依賴，在執(zhí)行任意一個交易子集前，傳輸分片可以將子集中跨片交易所需的狀態(tài)數(shù)據(jù)打包發(fā)送至對應(yīng)的更新分片，不會發(fā)生由于更新分片讀到舊數(shù)據(jù)產(chǎn)生的執(zhí)行結(jié)果不一致的情況.

圖9 展示了應(yīng)用算法4 優(yōu)化后的交易子集算法來劃分交易的一個例子.首先，使用算法2 處理跨片交易，并將它們劃分到交易子集S1中，因為T2和T5之間不存在沖突.接下來，使用算法4 處理片內(nèi)交易.交易T1與跨片交易T2存在沖突，因此被合并到新的交易子集S2中.類似地，交易T3與T2存在沖突，但與T1無沖突，因此也被合并到S2中.對于交易T4，根據(jù)算法4，當(dāng)遍歷到S2時，它與片內(nèi)交易T3沖突.繼續(xù)遍歷，直到檢測到與跨片交易T2沖突，記錄其并入的子集下標(biāo)為3，然后將其合并到新的交易子集S3中.交易T6與S2中的片內(nèi)交易T3存在沖突，但與任何跨片交易都沒有沖突，因此被合并到S1中.綜上所述，算法4 可以生成3 個交易子集S1={T2,T5,T6}，S2={T1,T3}和S3={T4}.簡而言之，通過優(yōu)化的重排方案，不僅跨片交易以并發(fā)執(zhí)行，而且整個分片區(qū)塊鏈系統(tǒng)在高傳輸效率運(yùn)行.

Fig.9 Optimized transactions partition and transactions execution圖9 優(yōu)化后的交易劃分與交易執(zhí)行

算法5.引入交易重排序策略后的交易執(zhí)行過程.

輸入：一批交易B.

算法5 描述了引入交易重排序策略后交易的執(zhí)行過程.交易開始執(zhí)行時，會初始化一個執(zhí)行隊列ExecutionQueue和遠(yuǎn)程狀態(tài)數(shù)據(jù)集RD.當(dāng)有遠(yuǎn)程數(shù)據(jù)傳輸至本地時，會將其暫存至RD中.在鎖定階段，算法5 首先將一批交易B按交易類型劃分至不同的交易隊列中，隊列中的交易順序嚴(yán)格按照交易序列號從低到高排列.然后，通過算法2 與算法4 將多個交易子集進(jìn)行劃分.最后，利用多個鎖線程并行地給一個交易子集中的所有交易加鎖.順利完成加鎖操作的交易會進(jìn)入執(zhí)行階段，算法并行地從Execution-Queue中取出交易并執(zhí)行.由于跨片交易在同一個交易子集中不存在沖突，傳輸分片可以一次性將多個狀態(tài)數(shù)據(jù)提前傳輸至更新分片，無需等待交易執(zhí)行過程中傳輸.

4 實驗與結(jié)果

基于提出的無協(xié)調(diào)者跨片交易執(zhí)行方法，本節(jié)實現(xiàn)了原型系統(tǒng)CoCoS，并對其性能進(jìn)行測試.主要測試了該方法在不同跨片交易占比下的系統(tǒng)執(zhí)行交易的吞吐量、交易延遲等方面的性能，并與基于2PC協(xié)議的分片系統(tǒng)（如AHL）進(jìn)行對比.

4.1 實驗環(huán)境

1）硬件環(huán)境.所有的實驗都在一個集群上進(jìn)行，該集群有20 臺機(jī)器，配備了英特爾至強(qiáng)2.5 GHz CPU，每個CPU 包含了32 個核心，還配備了32 GB 內(nèi)存和320 GB 磁盤空間以及100 MB 網(wǎng)絡(luò)帶寬.本實驗使用Ubuntu 16 系統(tǒng)，并運(yùn)行g(shù)++的7.3 版本.本實驗使用go-Ethereum 作為庫，并將一個開源的PBFT 實現(xiàn)集成到本文的系統(tǒng)中.每個分片被分配多個工作線程來處理交易.實驗的結(jié)果取10 次測試結(jié)果的平均值，以提高實驗的準(zhǔn)確性.

2）軟件環(huán)境.本文采用具有C++版本的Ethereum作為系統(tǒng)庫來執(zhí)行智能合約.為了實現(xiàn)交易的并發(fā)執(zhí)行，本實驗創(chuàng)建了一個虛擬機(jī)實例池，每個實例池管理1 個以太坊虛擬機(jī)（Ethereum virtual machine，EVM）.實驗設(shè)置了1 個共識分片和4 個執(zhí)行分片.每一個分片都由4 個節(jié)點(diǎn)組成，并且每個節(jié)點(diǎn)都被分配在不同的機(jī)器上.共識分片負(fù)責(zé)向每個執(zhí)行分片傳輸共識協(xié)議產(chǎn)生的共識區(qū)塊.

3）智能合約.本文通過SmallBank 智能合約來測試跨片交易執(zhí)行方法的性能.SmallBank 智能合約經(jīng)常被用作評估OLTP 數(shù)據(jù)庫系統(tǒng)的性能基準(zhǔn)，也被廣泛用于區(qū)塊鏈系統(tǒng)的性能測試.本文所有實驗使用的數(shù)據(jù)集包含1 000 萬客戶和相應(yīng)的1 000 萬賬戶.此外，本文為SmallBank 設(shè)計了一個額外的Send-Payment交易來實現(xiàn)轉(zhuǎn)賬功能.

4.2 測試負(fù)載

在介紹實驗中使用的工作負(fù)載之前，需要先定義跨片率（cross-shard rate）與沖突率（conflict rate）的概念.跨片率主要指的是跨片交易數(shù)量與總交易數(shù)量之比.本實驗實現(xiàn)的負(fù)載生成器考慮了交易數(shù)、賬戶數(shù)和跨片率，可以為每組實驗生成相應(yīng)的負(fù)載.實驗測試了在4 個不同跨片率下系統(tǒng)執(zhí)行跨片交易的性能，這4 個跨片率分別為0，0.3，0.6 和0.9.跨片率也反映了分片之間的通信頻率.所有跨片和分片內(nèi)的交易被均勻地分布在不同的分片上，以達(dá)到分片的負(fù)載均衡.而沖突率表示沖突交易的數(shù)量與總交易的數(shù)量之比.實驗使用沖突率來描述交易集的負(fù)載情況，并選擇0.3，0.6 和0.9 的沖突率代表3 種不同程度的沖突.此外，這些沖突交易被均勻地分布在每個分片中，以確保每個分片的性能保持相似.另外，需要注意的是，一個區(qū)塊最多只能包含1 000 筆交易.

4.3 系統(tǒng)跨片處理性能

本節(jié)介紹跨片交易執(zhí)行方法的實驗結(jié)果，包括吞吐量、延遲和擴(kuò)展性.我們從單節(jié)點(diǎn)吞吐量和每個塊的延遲評估方法的總體性能，無需共識.本文部署了4 個執(zhí)行分片.實驗細(xì)節(jié)如下.

4.3.1 系統(tǒng)吞吐量

圖10 展示了每個節(jié)點(diǎn)的跨片率與吞吐量之間的關(guān)系.本文方法和基于2PC 協(xié)議的跨片執(zhí)行方法進(jìn)行了比較.由于2PC 協(xié)議涉及分片之間多輪的通信與交易阻塞，它在處理跨片交易時表現(xiàn)不佳.基于2PC 協(xié)議的跨片執(zhí)行方法在高跨片率下最高只能達(dá)到6 000 TPS，而在高跨片率情況下僅能達(dá)到1 200 TPS.其性能低下的主要原因在于處理跨片交易時需要進(jìn)行多輪片間交互，導(dǎo)致跨片交易確認(rèn)時間延長，并嚴(yán)重阻塞其他交易的執(zhí)行.同時，隨著負(fù)載跨片率的升高，龐大的通信開銷使得系統(tǒng)處理性能急劇惡化，該現(xiàn)象與本文的預(yù)期結(jié)果一致.

Fig.10 System throughput圖10 系統(tǒng)吞吐量

本節(jié)還測試了不同數(shù)量的工作線程下無協(xié)調(diào)者的跨片交易執(zhí)行方法的表現(xiàn).由圖10 可知，該方法可以利用多線程的優(yōu)勢來處理交易.當(dāng)利用4 個工作線程處理無跨片交易的交易集時，每個節(jié)點(diǎn)的吞吐量可以達(dá)到22 000 TPS；相較于基于2PC 協(xié)議的方法，在高跨片率下系統(tǒng)的性能僅下降了約30%.并且，隨著工作線程數(shù)量的增加，系統(tǒng)的吞吐量也會明顯地提升.然而，由于狀態(tài)數(shù)據(jù)傳輸所需的時間以及單一鎖管理器可能存在的瓶頸，特別是在高跨片率負(fù)載時，增加線程數(shù)并不能顯著提高系統(tǒng)的執(zhí)行性能.這是因為系統(tǒng)性能的瓶頸從線程數(shù)量轉(zhuǎn)移到了狀態(tài)傳輸和鎖管理器上.此外，隨著節(jié)點(diǎn)數(shù)量增加至30 個，系統(tǒng)吞吐量并無明顯地降低.

4.3.2 交易延遲

圖11 展示了每個節(jié)點(diǎn)的跨片率與交易延遲之間的關(guān)系.在區(qū)塊鏈中，交易以塊為單位進(jìn)行提交，并且只有區(qū)塊內(nèi)所有交易都執(zhí)行完畢，對應(yīng)區(qū)塊才能提交.在區(qū)塊內(nèi)的交易設(shè)置為1 000 筆的情況下，基于2PC 的執(zhí)行方法的交易延遲隨著跨片率的上升而急劇增加，在高跨片率下延遲達(dá)到837 ms.這是因為在高跨片負(fù)載下大量的塊內(nèi)交易堆積，執(zhí)行速度緩慢，而區(qū)塊提交的時間也會因此延長.

Fig.11 Transaction latency圖11 交易延遲

反觀本文提出的跨片交易執(zhí)行方法，無論在任何跨片負(fù)載下，甚至系統(tǒng)擴(kuò)展至30 個節(jié)點(diǎn)，交易延遲都能夠保持在較低水平，且趨勢幾乎為一條水平線.同時，與2PC 協(xié)議不同，本文方法還可以更靈活地利用多線程的優(yōu)勢來加速跨片交易的執(zhí)行，無需考慮協(xié)調(diào)者的數(shù)量與開銷.

4.3.3 系統(tǒng)擴(kuò)展性

圖12 顯示了CoCoS 系統(tǒng)在不同分片數(shù)量的執(zhí)行分片下的系統(tǒng)吞吐量.實驗使用的交易集包含1 000萬名客戶和相應(yīng)的1 000 萬賬戶，交易的讀寫集均勻分布在1 000 萬數(shù)量集的賬戶里.同時，本實驗給每個分片配備了2 個工作線程來執(zhí)行交易.本測試將CoCoS 系統(tǒng)分片數(shù)量從1 擴(kuò)展至12，并通過不同分片數(shù)量下的吞吐量表現(xiàn)來衡量系統(tǒng)的可擴(kuò)展性.實驗表明，隨著分片數(shù)量的增加，系統(tǒng)的吞吐量呈線性增長趨勢.當(dāng)擴(kuò)展到12 個分片時，CoCoS 系統(tǒng)的吞吐量達(dá)到了近75 000 TPS.

Fig.12 System scalability圖12 系統(tǒng)可擴(kuò)展性

隨著分片數(shù)量的不斷增加，跨片交易比例也不斷上升，從而導(dǎo)致分片單點(diǎn)性能下降，交易延遲略微增加.然而，整個系統(tǒng)的性能隨著分片數(shù)量的增加而線性提升，這也符合對系統(tǒng)擴(kuò)展性的定義.綜合本文的所有實驗，可以證明本節(jié)設(shè)計的CoCoS 系統(tǒng)在系統(tǒng)吞吐量、交易延遲和可擴(kuò)展性方面遠(yuǎn)優(yōu)于采用兩階段提交協(xié)議的系統(tǒng).

4.3.4 系統(tǒng)容錯恢復(fù)

圖13 展示了CoCoS 系統(tǒng)在面對各種類型攻擊時的容錯能力.本文通過模擬傳輸節(jié)點(diǎn)的宕機(jī)或作惡行為，使得執(zhí)行節(jié)點(diǎn)無法收到狀態(tài)數(shù)據(jù)或接收到錯誤的狀態(tài)數(shù)據(jù).

Fig.13 System fault tolerance圖13 系統(tǒng)容錯

圖13 表明，在單一工作線程的條件下，傳輸節(jié)點(diǎn)的崩潰并不會嚴(yán)重影響交易執(zhí)行.這是因為本文提出的執(zhí)行方法是非阻塞的，當(dāng)一筆跨片交易無法滿足執(zhí)行條件時，系統(tǒng)會將其掛起，并繼續(xù)處理其他交易，直到所需的狀態(tài)數(shù)據(jù)到達(dá).當(dāng)節(jié)點(diǎn)收到拜占庭節(jié)點(diǎn)的錯誤數(shù)據(jù)時，會產(chǎn)生額外的開銷用于重做交易.隨著跨片率的提高，節(jié)點(diǎn)受到攻擊的頻率也會增加，導(dǎo)致需要重做的交易數(shù)量增加，從而降低系統(tǒng)的吞吐量.此外，當(dāng)節(jié)點(diǎn)檢測到惡意的傳輸節(jié)點(diǎn)時，可以選擇拒絕該節(jié)點(diǎn)的消息，并從其他誠實的傳輸節(jié)點(diǎn)獲取數(shù)據(jù)；由于不再從惡意傳輸節(jié)點(diǎn)獲得狀態(tài)數(shù)據(jù)，系統(tǒng)的吞吐也不會因重做交易而降低.

4.4 交易重排序方法性能

本節(jié)將分別介紹排序鎖機(jī)制的原方案、引入交易重排序方案和針對跨片交易優(yōu)化后的方案的實驗結(jié)果.節(jié)點(diǎn)的配置與4.3 節(jié)的實驗相同.此外，本節(jié)設(shè)置了2 個不同的交易集，分別是跨片沖突和片內(nèi)沖突，以展示交易重排序方案在不同性質(zhì)負(fù)載沖突下的效率.

4.4.1 原始的跨片交易執(zhí)行方法

圖14 和圖15 分別展示了傳統(tǒng)排序鎖機(jī)制在面對不同沖突率和不同沖突類型時的表現(xiàn).

Fig.14 Throughput of ordered locking mechanism under intraconflict圖14 采用排序鎖機(jī)制的片內(nèi)沖突下的吞吐量

Fig.15 Throughput of ordered locking mechanism under crossconflict圖15 采用排序鎖機(jī)制的跨片沖突下的吞吐量

通過實驗可以看出，基于排序鎖的并發(fā)控制方法不能高效地處理沖突交易.當(dāng)交易不存在沖突時，交易之間不會同時訪問一個狀態(tài)數(shù)據(jù)，因此鎖線程可以無阻塞地向這些交易授予鎖，所有交易可以完全地并行執(zhí)行.在這種情況下，基于排序鎖的并發(fā)控制方法的性能和樂觀并發(fā)控制方法的性能相當(dāng)，在8 個工作線程的條件下單分片的吞吐量可以達(dá)到45 000 TPS.

但隨著沖突率的增加，基于排序鎖機(jī)制的并發(fā)控制方法的性能急劇降低.由圖14 可知，在沖突率為0.3 的情況下，吞吐量下降到原來的30%左右.產(chǎn)生這種現(xiàn)象的原因在于，根據(jù)基于鎖的并發(fā)控制的特點(diǎn)，在高沖突負(fù)載下，多個交易會同時請求對同一狀態(tài)數(shù)據(jù)進(jìn)行大量的加解鎖操作，線程在等待鎖和釋放鎖的過程中來回顛簸，從而影響了系統(tǒng)整體的性能.沖突嚴(yán)重時，系統(tǒng)近乎串行地執(zhí)行交易.此時，即便擁有多個工作線程，系統(tǒng)也難以利用它們高效地執(zhí)行交易，反而多線程頻繁的上下文切換會消耗大量的CPU 資源，從而降低系統(tǒng)的吞吐量.

特別是在基于排序鎖機(jī)制的分片區(qū)塊鏈系統(tǒng)中，跨片交易沖突對系統(tǒng)性能的影響是災(zāi)難性的.由圖15可知，在負(fù)載沖突率為0.3 的情況下，分片的吞吐量最高僅為2 031 TPS，僅為同條件下片內(nèi)交易沖突的22%；而在面對高沖突率負(fù)載時，系統(tǒng)性能更加糟糕；在8 個工作線程的條件下，系統(tǒng)性能僅為同條件下片內(nèi)沖突的15%.隨著線程數(shù)量的增加，系統(tǒng)的處理性能會進(jìn)一步下降.具體而言，高沖突場景下跨片交易的狀態(tài)傳輸延遲和鎖機(jī)制本身的缺陷是系統(tǒng)性能惡化的主要原因.在跨片交易沖突率達(dá)到0.9 的情況下，將線程數(shù)量從4 增加到8 時幾乎沒有對系統(tǒng)吞吐量產(chǎn)生提升，此時系統(tǒng)的性能瓶頸在于激烈的鎖資源競爭.因此，采用更為高效的策略來應(yīng)對高沖突的場景是必要的.

4.4.2 引入交易重排序的跨片交易執(zhí)行方法

圖16 展示了排序鎖機(jī)制在引入交易重排序策略后，系統(tǒng)在處理片內(nèi)交易沖突時的性能，其中吞吐比為引入交易重排序方案的吞吐量和基于排序鎖方案的吞吐量的比值.在高沖突的交易負(fù)載下，系統(tǒng)可以利用8 個工作線程來達(dá)到41 000 TPS 的吞吐量.與執(zhí)行無沖突的交易集相比，采用交易重排序方法的系統(tǒng)在處理高沖突交易集的表現(xiàn)依舊出色，其吞吐量降低了不到10%.不難發(fā)現(xiàn)，交易重排序方案通過將交易的順序進(jìn)行調(diào)換來增加交易執(zhí)行的并發(fā)度，縮短了交易的阻塞時間.此外.根據(jù)交易子集劃分算法，鎖線程還可以并行給同一個交易子集內(nèi)部的交易上鎖，突破了單點(diǎn)瓶頸問題.如此一來，盡可能多的交易能夠通過交易重排序機(jī)制迅速獲得鎖資源并執(zhí)行.總而言之，該并發(fā)執(zhí)行方法有效地利用多核處理器執(zhí)行交易，顯著增加了系統(tǒng)的吞吐量，整體性能明顯優(yōu)于原排序鎖機(jī)制.

Fig.16 Throughput of scheme with reorder mechanism under intra-conflict圖16 引入交易重排序機(jī)制的片內(nèi)沖突下的吞吐量

而圖17 展示了排序鎖算法在引入交易重排序后，系統(tǒng)在處理跨片交易沖突時的性能，其中吞吐比為引入交易重排序方案的吞吐量和基于排序鎖方案的吞吐量的比值.實驗數(shù)據(jù)表明，引入重排序方案的系統(tǒng)在處理跨片交易沖突時表現(xiàn)依然優(yōu)秀.在采用4 個工作線程的條件下，系統(tǒng)的吞吐量基本維持在20 000 TPS 左右，并且不會因負(fù)載的變化而大幅度下降.與片內(nèi)交易不同，在處理跨片交易中，交易執(zhí)行并發(fā)度越高，越多的跨片交易可以有效地利用帶寬將狀態(tài)數(shù)據(jù)更加迅速地發(fā)送到更新分片上，提高跨片交易的執(zhí)行效率.但是在8 個工作線程的情況下，處理跨片沖突的性能略低于處理片內(nèi)沖突的性能.這是因為此時整個系統(tǒng)的性能瓶頸已從線程數(shù)量轉(zhuǎn)移到了執(zhí)行跨片交易時的狀態(tài)傳輸上，系統(tǒng)已經(jīng)無法通過增加工作線程數(shù)量來提高吞吐量，唯有通過對狀態(tài)數(shù)據(jù)傳輸進(jìn)行優(yōu)化，系統(tǒng)的性能才能再進(jìn)一步提高.

Fig.17 Throughput of scheme with reorder mechanism under cross-conflict圖17 引入交易重排序機(jī)制的跨片沖突下的吞吐量

4.4.3 針對跨片交易的重排序優(yōu)化策略

圖18 展示了針對跨片交易優(yōu)化后的排序鎖機(jī)制的性能，其中吞吐比為針對跨片交易優(yōu)化方案的吞吐量和引入交易重排序方案的吞吐量的比值.該優(yōu)化策略在8 個工作線程下的表現(xiàn)比單純引入重排序的策略高出6 000 TPS.由于傳輸節(jié)點(diǎn)提前將某些狀態(tài)傳輸打包傳輸?shù)礁鹿?jié)點(diǎn)，更新分片在處理部分跨片交易時無需等待數(shù)據(jù)的傳輸就可以及時從本地獲取，一定程度降低了跨片交易的延遲.

Fig.18 Throughput of optimized scheme for state transfer圖18 針對狀態(tài)傳輸優(yōu)化后的吞吐量

5 總結(jié)

本文提出了一種用于分片許可區(qū)塊鏈的跨片交易執(zhí)行方法，用來提高分片系統(tǒng)的性能和降低跨片交易的延遲.在本文提出的方法中，跨片交易可以通過基于確定性執(zhí)行的單向通信執(zhí)行，并且無需協(xié)調(diào)者的幫助.此外，本文設(shè)計了一種抗沖突的跨片交易執(zhí)行優(yōu)化方案，通過交易重排序策略實現(xiàn)支持高并發(fā)的交易子集劃分，從而提高系統(tǒng)在高沖突負(fù)載下的吞吐量和狀態(tài)傳輸?shù)男?實驗結(jié)果支持了本文工作的實用性與有效性.

作者貢獻(xiàn)聲明：闕琦峰提出了研究思路，設(shè)計與完成實驗；陳之豪負(fù)責(zé)論文修改和實驗設(shè)計；張召提出指導(dǎo)意見并修改論文；楊艷琴與周傲英負(fù)責(zé)審閱論文并提出指導(dǎo)意見.