導(dǎo)讀：在業(yè)務(wù)系統(tǒng)中很多場景下需要生成不重復(fù)的 ID，比如訂單編號、支付流水單號、優(yōu)惠券編號等都需要使用到。

文｜古德

網(wǎng)易云信資深 JAVA 開發(fā)工程師

本文將介紹分布式 ID 的產(chǎn)生原因，以及目前業(yè)界常用的四種分布式 ID 實現(xiàn)方案，并且詳細(xì)介紹其中兩種的實現(xiàn)以及優(yōu)缺點，希望可以給您帶來關(guān)于分布式 ID 的啟發(fā)。

為什么要用分布式 ID

隨著業(yè)務(wù)數(shù)據(jù)量的增長，存儲在數(shù)據(jù)庫中的數(shù)據(jù)越來越多，當(dāng)索引占用的空間超出可用內(nèi)存大小后，就會通過磁盤索引來查找數(shù)據(jù)，這樣就會極大的降低數(shù)據(jù)查詢速度。如何解決這樣的問題呢？一般我們首先通過分庫分表來解決，分庫分表后就無法使用數(shù)據(jù)庫自增 ID 來作為數(shù)據(jù)的唯一編號，那么就需要使用分布式 ID 來做唯一編號了。

分布式 ID 實現(xiàn)方案

目前，關(guān)于分布式 ID ，業(yè)界主要有以下四種實現(xiàn)方案：

• UUID：使用 JDK 的 UUID#randomUUID() 生成的 ID；

• Redis 的原子自增：使用 Jedis#incr(String key) 生成的 ID；

• Snowflake 算法：以時間戳機(jī)器號和毫秒內(nèi)并發(fā)組成的 64 位 Long 型 ID；

• 分段步長：按照步長從數(shù)據(jù)庫讀取一段可用范圍的 ID；

我們總結(jié)一下這幾種方案的特點：

方案	順序性	重復(fù)性	可用性	部屬方式	可用時間
UUID	無序	通過多位隨機(jī)字符達(dá)到極低重復(fù)概率，但理論上是會重復(fù)的	一直可用	JDK 直接調(diào)用	永久
Redis	單調(diào)遞增	RDB?持久化模式下，會出現(xiàn)重復(fù)	Redis 宕機(jī)后不可用	Jedis 客戶調(diào)用	永久
Sonwflake	趨勢遞增	不會重復(fù)	發(fā)生時鐘回?fù)懿⑶一負(fù)軙r間超過等待閾值時不可用	集成部署、集群部署	69年
分段步長	趨勢遞增	不會重復(fù)	如果數(shù)據(jù)庫宕機(jī)并且獲取步長內(nèi)的 ID 用完后不可用	集成部署、集群部署	永久

前面兩種實現(xiàn)方案的用法以及實現(xiàn)大家日常了解較多，就不在此贅述...本文我們會詳細(xì)介紹 Snowflake 算法以及分段步長方案。

Snowflake 算法可以做到分配好機(jī)器號后就可以使用，不依賴任何第三方服務(wù)實現(xiàn)本地 ID 生成，依賴的第三方服務(wù)越少可用性越高，那么我們先來介紹一下 Snowflake 算法。

Snowflake 算法

長整型數(shù)字（即 Long 型數(shù)字）的十進(jìn)制范圍是 -2^64 到 2^64-1。

Snowflake 使用的是無符號長整型數(shù)字，即從左到右一共 64 位二進(jìn)制組成，但其第一位是不使用的。所以，在 Snowflake 中使用的是 63bit 的長整型無符號數(shù)字，它們由時間戳、機(jī)器號、毫秒內(nèi)并發(fā)序列號三個部分組成 ：

• 時間戳位：當(dāng)前毫秒時間戳與新紀(jì)元時間戳的差值（所謂新紀(jì)元時間戳就是應(yīng)用開始使用 Snowflake 的時間。如果不設(shè)置新紀(jì)元時間，時間戳默認(rèn)是從1970年開始計算的，設(shè)置了新紀(jì)元時間可以延長 Snowflake 的可用時間）。41 位 2 進(jìn)制轉(zhuǎn)為十進(jìn)制是 2^41，除以（365 天 * 24 小時 * 3600 秒 * 1000 毫秒），約等于 69年，所以最多可以使用 69 年；

• 機(jī)器號：10 位 2 進(jìn)制轉(zhuǎn)為十進(jìn)制是 2^10，即 1024，也就是說最多可以支持有 1024 個機(jī)器節(jié)點；

• 毫秒內(nèi)并發(fā)序列號：12 位 2 進(jìn)制轉(zhuǎn)為十進(jìn)制是 2^12，即 4096，也就是說一毫秒內(nèi)在一個機(jī)器節(jié)點上并發(fā)的獲取 ID，最多可以支持 4096 個并發(fā)；

下面我們來看一下各個分段的使用情況：

二進(jìn)制分段	[1]	[2,42]	[43,52]	[53,64]
說明	最高符號位不使用	一共41位，是毫秒時間戳	一共10位，是機(jī)器號位	一共12位，是毫秒內(nèi)并發(fā)序列號，當(dāng)前請求的時間戳如果和上一次請求的時間戳相同，那么就將毫秒內(nèi)并發(fā)序列號加一

那么 Snowflake 生成的 ID 長什么樣子呢？下面我們來舉幾個例子（假設(shè)我們的時間戳新紀(jì)元是 2020-12-31 00:00:00）：

時間	機(jī)器	毫秒并發(fā)	十進(jìn)制 Snowflake ID
2021-01-01 08:33:11	1	10	491031363588106
2021-01-02 13:11:12	2	25	923887730696217
2021-01-03 21:22:01	3	1	1409793654796289

Snowflake 可以使用三種不同的部署方式來部署，集成分布式部署方式、中心集群式部署方式、直連集群式部署方式。下面我們來分別介紹一下這幾種部署方式。

?Snowflake 集成分布式部署方式?

當(dāng)使用 ID 的應(yīng)用節(jié)點比較少時，比如 200 個節(jié)點以內(nèi)，適合使用集成分布式部署方式。每個應(yīng)用節(jié)點在啟動的時候決定了機(jī)器號后，運(yùn)行時不依賴任何第三方服務(wù)，在本地使用時間戳、機(jī)器號、以及毫秒內(nèi)并發(fā)序列號生成 ID。

下圖展示的是應(yīng)用服務(wù)器通過引入 jar 包的方式實現(xiàn)獲取分布式 ID 的過程。每一個使用分布式 ID 的應(yīng)用服務(wù)器節(jié)點都會分配一個拓?fù)渚W(wǎng)絡(luò)內(nèi)唯一的機(jī)器號。這個機(jī)器號的管理存放在 MySQL 或者 ZooKeeper 上。

當(dāng)拓?fù)渚W(wǎng)絡(luò)內(nèi)使用分布式 ID 的機(jī)器節(jié)點很多，例如超過 1000 個機(jī)器節(jié)點時，使用集成部署的分布式 ID 就不合適了，因為機(jī)器號位一共是 10 位，即最多支持 1024 個機(jī)器號。當(dāng)機(jī)器節(jié)點超過 1000 個機(jī)器節(jié)點時，可以使用下面要介紹的中心集群式部署方式。

?Snowflake 中心集群式部署方式?

中心集群式部署需要新增用來做請求轉(zhuǎn)發(fā)的 ID 網(wǎng)關(guān)，比如使用 nginx 反向代理（即下圖中的 ID REST API Gateway）。

使用 ID 網(wǎng)關(guān)組網(wǎng)后，應(yīng)用服務(wù)器通過 HTTP 或 RPC 請求 ID 網(wǎng)關(guān)獲取分布式 ID。這樣相比于上面的集成分布式部署方式，就可以支撐更多的應(yīng)用節(jié)點使用分布式 ID 了。

如圖所示，機(jī)器號的分配只是分配給下圖中的 ID Generator node 節(jié)點，應(yīng)用節(jié)點是不需要分配機(jī)器號的。

使用中心集群式部署方式需要引入新的 nginx 反向代理做網(wǎng)關(guān)，增加了系統(tǒng)的復(fù)雜性，降低了服務(wù)的可用性。那么我們下面再介紹一種不需要引入 nginx 又可以支持超過 1000 個應(yīng)用節(jié)點的直連集群部署方式。

?Snowflake 直連集群式部署方式?

相比于中心集群部署方式，直連集群部署方式可以去掉中間的 ID 網(wǎng)關(guān)，提高服務(wù)的可用性。

在使用 ID 網(wǎng)關(guān)的時候，我們需要把 ID generator node 的服務(wù)地址配置在 ID 網(wǎng)關(guān)中。而在使用直連集群式部署方式時，ID generator node 的服務(wù)地址可以配置在應(yīng)用服務(wù)器本地配置文件中，或者配置在配置中心。應(yīng)用服務(wù)器獲取到服務(wù)地址列表后，需要實現(xiàn)服務(wù)路由，直連 ID 生成器獲取 ID。

?Snowflake 算法存在的問題?

Snowflake 算法是強(qiáng)依賴時間戳的算法，如果一旦發(fā)生時鐘回?fù)芫蜁a(chǎn)生 ID 重復(fù)的問題。那么時鐘回?fù)苁窃趺串a(chǎn)生的，我們又需要怎么去解決這個問題呢？

NTP（Network Time Protocol）服務(wù)自動校準(zhǔn)可能導(dǎo)致時鐘回?fù)堋Ｎ覀兩磉叺拿恳慌_計算機(jī)都有自己本地的時鐘，這個時鐘是根據(jù) CPU 的晶振脈沖計算得來的，然而隨著運(yùn)行時間的推移，這個時間和世界時間的偏差會越來越大，那么 NTP 就是用來做時鐘校準(zhǔn)的服務(wù)。

一般情況下發(fā)生時鐘回?fù)艿母怕室卜浅Ｐ?#xff0c;因為一旦出現(xiàn)本地時間相對于世界時間需要校準(zhǔn)，但時鐘偏差值小于 STEP 閾值（默認(rèn)128毫秒）時，計算機(jī)會選擇以 SLEW 的方式進(jìn)行同步，即以 0.5 毫秒/秒的速度差調(diào)整時鐘速度，保證本地時鐘是一直連續(xù)向前的，不產(chǎn)生時鐘回?fù)?#xff0c;直到本地時鐘和世界時鐘對齊。

然而如果本地時鐘和世界時鐘相差大于 STEP 閾值時，就會發(fā)生時鐘回?fù)堋＿@個 STEP 閾值是可以修改的，但是修改的越大，在 SLEW 校準(zhǔn)的時候需要花費(fèi)的校準(zhǔn)時間就越長，例如 STEP 閾值設(shè)置為 10 分鐘，即本地時鐘與世界時鐘偏差在 10 分鐘以內(nèi)時都會以 SLEW 的方式進(jìn)行校準(zhǔn)，這樣最多會需要 14 天才會完成校準(zhǔn)。

為了避免時鐘回?fù)軐?dǎo)致重復(fù) ID 的問題，可以使用 128 毫秒的 STEP 閾值，同時在獲取 SnowflakeID 的時候與上一次的時間戳相比，判斷時鐘回?fù)苁欠裨?1 秒鐘以內(nèi)，如果在 1 秒鐘以內(nèi)，那么等待 1 秒鐘，否則服務(wù)不可用，這樣可以解決時鐘回?fù)?1 秒鐘的問題。

分段步長方案

Snowflake 由于是將時間戳作為長整形的高位，所以導(dǎo)致生成的最小數(shù)字也非常大。比如超過時間新紀(jì)元 1 秒鐘，機(jī)器號為 1，毫秒并發(fā)序列為 1 時，生成的 ID 就已經(jīng)到 4194308097 了。那么有沒有一種方法能夠?qū)崿F(xiàn)在初始狀態(tài)生成數(shù)字較小的 ID 呢？答案是肯定的，下面來介紹一下分段步長 ID 方案。

使用分段步長來生成 ID 就是將步長和當(dāng)前最大 ID 存在數(shù)據(jù)庫中，每次獲取 ID 時更新數(shù)據(jù)庫中的 ID 最大值增加步長。

數(shù)據(jù)庫核心表結(jié)構(gòu)如下所示：

CREATE TABLE `segment_id` (`id` bigint(20) NOT NULL AUTO_INCREMENT,`biz_type` varchar(64) NOT NULL DEFAULT '', // 業(yè)務(wù)類型`max` bigint(20) DEFAULT '0', // 當(dāng)前最大 ID 值`step` bigint(20) DEFAULT '10000', // ID 步長PRIMARY KEY (`id`) ) ENGINE=InnoDB AUTO_INCREMENT=3 DEFAULT CHARSET=utf8

在獲取 ID 時，使用開啟事務(wù)，利用行鎖保證讀取到當(dāng)前更新的最大 ID 值：

start transaction; update segment_id set max = max + step where biz_type = 'ORDER'; select max from segment_id where biz_type = 'ORDER'; commit

分段步長 ID 生成方案的優(yōu)缺點：

• 優(yōu)點：ID 生成不依賴時間戳，ID 生成初始值可以從 0 開始逐漸增加；

• 缺點：當(dāng)服務(wù)重啟時需要將最大 ID 值增加步長，頻繁重啟的話就會浪費(fèi)掉很多分段；

針對上述兩種實現(xiàn)方式的優(yōu)化

上文介紹了 Snowflake 算法以及分段步長方案，他們各有優(yōu)缺點，針對他們各自的情況我們在本文也給出相應(yīng)的優(yōu)化方案。

?ID 緩沖環(huán)?

為了提高?SnowflakeID?的并發(fā)性能和可用性，可以使用 ID 緩沖環(huán)（即 ID Buffer Ring）。提高并發(fā)性提現(xiàn)在通過使用緩沖環(huán)能夠充分利用毫秒時間戳，提高可用性提現(xiàn)在可以相對緩解由時鐘回?fù)軐?dǎo)致的服務(wù)不可用。緩沖環(huán)是通過定長數(shù)組加游標(biāo)哈希實現(xiàn)的，相比于鏈表會不需要頻繁的內(nèi)存分配。

在 ID 緩沖環(huán)初始化的時候會請求 ID 生成器將 ID 緩沖環(huán)填滿，當(dāng)業(yè)務(wù)需要獲取 ID 時，從緩沖環(huán)的頭部依次獲取 ID。當(dāng) ID 緩沖環(huán)中剩余的 ID 數(shù)量少于設(shè)定的閾值百分比時，比如剩余 ID 數(shù)量少于整個 ID 緩沖環(huán)的 30% 時，觸發(fā)異步 ID 填充加載。異步 ID 填充加載會將新生成的 ID 追加到 ID 緩沖環(huán)的隊列末尾，然后按照哈希算法映射到 ID 緩沖環(huán)上。另外有一個單獨的定時器異步線程來定時填充 ID 緩沖環(huán)。

下面的動畫展示了 ID 緩沖環(huán)的三個階段：ID 初始化加載、ID 消費(fèi)、ID 消費(fèi)后填充：

• Buffer Ring Initialize load，ID 緩沖環(huán)初始化加載：從 ID generator 獲取到 ID 填充到 ID 緩沖環(huán)，直到 ID 緩沖環(huán)被填滿；

• Buffer Ring consume，ID 緩沖環(huán)消費(fèi)：業(yè)務(wù)應(yīng)用從 ID 緩沖環(huán)獲取 ID；

• Async reload，異步加載填充 ID 緩沖環(huán)：定時器線程負(fù)責(zé)異步的從 ID generator 獲取 ID 添加到 ID 緩沖隊列，同時按照哈希算法映射到 ID 緩沖環(huán)上，當(dāng) ID 緩沖環(huán)被填滿時，異步加載填充結(jié)束；

下面的流程圖展示了 ID 緩沖環(huán)的運(yùn)行的整個生命周期，其中：

• IDConsumerServer：表示使用分布式 ID 的業(yè)務(wù)系統(tǒng)；

• IDBufferRing：ID 緩沖環(huán)；

• IDGenerator：ID 生成器；

• IDBufferRingAsyncLoadThread：異步加載 ID 到緩沖環(huán)的線程；

• Timer：負(fù)責(zé)定時向異步加載線程添加任務(wù)來裝載 ID；

• ID 消費(fèi)流程：即 上面提到的 Buffer Ring consume；

整體流程：客戶端業(yè)務(wù)請求到應(yīng)用服務(wù)器，應(yīng)用服務(wù)器從 ID 緩沖環(huán)獲取 ID，如果 ID 緩沖環(huán)內(nèi)空了那么拋出服務(wù)不可用；如果 ID 緩沖環(huán)內(nèi)存有 ID 那么就消費(fèi)一個 ID 。同時在消費(fèi) ID 緩沖環(huán)中的 ID 時，如果發(fā)現(xiàn) ID 緩沖環(huán)中存留的 ID 數(shù)量少于整個 ID 緩沖環(huán)容量的 30% 時觸發(fā)異步加載填充 ID 緩沖環(huán)。

?ID 雙桶 Buffer?

在使用分段步長 ID 時，如果該分段的 ID 用完了，需要更新數(shù)據(jù)庫分段最大值再繼續(xù)提供 ID 生成服務(wù)，為了減少數(shù)據(jù)庫更新查詢可能帶來的延時對 ID 服務(wù)的性能影響，可以使用雙桶緩存方案來提高 ID 生成服務(wù)的可用性。

其主要原理為：設(shè)計兩個緩存桶：currentBufferBucket 和 nextBufferBucket，每個桶都存放一個步長這么多的 ID，如果當(dāng)前緩存桶的 ID 用完了，那么就將下一個緩存桶設(shè)置為當(dāng)前緩存桶。

下面的動畫展示了雙桶緩存初始化、異步加載預(yù)備桶和將預(yù)備桶切換成當(dāng)前桶的全過程：

• Current bucket initial load：初始化當(dāng)前的緩存桶，即更新 max = max + step，然后獲取更新后的 max 值，比如步長是 1000，更新后的 max 值是 1000，那么桶的高度就是步長即 1000，桶 min = max - step + 1 = 1，max = 1000；

• Current bucket remaining id count down to 20%，Next bucket start to load。當(dāng)前緩存桶的 ID 剩余不足 20% 的時候可以加載下一個緩存桶，即更新 max = max + step，后獲取更新后的 max 值，此時更新后的 max 值是 2000，min = max - step + 1 = 1001， max = 2000；

• Current bucket is drained，Switch current bucket to the next bucket，如果當(dāng)前桶的 ID 全部用完了，那么就將下一個 ID 緩存桶設(shè)置為當(dāng)前桶；

下面是雙桶 Buffer 的流程圖：

總結(jié)

本文主要介紹了分布式 ID 的實現(xiàn)方案，并詳細(xì)介紹了其中 Snowflake 方案和分段步長方案，以及針對這兩種方案的優(yōu)化方案。我們再簡單總結(jié)一下兩個方案：

• 在高并發(fā)場景下生成大量的分布式 ID，適合使用 Snowflake 算法方案，毫秒內(nèi)并發(fā)序列為2^12=4096，單機(jī) QPS 支持高達(dá) 4 百萬，但是需要對 ID 生成器的機(jī)器號進(jìn)行管理；

• 使用分段步長方式生成 ID 就可以免去對機(jī)器號的管理，但是需要合理的設(shè)置步長，如果步長太短滿足不了并發(fā)需求，如果步長太長又會造成分段的過渡浪費(fèi)；

以上就是本文的全部內(nèi)容，如果有更多關(guān)于分布式 ID 的技術(shù)也歡迎留言與我們交流。

?作者介紹?

古德，網(wǎng)易云信資深 JAVA 開發(fā)工程師。現(xiàn)在負(fù)責(zé)網(wǎng)易會議賬戶體系、互動直播等模塊的設(shè)計與研發(fā)。對微服務(wù)、分布式事務(wù)等中間件技術(shù)方面有一定的經(jīng)驗。熱愛技術(shù)喜歡 Coding，善于面向?qū)ο笤O(shè)計編程、領(lǐng)域驅(qū)動設(shè)計與代碼優(yōu)化重構(gòu)。

?線上直播預(yù)告?

1月14日19:30，邀請到網(wǎng)易云信音視頻算法工程師線上分享《RTC 業(yè)務(wù)中的視頻編解碼引擎構(gòu)建》，歡迎掃碼關(guān)注直播~

?更多閱讀?

• Mobile DevOps 之 Proxmox 實現(xiàn)節(jié)流提效

• 線上開票系統(tǒng)設(shè)計實踐

• 細(xì)說websocket快速重連機(jī)制

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的浅谈分布式 ID 的实践与应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。