分散式系統基礎理論（五）
本節開始概述 ofollow,noindex">Distributed systems for fun and profit 的第三章節，"Time and order"。
在單體應用中，所有操作之間都是有序的
無論是作業系統還是WEB框架，它們都對底層邏輯進行了很好的抽象。例如，由於作業系統對底層硬體的抽象，開發在寫程式碼時，無需考慮程序間的切換，程序間共享實體記憶體等問題。抽象的目的是為了保持程式設計模型的簡單，開發寫程式碼時，可以至上而下，一氣呵成。Every operation will have a well-defined predecessor and successor. That's basically the programming model that we've worked very hard to preserve.
雖然作業系統支援多執行緒程式設計（threaded-programming）或事件程式設計（event-programming），但是併發的執行緒之間是沒有因果關係的，這些操作的順序對最終結果也沒有影響。而且，作業系統還支援執行緒間同步，開發人員掌握著為所有操作進行序列化的能力。
在分佈系統中，所有操作之間不全是有序的
在分散式系統下，我們可以有兩種方式，使得所有操作之間都是有序的。
方法一：所有請求都先訪問結點A，A會為每一個請求都賦予唯一的遞增編號，那麼操作的順序問題可以得到解決。但是該方法也帶來了問題：1. 結點A存在單點故障；2. 網路IO劇增，系統性能受損；3. 影響系統的可擴充套件性。
方法二：每個結點上的時鐘系統是完全準確的（a completely accurate clock），那麼所有操作的順序可通過比較時間來裁決，且無需通訊。但是時鐘系統受物理材料的影響，本身是做不到完全準確的。通常，使用時鐘同步協議（clock synchronization protocol）NTP，能保證某種程度的準確（a limited degree of accuracy）。注意，即使定時通過NTP協議同步時鐘，也會有傳輸時延（最大時速為光速）。
總結：This order can be maintained on a distributed system, but at a cost: communication is expensive, and time synchronization is difficult and fragile.
Total and partial order
total order滿足以下三個條件：
- If a ≤ b and b ≤ a then a = b (antisymmetry，反對稱)
- If a ≤ b and b ≤ c then a ≤ c (transitivity，傳遞性)
- a ≤ b or b ≤ a (totality) for all a, b in X （任意兩個元素均可比較）
partial order 滿足反對稱性和傳遞性。即在結點內部的操作，兩者的順序是可以比較的；在結點之間的操作順序是不可比較的。
總結：在單體應用中，操作之間是全序關係；在分散式應用中，操作之間是偏序關係。
Timing assumptions
關於對時序的假設一般分為以下三種
- Time with a "global-clock" assumption
- 藉助NTP定時同步各個結點的時鐘；
- 排序操作時無需通訊（you can use timestamps freely to determine a global total order）
- 代表：Facebook'sCassandra，Google'sSpanner
- Time with a "Local-clock" assumption
- The local clock assumption corresponds more closely to the real world.
- you cannot meaningfully compare timestamps from two different machines.
- Time with a "No-clock" assumption
- we can use counters and communication to determine whether something happened before, after or concurrently with something else.
- events can be ordered on a single system using a counter and no communication, but ordering events across systems requires a message exchange.
- This is a partial order. 因為沒有發生訊息互動的操作之間是無法進行排序的。
- 代表：Cassandra's cousins Riak (Basho) and Voldemort (Linkedin)
系統模型
在 分散式系統基礎理論（三） 中，系統模型假設的餘地不多，包括：1. whether or not network partitions are included in the failure model；2. sync vs. async timing assumptions.
- 同步系統模型的定義（Synchronous system model）
- Processes execute in lock-step;
- there is a known upper bound on message transmission delay;
- each process has an accurate clock（ Time with a "global-clock" assumption ）
- 非同步系統模型的定義（Asynchronous system model）
- No timing assumptions, e.g. processes execute at independent rates
- no bound on message transmission delay;
- useful clocks do not exist（ Time with a "No-clock" assumption ）
注意，同步/非同步系統模型不但對時序進行了假設，同時也包含了對結點、網路的假設。
即使在一個全序（total order）的分散式系統中，也存在訊息丟失的可能。那麼，如何理解時序假設和網路假設之間的關係？
- 在全序模型中，結點可以對接收到的所有events進行排序，且無需額外通訊；
- 由於存在訊息丟失和延遲，所有結點不是在同一時間點，接收到該event的。有先有後
- 結點間仍需要藉助一致性協議，確保結點狀態的一致性。所以，某些events有可能雖然早早發生，但是在較晚時間達成了一致。