李光程，趙慶林，謝 侃

（1. 澳門科技大學 資訊科技學院，澳門 999078；2. 廣東工業(yè)大學 自動化學院，廣東 廣州 510006）

當前，集中式框架已被大多數(shù)數(shù)據(jù)處理平臺(例如，MapReduce[1]，storm[2]，flink[3])廣泛采用，在該平臺中，主節(jié)點集中控制和管理多個從節(jié)點。但是，這種集中式框架通常具有以下缺點：(1) 主節(jié)點中出現(xiàn)單點故障或瓶頸[4-5]；(2) 擴展集群規(guī)模的維護成本高[3]；(3) 集群達到一定規(guī)模時的吞吐量可伸縮性問題。在大數(shù)據(jù)時代，隨著高并發(fā)的實時流媒體數(shù)據(jù)處理的增加，上述問題變得越來越嚴重。因此，一個根本的解決方案是采用去中心化的框架。

最初設計用于記錄交易的區(qū)塊鏈[6]被認為是一種新的去中心化計算框架，具有很大的潛力來滿足各種計算需求。在這種去中心化的框架中，沒有中心實體，所有節(jié)點都是等效的參與者，并通過共識機制共同維護交易的一致性[7]。去中心化的本質(zhì)允許無限的計算節(jié)點加入?yún)^(qū)塊鏈系統(tǒng)，因此該系統(tǒng)能夠聚合巨大的計算資源。例如，早在2013年，比特幣網(wǎng)絡[7]就已經(jīng)比前500名超級計算機的總和強大[8]。區(qū)塊鏈的去中心化特征和聚集的巨大計算資源是解決集中式框架的上述缺點所迫切需要的。

不幸的是，在主流的區(qū)塊鏈系統(tǒng)中，例如比特幣[7]和以太坊[9]，巨大的計算資源主要消耗在共識機制中，例如工作量證明(Proof of Work, PoW)，而不是解決有意義的實際問題(如統(tǒng)計流媒體視頻中的汽車數(shù)量)。因此，提出了有用工作證明(Proof of Useful Work, PoUW)[10]，以克服PoW的缺點，其目的是讓這些計算資源解決實際問題，同時也達成共識。PoUW向前邁進，利用這些潛在的巨大計算資源進行有意義的數(shù)據(jù)處理。然而，要使用區(qū)塊鏈進行數(shù)據(jù)處理，一項挑戰(zhàn)是改造用于去中心化數(shù)據(jù)處理的交易記錄區(qū)塊鏈。本文致力于解決這一挑戰(zhàn)。

在本文中，對于不需要激勵機制且可以忽略網(wǎng)絡延遲的私有網(wǎng)絡(如數(shù)據(jù)中心)，本文改造了用于交易記錄的區(qū)塊鏈框架，使其成為具有去中心化控制的數(shù)據(jù)處理框架。也就是說，本文提出了一個基于區(qū)塊鏈的去中心化數(shù)據(jù)處理框架。在所提框架中(如圖1所示)，采用PoUW共識的區(qū)塊鏈存儲任務交易。每個區(qū)塊鏈節(jié)點扮演3個角色：task manager(任務管理器)、worker(工作者)和scheduler(調(diào)度器)。task manager從數(shù)據(jù)源收集原始數(shù)據(jù)；worker首先從區(qū)塊鏈中選擇任務并從task manage下載任務，然后在本地處理它們并將結(jié)果返回給結(jié)果收集器，之后執(zhí)行PoUW以競爭成為scheduler的角色；scheduler將任務信息分發(fā)到區(qū)塊鏈中。最后，通過模擬驗證了該框架的有效性。在系統(tǒng)吞吐量和任務響應時間方面，本文提出的框架優(yōu)于傳統(tǒng)的基于主/從的框架。同時，本文的解決方案實現(xiàn)了與基于主/從的框架類似的公平性。

圖1 所提出的去中心化數(shù)據(jù)處理方案Fig.1 The proposed blockchain-based data processing framework

1 相關工作

本文提出了一種基于區(qū)塊鏈的去中心化框架，用于公平數(shù)據(jù)處理。它涉及以下2個方面的相關工作。

(1) 數(shù)據(jù)處理框架。基于主/從的集中式框架已在大多數(shù)數(shù)據(jù)處理平臺(例如MapReduce[1]、flink[3])中廣泛采用，但它容易受到單點故障、性能瓶頸等的影響。這些缺點已引起人們的廣泛關注。例如，文獻[5]提出了一種熱備份機制來解決單點故障(即建立一個備份節(jié)點來接管發(fā)生故障的主節(jié)點)。文獻[11]提出了一種分層的主/工作器范式(Hierarchical Master-Worker，HMW)，以克服主節(jié)點的性能瓶頸。但是，所有這些改進都關注集中式框架。一個基本的解決方案是采用本文所述的去中心化框架。在去中心化框架中，所有節(jié)點都是設備參與者，因此永遠不會發(fā)生單點故障。此外，該去中心化式系統(tǒng)易于大規(guī)模擴展，因此在性能(如吞吐量和安全性)以及硬件升級方面具有良好的可伸縮性。

(2) 區(qū)塊鏈應用。區(qū)塊鏈天然具有去中心化功能，因此受到越來越多的關注。例如，文獻[12]為眾包提供了一個基于區(qū)塊鏈的去中心化框架，使請求者的任務可以由一群worker來解決，而無需依賴任何第三方信任的機構(gòu)。文獻[13]研究了基于邊緣輔助的區(qū)塊鏈的IoT，并建議使用基于信用的支付方式進行快速計算資源交易。文獻[14]提出了一種用于車輛網(wǎng)絡的基于區(qū)塊鏈的去中心化式信任管理系統(tǒng)。文獻[15]將區(qū)塊鏈用于隱私保護，而用戶則在陌生人之間共享信息。與上述工作不同，本文首次重塑區(qū)塊鏈進行數(shù)據(jù)處理。這項研究有助于更好地設計通用的去中心化計算框架，以滿足各種計算需求。

2 數(shù)據(jù)處理框架

本節(jié)主要介紹用于私有數(shù)據(jù)中心的基于區(qū)塊鏈的數(shù)據(jù)處理框架。

在所提出的的框架中(如圖1所示)，底層區(qū)塊鏈P2P網(wǎng)絡由云/邊緣節(jié)點組成。每個節(jié)點作為一個task manager(任務管理器)，從數(shù)據(jù)源接收原始數(shù)據(jù)并將其組織成任務，其中每個任務(即最細粒度的可處理數(shù)據(jù)單元)被分配一個全局唯一的ID，并可以通過統(tǒng)一資源定位器(Uniform Resource Locator, URL)進行訪問。屬于同一服務的任務可被視為一種類型的任務，它們具有相同的屬性(即資源需求、處理時間消耗、到達率)。

這些節(jié)點在充當worker或scheduler時，將通過PoUW共識機制[10]共同創(chuàng)建和維護區(qū)塊鏈，每個區(qū)塊都存儲著待處理/處理中/完成的任務交易。也就是說，每個worker不斷從區(qū)塊鏈中選擇待處理的任務交易，然后在本地處理相應的任務；在完成一個任務后(即完成一定量的有用工作)，每個worker首先計算其執(zhí)行的CPU指令的數(shù)量，作為完成有用工作的證明，然后依數(shù)量競爭成為scheduler的資格。成為scheduler后，節(jié)點將從task manager那里收集待處理的任務交易，從worker那里收集處理中/完成的任務交易，然后將它們發(fā)布到區(qū)塊鏈上。

下面，將依次詳細介紹區(qū)塊鏈交易、scheduler和worker的功能，以及系統(tǒng)的工作流程。

2.1 區(qū)塊鏈交易

在區(qū)塊鏈中區(qū)塊被用來存儲任務交易，其中任務交易設定了一個任務的概況(如ID和類型)。如圖2(a)所示，每個區(qū)塊由2部分組成：區(qū)塊頭和區(qū)塊體。

圖2 區(qū)塊的數(shù)據(jù)結(jié)構(gòu)和示例Fig.2 The data structure of a block and a block sample

區(qū)塊頭用于識別區(qū)塊鏈上的一個特定區(qū)塊，由以下字段組成。

(1) hashPrevBlock：上一個區(qū)塊的區(qū)塊頭的哈希，通過它可以將此區(qū)塊連接到上一個區(qū)塊。

(2) time：當前區(qū)塊的生成時間(時間戳)。

(3) diff：worker在執(zhí)行PoUW算法時獲勝的難度系數(shù)(在算法1中進行了解釋)。它控制區(qū)塊鏈的區(qū)塊生成速率，并且可以定期調(diào)整以穩(wěn)定該速率。

(4) PoUW：worker在執(zhí)行PoUW算法時獲勝的憑證。有效的PoUW包含有關采礦成功的有用工作程序證明，以及該程序符合性檢查的證明。

(5) hashBody：此區(qū)塊的區(qū)塊體部分的哈希，worker可利用此哈希驗證區(qū)塊體的正確性和完整性。

(6) transNum：包含在此區(qū)塊中的交易數(shù)

區(qū)塊主體存儲任務交易。每個任務由其task manager分配一個全球唯一的ID。例如，假設有3個task manager：001、002和003。這些task manager分配的任務ID可以是001109、002087、003272。每個任務(以及每個任務事務)都有3種狀態(tài)：待處理、處理中和完成。每個worker將根據(jù)任務屬性和它的可用資源來選擇和處理任務。每當一個worker選擇或完成一項任務時，它將創(chuàng)建相應的任務交易。在收到這些交易后，其他worker將更新其本地任務列表中相應任務的狀態(tài)，而scheduler將把這些交易收集到其新創(chuàng)建的區(qū)塊中，新區(qū)塊將被鏈接到區(qū)塊鏈上。

一個待處理的任務交易用來通知worker哪個任務需要被處理。它由以下字段組成。

(1) taskID：任務的唯一ID。

(2) taskState：其值設置為“ pending”，表示此任務需要處理。

(3) taskType：代表任務服務類型的整數(shù)。每種任務的處理流程、到達率、資源需求(例如CPU內(nèi)核、內(nèi)存、網(wǎng)絡帶寬)和處理時間都相同。

(4) srcURL：任務的URL，用于下載任務數(shù)據(jù)。

(5) fairIndex：一個正數(shù)，指示處理任務以實現(xiàn)某些公平性標準的順序。如果系統(tǒng)希望確保不同任務類型之間的處理公平性，則應按公平指數(shù)的升序處理所有任務。

處理中任務交易用于聲明正在處理的任務。它由以下字段組成。

(1) taskID：任務的唯一ID。

(2) taskState：其值設置為“processing”，表示該任務正被處理。

(3) blockHeight：該任務的待處理交易所處區(qū)塊的高度。如果在超時后該任務仍未完成，則worker可以找到hight = blockHeight的塊，并獲取任務的srcURL進行重新處理。例如，假設blockHeight = 10。一旦任務超時，worker將找到第10個塊并訪問相應的待處理任務交易。

(4) workerID：選擇該任務的worker的ID。

(5) selectedTime：該任務被選擇并開始處理的時間。根據(jù)selectedTime和當前時間，worker可以推斷該任務的處理是否已超時。

已完成的任務交易用于聲明已經(jīng)完成的任務。它包含以下字段：

(1) taskID：任務的唯一ID。

(2) taskState：其值設置為“ completed”，表示任務已完成。

(3) blockHeight：該任務的待處理交易所處區(qū)塊的高度。

(4) workerID：完成該任務的worker的ID。

圖2(b)顯示了一個區(qū)塊的例子，其中有2個待處理的任務交易，1個正在處理的任務交易和2個已完成的任務交易。

2.2 worker(工作者)

在所提出的去中心化框架中，每個worker主動從區(qū)塊鏈上選擇和下載任務，然后在本地處理，而不是像中心化框架那樣被動地接收任務。每個worker不斷將其本地區(qū)塊鏈與系統(tǒng)的區(qū)塊鏈同步。在收到一個新的區(qū)塊后，worker將進行以下3個操作。

(1) 選擇任務。首先，每個worker更新自己的可選擇任務表，例如，添加待處理任務，標記處理中任務，刪除已完成的任務。然后，它調(diào)用一個任務選擇方案，根據(jù)一些標準(如處理公平性)選擇任務。接著，它把選擇的任務廣播給P2P網(wǎng)絡。當收到這些廣播信息時，其他worker會選擇其他任務，而下一個scheduler將為每個被選中的任務創(chuàng)建一個處理中任務交易(這意味著這個任務已經(jīng)被選中并在處理中)，并將其記錄到一個新的區(qū)塊中，一旦發(fā)現(xiàn)這個任務的相關信息被下載，相應的task manager將改變每個被選中任務的狀態(tài)(從待處理到處理中)。

(2) 處理任務。下載選定的任務后，該worker在本地處理這些任務(例如，計算一個小視頻中的汽車數(shù)量)。請注意，根據(jù)PoUW共識的要求，任務應該在可信執(zhí)行環(huán)境(Trusted Execution Environment，TEE)[16-17]中處理，例如Intel SGX[18]，以防止惡意worker報告虛假的工作量。當完成一個任務時，worker會計算處理該任務所執(zhí)行的CPU指令的數(shù)量，并將任務的結(jié)果發(fā)送給收集器，最后將完成此任務的信息廣播給P2P網(wǎng)絡。

(3) 競選scheduler。每當一個worker完成一個任務，它將執(zhí)行PoUW共識，通過運行算法1來競選scheduler。讓m代表完成一個任務所執(zhí)行的CPU指令數(shù)，讓d代表區(qū)塊鏈的當前難度系數(shù)。在這個算法中，worker生成一個隨機數(shù)nonce(第4行)，然后檢查nonce是否滿足與m和d有關的不等式(第5行)。如果是，競爭結(jié)果 win被設置為1，表示該worker在競選中獲勝，因此將成為scheduler；否則， win被設置為0，表示該worker將不改變其角色。

2.3 scheduler(調(diào)度器)

當一個worker在競爭中獲勝時，它將充當scheduler。在任何時候，系統(tǒng)只有一個scheduler。scheduler將執(zhí)行以下2個操作。

(1) 創(chuàng)建待處理任務交易。scheduler首先從任務池中收集新到達的任務的配置文件。然后，它通過調(diào)度算法計算每個新任務的fairIndex，最后創(chuàng)建待處理的任務交易。去中心化的調(diào)度算法是我們未來的研究工作。

(2) 創(chuàng)建并分發(fā)區(qū)塊。scheduler首先構(gòu)造一個塊體。在此主體中，它打包了3種類型的任務交易：新創(chuàng)建的待處理任務交易、收集的處理中任務交易和已完成的任務交易(由worker廣播)。然后，構(gòu)造一個包含PoUW的塊頭。之后，通過將塊頭拼接到主體上來創(chuàng)建一個新塊，最后將新塊廣播到區(qū)塊鏈P2P網(wǎng)絡。

2.4 工作流程

基于區(qū)塊鏈的數(shù)據(jù)處理方案的工作流程如圖3所示。

圖3 本文所提去中心化系統(tǒng)的工作流程Fig.3 The workflow of the decentralized system

(1) 一個worker不斷地與其他worker同步其區(qū)塊鏈狀態(tài)，并更新其本地任務表。

(2) 它根據(jù)任務選擇方案從其本地任務表中選擇待處理任務，然后從task manager中提取選定的任務，最后將其選擇廣播到P2P網(wǎng)絡。

(3) 該worker處理所選任務。

(4) 每當一個任務完成后，它就會報告數(shù)據(jù)處理結(jié)果，然后執(zhí)行PoUW共識(在算法1中解釋)以競選scheduler。如果獲選，該節(jié)點將從worker轉(zhuǎn)變?yōu)閟cheduler；否則，它將返回到第(1)步，繼續(xù)處理任務。

(5) scheduler從所有task manager中收集新到達的任務。

(6) scheduler執(zhí)行任務調(diào)度算法以計算所有新到達的任務的公平指數(shù)。

(7) scheduler創(chuàng)建一個新區(qū)塊(包括待處理，處理中和已完成的任務交易)，并將新塊分發(fā)到P2P網(wǎng)絡。

3 評估

本節(jié)通過廣泛的模擬以評估本文的設計。在模擬中從系統(tǒng)吞吐量、響應時間和公平性方面比較了以下3個框架。

(1) Decentralization。這是本文件提出的框架。

(2) M/S。這是一個基于主/從結(jié)構(gòu)的數(shù)據(jù)處理框架，主節(jié)點安排和分配任務給worker。一個主節(jié)點有12個資源份額，每個資源份額能夠安排或分配15個任務/單位時間。

(3) M/S-failure。它也使用了一個基于主/從結(jié)構(gòu)的框架。主節(jié)點會在一個隨機的時間內(nèi)失敗一次，在此期間它不能安排和分配任務，但worker可以繼續(xù)處理已經(jīng)獲得的任務。主節(jié)點將在10個單位時間后恢復。

在模擬中，固定任務屬性，并改變worker的數(shù)量。假設任務的到達率遵循泊松分布，當一個任務被處理時，它需要占用worker的一部分資源并消耗一些時間。默認參數(shù)設置見表1。表1列出了8類任務的屬性和5種類型的worker的屬性。例如，當“worker類型”為1時，“類型1的worker數(shù)量”被設置為“5∶5∶50”。這里，“5∶5∶50”中的第二個參數(shù)5代表了步長。因此，“5∶5∶50”表示將第一類worker的數(shù)量從5以步長5依次增加到50。這相當于一個模擬序列，所有類型的worker總數(shù)從25、50、75、···增加到250，在圖4、圖5和圖6的x軸上標出。每個模擬值是3次模擬運行的平均值，每次運行持續(xù)時間為1 200個時間單位。

表1 默認參數(shù)設置Table 1 Default parameter settings

本文用單位時間內(nèi)的原子任務數(shù)來衡量吞吐量。原子任務指只需要消耗1份資源且能在1個單位時間內(nèi)完成的任務。

圖4繪制了當worker數(shù)量從50到250變化時的系統(tǒng)吞吐量。從圖中可看到本文的方案的吞吐量總是高于方案M/S和M/S-failure。當worker數(shù)量達到175人時，方案M/S和M/S-failure的主節(jié)點就會出現(xiàn)性能瓶頸。因此，M/S和M/S-failure的系統(tǒng)吞吐量不再隨著worker數(shù)量的增加而增加。

圖4 系統(tǒng)吞吐量與worker數(shù)量關系Fig.4 Relation of system throughput and number of workers

響應時間是指從任務生成到開始由worker處理的時間。響應時間越短，任務的處理就越及時。圖5描繪了worker數(shù)量從25到250變化時的響應時間。從圖中可看到，當worker數(shù)量少于150時，3種方案的響應時間幾乎相同，并且隨著worker數(shù)量的增加而幾乎線性下降。當worker數(shù)量超過150人時，本文方案的響應時間下降得更快。由于主節(jié)點的瓶頸，當worker數(shù)量超過175時，M/S和M/S-failure的響應時間不再變化。

圖5 響應時間與worker數(shù)量的關系Fig.5 Relation of response time and number of workers

在模擬中，通過Jain公平指數(shù)(Jain's Fairness Index)來衡量實現(xiàn)的公平性，其計算方法為

圖6比較了Decentralization，M/S和M/S-failure之間的Jain公平指數(shù)。從圖中可看到，去中心化框架的公平性總是低于2個中心化框架的公平性。這是因為在去中心化框架中，沒有一個主節(jié)點來分配任務，worker自己從區(qū)塊鏈上選擇任務來處理。因此，公平性不能得到很好的保證。

圖6 Jain公平指數(shù)與worker數(shù)量的關系Fig.6 Relation of Jain's indexas and number of workers

4 結(jié)論

傳統(tǒng)的集中式數(shù)據(jù)處理框架易受單點故障和性能瓶頸的影響。為了解決這些缺點，本文提出使用去中心化的數(shù)據(jù)處理框架重塑流行的區(qū)塊鏈。在公共區(qū)塊鏈中，工作量證明(PoW)共識消耗大量計算資源，主要是為了競爭領導者，而不是解決有意義的實際問題。為了避免浪費大量資源，在本文所提出的框架中，PoUW共識代替了PoW，并讓區(qū)塊鏈存儲任務信息。通過執(zhí)行PoUW，節(jié)點可以從區(qū)塊鏈中選擇和處理任務，同時競爭負責將待處理任務分配給區(qū)塊鏈的領導者。仿真證明本文所提出的框架可以很好地實現(xiàn)設計目標。這項研究有助于更好地設計通用的去中心化計算框架，以滿足各種計算需求。將來，我們將擴展所提出的框架，使其適用于高吞吐量的區(qū)塊鏈協(xié)議，例如Bitcoin-NG[19]，ELASTICO[20]和RapidChain[21]。