《雲資料管理：挑戰與機遇》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　向量時鐘

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