最近在學(xué)習(xí)分布式系統(tǒng)的知識．在學(xué)習(xí)Raft算法時，看到其中有提到狀態(tài)機．于是就去研究了一下狀態(tài)機派歌，在研究狀態(tài)機的時候胶果，又看到其中提到Logic Clock．Google了一下，發(fā)現(xiàn)有一個很著名的就是Lamport大神提出的Lamport Clock,于是找了一下他的論文拜讀了一下．
這篇文章是我在讀完論文之后的總結(jié)．由于水平有限早抠，其中有些地方可能有錯誤．所以建議各位先讀原作，再來讀這篇文章，防止我誤人子弟．論文題目為:Time, Clocks, and the Ording of Events in a Distributed System
happened-before
我們先來介紹一下happened-before模型． 為什么需要這個模型呢游昼？ 因為在不同的機器上酱床，時間往往都不是相同的趟佃，盡管我們可能看起來相同昧捷，但是其中還是有微秒級的差距．在普通情況下可能沒什么關(guān)系，但是對于一個要處理高并發(fā)請求的分布式系統(tǒng)來說序矩，就很致命了．完全有可能就是由于這微秒級的差距跋破，導(dǎo)致事件是無序的．
比如說毒返，我們有三臺服務(wù)器，分別為A,B,C.服務(wù)器A和B向服務(wù)器C發(fā)送請求劲绪，然后服務(wù)器C對這些請求進行排序．假設(shè)沒有邏輯時鐘盆赤，那么服務(wù)器A和B向服務(wù)器C發(fā)送請求的時候，需要帶上從本機獲取的時間戳颤枪，否則就可能會由于網(wǎng)絡(luò)延時而造成服務(wù)器C進行錯誤的排序．
因為服務(wù)器發(fā)送請求時淑际，都是從本機上獲取時間戳．這本身又是一個問題．因為不同服務(wù)器上的時鐘都是不同的．假設(shè)同一時刻庸追，服務(wù)器A的時鐘是10:10,服務(wù)器B的時鐘是11:11，當(dāng)然這有點夸張读整，但是也是符合時鐘不相同的定義的．假設(shè)服務(wù)器A在這一時刻先讓服務(wù)器B向服務(wù)器C發(fā)送請求咱娶，隨后服務(wù)器A再發(fā)送．那么服務(wù)器C根據(jù)消息中的時間戳進行排序時强品，便會將服務(wù)器B的請求排在后面的榛，而服務(wù)器A的請求排在前面．我們可以看到逻锐，這和實際的發(fā)送順序是完全相反的．
為了解決這個問題，論文中就提出了happened-before模型．
那happened-before模型到底是什么呢晓淀？ 我們定義兩個時間如果符合下面的三個關(guān)系中的一個盏档，則其就有happened-before關(guān)系:
- 如果事件A和事件B都是相同進程發(fā)出的，并且事件A在事件B之前發(fā)生懦窘，則事件A happened before 事件B.
- 如果事件A在進程1上被發(fā)出畅涂，然后在進程B上被接收药有，作為事件B．那么事件A happened before 事件B.
- 如果事件A happened before事件B,事件B又happened before事件C, 那么事件A happened before事件C.
其他任何不滿足上述關(guān)系的事件，我們都稱這些事件為并發(fā)事件．
我們注意第一個關(guān)系苇经，重點是在相同進程中.由于是在相同進程中宦言，我們很容易就能知道事件A和事件B誰先誰后．
在第二個關(guān)系中奠旺，重點是在不同進程中，并且有發(fā)送－接收關(guān)系．這里不同進程并不一定是在同一臺機器上的兩個不同進程鄙信，一般是位于不同機器上的不同進程．因為實際上忿晕，如果是同一臺機器上的不同進程，那么我們還是能夠通過獲取時間戳的方式鸦采，來獲取事件的先后順序的．
第三個關(guān)系就很簡單了．
我們可以從上面三個關(guān)系中看到渔伯，我們并沒有涉及到物理時鐘．
邏輯時鐘
了解了happened-before模型之后，再來了解邏輯時鐘就很簡單了．在happened-before那節(jié)中选浑，我們看到了吐限，既不能使用獲取時間戳的方式來進行排序，又不能通過讓服務(wù)器C按照接收順序來作為排序順序．那我們到底應(yīng)該如何來排序呢？
這就要介紹我們的邏輯時鐘了．
邏輯時鐘就相當(dāng)于一個序號狐粱，就是現(xiàn)在我們統(tǒng)一給不同進程中的時間進行編號胆数，來代表其順序．
如果事件A happened before事件B，那么事件A的邏輯時鐘值就比事件B的邏輯時鐘值小蒋搜，也就是事件A的編號比事件B的編號小.
那么怎樣做到如果事件A happened before事件B判莉，那么事件A的邏輯時鐘值就比事件B的邏輯時鐘值小呢券盅？
分兩種情況討論．
事件A和事件B在相同的進程上
邏輯時鐘跟物理時鐘相比，它也是會"滴答"的娘侍，每滴答一次泳炉，邏輯時鐘值就加一．但是物理時鐘是每秒滴答一次花鹅，而邏輯時鐘可就不是了．我們可以自定義每隔多長時間滴答一次，一般會讓其足夠小容贝，做到事件B的邏輯時鐘值比事件A的邏輯時鐘值小．
其實這里我也挺困惑的．論文中并沒有說明我們要如何衡量應(yīng)該多長時間讓其滴答一次．如果我們設(shè)置的太大膏潮，就會造成相同進程上的不同事件具有相同的邏輯時鐘值满力，而違背了上面說的如果事件A happened before事件B油额，那么事件A的邏輯時鐘值就比事件B的邏輯時鐘值小，也就是事件A的編號比事件B的編號猩．
如果是每次一有事件發(fā)生掂僵，才滴答一次的話，那么在高并發(fā)的情況下幔睬，由于滴答的這個操作是串行的麻顶，必然會有性能問題．
這里如果有高人了解如何解決的話舱卡，還望告知一下．
事件A和事件B在不同的進程上
我們稱進程之間進行交互時，是發(fā)出的消息(message), 消息中會包含事件以及事件對應(yīng)的邏輯時鐘值．當(dāng)進程2收到進程發(fā)來的消息時宛瞄，它會比較消息中事件的邏輯時鐘值和當(dāng)前它的邏輯時鐘的值交胚，如果發(fā)現(xiàn)事件的邏輯時鐘值大于它的邏輯時鐘的值蝴簇，則將它的邏輯時鐘的值修改為事件的邏輯時鐘值+1．否則就不修改．
局部有序性
理解了上文的讀者，現(xiàn)在應(yīng)該已經(jīng)清楚如何通過邏輯時鐘來實現(xiàn)局部有序性的了．
我們還是通過夸張的方式來描述局部有序性．
假設(shè)我們設(shè)置的邏輯時鐘每隔十分鐘滴答一次.假設(shè)進程1在這十分鐘之內(nèi)給進程2發(fā)送了一個消息旁钧，其中包含事件A，以及其邏輯時鐘值6,進程2檢查其邏輯時鐘值嚎幸，發(fā)現(xiàn)其為7,于是不修改其邏輯時鐘值寄猩，直接將接收到的事件A作為它的事件B,設(shè)置其邏輯時鐘為7.
時鐘過去之后田篇，進程1又發(fā)生了一個事件C，這個事件只是一個進程內(nèi)部的事件泊柬，即其不會發(fā)送給進程2．那么這個事件C的邏輯時鐘值為7.
這里我們就能看到了椎镣，進程2上的事件B和進程1上的事件C具有相同的邏輯時鐘值7．但是由于它們沒有happened-before關(guān)系，因此沒有違背如果事件A happened before事件B兽赁，那么事件A的邏輯時鐘值就比事件B的邏輯時鐘值小状答，也就是事件A的編號比事件B的編號小．
你看刀崖，兩個不同的事件具有相同的邏輯時鐘值剪况，那排序的時候咋排? 無所謂啦，因為它們又不是相關(guān)的事件蒲跨，誰先誰后無所謂啦．
但是在排序的結(jié)果中，一定能夠保證具有happened-before關(guān)系的事件的前后關(guān)系．
這就實現(xiàn)了我們所說的局部有序性．
全局有序性
在有些情況下授翻，確實滿足局部有序性就好啦．但是或悲，有些情況下則不行．比如在狀態(tài)機中堪唐，我們必須找到一個確定的執(zhí)行序列．使不同機器上的狀態(tài)機最后都到達相同的狀態(tài)．如果狀態(tài)機1執(zhí)行A->B->C,狀態(tài)機2執(zhí)行A->C->B.那還了得巡语？
所以，論文中又在局部有限性的前提下淮菠，加了一個約束男公，就是如果兩個時間的邏輯時鐘值相同的話，那么由具有較小進程號的進程發(fā)出的事件排在前面．也就是說合陵，在局部有限性那一節(jié)的例子中枢赔，最終得到的排序序列為A->C->B.
其實這里是選取較小進程號還是較大進程號無所謂，只要能確定這么一個順序就好啦．
但是拥知，即使這樣還是有缺陷的．
使用物理時鐘來解決由于延時而造成排序錯誤的問題
比如從網(wǎng)上看到的一個例子踏拜，在一次用戶購買流程中，購買服務(wù)先向日志服務(wù)發(fā)送一個消息低剔，然后再向優(yōu)惠服務(wù)發(fā)送一個消息速梗，優(yōu)惠服務(wù)收到這個消息之后肮塞，再向日志服務(wù)發(fā)送一個消息．那么由于網(wǎng)絡(luò)延時，日志服務(wù)可能會先記錄優(yōu)惠服務(wù)發(fā)送的消息姻锁，其后才記錄購買服務(wù)發(fā)送的消息枕赵，這是完全錯誤的行為．
有兩張方式可以避免這種情況．第一種就是購買服務(wù)告訴優(yōu)惠服務(wù)它從優(yōu)惠服務(wù)的機器上獲取的時間戳，然后優(yōu)惠服務(wù)發(fā)送一個比這個更大的時間戳位隶，給日志服務(wù)拷窜，日志服務(wù)再根據(jù)時間戳來判斷先后．
但是這種方式需要用戶來編寫代碼來控制，不可鹊鍪浴．
另一種方式就是協(xié)調(diào)不同機器的時間的方式．
這種方式需要我們滿足兩個基本的條件:
- 機器上的物理時鐘和正確的物理時鐘之間的誤差很凶昂凇．注意機器上物理時鐘和正確的物理時鐘的差別．
- 不同機器間的物理時鐘的誤差很小
但是，即使?jié)M足了這兩個條件弓熏，也不能確保就能解決上面的那個問題．
因為不同機器上的滴答速度不相同恋谭，所以，不同機器上的物理時鐘的誤差可能會越來越大．
那什么時候能夠真正解決這個問題呢挽鞠？
不同機器間的物理時鐘的誤差 * ( 1 - 機器上物理時鐘跟正確的物理時鐘的誤差) <= 消息的最短傳輸時間．
具體的證明請各位自行查看論文．
