《雲數據管理：挑戰與機遇》2.1　向量時鍾

本節書摘來自華章出版社《雲數據管理》一書中的第2章，第1節，作者迪衛艾肯特·阿格拉沃爾，更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看

2.1.2　向量時鍾

邏輯時鍾可以捕獲潛在的因果關係，但是，這並不意味著一定有因果關係，邏輯時鍾條件隻是一個必要條件，並不是充分條件。分布式係統中的所有事件可能需要一個更強的時鍾條件：

e→f當且僅當clock(e)<clock(f)。

該條件可按如下方式實現：為每一進程i賦一個長度為n的向量Vi，n是係統中所有進程的數量。每一個執行的事件都被賦一個本地向量。

每個向量都初始化為0，即：Vi[j] = 0，其中i, j = 1, …, N。進程i在每一個事件之前增加本地向量元素的值，Vi[j] = Vi[j] +1。當進程i發送消息的時候，會將本地向量Vi和消息一起發送。當進程j接收消息時，會將接收向量和本地向量的元素逐個進行比較，並將本地向量設置為兩者之中較大的值，Vj[i] = max(Vi[i], Vj[i]), i = 1, …, N。

給定兩個向量V和V'，V=V'當且僅當V[i] = V'[i], i = 1, …, N，並且V≤V'當且僅當V[i]≤V'[i], i = 1, …, N。如果至少存在一個j(1≤j≤N)，使得V[j]<V'[j]，並且，對所有的i≠j，其中，1≤i≤N，V[i]≤V'[i]，則V<V'。對任意兩個事件e和f，e→f當且僅當V(e)<V(f)。如果既不滿足V(e)<V(f)，又不滿足V(f)<V(e)，那麼兩個事件是並發的。

圖2-3中，我們為圖2-1示例中的所有事件都賦了向量時間值。

 

圖2-3　向量時鍾

雖然向量時間可以準確地捕獲因果關係，但是向量的大小是網絡大小的函數，可能非常大，並且每一個消息都需要攜帶額外的向量