本文是Distributed systems for fun and profit的第三部分贮尖，本文是閱讀該文后的一些記錄既们。
Time and order
先來看第一個(gè)問題：
What is order and why is it important?
為什么我們要關(guān)心是否 A happened before B?
回答這個(gè)問題之前，我們先來看下分布式編程的定義酷含。
the art of solving the same problem that you can solve on a single computer using multiple computers.
在單機(jī)系統(tǒng)中香璃，傳統(tǒng)的模式是： a single program, one process, one memory space running on one CPU删窒。我們做了很多努力來給編程者提供一種簡單的編程模型，一種順序執(zhí)行的模型颠毙，讓程序?qū)嶋H執(zhí)行的順序就是代碼的順序斯入。
但是我們一旦來到分布式環(huán)境中，我們卻發(fā)現(xiàn)再也沒有這種簡單的編程模型了蛀蜜，程序?qū)嶋H執(zhí)行的順序你忽然間就無法預(yù)測(cè)了刻两，因?yàn)槊總€(gè)節(jié)點(diǎn)時(shí)鐘不是嚴(yán)格同步的，當(dāng)然你可以去用復(fù)雜的技術(shù)來實(shí)現(xiàn)所有節(jié)點(diǎn)的時(shí)鐘同步滴某，然后給予每個(gè)操作一個(gè)時(shí)間戳磅摹，從而得到一個(gè)全局的total order；另一個(gè)思路是通過一個(gè)communication system霎奢，給每個(gè)操作都編號(hào)户誓，從而得到一個(gè)順序，但是就像我們之前說的一樣幕侠，在分布式系統(tǒng)中帝美，通信是不可靠的，您不可能確定的知道另外一個(gè)節(jié)點(diǎn)的狀態(tài)橙依，我們可以看到以上兩種方法都很難证舟。
Total and partial order
在分布式環(huán)境中一種常見的狀態(tài)是：partial order硕旗，即部分有，在集合中不是任意兩個(gè)元素都是可比較的女责。
Total 和 partial order 都滿足 自反性和傳遞性漆枚。
If a ≤ b and b ≤ a then a = b
(antisymmetry);
If a ≤ b and b ≤ c then a ≤ c
(transitivity);
total order還滿足：
a ≤ b or b ≤ a (totality) for all a, b in X
即所有集合中的元素都是有序的，而partial order則：
a ≤ a (reflexivity) for all a in X
即集合中的元素不是都有序抵知，只滿足自反性墙基。
在單機(jī)系統(tǒng)中，所有的指令和消息的執(zhí)行都是可預(yù)測(cè)的刷喜，是有一個(gè)total order的残制，因此程序的行為是可預(yù)測(cè)的，但是在分布式系統(tǒng)中想要實(shí)現(xiàn)total order掖疮，代價(jià)是巨大的初茶，因?yàn)?/p>
communication is expensive, and time synchronization is di?cult and fragile
What is time?
Time is a source of order - it allows us to de?ne the order of operations- which coincidentally also has an interpretation that people can understand (a second, a minute, a day and so on).
什么是時(shí)間？時(shí)間有時(shí)候就像一個(gè)計(jì)數(shù)器浊闪，只不過時(shí)間這個(gè)計(jì)數(shù)器比較重要恼布，我們用這個(gè)計(jì)數(shù)器產(chǎn)生的數(shù)值來定義整個(gè)人類的最重要的概念：時(shí)間。
Timestamps really are a shorthand value for representing the state of the world from the start of the universe to the current moment - if something occurred at a particular timestamp, then it was potentially in?uenced by everything that happened before it.
什么是時(shí)間戳（Timestamps）搁宾，Timestamps定義了世界從初始到現(xiàn)在的狀態(tài)折汞，如果某件事發(fā)生在一個(gè)特定的時(shí)間點(diǎn)上，是之前影響產(chǎn)生的結(jié)果盖腿。
此處有個(gè)大前提爽待，所有的時(shí)間都以相同的速率前行著，time and timestamps在程序中應(yīng)用的時(shí)候翩腐，有3個(gè)常用的解釋：
- Order
- Duration
- Interpretation
當(dāng)我說：time is a source of order鸟款，我指的是：
- we can attach timestamps to unordered events to order them【通過給事件安排一個(gè)時(shí)間戳，從而給事件排序】
- we can use timestamps to enforce a speci?c ordering of operations or the delivery of messages (for example, by delaying an operation if it arrives out of order)【我們可以通過時(shí)間戳給操作重新排序】
- we can use the value of a timestamp to determine whether something happened chronologically before something else【通過時(shí)間戳知道哪個(gè)事件發(fā)生在前】
Interpretation - time as a universally comparable value.
時(shí)間戳的絕對(duì)值解釋為日期（date）栗菜，對(duì)人們非常有用的概念
Duration - durations measured in time have some relation to the real world.
像算法一般只關(guān)心Duration欠雌，通過Duration來判斷延遲，一個(gè)好的算法都希望能有低延遲疙筹。
Does time progress at the same rate everywhere?
對(duì)于問題：時(shí)間以同樣的速率進(jìn)行嗎富俄？有3個(gè)常見的回答：
- "Global clock": yes
- "Local clock": no, but
- "No clock": no!
以上回答的的意思是：
- the synchronous system model has a global clock,
- the partially synchronous model has a local clock, and
- in the asynchronous system model one cannot use clocks at all
下面分別來看下
Time with a "global-clock" assumption
全局時(shí)鐘（global-clock）假設(shè)是我們有個(gè)非常精確的時(shí)鐘，我們?nèi)魏稳嗽谌魏蔚胤蕉寄芸吹剿亍＿@也是平時(shí)生活中我們最習(xí)以為常的時(shí)鐘霍比，對(duì)于不同時(shí)鐘間微小的差別我們并不關(guān)注。
在實(shí)際系統(tǒng)中暴备，如果我們假設(shè)有個(gè)global-clock悠瞬，即每個(gè)節(jié)點(diǎn)的時(shí)鐘都是同步的，那么我們可以通過timestamps都就可以得到一個(gè)total order，但是在系統(tǒng)間維持時(shí)鐘同步是非常難的浅妆，我們只能做到一定的范圍內(nèi)的同步望迎。
目前忽略時(shí)鐘之間的不同步問題做出來的系統(tǒng)有：
- Facebook's Cassandra：通過時(shí)間戳來解決沖突
- Google's Spanner：時(shí)間戳+偏差范圍來定義順序
Time with a "Local-clock" assumption
它假設(shè)了一個(gè)偏序關(guān)系
events on each system are ordered but events cannot be ordered across systems by only using a clock.
同一個(gè)機(jī)器上我們可以通過時(shí)間戳來排序，但是不同機(jī)器上的時(shí)間戳不能比較
Time with a "No-clock" assumption
不在使用時(shí)間戳凌外，而是使用counter辩尊，通過傳遞消息來交換counter，從而定義不同機(jī)器之間的事件的前后順序康辑，比較有名的論文就是：time, clocks and the ordering of events摄欲。
How is time used in a distributed system?
時(shí)間的好處是：
- Time can de?ne order across a system (without communication)
- Time can de?ne boundary conditions for algorithms
在分布式系統(tǒng)中，定義事件的順序非常重要疮薇，因?yàn)椋?/p>
- where correctness depends on (agreement on) correct event ordering, for example serializability in a distributed database【正確性依賴于事件的順序】
- order can be used as a tie breaker when resource contention occurs, for example if there are two orders for a widget, ful?ll the ?rst and cancel the second one【當(dāng)發(fā)生資源爭(zhēng)用的時(shí)候可以用來做裁決】
當(dāng)我們有全局時(shí)鐘的時(shí)候胸墙，我們不需要通信就能夠確定順序，不幸的是按咒，我們一般都沒有全局時(shí)鐘迟隅，因此只能通過通信來確定時(shí)序。
時(shí)間除了用來確定時(shí)序外励七，還能定義算法的邊界玻淑，特別是可以區(qū)分 high latency 和 server or network link is down，而用來探測(cè)它倆區(qū)別的算法就是：failure detectors呀伙。
Failure detectors (time for cuto?)
在分布式環(huán)境中，我們?cè)趺粗酪粋€(gè)節(jié)點(diǎn)是否宕機(jī)了呢添坊？我們可以通過等待一定時(shí)間后認(rèn)為節(jié)點(diǎn)失敗了剿另。
那問題是這個(gè)一定時(shí)間是多久呢？
這依賴于節(jié)點(diǎn)之間的延遲贬蛙，算法一般不會(huì)直接設(shè)置一個(gè)精確的值雨女，而是會(huì)對(duì)“一定時(shí)間”這個(gè)概念做個(gè)很好的抽象。
A failure detector is a way to abstract away the exact timing assumptions. Failure detectors are implemented using heartbeat messages and timers. Processes exchange heartbeat messages. If a message response is not received before the timeout occurs, then the process suspects the other process.
而failure detector是一個(gè)解決方案阳准，通過心挑信息來探測(cè)存活性氛堕。
