專欄的絕大部分主題都側重于 Java 語言和虛擬機，基本都是單機模式下的問題，今天我會補充一個分布式相關的問題。嚴格來說，分布式并不算是 Java 領域，而是一個單獨的大主題，但確實也會在 Java 技術崗位面試中被涉及。在準備面試時，如果有豐富的分布式系統經驗當然好；如果沒有，你可以選擇典型問題和基礎技術進行適當準備。關于分布式，我自身的實戰經驗也非常有限，專欄里就談談從理論出發的一些思考。 今天我要問你的問題是，談談常用的分布式 ID 的設計方案？Snowflake 是否受冬令時切換影響？ ## 典型回答 首先，我們需要明確通常的分布式 ID 定義，基本的要求包括： * 全局唯一，區別于單點系統的唯一，全局是要求分布式系統內唯一。 * 有序性，通常都需要保證生成的 ID 是有序遞增的。例如，在數據庫存儲等場景中，有序 ID 便于確定數據位置，往往更加高效。 目前業界的方案很多，典型方案包括： * 基于數據庫自增序列的實現。這種方式優缺點都非常明顯，好處是簡單易用，但是在擴展性和可靠性等方面存在局限性。 * 基于 Twitter 早期開源的[Snowflake](https://github.com/twitter/snowflake)的實現，以及相關改動方案。這是目前應用相對比較廣泛的一種方式，其結構定義你可以參考下面的示意圖。  整體長度通常是 64 （1 + 41 + 10+ 12 = 64）位，適合使用 Java 語言中的 long 類型來存儲。 頭部是 1 位的正負標識位。 緊跟著的高位部分包含 41 位時間戳，通常使用 System.currentTimeMillis()。 后面是 10 位的 WorkerID，標準定義是 5 位數據中心 + 5 位機器 ID，組成了機器編號，以區分不同的集群節點。 最后的 12 位就是單位毫秒內可生成的序列號數目的理論極限。 Snowflake 的[官方版本](https://github.com/twitter/snowflake)是基于 Scala 語言，Java 等其他語言的[參考實現](https://github.com/relops/snowflake)有很多，是一種非常簡單實用的方式，具體位數的定義是可以根據分布式系統的真實場景進行修改的，并不一定要嚴格按照示意圖中的設計。 * Redis、Zookeeper、MongoDB 等中間件，也都有各種唯一 ID 解決方案。其中一些設計也可以算作是 Snowflake 方案的變種。例如，MongoDB 的[ObjectId](http://mongodb.github.io/node-mongodb-native/2.0/tutorials/objectid/)提供了一個 12 byte（96 位）的 ID 定義，其中 32 位用于記錄以秒為單位的時間，機器 ID 則為 24 位，16 位用作進程 ID，24 位隨機起始的計數序列。 * 國內的一些大廠開源了其自身的部分分布式 ID 實現，InfoQ 就曾經介紹過微信的[seqsvr](http://www.infoq.com/cn/articles/wechat-serial-number-generator-architecture)，它采取了相對復雜的兩層架構，并根據社交應用的數據特點進行了針對性設計，具體請參考相關[代碼實現](https://github.com/nebula-im/seqsvr)。另外，[百度](https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md)、美團等也都有開源或者分享了不同的分布式 ID 實現，都可以進行參考。 關于第二個問題，**Snowflake 是否受冬令時切換影響？** 我認為沒有影響，你可以從 Snowflake 的具體算法實現尋找答案。我們知道 Snowflake 算法的 Java 實現，大都是依賴于 System.currentTimeMillis()，這個數值代表什么呢？從 Javadoc 可以看出，它是返回當前時間和 1970 年 1 月 1 號 UTC 時間相差的毫秒數，這個數值與夏 / 冬令時并沒有關系，所以并不受其影響。 ## 考點分析 今天的問題不僅源自面試的熱門考點，并且也存在著廣泛的應用場景，我前面給出的回答只是一個比較精簡的典型方案介紹。我建議你針對特定的方案進行深入分析，以保證在面試官可能會深入追問時能有充分準備；如果恰好在現有系統使用分布式 ID，理解其設計細節是很有必要的。 涉及分布式，很多單機模式下的簡單問題突然就變得復雜了，這是分布式天然的復雜性，需要從不同角度去理解適用場景、架構和細節算法，我會從下面的角度進行適當解讀： * 我們的業務到底需要什么樣的分布式 ID，除了唯一和有序，還有哪些必須要考慮的要素？ * 在實際場景中，針對典型的方案，有哪些可能的局限性或者問題，可以采取什么辦法解決呢？ ## 知識擴展 如果試圖深入回答這個問題，首先需要明確業務場景的需求要點，我們到底需要一個什么樣的分布式 ID？ 除了唯一和有序，考慮到分布式系統的功能需要，通常還會額外希望分布式 ID 保證： * 有意義，或者說包含更多信息，例如時間、業務等信息。這一點和有序性要求存在一定關聯，如果 ID 中包含時間，本身就能保證一定程度的有序，雖然并不能絕對保證。ID 中包含額外信息，在分布式數據存儲等場合中，有助于進一步優化數據訪問的效率。 * 高可用性，這是分布式系統的必然要求。前面談到的方案中，有的是真正意義上的分布式，有得還是傳統主從的思路，這一點沒有絕對的對錯，取決于我們業務對擴展性、性能等方面的要求。 * 緊湊性，ID 的大小可能受到實際應用的制約，例如數據庫存儲往往對長 ID 不友好，太長的 ID 會降低 MySQL 等數據庫索引的性能；編程語言在處理時也可能受數據類型長度限制。 在具體的生產環境中，還有可能提出對 QPS 等方面的具體要求，尤其是在國內一線互聯網公司的業務規模下，更是需要考慮峰值業務場景的數量級層次需求。 第二，**主流方案的優缺點分析**。 對于數據庫自增方案，除了實現簡單，它生成的 ID 還能夠保證固定步長的遞增，使用很方便。 但是，因為每獲取一個 ID 就會觸發數據庫的寫請求，是一個代價高昂的操作，構建高擴展性、高性能解決方案比較復雜，性能上限明顯，更不要談擴容等場景的難度了。與此同時，保證數據庫方案的高可用性也存在挑戰，數據庫可能發生宕機，即使采取主從熱備等各種措施，也可能出現 ID 重復等問題。 實際大廠商往往是構建了多層的復合架構，例如美團公開的數據庫方案[Leaf-Segment](https://tech.meituan.com/MT_Leaf.html)，引入了起到緩存等作用的 Leaf 層，對數據庫操作則是通過數據庫中間件提供的批量操作，這樣既能保證性能、擴展性，也能保證高可用。但是，這種方案對基礎架構層面的要求很多，未必適合普通業務規模的需求。 與其相比，Snowflake 方案的好處是算法簡單，依賴也非常少，生成的序列可預測，性能也非常好，比如 Twitter 的峰值超過 10 萬 /s。 但是，它也存在一定的不足，例如： * 時鐘偏斜問題（Clock Skew）。我們知道普通的計算機系統時鐘并不能保證長久的一致性，可能發生時鐘回撥等問題，這就會導致時間戳不準確，進而產生重復 ID。 針對這一點，Twitter 曾經在文檔中建議開啟[NTP](http://doc.ntp.org/4.1.0/ntpd.htm)，畢竟 Snowflake 對時間存在依賴，但是也有人提議關閉 NTP。我個人認為還是應該開啟 NTP，只是可以考慮將 stepback 設置為 0，以禁止回調。 從設計和具體編碼的角度，還有一個很有效的措施就是緩存歷史時間戳，然后在序列生成之前進行檢驗，如果出現當前時間落后于歷史時間的不合理情況，可以采取相應的動作，要么重試、等待時鐘重新一致，或者就直接提示服務不可用。 * 另外，序列號的可預測性是把雙刃劍，雖然簡化了一些工程問題，但很多業務場景并不適合可預測的 ID。如果你用它作為安全令牌之類，則是非常危險的，很容易被黑客猜測并利用。 * ID 設計階段需要謹慎考慮暴露出的信息。例如，[Erlang 版本](https://github.com/boundary/flake)的 flake 實現基于 MAC 地址計算 WorkerID，在安全敏感的領域往往是不可以這樣使用的。 * 從理論上來說，類似 Snowflake 的方案由于時間數據位數的限制，存在與[2038 年問題](https://en.wikipedia.org/wiki/Year_2038_problem)相似的理論極限。雖然目前的系統設計考慮數十年后的問題還太早，但是理解這些可能的極限是有必要的，也許會成為面試的過程中的考察點。 如果更加深入到時鐘和分布式系統時序的問題，還有與分布式 ID 相關但又有所區別的問題，比如在分布式系統中，不同機器的時間很可能是不一致的，如何保證事件的有序性？Lamport 在 1978 年的論文（[Time, Clocks, and the Ording of Events in a Distributed System](https://amturing.acm.org/p558-lamport.pdf)）中就有很深入的闡述，有興趣的同學可以去查找相應的翻譯和解讀。 最后，我再補充一些當前分布式領域的面試熱點，例如： * 分布式事務，包括其產生原因、業務背景、主流的解決方案等。 * 理解[CAP](https://en.wikipedia.org/wiki/CAP_theorem)、[BASE](https://en.wikipedia.org/wiki/Eventual_consistency)等理論，懂得從最終一致性等角度來思考問題，理解[Paxos](https://en.wikipedia.org/wiki/Paxos_(computer_science))、[Raft](https://raft.github.io/)等一致性算法。 * 理解典型的分布式鎖實現，例如最常見的[Redis 分布式鎖](https://redis.io/topics/distlock)。 * 負載均衡等分布式領域的典型算法，至少要了解主要方案的原理。 這些方面目前都已經有相對比較深入的分析，尤其是來自于一線大廠的實踐經驗。另外，在[左耳聽風專欄的“程序員練級攻略”](http://time.geekbang.org/column/48)里，提供了非常全面的分布式學習資料，感興趣的同學可以參考。 今天我簡要梳理了當前典型的分布式 ID 生成方案，并探討了 ID 設計的一些考量，尤其是應用相對廣泛的 Snowflake 的不足之處，希望對你有所幫助。 ## 一課一練 關于今天我們討論的題目你做到心中有數了嗎？今天的思考題是，從理論上來看，Snowflake 這種基于時間的算法，從形式上天然地限制了 ID 的并發生成數量，如果在極端情況下，短時間需要更多 ID，有什么辦法解決呢？