溫宇強 邵孟良

摘要：本文提出的基于廣播信道的分布式事務(wù)處理方法，該方法在廣域網(wǎng)環(huán)境下仍然適用且高效。相比于基于消息傳遞的分布式事務(wù)處理的算法，針對某類分布式問題，在滿足ACID（ Atomicity.Consistency.lsolation，Durability）條件下，本文通過實例展示基于廣播信道的分布式事務(wù)處理方法在處理某類分布式問題時的優(yōu)勢：計算量通信量減少，系統(tǒng)擴展性增強，算法調(diào)試簡單。

關(guān)鍵詞：分布式計算;事務(wù)處理;廣播信道

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2020）18-0001-04

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

1 引言

在分布式系統(tǒng)中，為了提高數(shù)據(jù)的可用性，增強系統(tǒng)的擴展性，數(shù)據(jù)經(jīng)通過存儲多份的方式來實現(xiàn)系統(tǒng)能力的擴展。然而，一些異常情況將導(dǎo)致數(shù)據(jù)出現(xiàn)不一致性，因此高可用事務(wù)處理系統(tǒng)的并發(fā)控制在可擴展性、副本恢復(fù)和單點性能等方面面臨著諸多挑戰(zhàn)?；谙鬟f的共識協(xié)議算法，對消息傳遞的質(zhì)量和延時是非常敏感的。在一個數(shù)據(jù)中心的環(huán)境下，節(jié)點之間的網(wǎng)絡(luò)通信質(zhì)量和帶寬是有保證的。所以這些算法多用于一個數(shù)據(jù)中心內(nèi)，或僅用于通過廣域網(wǎng)連接的少數(shù)節(jié)點。

在Internet應(yīng)用情況下，我們需要處理的分布式計算任務(wù)往往是地理上非常分散的節(jié)點參與的。由于網(wǎng)絡(luò)環(huán)境的不穩(wěn)定性和復(fù)雜性，如果使用現(xiàn)有的基于消息的共識算法，在執(zhí)行效率和系統(tǒng)可用性等方面會遇到極大挑戰(zhàn)。

本文提出的基于廣播信道的分布式事務(wù)處理方法，是在廣域網(wǎng)環(huán)境下仍然適用且高效。在同一個數(shù)據(jù)中心的這種環(huán)境下，找到合適的廣播媒介（比如：基于DTMB技術(shù)的廣播信道），相比于基于消息傳遞的分布式事務(wù)處理的算法，仍有系統(tǒng)處理簡單高效的優(yōu)勢。

2 基于廣播信道的系統(tǒng)模型

針對分布式事務(wù)處理，學(xué)者們提出了多種解決分布式事務(wù)處理問題的算法，即共識協(xié)議算法。比如：兩階段提交（2PC）[1]，三階段提交（3PC）[2]，Paxos算法[3]，Raft算法[4]或ZAB算法[5]。這類算法以應(yīng)用于數(shù)據(jù)中心環(huán)境下，而Internet的網(wǎng)絡(luò)環(huán)境，比數(shù)據(jù)中心的網(wǎng)絡(luò)環(huán)境要更不可控。盡管現(xiàn)有業(yè)界提出了一些web服務(wù)環(huán)境下的事務(wù)組合及控制，例如google的chubbv[6]以及Apache的ZooKepper[7]，他們都使用復(fù)制狀態(tài)機來為少量配置數(shù)據(jù)提供鍵值（Key-Value）存儲。這類復(fù)制狀態(tài)機系統(tǒng)通常只由3個或5個服務(wù)器組成。但Web環(huán)境下的分布式計算問題需要更大的規(guī)模，目前仍存在多方面的挑戰(zhàn)。

面對Internet環(huán)境，若采用分而治之的方案，比如：

在這些系統(tǒng)中，需要在待處理的問題中有可以進(jìn)行分層或分塊到較小的系統(tǒng)中數(shù)據(jù)。但如果系統(tǒng)中某些數(shù)據(jù)就是全系統(tǒng)唯一的，所有子系統(tǒng)都會用到的數(shù)據(jù)，系統(tǒng)分層或分塊處理都會導(dǎo)致這類數(shù)據(jù)的一致性（ACID）受到破壞。所以可能不得不在廣域網(wǎng)下使用基于消息的共識協(xié)議算法。而廣域網(wǎng)環(huán)境下，共識協(xié)議算法還不能在大規(guī)模系統(tǒng)上應(yīng)用。

然而利用作者提出的信道異構(gòu)CDN（ CHCND）系統(tǒng)架構(gòu)[8]，針對分布式事務(wù)處理中，共享數(shù)據(jù)可累計的更新，且只有總量變化會對業(yè)務(wù)邏輯產(chǎn)生影響，而操作順序并無要求的操作。例如：電子購物系統(tǒng)，電子訂票系統(tǒng)等的某些類型數(shù)據(jù)更新。本文提出了一種分布式事務(wù)處理方法，可以有效解決數(shù)據(jù)副本更新問題，使得這類系統(tǒng)的事務(wù)更有效率。系統(tǒng)結(jié)構(gòu)如圖1。

本文利用CHCDN系統(tǒng)的傳輸效率高的特性，將共享數(shù)據(jù)通過中心節(jié)點進(jìn)行事務(wù)更新，再通過廣播信道進(jìn)行副本更新。分布處理節(jié)點在數(shù)據(jù)需要更新時，將逐級匯總，最后在中心節(jié)點完成數(shù)據(jù)更新，我們稱此方案為信道異構(gòu)共識協(xié)議。針對某些類型的分布式事務(wù)處理，異構(gòu)共識協(xié)議可以更加有效率。

3 信道異構(gòu)共識協(xié)議

結(jié)合廣播信道通信的優(yōu)勢，我們提出的信道異構(gòu)共識協(xié)議如下：

算法所有參與方都是節(jié)點Ni，i∈[0，n]，運行算法之初，對Ni.產(chǎn)生一個節(jié)點的偏序集Pi，i∈[0，n]。Pi的選擇都是根據(jù)具體應(yīng)用來定義的。其中的第一個服務(wù)器PO便是主服務(wù)器，其他服務(wù)器成為從服務(wù)器。中心節(jié)點為C，C可以把數(shù)據(jù)發(fā)送到廣播信道傳輸。偏序集合的依據(jù)有很多種，比如：以節(jié)點P2到中心節(jié)點C的雙向點對點網(wǎng)絡(luò)（可以是WAN網(wǎng)絡(luò)）的延遲，作為產(chǎn)生偏序集合的依據(jù)。P0對只提供服務(wù)，最終客戶通過P2獲取服務(wù)器，其中Pi，i∈[0，n]。另外，c可以是只中的一員，也可以是一個獨立的節(jié)點。只都可以與P0通過點對點網(wǎng)絡(luò)通信。Po可以通過點對點網(wǎng)絡(luò)與C通信。系統(tǒng)初始化時統(tǒng)計出

對于要通過分布式系統(tǒng)更新的數(shù)據(jù)項，算法引入廣播變量類型，其狀態(tài)有：fboardcast-read.boardcast-lock），同時還有更新版本號boardcast_revision，數(shù)據(jù)項的更新版本號會隨著數(shù)據(jù)更新提交的次數(shù)變化，為敘述方便，我們假設(shè)變量更新版本號從0開始遞增。廣播變量類型的屬性，都存儲在主服務(wù)器PO上。其他節(jié)點會通過廣播信道得到對應(yīng)數(shù)據(jù)項的更新狀態(tài)。則在只系統(tǒng)中，要更新的數(shù)據(jù)便有了廣播變量類型。其值在Pi系統(tǒng)中，對Pi中的應(yīng)用程序為只讀的屬性。通過廣播信道，可以實現(xiàn)所有節(jié)點的系統(tǒng)時間統(tǒng)一，并且這個時間精度可以足夠用于分布式事務(wù)的先后區(qū)分。如果有相同的兩個更新請求的時間戳一樣，則再利用節(jié)點的排序，人為定義相同時間戳的更新請求先后次序。

系統(tǒng)事務(wù)處理具體處理流程如下，算法1：

Stepl節(jié)點Pi發(fā)出數(shù)據(jù)的修改請求，通過點對點網(wǎng)絡(luò)，請求送達(dá)PO。

PI中對于狀態(tài)為boardcast-read的數(shù)據(jù)項，只若要執(zhí)行數(shù)據(jù)更新的操作，則節(jié)點Pi需通過點對點網(wǎng)絡(luò)提交該數(shù)據(jù)項的更新請求給P0，請求信息帶有時間戳，以及當(dāng)前數(shù)據(jù)項的更新版本號boardcast_revision=Vi。

Step2 Po在接到對某廣播類型變量boardcasLrevision=Vi的第一個更新請求后，通知C，C通過廣播信道把對應(yīng)數(shù)據(jù)項的狀態(tài)變?yōu)閎oardcast-lock的消息發(fā)送出去.廣播信道發(fā)送出去該消息的當(dāng)前時間戳為to.

to+ TB時間過后，所有的節(jié)點都應(yīng)收到這個消息，并把系統(tǒng)內(nèi)對應(yīng)的數(shù)據(jù)項的狀態(tài)由boardcast-read變?yōu)閎oardcast-lock。則此時以后的對此數(shù)據(jù)的修改請求將會視為無效。這些有效的boardcast_revision=Vi更改請求中，最遲會到達(dá)PO的時間為Tmax;io，如果超過了這個時間到達(dá)，也視為無效數(shù)據(jù)，并且會根據(jù)到達(dá)時間修訂Tmax：i-0，具體修訂算法不屬于本文討論的內(nèi)容。

所以，Po對boardcast_revision=K時間標(biāo)簽為to+ TB+ Tmax：io以后的數(shù)據(jù)提交請求，以及，boardcast_revi-sion=Vi但是在t0+TB+Tmax：i-0以后才到達(dá)的數(shù)據(jù)更新請求都會忽略。

PO收到有效的的更新請求，順序進(jìn)行處理。其他的處理可以并行：返回結(jié)果給對應(yīng)的節(jié)點;對無效的數(shù)據(jù)請求，直接給節(jié)點返回對應(yīng)的錯代碼;發(fā)送結(jié)果的反饋，使用的是點對點網(wǎng)絡(luò)。

假設(shè)順序處理完當(dāng)前時間窗內(nèi)的有效更改需求后，分兩步提交這個數(shù)據(jù)項的持久化存儲：

Step2.1，PO將結(jié)果在持久化系統(tǒng)中（數(shù)據(jù)庫）更新，并設(shè)置新的boardcast_revision=Vi+i，并發(fā)送更改后的數(shù)據(jù)項給C，C通過廣播信道發(fā)送對應(yīng)數(shù)據(jù)項的更新信息。從t0+TB+Tmax：i-0開始處理更新請求到C收到更改后的數(shù)據(jù)值并把值更新消息發(fā)送到廣播信道，耗時為g;

Step2.2，當(dāng)PO收到廣播信道中的數(shù)據(jù)更改信息，時刻為to+ 2TB+Tmax：i-0 +9，執(zhí)行持久化系統(tǒng)的更新確認(rèn)。

由于數(shù)據(jù)更新的請求多數(shù)是值更新類的請求，所以批量處理在一定時間間隔內(nèi)的更新請求，有合并對同一變量的操作的可能，而減輕數(shù)據(jù)庫持久化的1/0壓力。提高系統(tǒng)的響應(yīng)速度。

同理只節(jié)點也會在tc）+ '2TB+Tmax：t一0+g時刻收到廣播更新信息，數(shù)據(jù)項狀態(tài)則由boardcast-lock轉(zhuǎn)化為boardcast-read，boardcasLrevision也做相應(yīng)的更新，所以白t0+2TB+ Tmaxi-0+g開始的數(shù)據(jù)請求將會是有效的，對應(yīng)的數(shù)據(jù)項更新請求將是boardcasLrevision=Vi+1

Step3只節(jié)點通過廣播信道接收數(shù)據(jù)庫的更新，對比自己的數(shù)據(jù)庫中的條目，進(jìn)行更新。某些條目也許不在本節(jié)點的數(shù)據(jù)庫中，則不用管。某些更新失敗的節(jié)點，需要重新檢查廣播數(shù)據(jù)項的狀態(tài)，再提交新的更新請求。

Step4提交新的請求即重復(fù)上面的1-3的過程。

本系統(tǒng)數(shù)據(jù)更新最小間隔Tsp，也就是響應(yīng)速度為。Trsp與分布式系統(tǒng)的規(guī)模無關(guān)，有下列關(guān)系：TB是基于系統(tǒng)所選擇的廣播信道而決定的，其值為：TB=電磁信號在空中傳播時間+調(diào)制解調(diào)時間

如果選擇同步衛(wèi)星，則TB大概是0.27秒;如果選擇低軌道衛(wèi)星，TB則很小大概是同步衛(wèi)星的1/36-1/6;若采用高空氣球或高空無人機作為信號中繼，則B的值更小。（ ）與（ ）的值有賴于分布式系統(tǒng)節(jié)點間的網(wǎng)絡(luò)環(huán)境，系統(tǒng)在運行過程中可以動態(tài)監(jiān)控這些值;g是PO處理時間窗內(nèi)請求需要的時間。所以，本算法的系統(tǒng)的可用性是有保證的。

對應(yīng)上面的系統(tǒng)事務(wù)處理流程流程，Pi節(jié)點內(nèi)的處理流程描述如下：

假設(shè)Data為我們感興趣的全局一致的廣播類型數(shù)據(jù)，Val-ueChange為本地應(yīng)用對Data變化的期望，realchange為本地應(yīng)用最終得到的Data變化。由于boardcast_revision更新主要是通過廣播信道更新，所以下面算法主要敘述Data的狀態(tài)和值的更新。 只節(jié)點廣播信道更新數(shù)據(jù)的處理流程的偽代碼片段如下，算法2：

1：

2：

if（Data.status==boardcast-read）（

//new value change command can be send now

3：Send_update（Data， ValueChange）;// Asynic messagesend

4： ） else if（Data.status==boardcast-lock）（

5：Invalidate（Data）;// local variables need to bechecked. Data value maybe changed

6： j

Pi節(jié)點收到P0返回的異步消息處理結(jié)果的處理流程為代碼如下，算法3：

0：

1：

value=Get_CurrentValue（Data）

2： if（resuh.status==sucess）{

3：realchange=ValueChange;

4： ）else if（result.status==fail）（

5：

realchange=0;

6： 1

7

Pi節(jié)點的數(shù)據(jù)處理邏輯，應(yīng)該基于ValueChange和real-change，而不是基于廣播類型數(shù)據(jù)Data的value。

通過引入廣播數(shù)據(jù)類型，分布式程序的設(shè)計上可以不需要為分布式變量操作的同步而消耗時間等待。廣播數(shù)據(jù)類型的修改采用異步的方式，不會影響本地的應(yīng)用效率。只是在應(yīng)用設(shè)計上，要正確靈活地使用廣播數(shù)據(jù)類型。這大大簡化了分布式系統(tǒng)的設(shè)計。分布節(jié)點Pi對應(yīng)用邏輯的處理中，不需要執(zhí)行對數(shù)據(jù)庫的持久化操作，所有的持久化操作集中在Po做。這會讓應(yīng)用程序負(fù)擔(dān)小，跑得更快。在Po中，對值更新類型的數(shù)據(jù)操作，可以在Trsp時間內(nèi)合并對相同數(shù)據(jù)操作，最后只需一次數(shù)據(jù)庫的持久化寫入，這種合并處理對PO的數(shù)據(jù)庫10操作的減少也是有很大幫助的，此部分的處理可以在Po系統(tǒng)中劃分一個中間件子系統(tǒng)來處理;另外在每次提交的操作間隔中，已經(jīng)包括了p0數(shù)據(jù)庫的提交，所以Po的處理速度會因為數(shù)據(jù)量的增大有所減慢（g增加），從而增加系統(tǒng)最小更新時間間隔Trsp。但目前有很多比較成熟的技術(shù)可以提高這部分的執(zhí)行效率[1][2]。

對數(shù)據(jù)項的操作盡量多使用更新類型的數(shù)據(jù)操作，而不是設(shè)置類型的數(shù)據(jù)操作。這是分布式系統(tǒng)數(shù)據(jù)處理中常見的情況，比如：對金額，計數(shù)等的操作，主要是更新類型操作。

4 模擬仿真

例如：全國鐵路售票系統(tǒng)使用本算法實現(xiàn)全國范圍內(nèi)的列車剩余車票數(shù)據(jù)的更新事務(wù)處理。全國所有的鐵路售票系統(tǒng)通過網(wǎng)站為全國人民服務(wù)，全國人民可以訪問網(wǎng)站來訂票，訂票的規(guī)則是先到先得。

現(xiàn)此系統(tǒng)準(zhǔn)備使用本算法，實施如下。

1.對全國所有的鐵路售票系統(tǒng)通過網(wǎng)站，按CHCDN的方式，在全國建立多個鏡像服務(wù)器。假設(shè)全國每個小區(qū)都有一個邊緣計算中心，則可以在每個小區(qū)的邊緣計算中心中，利用CHCDN系統(tǒng)部署鏡像站點，為小區(qū)中的居民服務(wù)。

2.每個鏡像站點初始時有一致的數(shù)據(jù)庫，里面保存了全國各列車的售票情況數(shù)據(jù)。

3.通過本算法，系統(tǒng)初始化后，選擇了一個在北京交通部的服務(wù)節(jié)點作為Po，同時在交通部內(nèi)有一個服務(wù)器C可以把數(shù)據(jù)傳到中星9號上的某個數(shù)據(jù)頻點。系統(tǒng)中的所有節(jié)點，都安裝有廣播接收子系統(tǒng)可以獲取中星9號上的這個數(shù)據(jù)頻點中的數(shù)據(jù)。系統(tǒng)經(jīng)過初始化后，確認(rèn)的系統(tǒng)響應(yīng)間隔Trsp為0.8秒。

4.通過廣播信道，可以直接更新系統(tǒng)中各節(jié)點的全國各列車的售票情況數(shù)據(jù)。

5.這樣，各節(jié)點中的網(wǎng)站設(shè)計，大部分沒有什么區(qū)別，只是把用戶部分的用戶信息，作為各節(jié)點自己管理的數(shù)據(jù)。用戶信息的數(shù)據(jù)，在全網(wǎng)也保持一致，此部分信息可以不用存在一個單一的節(jié)點內(nèi)，而是分布式的存于客戶登錄過的節(jié)點中，不同節(jié)點之間的用戶信息之間是可以確保一致的。（這不是本算法要討論的內(nèi)容，所以不詳細(xì)展開）

6.系統(tǒng)中某小區(qū)a有用戶Ua登錄到該小區(qū)內(nèi)的全國所有的鐵路售票系統(tǒng)網(wǎng)站鏡像，這個網(wǎng)站鏡像運行在節(jié)點Pa，Ua在網(wǎng)站上瀏覽L列車的剩余車票時，還有100張，在時刻to，Ua在鏡像網(wǎng)站上訂了一張L列車的車票，這時網(wǎng)站顯示“車票訂票執(zhí)行中…”。由于鏡像網(wǎng)站運行在Pa，Pa中有足夠的資源保證Ua的體驗，用戶體驗到的就是分布式系統(tǒng)處理的速度。

8.ta到tz的時間中，假設(shè)tz最大，tz

9.PO在to +0.5前的時間內(nèi)（t。+0.5對應(yīng)于算法1中的to+ TB+Tmax：i_o）接收Pa到Pz發(fā)來的boardcast_revision=0的更新請求，其中只有Pa到Pj的請求是有效的，假設(shè)他們都在ta+0.5之前到達(dá)PO。Po處理了這些請求后，L列車的余票為9張。Po把這個結(jié)果提交本地數(shù)據(jù)庫，數(shù)據(jù)版本更新為board-cast_revision=1，把結(jié)果通過C傳到中星9的廣播信道中。同時，Po通過點對點的網(wǎng)絡(luò)對Pa到Pz的請求進(jìn)行應(yīng)答。

10.在to +0.8時刻（to +0.8對應(yīng)于算法1中t0+2TB+Tmax：i-0 +9），所有節(jié)點收到廣播信道更新。Uk到Uz的用戶界面上可以瀏覽新的余票信息，只有9張了，重新調(diào)整訂票數(shù)為每人1張。

11.假設(shè)Uk到Uz在重新提交訂票請求的時候，又同時進(jìn)行了提交（這在實際系統(tǒng)中幾乎不可能，但是為了說明系統(tǒng)對這種極端情況的處理，我們假設(shè)同時條件成立）。由于Uk到Uz提交的請求需要16張票，但是現(xiàn)在系統(tǒng)只有9張票，所以只能滿足部分用戶的請求。最）收到這些更新請求后，會根據(jù)Pk到Pz在系統(tǒng)中的排序，定義這些請求的執(zhí)行順序;假設(shè)就按照k-z的順序，則Uk到Us可以每個人得到1張票，Ut到Uz還是沒有搶到票。這時系統(tǒng)中L列車的余票為0張。

同樣的方式，在處理更多的列車數(shù)據(jù)和更多的用戶的時候方法類似。

這個例子體現(xiàn)了利用本算法后的系統(tǒng)的分布式系統(tǒng)的可擴展性和在事務(wù)處理中的高效和公平。

5 結(jié)論

基于廣播信道的分布式事務(wù)處理模型的提出，雖然不能把所有的事務(wù)處理問題都解決。但是針對大量存在的公共變量更新問題，該模型提出了十分有效方法，在計算量、通信量、算法調(diào)試復(fù)雜度等方面都大大改善?；趶V播信道的分布式事務(wù)處理在這類問題的應(yīng)用，將會推動分布式事務(wù)處理方式的改變。

參考文獻(xiàn)：

[1] Lechtenborger J.Two-Phase Commit Protocol. In： Liu L.，Ozsu M. （eds） Encyclopedia of Database Systems[M]. Springer，New York， NY， 2016

[2]Al-Houmaily Y.J.， Samaras G.Three-Phase Commit. In： LiuL.， Ozsu M.T. （eds） Encyclopedia of Database Systems[M].Springer， Boston， MA. 2009

[3]Lamport Leslie，Ceneralized Consensus and Paxos，Microsoft Re-search Technical Report MSR-TR-2005-33， 2005

[4]Ongaro D，Ousterhout J. In search of an understandable consen-sus algorithm[C]. usenix annual technical conference， 2014：305-320+

[5]Junqueira F，Reed B，Serafini M，et al.Zab： High-performancebroadcast for primary-backup systems[C]. dependable systemsand networks. 2011： 245-256.

[6]Burrows M. The Chubby lock service for loosely-coupled dis-tributed systems[C]. operating systems design and implementa-tion。2006： 335-350.

[7]Hunt P D，Konar M， Junqueira F，et al.ZooKeeper： wait-freecoordination for internet-scale systems[C]. usenix annual tech-nical conference. 2010： 11-11.

[8]溫宇強.CDN系統(tǒng)中數(shù)據(jù)請求、發(fā)送的方法、裝置及系統(tǒng)結(jié)構(gòu)：中國專利，ZL 2014 1 0271393.X [P].2014-08-27

【通聯(lián)編輯：梁書】

基金項目：2018年廣州市科技計劃項目“實時大數(shù)據(jù)處理中間件關(guān)鍵技術(shù)研究與開發(fā)”（201804010402）;2018年廣州南洋理工職業(yè)學(xué)院創(chuàng)新強校工程項目“信息技術(shù)創(chuàng)新與應(yīng)用基地”（NY-2018coPT-01）;2019年廣東省普通高校重點研究（自然）項目“實時大數(shù)據(jù)處理平臺關(guān)鍵技術(shù)研究與開發(fā)”

專利：CDN系統(tǒng)中數(shù)據(jù)請求、發(fā)送的方法、裝置及系統(tǒng)結(jié)構(gòu)專利號：ZL 2014 1 0271393.X

作者簡介：溫宇強（1978-），男，碩士，主要研究方向為分布式計算、大數(shù)據(jù)等;邵孟良，副教授，碩士。