分散式系統因果一致性與COPS演算法

COPS是保序系統的集群(Clusters of Order Preserving System)的簡稱。在了解COPS之前，最好首先了解一下分散式系統CAC演算法，從CAP-->CAC-->COPS是分散式系統的確保高性能低延遲高可擴展性的前提下追求高一致性直至事務機制的發展路徑。

COPS系統能夠提供因果+一致性causal+ consistency，設計為支持複雜的在線應用，這些應用託管在少量的大規模數據中心，每個應用都是有前端伺服器(COPS客戶端)以及後端key-value數據存儲，COPS在本地數據中心以線性化方式執行所有的put寫操作和get讀操作，然後會跨數據中心以因果一致性的順序在後台進行複製。

通過COPS我們能夠獲得ALPS：Availability, Low-Latency,Partition-tolerance, 和 Scalability.

• 可用性 Availability: 所有操作讀能成功，沒有會無限期堵塞或返回一個顯示數據不可用的錯誤。
• 低延遲Low-latency: 目標響應時間在毫秒級別。
• 分區容錯Partition tolerance: 數據存儲能夠在網路分區的情況下持續操作。
• 可擴展性Scalability: 數據存儲能夠線性水平擴展。

按照CAP定理，這種ALPS系統必然會犧牲強一致性，比如linearizability線性一致性，但是我們還是能夠在此約束下尋找到最強的一致性，也就是因果一致性。

下面看看什麼是因果一致性。我們假設一個key-value數據存儲，有兩個基本操作: put(key,val) 和 get(key)=val. 這個類似於在單機的共享內存系統中的讀操作和寫操作(可參考：Go語言Goroutine與Channel內存模型)。

我們約定遵循下面三個規則表示潛在一致性，用符號表達 ->：

1. 在同一執行線程：. 如果a 和 b 是一個執行線程中的兩個操作，如果操作a發生在操作b之前，那麼a ->b；
2. 不同線程Gets From. 如果 a是一個put放入操作，且b是一個獲得操作，能返回被a放入的寫操作結果值，那麼a->b；
3. 傳遞性Transitivity. 對於操作a, b, 和 c, if a -> b 且 b -> c, 那麼 a -> c.

這些規則在同一個線程內的操作之間以及在與數據存儲交互的不同線程的操作之間創建了潛在的因果關係，這個模型，並不允許線程直接通訊，而是通過數據存儲進行通訊。

下面我們使用這個因果規則來看看具體分散式系統的情況，如下圖：

上圖模擬了三個規則，在同一執行線程規則是get(y)=2 -> put(x,4)（圖中的client 2）；而gets from規則是put(y,2) -> get(y)=2（圖中client1和client2中間縱向，代表兩個不同線程的寫讀操作）; 而傳遞性規則是 put(y,2) -> put(x,4)（根據前兩個規則推導出的因果性）。即使一些操作如put(x,3)也實時發生了。因為沒有其他操作依賴它， 沒有任何其他讀操作會讀取器寫入的值，也沒有同一個線程內存中跟隨其後的其他操作，因此，client3獲得的x值是4，而不是3。

因果一致性是指在一個分散式複製環境通過get操作獲得的值結果是由->順序定義的。以上圖來說，似乎put(y,2)發生在put(x,4)之前，而put(x,4)發生在put(z,5)之前，如果client2看到get(x)=4然後又看到get(x)=1，那麼就違背了因果一致性了。

因果一致性並不對並發操作排序，如果 a不在b之前發生，b也不在a之前發生，那麼a 和b是並發的，a和b是兩個不相關的操作，那麼它們在分散式系統中複製就不必遵循任何順序了，這樣就避免了在它們之間使用因果這種串列化方式。

但是，如果a和b進行的是使用相同key值的put寫操作，那麼就發生衝突了。比如a操作是put(x,1)，b操作是put(x,2)，那麼一個複製節點就永遠返回x值為1；另外一個返回x值為2；還有一種意外情況發生，兩個人使用同樣的用戶名登錄，同時將商品放入他們的購物車，那麼與用戶帳戶一一對應的購物車該選擇哪個商品放入呢？

解決這種衝突是採取基於 Lamport clock的 last-writer-win策略：

初始存儲節點使用一個Lamport時間錯為每次更新分配唯一的版本號，節點將版本號作為其高位位元組，低位位元組保存的是節點標識，. Lamport時間戳允許COPS將每個key的所有寫操作維護全局的順序。這個順序暗含了實現last-writer-win的收斂衝突策略 (convergent conflict handling policy）。

原文：Don』t Settle for Eventual:

Scalable Causal Consistency for Wide-Area Storage with COPS

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！