序

一些技術(shù)點(diǎn)仿佛俯拾皆是，但很少有時(shí)間有精力把他們串起來形成體系，進(jìn)而系統(tǒng)性地理解它們。象多人共著《深入分布式緩存》那樣多角度認(rèn)識緩存技術(shù)并不多見，“臨淵羨魚，不如退而結(jié)網(wǎng)”，石頭兄弟的這篇關(guān)于時(shí)間的文字成于去年，歷久反而彌新。

?[[315238]]?

目錄

1 什么是時(shí)間?

2 物理時(shí)間：墻上時(shí)鐘

3 邏輯時(shí)鐘：為事件定序

4 Turetime：物理時(shí)鐘回歸

5 區(qū)塊鏈：重新定義時(shí)間

6 其他影響

6.1 NTP的時(shí)間同步

6.2 有限時(shí)間內(nèi)的不可能性

6.3 延遲

6.4 租約

7 總結(jié)

8 參考文獻(xiàn)

?[[315239]]?

1 什么是時(shí)間?

時(shí)間是困擾了無數(shù)哲人的一個(gè)很抽象的概念。

偉人牛頓的絕對時(shí)空原理，可能代表了多數(shù)人的觀點(diǎn)——時(shí)間在整個(gè)宇宙中是一個(gè)不變常量：

• 在牛頓的時(shí)空觀念中，時(shí)間和空間是各自獨(dú)立的，沒有關(guān)聯(lián)的兩個(gè)事物。
• 絕對空間就像一間空房子，它區(qū)分物理事件發(fā)生的地點(diǎn)，用3維坐標(biāo)來描述。
• 絕對時(shí)間就像一個(gè)滴答作響的秒表，它區(qū)別物理事件發(fā)生的先后次序，用不可逆轉(zhuǎn)的1維坐標(biāo)來描述。

“牛頓以為他知道時(shí)間是什么”——有人調(diào)侃說。在牛頓的絕對時(shí)空里，時(shí)間的概念是恒定的，在整個(gè)宇宙中是一致的，時(shí)間是度量事件先后的依據(jù)。這非常像我們的一個(gè)單一計(jì)算機(jī)或者緊耦合的計(jì)算機(jī)集群里，時(shí)間是明確的，事件進(jìn)行的順序也是明確的。在計(jì)算機(jī)科學(xué)最初的幾十年里，我們從來沒有想過計(jì)算機(jī)之間的時(shí)間問題。

?[[315240]]?

另一位科學(xué)巨匠愛因斯坦，在他的狹義相對論中，主要有兩點(diǎn)：

• ? 物理定律，包括時(shí)間，對所有的觀察者來說是相同的。
• ? 光速不變。

而廣義相對論說，整個(gè)時(shí)空都是一個(gè)引力場，時(shí)間和空間都不是連續(xù)的。

狹義相對論的主要意義是沒有概念上的同時(shí)性，同時(shí)的概念相對于觀察者，時(shí)間的推移也相對于觀察者。同時(shí)，這一理論也說明了當(dāng)事情發(fā)生在遙遠(yuǎn)的地方，我們需要時(shí)間去發(fā)現(xiàn)事情是否真的發(fā)生了。這個(gè)等待的時(shí)間可能很長。

?[[315241]]?

分布式系統(tǒng)可能比愛因斯坦的宇宙還要糟糕。在分布式系統(tǒng)中，信息傳播所需要的時(shí)間范圍是不可預(yù)知的，可能遠(yuǎn)超過了陽光到達(dá)地球的8分鐘。在這段時(shí)間內(nèi)，無法知道網(wǎng)絡(luò)另一端的計(jì)算機(jī)發(fā)生了什么。就算你可以通過發(fā)送消息來詢問或探測，消息的投遞和反饋總是要花費(fèi)時(shí)間的。因此，系統(tǒng)延遲時(shí)間和超時(shí)值的設(shè)置是分布式系統(tǒng)的重要設(shè)計(jì)點(diǎn)之一。

“一切抽象都是數(shù)學(xué)，一切結(jié)論都是概率”，我們可以獲得一個(gè)信息傳播的統(tǒng)計(jì)結(jié)果，但無法知道每一次消息投遞的準(zhǔn)確時(shí)間。從這個(gè)角度上理解，分布式系統(tǒng)的正確運(yùn)行都是運(yùn)氣很好的概率上，概率小到我們認(rèn)為是高可靠的。

關(guān)于時(shí)間的本質(zhì)，馬赫(Ernst Mach)說：我們根本沒有能力以時(shí)間來測量事物的變化，相反的，我們是透過事物的變化因而產(chǎn)生時(shí)間流動的抽象概念。

在《七堂極簡物理課》中，作者指出：只有存在熱量的時(shí)候，過去和未來才有區(qū)別。能將過去和未來區(qū)分開來的基本現(xiàn)象就是熱量總是從熱的物體跑到冷的物體上。

所以，愛因斯坦說時(shí)間是幻像。從文學(xué)意義上說，不是時(shí)間定義了我們的生命，而是我們的生命定義了時(shí)間。

或許，這就是我們放棄物理時(shí)鐘，使用邏輯時(shí)鐘的背景吧!

2 物理時(shí)間：墻上時(shí)鐘

物理時(shí)間，在英文文獻(xiàn)中也稱為wall clock。wall time，也稱為真實(shí)世界的時(shí)間或掛鐘時(shí)間，是指由鐘表或掛鐘等計(jì)時(shí)器確定的經(jīng)過時(shí)間。(“wall”一詞最初得名于對掛鐘的引用。)

?[[315242]]?

在計(jì)算機(jī)的世界里，中心化系統(tǒng)的時(shí)間是明確的。例如進(jìn)程A和B分別在t1，t2時(shí)刻向系統(tǒng)的內(nèi)核發(fā)起獲得時(shí)間的系統(tǒng)調(diào)用，得到時(shí)間必然是t1

??

單機(jī)系統(tǒng)中的時(shí)間依賴于石英鐘，并且具有極小的時(shí)鐘漂移。

3 邏輯時(shí)鐘：為事件定序

分布式系統(tǒng)中的同步和異步都是對物理時(shí)間做的假設(shè)，但是，邏輯時(shí)鐘第一次擺脫了物理時(shí)鐘的限制。

邏輯時(shí)鐘認(rèn)為分布式系統(tǒng)中的機(jī)器可以無法對時(shí)間達(dá)成一致，但是對時(shí)間發(fā)生順序是一致認(rèn)同的。一個(gè)消息不能在被發(fā)送之前收到，這樣，如果一個(gè)進(jìn)程A向進(jìn)程B發(fā)送了消息，我們可以認(rèn)為A發(fā)生在B之前。

??

這樣就定義了分布式系統(tǒng)中不同節(jié)點(diǎn)上不同事件之間的因果關(guān)系，后來衍生的向量時(shí)鐘也是同樣的道理。

本質(zhì)上來說，邏輯時(shí)鐘定義了事件到整數(shù)值的映射。所以很多邏輯時(shí)鐘的實(shí)現(xiàn)都采用單調(diào)遞增的軟件計(jì)數(shù)器，這個(gè)計(jì)數(shù)器的值與任何物理時(shí)鐘都沒有關(guān)系。分布式系統(tǒng)中的節(jié)點(diǎn)和進(jìn)程在使用邏輯時(shí)鐘時(shí)，為事件加上邏輯時(shí)鐘的時(shí)間戳，比如文件讀寫和數(shù)據(jù)庫更新等。

邏輯時(shí)鐘的貢獻(xiàn)來自于Leslie Lamport在1978年發(fā)表的一篇論文《Time, Clocks, and the Ordering of Events in a Distributed System》。

??

4 Truetime：物理時(shí)鐘回歸

Google的Spanner提出了一種新的思路，在不進(jìn)行通信的情況下，利用高精度和可觀測誤差的本地時(shí)鐘 (TrueTime API)給事件打上時(shí)間戳，并且以此比較分布式系統(tǒng)中兩個(gè)事件的先后順序。利用這個(gè)方法，Spanner實(shí)現(xiàn)了事務(wù)之間的外部一致性(external consistency，如下圖所示)。

??

也就是說，一個(gè)事務(wù)結(jié)束后另一個(gè)事務(wù)才開始，Spanner可以保證第一個(gè)事務(wù)的時(shí)間戳比第二個(gè)事務(wù)的時(shí)間戳要早，從而兩個(gè)事務(wù)被序列化后也一定能保持正確的順序。

TrueTime API是一個(gè)提供本地時(shí)間的接口，但與Linux上gettimeofday接口不一樣，它除了可以返回一個(gè)時(shí)間戳t，還會給出一個(gè)誤差ε。例如，返 回的時(shí)間戳是1分30秒350毫秒，而誤差是5毫秒，那么真實(shí)的時(shí)間在1分30秒345毫秒到355毫秒之間。真實(shí)的系統(tǒng)中ε平均下來是4毫秒。

利用TrueTime API，Spanner可以保證給出事務(wù)標(biāo)記的時(shí)間戳介于事務(wù)開始的真實(shí)時(shí)間和事務(wù)結(jié)束的真實(shí)時(shí)間之間。假如事務(wù)開始時(shí)TrueTime API返回的時(shí)間是{t1, ε1}，此時(shí)真實(shí)時(shí)間在 t1-ε1到t1+ε1之間;事務(wù)結(jié)束時(shí)TrueTime API返回的時(shí)間是{t2, ε2}，此時(shí)真實(shí)時(shí)間在t2-ε2到t2+ε2之間。Spanner會在t1+ε1和t2-ε2之間選擇一個(gè)時(shí)間點(diǎn)作為事務(wù)的時(shí)間戳，但這需要保證 t1+ε1小于t2-ε2，為了保證這點(diǎn)，Spanner會在事務(wù)執(zhí)行過程中等待，直到t2-ε2大于t1+ε1時(shí)才提交事務(wù)。由此可以推導(dǎo)出，Spanner中一個(gè)事務(wù)至少需要2ε的時(shí)間(平均8毫秒)才能完成。

由此可見，這種新方法雖然避免了通信開銷，卻引入了等待時(shí)間。為了保證外部一致性，寫延遲是不可避免的，這也印證了CAP定理所揭示的法則，一致性與延遲之間是需要權(quán)衡的。

??

為什么Google要采用這樣設(shè)計(jì)呢?

Truetime根本上解決了什么問題?

Spanner是要解決全球規(guī)模分布式系統(tǒng)中關(guān)于時(shí)間的兩大難題：

1. 在數(shù)據(jù)中心之間同步時(shí)間是超級困難和不確定的
2. 在全球規(guī)模范圍內(nèi)序列化請求是不可能的

解決這些問題的辦法是接受不確定性，使用GPS和原子時(shí)鐘，把不確定性減低到最小。對于 Spanner這樣全球部署或者跨地域部署的系統(tǒng)，如何來為事務(wù)分配 timestamp, 才能保證系統(tǒng)的響應(yīng)時(shí)間在可接受的范圍內(nèi)? 如果整個(gè)系統(tǒng)采用一個(gè)中心節(jié)點(diǎn)來分配時(shí)間戳, 那么系統(tǒng)的響應(yīng)時(shí)間就變得非常不可控，對于離中心節(jié)點(diǎn)隔了半圈地球的用戶來說， 響應(yīng)時(shí)間估計(jì)會是100ms 級別。

如何理解turetime 呢?要弄明白truetime在事務(wù)操作中作用，首先看一下Spanner支持的幾種事務(wù)類型：

??

簡單只讀事務(wù)。Spanner設(shè)計(jì)的只讀事務(wù)有以下要求：

? 客戶程序自己實(shí)現(xiàn)重試動作

? 讀操作要顯式的聲明沒有寫(例如只讀打開一個(gè)文件)

? 系統(tǒng)無需獲得鎖，不阻塞讀過程中進(jìn)來的寫操作

? 系統(tǒng)自己選擇一個(gè)時(shí)間戳，用來確定讀取副本的時(shí)間戳

? 任何一個(gè)滿足時(shí)間戳的副本都可以用作讀操作

當(dāng)然，快照讀就更簡單了，無鎖的讀取過去的快照，客戶可以指定時(shí)間戳，也可以讓系統(tǒng)選擇一個(gè)時(shí)間戳，無需贅述。

讀寫事務(wù)則使用兩階段鎖，來保證外部一致性：

??

Spanner 利用truetime機(jī)制，把系統(tǒng)中的操作按照發(fā)生的先后順序，構(gòu)造一個(gè) Linearizability 的運(yùn)行記錄。所以，我們說Spanner是實(shí)現(xiàn)Linearizability的系統(tǒng)。

總結(jié)來說，Spanner 是采用全球同步(有一定誤差)的物理時(shí)間truttime戳作為系統(tǒng)的時(shí)間戳，并且作為系統(tǒng)內(nèi)各種操作的版本號。

5 區(qū)塊鏈：重新定義時(shí)間

中本聰在比特幣一文——《Bitcoin: A Peer-to-Peer Electronic Cash System》中提出了時(shí)間戳服務(wù)器模型，并奠定了區(qū)塊鏈的基礎(chǔ)。為了解決雙花問題，中本聰設(shè)想了一個(gè)去中心化的自驗(yàn)證體系：

在基于鑄幣的模型中，鑄幣方知道所有的交易并決定哪個(gè)先到達(dá)。要在沒有可信方的情況下完成此任務(wù)，必須公開宣布交易，并且我們需要一個(gè)系統(tǒng)，讓參與者就接收它們的順序的單一歷史記錄達(dá)成共識。收款人需要一個(gè)證明：對于一個(gè)交易，大多數(shù)節(jié)點(diǎn)都同意該交易是第一個(gè)收到的。

我們建議的解決方案是從時(shí)間戳服務(wù)器開始的。時(shí)間戳服務(wù)器的工作方式是獲取要加蓋時(shí)間戳的數(shù)據(jù)塊的散列，并廣泛地發(fā)布散列，就像在報(bào)紙或Usenet post上發(fā)布一樣。顯然，時(shí)間戳證明了數(shù)據(jù)必須在那個(gè)時(shí)候存在，以便進(jìn)入散列。每個(gè)時(shí)間戳散列包含前一個(gè)時(shí)間戳的散列，由此形成一個(gè)鏈，每個(gè)后續(xù)的時(shí)間戳都會增強(qiáng)前一個(gè)時(shí)間戳的有效性。

??

這樣，區(qū)塊鏈作為時(shí)間機(jī)器的滴答機(jī)制就形成了，一個(gè)區(qū)塊高度對應(yīng)一個(gè)時(shí)間窗口，這是為什么區(qū)塊鏈也被稱為時(shí)間機(jī)器的原因。為了讓時(shí)鐘跳動均勻，POW區(qū)塊鏈會自動調(diào)整算法難度，維持滴答周期在一個(gè)平均的物理時(shí)間范圍內(nèi)，比如比特幣是在10分鐘左右，以太坊在15秒左右。非POW的區(qū)塊鏈也維護(hù)這樣的時(shí)鐘滴答，比如filecoin測試網(wǎng)維護(hù)在45秒左右。

進(jìn)一步，非POW的區(qū)塊鏈維護(hù)固定的時(shí)鐘滴答是很難的，再以filecoin為例，采用在全網(wǎng)采用UTC時(shí)間戳(類似前面谷歌的做法)來實(shí)現(xiàn)固定的物理時(shí)間間隔，這要求全網(wǎng)的服務(wù)器都和NTP服務(wù)器同步，并限制了嚴(yán)格的時(shí)鐘飄移范圍(1s)。因?yàn)閰^(qū)塊鏈這樣的時(shí)間機(jī)器特性，才讓鏈上的數(shù)據(jù)在沒有分叉的情況下無法篡改。也正因?yàn)檫@樣，區(qū)塊鏈才讓人聯(lián)想到物理時(shí)間的消逝，熵的增加，能量的耗散，以及“青春散場、昨日不再”。

??

由區(qū)塊鏈的本質(zhì)引申開來，研究者試圖找到替代的解決方案。其中一個(gè)非常有吸引力的方案是VDF。VDF是 Verifiable Delay Function的縮寫，可驗(yàn)證延遲函數(shù)VDF的概念是斯坦福大學(xué)計(jì)算機(jī)科學(xué)和電子工程教授、計(jì)算機(jī)安全實(shí)驗(yàn)室聯(lián)合主任Dan Boneh在Crypto 2018大會發(fā)布的《Verifiable Delay Functions》論文中首次提出的。Function說明了VDF是一個(gè)函數(shù)，對每一個(gè)輸入都有一個(gè)唯一的輸出。Delay 可以用一個(gè)時(shí)間T(wall time)來表示，延遲函數(shù)在時(shí)間T完成計(jì)算，但不能通過并行加速在小于時(shí)間T完成計(jì)算。Verifiable 要求延遲函數(shù)的輸出非常容易驗(yàn)證。詳細(xì)請閱讀《Paxos、PoW、VDF：一條美麗的黃金線》一文。

Function:

§ unique output for everyinput

Delay:

§ can be evaluated in time T

§ can not be evaluated intime

Verifiable:

??

VDF計(jì)算過程最重要的一點(diǎn)是：在計(jì)算時(shí)要求大量計(jì)算資源，但驗(yàn)證時(shí)只需花費(fèi)相對少的計(jì)算資源。這樣的計(jì)算和驗(yàn)證的非對稱關(guān)系乍看起來有點(diǎn)像工作量證明(PoW)。于是，批評接踵而至：“ 聽起來我們又回到了工作量證明 ”，“ 不再燒一輪 CPU 我們就干不了這事是嗎 ?”——文獻(xiàn)《VDF不是工作量證明》一文指出：雖然 VDF 和傳統(tǒng)的 PoW 算法都擁有“難以計(jì)算”且“易于驗(yàn)證”這樣的屬性，最核心的區(qū)別在于，區(qū)塊鏈工作量證明的共識算法是可并行化的工作量證明，并且只是有概率會成功，不是一種函數(shù)。相反，VDF 是連續(xù)工作量證明，是確定的函數(shù)。

?[[315246]]?

關(guān)于VDF和PoW的區(qū)別，已有很多爭論?？傮w來說，PoW 直接作為隨機(jī)數(shù)的來源是有缺陷的，同時(shí)，VDF 也無法直接替代 PoW。但是，這并不能說明 VDF 不可以被用到共識協(xié)議里。原因如下：

? PoW 不抵抗并行計(jì)算加速而 VDF 是抵抗的。實(shí)際上，PoW 不抗并行計(jì)算加速是符合中本聰關(guān)于“一個(gè) CPU 一票”的設(shè)想的，而抗并行加速的性質(zhì)只會與這個(gè)目的背道而馳。VDF 會使得多 CPU 的計(jì)算者和單 CPU 的計(jì)算者相比幾乎沒有什么優(yōu)勢。

? 對于固定的難度設(shè)定 d，PoW 可以有很多合法的解，這也是保證 PoW 共識網(wǎng)絡(luò)擁有穩(wěn)定的吞吐量以及刺激礦工進(jìn)行競爭的前提。而對于給定輸入 x，VDF 擁有唯一的輸出(這也是為什么它被稱作函數(shù))。

總體來說，VDF很好的刻畫了區(qū)塊鏈對于時(shí)間滴答機(jī)制的本質(zhì)需求。在一些非PoW區(qū)塊鏈和非區(qū)塊鏈的領(lǐng)域，都有大量研究和探索，比如協(xié)議實(shí)驗(yàn)室和以太坊聯(lián)合成立的實(shí)驗(yàn)室，以及大量對VDF感興趣的項(xiàng)目。

注：filecoin的協(xié)議實(shí)現(xiàn)也在考慮VDF：

Future versions of the Filecoin protocol may use Verifiable Delay Functions (VDFs) to strongly enforce block time and fulfill this leader election requirement; we choose to explicitly assume clock synchrony until hardware VDF security has been proven more extensively.

??

6 其他影響

和影響人們的生活一樣，時(shí)間更是影響了計(jì)算機(jī)系統(tǒng)的方方面面，也自然影響了我們。

6.1 NTP的時(shí)間同步

在分布式系統(tǒng)中，關(guān)于時(shí)間的共識是非常困難的。不同機(jī)器中石英鐘的頻率可能不一致，這會導(dǎo)致不同機(jī)器中時(shí)間并不一致。為了同步不同機(jī)器中的時(shí)間，人們提出了NTP協(xié)議。這樣，一個(gè)機(jī)器的時(shí)間就會依賴于另外一個(gè)外部時(shí)鐘。

??

NTP協(xié)議基于這樣原理：網(wǎng)絡(luò)通信延遲來回是相等的。基于此可以獲得兩臺機(jī)器時(shí)間差值 。在NTP服務(wù)器(上)獲得的時(shí)間再加上(時(shí)間落后本機(jī))或減去(時(shí)間領(lǐng)先本機(jī))這個(gè)延遲就可以設(shè)置為本地的時(shí)間，由此獲得時(shí)間同步。

6.2 有限時(shí)間內(nèi)的不可能性

1985年，F(xiàn)ischer，Lynch和Patterson發(fā)布了他們著名FLP成果(Impossibility of distributed consensus with one faulty process)：在異步的系統(tǒng)中，如果存在進(jìn)程故障，系統(tǒng)是不可能達(dá)成一致的。FLP表明，當(dāng)至少有一個(gè)進(jìn)程可能崩潰時(shí)，沒有一種確定性地解決異步環(huán)境中共識問題的算法。在工程應(yīng)用中，這個(gè)理論也可以理解為：在不穩(wěn)定故障的異步系統(tǒng)中，不可能有一個(gè)完美的故障檢測器。

根本的原因在于時(shí)間。FLP結(jié)果并不意味著共識是無法達(dá)到的，只是在有限的時(shí)間內(nèi)并不總是可以達(dá)到的。同步系統(tǒng)在進(jìn)程和進(jìn)程計(jì)算之間為消息傳遞提供了一個(gè)已知的上限。異步系統(tǒng)沒有固定的上限。

在《分布式系統(tǒng)：概念與設(shè)計(jì)》一書中，作者針對FLP指出：在分布式系統(tǒng)中，并不是說，如果有一個(gè)進(jìn)程出現(xiàn)了故障，進(jìn)程就永遠(yuǎn)不可能達(dá)到共識。它允許我們達(dá)到共識的概率大于0，這也是與實(shí)際情況相符合的。例如現(xiàn)在運(yùn)行在廣域網(wǎng)上的分布式系統(tǒng)，都是異步的，但是事務(wù)系統(tǒng)這么多年來一直都能達(dá)到共識。

所以，F(xiàn)LP表述為：在有限的時(shí)間內(nèi)，不可能達(dá)成一致。系統(tǒng)可能或者極有可能達(dá)成一致，但這不是保證的。也就是說, 在異步的系統(tǒng)中，有限時(shí)間內(nèi)達(dá)到一致性是不可能的。在分布式計(jì)算上，試圖在異步系統(tǒng)和不可靠的通道上達(dá)到一致性是不可能的。

因此，一般的一致性前提都是要求保證：在這里我們不考慮拜占庭類型的錯(cuò)誤，同時(shí)假設(shè)消息系統(tǒng)是可靠的。因此，對一致性的研究一般假設(shè)信道是可靠的，或不存在異步系統(tǒng)在運(yùn)行。

?[[315248]]?

概率，深刻的影響著分布式系統(tǒng)可靠性。世界的概率本質(zhì)雖然不能讓我們準(zhǔn)確的推斷未來，但是對于預(yù)測消息是否準(zhǔn)確傳遞卻綽綽有余。想一想，我們知道在有限時(shí)間內(nèi)達(dá)到絕對的一致性是不可能的，那為什么程序員自信的設(shè)置超時(shí)值為5秒呢?

就像這個(gè)世界的概率本質(zhì)一樣，分布式系統(tǒng)同樣構(gòu)建在概率的基礎(chǔ)之上。

6.3 延遲

很多人把延遲歸類到網(wǎng)絡(luò)延遲，指數(shù)據(jù)在傳輸介質(zhì)中傳輸所用的時(shí)間，即從報(bào)文開始進(jìn)入網(wǎng)絡(luò)到它開始離開網(wǎng)絡(luò)之間的時(shí)間。實(shí)際上，在計(jì)算機(jī)世界里，延遲無所不在。

除了VDF之外，程序員可能還要知道下面的這些時(shí)間數(shù)字：

• L1 cache reference ......................... 0.5 ns
• Branch mispredict ............................ 5 ns
• L2 cache reference ........................... 7 ns
• Mutex lock/unlock ........................... 25 ns
• Main memory reference ...................... 100 ns
• Compress 1K bytes with Zippy ............. 3,000 ns = 3 μs
• Send 2K bytes over 1 Gbps network ....... 20,000 ns = 20 μs
• SSD random read ........................ 150,000 ns = 150 μs
• Read 1 MB sequentially from memory ..... 250,000 ns = 250 μs
• Round trip within same datacenter ...... 500,000 ns = 0.5 ms
• Read 1 MB sequentially from SSD* ..... 1,000,000 ns = 1 ms
• Disk seek ........................... 10,000,000 ns = 10 ms
• Read 1 MB sequentially from disk .... 20,000,000 ns = 20 ms
• Send packet CA->Netherlands->CA .... 150,000,000 ns = 150 ms
• ......

?[[315249]]?

6.4 租約

租約(lease)在分布式系統(tǒng)中的一般描述如下：

• 租約是由授權(quán)者授予的在一段時(shí)間內(nèi)的承諾。
• 授權(quán)者一旦發(fā)出租約，則無論接受方是否收到，也無論后續(xù)接收方處于何種狀態(tài)，只要租約 不過期，授權(quán)者一定遵守承諾，按承諾的時(shí)間、內(nèi)容執(zhí)行。
• 接收方在有效期內(nèi)可以使用授權(quán)者的承諾，只要租約過期，接收方將放棄授權(quán)，不再繼續(xù)執(zhí)行，如果重新執(zhí)行需要重新申請租約。
• 通過版本號、時(shí)間周期，或者到某個(gè)固定時(shí)間點(diǎn)認(rèn)為租約的證書失效

租約可以說是分布式系統(tǒng)的心跳機(jī)制。在分布式系統(tǒng)中，像分布式鎖，集群leader這樣角色，可能隨時(shí)變化。為了避免死鎖，或者錯(cuò)誤的leader認(rèn)知，一般都要設(shè)計(jì)租約機(jī)制。

?[[315250]]?

7 總結(jié)

本文主要回顧了計(jì)算機(jī)系統(tǒng)演進(jìn)過程中的時(shí)間問題，特別是古典分布式系統(tǒng)的時(shí)間問題，以及由時(shí)間帶來的順序問題;探討了最新支持拜占庭容錯(cuò)的區(qū)塊鏈網(wǎng)絡(luò)系統(tǒng)的時(shí)間本質(zhì)，以及在可驗(yàn)證延遲函數(shù)方面的最新探索。

目前的分布式系統(tǒng)無法超越時(shí)空的限制來運(yùn)行，系統(tǒng)的設(shè)計(jì)也受到時(shí)空考慮范圍的約束。而未來，量子計(jì)算機(jī)將會在時(shí)空約束方面帶來哪些改變，值得期待。