Time, Clocks, and the Ordering of Events in a Distributed System

文章目錄

• • 時間，時鐘，分布式系統中的事件順序
  • 偏序
  • 邏輯時鐘
  • 全部事件排序
  • 異常行為
  • 實體時鐘
  • 總結

時間，時鐘，分布式系統中的事件順序

https://www.cnblogs.com/hzmark/p/Time_Clocks_Ordering.html

https://zhuanlan.zhihu.com/p/401173606

https://zhuanlan.zhihu.com/p/34057588

https://zhuanlan.zhihu.com/p/27503041

        首先提出happen-before的概念，用來定義分布式系統中的偏序，再給出一套分布式算法同步邏輯時鐘以建構全序。全序可以解決同步問題，同步實體時鐘和限定實體時鐘的誤差。

        時間這一概念源自于事件的更替（事件發生順序）。如果與單個程序中事件發生的間隔時間相比，消息傳輸延遲不可忽略，則系統是分布式的。單機多處理系統所設計的問題和分布式系統的問題類似，因為某些事件的發生順序不可預測。分布式系統中事件順序很難确定，提出偏序概念，事件部分排序。

偏序

        實體時鐘不準确，定義偏序happen-before，定義事件，并用消息的發送和接受來定義事件的先後。

        我們假設a→a是不成立的（一個事件發生于自己之前顯得沒有什麼意義），那麼→是不具備自反性的偏序關系。

邏輯時鐘

        建構不依賴實體時間，依據事件順序來建構邏輯時鐘，可以采用計數器的實作方式。if a → b then C<a> < C<b>，需要注意的是我們不能期望這個條件的逆命題成立。Ci的值在發生事件時會改變，Ci的改變本身不包含事件。

        如果滿足一下兩個條件，那麼久滿足Clock Condition:

1. 如果a、b是同一個程序中的事件，且a發生在b之前，那麼C<a> < C<b>
2. 如果a、b是不同程序中的事件，且a是發送一條消息的事件，而b是接收這條消息的事件，那麼C<a> < C<b>

        為了滿足Clock Condition，我們需要確定滿足C1、C2條件:

1. IR1：任何一個程序Pi在兩個成功事件之間遞增Ci

2. 為了滿足C2，我們需要每條消息m包含一個時間戳Tm，Tm表示消息被發送的時間。收到該消息的程序需要将時鐘調整到大于Tm。更準确的，需要滿足一下規則：

   IR2：(a)如果事件a表示Pi程序發送消息m，那麼m包含一個時間戳Tm，Tm=Ci<a>。(b)程序Pj收到消息m，Pj需要将Cj設定為等于或大于目前值，且大于Tm的值。

全部事件排序

        分布式互斥算法，需要所有程序的積極參與，一個程序必須知道其他程序發出的所有指令，是以單個程序的失敗将使得其他程序無法執行狀态機指令。我們将觀察到，整個失敗的概念僅在實體時間的背景下才有意義。如果沒有實體時間，就無法将失敗的過程與僅在事件之間暫停的過程區分開來。使用者隻能因為等待響應時間過長而判斷系統“崩潰”。

異常行為

        當存在與本事件相關的外部事件，算法失效。兩種解決方案：

1. 将系統中必要的有關排序的資訊引入系統，A打電話時候将自己的時間戳帶過去

2. 建構一個滿足以下條件的時鐘系統，更強的時鐘條件

   如果a->b，那麼C<a> < C<b>，使用實體時鐘來避免異常行為

實體時鐘

總結

        happen-before定義偏序關系，将偏序擴充為全序的算法，展示算法在分布式互斥的應用。

        該算法定義的全序關系有些随意。當系統與使用者觀察到的順序不一緻時會産生異常行為。該問題可以通過使用一個被正确同步的實體時鐘系統來避免。我們的定理還展示了時鐘可以被同步到怎樣的程度。在分布式系統中，認識到事件的發生順序是隻是一個偏序關系是非常重要的。我們認為這個觀點對了解所有多程序的系統非常有幫助。它可以幫助人們了解多程序系統中的基本問題，撇開那些用于解決這些問題的各種機制。