導讀git
在分佈式數據庫系統中，爲了解決不一樣集羣、節點事件發生的前後順序問題，時鐘同步相當重要。本文將爲你們介紹業界現有的幾種主流的時鐘同步解決方案，以及分佈式數據庫 ZNBase 基於原子鐘技術實現的 Ture-time 機制。算法
業內的時鐘方案
目前業內主流的分佈式數據庫系統中，採用的時鐘同步方案各不相同。數據庫
國內比較熱門的 TiDB 和 OceanBase 使用的是 Timestamp Oracle （TSO）方案，即中心化授時方案。TSO 採用單時間源、單點授時的方式實現全局時鐘，用一個全局惟一的時間戳做爲全局事務 id。其中，TiDB 的事務模型是基於 Google Percolator 的，因此從一開始就使用的是相似 Percolator 的 TSO 機制。TiDB 經過集羣管理模塊 PD 統一進行時間的分配，以保障整個系統時間的全局同步。這種模式的優點是實現簡單，在同一個數據中心下網絡開銷很是小，但在跨地域的使用場景中延遲較高。而且，中心化授時方案會成爲整個系統的性能bottleneck，且授時服務的單點故障會直接致使整個分佈式集羣的不可用。安全
此外，CockroachDB 採用的是 HLC 做爲時鐘同步方案；Google 的 Spanner 使用的是結合原子鐘+GPS 硬件的 ture-time 機制，實現了全球化低延遲部署。服務器
瞭解時鐘同步
數據庫的核心就是將每個事務的操做進行排序，在傳統的單機架構下，事務的排序能夠經過日誌序列號或事務 ID 輕鬆實現。可是在分佈式架構下，數據庫運行在多臺服務器上，每一個數據庫實例有獨立的時鐘或日誌（LSN），而服務器和服務器之間時鐘點有快慢之差，因此分佈式數據庫下的時鐘沒法反映全局的事物順序。做爲分佈式數據庫的關鍵技術之一，時鐘同步技術就是爲了解決分佈式數據庫中事件發生的前後順序問題而存在。網絡
隨着分佈式系統規模的不斷擴大，不一樣集羣和不一樣節點的時間同步問題變得異常複雜。目前，分佈式數據庫業界廣泛採用的時鐘同步方案包括物理時鐘、邏輯時鐘、向量時鐘、混合邏輯時鐘、True-Time 機制五大類。 架構
1. 物理時鐘(PT)併發
物理時鐘即機器本地的時鐘，而因爲設備硬件不一樣，自己存在誤差，一天的偏差可能有毫秒甚至秒級，因此須要對不一樣的機器時鐘進行同步使得機器之間的時間進行相對統一。一般使用中心化的全局時間同步來保證各節點的時間統一。app
NTP 是目前比較經常使用的同步時間的方式。NTP 協議（Network Time Protocol）是用來使計算機時間同步化的一種網絡協議，它可使計算機對其服務器或時鐘源（如石英鐘，GPS 等等)作同步化，能夠提供較高精準度的時間校訂。其機制爲 C/S 架構，即每臺機器上存在一個 NTP 的客戶端，與 NTP 的服務端進行同步，校準本地的時間。 分佈式
然而，在分佈式數據庫中採用 NTP 協議進行對時，仍會存在 100-500ms 的偏差，這會形成分佈式節點間時鐘偏差較大，從而影響數據庫的高併發性能。
2. 邏輯時鐘(LC)
邏輯時鐘是由圖靈獎得主 Leslie Lamport 於 1978 年提出的概念，是一種在分佈式系統中用於區分事件的發生順序的時間機制。邏輯時鐘沒有任何一箇中心節點來產生時間，每個節點都有本身本地的邏輯時間，主要經過 happened-before 關係肯定事務的邏輯順序，從而肯定事務的偏序關係。
好比在兩個不一樣的實例中，A 節點先產生事務 1，事務 1 與其餘任何節點沒有產生聯繫，此時 A 節點邏輯時鐘+1，其餘節點不變；A 節點再產生事務 2，事務 2 與 B 節點產生聯繫，此時 A 節點邏輯時鐘+1，B 節點邏輯時鐘直接 +2，從而與 A 節點時鐘同步。經過在兩個時鐘之間創建聯繫，將兩個節點之間的邏輯時鐘同步，這時候就構建了它們之間的 happened-before 的前後關係，表明 A 節點的事務是在 B 節點的新事務開始以前完成的。
分佈式數據庫中，若是兩個事務沒有操做一樣的節點，則兩個事務是無關的事務。無關的事務能夠認爲是沒有前後順序的。可是當一個事務橫跨多個節點的時候，將多個節點之間的關係創建起來，就變成有關係的事務，構建的是事務間的因果序。
而邏輯時鐘的問題主要在於僅能保證同一個進程內的事件有序執行，當涉及到不一樣進程時，沒法肯定合適的全序關係，容易形成衝突。
3. 向量時鐘(VC)
向量時鐘是在 Lamport 算法基礎上演進的另外一種邏輯時鐘方法，它經過向量結構，不只記錄本節點的 Lamport 時間戳，同時也記錄了其餘節點的 Lamport 時間戳，所以可以很好描述同時發生關係以及事件的因果關係。
向量時鐘在每一個節點存儲一個向量，向量的每一個元素就是各個節點的邏輯時鐘，本質上是經過存儲全部節點的時鐘備份來解決邏輯時鐘的衝突問題。但因爲時鐘向量的維度等於節點數量，所以空間複雜度較高，影響了數據庫存儲和傳輸的效率。
4. 混合邏輯時鐘(HLC)
混合邏輯時鐘是一種將物理時鐘和邏輯時鐘進行組合的解決方案。
混合邏輯時鐘把分佈式下的時鐘切成兩部分，上半部分用物理時鐘來填充，下半部分用邏輯時鐘來填充。即在物理時鐘的基礎上，在必定的誤差範圍內引入邏輯時鐘進行校準，儘量使得二者達成一致。其核心內容包括如下 4 點：
（a）知足 LC 的因果一致性 happened-before。
（b）單個時鐘 O(1) 的存儲空間（VC 是 O(n)，n 爲分佈式系統下的節點個數）。
（c）單個時鐘的大小有肯定的邊界（不會無窮大）。
（d）儘量接近物理時鐘 PT，也就是說，HLC 和 PT 的差值有個肯定的邊界。
混合邏輯時鐘一共 64 位，前 32 位表示物理時鐘，後 32 位用於邏輯計數。
前文提到的物理時鐘同步精度問題也是 HLC 目前面臨的主要問題之一。在雲原生的 NewSQL 數據庫中，使用 HLC 時鐘也須要在物理時鐘層面進行高精度對時。然而基於 NTP 的 HLC 協議，在局域網下的延遲較小，偏差小，但在廣域網下時延長並且不穩定，對於多地域的分佈式集羣來講偏差很大，極大的限制了雲原生 NewSQL 數據庫的併發量。如何提高對時精度，從而提高雲原生 NewSQL 數據庫的讀寫併發量，成爲一個亟待解決的問題。
5. True-time 機制
True-time 機制是 Google 公司在 Spanner 論文中提出的時間同步機制，該機制假設系統中每臺機器產生的時間戳都有偏差，整個系統中達成了關於時間戳偏差範圍的共識，進而延遲提交事務，延遲時間和時間戳偏差有關，所以谷歌每一個數據中心都部署了基於 GPS 和原子鐘的主時鐘服務器，保證延持提交的等待時間儘量短。
True-time 本質上是確保兩個服務器之間時鐘偏移在很小的範圍以內，所以對機器的物理時鐘精度提出了極高的要求。Google 經過在各個數據中心部署昂貴的原子鐘+GPS 系統，來同步數據中內心各個機器的時間。與傳統石英鐘一天毫秒甚至秒級的偏差相比，原子鐘的精度可到達 2000 萬年差一秒。
固然，這種方案的缺點也顯而易見，由於是結合硬件實現的解決方案，成本高昂，難以在其餘地方大規模推廣。
ZNBase 的原子鐘方案
ZNBase 是由浪潮開源的一款 NewSQL 雲原生分佈式數據庫，與 CockroachDB、TiDB 同樣同爲參考自谷歌的 Spanner+F1 論文設計，具有強一致、高可用分佈式架構、分佈式水平擴展、高性能、企業級安全等特性。其時鐘同步方案通過優化迭代，目前採用的也是業界領先的 ture-time 方案。
ZNBase 最初採用的時鐘同步方案也是 NTP 對時+HLC。因爲前文提到的 NTP 協議存在偏差的問題，致使集羣內節點存在 500ms 左右的偏差，很大程度上影響了數據庫的高併發性能。爲解決這一問題，ZNBase 團隊決定捨棄 HLC 模塊，引入更高精度的原子鐘+PTP 協議，實現了本身的 ture-time 方案。
PTP 即精確時間同步協議，是一種在硬件層面實現的時間同步協議，通常採用硬件時間戳，並配合比 NTP 更高精度的延時測量算法。PTP 能夠直接在 MAC 層進行 PTP 協議包分析 , 這樣能夠不通過 UDP 協議棧 , 減小 PTP 在協議棧中駐留時間 , 從而提升時間同步的精確度。
如下是 ZNBase 團隊針對 NTP 與 PTP 進行的實驗對比數據：
經過在不一樣併發場景下的壓測 TPMC 結果，原子鐘與原有方案的性能數據相比，原子鐘方案性能提高 10%-20%。而且，原子鐘方案與原有方案相比，更加適合高併發及事務衝突場景。
因爲谷歌 Spanner 的 true-time 機制是配合原子鐘+GPS 的硬件實現的，相關的軟件部分並未開源，沒法直接照搬或借鑑。ZNBase 團隊在落地自身的 ture-time 機制過程當中遇到了諸多挑戰。
針對這種狀況，ZNBase 研發團隊查閱了大量的論文及技術資料，研究 true-time 的技術理論，經過前期的大量壓測及開展校企合做的方式，並與大學科研機構開展相關子課題的研究。最終，經過大量理論與實踐研究的工做，ZNBase 實現了現有的原子鐘方案。
目前，ZNBase 的 true-time 方案基於高精度時間同步主時鐘實現。支持 PTP/NTP/GPS/北斗/原子鐘五種模式。使用 GPS/北斗做爲參考時鐘時，跟蹤 UTC 的精度優於 100ns，可經過以太網提供百納秒級的時間信號源，極大地縮小了不一樣服務器之間的時鐘偏移範圍。
高精度時間同步主時鐘
經過將 NTP+HLC 方案優化成 PTP+原子鐘方案，ZNBase 將集羣內的節點偏差控制在了 1ms 之內，解決了異地多中心部署時，分佈式節點間時鐘偏差較大的問題。
本文介紹了分佈式數據庫系統經常使用的幾種時鐘同步解決方案，以及 ZNBase 的時鐘同步方案的優化迭代過程。歡迎對相關技術感興趣的朋友留言討論，不足之處也歡迎指出。
關於 ZNBase 的更多詳情能夠查看：
官方代碼倉庫：https://gitee.com/ZNBase/zn-kvs
ZNBase 官網：http://www.znbase.com/
對相關技術或產品有任何問題歡迎提 issue 或在社區中留言討論。同時歡迎廣大對分佈式數據庫感興趣的開發者共同參與 ZNBase 項目的建設。
聯繫郵箱：haojingyi@inspur.com