應邀來簡單聊聊分布式時間戳的故事。時間戳
和人類一樣，計算機系統也需要時間的概念；通常我們需要一個時間戳來標記事件發生的時間。例如，當我們使用Mac的來為系統進行備份的時候，我們需要知道當前備份的時間；這樣我們可以在恢復時明確我們恢復的什么時候的備份。
分布式時間戳
分布式系統和單機系統一樣，也需要時間戳來標記事件（如數據更新）的時間。如何生成系統的時間戳？我們可否直接使用系統的時間，比如linux的系統調用，中time()? 如果系統中只有一臺機器，那么我們當然可以使用這個方法來確定時間戳。然而，如果系統中有許多臺機器，那么使用每臺機器自己的時間戳通常是不夠的；因為他們之間的時鐘往往是不同步的。例如，我們手機上的時間可能會和電腦的時間不一樣。
不同步時鐘帶來的問題：我們用一個簡單的例子來看不能同步的時間戳會在分布式系統中帶來何種問題。我們以一個簡單數據庫為例子，假設我們有兩個服務器，和，如下圖所示。 他們存儲同一個數據庫。數據庫接受客戶端()的 來更新：add x將x添加到數據庫； x將x刪除。假設需要在數據庫中添加x，則他會同時往兩臺服務器同時發送add x的請求。我們假設服務器順序的執行所有的 。
由于數據存在備份，那么就會有一致性()的問題。例如下圖所示：一個給發送add x1而另一個發送add x2。 由于網絡消息的到達可能會亂序，這么兩臺服務器執行 的順序會不同，造成不一致。
備份系統通常需要提供一定程度的一致性來方便開發人員使用存儲的數據。我們這邊考慮最簡單（也最弱）的一致性： ：即最終和的狀態最終會是一樣的。我們之后會看到，由于不一致的時鐘，即使是這種最弱的一致性條件下也會出現問題。
實現 最簡單的方法就是采用有序日志（ log); 即我們將發送來的 記入一個日志（log)，然后按照他們的發送時間戳排序；最后按照排序依次執行。一種簡單的時間戳分配方法就是使用的本地時鐘來標記 的時間。如下圖所示， log完美的解決了問題：雖然不同服務器收到的 的順序不一樣，但我們可以利用已知的時間戳來為他們進行排序；再進行執行。這樣java獲取當天零點的時間戳，最終和的狀態總會是一樣的。
讀者可能好奇，在這個簡單支持 的例子中，似乎我們對時間戳幾乎沒有要求：因為這里的時間戳僅僅是作為排序日志的一種方式。然而，如果真的對時間戳沒有要求的話，實際上并不能保證用戶需要的一致性！我們來看下面一個例子：先發送了add x而隨后發送了del x；然而由于的時鐘在分布式下可能會不一致，del x的時間戳（0）可能于add x。 這樣，服務器可能會先于add x執行del x。
不同步時間戳帶來的問題：我們可以看到，在或者執行的時候，del x會先于add x執行，這其實違反了用戶需要的一致性！通常，在客戶端看來，他是先確定添加了x之后才會將其刪除。這主要是由于這些請求可能來自于不同的；而他們的時間未必會和事件發生的真實事件一致。
其實我們看到，不同步的時間戳的最關鍵問題就是有序的事件需要給他們分配有序的時間戳。在上文的例子中，由于del x邏輯上是依賴于add x的，因此del x在客戶端發送的時候，理想情況下他發送的時間戳需要更大。如果直接簡單的用客戶端的機器時間戳來作為 log的依據，則沒有辦法保證這一特性，因為分布式系統中不同機器之間的時鐘是不一致的。
為了解決這一問題，大名鼎鼎的 提出了 [1]，如下圖[2]所示:
的思想非常簡單，如果事件之間有依賴關系，則更新時間戳來體現這種依賴關系。具體的方法，就是將時間戳更新為比依賴事件的時間戳更大。
我們來從之前的例子來看， 怎么解決 之前例子的問題。假設add x 先執行了，則我們以 的方式記下add x的時間。在發送del x 的時候我們以 的方式來給其分配時間戳；這樣del x的時間戳永遠會比add x 大。這樣，在以他們的時間戳排序 log的時候，就會避免之前執行順序的問題。
全局有序的時鐘
只能保證一個偏序：如果一個事件依賴于另一個事件，則他的時間戳會更大；反之則不成立。通常，人們還是希望時間戳能夠提供更強的順序， 而不單單提供邏輯事件之間的關系。這種順序通?？坍嫗橥獠恳恢滦? )，即如果一個事件在真實時間中發生在另一件事件之后，那么他就會有一個更大的時間戳，無論他們是否具有依賴關系。
通常，最簡單的在分布式下提供 一致性的時間戳的方法有以下兩種：
全局的時間戳服務器顯然是最直觀提供符合事件發生先后順序的方法；然而他也有明顯的弊端，即所有的請求都會發送一個額外的請求到時間戳服務器，這樣會造成一次額外的通信開銷；同時時間戳服務器會成為性能的瓶頸。這在geo-，即服務器分布在地球各地的情況下更加糟糕，因為跨地域的網絡延遲通常會非常大。
在2012年的[3] 數據庫中提出了一個 API，來避免使用一個全局時間戳服務器，同時提供的時間能夠保證外部一致性。
簡單來說java獲取當天零點的時間戳，提供了一個delta； 并且保證不同機器之間的時鐘最多不會超過delta。這樣，當一個事件發生時 ,最多只需要等待delta的事件，便可保證他的時間戳一定大于先于他之前發生的事件的時間戳。用在geo-的情況下支持 的數據庫事務。
Delta的大小對使用應用的性能非常相關：通常使用的應用需要等待delta來確保時間戳的準確。提供的delta通常是毫秒級。Delta的大小取決于許多因素，如網絡延遲。最近有研究在單數據中心的情況下，利用快速的網絡（如RDMA）可以將delta降低到微秒級[4]。
總結
本文介紹了時間戳在分布式系統的應用，以及常見的分布式時間戳方法。
[1] Time, and the of in a ,/pubs/time-.pdf
[2] //ads//lec3-.pdf
[3] ///-//
[4] /en-us///prod/2019/01/.pdf