[發明專利]一種數據篩選規則系統的分布式一致性實現方法

在審

• 申請號: 201510230896.7
• 申請日: 2015-05-08
• 公開（公告）號: CN104820698A
• 公開（公告）日: 2015-08-05
• 發明（設計）人: 郭通;張巨;董鴻軍;劉鵬;楊立軍;孫家輝;孫戰軍;李聰;王運闊
• 申請（專利權）人: 中國人民解放軍61600部隊
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京理工大學專利中心 11120
• 代理人: 仇蕾安

本發明提供一種數據篩選規則系統的分布式一致性實現方法，避免了集中式方式因規則中心的節點異常而導致系統全局不可用的情況發生，同時又確保所有創建生效的規則均經過審批。本發明采用“集中式+分布式”雙棧架構的解決方案，兩個棧在廣域網層面上同時運行、互不干涉，在端點上調和兩個棧上結果的不一致狀態，實現了集中審批功能和局部可用性優先。以審計代審批為讓步條件，支撐局部可用優先約束。

技術領域

本發明涉及一種數據篩選規則系統的分布式一致性實現方法，屬于現代數據過濾領域。

背景技術

數據篩選規則系統將在多用戶、分布式和廣域組網的環境下進行應用，其數據中心往往在網絡末梢，資源大，互聯帶寬低，資源和用戶之間也存在一定的約束策略，本地用戶可直接管理到本地資源，遠程用戶則需通過綜合利用服務器連到資源端。

不同于一般分布式系統“去中心化”的特點，數據篩選規則系統要求有一個管控/仲裁角色，來完成對規則的集中審批，以實現對規則合法性的篩選。這就需要我們設計一個集中管控方案。分布式廣域組網并不十分可靠，存在中斷、帶寬低、丟包、延遲大等缺點，如果分布式解決方案設計的不合理，為了全局一致性，就可能得犧牲局部可用性，甚至造成用戶使用本地資源上的障礙，而局部可用性優先又是用戶的基本需求。

CAP(Consistency，Availability，Partition tolerance)定律告訴我們：在一個分布式系統中，一致性、可用性和分區容錯性這三種保證無法同時得到滿足。對于分布式系統，分區容錯性是基本要求，因此設計只能在一致性和可用性之間做出權衡，這就是會有CP系統、AP系統和BASE模型系統【即基本可用(Basically Available)，柔性一致(Softstate)和最終一致(Eventually consistent)】等設計范式的原因。

分布式系統(這里主要指地理上的分布式)中數據一致性問題主要來自于多副本，即系統中存在多個副本、數據的修改通常會在不同的副本上進行。為了解決分布式中的一致性問題，現有的幾種典型算法主要有：兩階段提交算法、Lamport面包店算法、Paxos算法、Gossip算法和采用樂觀鎖原理實現的同步方式等。2006年Google的三篇關于“chubby鎖服務”的論文指出，其他分布式算法都可看作是Paxos的特異化形式。鑒于此，下面僅重點介紹一下Paxos算法：

Paxos算法是分布式一致性算法用來解決一個分布式系統如何就某個值(決議)達成一致的問題。一個典型的場景是，在一個分布式數據庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那么他們最后能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個一致性算法以保證每個節點看到的指令一致。Paxos算法是一個較高效的一致性算法，和傳統的分布式鎖算法還是不太一樣的，比如RA算法，它和單機上的加鎖解鎖有一個最大的共同點就是有很明顯的“請求--等待”的過程，而Paxos算法每一個實例之間相對獨立，選舉過程可以平行執行，后發生的實例是可以再先發生的實例之前表決的，并沒有明顯的“請求--等待”的感覺。在具體的應用時，分布式鎖算法更多的是“互斥”的感覺，一致性算法更多的是“同步”的感覺。整個Paxos算法可以看作是多個交叉執行而又相互影響的兩階段提交算法，該算法具有以下特點：

1、基于消息傳遞的三點假設，即沒有拜占庭將軍問題(Byzantine failure)；只要等待足夠的時間，消息就會被傳到；以及Paxos島上的議員是不會反對其他議員提出的決議。

2、在結點數少于半數失效的情況下仍然能正常的工作，結點失效可以在任何時候發生而不影響算法正常執行；proposer提出一個提案前，首先要和足以形成多數派的acceptors進行通信，獲得他們進行的最近一次接受的提案。

3、整個算法基本上就是圍繞著提案編號在進行：proposer忙于選擇更大的編號提交proposal，acceptor則比較提交的proposal的編號是否已是最大，只要編號確定了，所對應的value也就確定了。