京東一面：分布式 ID 生成方案怎么選？寫得太好了！

背景

在分布式系統(tǒng)中，經常需要用到全局唯一ID發(fā)生器，標識需要存儲的數(shù)據(jù)。我們需要什么樣的ID生成器？

ID生成器除了是數(shù)據(jù)的唯一標識以外，一般需要在系統(tǒng)中承擔更多的責任，概括起來有以下幾點。另外，分布式系列面試題和答案全部整理好了，微信搜索Java技術棧，在后臺發(fā)送：面試，可以在線閱讀。

唯一性：“全局唯一” vs “業(yè)務唯一”？

分布式系統(tǒng)使用唯一的ID生成器，會有非常嚴重的申請互斥問題?；コ饧渔i意味著成本和性能的下降，不容易去實現(xiàn)一個高性能高可靠的架構。在業(yè)務系統(tǒng)中，往往也不需要全局唯一的ID。

比如在通訊系統(tǒng)里，聊天消息不需要全局唯一，標識一條用戶發(fā)出的消息的ID，只要保證用戶唯一性即可。因為消息本身歸屬于某一用戶，因此用戶唯一已經隱含了“全局唯一ID （ = 用戶ID + 消息ID ）”。

時間相關：“秒級” vs “毫秒”？

時間是天然唯一的，因此也是很多設計的選擇。但對于一個8Byte的 ID 而言，時間并沒有那么多。你如果精確到秒級別，三十年都要使用30bit，到毫秒級則要再增加10bit，你也只剩下20bit 可以做其他事情了。每秒一個或者每毫秒一個ID明顯是不夠的，剛才說到還有20bit 可以做其他事情，就包括一個SequenceID。

那時間用秒還是毫秒呢？其實不用毫秒的時候就可以把空出來的10bit 送給 Sequence，但整個ID 的精度就下降了。峰值速度是更現(xiàn)實的考慮。Sequence 的空間決定了峰值的速度，而峰值也就意味著持續(xù)的時間不會太久。這方面，每秒100萬比每毫秒1000限制更小。

有序：“粗略有序” vs “精確有序”？

首先，如果要達到精確的有序，就要對 Sequence 進行并發(fā)控制，性能上肯定會打折。其次，同一時間只能生成一個ID，意味著同一時間只有一個ID生成服務實例可以提供服務，精確有序還會面臨容災問題。

另外一個選擇就是，在這個秒的級別上不再保證順序，而整個 ID 則只保證時間上的有序。后一秒的 ID肯定比前一秒的大，但同一秒內可能后取的ID比前面的號小。粗略有序在使用時非常關鍵，業(yè)務上可接受才能成為候選方案。

設計細節(jié)

看下業(yè)界如何設計ID發(fā)生器。另外，想成為架構師，這份架構師圖譜建議看看，少走彎路。

SnowFlake

41bit留給毫秒時間，10bit給機器 (MachineID) ，剩下12bit留給Sequence。

Weibo

微博 30bit的秒級時間，4bit來區(qū)分IDC，2bit 區(qū)分業(yè)務，15bit 給 Sequence。理論上限3.2w/s的速度。由于當前發(fā)號服務是機房中心式的，1bit 來區(qū)分熱備。最終，沒有用滿64bit。

Flicker

Flicker 在解決全局ID生成方案里就采用了MySQL自增長ID的機制（auto_increment + replace into + MyISAM）。在我們的應用端需要做下面這兩個操作，在一個事務會話里提交：

REPLACE?INTO?Tickets64?(stub)?VALUES?('a');
SELECT?LAST_INSERT_ID();

Flicker啟用了兩臺數(shù)據(jù)庫服務器生成ID來容災，通過區(qū)分auto_increment的起始值和步長來生成奇偶數(shù)的ID。

TicketServer1:
auto-increment-increment?=?2
auto-increment-offset?=?1

TicketServer2:
auto-increment-increment?=?2
auto-increment-offset?=?2

微信

微信使用MySQL持久化未分配的最大ID，每次從DB取一段放到內存分配給調用方。微信的ID生成是嚴格遞增的，意味著同一時間只能有一臺機器提供服務，因此使用仲裁服務+租約機制+路由表，進行容災。

Shopee Feeds 如何生成ID ？

考慮到Feeds業(yè)務的特性，并不需要精確有序，因此我們使用snowflake算法進行ID生成。使用39 (毫秒)+ 5（機器） + 9（seq），來保證ID作為Redis的score不會溢出。最新面試題整理好了，大家可以在Java面試庫小程序在線刷題。

Redis 有序集合的分數(shù)使用雙精度64位浮點數(shù), 表示為一個IEEE 754 floating point number，它能包括的整數(shù)范圍是-(2^53) 到 +(2^53)

這樣的ID生成器可以使用大約17年，對于一款產品的生命周期來說已經足夠使用。

針對時間回撥產生的問題，因為發(fā)生的頻率極小，所以只需要簡單判斷，如果不滿足 currentMillis <= lastTime，則返回錯誤即可。

作者：cyningsun
來源：www.cyningsun.com/12-26-2018/id-generator.html