專欄的絕大部分主題都側重于 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,有什么辦法解決呢?
- 前言
- 開篇詞
- 開篇詞 -以面試題為切入點,有效提升你的Java內功
- 模塊一 Java基礎
- 第1講 談談你對Java平臺的理解?
- 第2講 Exception和Error有什么區別?
- 第3講 談談final、finally、 finalize有什么不同?
- 第4講 強引用、軟引用、弱引用、幻象引用有什么區別?
- 第5講 String、StringBuffer、StringBuilder有什么區別?
- 第6講 動態代理是基于什么原理?
- 第7講 int和Integer有什么區別?
- 第8講 對比Vector、ArrayList、LinkedList有何區別?
- 第9講 對比Hashtable、HashMap、TreeMap有什么不同?
- 第10講 如何保證集合是線程安全的? ConcurrentHashMap如何實現高效地線程安全?
- 第11講 Java提供了哪些IO方式? NIO如何實現多路復用?
- 第12講 Java有幾種文件拷貝方式?哪一種最高效?
- 第13講 談談接口和抽象類有什么區別?
- 第14講 談談你知道的設計模式?
- 模塊二 Java進階
- 第15講 synchronized和ReentrantLock有什么區別呢?
- 第16講 synchronized底層如何實現?什么是鎖的升級、降級?
- 第17講 一個線程兩次調用start()方法會出現什么情況?
- 第18講 什么情況下Java程序會產生死鎖?如何定位、修復?
- 第19講 Java并發包提供了哪些并發工具類?
- 第20講 并發包中的ConcurrentLinkedQueue和LinkedBlockingQueue有什么區別?
- 第21講 Java并發類庫提供的線程池有哪幾種? 分別有什么特點?
- 第22講 AtomicInteger底層實現原理是什么?如何在自己的產品代碼中應用CAS操作?
- 第23講 請介紹類加載過程,什么是雙親委派模型?
- 第24講 有哪些方法可以在運行時動態生成一個Java類?
- 第25講 談談JVM內存區域的劃分,哪些區域可能發生OutOfMemoryError?
- 第26講 如何監控和診斷JVM堆內和堆外內存使用?
- 第27講 Java常見的垃圾收集器有哪些?
- 第28講 談談你的GC調優思路?
- 第29講 Java內存模型中的happen-before是什么?
- 第30講 Java程序運行在Docker等容器環境有哪些新問題?
- 模塊三 Java安全基礎
- 第31講 你了解Java應用開發中的注入攻擊嗎?
- 第32講 如何寫出安全的Java代碼?
- 模塊四 Java性能基礎
- 第33講 后臺服務出現明顯“變慢”,談談你的診斷思路?
- 第34講 有人說“Lambda能讓Java程序慢30倍”,你怎么看?
- 第35講 JVM優化Java代碼時都做了什么?
- 模塊五 Java應用開發擴展
- 第36講 談談MySQL支持的事務隔離級別,以及悲觀鎖和樂觀鎖的原理和應用場景?
- 第37講 談談Spring Bean的生命周期和作用域?
- 第38講 對比Java標準NIO類庫,你知道Netty是如何實現更高性能的嗎?
- 第39講 談談常用的分布式ID的設計方案?Snowflake是否受冬令時切換影響?
- 周末福利
- 周末福利 談談我對Java學習和面試的看法
- 周末福利 一份Java工程師必讀書單
- 結束語
- 結束語 技術沒有終點
- 結課測試 Java核心技術的這些知識,你真的掌握了嗎?