基于模式識別的分布式存儲信息一致性控制

衛朝霞，徐 艷

(四川大學錦城學院，四川 成都 611731)

1 引言

大型的分布式存儲系統中，通常將同一數據的不同副本存儲在多個異地數據庫上，由于部分副本數據庫是可移動的，很難保證可以實時更新最新數據信息，如何保證異地數據庫中不同副本的數據一致性已成為開發高效分布式信息存儲機制必不可少的關鍵技術。

針對這一問題，相關科研人員提出了幾種分布式存儲信息一致性控制方法：文獻[1]運用值計算的方法控制分布式存儲機制傳輸數據一致性，通過構建大規模異地數據傳輸架構，對數據包中的數據進行分塊處理和值計算，得到值和序列號，對數據包是否連續進行判斷。文獻[2]重新定義了條件函數依賴和微函數依賴，應用依賴控制數據一致性，確定了依賴集合，發現違反依賴的錯誤數據和修復錯誤，并對其中兩個步驟展開了深入的研究。

但是以上兩種方法還存在一些問題，主要有兩個方面：問題1：數據存儲：傳統的數據存儲方式，需要設立1個或者多個字段用于記錄數據的更新記錄，大大增加了存儲的開銷；問題2：數據傳輸：傳統的數據一致性控制方法對網絡通信開銷的需求比較大，一般的互聯網環境很難滿足。

基于此，本文提出了一種基于模式識別的分布式存儲信息一致性控制方法。模式識別相對于其它控制方法特征分類更精準，安全性更高，開銷成本更低，同時結合數據全相關的一致性更新技術，可以有效并且在節約存儲開銷的前提下完成對分布式信息存儲機制的一致性控制。

2 模式識別下分布式存儲信息一致性控制

2.1 分布式信息存儲機制組建

分布式信息存儲機制由主副本兩部分組成：

1)副本移動端

如PDA、手機、筆記本電腦等是可進行移動的便攜電子設備，其數據庫為副本數據庫[3-4]。

2)主本固定端

有固定的數據存儲設備，安全性、可靠性極高。具有可用來傳輸數據的通信接口，可以和副本數據庫進行數據傳輸，其數據庫為主本數據庫。

分布式信息存儲機制如圖1所示。

圖1 分布式信息存儲機制

該分布式信息存儲機制分為3層結構：

結構1：中心控制端

中心控制端是主本數據庫所在的固定端。采集分布式信息存儲機制所有的數據集，可以操控整個系統，以及對副本的權限進行設置。

結構2：傳輸控制端

傳輸控制端對主副本各節點之間的數據信息進行傳輸，并判斷其使用的廣域網還是企業內部的局域網或者企業網。

結構3：移動端

移動端中的各個副本由于是可移動的，工作環境復雜多變，而且是不可預測的，很難具備實時更新數據的條件，但分布式信息存儲機制中的主本數據處在動態變化之中，而且每個數據的副本數量多。

2.2 主副本數據更新過程分析

為了提高分布式信息存儲機制的存儲效率、時效性、可用性以及可靠性，需要采用主副本的方式來存儲信息。建立副本存儲機制不但可以提高數據的可靠性、安全性，而且還可以大大提高整個系統的存儲效率。但是副本也需要占用一部分的存儲空間，增加了整個分布式信息存儲機制的復雜性。對副本的實時更新成為控制分布式信息存儲機制一致性的重要研究內容。圖2為產品數據規劃圖，以某企業B為例，達到分布式存儲產品數據一致性更新的目的。

圖2 產品數據規劃圖

在圖2產品數據規劃圖中，企業B擁有零件Pi的生產權限，下屬部門有B1和B2，B2部門擁有零件Pi的數據主本數據以及研發設計權限。有關零件Pi的主本信息如結構化數據、有關零件Pi的全部文檔信息存儲在企業B的數據庫中；一些副本信息如非結構化數據存儲在企業B與其它企業A、C、F的分布式存儲系統中。為了更好的實現信息一致性控制，可以借助文件指針功能把企業B數據庫中的主副本信息聯系在一起，實時更新主副本數據以達到主副本信息一致性控制的目的。為了防止數據丟失或損壞，將數據分布式存儲在企業A的數據庫中，當做零件Pi的備份數據。則企業B對零件Pi的數據進行更新的同時也要對企業A的數據庫中有關零件Pi的數據進行一致性更新。企業C和企業F是零件Pi的相關配件企業，如子裝配件、套用件、裝配基準件等可能來自企業C或者企業F。所以當企業B有關零件Pi的數據發生變化時，相應的也要及時更新企業C和企業F的次級庫的產品數據。

由于零件Pi由企業B生產研發，那么企業B所擁有的有關零件Pi的所有產品數據都是主本數據，而企業A是該數據的備份存儲部門，企業C和企業F是相關配件企業，所以企業A、C、F中有關零件Pi的數據是零件Pi數據的副本。

如圖2中的部門B2是零件Pi的設計研發部門，B1是零件Pi數據備份部門，對于企業B內部的多個設計或者制造部門，由于這些部門使用的是企業內部的局域網或者是企業網，使用的是同一個網絡地址，所以企業B的所有部門都擁有零件Pi的主本數據信息，并且各部門之間不存在數據一致性要求。

在企業B有關零件Pi的主副本數據存儲方式中，對于零件Pi的數據需要在中心庫、次級庫和數據相關性的其它次級庫重復更新設置，這種分布式存儲信息的方法較為復雜，但是安全性極高。每個企業節點都有零件Pi的副本數據，當其中某一個節點出現故障時，不會影響其它企業繼續使用這些數據，而且每個節點使用的都是企業內部的局域網或者企業網，不使用廣域網，相對成本也較低。因此采用數據全相關的一致性更新技術，可以滿足異地企業之間動態聯盟的數據管理要求。

在這種分布式信息存儲機制中，擁有產品數據主本的企業對數據進行更新和維護，以保證實時更新其它相關企業的數據。當數據主本發生改變時，數據全相關的一致性更新機制將所有有關產品數據的企業節點庫中的數據副本進行更新。

2.3 模式識別下最優特征子集選取

模式識別技術在數據的處理、特征的提取等方面有一定的優越性，且在各行業中應用廣泛，因此本文利用該方法提取數據特征信息。

特征選擇方法一般有篩選和復選兩種。篩選與復選的方式有所不同，篩選中判別函數J(X)所得到的最優特征子集只依賴于訓練樣本，而復選主要是依據分類器的學習算法在不同特征子集上的正確識別率，來判斷所選子集是否為最優特征子集。那么可知訓練樣本的統計特性同時影響篩選和復選的結果，并且測試樣本的學習算法復選的結果也有一定的影響，復選在實際的應用中會比篩選難的多，所以應用的也比篩選少。

無論用篩選或者復選哪一種方法，在d中選取r的最優特征子集最簡單也是最常用的方法就是衡量每一個特征子集，從中找出使J(X)可以達到最大值的那個特征子集。

為了解決這個問題，通過模式識別法來獲取最優特征子集，找出可以構成最優特征子集所需的單個特征。雖然這種方法不能保證找出的就是最優特征子集，或者說找到的就是次優特征子集，但是由于這種方法計算量非常的小，在實際應用中也是比較常見的。本文通過大量分析得出，在所有d沒有任何關系時，單個最優特征所構成的子集未必是最優特征子集，但是自動文本分類的諸多實驗數據說明，由單個最優特征構成最優特征子集依然是應用最多的一種方法。在大量提取單個最優特征的算法中，模式識別最為有效。

在從d中選取r個特征的計算如下：

d中的每個特征f與類別標號的互信息用式(1)表示為

(1)

其中，f的觀測值用x表示，x的類別標號用?表示。

將互信息最大的r個特征選取出來，構成所需的最優特征子集，以便接下來對分布式存儲信息進行一致性控制。

3 分布式存儲信息一致性控制體系

3.1 數據操作模型和定義

將數據模型定義比較常見的二元組(ID，DataSet)。ID可以表示其中某一個數據項，也可以表示多個數據項結合起來所構建的，是數據庫中每組數據獨有的標識；DataSet表示與ID相對應的某一個數據集合。

對數據庫中的數據進行操作主要有添加、修改、刪除三種。對數據進行這三種操作所產生的數據集就是結構序列，為了實現計算機編程計算，將這三種操作用形式化表達為：

1)ADD(ID，DataSet)，對ID所對應的數據項中增加一個DataSet

2)DELETE(ID，DataSet)，對ID所對應的數據項中刪除DataSet；

3)MODIFY(ID，DataSet)，修改ID所對應的數據項DataSet。

對同一個DataSet執行多次重復的添加、刪除和修改，只有第一次操作對數據產生實際改變。

3.2 數據操作構成的結構序列

當對系統中的數據進行添加、刪除或者修改時，操作記錄會被記錄在分布式信息存儲機制的結構序列[5]中。結構序列由以下三種格式構成：

1)(“+”，ID，DataSet)：對ID添加了一個DataSet；

2)(“-”，ID，DataSet)：對ID刪除了一個DataSet；

3)(“｀”，ID，DataSet)：對ID修改了數據DataSet。

結構序列僅記錄對數據產生實際改變的操作，并且只有提交對數據的操作，使數據發生改變，操作記錄[6]才會被記錄在結構序列中。如果對一個數據項添加或者刪除一個已經存在的數據時，數據項不會發生任何的改變，也不會有操作記錄，更不會被記錄在結構序列中。這樣不僅減少了存儲機制的存儲開銷，而且減少了對系統數據的誤操作，保證了系統數據的安全性。如果要修改其中某一個數據項，可以通過先在系統中刪除這個數據項，再添加新的數據項來實現。

在對系統中數據進行一致性控制時，整個結構序列會被分為n個序列域。在同一數據庫中，一個序列域可以包含數據一致性控制間隔中對數據操作產生的所有結構序列條目[7]。序列域只有在本地節點中創建，如果要與其它節點進行數據一致性控制，一定要在發送到其它節點數據庫之前關閉。在數據一致性控制完成后，會有新的序列域產生，因此，結構序列也可以說是本地節點的序列域與其它節點的序列域的集合。

在整個分布式存儲機制中，已知所有主副本數據庫，也就是所有節點數據庫的版本狀態，所有的版本狀態可以通過狀態向量[8]體現并記錄，記錄格式如表1。

表1 狀態向量的記錄

狀態向量可以用來表示和記錄整個分布式信息存儲機制中所有的主副本數據庫，也就是已知節點數據庫所處的版本集合，在分布式存儲信息一致性控制中是數據庫狀態的主要參考，有著不可或缺的作用。

3.3 分布式存儲信息一致性控制實現

在對分布式信息存儲系統的兩個節點進行數據一致性控制時，可以通過對比分析兩個節點數據庫的狀態向量，盡可能選擇少的信息進行傳輸，以減少系統的工作量。

企業B的狀態向量中包含了其副本數據企業A、C、F的狀態，并同時體現在企業B的數據集中。在完整的分布式信息存儲機制中，每個節點數據庫的狀態向量是遞增的，如果企業A的狀態向量值大于企業B的狀態向量值，說明企業A擁有的數據信息要比企業B的新，所以，要把相應的數據集發送給企業B，例如企業A的狀態向量是3，企業B是2，那么企業B會接收到來自企業A狀態向量為3所對應的所有數據集。當企業A、B中所有數據集的狀態向量完成對比后，企業A就可以得到所有狀態向量值大于企業B的數據集清單[9]，并通過網絡傳輸給企業B。

企業A利用模式識別技術掃描整個數據庫，將所有需要發送的數據集按r分類，否則可能導致數據無法被正確同步，然后將完成分類的數據集發送給企業B，企業B在接收到這些數據集后，后臺程序對整個數據庫進行掃描對照，并將相應的數據操作對企業B的主本數據庫進行更新，同時把數據集添加到本地數據庫中，使接收到的數據集只有對本地數據產生實際的改變才會被寫入，否則將不會被寫入。

不同企業之間數據集順序[10]的不同不會影響到分布式信息存儲機制中主副本數據之間的一致性控制。因為對于每一個數據項來說，在本地數據集進行更新時，與該數據項有關的信息是否可以被添加到本地數據庫中，與其它數據項無關，即使該數據項的內容在兩個數據庫中的順序是完全不同的，最終也能實現一致性控制的目的。

4 仿真研究

為了驗證本文方法對分布式存儲信息一致性控制的綜合有效性，進行仿真。將本文方法與文獻[1]方法和文獻[2]方法對比，以分布式存儲信息一致性控制的準確性和耗時為實驗指標進行測試。

首先對準確度進行測試，依次向系統寫入300M、500M、1G、2G、3G、5G的數據，結果如表1所示，其中，J代表數據文件大小，D表示主本數據，R表示副本數據，A表示實際一致情況，Z表示本文方法測試結果，F表示文獻[1]測試結果，X表示文獻[2]測試結果，而表中的Y代表測試結果一致，N代表測試結果不一致。

表2 三種方法對分布式存儲信息一致性控制測試結果

分析表1可知，本文方法測試結果與實際結果一致，而文獻[1]和文獻[2]方法都存在數據錯誤的情況，說明本文方法在控制分布式存儲信息上準確度更高。

其次，使用三種方法對綜合數據庫和企業數據庫再次進行一致性控制準確度測試。綜合數據庫通過信息檢索和機器學習所得，二者均為大規模數據庫。結果如圖3所示。

圖3 綜合數據庫和企業數據庫準確度測試結果

分析圖3可知，不管是綜合數據庫還是企業數據庫，本文方法在控制分布式存儲信息一致性上準確度一直最高，而文獻[1]方法和文獻[2]方法對綜合數據庫的一致性控制準確度相對較低，對企業數據庫的一致性控制準確度明顯降低，這是因為本文使用了模式識別提取出最優特征子集，使得一致性控制結果更優，同時適用性更強。

在上述實驗的基礎上，給出本文方法、文獻[1]方法和文獻[2]方法對不同數據庫進行一致性控制的耗時，結果如圖4所述。

圖4 對綜合數據庫和企業數據庫一致性控制耗時

分析圖4可知，不管是綜合數據庫還是企業數據庫，本文方法耗時明顯比其它兩種方法少，說明本文將模式識別與數據全相關的一致性更新技術相結合的方法不僅對控制分布式存儲信息一致性的準確度高，而且可有效解決分布式存儲信息實時更新的問題。

5 結論

本文采用的基于模式識別的分布式存儲信息一致性控制方法，與現有的數據一致性控制方法相比具有計算簡單、數據更新及時、節省存儲開銷等優勢。采用模式識別技術對數據集進行甄別和預處理，篩選出某些特征相似的信息與數據全相關的一致性更新技術相結合，二者協同對分布式存儲信息一致性控制有很大的幫助，可以在一定程度上節省系統存儲開銷，更有效的支持移動設備在移動條件下的數據一致性控制，為繼續研究分布式信息存儲一致性控制提供了參考依據。