京東一面：高并發(fā)下，如何保證分布式唯一全局 ID 生成？

來源：blog.csdn.net/LookForDream_/article/details/109355335
前言
系統(tǒng)唯一ID是我們在設(shè)計一個系統(tǒng)的時候常常會遇見的問題，也常常為這個問題而糾結(jié)。
這篇文章就是給各位看官提供一個生成分布式唯一全局id生成方案的思路，希望能幫助到大家。
不足之處，請多多指教??！
問題
為什么需要分布式全局唯一ID以及分布式ID的業(yè)務(wù)需求
在復(fù)雜分布式系統(tǒng)中，往往需要對大量的數(shù)據(jù)和消息進行唯一標(biāo)識，如在美團點評的金融、支付、餐飲、酒店
貓眼電影等產(chǎn)品的系統(tǒng)中數(shù)據(jù)逐漸增長，對數(shù)據(jù)庫分庫分表后需要有一個唯一ID來標(biāo)識一條數(shù)據(jù)或信息；
特別Ian的訂單、騎手、優(yōu)惠券都需要有唯一ID做標(biāo)識
此時一個能夠生成全局唯一ID的系統(tǒng)是非常必要的
ID生成規(guī)則部分硬性要求
全局唯一
趨勢遞增

在MySQL的InnoDB引擎中使用的是聚集索引，由于多數(shù)RDBMS使用Btree的數(shù)據(jù)結(jié)構(gòu)來存儲索引，在主鍵的選擇上面我們應(yīng)該盡量使用有序的主鍵保證寫入性能
單調(diào)遞增

保證下一個ID一定大于上一個ID，例如事務(wù)版本號、IM增量消息、排序等特殊需求
信息安全

如果ID是連續(xù)，惡意用戶的爬取工作就非常容易做了，直接按照順序下載指定URL即可，如果是訂單號就危險了，競爭對手可以直接知道我們一天的單量，所以在一些應(yīng)用場景下，需要ID無規(guī)則不規(guī)則，讓競爭對手不好猜
含時間戳

一樣能夠快速在開發(fā)中了解這個分布式ID什么時候生成的
ID號生成系統(tǒng)的可用性要求
高可用

發(fā)布一個獲取分布式ID請求，服務(wù)器就要保證99.999%的情況下給我創(chuàng)建一個唯一分布式ID
低延遲

發(fā)一個獲取分布式ID的請求，服務(wù)器就要快，極速
高QPS

例如并發(fā)一口氣10萬個創(chuàng)建分布式ID請求同時殺過來，服務(wù)器要頂?shù)米∏乙幌伦映晒?chuàng)建10萬個分布式ID
一般通用解決方案
UUID
UUID.randomUUID(), UUID的標(biāo)準(zhǔn)型包含32個16進制數(shù)字，以連字號分為五段，形式為 8-4-4-4-12的36個字符，性能非常高，本地生成，沒有網(wǎng)絡(luò)消耗。
存在問題
入數(shù)據(jù)庫性能差，因為UUID是無序的
無序，無法預(yù)測他的生成順序，不能生成遞增有序的數(shù)字
首先分布式id一般都會作為逐漸，但是按照mysql官方推薦主鍵盡量越短越好，UUID每一個都很長，所以不是很推薦。另外，搜索公眾號互聯(lián)網(wǎng)架構(gòu)師后臺回復(fù)“2T”，獲取一份驚喜禮包。
主鍵，ID作為主鍵時，在特定的環(huán)境下會存在一些問題
比如做DB主鍵的場景下，UUID就非常不適用MySQL官方有明確的說明
索引，B+樹索引的分裂
既然分布式ID是主鍵，然后主鍵是包含索引的，而mysql的索引是通過B+樹來實現(xiàn)的，每一次新的UUID數(shù)據(jù)的插入，為了查詢的優(yōu)化，都會對索引底層的B+樹進行修改，因為UUID數(shù)據(jù)是無序的，所以每一次UUID數(shù)據(jù)的插入都會對主鍵的B+樹進行很大的修改，這一點很不好，插入完全無序，不但會導(dǎo)致一些中間節(jié)點產(chǎn)生分裂，也會白白創(chuàng)造出很多不飽和的節(jié)點，這樣大大降低了數(shù)據(jù)庫插入的性能。
UUID只能保證全局唯一性，不滿足后面的趨勢遞增，單調(diào)遞增
數(shù)據(jù)庫自增主鍵
單機
在分布式里面，數(shù)據(jù)庫的自增ID機制的主要原理是：數(shù)據(jù)庫自增ID和mysql數(shù)據(jù)庫的replace into實現(xiàn)的，這里的replace into跟insert功能 類似，不同點在于：replace into首先嘗試插入數(shù)據(jù)列表中，如果發(fā)現(xiàn)表中已經(jīng)有此行數(shù)據(jù)（根據(jù)主鍵或唯一索引判斷）則先刪除，在插入，否則直接插入新數(shù)據(jù)。
REPLACE INTO的含義是插入一條記錄，如果表中唯一索引的值遇到?jīng)_突，則替換老數(shù)據(jù)
REPLACE?into?t_test(stub)?values('b');
select?LAST_INSERT_ID();
我們每次插入的時候，發(fā)現(xiàn)都會把原來的數(shù)據(jù)給替換，并且ID也會增加
這就滿足了
遞增性
單調(diào)性
唯一性
在分布式情況下，并且并發(fā)量不多的情況，可以使用這種方案來解決，獲得一個全局的唯一ID
集群分布式集群
那數(shù)據(jù)庫自增ID機制適合做分布式ID嗎？答案是不太適合
系統(tǒng)水平擴展比較困難，比如定義好步長和機器臺數(shù)之后，如果要添加機器該怎么辦，假設(shè)現(xiàn)在有一臺機器發(fā)號是：1,2,3,4,5,（步長是1），這個時候需要擴容機器一臺，可以這樣做：把第二胎機器的初始值設(shè)置得比第一臺超過很多，貌似還好，但是假設(shè)線上如果有100臺機器，這個時候擴容要怎么做，簡直是噩夢，所以系統(tǒng)水平擴展方案復(fù)雜難以實現(xiàn)。
數(shù)據(jù)庫壓力還是很大，每次獲取ID都得讀寫一次數(shù)據(jù)庫，非常影響性能，不符合分布式ID里面的延遲低和高QPS的規(guī)則（在高并發(fā)下，如果都去數(shù)據(jù)庫里面獲取ID，那是非常影響性能的）
基于Redis生成全局ID策略
單機版
因為Redis是單線程，天生保證原子性，可以使用原子操作INCR和INCRBY來實現(xiàn)
INCRBY：設(shè)置增長步長
集群分布式
注意：在Redis集群情況下，同樣和MySQL一樣需要設(shè)置不同的增長步長，同時key一定要設(shè)置有效期，可以使用Redis集群來獲取更高的吞吐量。
假設(shè)一個集群中有5臺Redis，可以初始化每臺Redis的值分別是 1,2,3,4,5 ， 然后設(shè)置步長都是5
各個Redis生成的ID為：
A：1 6 11 16 21
B：2 7 12 17 22
C：3 8 13 18 23
D：4 9 14 19 24
E：5 10 15 20 25
但是存在的問題是，就是Redis集群的維護和保養(yǎng)比較麻煩，配置麻煩。因為要設(shè)置單點故障，哨兵值守
但是主要是的問題就是，為了一個ID，卻需要引入整個Redis集群，有種殺雞焉用牛刀的感覺。
雪花算法
是什么
Twitter的分布式自增ID算法，Snowflake
最初Twitter把存儲系統(tǒng)從MySQL遷移到Cassandra（由Facebook開發(fā)一套開源分布式NoSQL數(shù)據(jù)庫系統(tǒng)）因為Cassandra沒有順序ID生成機制，所有開發(fā)了這樣一套全局唯一ID生成服務(wù)。
Twitter的分布式雪花算法SnowFlake，經(jīng)測試SnowFlake每秒可以產(chǎn)生26萬個自增可排序的ID
twitter的SnowFlake生成ID能夠按照時間有序生成
SnowFlake算法生成ID的結(jié)果是一個64Bit大小的整數(shù)，為一個Long型（轉(zhuǎn)換成字符串后長度最多19）
分布式系統(tǒng)內(nèi)不會產(chǎn)生ID碰撞（由datacenter 和 workerID做區(qū)分）并且效率較高
分布式系統(tǒng)中，有一些需要全局唯一ID的場景，生成ID的基本要求
在分布式環(huán)境下，必須全局唯一性
一般都需要單調(diào)遞增，因為一般唯一ID都會存在數(shù)據(jù)庫，而InnoDB的特性就是將內(nèi)容存儲在主鍵索引上的葉子節(jié)點，而且是從左往右遞增的，所有考慮到數(shù)據(jù)庫性能，一般生成ID也最好是單調(diào)遞增的。為了防止ID沖突可以使用36位UUID，但是UUID有一些缺點，首先是它相對比較長，并且另外UUID一般是無序的
可能還會需要無規(guī)則，因為如果使用唯一ID作為訂單號這種，為了不讓別人知道一天的訂單量多少，就需要這種規(guī)則。
結(jié)構(gòu)
雪花算法的幾個核心組成部分
在Java中64bit的證書是long類型，所以在SnowFlake算法生成的ID就是long類存儲的
第一部分
二進制中最高位是符號位，1表示負(fù)數(shù)，0表示正數(shù)。生成的ID一般都是用整數(shù)，所以最高位固定為0。
第二部分
第二部分是41bit時間戳位，用來記錄時間戳，毫秒級
41位可以表示 2^41 -1 個數(shù)字
如果只用來表示正整數(shù)，可以表示的范圍是：0 - 2^41 -1，減1是因為可以表示的數(shù)值范圍是從0開始計算的，而不是從1。
也就是說41位可以表示 2^41 - 1 毫秒的值，轉(zhuǎn)換成單位年則是 69.73年
第三部分
第三部分為工作機器ID，10Bit用來記錄工作機器ID
可以部署在2^10 = 1024個節(jié)點，包括5位 datacenterId（數(shù)據(jù)中心，機房） 和 5位 workerID（機器碼）
5位可以表示的最大正整數(shù)是 2 ^ 5 = 31個數(shù)字，來表示不同的數(shù)據(jù)中心 和 機器碼
第四部分
12位bit可以用來表示的正整數(shù)是 2^12 = 4095，即可以用0 1 2 … 4094 來表示同一個機器同一個時間戳內(nèi)產(chǎn)生的4095個ID序號。
SnowFlake可以保證
所有生成的ID按時間趨勢遞增
整個分布式系統(tǒng)內(nèi)不會產(chǎn)生重復(fù)ID，因為有datacenterId 和 workerId來做區(qū)分
實現(xiàn)
雪花算法是由scala算法編寫的，有人使用java實現(xiàn)，github地址：
https://github.com/beyondfengyu/SnowFlake/blob/master/SnowFlake.java
/**
?*?twitter的snowflake算法?--?java實現(xiàn)
?*
?*?@author?beyond
?*/
public?class?SnowFlake?{

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

????/**
?????*?每一部分占用的位數(shù)
?????*/
????private?final?static?long?SEQUENCE_BIT?=?12;?//序列號占用的位數(shù)
????private?final?static?long?MACHINE_BIT?=?5;???//機器標(biāo)識占用的位數(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;?????//機器標(biāo)識
????private?long?sequence?=?0L;?//序列號
????private?long?lastStmp?=?-1L;//上一次時間戳

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

????/**
?????*?產(chǎn)生下一個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)，序列號自增
????????????sequence?=?(sequence?+?1)?&?MAX_SEQUENCE;
????????????//同一毫秒的序列數(shù)已經(jīng)達到最大
????????????if?(sequence?==?0L)?{
????????????????currStmp?=?getNextMill();
????????????}
????????}?else?{
????????????//不同毫秒內(nèi)，序列號置為0
????????????sequence?=?0L;
????????}

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

????????return?(currStmp?-?START_STMP)?<????????????????|?datacenterId?<????????????????|?machineId?<????????????????|?sequence;?????????????????????????????//序列號部分
????}

????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?????????????System.out.println(snowFlake.nextId());
????????}

????}
}
工程落地經(jīng)驗
hutools工具包
地址：https://github.com/looly/hutool
SpringBoot整合雪花算法
引入hutool工具類

????cn.hutool
????hutool-all
????5.3.1

整合
/**
?*?雪花算法
?*
?*?@author:?陌溪
?*/
public?class?SnowFlakeDemo?{
????private?long?workerId?=?0;
????private?long?datacenterId?=?1;
????private?Snowflake?snowFlake?=?IdUtil.createSnowflake(workerId,?datacenterId);

????@PostConstruct
????public?void?init()?{
????????try?{
????????????//?將網(wǎng)絡(luò)ip轉(zhuǎn)換成long
????????????workerId?=?NetUtil.ipv4ToLong(NetUtil.getLocalhostStr());
????????}?catch?(Exception?e)?{
????????????e.printStackTrace();
????????}
????}

????/**
?????*?獲取雪花ID
?????*?@return
?????*/
????public?synchronized?long?snowflakeId()?{
????????return?this.snowFlake.nextId();
????}

????public?synchronized?long?snowflakeId(long?workerId,?long?datacenterId)?{
????????Snowflake?snowflake?=?IdUtil.createSnowflake(workerId,?datacenterId);
????????return?snowflake.nextId();
????}

????public?static?void?main(String[]?args)?{
????????SnowFlakeDemo?snowFlakeDemo?=?new?SnowFlakeDemo();
????????for?(int?i?=?0;?i?????????????new?Thread(()?->?{
????????????????System.out.println(snowFlakeDemo.snowflakeId());
????????????},?String.valueOf(i)).start();
????????}
????}
}
得到結(jié)果
1251350711346790400
1251350711346790402
1251350711346790401
1251350711346790403
1251350711346790405
1251350711346790404
1251350711346790406
1251350711346790407
1251350711350984704
1251350711350984706
1251350711350984705
1251350711350984707
1251350711350984708
1251350711350984709
1251350711350984710
1251350711350984711
1251350711350984712
1251350711355179008
1251350711355179009
1251350711355179010
優(yōu)缺點
優(yōu)點
毫秒數(shù)在高維，自增序列在低位，整個ID都是趨勢遞增的
不依賴數(shù)據(jù)庫等第三方系統(tǒng)，以服務(wù)的方式部署，穩(wěn)定性更高，生成ID的性能也是非常高的。另外，搜索公眾號互聯(lián)網(wǎng)架構(gòu)師后臺回復(fù)“面試”，獲取一份驚喜禮包。
可以根據(jù)自身業(yè)務(wù)特性分配bit位，非常靈活
缺點
依賴機器時鐘，如果機器時鐘回?fù)?，會?dǎo)致重復(fù)ID生成
在單機上是遞增的，但由于涉及到分布式環(huán)境，每臺機器上的時鐘不可能完全同步，有時候會出現(xiàn)不是全局遞增的情況，此缺點可以認(rèn)為無所謂，一般分布式ID只要求趨勢遞增，并不會嚴(yán)格要求遞增，90%的需求只要求趨勢遞增。
其它補充
為了解決時鐘回?fù)軉栴}，導(dǎo)致ID重復(fù)，后面有人專門提出了解決的方案

百度開源的分布式唯一ID生成器 UidGenerator
Leaf - 美團點評分布式ID生成系統(tǒng)