一文了解分布式系統(tǒng)ID生成策略

在分布式系統(tǒng)中，經(jīng)常需要對(duì)大量的數(shù)據(jù)、消息、http請(qǐng)求等進(jìn)行唯一標(biāo)識(shí)，例如鏈路追蹤traceId、身份標(biāo)識(shí)號(hào)、訂單流水號(hào)、操作記錄流水號(hào)、優(yōu)惠券id等等。

這個(gè)時(shí)候數(shù)據(jù)庫(kù)自增主鍵已經(jīng)不能滿(mǎn)足需求，需要一個(gè)能夠生成分布式ID的系統(tǒng)。

分布式ID的特性

1. 全局唯一。不能出現(xiàn)重復(fù)的ID，這是最基本的要求。

2. 遞增。遞增有利于關(guān)系數(shù)據(jù)庫(kù)索引性能。除了常見(jiàn)的連續(xù)遞增，如1001，1002，1003等等，分布式ID還存在趨勢(shì)遞增的形式，即保證下一個(gè)ID大于上一個(gè)ID但不連續(xù)。這樣的好處可以防止關(guān)鍵信息被泄露，例如toc業(yè)務(wù)中暴露給用戶(hù)的ID，可能會(huì)暴露用戶(hù)數(shù)量。（訂單id同理）

3. 高可用。為多個(gè)服務(wù)提供ID服務(wù)，一旦宕機(jī)，會(huì)造成嚴(yán)重影響。

4. 好接入。秉著拿來(lái)即用的設(shè)計(jì)原則，接入文檔要盡可能的簡(jiǎn)單。

5. 高性能：必須要在壓測(cè)下表現(xiàn)良好，如果達(dá)不到要求則在高并發(fā)環(huán)境下會(huì)導(dǎo)致系統(tǒng)癱瘓。

6. 靈活多變：每個(gè)業(yè)務(wù)場(chǎng)景對(duì)ID的要求也各不相同，ID生成要做到靈活多變可配置，盡可能多的滿(mǎn)足需求。

解決方案

1. UUID

UUID是Universally Unique Identifier的縮寫(xiě)，包含32個(gè)16進(jìn)制數(shù)字，以連字號(hào)分為五段，形式為8-4-4-4-12包含36個(gè)字符的字符串，例如：321dsa13-das2-d231-gfdd-213as8asd899

UUID經(jīng)由一定的算法機(jī)器生成，為了保證UUID的唯一性，規(guī)范定義了包括網(wǎng)卡MAC地址、時(shí)間戳、名字空間、隨機(jī)或偽隨機(jī)數(shù)、時(shí)序等元素，以及從這些元素生成UUID的算法。

優(yōu)點(diǎn)：

1. 性能非常高，本地生成，沒(méi)有網(wǎng)絡(luò)消耗。

2. 生成簡(jiǎn)單，沒(méi)有高可用風(fēng)險(xiǎn)。

3. 有利于信息安全，因?yàn)榭勺x性差，無(wú)規(guī)律。

缺點(diǎn)：

1. 太長(zhǎng)，不易于存儲(chǔ)。

2. 無(wú)序，對(duì)MySQL索引不利，在InnoDB中，UUID的無(wú)序性可能會(huì)引起數(shù)據(jù)位置頻繁變動(dòng)，嚴(yán)重影響性能。

3. UUID不能標(biāo)識(shí)業(yè)務(wù)含義，可讀性差。

2. 數(shù)據(jù)庫(kù)自增 ID

利用數(shù)據(jù)庫(kù)自增ID的特性來(lái)生成，如MySQL的auto_increment。其優(yōu)點(diǎn)是數(shù)字類(lèi)型，并且可以自增。當(dāng)然缺點(diǎn)就是并發(fā)場(chǎng)景下的性能瓶頸。

優(yōu)點(diǎn)：

1. 簡(jiǎn)單，利用數(shù)據(jù)庫(kù)自有功能實(shí)現(xiàn)。

2. ID嚴(yán)格連續(xù)自增，可以實(shí)現(xiàn)一些對(duì)ID有特殊要求的業(yè)務(wù)。

缺點(diǎn)：

1. 有重復(fù)發(fā)號(hào)的風(fēng)險(xiǎn)，例如MySQL數(shù)據(jù)庫(kù)主從切換的場(chǎng)景。

2. 發(fā)號(hào)性能限制于數(shù)據(jù)庫(kù)性能。

3. 強(qiáng)依賴(lài)數(shù)據(jù)庫(kù)，當(dāng)數(shù)據(jù)庫(kù)異常時(shí)整個(gè)系統(tǒng)不可用。

進(jìn)一步優(yōu)化：
放棄主從復(fù)制的高可用架構(gòu)，采用多主架構(gòu)。每個(gè)主庫(kù)設(shè)置不同的起始值和相同的步長(zhǎng)，保證了號(hào)段的隔離。

3. Redis

Redis中的incr命令，可以實(shí)現(xiàn)原子自增。相比較數(shù)據(jù)庫(kù)而言，Redis可支撐的并發(fā)量非常高，性能好。

但需要考慮下面兩種情況造成的數(shù)據(jù)不一致問(wèn)題：

1. 宕機(jī)后重啟恢復(fù)但存在未及時(shí)初始化。

2. 主從切換，主從數(shù)據(jù)同步延遲。

優(yōu)點(diǎn)：

1. 簡(jiǎn)單，自有能力。

2. 高并發(fā)環(huán)境下性能好，優(yōu)于數(shù)據(jù)庫(kù)。

缺點(diǎn)：

1. 可能會(huì)重復(fù)發(fā)號(hào)。

2. 需要保障Redis服務(wù)的高可用。

4. Zookeeper 實(shí)現(xiàn)

使用ZooKeeper作為分段節(jié)點(diǎn)協(xié)調(diào)工具，每臺(tái)服務(wù)器首先從Zookeeper 獲取一段號(hào)碼，如[1,1000]的ID，此時(shí)Zookeeper上保存最大值 1000，每次獲取的時(shí)候都會(huì)進(jìn)行判斷，如果ID <=1000，則更新本地的當(dāng)前值，如果為1001，則會(huì)將Zookeeper 上的最大值更新至2000，本地緩存段更新為1001-2000，更新的時(shí)候使用分布式鎖來(lái)實(shí)現(xiàn)。（相當(dāng)于用Zookeeper實(shí)現(xiàn)了基于數(shù)據(jù)庫(kù)的號(hào)段模式）

優(yōu)點(diǎn)：

效率高。

缺點(diǎn)：

維護(hù)成本較高，不能同時(shí)滿(mǎn)足多個(gè)系統(tǒng)對(duì)ID的需求，不夠靈活。

5、基于數(shù)據(jù)庫(kù)的號(hào)段模式

號(hào)段模式的思想是客戶(hù)端每次從數(shù)據(jù)庫(kù)中取出一批ID供程序使用，從表中獲取本次ID值的范圍，如[1,1000]，然后客戶(hù)端將申請(qǐng)的號(hào)段[1,1000]加載到內(nèi)存。表結(jié)構(gòu)參考如下：

CREATE TABLE id_generator (
  id int(10) NOT NULL,
  max_id bigint(20) NOT NULL COMMENT '當(dāng)前最大id',
  step int(20) NOT NULL COMMENT '號(hào)段的布長(zhǎng)',
  biz_type    int(20) NOT NULL COMMENT '業(yè)務(wù)類(lèi)型',
  version int(20) NOT NULL COMMENT '樂(lè)觀鎖版本號(hào)',
  PRIMARY KEY (`id`)
)

等這批號(hào)段ID用完，再次向數(shù)據(jù)庫(kù)申請(qǐng)新號(hào)段，對(duì)max_id字段做一次update操作（update id_generator set max_id = #{max_id+step}, version = version + 1 where version = # {version} and biz_type = XXX），update成功則說(shuō)明新號(hào)段獲取成功，新的號(hào)段范圍是(max_id ,max_id +step]

進(jìn)一步優(yōu)化：

1. 在號(hào)段消耗一半的時(shí)候，提前預(yù)留下一段號(hào)段。將預(yù)留號(hào)段時(shí)機(jī)提前，減少阻塞發(fā)生概率。一般稱(chēng)此為雙Buffer機(jī)制。

2. 不同業(yè)務(wù)可以設(shè)置不同的生成規(guī)則。

5.雪花算法

雪花算法（Snowflake）是twitter公司內(nèi)部分布式項(xiàng)目采用的ID生成算法，開(kāi)源后廣受?chē)?guó)內(nèi)大廠的好評(píng)，在該算法影響下各大公司相繼開(kāi)發(fā)出各具特色的分布式生成器。

雪花算法，不依賴(lài)其它系統(tǒng)或數(shù)據(jù)庫(kù)，以服務(wù)的方式部署，供其它服務(wù)調(diào)用，穩(wěn)定性高，生成 ID 的性能也非常高。

給每臺(tái)機(jī)器分配一個(gè)唯一標(biāo)識(shí)，然后通過(guò)下面的結(jié)構(gòu)實(shí)現(xiàn)全局唯一ID：

• 1位。未使用（二進(jìn)制中最高位為1的都是負(fù)數(shù)，所以這個(gè)最高位固定是0）

• 41位。毫秒級(jí)時(shí)間（41 位的長(zhǎng)度可以使用 69 年）

• 10位。包含5位datacenterId和5位workerId（10位的長(zhǎng)度最多支持部署1024個(gè)節(jié)點(diǎn)）

• 12位。最后12位是毫秒內(nèi)的計(jì)數(shù)（12位的計(jì)數(shù)順序號(hào)支持每個(gè)節(jié)點(diǎn)每毫秒產(chǎn)生4096個(gè)ID序號(hào)）

由于在Java中64bit的整數(shù)是long類(lèi)型，所以在Java中SnowFlake算法生成的id就是long來(lái)存儲(chǔ)的。

優(yōu)點(diǎn)：

1. 生成性能高。

2. 整體上按照時(shí)間自增排序。

缺點(diǎn)：

1. 強(qiáng)依賴(lài)機(jī)器時(shí)鐘，如果時(shí)鐘回?fù)?，可能?huì)導(dǎo)致服務(wù)異常。

2. 不能同時(shí)滿(mǎn)足多個(gè)系統(tǒng)對(duì)ID的需求，不夠靈活。

3. 在單機(jī)上是遞增的，但是由于涉及到分布式環(huán)境，每臺(tái)機(jī)器上的時(shí)鐘不可能完全同步，會(huì)出現(xiàn)不是全局遞增的情況。

6.Tinyid

Tinyid是滴滴開(kāi)源的分布式ID生成方案，開(kāi)源地址見(jiàn)于參考文檔1，只提供基于號(hào)段模式來(lái)生成ID（加入了雙Buffer機(jī)制）。

7.Uidgenerator

UidGenerator是由百度技術(shù)部開(kāi)發(fā)，開(kāi)源地址見(jiàn)于參考文檔2，基于Snowflake實(shí)現(xiàn)的優(yōu)化算法。借用未來(lái)時(shí)間和雙Buffer來(lái)解決時(shí)間回?fù)芘c生成性能等問(wèn)題，同時(shí)結(jié)合MySQL進(jìn)行ID分配。

8.Leaf

Leaf是美團(tuán)開(kāi)源的分布式ID生成方案，開(kāi)源地址見(jiàn)于參考文檔3。提供兩種生成的ID的方式：雪花算法模式和號(hào)段模式?？赏ㄟ^(guò)配置文件來(lái)指定。

Leaf的雪花算法模式依賴(lài)于ZooKeeper，其workId的生成策略是基于ZooKeeper的順序ID來(lái)生成的；號(hào)段模式也是基于數(shù)據(jù)庫(kù)的號(hào)段模式+雙Buffer機(jī)制實(shí)現(xiàn)的。

參考文檔：

1. https://github.com/didi/tinyid

2. https://github.com/baidu/uid-generator

3. https://github.com/Meituan-Dianping/Leaf