基于ｓｐｒｅａｄ組通信的遠程備份系統的設計與實現

摘要：基于spread組通信系統及其服務，論述了在現有網絡條件下實現遠程數據備份的解決方案。論述了系統的體系結構模型，提出了解決遠程備份過程中通信量過大及數據一致性問題的數據訪問算法，并對算法的正確性進行了證明。

關鍵詞：spread；組通信；容災；遠程備份

中圖分類號：TP302.8

文獻標志碼：A

文章編號：1001-3695（2007）09-0090-03

為了防止地震、火災、人為破壞等造成重要數據的丟失，人們對遠程備份系統給予了廣泛關注。在遠程備份中如何利用現有網絡帶寬進行數據備份、傳輸、共享，以及如何保證遠程備份過程中數據的一致性和完整性成為人們研究的重點。隨著廣域網組通信技術研究的進展，特別是 spread 廣域網組通信系統的日趨成熟，借助于廣域網組通信技術實現遠程數據備份及共享，可以很好地解決遠程數據共享訪問中存在的數據一致性、操作原子性、文件加/解鎖、網絡分區等問題，能顯著改善遠程數據共享訪問性能。

1系統的體系結構

1.1系統的網絡模型

在該系統的網絡配置上，依照spread 組通信系統要求，將整個網絡按照地理因素劃分成不同的 site，每個site代表著位于同一地域的一系列終端和后臺程序（daemon），如圖1所示。

Daemon將這些終端劃分成多個組（每個組擁有本site的惟一組標志——groupID）。每個daemon可以為一個或多個組提供服務。在每一次通信過程中，daemon扮演著site代理和組代理兩重角色。作為site代理，daemon要維護一張包含整個組通信系統的所有site的組成員視圖，并按照這個視圖根據 Dijkstra’s 最短路徑算法，建立起本site與其他site的動態路由樹。作為組代理，daemon要能接收組內終端的訪問請求，更新數據項與訪問組列表，向組內組播或廣播消息。

在spread系統中，通過傳輸層協議在網絡中的所有活動狀態后臺程序間實現消息傳輸、排序、時效性等服務；通過網絡層協議實現可靠傳輸、流量控制、構建最短路由路徑等服務。特別在廣域網絡中，spread 通過hop協議實現不同site之間的點到點通信。在site內部，spread 集中了不同的底層通信協議，如硬件廣播、硬件多播及IP多播等實現daemon向終端的消息傳輸；通過ring協議實現同一site下的多個daemon之間的通信服務。

每一個site由一個或多個通信組(group)構成，如圖2所示。在每個通信組中包含了存儲設備、存儲區域網絡(SAN)、daemon、終端等。終端與存儲設備之間的數據交互通過ROSY系統實現。ROSY系統采用存儲區域網絡，通過第三方數據傳送的訪問方式，實現開放平臺上的應用程序對本地數據服務器上數據的高速訪問[1]。通過把ROSY系統的客戶端部署到通信組的daemon上，允許本地多個客戶端及遠程客戶端對通信組內存儲設備上數據的訪問。

1.2系統的設計思想

基于spread組通信服務，該系統的主要設計思想包括以下五方面：

a)異步性及負載平衡。本系統的備份采用異步復制[2]的思想。該地數據在更新操作完成后，在網絡帶寬利用率較低時進行更新。另外，在遠程備份過程中，為了降低網絡延遲帶來的性能損失，系統進行了負載平衡。

在spread組通信系統中，每一個daemon都依據Dijkstra’s 最短路徑算法建立了與其他site中的代理daemon進行通信的路由樹。在路由樹中的每一個daemon均代表一個site。在遠程數據共享中，當路由樹建立起來后，spread 的負載平衡策略可以使共享的數據快速進行備份更新；通過負載平衡，有效減輕了更新備份節點壓力及網絡負荷，如圖3所示。

b)采用增量備份策略實現完全備份。通過檢查備份歸檔表，系統可以判斷該數據在上次備份后是否更新。如果發生更新，主系統需要通過組通信服務取得該數據的新備份，并修改備份歸檔表。如果沒有發生更新，主系統只需要通知從系統將該數據從上一個備份節點完成一次本地拷貝，而不需要網絡傳輸。備份實際上是只對更新了的數據進行遠程備份，但在終端看來結果卻與完全備份一致。

c) Site內部的組通信過程。在site內部，收到服務請求的daemon通過ring協議將服務請求在本site的所有daemon之間組播，如果請求被響應，則由響應的daemon將響應結果通過ring協議發送給最先收到服務請求的daemon。該daemon再將響應結果通過底層通信協議向請求終端所在組進行組播或廣播；如果請求在本site沒有被響應，則進行site之間的通信。

d) Site之間的通信過程。在site之間，收到服務請求的daemon作為所在site的代理沿路由樹通過hop協議把服務請求發送給后繼site節點;后繼site收到服務請求后，先進行本site的內部通信過程；如果能夠響應，則沿路由樹通過hop協議把結果返回給先驅節點。如果先驅節點不是最初請求site，則繼續向先驅節點發送響應結果；如果先驅節點是最初請求site，則在site內部組播響應結果。

e）虛擬同步通信過程。在數據備份過程中，傳輸一個文件內部的數據是一個連續傳輸過程，但在傳輸不同文件時必須進行一個同步的過程。每發送完一個文件后，都要求接收daemon回送接收到的該文件的大小信息（判斷數據是否完整）和文件的更新時間信息（判斷數據是否一致）。發送daemon依據回饋信息，判斷備份是否成功。如果成功，則備份過程完成；否則必須進行回滾操作及相應的異常處理。

1.3系統實現的難點及解決方案

1）網絡消息排序在遠程數據共享中，數據的訪問請求排序是通過加/解鎖機制來實現的，但是必須對加/解鎖請求的消息進行排序，以保證所有site收到的請求順序一致。系統按照Lamports邏輯時鐘算法為每個site的消息分配一個惟一時間戳（time stamp）；依據此時間戳對消息進行先進先出排序（FIFO）、因果順序(causal)，或者完全排序（totally order）服務。

2）消息時效性在遠程數據共享中，由于網絡本身的原因，不可避免地存在傳輸延遲；另一方面也可能由于機器崩潰或網絡分區的原因，導致某些消息丟失。為了避免無效地等待，提高數據傳輸效率，系統在每一個site都分配了ARU值（小于某個固定值），并把這個值發送給其他site。正常情況下，其他site發送給這個site的消息的site_aru字段值應當小于這個site的ARU值。如果一個site從崩潰中恢復后，它對崩潰前的消息回復消息的site_aru字段的值設置為大于或等于消息目的site的ARU值。通過比較消息的site_aru字段值與site的ARU值大小，可以判斷消息是否過期。過期的消息被丟棄，但可以通過收到過期的消息得知某個site已經恢復正常工作，并據此進行組員關系視圖更新。

3）數據路徑列表為了使daemon能準確取得需要備份的數據，客戶端要向daemon提供包含所有備份數據路徑和更新時間的數據路徑列表。Daemon根據客戶端提供的數據路徑列表中的更新時間與備份歸檔表進行比較，決定是否需要進行遠程備份操作。數據路徑列表格式：**數據組織ID*更新標志位*創建時刻*更新時刻**。其中的更新標志位表示數據是更新還是新建。

4)更新時間生成備份歸檔表備份歸檔表記錄了數據的描述符和該文件最后一次更新時間等信息。其基本格式為**數據組織ID*創建日期*更新日期**。數據備份時，daemon讀取存儲設備上該數據的更新時間，將這個時間和備份歸檔表中該數據的更新時間進行比較。如果相等，則主備份設備告訴從備份設備將該文件從上次備份中直接拷貝（不進行遠程備份）；否則主備份設備向從備份設備發送該數據，從設備重新生成該數據的備份，備份成功后，主備份設備修改備份歸檔表。

2遠程數據共享算法

在系統中，由于數據的讀讀操作不發生沖突，對同一數據的讀操作具有重復性——在前一個讀操作未完成之前，可以進行后一個該數據的讀操作；數據的讀寫、寫讀、寫寫都會發生沖突，所以對同一數據的讀寫、寫讀、寫寫操作的加鎖具有排他性——前一個操作未完成之前，不允許進行后一個操作。

2.1讀算法

遠程數據共享系統的讀數據是指獲取整個系統的訪問許可后，遵循就近訪問原則從位于本site的數據存儲服務器上讀取數據項的內容。如果本site的數據服務器崩潰，則需要從其他某一個距離本site最近的site的數據服務器讀取。其算法描述如下：

a）如果讀數據加鎖失敗，表示數據正在進行其他操作，不可讀，算法結束。

b）如果從本site內部取數據的返回值不是error，表示從本site自身的數據服務器可以獲得數據，轉e);否則轉c)。

c）本site將讀數據的請求依照路由樹發送給最近的site。

d）其余的site接收到讀數據的請求后，如果本site的數據可以訪問，便將數據內容返回；否則，繼續依照路由樹發送讀數據的請求。

e）本site接收到數據內容后，讀操作完成。

f）如果所有site的數據服務器都不能訪問，則讀數據操作失敗。

g）讀數據解鎖，算法結束。

2.2寫算法

遠程數據共享系統的寫數據是指獲取整個系統的訪問許可后，遵循操作的原子性原則，將寫數據的內容提交給本site的daemon，由本site的daemon與其他site的daemon通過組通信過程完成在所有site建立起完全一致的數據備份過程。寫數據完成后，所有site的數據服務器上都建立起該數據最新的完全一致的備份。其算法描述如下：

a）如果寫數據加鎖失敗，表示當前數據正在被訪問，不能進行寫操作，算法結束。

b）事務處理開始。

c）在site內部寫數據，如果失敗，轉f)；否則轉d)。

d）依據路由樹向所有的site多播更新數據的內容，各site更新成功后，則提交事務；否則轉f)。

e）寫數據解鎖，算法結束。

f）事務卷回，轉異常處理算法。

2.3異常處理算法

關于組通信過程異常處理的論述詳見文獻［3，6］。該算法所論述的異常是指在執行寫操作時，發生了網絡分區/合并、數據服務器崩潰/恢復等引起的寫操作無法在所有site建立起一致備份的問題。異常處理分為以下兩類：

a）發生網絡分區或數據服務器崩潰時的處理算法

(a)當在讀操作過程中發生網絡分區，如果是從本site訪問數據，則操作繼續完成；如果遠程訪問數據，網絡分區引起操作訪問失敗，不會引起數據不一致性，轉（c）。

(b)當在寫操作過程中發生了網絡分區或數據服務器崩潰時，系統無法在當前組成員視圖中的所有site建立起完全一致的數據備份。此時，先將寫數據事務卷回。

(c)更新組成員視圖。

(d)在新的組成員視圖中的所有site上執行讀/寫數據操作。

b）發生網絡合并或數據服務器恢復時的處理算法

(a)當發生網絡合并或數據服務器恢復時，新合并/恢復的site首先進行消息時效性驗證，向整個系統中多播一條過時（stable）的消息。

（b)其余site收到過時消息后將這些消息丟棄，但在本次數據訪問操作結束后、下次數據訪問操作前，將恢復的site更新到組成員視圖中。

(c)被新加入組成員視圖的site此后的操作完全與其他site相同，但加入組成員視圖前該site的數據服務器上的數據部分已成為過時數據。這些數據的讀訪問必須從網絡上其他site讀取。

3算法的正確性分析證明

該算法可根據可串行化理論[6]進行正確性分析證明。可串行化理論通過對算法允許的執行序列進行分析，如果算法的所有操作序列都是正確的，則算法是正確的。對于本文所提出的算法，只要對其沖突和異常處理情況進行分析，證明其是正確的即可。

1）采用加鎖機制進行沖突處理因為本算法是基于spread組通信服務提出的，基于lamports邏輯時鐘算法的排序服務能夠保證操作序列對所有site是完全一致的。假定操作序列不可串行化，則只可能有一種情況，即操作A和B都是讀操作；否則違背了讀寫、寫讀、寫寫操作的排他性。對于操作A和B，spread組通信的排序服務能夠保證它們以完全一致的順序在系統中執行。無論這個順序是A先于B或者B先于A，結果都是正確的（兩種順序下讀取的值是相同的）。

2）關于異常的處理其分為兩種情況。在第一種情況中，事務卷回后，所有活動site的狀態達到了統一，再進行組成員視圖更新，在更新后的組成員視圖上進行預期操作。此過程本身是序列化的。對于第二種情況，如果site的新合并/恢復是在兩個操作中間發生的，那么執行后一個操作前，組成員視圖已經得到更新，后續操作將在新的組成員視圖上執行；如果site的新合并/恢復是在某個操作的執行過程中發生的，該算法的處理是當前操作在此前的組成員視圖上繼續執行，該操作完成后，將組成員視圖更新。以上操作過程都是可序列化的。

綜合以上兩點可以證明，該算法的操作過程是可串行化的。依據可串行化理論，該算法是正確的。

4結束語

本文基于spread組通信系統及其服務提出了遠程數據備份方案及數據訪問算法，并對該算法進行了分析證明。該方案的特點是：a)可靠性高。在整個系統中，只要有一個數據備份可用，就能正常訪問數據。也就是在發生了k級錯誤時，只要有l+1個備份存在，系統就能正常工作。b）數據的讀操作遵循就近訪問原則，只要本地的數據服務器可用，數據的讀操作就不會影響整個網絡。c)采用了spread廣域網組通信系統，算法對出現網絡分區、節點崩潰恢復等情況有很好的處理機制。d)采用spread廣域網組通信系統的修剪路由樹策略，算法能夠實現負載動態平衡，避免發生單點故障。

參考文獻：

［1］賈瑞勇. 基于存儲區域網絡的開放平臺與大型機共享文件系統關鍵技術研究[D]. 西安: 西北工業大學，2005:97-162.

[2]AMIR Y， NITAROTARU C， STAN TON J， et al. Secure spread:an integrated architecture for secure groupcommunication[J].IEEE Trans on Dependable and Secure Computing， 2005， 2(3):248-261.

[3]AMIR Y， STANTON J. The spread wide area group communication system， CNDS-98-4[R].[S.l.]:Department of Computer Science， The Johns Hopkins University， 1998:1-16.

[4]BARTOLI A. Implementing a replicated service with group communication [J].Journal of Systems Architecture，2004， 50(8):493-519.

[5]舒后，段成華.基于組通信技術的同步復制方法的研究[J]. 計算機應用研究，2003，20(3):33-37.

[6]BERSTEIN P A， GOODMAN N. An algorithm for concurrency control and recovery in replicated distributed databases[J].ACM Trans on Database Systems，1994， 9(4):596-615.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”