2（C根據排列組合，一共產生了8種可能性，其中NTP（NetworkTimeProtocol）誤差大，也不能保證單調遞增，所以就沒有單獨使用NTP的產品；還有一些方案在實踐中則是不適用的（N/A）。因此常見的方案主要只有4類，我畫了張表格，總結了一下。r采用的方案是e。它的時間源是GPS就像這一講開頭說的，TrueTime是會出現時光倒流的。例如，A、B兩個進程先后調用TrueTimeB于A的時間。不只是TrueTime，任何物理時鐘都會存在時鐘偏移甚至回撥。TrueTimeCockroachDB和YgabytB也是以高性能高可靠和全球化部署為目標，不過e是的獨門絕技，它依賴于特定硬件設備的思路，不適用于開源軟件。所以，它們使用了混合邏輯時鐘（idlCloc，HC），同樣是多時間源、多點授時，但時鐘采用了物理時鐘與邏輯時鐘混合的方式。LCe同樣有整體性的時間誤差。對于這個共性問題，Spanner和CockroachDB都會通過一些容錯設計來消除時間誤差，我會在第12講中具體介紹相關內容。其他的分布式數據庫大多選擇了單時間源、單點授時的方式，承擔這個功能的組件在NewQL風格架構中往往被稱為OampOrac），而在PGXCsnnagerGM）。這就是說一個單點遞增的時間戳和全局事務號基本是等效的。這種授時機制的最大優點就是實現簡便，如果能夠保證時鐘單調遞增，還可以簡化事務時的設計。但缺點也很明顯，集群不能大范圍部署，同時性能也有上限。BOcenBasGoldenB和e最后，還有一些小眾的方案，比如巨杉的STP(SequoiaDBTimeProtoco)。它采用了單時間源、多點授時的方式，優缺點介于HLC和TSO之間。到這里，我已經介紹了4種方案在技術路線上大致的區別。其中TrueTime是基于物理設備的外部授時方案，所以Spanner直接使用就可以了，自身不需要做專門的設計。而對于其他3種方案，如果我們想要深入理解，那么還得結合具體的產品來看。首先，我們從最簡單的TSO最早提出TSO的，大概是的 Large-scaleIncrementalProcessingUsingDistributedTransactionsandNotifications”。這篇 系統Percolator的實現機制，其中提到通過一臺Oracle為集群提供集中授時服務，稱為TimestampOracle。所以，后來的很多分布式系統也用它的縮寫來命名自己的單點授時機制，比如TiDB和Yahoo的Omid。考慮到TiDBTiDBTiDB的全局時鐘是一個數值，它由兩部分構成，其中是物理時間，也就是操作系統的毫秒時間；低位是邏輯時間，是一個18位的數值。那么從空間看，1毫秒最多可以產生262,144個時間戳（2^18），這已經是一個很大的數字了，一般來說足夠使用了。cementDriver，PDPDRaft那問題來了，如何保證新主產生的時間戳一定大于舊主呢？那就必須將舊主的時間戳起來，也必須是高可靠以B使用了d保存嗎？顯然不行，那樣時間戳的產生速度直接與磁盤I/O當前PD（主節點）的系統時間是103毫秒，PD向etcd申請了一個“可分配的時間窗口”。要知道時間窗口的跨度是可以通過參數指定的，系統的默認配置是3毫秒，示例采用了默認配置，所以這個窗口的起點是PD當前時間103，時間窗口的終點就在106毫秒處。。寫入etcd成功后，PD將得到一個從103到106的“可分配時間窗口”，在這個時間窗口內PD可以使用系統的物理時間作為，拼接自己在內存中累加的邏輯時間，對上述設計意味著，所有PD已分配時間戳的，也就是物理時間，小于etcd的最大值。那么，如果PD主節點宕機，新主就可以etcd中的最大值，在此基礎上此外，為了降低通訊開銷，每個客戶端一次可以申請多個時間戳，時間戳數量作為參數，由客戶端傳給P前面已經TrueTime依賴強大的工程能力和特殊硬件，不具有普適性。相反，HLCCockroachDB、YugabyteDBHLC不只是字面上的意思，TiDB的TSO也混合了物理時鐘與邏輯時鐘，但兩者截然不同。HLC代表了一種計時機制，它的首次提出是 “ ClocksConsistentSnapshotsinGloballyDistributedDatabases”中，CockroachDB 假如我們有ABCD四個節點，方框是節點上發生的，方框內的三個數字依次是節點的本地物理時間（簡稱本地時間，Pt）、HLC的（簡稱L值）和HLC的低位（簡稱CA節點的本地時間初始值為10，其他節點的本地時間初始值都是0。四個節點的第一個事件都是在節點剛啟動的一刻發生的。首先看A1，它的HLC應該是(10,0)，其中直接取本地時間，低位從0開始。同理，其他的HLC都是(0,0)。D2發生時，首先取上一個D1的L值和本地時間比較。L值等于0，本地時間已經遞增變為1，取最大值，那么用本地時間作為D2的L值。變更了，低位要歸零，所以D2的HLC就是(1,0)。如果你看懂了D2的計時邏輯就會發現，D1其實是一樣的，只不過D1沒有上一個L0如果節點間有調用關系，計時邏輯會更復雜一點。我們看B2，要先判斷B2的L值，本節點上前一個B1的L調用A1的L值，A1的HLC是隨著函數調用傳給B節點0、110B2L10，A1CA1C1，B2HLC(10,1B3發生時，發現當前本地時間比B2的L值還要小，所以沿用了B2的L值，而C值是在B2的C值上加一，最終B3的HLC就是(10,2)。代代Initiallyl:j:=0;c:j:=Sendorlocall’:j:=l:j:=max(l’:j;If(l:j=l’:j)thenc:j:=c:j+Elsec:j:=Timestampwithl:j;Receiveeventofmessagel’:j:=l:j:=max(l’:j;l:m;If(l:j=l’:j=l:m)thenc:j:=max(c:j;Elseif(l:j=l’:j)thenc:j:=c:j+Elseif(l:j=l:m)thenc:j:=c:m+Elsec:j:=Timestampwithl:j;其中，對于節點J，l.j表示L值，c.j表示C值，pt.j在HLC機制下，每個節點會使用本地時鐘作為參照，但不受到時鐘回撥的影響，可以保證單調遞增。本質上，HLC還是Lamport系的兩個，是無法精確判斷先后關系的。比如，上面例子中的C2和D2有同樣的HLC，但從上帝視角看，C2是早于D2發生的，因為兩個節點的本地時鐘有差異，就沒有體現這種先后關系。HLC確，還要靠NTP或類似的協議來保證。STP（SerialTimeProtocol），是內部邏輯時間同步的協議，并不依賴于NTP協議。下面是STPSTPSTPSTPNodeSTPServer。STPServerSTPServer被稱為Primary，對外提供服務。 。PrimaryServer巨杉數據庫的其他角色節點，如編目節點（CAG）、協調節點（COORDDAA）等，都從本地的PNode節點獲得時間。STP與TSO一樣都是單時間源，但通過增加的授時點，避免了單點性能瓶頸，而負副作用是多點授時就會造成全局性的時間誤差，因此和HLC一樣需要做針對性設計。TrueTime高性能，能夠支持Spanner做到全球化部署，是一種非常強悍的設計方案。TrueTimeGPSSpanner時服務，不需要Spanner做專門的設計。HLC同樣是多時間源、多授時點，由于是純軟方案，所以具有更好的通用性。CockroachDBYugabyteDBHLC設計基礎是Lamport邏輯時鐘，對NTP的時間偏移有一定的依賴。TSO是典型的單時間源、單點授時方案，實現簡便，所以成為多數分布式數據庫的選擇。如果TSO能夠做到單調遞增，會簡化讀寫時候的處理過程，但缺點是集群部署還有一些小眾的方案，比如巨杉的STP，中都最后，今天留給你的思考題還是關于時間的。在后續課程沒有展開之前，我們不妨先來開放式地討論一下，你覺得時間對于分布式數據庫的影響是什么？或者你也可以談談在其他分布式系統中曾經遇到的關于時間的問題。歡迎你在評論區留言和我一起討論，我會在答疑篇回復這個問題。如果你身邊的朋友也對全局時鐘或者分布式架構下如何同步時間這個話題感，你也可以把今天這一講給他，我們一起討論。DanielPengandFrankDabek: Large-scaleIncrementalProcessingUsingDistributedTransactionsandNotificationsSandeepS.Kulkarnietal.: LogicalPhysicalClocksandConsistentSnapshotsinGloballyDistributedDatabases