如何選擇合適的分布式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é)任，概括起來有以下幾點(diǎn)：

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

分布式系統(tǒng)使用唯一的ID生成器，會(huì)有非常嚴(yán)重的申請(qǐng)互斥問題。互斥加鎖意味著成本和性能的下降，不容易去實(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í)間并沒有那么多。你如果精確到秒級(jí)別，三十年都要使用30bit，到毫秒級(jí)則要再增加10bit，你也只剩下20bit 可以做其他事情了。每秒一個(gè)或者每毫秒一個(gè)ID明顯是不夠的，剛才說到還有20bit 可以做其他事情，就包括一個(gè)SequenceID。

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

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

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

SnowFlake

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

Weibo

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

Flicker

Flicker 在解決全局ID生成方案里就采用了MySQL自增長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ù)庫服務(wù)器生成ID來容災(zāi)，通過區(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取一段放到內(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），來保證ID作為Redis的score不會(huì)溢出。

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

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

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

作者：cyningsunwww.cyningsun.com/12-26-2018/id-generator.html

分享&在看