向量時鐘解決資料一緻性

向量時鐘解決資料一緻性

向量時鐘簡介

向量時鐘，最早是用于分布式系統中程序間的時間同步。由于在分布式系統中沒有一個直接的全局邏輯時鐘。在一個由n個并發程序構成的系統中，每個事件的邏輯時鐘均由一個n維向量（n元組）構成，其中第i維（分量）對應于第i個程序的邏輯時鐘Vi

向量時鐘的維護方法：

*初值

*第i個程序在事件發生時，繼承上一事件的邏輯時鐘并将自身所對應的分量Vi增加一個步長

*任何程序Pi在發出任何消息m時都要将自己目前的邏輯時鐘分量Vi一起發送出去

*如果是接收事件，且發送方為j，則比較自己繼承的Vj和收到的邏輯時鐘，并取其中較大者為自己的Vj

形式化表示如下：

在向量時鐘方法中，每個程序Pi和一個向量LCi[1...n]相關聯，其中

* LCi[i]描述了程序Pi，即自身程序

* LCi[j]表示Pi關于Pj程序的知識

* LCi[1...n]組成Pi對于邏輯全局時間的局部視圖

對每一個程序LCi的更新規則如下

*規則1：在發生一個事件（一個外部發送或内部事件）之前，我們更新LCi[i]:

LCi[i] := LCi[i] + d (d > 0)

*規則2：每個消息捎帶發送方在發送時的向量時鐘。當接收到一個消息（m, LCj, j）時，Pi執行更新：

LCi[k] := max(LCi[k], LCj[k]), 1

LCi[i] := LCi[i]+d

下圖為增量值d=1，初始值init=0時的示例圖

資料一緻性（Quorum）

定義

N：系統中資料的備份數

R：讀取操作最小成功數

W：寫操作最小成功數

要求：R+W>N

配置

R+W>N，保證讀操作至少能讀取到一個最新資料

讀寫速度受性能最差的節點影響

R和W越小，系統的響應越快

W越大，資料的一緻性，可用性越強

通常：N=3， R=W=2

時鐘向量與資料沖突處理

*将上述向量時鐘應用到解決資料一緻性的問題上來

*向量時鐘在分布式環境中表示對象或事件的邏輯關系

*分布式系統中每個消息都附加Vector Clock的資訊

*當某個節點内部處理一個事件時，将其自身對應的counter加1

*節點發送一個消息前，将其自身對應的counter加1

*節點收到一個消息時，将其自身對應的counter加1；同時，根據消息中的Vector Clock資訊更新所有其他counter

在Dynamo系統中為了可用性，是以對一緻性的限制做了妥協。使得整個系統對“寫”一直是可用的，而将資料不一緻性的處理部分放到了用戶端程式讀資料時再進行處理。

在用戶端使用get擷取資料時，coordinator對node傳回資料依據時鐘向量進行version處理。如果資料一緻則将取得的值傳回給用戶端。如果資料沖突，則将所有資料傳回給用戶端，由用戶端進行解決。