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

背景

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

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

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

分布式系統(tǒng)使用唯一的ID生成器，會(huì)有非常嚴(yán)重的申請(qǐng)互斥問(wèn)題。互斥加鎖意味著成本和性能的下降，不容易去實(shí)現(xiàn)一個(gè)高性能高可靠的架構(gòu)。在業(yè)務(wù)系統(tǒng)中，往往也不需要全局唯一的ID。

比如在通訊系統(tǒng)里，聊天消息不需要全局唯一，標(biāo)識(shí)一條用戶發(fā)出的消息的ID，只要保證用戶唯一性即可。因?yàn)橄⒈旧須w屬于某一用戶，因此用戶唯一已經(jīng)隱含了“全局唯一ID （ = 用戶ID + 消息ID ）”。

時(shí)間相關(guān)：“秒級(jí)” vs “毫秒”？

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

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

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

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

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

設(shè)計(jì)細(xì)節(jié)

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

SnowFlake

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

Weibo

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

Flicker

Flicker 在解決全局ID生成方案里就采用了MySQL自增長(zhǎng)ID的機(jī)制（auto_increment + replace into + MyISAM）。在我們的應(yīng)用端需要做下面這兩個(gè)操作，在一個(gè)事務(wù)會(huì)話里提交：

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

Flicker啟用了兩臺(tái)數(shù)據(jù)庫(kù)服務(wù)器生成ID來(lái)容災(zāi)，通過(guò)區(qū)分auto_increment的起始值和步長(zhǎng)來(lái)生成奇偶數(shù)的ID。

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

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

微信

微信使用MySQL持久化未分配的最大ID，每次從DB取一段放到內(nèi)存分配給調(diào)用方。微信的ID生成是嚴(yán)格遞增的，意味著同一時(shí)間只能有一臺(tái)機(jī)器提供服務(wù)，因此使用仲裁服務(wù)+租約機(jī)制+路由表，進(jìn)行容災(zāi)。

Shopee Feeds 如何生成ID ？

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

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

這樣的ID生成器可以使用大約17年，對(duì)于一款產(chǎn)品的生命周期來(lái)說(shuō)已經(jīng)足夠使用。

針對(duì)時(shí)間回?fù)墚a(chǎn)生的問(wèn)題，因?yàn)榘l(fā)生的頻率極小，所以只需要簡(jiǎn)單判斷，如果不滿足 currentMillis <= lastTime，則返回錯(cuò)誤即可。

作者：cyningsun
來(lái)源：www.cyningsun.com/12-26-2018/id-generator.html