一種移動網絡下基于雙時間戳的數據增量同步研究

郝 平 林原沖

一種移動網絡下基于雙時間戳的數據增量同步研究

郝 平 林原沖

(浙江工業大學計算機科學與技術學院 浙江 杭州 310023)

隨著移動計算的廣泛應用，數據同步技術在分布式環境下發揮越來越大的作用。針對分布式移動環境的特殊性，研究并提出一種基于雙時間戳的數據增量同步機制，為移動數據庫復制技術提供一種可行的解決方案。在保證數據一致性的同時，為系統層級擴展提供了新的思路。實驗結果表明，設定合理的批量傳輸單位能有效地提升同步機制的可靠性。最后設計并實現移動執法智能終端系統，輔助現場作業。

數據同步 雙時間戳 擴展 批量傳輸

0 引 言

在移動互聯網領域，網絡環境變得越來越復雜。傳統的在固定主機FH(Fixed Host)保存數據副本，移動終端機MH(Mobile Host)獲取的數據都來自FH，數據流動是單向的集中式架構不適合當前的移動環境。根據Jim Gray等提出的兩級復制機制思想，使用FM和MH都保存數據副本的兩級分布式架構。兩者是一對多的關系(一個FM對應一個或多個MH)，數據交流是雙向的，并采用松散性的差異式同步策略[2]成為應對當前移動網絡環境的主要選擇。

同步粒度是移動數據庫數據同步的基本單位，根據是否為事務性主要分為兩類：事務、元組。利用事務提交變更可以保證數據的ACID特性，但事務提交需要保持一段時間的連接性，回滾過多容易影響系統效率[3]。而當前主流的移動操作系統對遠程事務支持不足，采用元組作為同步粒度是該類系統的一個考量。本文研究背景以移動環境下的作業為主，以元組作為同步粒度，提出基于雙時間戳的數據增量同步機制，有效地保證數據一致性和可用性。

1 算法研究

分布式系統一般采用經典的主從式結構，體系架構如圖1所示。

圖1 主從式網絡架構

這里，我們需要處理好所謂的“CAP原理”[4]，即數據一致性(C)，系統/數據可用性(A)，分區容錯性(P)。而分區容錯性是在分布式系統中必須實現的，因此為了保證系統/數據的可用性，需要提供在線或是離線時的數據存儲，以及進一步通過會話在軟實時的更新傳播下實現數據的一致性。而當前的移動數據庫系統同樣可以視作一個準分布式體系結構[5]。

數據同步分為上傳和下載兩個部分。上傳一般由MH發起；下載則有不同的實現方式，可以由MH發起，也可以是在MH上傳之后由FM端將針對MH的差異數據返回，即將上傳下載合并。

針對數據沖突，由于時間上的異步而產生的沖突是不可避免的，只能在邏輯上犧牲一方的操作或者在應用上按一定策略進行操作內容的合并。主要機制包括：主從表、邏輯合并、分組[7]。主從表機制雖然簡化了沖突處理方式，但弱化了數據操作的時間順序；邏輯合并和分組機制則都需要根據相關業務設置策略。本文側重數據操作的時間順序性(基于時間順序法)，該方法除了實現簡便，還能方便在現有的集中式架構基礎上擴展分布式系統。

增量同步，需要把整體任務細分成多個獨立的子任務， 本地通過隊列維護多個子任務，并利用數據的時間戳記錄同步的進度。而對于任務生成源的選擇，文獻[6]給出從FM端獲取的方式，好處是方便于FM端對任務統一管理，缺點是增加了同步的請求次數成本。

本文的數據同步模型如圖2所示。

圖2 數據同步模型

其中MH和FM各自包含沖突檢測、沖突處理、結果處理的功能，以及MH端另外設置了任務的生成、管理功能，其中各個模塊之間是調用的關系。

1.1 同步算法

為了便于在現有的集中式系統上擴展分布式系統，本文在MH和FM數據庫元組原有屬性的基礎上做以下調整：

MH端設置或添加三個屬性，如表1所示。

表1 MH端調整后的屬性

FM端設置或添加以下三個屬性，如表2所示。

表2 FM端調整后的屬性

其中，本地變更時間記錄MH操作時間，用于數據的同步沖突檢測。服務器變更時間用于增量數據同步的參照，因此保證MH和FM時間的一致性顯得尤為重要[8]。刪除標記用于標記被刪除的數據對象Ddel，刪除標記的引入，將刪除操作d(D)當做是一個更新操作u(D)，即d(D)∈R(x|x∈u(D))，而且因為任何人都不會對已加刪除標記的記錄進行修改操作，所以刪除有刪除標記的記錄不會引起數據庫數據的刪除沖突[9]。

針對TC和TS，通過設置以下幾條基本操作規則，作為數據同步的標準：

(1) MH對于數據對象D的操作，只涉及TCm。

(2) 數據對象D的操作結果上傳到FM時，令TCf=TCm，TSf=服務器時間。

(3) FM單獨對數據對象D的操作，涉及TCf和TSf，且TCf=TSf=服務器時間。

(4) MH下載數據對象D，令TSm=TSf。

(5) 沖突處理以數據對象D的最晚TC為考量(時間順序法)。

其中規則(3)表現為在FM端直接修改數據的情況，等同于是規則(1)和規則(2)的無間隙合并操作。數據同步圍繞TCm、TSm、TCf、TSf進行，圖3給出了針對該4個屬性的時間順序閉環圖。

圖3 TC-TS閉環圖

對于FM上的數據對象D，TCf～TSf稱之為其操作op(D)的 “風險時段”，即如果其他Site上有op(D)’的TCm處于該時段，則op(D)有在該時間段被替換的風險，否則予以保留。所以需要將上傳下載分開，并且每次MH端要先執行下載操作，通過下載其他MH可能操作并上傳過的數據對象，錯開TCm和TCf～TSf，可以降低本地操作被替換的幾率。

對于數據的上傳下載，設置單次數據傳輸大小上限N。因為考慮到移動網絡環境下數據上下行帶寬的差異性以及本地設備硬件性能等問題，對于大量數據的傳輸，如果不分批次進行，一旦傳輸失敗，則要全部重新開始，這無疑提高了操作的失敗成本；如果每個批次分得過小，又會增加網絡請求次數成本。

數據上傳算法描述如下：

BEGIN

(a) MH從待上傳數據集中取得數據量大小不大于N的數據集Sm。

(b) 如果Sm為空

(c) 跳到END

(d) 否則

(e) FM收到數據集Sm，對于每個數據對象Dm∈Sm，檢測庫中是否已存在該數據。

(f) 如果存在

(g) 比較Dm的本地變更時間TCm與庫中的數據Df的本地變更時間TCf。

(h) 如果TCm>=TCf，則

(i) 將Dm更新到FM數據庫中。

(j) 否則

(k) 將Df的TSf設為TSm并返回，更新到MH數據庫中，從待上傳數據集中移除Dm。

(l) 否則

(m) 將數據添加到數據庫中

(n) 跳到BEGIN

END

數據下載時序一致性保證策略：

MH需要從FM獲取數據集總量包含m個數據對象，對應的TSf依次為t1,t2,…,tm(t1≤t2≤…≤tm)。假設分為多次獲取，對應的時序分別為(t1,t2,…,ti)，(tj,tj+1,…,tk),…,(tl,tl+1,…,tm)。為了保證數據下載時序一致性以及避免重復下載的情況,需要保證相連的兩序列滿足ti-1≤ti1-η，則令i=p；(2) 如果(q-1-v)/(N/D)≤1-η，則令i=q-1；(3) 對于數據局部密集(即t1=t2=…=tv=tv+1=…=tq-1)的情況，即當(q-1-v)/(N/D)>1-η且p<1時，需要將tv時刻所有的數據分批次傳輸給MH。以上一批次MH的確認狀態作為發送下一批次的參照，并在(3)情況下將FM返回的最后一批次數據的標記flag改為1或2。

數據下載算法描述：

BEGIN

(a) 設置本地數據累加池S，用于存放數據集。

(b) MH將本地最大的TSm作為參數向FM發起下載請求。

(c) MH收到FM返回TSf>TSm且數據大小不大于N的數據集Sf。

(d) 如果Sf為空

(e) 跳到END

(f) 否則

(g) 對于Sf的狀態碼flag

(h) 如果狀態碼flag等于1或2

(i) 將Sf添加到S

(j) MH對每個數據對象Df∈S，檢測本地是否有該數據對象。

(k) 如果存在

(l) 則比較Df的本地變更時間TCf與庫中的數據對象Dm的本地變更時間TCm。

(m) 如果TCf>=TCm，則

(n) 將Df更新到MH數據庫中，如果待上傳數據集中有Dm則移除。

(o) 否則

(p) 將Df添加到MH數據庫中

(q) 清空S

(r) 如果狀態碼flag等于3

(s) 將Sf加到S，向FM發送繼續獲取請求，保持TSm參數不變，并以S中Df個數作為偏移量參數，請求得到從FM返回的新數據集Sf。

(t) 跳到(g)

(u) 跳到BEGIN

END

對于比較是否為相同對象，可以采用分值法：根據關鍵度給若干屬性設置不同的分值，針對兩個元組相同的屬性，累加分值，根據總分所屬區間判定。采用分值法比較對象，可以解決數據添加沖突，但如果比較的屬性過多容易影響效率，需要權衡把控。

1.2 多級擴展

前面提到的TC-TS機制適用于兩級分布式主從架構系統，有時因為一些其他需求，需要將FM當做MH，如各個部門的系統需要定時將新數據上交到中央數據庫；或是將MH當做FM，如外出作業的幾個人員，因為業務需要，可將數據都傳給其中的一個人，由他和FM交互數據，臨時充當了FM的角色。針對三級或多級分布式主從架構系統，TC-TS理論上也可以很容易得到擴展，如圖4所示。

圖4 多級閉環圖

其中Level-1與Level-2、Level-2與Level-3之間各自形成閉環，并通過TS2實現數據的跨層交互。TS2在不同的閉環中起著不同的作用。每層只負責跟相連層通信，降低了數據的耦合，體現了數據同步的層次性。

2 技術實現與應用

相比于傳統的時間戳方式：在元組中添加2個屬性，如創建時間和更新時間，通過它們獲取新插入和更新過的數據；本文采用本地時間結合服務器時間的形式，更加契合客戶端和服務器的同步關聯性，結合刪除標記，降低了沖突檢測的維度。

2.1 Android平臺下數據同步流程

通過后臺設置任務隊列并定時獲取隊列任務，根據任務標識執行相應的子任務。

部分代碼如下：

while(true){

if(!tasks.isEmpty()){

Task task=tasks.poll();

if(null!=task){

doTask(task);

}}Thread.sleep(2000);}

下載的數據主要包括兩類： (1) 表記錄；(2) 數據庫文件。對于記錄，可以采用本文的增量同步機制更新；對于數據庫文件，通過從FM下載壓縮包的形式更新，系統中往往定義有數據庫的版本信息，因此可以和系統更新相結合。

初次安裝系統，提示下載對應版本號的初始數據庫；每次升級系統，自定義的數據庫升級方案可以將數據庫版本號升級到最新；如果選擇替換本地數據庫，要保證本地沒有待上傳的數據，以免數據丟失。

如果本地有數據待上傳，則當用戶退出系統時，提醒用戶是否上傳，退出后在后臺上傳數據，上傳結束后通知用戶上傳結果。

2.2 本地化編碼策略

分布式環境下，因為某些特殊業務需要(如本地新增數據的離線打印)，可能需要在本地生成一些標識信息(如標識記錄的編碼)，我們通過在標識信息基礎上添加后綴的形式，并通過語義控制，一定程度上保證了數據的有效和合理性。

該策略比較適用于網絡信號差或沒有信號的環境，雖然可能存在本地打印的標識信息和服務器端保存的標識信息相差一個后綴的情況。但對查詢等操作影響不大，滿足了一定程度上的業務需求。

2.3 實驗結果與分析

測試使用的是2G網絡，基于Android2.3.3系統，利用第三方類庫Ksoap2調用WebService接口實現數據交互。以同步500 MB的數據為例，通過設置斷網模擬偏遠地區無信號時的環境，對于設定不同的N，實驗結果如圖5、圖6所示，其中橫坐標表示N大小，單位MB。

圖5 各類時長對比 圖6 同步被阻斷的概率

實驗結果表明，使用上述增量同步方法，能有效地保證數據同步的一致性，并且通過合理的設置N，不僅可以縮短總的同步時間，也能有效降低同步請求被阻斷的幾率，提高了系統的可靠性和使用性。

3 結 語

隨著移動互聯網的不斷發展，移動辦公在今后的作用會不斷顯現。本文通過設計的數據增量同步機制，以及其他一些策略的調整，便于在原有的集中式系統架構下擴展，并且也探討了批次傳輸大小對同步性能的影響，保證并最大化滿足人員的辦公需求。基于本文設計并實現的移動執法智能終端系統，已經在農業執法領域投入使用，并取得了良好的成效。

[1] 陶濤.基于Android平臺的嵌入式數據庫同步及優化策略研究[D].天津:南開大學,2010.

[2] 姚嵐.基于Web服務的智能客戶端數據同步[D].上海:復旦大學,2008.

[3] 張曉丹,何銳,牛建偉.基于關聯事務的移動數據庫沖突處理算法[J].計算機工程,2008,34(16):60-65.

[4] Lomotey R K,Deters R.Reliable Consumption of Web Services in a Mobile-Cloud Ecosystem Using REST[C]//2013 IEEE Seventh International Symposium on Service-Oriented System Engineering(SOSE),2013(3):13-24.

[5] 趙旸.基于移動數據庫的事務處理模型的研究[J].計算機工程,2006,32(5):68-70.

[6] 劉宇,戴鴻君,郭鳳華,等.Android平臺可增量同步的網絡應用協議[J].計算機工程,2011,37(18):59-64.

[7] 邵寶軍,王延章.非連接數據庫間的數據交換方法[J].計算機工程,2004,30(17):77-78.

[8] 茅敏濤.基于Mobilink實現分布式數據庫同步的研究[J].計算機應用與軟件,2009,26(6):152-154,174.

[9] 封明玉,趙政,張鋼.分布式環境下數據沖突及其解決方案[J].計算機應用研究,2002,19(2):72-74.

ON A DATA INCREMENT SYNCHRONISATION BASED ON DOUBLE TIMESTAMP IN MOBILE NETWORK

Hao Ping Lin Yuanchong

(SchoolofComputerScienceandTechnology,ZhejiangUniversityofTechnology,Hangzhou310023,Zhejiang,China)

Along with the wide use of mobile computing, data synchronisation technique plays an increasing important role in distributed environment. To deal with the specificity of distributed mobile environment, we studied and proposed a double timestamp-based data increment synchronisation mechanism, which provided a viable solution to mobile database replication technology. It presented a new thought to the hierarchical expansion of system while ensuring data consistency. Moreover, it was demonstrated through experimental results that to properly set bulk transfer units could improve the reliability of synchronous mechanism effectively. Finally we designed and implemented the intelligent terminal system of law enforcement to help site operations.

Data synchronisation Double timestamp Expansion Bulk transfer

2014-08-30。郝平，副教授，主研領域：智能控制，過程監控，故障診斷，數據倉庫和挖掘。林原沖，碩士。

TP3

A

10.3969/j.issn.1000-386x.2016.04.034