背景

在復(fù)雜的分布式系統(tǒng)中，往往需要對大量的數(shù)據(jù)進(jìn)行唯一標(biāo)識，比如在對一個(gè)訂單表進(jìn)行了分庫分表操作，這時(shí)候數(shù)據(jù)庫的自增ID顯然不能作為某個(gè)訂單的唯一標(biāo)識。除此之外還有其他分布式場景對分布式ID的一些要求：

趨勢遞增： 由于多數(shù)RDBMS使用B-tree的數(shù)據(jù)結(jié)構(gòu)來存儲索引數(shù)據(jù)，在主鍵的選擇上面我們應(yīng)該盡量使用有序的主鍵保證寫入性能。

單調(diào)遞增： 保證下一個(gè)ID一定大于上一個(gè)ID，例如排序需求。

信息安全： 如果ID是連續(xù)的，惡意用戶的扒取工作就非常容易做了；如果是訂單號就更危險(xiǎn)了，可以直接知道我們的單量。所以在一些應(yīng)用場景下，會需要ID無規(guī)則、不規(guī)則。

就不同的場景及要求，市面誕生了很多分布式ID解決方案。本文針對多個(gè)分布式ID解決方案進(jìn)行介紹，包括其優(yōu)缺點(diǎn)、使用場景及代碼示例。

1、UUID

UUID(Universally Unique Identifier)是基于當(dāng)前時(shí)間、計(jì)數(shù)器（counter）和硬件標(biāo)識（通常為無線網(wǎng)卡的MAC地址）等數(shù)據(jù)計(jì)算生成的。包含32個(gè)16進(jìn)制數(shù)字，以連字號分為五段，形式為8-4-4-4-12的36個(gè)字符，可以生成全球唯一的編碼并且性能高效。

JDK提供了UUID生成工具，代碼如下：

import?java.util.UUID;

public?class?Test?{
????public?static?void?main(String[]?args)?{
????????System.out.println(UUID.randomUUID());
????}
}

輸出如下

b0378f6a-eeb7-4779-bffe-2a9f3bc76380

UUID完全可以滿足分布式唯一標(biāo)識，但是在實(shí)際應(yīng)用過程中一般不采用，有如下幾個(gè)原因：

存儲成本高： UUID太長，16字節(jié)128位，通常以36長度的字符串表示，很多場景不適用。

信息不安全： 基于MAC地址生成的UUID算法會暴露MAC地址，曾經(jīng)梅麗莎病毒的制造者就是根據(jù)UUID尋找的。

不符合MySQL主鍵要求： MySQL官方有明確的建議主鍵要盡量越短越好，因?yàn)樘L對MySQL索引不利：如果作為數(shù)據(jù)庫主鍵，在InnoDB引擎下，UUID的無序性可能會引起數(shù)據(jù)位置頻繁變動，嚴(yán)重影響性能。

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

利用Mysql的特性ID自增，可以達(dá)到數(shù)據(jù)唯一標(biāo)識，但是分庫分表后只能保證一個(gè)表中的ID的唯一，而不能保證整體的ID唯一。為了避免這種情況，我們有以下兩種方式解決該問題。

2.1、主鍵表

通過單獨(dú)創(chuàng)建主鍵表維護(hù)唯一標(biāo)識，作為ID的輸出源可以保證整體ID的唯一。舉個(gè)例子：

創(chuàng)建一個(gè)主鍵表

CREATE?TABLE?`unique_id`??(
??`id`?bigint?NOT?NULL?AUTO_INCREMENT,
??`biz`?char(1)?NOT?NULL,
??PRIMARY?KEY?(`id`),
?UNIQUE?KEY?`biz`?(`biz`)
)?ENGINE?=?InnoDB?AUTO_INCREMENT=1?DEFAULT?CHARSET?=utf8;

業(yè)務(wù)通過更新操作來獲取ID信息，然后添加到某個(gè)分表中。

BEGIN;

REPLACE?INTO?unique_id?(biz)?values?('o')?;
SELECT?LAST_INSERT_ID();

COMMIT;

?

?

2.2、ID自增步長設(shè)置

我們可以設(shè)置Mysql主鍵自增步長，讓分布在不同實(shí)例的表數(shù)據(jù)ID做到不重復(fù)，保證整體的唯一。

如下，可以設(shè)置Mysql實(shí)例1步長為1，實(shí)例1步長為2。

查看主鍵自增的屬性

show?variables?like?'%increment%'

顯然，這種方式在并發(fā)量比較高的情況下，如何保證擴(kuò)展性其實(shí)會是一個(gè)問題。

3、號段模式

號段模式是當(dāng)下分布式ID生成器的主流實(shí)現(xiàn)方式之一。其原理如下：

號段模式每次從數(shù)據(jù)庫取出一個(gè)號段范圍，加載到服務(wù)內(nèi)存中。業(yè)務(wù)獲取時(shí)ID直接在這個(gè)范圍遞增取值即可。

等這批號段ID用完，再次向數(shù)據(jù)庫申請新號段，對max_id字段做一次update操作，新的號段范圍是(max_id ,max_id +step]。

由于多業(yè)務(wù)端可能同時(shí)操作，所以采用版本號version樂觀鎖方式更新。

例如 (1,1000] 代表1000個(gè)ID，具體的業(yè)務(wù)服務(wù)將本號段生成1~1000的自增ID。表結(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?'號段的長度',
??biz_type????int(20)?NOT?NULL?COMMENT?'業(yè)務(wù)類型',
??version?int(20)?NOT?NULL?COMMENT?'版本號,是一個(gè)樂觀鎖，每次都更新version，保證并發(fā)時(shí)數(shù)據(jù)的正確性',
??PRIMARY?KEY?(`id`)
)?

這種分布式ID生成方式不強(qiáng)依賴于數(shù)據(jù)庫，不會頻繁的訪問數(shù)據(jù)庫，對數(shù)據(jù)庫的壓力小很多。但同樣也會存在一些缺點(diǎn)比如：服務(wù)器重啟，單點(diǎn)故障會造成ID不連續(xù)。

4、Redis INCR

基于全局唯一ID的特性，我們可以通過Redis的INCR命令來生成全局唯一ID。

Redis分布式ID的簡單案例

/**
?*??Redis?分布式ID生成器
?*/
@Component
public?class?RedisDistributedId?{

????@Autowired
????private?StringRedisTemplate?redisTemplate;

????private?static?final?long?BEGIN_TIMESTAMP?=?1659312000l;

????/**
?????*?生成分布式ID
?????*?符號位????時(shí)間戳[31位]??自增序號【32位】
?????*?@param?item
?????*?@return
?????*/
????public?long?nextId(String?item){
????????//?1.生成時(shí)間戳
????????LocalDateTime?now?=?LocalDateTime.now();
????????//?格林威治時(shí)間差
????????long?nowSecond?=?now.toEpochSecond(ZoneOffset.UTC);
????????//?我們需要獲取的?時(shí)間戳?信息
????????long?timestamp?=?nowSecond?-?BEGIN_TIMESTAMP;
????????//?2.生成序號?--》?從Redis中獲取
????????//?當(dāng)前當(dāng)前的日期
????????String?date?=?now.format(DateTimeFormatter.ofPattern("yyyydd"));
????????//?獲取對應(yīng)的自增的序號
????????Long?increment?=?redisTemplate.opsForValue().increment("id:"?+?item?+?":"?+?date);
????????return?timestamp?<

	同樣使用Redis也有對應(yīng)的缺點(diǎn)：ID 生成的持久化問題，如果Redis宕機(jī)了怎么進(jìn)行恢復(fù)?

	5、雪花算法

	Snowflake，雪花算法是有Twitter開源的分布式ID生成算法，以劃分命名空間的方式將64bit位分割成了多個(gè)部分，每個(gè)部分都有具體的不同含義，在Java中64Bit位的整數(shù)是Long類型，所以在Java中Snowflake算法生成的ID就是long來存儲的。具體如下：

	

	第一部分： 占用1bit，第一位為符號位，不適用

	第二部分： 41位的時(shí)間戳，41bit位可以表示241個(gè)數(shù)，每個(gè)數(shù)代表的是毫秒，那么雪花算法的時(shí)間年限是(241)/(1000×60×60×24×365)=69年

	第三部分： 10bit表示是機(jī)器數(shù)，即 2^ 10 = 1024臺機(jī)器，通常不會部署這么多機(jī)器

	第四部分： 12bit位是自增序列，可以表示2^12=4096個(gè)數(shù)，一秒內(nèi)可以生成4096個(gè)ID，理論上snowflake方案的QPS約為409.6w/s

	雪花算法案例代碼：

	public?class?SnowflakeIdWorker?{

????//?==============================Fields===========================================
????/**
?????*?開始時(shí)間截?(2020-11-03，一旦確定不可更改，否則時(shí)間被回調(diào)，或者改變，可能會造成id重復(fù)或沖突)
?????*/
????private?final?long?twepoch?=?1604374294980L;

????/**
?????*?機(jī)器id所占的位數(shù)
?????*/
????private?final?long?workerIdBits?=?5L;

????/**
?????*?數(shù)據(jù)標(biāo)識id所占的位數(shù)
?????*/
????private?final?long?datacenterIdBits?=?5L;

????/**
?????*?支持的最大機(jī)器id，結(jié)果是31?(這個(gè)移位算法可以很快的計(jì)算出幾位二進(jìn)制數(shù)所能表示的最大十進(jìn)制數(shù))
?????*/
????private?final?long?maxWorkerId?=?-1L?^?(-1L?<?maxWorkerId?||?workerId??maxDatacenterId?||?datacenterId?

	雪花算法強(qiáng)依賴機(jī)器時(shí)鐘，如果機(jī)器上時(shí)鐘回?fù)?，會?dǎo)致發(fā)號重復(fù)。通常通過記錄最后使用時(shí)間處理該問題。

	

	6、美團(tuán)(Leaf)

	Leaf同時(shí)支持號段模式和snowflake算法模式，可以切換使用。

	snowflake模式依賴于ZooKeeper，不同于原始snowflake算法也主要是在workId的生成上，Leaf中workId是基于ZooKeeper的順序Id來生成的，每個(gè)應(yīng)用在使用Leaf-snowflake時(shí)，啟動時(shí)都會都在Zookeeper中生成一個(gè)順序Id，相當(dāng)于一臺機(jī)器對應(yīng)一個(gè)順序節(jié)點(diǎn)，也就是一個(gè)workId。

	號段模式是對直接用數(shù)據(jù)庫自增ID充當(dāng)分布式ID的一種優(yōu)化，減少對數(shù)據(jù)庫的頻率操作。相當(dāng)于從數(shù)據(jù)庫批量的獲取自增ID，每次從數(shù)據(jù)庫取出一個(gè)號段范圍，例如 (1,1000] 代表1000個(gè)ID，業(yè)務(wù)服務(wù)將號段在本地生成1~1000的自增ID并加載到內(nèi)存。

	7、百度(Uidgenerator)

	UidGenerator是百度開源的Java語言實(shí)現(xiàn)，基于Snowflake算法的唯一ID生成器。它是分布式的，并克服了雪花算法的并發(fā)限制。單個(gè)實(shí)例的QPS能超過6000000。需要的環(huán)境：JDK8+，MySQL（用于分配WorkerId）。

	百度的Uidgenerator對結(jié)構(gòu)做了部分的調(diào)整，具體如下：

	

	時(shí)間部分只有28位，這就意味著UidGenerator默認(rèn)只能承受8.5年（2^28-1/86400/365），不過UidGenerator可以適當(dāng)調(diào)整delta seconds、worker node id和sequence占用位數(shù)。

	8、滴滴(TinyID)

	Tinyid是在美團(tuán)（Leaf）的leaf-segment算法基礎(chǔ)上升級而來，不僅支持了數(shù)據(jù)庫多主節(jié)點(diǎn)模式，還提供了tinyid-client客戶端的接入方式，使用起來更加方便。但和美團(tuán)（Leaf）不同的是，Tinyid只支持號段一種模式不支持雪花模式。Tinyid提供了兩種調(diào)用方式，一種基于Tinyid-server提供的http方式，另一種Tinyid-client客戶端方式。

	總結(jié)比較

	

	編輯：黃飛

	?