談?wù)劤Ｓ玫姆植际?ID 的設(shè)計(jì)方案？Snowflake 是否受冬令時(shí)切換影響？
典型回答
首先，我們需要明確通常的分布式 ID 定義，基本的要求包括：
全局唯一，區(qū)別于單點(diǎn)系統(tǒng)的唯一，全局是要求分布式系統(tǒng)內(nèi)唯一。
有序性，通常都需要保證生成的 ID 是有序遞增的。例如，在數(shù)據(jù)庫存儲(chǔ)等場(chǎng)景中，有序 ID 便于確定數(shù)據(jù)位置，往往更加高效。
目前業(yè)界的方案很多，典型方案包括：
基于數(shù)據(jù)庫自增序列的實(shí)現(xiàn)。這種方式優(yōu)缺點(diǎn)都非常明顯，好處是簡單易用，但是在擴(kuò)展性和可靠性等方面存在局限性。
基于 Twitter 早期開源的Snowflake的實(shí)現(xiàn)，以及相關(guān)改動(dòng)方案。這是目前應(yīng)用相對(duì)比較廣泛的一種方式，其結(jié)構(gòu)定義你可以參考下面的示意圖。
整體長度通常是 64 （1? 41? 10? 12 = 64）位，適合使用 Java 語言中的 long 類型來存儲(chǔ)。
頭部是 1 位的正負(fù)標(biāo)識(shí)位。
緊跟著的高位部分包含 41 位時(shí)間戳，通常使用 System.currentTimeMillis()。
后面是 10 位的 WorkerID，標(biāo)準(zhǔn)定義是 5 位數(shù)據(jù)中心? 5 位機(jī)器 ID，組成了機(jī)器編號(hào)，以區(qū)分不同的集群節(jié)點(diǎn)。
最后的 12 位就是單位毫秒內(nèi)可生成的序列號(hào)數(shù)目的理論極限。
Snowflake 的官方版本是基于 Scala 語言，Java 等其他語言的參考實(shí)現(xiàn)有很多，是一種非常簡單實(shí)用的方式，具體位數(shù)的定義是可以根據(jù)分布式系統(tǒng)的真實(shí)場(chǎng)景進(jìn)行修改的，并不一定要嚴(yán)格按照示意圖中的設(shè)計(jì)。
Redis、Zookeeper、MangoDB 等中間件，也都有各種唯一 ID 解決方案。其中一些設(shè)計(jì)也可以算作是 Snowflake 方案的變種。例如，MongoDB 的ObjectId提供了一個(gè) 12 byte（96 位）的 ID 定義，其中 32 位用于記錄以秒為單位的時(shí)間，機(jī)器 ID 則為 24 位，16 位用作進(jìn)程 ID，24 位隨機(jī)起始的計(jì)數(shù)序列。
國內(nèi)的一些大廠開源了其自身的部分分布式 ID 實(shí)現(xiàn)，InfoQ 就曾經(jīng)介紹過微信的seqsvr，它采取了相對(duì)復(fù)雜的兩層架構(gòu)，并根據(jù)社交應(yīng)用的數(shù)據(jù)特點(diǎn)進(jìn)行了針對(duì)性設(shè)計(jì)，具體請(qǐng)參考相關(guān)代碼實(shí)現(xiàn)。另外，百度、美團(tuán)等也都有開源或者分享了不同的分布式 ID 實(shí)現(xiàn)，都可以進(jìn)行參考。
關(guān)于第二個(gè)問題，Snowflake 是否受冬令時(shí)影響。
我認(rèn)為沒有影響，你可以從 Snowflake 的具體算法實(shí)現(xiàn)尋找答案。我們知道 Snowflake 算法的 Java 實(shí)現(xiàn)，大都是依賴于 System.currentTimeMillis()，這個(gè)數(shù)值代表什么呢？從 Javadoc 可以看出，它是返回當(dāng)前時(shí)間和 1970 年 1 月 1 號(hào) UTC 時(shí)間相差的毫秒數(shù)，這個(gè)數(shù)值與夏 / 冬令時(shí)并沒有關(guān)系，所以并不受其影響。
考點(diǎn)分析
今天的問題不僅源自面試的熱門考點(diǎn)，并且也存在著廣泛的應(yīng)用場(chǎng)景，我前面給出的回答只是一個(gè)比較精簡的典型方案介紹。我建議你針對(duì)特定的方案進(jìn)行深入分析，以保證在面試官可能會(huì)深入追問時(shí)能有充分準(zhǔn)備；如果恰好在現(xiàn)有系統(tǒng)使用分布式 ID，理解其設(shè)計(jì)細(xì)節(jié)是很有必要的。
涉及分布式，很多單機(jī)模式下的簡單問題突然就變得復(fù)雜了，這是分布式天然的復(fù)雜性，需要從不同角度去理解適用場(chǎng)景、架構(gòu)和細(xì)節(jié)算法，我會(huì)從下面的角度進(jìn)行適當(dāng)解讀：
我們的業(yè)務(wù)到底需要什么樣的分布式 ID，除了唯一和有序，還有哪些必須要考慮的要素？
在實(shí)際場(chǎng)景中，針對(duì)典型的方案，有哪些可能的局限性或者問題，可以采取什么辦法解決呢？
知識(shí)擴(kuò)展
如果試圖深入回答這個(gè)問題，首先需要明確業(yè)務(wù)場(chǎng)景的需求要點(diǎn)，我們到底需要一個(gè)什么樣的分布式 ID？
除了唯一和有序，考慮到分布式系統(tǒng)的功能需要，通常還會(huì)額外希望分布式 ID 保證：
有意義，或者說包含更多信息，例如時(shí)間、業(yè)務(wù)等信息。這一點(diǎn)和有序性要求存在一定關(guān)聯(lián)，如果 ID 中包含時(shí)間，本身就能保證一定程度的有序，雖然并不能絕對(duì)保證。ID 中包含額外信息，在分布式數(shù)據(jù)存儲(chǔ)等場(chǎng)合中，有助于進(jìn)一步優(yōu)化數(shù)據(jù)訪問的效率。
高可用性，這是分布式系統(tǒng)的必然要求。前面談到的方案中，有的是真正意義上的分布式，有得還是傳統(tǒng)主從的思路，這一點(diǎn)沒有絕對(duì)的對(duì)錯(cuò)，取決于我們業(yè)務(wù)對(duì)擴(kuò)展性、性能等方面的要求。
緊湊性，ID 的大小可能受到實(shí)際應(yīng)用的制約，例如數(shù)據(jù)庫存儲(chǔ)往往對(duì)長 ID 不友好，太長的 ID 會(huì)降低 MySQL 等數(shù)據(jù)庫索引的性能；編程語言在處理時(shí)也可能受數(shù)據(jù)類型長度限制。
在具體的生產(chǎn)環(huán)境中，還有可能提出對(duì) QPS 等方面的具體要求，尤其是在國內(nèi)一線互聯(lián)網(wǎng)公司的業(yè)務(wù)規(guī)模下，更是需要考慮峰值業(yè)務(wù)場(chǎng)景的數(shù)量級(jí)層次需求。
第二，主流方案的優(yōu)缺點(diǎn)分析。
對(duì)于數(shù)據(jù)庫自增方案，除了實(shí)現(xiàn)簡單，它生成的 ID 還能夠保
對(duì)于數(shù)據(jù)庫自增方案，除了實(shí)現(xiàn)簡單，它生成的 ID 還能夠保證固定步長的遞增，使用很方便。
但是，因?yàn)槊揩@取一個(gè) ID 就會(huì)觸發(fā)數(shù)據(jù)庫的寫請(qǐng)求，是一個(gè)代價(jià)高昂的操作，構(gòu)建高擴(kuò)展性、高性能解決方案比較復(fù)雜，性能上限明顯，更不要談擴(kuò)容等場(chǎng)景的難度了。與此同時(shí)，保證數(shù)據(jù)庫方案的高可用性也存在挑戰(zhàn)，數(shù)據(jù)庫可能發(fā)生宕機(jī)，即使采取主從熱備等各種措施，也可能出現(xiàn) ID 重復(fù)等問題。
實(shí)際大廠商往往是構(gòu)建了多層的復(fù)合架構(gòu)，例如美團(tuán)公開的數(shù)據(jù)庫方案Leaf-Segment，引入了起到緩存等作用的 Leaf 層，對(duì)數(shù)據(jù)庫操作則是通過數(shù)據(jù)庫中間件提供的批量操作，這樣既能保證性能、擴(kuò)展性，也能保證高可用。但是，這種方案對(duì)基礎(chǔ)架構(gòu)層面的要求很多，未必適合普通業(yè)務(wù)規(guī)模的需求。
與其相比，Snowflake 方案的好處是算法簡單，依賴也非常少，生成的序列可預(yù)測(cè)，性能也非常好，比如 Twitter 的峰值超過 10 萬 /s。
但是，它也存在一定的不足，例如：
時(shí)鐘偏斜問題（Clock Skew）。我們知道普通的計(jì)算機(jī)系統(tǒng)時(shí)鐘并不能保證長久的一致性，可能發(fā)生時(shí)鐘回?fù)艿葐栴}，這就會(huì)導(dǎo)致時(shí)間戳不準(zhǔn)確，進(jìn)而產(chǎn)生重復(fù) ID。
針對(duì)這一點(diǎn)，Twitter 曾經(jīng)在文檔中建議開啟NTP，畢竟 Snowflake 對(duì)時(shí)間存在依賴，但是也有人提議關(guān)閉 NTP。我個(gè)人認(rèn)為還是應(yīng)該開啟 NTP，只是可以考慮將 stepback 設(shè)置為 0，以禁止回調(diào)。
從設(shè)計(jì)和具體編碼的角度，還有一個(gè)很有效的措施就是緩存歷史時(shí)間戳，然后在序列生成之前進(jìn)行檢驗(yàn)，如果出現(xiàn)當(dāng)前時(shí)間落后于歷史時(shí)間的不合理情況，可以采取相應(yīng)的動(dòng)作，要么重試、等待時(shí)鐘重新一致，或者就直接提示服務(wù)不可用。
另外，序列號(hào)的可預(yù)測(cè)性是把雙刃劍，雖然簡化了一些工程問題，但很多業(yè)務(wù)場(chǎng)景并不適合可預(yù)測(cè)的 ID。如果你用它作為安全令牌之類，則是非常危險(xiǎn)的，很容易被黑客猜測(cè)并利用。
ID 設(shè)計(jì)階段需要謹(jǐn)慎考慮暴露出的信息。例如，Erlang 版本的 flake 實(shí)現(xiàn)基于 MAC 地址計(jì)算 WorkerID，在安全敏感的領(lǐng)域往往是不可以這樣使用的。
從理論上來說，類似 Snowflake 的方案由于時(shí)間數(shù)據(jù)位數(shù)的限制，存在與2038 年問題相似的理論極限。雖然目前的系統(tǒng)設(shè)計(jì)考慮數(shù)十年后的問題還太早。
如果更加深入到時(shí)鐘和分布式系統(tǒng)時(shí)序的問題，還有與分布式 ID 相關(guān)但又有所區(qū)別的問題，比如在分布式系統(tǒng)中，不同機(jī)器的時(shí)間很可能是不一致的，如何保證事件的有序性？Lamport 在 1978 年的論文（Time, Clocks, and the Ording of Events in a Distributed System）中就有很深入的闡述，有興趣的同學(xué)可以去查找相應(yīng)的翻譯和解讀。
最后，我再補(bǔ)充一些當(dāng)前分布式領(lǐng)域的面試熱點(diǎn)，例如：
分布式事務(wù)，包括其產(chǎn)生原因、業(yè)務(wù)背景、主流的解決方案等。
理解CAP、BASE等理論，懂得從最終一致性等角度來思考問題，理解Paxos、Raft等一致性算法。
理解典型的分布式鎖實(shí)現(xiàn)，例如最常見的Redis 分布式鎖。
負(fù)載均衡等分布式領(lǐng)域的典型算法，至少要了解主要方案的原理。
