帶你吃透幾種大廠分布式ID設(shè)計(jì)方案

“

今天無聊帶你們撩一下主流的分布式ID生成方案

前言

最近公司在擴(kuò)招后端高級(jí)開發(fā)，有幸成為面試官之一，其中問的最多一個(gè)問題就是分布式ID的幾種解決方案，不客氣的說前身小公司的開發(fā)答得完整的很少。

于是就抽出了周末的時(shí)間整理了幾種主流的分布式ID生成方案，希望能夠幫助到你們。

開篇幾個(gè)問題

1. 為什么需要分布式全局唯一ID以及分布式ID的業(yè)務(wù)需求

在復(fù)雜分布式系統(tǒng)中，往往需要對(duì)大量的數(shù)據(jù)和消息進(jìn)行唯一標(biāo)識(shí)。

• 如在美團(tuán)點(diǎn)評(píng)的金融、支付、餐飲、酒店等業(yè)務(wù)場(chǎng)景
• 貓眼電影等產(chǎn)品的系統(tǒng)中數(shù)據(jù)日漸增長(zhǎng)，對(duì)數(shù)據(jù)分庫分表后需要有一個(gè)唯一ID來表示一條數(shù)據(jù)或者消息。
• 特別一點(diǎn)的如訂單、騎手、優(yōu)惠劵也都需要一個(gè)唯一ID做為標(biāo)識(shí)。

此時(shí)一個(gè)能生成唯一ID的系統(tǒng)是非常必要的。

2. ID生成規(guī)則部分硬性要求

1. 全局唯一：既然是唯一標(biāo)識(shí)，那么全局唯一是最基本的要求。
2. 趨勢(shì)遞增：在MySQL的InnoDB引擎中使用的是聚集索引，由于多數(shù)RDBMS使用Btree的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)索引數(shù)據(jù)，在主鍵的選擇上面我們應(yīng)該盡量使用有序的主鍵來保證寫入性能。
3. 單調(diào)遞增：保證下一個(gè)ID一定大于上一個(gè)ID，例如事務(wù)版本號(hào)、IM增量消息、排序等特殊需求。
4. 信息安全：如果ID是連續(xù)的，那么惡意用戶的扒取工作就非常容易做了，直接按照順序下載指定URL即可；如果是訂單號(hào)那么更加危險(xiǎn)，競(jìng)爭(zhēng)對(duì)手可以知道我們一天的單量;所以在一些應(yīng)用場(chǎng)景下，需要ID無規(guī)則不規(guī)則，讓競(jìng)爭(zhēng)對(duì)手不好猜。
5. 含時(shí)間戳：這樣就能在開發(fā)中快速了解這個(gè)分布式ID的生成時(shí)間。

3. ID生成系統(tǒng)的可用性要求

1. 高可用：發(fā)一個(gè)獲取分布式ID的請(qǐng)求，服務(wù)器就要保證99.999%的情況下給我創(chuàng)建一個(gè)唯一分布式ID
2. 低延遲：發(fā)一個(gè)獲取分布式ID的請(qǐng)求，服務(wù)器就要快，極速
3. 高QPS：假如并發(fā)一口氣10萬個(gè)創(chuàng)建分布式ID請(qǐng)求同時(shí)過來，服務(wù)器需要頂?shù)米∏页晒?chuàng)建10萬個(gè)分布式ID

通用的幾種方案

隨著系統(tǒng)架構(gòu)以及業(yè)務(wù)的演變，分布式ID生成也是有N中解決方案，以下就簡(jiǎn)單的列舉幾種。

1. UUID

這種方案估計(jì)大家都了解，最簡(jiǎn)單的一種方案。

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

如果只是考慮唯一性，那么UUID基本可以滿足需求。

缺點(diǎn)

• 無序：無法預(yù)測(cè)他的生成順序，不能生成遞增有序的數(shù)字
• 主鍵：ID作為主鍵時(shí)在特定的環(huán)境下會(huì)存在一些問題，比如做DB主鍵的場(chǎng)景下，UUID非常不適用，MySQL官方有明確的建議主鍵要盡量越短越好，36位的UUID不合要求。
• 索引：會(huì)導(dǎo)致B+樹索引的分裂。

2. 數(shù)據(jù)庫自增主鍵

此種方案有一定的局限性，在高并發(fā)集群上此策略不可用。

3. 基于Redis生成全局ID策略

• 因?yàn)镽edis是單線程，天生保證原子性，所以可以使用INCR和INCRBY來實(shí)現(xiàn)。
• 集群分布式

“

在Redis集群下，同樣和MySQL一樣需要設(shè)置不同的增長(zhǎng)步數(shù)，同時(shí)key需要設(shè)置有效期;可以使用Redis集群來獲取更高的吞吐量;假如一個(gè)集群中有五個(gè)Redis，那么初始化每臺(tái)Redis步長(zhǎng)分別是1，2，3，4，5，然后步長(zhǎng)都是5。

4. snowflake(雪花算法)

• 推特的雪花算法生成ID能夠按照時(shí)間有序生成。
• 雪花算法生成ID的結(jié)果是一個(gè)64bit大小的整數(shù)，為一個(gè)Long型（轉(zhuǎn)換為字符串后長(zhǎng)度最多19）
• 分布式系統(tǒng)內(nèi)不會(huì)產(chǎn)生ID碰撞（由datecenter和workerId作區(qū)分），并且效率較高。

結(jié)構(gòu)

雪花算法的幾個(gè)核心組成部分如下圖：

號(hào)段解析

• 1bit符號(hào)位：不用，因?yàn)槎M(jìn)制最高位是符號(hào)位，1表示負(fù)數(shù)，0表示正數(shù)，生成的id一般都是用正數(shù)，所以最高位固定位0

• 41bit時(shí)間戳，用于記錄時(shí)間戳，毫秒級(jí)

• 41位可以表示2^41 - 1個(gè)數(shù)字
• 如果只用來表示正整數(shù)（計(jì)算機(jī)正數(shù)包含0），可以表示的數(shù)值范圍是0-2^41 - 1，減一是因?yàn)榭杀硎镜臄?shù)值范圍是從0開始算的，而不是1
• 也就是說41位可以表示2^41 - 1個(gè)毫秒的值，轉(zhuǎn)換為單位年則是69年。

• 10bit工作進(jìn)程位，用于記錄工作機(jī)器id

• 可以部署在2^10 = 1024個(gè)節(jié)點(diǎn)，包括五位datacenterId和五位workerId
• 五位可以表示的最大整數(shù)位2^5 - 1 = 31，即可以使用0，1，2…31這32個(gè)數(shù)字來表示不同的datacenterId和workerId

• 12bit序列號(hào)，序列號(hào)，用來記錄同毫秒內(nèi) 產(chǎn)生的不同的ID

• 12bit可以表示的最大正整數(shù)位2^12 - 1 = 4095，即可以表示0，1….4094這4095個(gè)數(shù)字
• 表示同一機(jī)器同一時(shí)間戳（毫秒）中產(chǎn)生的4095個(gè)ID序號(hào)

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

• 所有生成的id按時(shí)間趨勢(shì)遞增
• 整個(gè)分布式內(nèi)不會(huì)產(chǎn)生重復(fù)id，因?yàn)橛衐atacenterId和workerId來做區(qū)分。
• 毫秒數(shù)在高位，自增序列在低位，整個(gè)ID都是趨勢(shì)遞增的
• 不依賴數(shù)據(jù)庫、redis等第三方系統(tǒng)，以服務(wù)的方式部署，穩(wěn)定性更高，生成ID的性能也是非常高的。
• 可以根據(jù)自身業(yè)務(wù)分配bit位，非常靈活。

缺點(diǎn)

• 依賴機(jī)器時(shí)鐘，如果機(jī)器時(shí)鐘回退，會(huì)導(dǎo)致重復(fù)ID生成
• 在單機(jī)上是遞增的，但是由于設(shè)計(jì)到分布式環(huán)境，每臺(tái)機(jī)器上的時(shí)鐘不可能完全同步，有時(shí)候會(huì)出現(xiàn)不是全局遞增的情況。（此缺點(diǎn)可以認(rèn)為蕪鎖胃，一般分布式ID只要求趨勢(shì)遞增，并不會(huì)嚴(yán)格要求遞增，90%的需求都只需要趨勢(shì)遞增）

源碼

/**
?*?twitter的snowflake算法?--?java實(shí)現(xiàn)
?*?
?*?@author?beyond
?*?@date?2016/11/26
?*/
public?class?SnowFlake?{

????/**
?????*?起始的時(shí)間戳
?????*/
????private?final?static?long?START_STMP?=?1480166465631L;

????/**
?????*?每一部分占用的位數(shù)
?????*/
????private?final?static?long?SEQUENCE_BIT?=?12;?//序列號(hào)占用的位數(shù)
????private?final?static?long?MACHINE_BIT?=?5;???//機(jī)器標(biāo)識(shí)占用的位數(shù)
????private?final?static?long?DATACENTER_BIT?=?5;//數(shù)據(jù)中心占用的位數(shù)

????/**
?????*?每一部分的最大值
?????*/
????private?final?static?long?MAX_DATACENTER_NUM?=?-1L?^?(-1L?<????private?final?static?long?MAX_MACHINE_NUM?=?-1L?^?(-1L?<????private?final?static?long?MAX_SEQUENCE?=?-1L?^?(-1L?<
????/**
?????*?每一部分向左的位移
?????*/
????private?final?static?long?MACHINE_LEFT?=?SEQUENCE_BIT;
????private?final?static?long?DATACENTER_LEFT?=?SEQUENCE_BIT?+?MACHINE_BIT;
????private?final?static?long?TIMESTMP_LEFT?=?DATACENTER_LEFT?+?DATACENTER_BIT;

????private?long?datacenterId;??//數(shù)據(jù)中心
????private?long?machineId;?????//機(jī)器標(biāo)識(shí)
????private?long?sequence?=?0L;?//序列號(hào)
????private?long?lastStmp?=?-1L;//上一次時(shí)間戳

????public?SnowFlake(long?datacenterId,?long?machineId)?{
????????if?(datacenterId?>?MAX_DATACENTER_NUM?||?datacenterId?0)?{
????????????throw?new?IllegalArgumentException("datacenterId?can't?be?greater?than?MAX_DATACENTER_NUM?or?less?than?0");
????????}
????????if?(machineId?>?MAX_MACHINE_NUM?||?machineId?0)?{
????????????throw?new?IllegalArgumentException("machineId?can't?be?greater?than?MAX_MACHINE_NUM?or?less?than?0");
????????}
????????this.datacenterId?=?datacenterId;
????????this.machineId?=?machineId;
????}

????/**
?????*?產(chǎn)生下一個(gè)ID
?????*
?????*?@return
?????*/
????public?synchronized?long?nextId()?{
????????long?currStmp?=?getNewstmp();
????????if?(currStmp?????????????throw?new?RuntimeException("Clock?moved?backwards.??Refusing?to?generate?id");
????????}

????????if?(currStmp?==?lastStmp)?{
????????????//相同毫秒內(nèi)，序列號(hào)自增
????????????sequence?=?(sequence?+?1)?&?MAX_SEQUENCE;
????????????//同一毫秒的序列數(shù)已經(jīng)達(dá)到最大
????????????if?(sequence?==?0L)?{
????????????????currStmp?=?getNextMill();
????????????}
????????}?else?{
????????????//不同毫秒內(nèi)，序列號(hào)置為0
????????????sequence?=?0L;
????????}

????????lastStmp?=?currStmp;

????????return?(currStmp?-?START_STMP)?<//時(shí)間戳部分
????????????????|?datacenterId?<//數(shù)據(jù)中心部分
????????????????|?machineId?<//機(jī)器標(biāo)識(shí)部分
????????????????|?sequence;?????????????????????????????//序列號(hào)部分
????}

????private?long?getNextMill()?{
????????long?mill?=?getNewstmp();
????????while?(mill?<=?lastStmp)?{
????????????mill?=?getNewstmp();
????????}
????????return?mill;
????}

????private?long?getNewstmp()?{
????????return?System.currentTimeMillis();
????}

????public?static?void?main(String[]?args)?{
????????SnowFlake?snowFlake?=?new?SnowFlake(2,?3);

????????for?(int?i?=?0;?i?1?<12);?i++)?{
????????????System.out.println(snowFlake.nextId());
????????}

????}
}

測(cè)試

//測(cè)試使用雪花算法生成ID
//構(gòu)造函數(shù)中傳入datacenterId和workerId
SnowFlake?snowFlake?=?new?SnowFlake(1,1);
for?(int?i?=?0;?i?10;?i++)?{
????long?id?=?snowFlake.nextId();
????System.out.println("id："?+?id?+?"\t"?+?String.valueOf(id).length()?+?"位");
????System.out.println("------------------------------------------");
}

Spring Boot整合雪花算法

引入hutool-all，maven依賴引入如下：

<dependencies>
????<dependency>
????????<groupId>cn.hutoolgroupId>
????????<artifactId>hutool-allartifactId>
????????<version>5.4.2version>
????dependency>
????<dependency>
????????<groupId>org.springframework.bootgroupId>
????????<artifactId>spring-boot-starter-webartifactId>
????????<version>2.2.1.RELEASEversion>
????dependency>
????<dependency>
????????<groupId>org.projectlombokgroupId>
????????<artifactId>lombokartifactId>
????????<version>1.18.16version>
????dependency>
dependencies>

創(chuàng)建一個(gè)SnowFlake配置類

@Configuration
public?class?SnowFlakeConfig?{
????@Value("${application.datacenterId}")
????private?Long?datacenterId;
????@Value("${application.workerId}")
????private?Long?workerId;

????/***
?????*?注入一個(gè)生成雪花ID的對(duì)象
?????*?@return
?????*/
????@Bean
????public?Snowflake?snowflake()?{
????????return?new?Snowflake(workerId,datacenterId);
????}
}

yml配置文件：

application:
??datacenterId:?2
??workerId:?1
server:
??port:?7777

service 層：

@Service
public?class?OrderService?{
????@Autowired
????private?Snowflake?snowflake;

????public?String?getIdBySnowFlake()?{
????????return?String.valueOf(snowflake.nextId());
????}
}

其他開源的解決方案

很多大廠都對(duì)雪花算法做出了改進(jìn)，開源了一些改進(jìn)方案，如下：

• 百度開源的分布式唯一ID生成器UidGenerator
• Leaf–美團(tuán)點(diǎn)評(píng)分布式ID生成系統(tǒng)