一種數據同步方法及其差分編碼和解碼方法
2023-10-09 05:50:29
專利名稱：一種數據同步方法及其差分編碼和解碼方法
技術領域：
本發明涉及電子數據處理技術，特別是涉及一種數據同步方法及其差分編碼和解碼方法。
背景技術：
隨著信息技術的發展，各種電子數據處理系統以及網絡的應用日益廣泛。在很多網際網路增值業務中，為加強用戶之間的溝通和增強用戶的體驗，很多業務和應用伺服器都需要感知用戶的狀態信息。在一些其他的領域，如電子商務搜索等領域，也需要感知用戶的在線狀態並提供搜索過濾功能等。
為提高對用戶狀態信息處理的效率，需要將用戶的狀態數據從狀態數據中心(也可稱之為數據同步中心)同步到要接受用戶狀態數據的各業務伺服器(也可稱之為同步端)中。
因此，有必要設計和實現某種數據同步方案以高效地同步這些頻繁更新的狀態數據到各業務伺服器，而不增加業務伺服器的負荷。
現有技術中，存在一些數據同步的方法。目前，比較通用、高效的數據同步方案一般基於同步中心和同步端間數據塊的校驗算法，如較為流行的遠程數據同步工具Rsync等，屬於增量同步方式。
基於校驗算法的數據同步方法的工作原理為同步中心針對要同步數據目錄中的每個文件，對文件中每個固定大小的數據塊(Chunk)生成校驗碼Checksum，該校驗碼是能唯一標識文件中某個數據塊的數據；然後發送到同步端；同步端收到該信息後，首先也對相應文件的數據塊生成校驗碼Checksum』，將生成的檢驗碼Checksum』與同步中心發送過來的校驗碼Checksum進行校對；若校驗碼一致則該數據塊中的數據一致，則通知同步中心不需進行數據同步；若兩端校驗碼不一致，則同步端發送同步請求到同步中心，同步中心將數據發送到同步端。如此逐一數據塊進行校驗碼的校對，以及同步；直到整個文件處理完畢。
請參閱圖1，是一種現有技術的數據同步方法進行數據同步的流程圖。
同步中心對文件的數據塊Chunk1(0，1000)生成校驗碼Checksum1；向同步端發送信息Check_update(filename，Chunk1，Checksum1，…)；同步端接受該信息後，對文件的數據塊Chunk1(0，1000)採用相同的算法生成校驗碼Checksum1』；隨後比較Checksum1和Checksum1』；由於二者一致，因此向同步中心發送不需同步的通知，攜帶參數(proto_version，chunkid，oper_type，…)，其中proto_version為協議版本，chunkid為數據塊標識，oper_type為操作類型(同步或不需同步)。
隨後，同步中心對文件的數據塊Chunk2(1000，2000)生成校驗碼Checksum2；向同步端發送信息Check_update(filename，Chunk2，Checksum2，…)；同步端接受該信息後，對文件的數據塊Chunk2(1000，2000)生成校驗碼Checksum2』；隨後比較Checksum2和Checksum2』；由於二者不一致，因此向同步中心發送同步請求，攜帶參數(proto_version，chunkid，oper_type，…)；同步中心向同步端發送數據同步消息(filename，chunk2，data)；同步端接收數據並更新相應的chunk2；然後向同步中心發送同步成功消息。
對於Rsync來說，校驗碼的生成採用的是md4，在開始時對文件各數據塊生成好一系列的checksum列表，然後逐個校對。
但是，該現有技術存在缺陷首先，數據同步中心與同步端都需對文件中每個數據分塊進行校驗運算和協商同步，協商的次數取決於文件數據分塊的大小，若數據分塊較小，則需協商的次數較多，協商導致的耗時開銷較大；其次，在同步兩端校驗碼不一致的情況下，即使數據塊中僅有1個bit的數據發生改變，同步中心也要將整個數據塊或者將整個數據塊壓縮後發送給同步端，數據壓縮編碼率較低。
由前述可知，若數據分塊太小，則會導致同步兩端校驗運算和協商時延增大；若數據分塊太大，則會導致數據壓縮編碼率降低，故難以找到一個最佳的數據分塊值，使其適合所有的應用場景。
現有技術中，另外一種在數據同步領域中使用較多的是全同步方式，同步中心和同步端協商好後，建立數據傳輸通道，並將要同步的整個數據文件傳輸到同步端，即使該數據文件僅有少數幾個bit發生改變。
該全同步方式的機制相對比較簡單，協商只需一次，沒有同步過程中多次協商和校驗運算的時間開銷，但是由於總是要同步整個數據文件，故數據壓縮編碼率很低，從而增加伺服器的網絡I/O和帶寬消耗。
發明內容
本發明解決的技術問題在於提供一種數據同步方法及其差分編碼和解碼方法，其協商和校驗運算的時間開銷小，且可以具有較高的壓縮編碼率。
為此，本發明解決技術問題的技術方案是提供一種數據同步方法，用於數據同步中心和同步端之間的數據同步；所述方法包括步驟11)數據同步中心和同步端協商啟動差分編碼同步；數據同步中心對數據文件較上次同步以來的差異特性進行編碼；12)數據同步中心將編碼後的編碼字符串和新生成的最近同步流水號發送到同步端；13)同步端接收到數據同步中心發送的同步信息後，對前述編碼字符串進行解碼，並根據解碼結果設置上次同步得到的數據文件；14)當完成數據同步後，同步端保存前述最近同步流水號。
優選地，在所述步驟11)的協商是同步中心和同步端進行最近同步流水號校對協商；如果最近同步流水號一致，則啟動差分編碼同步；如果不一致，則採用全同步方式進行數據同步。
優選地，所述步驟11)由同步中心定期發起，且同步頻率可配置。
優選地，所述步驟11)還包括對該編碼進行壓縮；所述步驟13)還包括對該編碼字符串進行解壓縮。
優選地，所述步驟11)的編碼包括
51)對當前數據文件和上次同步後的數據文件進行多字節讀入並進行異或運算；52)若異或結果為零，則統計數據塊的偏移值；53)若異或結果不等於零，則算出當前數據塊的位置值及差異值；54)將當前數據塊的位置及差異值組成元素對；對其進行壓縮後增加到編碼串中。
優選地，所述步驟51)讀入的字節的數目可配置；所述步驟53)的位置值為當前數據塊位置與上次出現差異特性的數據塊位置的差；所述步驟54)採用的壓縮算法為Vint壓縮算法、zip壓縮算法、或離散二進位串的前綴壓縮算法。
優選地，所述步驟13)的解碼包括獲得當前數據塊的位置值及差異值；所述步驟13)的設置包括根據編碼串中的位置值獲得對應的數據文件的數據塊；將差異值和前述數據塊進行異或運算，得到更新後的數據塊；將更新後的數據塊寫入數據文件中，得到同步後的數據文件。
另外，本發明還提供一種差分編碼方法，所述方法包括步驟81)對當前數據文件和與其對應的數據文件進行多字節讀入並進行異或運算；82)若異或結果為零，則統計數據塊的偏移值；83)若異或結果不等於零，則算出當前數據塊的位置值及差異值；84)將當前數據塊的位置及差異值組成元素對；對其進行壓縮後增加到編碼串中。
優選地，所述步驟81)讀入的字節的數目可配置；所述步驟83)的位置值為當前數據塊位置與上次出現差異特性的數據塊位置的差；所述步驟84)採用的壓縮算法為Vint壓縮算法、zip壓縮算法、或離散二進位串的前綴壓縮算法。
此外，本發明再提供一種應用於數據同步的差分解碼方法，所述方法包括步驟
101)對接收到的編碼字符串進行解碼，獲得當前數據塊的位置值及差異值；102)根據編碼串中的位置值獲得對應的數據文件的數據塊；103)將差異值和前述數據塊進行異或運算，得到更新後的數據塊；104)將更新後的數據塊寫入數據文件中，得到同步後的數據文件。
相對於現有技術，本發明的有益效果是首先，由於本發明中數據同步中心和同步端經協商啟動數據同步過程後，在同步過程中不需要再進行協商，因此可以減少協商的時間開銷，且同步端無需進行校驗運算，可以提高工作效率；其次，由於採用差分編碼方式，對數據文件較上次同步以來的差異特性進行編碼，數據編碼率較高，從而可以減少網絡I/O和帶寬使用的開銷。
在本發明的優選方案中，數據同步中心和同步端僅需對最近同步流水號協商一次，其協商的時間開銷小。
此外，在採用差分編碼的基礎上，應用壓縮算法來實現壓縮，數據壓縮編碼率較高，從而進一步減少網絡I/O和帶寬使用的開銷。
圖1是一種現有技術的數據同步方法進行數據同步的流程圖；圖2是本發明的數據同步方法的流程圖；圖3是本發明的數據同步方法的實施例中進行差分編碼的示意圖；圖4是本發明的數據同步方法的實施例中進行差分解碼的示意圖；圖5是本發明的數據同步方法中的差分編碼器的工作流程圖；圖6是本發明的數據同步方法中的差分解碼器的工作流程圖。
具體實施例方式
請參閱圖2，是本發明的數據同步方法的流程圖。
步驟S211，同步中心和同步端進行最近同步流水號校對協商。如果最近同步流水號一致，則進入步驟S221；如果不一致，則進入步驟S231，採用全同步方式進行數據同步。
在本發明中，所述最近同步流水號校對協商的過程可以由同步中心定期發起，且同步頻率可以進行配置。
同步中心針對特定的文件向同步端發送消息file，last_sync_seq，其中，last_sync_seq為文件file對應的最近同步流水號；同步端提取本地保存的該文件(上次同步得到數據)的最近同步流水號(上次同步的流水號)，進行校對；若不一致，則表示同步端沒有獲取得到同步中心最近同步的數據，同步端向同步中心發送以全同步方式進行數據同步的請求file，full_sync_type；當同步中心收到該請求後，將要同步的數據文件通過建立的數據通道發送到同步端，格式為file，last_sync_seq，full_sync_type，code_string。
步驟S221，若最近同步流水號一致，則同步端和數據同步中心之間啟動壓縮差分編碼同步。
步驟S222，數據同步中心對數據文件和數據文件較上次同步以來的差異特性進行壓縮編碼。
步驟S223，數據同步中心將壓縮編碼後的編碼字符串和新生成的最近同步流水號發送到同步端。
步驟S224，同步端收到數據同步中心發送的同步信息後，對編碼字符串進行解碼，並設置上次同步得到的數據文件。
步驟S225，當完成數據同步後，保存最近同步流水號。
為了便於對本發明做進一步的了解，下面結合實施例對本發明進行詳細描述。
首先，數據同步中心和同步端進行最近流水號校對協商。如果最近同步流水號不一致，則採用全同步方式進行數據同步。如果一致，則由同步端通知數據同步中心進行壓縮差分編碼同步，所述通知的格式可以是file，last_sync_seq，sync_type。
其次，數據同步中心在接收到該通知後，啟動差分壓縮編碼器，對數據文件和數據文件較上次同步以來的差異特性進行壓縮編碼，並將壓縮編碼後的編碼字符串和新生成的最近同步流水號last_sync_seq，code_string發送到同步端。其中，對差異特性進行壓縮編碼的目的是減少要傳輸的字節數，從而減少網絡帶寬的開銷。
請參閱圖3，是本發明的數據同步方法的實施例中進行差分編碼的示意圖。
假設數據文件D的t時刻為D1，當前時刻為D2，經過差分編碼器(DiffEncoder)300後將得到數據文件D1和D2差異特性表示的編碼串code string。
本實施例中，數據同步中心和同步端進行同步時，壓縮編碼串(Code String)格式定義為Vint{(offset，diff_value)diff_count}。
其中，數據文件D1和D2的差異特性通過元素對(offset，diff_value)進行表示，diff_count為差異元素對個數，offset為相對上次元素對表示差異特性的數據塊偏移，diff_value為差異值。
差異值為數據文件與上次同步數據文件的相應數據塊進行異或運算得到。
當然，本領域的技術人員數據塊的位置也可以直接用該字節的位置(即相對於文件頭的偏移)表示。
優選採用相對偏移，如此有利於壓縮，使用本實施例提到的壓縮算法，一般只使用一個字節則能進行表示。而若直接用該字節的位置表示，將需要多個字節表示。
本實施例採用的Vint壓縮算法是一種簡單且效率很高的整形壓縮算法，其主要思想為每7bits使用一個字節進行表示。當然，本領域的技術人可以理解，還可以採用其他的壓縮算法來進行壓縮。例如zip壓縮算法、或離散二進位串的前綴壓縮算法等等。
請參閱表1，是壓縮的示例。
表1
該表格1列舉了一些數值在壓縮前後的對應，並清楚地表示出其壓縮特性。其中，Value為需要壓縮的值，first byte、second byte、third byte則分別表示壓縮後各字節的值。
再次，同步端收到數據同步中心發送的同步信息last_sync_seq，code_string後，啟動差分壓縮解碼器對code_string進行解碼，得到多個二元組(offset，diff_value)，並設置上次同步得到的數據文件。當完成數據同步後，設置最近同步流水號到數據同步登記表中。
請參閱圖4，本發明的數據同步方法的實施例中進行差分解碼的示意圖。
啟動差分壓縮解碼器(Diff_Decoder)400對code_string進行解碼，得到多個二元組(offset，diff_value)；對每個(offset，diff_value)，從上次同步得到的數據文件D1中獲取相對offset的數據塊，並與diff_value進行異或運算，完成後再寫回到D1數據文件，得到要同步的數據文件D2。
請參閱圖5，是本發明的數據同步方法中的差分編碼器的工作流程圖。
步驟S510，差分編碼器進行編碼時，對數據文件D1和D2進行多字節讀入並進行異或運算(讀入的字節個數為差分編碼器的可調參數，預設為32bits)。
步驟S520，若異或結果為0，則統計offset值。
步驟S530，若異或結果不等於0，則算出其offset及diff_value值。將offset和diff_value組成元素對(offset，diff_value)。
其中，offset及diff_value值可以採用這樣的方式來計算offset＝當前數據塊位置-上次出現差異特性的數據塊位置；若data_d1 data_d2分別表示數據文件D1和D2相應數據塊(chunk)的數據，則diff_value＝data_d1^data_d1。
步驟S540，使用壓縮算法對offset及diff_value值進行壓縮，增加到編碼隊列中。
請參閱圖6，是本發明的數據同步方法中的差分解碼器的工作流程圖。
步驟S610，差分解碼器進行解碼時，獲取差分編碼器生成的編碼串。
步驟S620，根據編碼串中的offset獲得對應的數據文件D1的數據塊。
步驟S630，將diff_value值和前述數據塊進行異或運算，得到更新後的數據塊。
步驟S640，將其寫入數據文件D1中，得到要同步的數據文件D2。
本領域的技術人員理解，本發明中，差分編/解碼器採用的是邊讀入邊進行編碼壓縮或邊讀入邊進行解碼的方式，效率比較高。
應用實例應用本發明的技術方案在用戶狀態數據中心和各應用伺服器(同步端)間進行數據同步，效果比較好。
140M的用戶狀態數據在狀態同步中心與同步端間，每5s需進行一次同步，同步更新較為頻繁，5s內總共大概有25000個用戶的狀態發生變化(上線，下線或隱身，每狀態使用2bit進行表示)。
應用本發明的技術方案所描述的具壓縮特性的差分編碼器處理後的編碼數據僅為65K，而編碼的效率為ms級，同步端進行解碼同步的速度更為微秒級。整個同步過程從數據同步中心發起同步請求，到同步端收到應答後完成數據同步，耗時為ms級，效率極高。並且由於大大壓縮了要同步的數據量，節省了兩端CPU和內網帶寬的開銷。
綜上所述，本發明提供一種使數據同步中心和同步端高效進行數據同步的方法，該技術方案對於數據文件同步前後的差異具有稀疏特性，且同步中心需與同步端進行頻繁準實時同步的應用場景效果很好。
本發明的方法對同步中心和同步端的同步機制進行了改進。
同時，具有壓縮特性的差分編/解碼方法的實現能對數據文件較上次同步以來的差異特性進行編碼壓縮表示，另一側獲得這個編碼串並進行解碼後能得到要同步的數據。
以上所述僅僅是本發明的優選實施方式，應當指出，對於本技術領域的普通技術人員來說，在不脫離本發明原理的前提下，還可以做出若干改進和潤飾，這些改進和潤飾也應視為本發明的保護範圍。
權利要求
1.一種數據同步方法，用於數據同步中心和同步端之間的數據同步；其特徵在於，包括步驟11)數據同步中心和同步端協商啟動差分編碼同步；數據同步中心對數據文件較上次同步以來的差異特性進行編碼；12)數據同步中心將編碼後的編碼字符串和新生成的最近同步流水號發送到同步端；13)同步端接收到數據同步中心發送的同步信息後，對前述編碼字符串進行解碼，並根據解碼結果設置上次同步得到的數據文件；14)當完成數據同步後，同步端保存前述最近同步流水號。
2.根據權利要求1所述的數據同步方法，其特徵在於，所述步驟11)中的協商是同步中心和同步端進行最近同步流水號校對協商，如果最近同步流水號一致，則啟動差分編碼同步；如果不一致，則採用全同步方式進行數據同步。
3.根據權利要求2所述的數據同步方法，其特徵在於，所述步驟11)由同步中心定期發起，且同步頻率可配置。
4.根據權利要求1至3任一項所述的數據同步方法，其特徵在於，所述步驟11)還包括對該編碼進行壓縮；所述步驟13)還包括對該編碼字符串進行解壓縮。
5.根據權利要求4所述的數據同步方法，其特徵在於，所述步驟11)的編碼包括51)對當前數據文件和上次同步後的數據文件進行多字節讀入並進行異或運算；52)若異或結果為零，則統計數據塊的偏移值；53)若異或結果不等於零，則算出當前數據塊的位置值及差異值；54)將當前數據塊的位置及差異值組成元素對；對其進行壓縮後增加到編碼串中。
6.根據權利要求5所述的數據同步方法，其特徵在於，所述步驟51)讀入的字節的數目可配置；所述步驟53)的位置值為當前數據塊位置與上次出現差異特性的數據塊位置的差；所述步驟54)採用的壓縮算法為Vint壓縮算法、zip壓縮算法、或離散二進位串的前綴壓縮算法。
7.根據權利要求6所述的數據同步方法，其特徵在於，所述步驟13)的解碼包括獲得當前數據塊的位置值及差異值；所述步驟13)的設置包括根據編碼串中的位置值獲得對應的數據文件的數據塊；將差異值和前述數據塊進行異或運算，得到更新後的數據塊；將更新後的數據塊寫入數據文件中，得到同步後的數據文件。
8.一種差分編碼方法，其特徵在於，包括步驟81)對當前數據文件和與其對應的數據文件進行多字節讀入並進行異或運算；82)若異或結果為零，則統計數據塊的偏移值；83)若異或結果不等於零，則算出當前數據塊的位置值及差異值；84)將當前數據塊的位置及差異值組成元素對；對其進行壓縮後增加到編碼串中。
9.根據權利要求8所述的差分編碼方法，其特徵在於，所述步驟81)讀入的字節的數目可配置；所述步驟83)的位置值為當前數據塊位置與上次出現差異特性的數據塊位置的差；所述步驟84)採用的壓縮算法為Vint壓縮算法、zip壓縮算法、或離散二進位串的前綴壓縮算法。
10.一種應用於數據同步的差分解碼方法，其特徵在於，包括步驟101)對接收到的編碼字符串進行解碼，獲得當前數據塊的位置值及差異值；102)根據編碼串中的位置值獲得對應的數據文件的數據塊；103)將差異值和前述數據塊進行異或運算，得到更新後的數據塊；104)將更新後的數據塊寫入數據文件中，得到同步後的數據文件。
全文摘要
本發明涉及一種數據同步方法，用於數據同步中心和同步端之間的數據同步；包括步驟數據同步中心和同步端協商啟動差分編碼同步；數據同步中心對數據文件較上次同步以來的差異特性進行編碼；數據同步中心將編碼後的編碼字符串和新生成的最近同步流水號發送到同步端；同步端接收到數據同步中心發送的同步信息後，對前述編碼字符串進行解碼，並根據解碼結果設置上次同步得到的數據文件；當完成數據同步後，同步端保存前述最近同步流水號。由於本發明中數據同步中心和同步端經協商啟動數據同步過程後，在同步過程中不需要再進行協商，因此可以減少協商的時間開銷，且同步端無需進行校驗運算，可以提高工作效率。
文檔編號H04L29/06GK1949761SQ200510100339
公開日2007年4月18日 申請日期2005年10月13日 優先權日2005年10月13日
發明者黃斌強 申請人:騰訊科技(深圳)有限公司