基本概念可以查看下面的參考鏈接
Lamport Lock
一張圖表示自己的理解：
Vector clock
上圖可以看出，ta<tb并不能推出a happens before b
vector clock的引進(jìn)就是來(lái)解決這個(gè)問(wèn)題的
簡(jiǎn)單比較
1.如何比較大??？
vector clock:
vp<vq 如果 vp[i] < vq[i] 對(duì)所有i均成立
存在i 使得vp[i] < vq[i] and 存在j 使得 vp[j]>vq[j]那么就是并發(fā)的
lamport clock:
(p,i)<(q,j)如果i<j;(p,i)<(q,i)如果p<q
2、全序？偏序？
vector clock 是偏序關(guān)系；lamport clock是全序關(guān)系
應(yīng)用
那么這么一個(gè)算法本質(zhì)上是為了給分布式系統(tǒng)提供全局的邏輯時(shí)鐘，保證各個(gè)副本執(zhí)行的操作是一樣的。
再舉例之前，先做幾點(diǎn)說(shuō)明：
1、參考原始論文的5條規(guī)則（參考鏈接1）
1.首先，每個(gè)進(jìn)程會(huì)維護(hù)各自在本地維護(hù)一個(gè)請(qǐng)求隊(duì)列。算法是由如下5個(gè)規(guī)則定義的。方便起見(jiàn)，每條規(guī)則定義的行為會(huì)被做為一個(gè)獨(dú)立事件。
為請(qǐng)求該項(xiàng)資源（在這個(gè)問(wèn)題中，資源就是日志服務(wù)器），進(jìn)程Pi發(fā)送一個(gè)(Tm,Pi)
2.資源請(qǐng)求消息給其他所有進(jìn)程，并將該消息放入自己的請(qǐng)求隊(duì)列，在這里Tm代表了消息的時(shí)間戳
3.當(dāng)進(jìn)程Pj收到(Tm,Pi)資源請(qǐng)求消息后，將它放到自己的請(qǐng)求隊(duì)列中，并發(fā)送一個(gè)帶時(shí)間戳的確認(rèn)消息給Pi。(注：如果Pj已經(jīng)發(fā)送了一個(gè)時(shí)間戳大于Tm的消息，那就可以不發(fā)送)
4.釋放該項(xiàng)資源時(shí)，進(jìn)程Pi從自己的消息隊(duì)列中刪除(Tm,Pi)資源請(qǐng)求，同時(shí)給其他所有進(jìn)程發(fā)送一個(gè)帶有時(shí)間戳的Pi資源釋放消息
5.當(dāng)進(jìn)程Pj收到Pi資源釋放消息后，它就從自己的消息隊(duì)列中刪除(Tm,Pi)資源請(qǐng)求
當(dāng)同時(shí)滿(mǎn)足如下兩個(gè)條件時(shí)，就將資源分配給進(jìn)程Pi：
(i)按照“=>”關(guān)系排序后，(Tm,Pi)資源請(qǐng)求排在它的請(qǐng)求隊(duì)列的最前面
(ii)Pi已經(jīng)從所有其他進(jìn)程都收到了時(shí)間戳>Tm的消息
2、在利用Lamport Timestamp實(shí)現(xiàn)全序組播時(shí)，要遵循如下假設(shè)：
(1)進(jìn)程Pj在接收進(jìn)程Pi的消息時(shí)，Pj對(duì)消息的接收順序與Pi發(fā)送消息的順序一致
(2)任何傳輸?shù)南⒉粫?huì)丟失
例子：
一個(gè)等價(jià)的問(wèn)題就是如何在分布式系統(tǒng)下實(shí)現(xiàn)全序組播(totally-ordered mulitcast)。這個(gè)可以利用Lamport提出的邏輯時(shí)鐘實(shí)現(xiàn)。
保證全序組播的具體算法為：
每一個(gè)進(jìn)程都維護(hù)一個(gè)本地請(qǐng)求隊(duì)列(Request Queue)，此隊(duì)列里的消息按時(shí)間戳排序。
進(jìn)程Pi給消息m加上時(shí)間戳Ti(m)，并廣播給所有進(jìn)程(包括Pi);
進(jìn)程Pj接收到消息m后，首先更新本地邏輯時(shí)鐘，并把消息m加入請(qǐng)求隊(duì)列，然后向
所有進(jìn)程（包括Pj）廣播接收到消息m的確認(rèn)信息ACK。
當(dāng)進(jìn)程的請(qǐng)求隊(duì)列中的某個(gè)消息位于隊(duì)列頂部，且已經(jīng)收到所有進(jìn)程關(guān)于此消息的
確認(rèn)信息ACK時(shí)，可以把此消息從隊(duì)列頂部取走，并傳給應(yīng)用程序。
上述算法結(jié)合假設(shè)，可以證明所有進(jìn)程都按相同的順序執(zhí)行一組操作。
證明中的關(guān)鍵點(diǎn)：
當(dāng)進(jìn)程Pi收到所有關(guān)于消息m的確認(rèn)信息ACK時(shí)，
首先，可以確認(rèn)其他進(jìn)程已經(jīng)收到了消息m；
其次，可以確認(rèn)其他進(jìn)程中“在關(guān)于消息m確認(rèn)信息ACK之前發(fā)的消息”進(jìn)程Pi都
已接收（這個(gè)可以從假設(shè)得到）。這表明如果存在需要在消息m之前執(zhí)行的消息，
進(jìn)程Pi已經(jīng)接收了，否則與假設(shè)矛盾。結(jié)合消息的執(zhí)行條件，就能保證消息m不會(huì)
被提前執(zhí)行。
最后，由于每個(gè)進(jìn)程是等價(jià)的，所以每個(gè)進(jìn)程的請(qǐng)求隊(duì)列都是一致的。
例子2:
其實(shí)logic clock要解決的問(wèn)題就是多點(diǎn)共同更新的問(wèn)題，每個(gè)節(jié)點(diǎn)都保存有完整數(shù)據(jù)，所以操作要全局同步。
比如，lamport clock就是保證每個(gè)節(jié)點(diǎn)的任務(wù)隊(duì)列的一致性，當(dāng)然原始paper有一些假設(shè)和規(guī)則來(lái)達(dá)到這個(gè)目的，不過(guò)思想是沒(méi)問(wèn)題的。
比如上面的例子同樣適用于多點(diǎn)更新（如銀行數(shù)據(jù)），只需要利用上面算法保證每個(gè)節(jié)點(diǎn)事務(wù)執(zhí)行的順序就行了
小結(jié)
- 可以看出，上述算法都是固定的線(xiàn)程數(shù)
- 如果有一個(gè)hang住了，系統(tǒng)會(huì)阻塞
- 解決的是最終一致性問(wèn)題
- 關(guān)于vector的應(yīng)用優(yōu)勢(shì)：
vector clock是logic clock的一種,并且是目前被證明的能精確進(jìn)行沖突檢測(cè)的最有效的數(shù)據(jù)結(jié)構(gòu)(有沒(méi)有更有效的?答案是有,后面會(huì)介紹,但是精確度會(huì)下降).它的原理就是所有允許寫(xiě)入的節(jié)點(diǎn)維護(hù)一個(gè)counter,每次本地提交的動(dòng)作會(huì)導(dǎo)致value+1并把這個(gè)值由本次操作攜帶,同步到其他節(jié)點(diǎn)去.遠(yuǎn)端節(jié)點(diǎn)在收到請(qǐng)求后也會(huì)為該操作分配一個(gè)本節(jié)點(diǎn)最新的counter.所以某個(gè)操作會(huì)在N-master集群中得到一個(gè)N個(gè)值的數(shù)組,只有當(dāng)所有節(jié)點(diǎn)上的操作A的counter都小于對(duì)應(yīng)節(jié)點(diǎn)上操作B的counter的時(shí)候才認(rèn)為他們具有明確的happen-before,否則視為沖突.
而我們所說(shuō)的Lamport clock是一種scalar clock,可以決定時(shí)序,但是任何的scalar clock并不能檢測(cè)沖突.因?yàn)閏ounter(A)<counter(B)并不能要求A操作先于B.所以在Lamport clock中即使產(chǎn)生并發(fā),也有可能是有序的,無(wú)法檢測(cè)到.這是dynamo系統(tǒng)不允許發(fā)生的,所以這類(lèi)系統(tǒng)會(huì)考慮使用vector clock.
vector clock有一個(gè)很大的缺點(diǎn)是不夠高效,因?yàn)镹-master集群需要N個(gè)元素來(lái)做判斷,這對(duì)于集群的拓展會(huì)有損害.對(duì)于消息傳遞需要攜帶過(guò)多的payload也是不小的開(kāi)銷(xiāo).這時(shí)候又出現(xiàn)了一種plausible clocks,可以在常量個(gè)vector元素的情況下,很高概率檢測(cè)出來(lái)沖突,但并不是100%.但是這種模型只適合用于對(duì)于并發(fā)進(jìn)行排序會(huì)提升效率的系統(tǒng)中,而不是影響正確性的系統(tǒng)中.
參考
Lamport大師的論文
Seif Haridi
logical clock lmaport vector-一個(gè)簡(jiǎn)單的pdf教程
國(guó)人解釋?zhuān)梢詤⒖?/a>
分布式系統(tǒng)一致性系列
