環球報道:CAP為什么沒有明確考慮收斂性？分布式系統中的收斂性

來源：CSDN 時間：2023-03-09 08:57:46

一致性Consistency, 可用性Availability, 和收斂性Convergence是分布式系統中相對于CAP定理的另外一個定理，2014年由Mahajan, Alvisi, 和 Dahlin提出： Consistency, Availability, and Convergence 。

【資料圖】

CAP(consistency, availability, partition)混合了分布式特性(如一致性和可用性)與系統模型(網絡可靠性指標)，在CAC中，則將這些分布式特性與系統模型進行了分離。

收斂性

在經典的最終一致性模型中有一些無用的模型，比如所有分布式節點都會一致返回一個常量值，Mahajian他們通過引入收斂性這個符合我們常識定義來修正了這些漏洞。

CAP為什么沒有明確考慮收斂性？是因為線性化和順序這兩種一致性里面已經包含了收斂性的需求，當我們檢查如因果一致性 causal consistency，我們會發現我們必須明確地考慮收斂性。

收斂性是指一種實現能力，它能確保被一個節點寫入的數據被另外一個讀取，收斂性的定義是：描述的是一個節點能夠讀取到其他節點的寫入時的一系列環境條件(如網絡，本地時鐘等)。

一個簡單的收斂性其實是一種最終一致性，如果一個系統停止了接受寫入和足夠的通訊發生，那么這個系統就會達到一種狀態，這種狀態是，對于任何對象o，o的讀取會在所有節點上返回同樣的值。

在節點A和B之間的單邊收斂 one way convergence是指：使用兩步單向通訊完成收斂性，首先 A將修改發往B，然后B將修改發往A。

如果說，一致性是指所有節點都同意，那么收斂性是指所有節點都同意是一種可取的有用的狀態。

通過引入收斂性，我們可以在安全（一致性）和靈活性（可用與收斂）之間取得平衡。

因果一致性

因果一致性(Causal consistency)遵循‘happens-before’ 圖義，也就是說，寫在讀之前發生，實時因果一致性(RTC)是增加了時間不可逆的約束。

沒有一致性比實時因果一致性(RTC)更強了，RTC能一邊提供可用性，一邊提供收斂性系統。

RTC的實現類似日志交換log-exchange協議，每個寫操作會產生一個帶有向量時鐘vector clock 或版本向量、對象標識和對象值三者結合的更新，向量時鐘決定更新的優先權，每個節點上的本地存儲跟蹤對每個對象的最近更新，當讀取一個對象o時，節點不需要任何通訊情況下從本地存儲返回最近更新給o，類似地，寫操作更新會被創建和加入到本地存儲和本地日志，節點之間會定期從它們的本地日志中交換這種更新。最新接受的更新會被追加到本地日志，這樣能夠用于更新節點的本地存儲，替換任何舊的更新，將在因果上優先于新的更新。

在我們實現中，每個節點定期發送它的日志到所有其他節點以確保單邊收斂，這種實現不需要任何節點之間通訊能確保讀寫完成，它是單邊收斂的原因是，因為接受來自一個發送者的更新能應用到接受者獲得收斂狀態，節點之間會定期廣播它們本地日志的所有更新。同時這也是因果一致性，因為向量時鐘攜帶了每次更新，能確保最新的寫操作被讀操作獲得（時間上先后）。最后，它是RTC實現，因為向量時鐘分配不會違反實時性要求，比如通過分配一個舊的向量時鐘給一個較新的更新。

責任編輯：

標簽：