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

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

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

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

（51205903035@stu.ecnu.edu.cn）

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 基本定義

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

Table 1 Symbol Table表1 符號(hào)表

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

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

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

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

2.1.2 跨片交易執(zhí)行

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

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

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

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

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

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

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

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

2.2.1 排序鎖的工作原理

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

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

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

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

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

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

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

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

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

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

舉例來(lái)展示該跨片交易執(zhí)行方法的實(shí)現(xiàn)細(xì)節(jié).如圖3 所示，分片1 與T1、T2和T3這三筆交易的關(guān)系可以分別對(duì)應(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 無(wú)需執(zhí)行T1，自然地將該交易忽略，這符合2.1.2 節(jié)中所述的第1 類(lèi)關(guān)系中描述的場(chǎng)景.對(duì)于T2，它需要判斷Alice 賬戶是否有余額，以此來(lái)確定是否在Carl 賬戶余額上增加5，此時(shí)分片1就會(huì)成為T(mén)2的一個(gè)傳輸分片，向Carl 賬戶所在的分片傳輸Alice 賬戶數(shù)據(jù)，這符合2.1.2 節(jié)中所述的第2類(lèi)關(guān)系中描述的場(chǎng)景.最后在處理T3時(shí)，Alice 需要向Bob 轉(zhuǎn)賬5.由于該筆交易需要同時(shí)修改Alice 和Bob 的賬戶余額，這2 個(gè)分片分別將Alice 與Bob 的賬戶余額發(fā)送給對(duì)方，然后雙方都執(zhí)行該筆交易，并根據(jù)執(zhí)行的結(jié)果修改各自的賬戶余額，這符合2.1.2節(jié)中所述的第3 類(lèi)關(guān)系中描述的場(chǎng)景.

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

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

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

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

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

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

本研究基于雙射傳輸[20]設(shè)計(jì)一種拜占庭數(shù)據(jù)傳輸方案，具體實(shí)現(xiàn)如圖4 所示.該方案支持跨片狀態(tài)傳輸，并能夠以最小的消息傳輸代價(jià)完成傳輸，同時(shí)避免了廣播所帶來(lái)的巨大成本.我們將對(duì)最小狀態(tài)數(shù)據(jù)傳輸問(wèn)題進(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個(gè)拜占庭節(jié)點(diǎn)；給定更新節(jié)點(diǎn)數(shù)量|Nu|=nu，Nu能夠容忍fu個(gè)拜占庭節(jié)點(diǎn).找到傳輸分片需要發(fā)送的狀態(tài)數(shù)據(jù)（簡(jiǎn)稱消息）的最小數(shù)量m.

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

定理1.給定一些傳輸分片的節(jié)點(diǎn)Nt和更新分片的節(jié)點(diǎn)Nu.當(dāng)nt≥nu時(shí)，讓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是一個(gè)誠(chéng)實(shí)的節(jié)點(diǎn)應(yīng)該接收或發(fā)送的最小消息數(shù)量.而變量r是需要接收或發(fā)送q+1 條消息的誠(chéng)實(shí)節(jié)點(diǎn)數(shù)量.以下是這2 條定理的證明.

證明1.通過(guò)反證法證明m為最小消息傳輸數(shù)量.假設(shè)僅需要傳輸m'=m-1 條消息，就可以保證消息成功被更新分片接收.當(dāng)nt≥nu時(shí)，將Nu中的節(jié)點(diǎn)分為P1和P2兩部分，將收到消息數(shù)量最多的前fu個(gè)節(jié)點(diǎn)劃入P1中，其余的nu-fu個(gè)節(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 時(shí)，可以得到mP1=qfu-v0 時(shí)，有mP1=qfu+fu-v<（q+1）fu和mP2=q（nu-fu）+r+v-1 >q（nu-fu），這意味著在P1中至少存在一個(gè)最多收到q條消息的節(jié)點(diǎn)，在P2中至少存在一個(gè)收到了q+1 條消息的節(jié)點(diǎn).由此可知，在P2中至少存在一個(gè)節(jié)點(diǎn)，使其收到的消息數(shù)量比P1中某個(gè)節(jié)點(diǎn)更多，這與P1劃分規(guī)則相悖.因此，證明mP1≥qfu+fusgnr和mP2≤q（nu-fu）+r-1成立.

由于更新節(jié)點(diǎn)中誠(chéng)實(shí)節(jié)點(diǎn)至少要收到2ft+1 條消息才能保證更新分片不會(huì)被傳輸分片欺騙，所以有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條，無(wú)法收到來(lái)自誠(chéng)實(shí)節(jié)點(diǎn)的ft+1 條消息.因此，m′的假設(shè)是不成立的.證畢.

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

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

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

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

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

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

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

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

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

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

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

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

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

Fig.5 Workflow of block storage and reconfiguration圖5 區(qū)塊存儲(chǔ)與重構(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)的惡意攻擊.舉例來(lái)說(shuō)，拜占庭節(jié)點(diǎn)可能會(huì)向更新節(jié)點(diǎn)發(fā)送錯(cuò)誤的讀集，導(dǎo)致不同節(jié)點(diǎn)在執(zhí)行相同的跨片交易時(shí)視圖不一致.為了確保系統(tǒng)一致性，執(zhí)行節(jié)點(diǎn)需要重新執(zhí)行特定的交易集，以達(dá)到正確和一致的結(jié)果.此外，重新執(zhí)行的順序應(yīng)該遵循共識(shí)協(xié)議確認(rèn)的順序.

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

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

2.4 安全性分析

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

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

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

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

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

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

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

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

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

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

Fig.7 Conflict graph圖7 沖突圖

Table 2 Transaction Table表2 交易集表

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

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

輸入：帶有交易序號(hào)的交易隊(duì)列Btxs；

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

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

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

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

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

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

輸入：一筆交易T，一個(gè)交易子集S；

輸出：一個(gè)布爾值Bool.

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

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

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

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

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

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

輸入：交易子集集合TSS，帶有交易序號(hào)的交易隊(duì)列Itxs；

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

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

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

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

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

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

輸入：一批交易B.

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

4 實(shí)驗(yàn)與結(jié)果

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

4.1 實(shí)驗(yàn)環(huán)境

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

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

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

4.2 測(cè)試負(fù)載

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

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

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

4.3.1 系統(tǒng)吞吐量

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

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

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

4.3.2 交易延遲

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

Fig.11 Transaction latency圖11 交易延遲

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

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

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

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

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

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

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

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

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

4.4 交易重排序方法性能

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

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

圖14 和圖15 分別展示了傳統(tǒng)排序鎖機(jī)制在面對(duì)不同沖突率和不同沖突類(lèi)型時(shí)的表現(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ī)制的跨片沖突下的吞吐量

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

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

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

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

圖16 展示了排序鎖機(jī)制在引入交易重排序策略后，系統(tǒng)在處理片內(nèi)交易沖突時(shí)的性能，其中吞吐比為引入交易重排序方案的吞吐量和基于排序鎖方案的吞吐量的比值.在高沖突的交易負(fù)載下，系統(tǒng)可以利用8 個(gè)工作線程來(lái)達(dá)到41 000 TPS 的吞吐量.與執(zhí)行無(wú)沖突的交易集相比，采用交易重排序方法的系統(tǒng)在處理高沖突交易集的表現(xiàn)依舊出色，其吞吐量降低了不到10%.不難發(fā)現(xiàn)，交易重排序方案通過(guò)將交易的順序進(jìn)行調(diào)換來(lái)增加交易執(zhí)行的并發(fā)度，縮短了交易的阻塞時(shí)間.此外.根據(jù)交易子集劃分算法，鎖線程還可以并行給同一個(gè)交易子集內(nèi)部的交易上鎖，突破了單點(diǎn)瓶頸問(wèn)題.如此一來(lái)，盡可能多的交易能夠通過(guò)交易重排序機(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í)的性能，其中吞吐比為引入交易重排序方案的吞吐量和基于排序鎖方案的吞吐量的比值.實(shí)驗(yàn)數(shù)據(jù)表明，引入重排序方案的系統(tǒng)在處理跨片交易沖突時(shí)表現(xiàn)依然優(yōu)秀.在采用4 個(gè)工作線程的條件下，系統(tǒng)的吞吐量基本維持在20 000 TPS 左右，并且不會(huì)因負(fù)載的變化而大幅度下降.與片內(nèi)交易不同，在處理跨片交易中，交易執(zhí)行并發(fā)度越高，越多的跨片交易可以有效地利用帶寬將狀態(tài)數(shù)據(jù)更加迅速地發(fā)送到更新分片上，提高跨片交易的執(zhí)行效率.但是在8 個(gè)工作線程的情況下，處理跨片沖突的性能略低于處理片內(nèi)沖突的性能.這是因?yàn)榇藭r(shí)整個(gè)系統(tǒng)的性能瓶頸已從線程數(shù)量轉(zhuǎn)移到了執(zhí)行跨片交易時(shí)的狀態(tài)傳輸上，系統(tǒng)已經(jīng)無(wú)法通過(guò)增加工作線程數(shù)量來(lái)提高吞吐量，唯有通過(guò)對(duì)狀態(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 針對(duì)跨片交易的重排序優(yōu)化策略

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

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

5 總結(jié)

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

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