面試官：高并發(fā)下，如何保證分布式唯一全局 ID 生成？
前言
問題
為什么需要分布式全局唯一ID以及分布式ID的業(yè)務(wù)需求
ID生成規(guī)則部分硬性要求
全局唯一 趨勢遞增 在MySQL的InnoDB引擎中使用的是聚集索引，由于多數(shù)RDBMS使用Btree的數(shù)據(jù)結(jié)構(gòu)來存儲索引，在主鍵的選擇上面我們應(yīng)該盡量使用有序的主鍵保證寫入性能 單調(diào)遞增 保證下一個(gè)ID一定大于上一個(gè)ID，例如事務(wù)版本號、IM增量消息、排序等特殊需求 信息安全 如果ID是連續(xù)，惡意用戶的爬取工作就非常容易做了，直接按照順序下載指定URL即可，如果是訂單號就危險(xiǎn)了，競爭對手可以直接知道我們一天的單量，所以在一些應(yīng)用場景下，需要ID無規(guī)則不規(guī)則，讓競爭對手不好猜 含時(shí)間戳 一樣能夠快速在開發(fā)中了解這個(gè)分布式ID什么時(shí)候生成的
ID號生成系統(tǒng)的可用性要求
高可用 發(fā)布一個(gè)獲取分布式ID請求，服務(wù)器就要保證99.999%的情況下給我創(chuàng)建一個(gè)唯一分布式ID 低延遲 發(fā)一個(gè)獲取分布式ID的請求，服務(wù)器就要快，極速 高QPS 例如并發(fā)一口氣10萬個(gè)創(chuàng)建分布式ID請求同時(shí)殺過來，服務(wù)器要頂?shù)米∏乙幌伦映晒?chuàng)建10萬個(gè)分布式ID
一般通用解決方案
UUID
UUID.randomUUID(), UUID的標(biāo)準(zhǔn)型包含32個(gè)16進(jìn)制數(shù)字，以連字號分為五段，形式為 8-4-4-4-12的36個(gè)字符，性能非常高，本地生成，沒有網(wǎng)絡(luò)消耗。存在問題
數(shù)據(jù)庫自增主鍵
單機(jī)
replace into實(shí)現(xiàn)的，這里的replace into跟insert功能 類似，不同點(diǎn)在于：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();
遞增性 單調(diào)性 唯一性
集群分布式集群
基于Redis生成全局ID策略
單機(jī)版
集群分布式
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
雪花算法
是什么
twitter的SnowFlake生成ID能夠按照時(shí)間有序生成 SnowFlake算法生成ID的結(jié)果是一個(gè)64Bit大小的整數(shù)，為一個(gè)Long型（轉(zhuǎn)換成字符串后長度最多19） 分布式系統(tǒng)內(nèi)不會(huì)產(chǎn)生ID碰撞（由datacenter 和 workerID做區(qū)分）并且效率較高
在分布式環(huán)境下，必須全局唯一性 一般都需要單調(diào)遞增，因?yàn)橐话阄ㄒ籌D都會(huì)存在數(shù)據(jù)庫，而InnoDB的特性就是將內(nèi)容存儲在主鍵索引上的葉子節(jié)點(diǎn)，而且是從左往右遞增的，所有考慮到數(shù)據(jù)庫性能，一般生成ID也最好是單調(diào)遞增的。為了防止ID沖突可以使用36位UUID，但是UUID有一些缺點(diǎn)，首先是它相對比較長，并且另外UUID一般是無序的 可能還會(huì)需要無規(guī)則，因?yàn)槿绻褂梦ㄒ籌D作為訂單號這種，為了不讓別人知道一天的訂單量多少，就需要這種規(guī)則
結(jié)構(gòu)
第一部分
第二部分
第三部分
第四部分
SnowFlake可以保證
實(shí)現(xiàn)
https://github.com/beyondfengyu/SnowFlake/blob/master/SnowFlake.java
/**
?*?twitter的snowflake算法?--?java實(shí)現(xiàn)
?*?
?*?@author?beyond
?*/
public?class?SnowFlake?{
????/**
?????*?起始的時(shí)間戳
?????*/
????private?final?static?long?START_STMP?=?1480166465631L;
????/**
?????*?每一部分占用的位數(shù)
?????*/
????private?final?static?long?SEQUENCE_BIT?=?12;?//序列號占用的位數(shù)
????private?final?static?long?MACHINE_BIT?=?5;???//機(jī)器標(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;?????//機(jī)器標(biāo)識
????private?long?sequence?=?0L;?//序列號
????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)，序列號自增
????????????sequence?=?(sequence?+?1)?&?MAX_SEQUENCE;
????????????//同一毫秒的序列數(shù)已經(jīng)達(dá)到最大
????????????if?(sequence?==?0L)?{
????????????????currStmp?=?getNextMill();
????????????}
????????}?else?{
????????????//不同毫秒內(nèi)，序列號置為0
????????????sequence?=?0L;
????????}
????????lastStmp?=?currStmp;
????????return?(currStmp?-?START_STMP)?<//時(shí)間戳部分
????????????????|?datacenterId?<//數(shù)據(jù)中心部分
????????????????|?machineId?<//機(jī)器標(biāo)識部分
????????????????|?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?1?<12);?i++)?{
????????????System.out.println(snowFlake.nextId());
????????}
????}
}
工程落地經(jīng)驗(yàn)
地址：https://github.com/looly/hutool
SpringBoot整合雪花算法
<dependency>
????<groupId>cn.hutoolgroupId>
????<artifactId>hutool-allartifactId>
????<version>5.3.1version>
dependency>
/**
?*?雪花算法
?*
?*?@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?20;?i++)?{
????????????new?Thread(()?->?{
????????????????System.out.println(snowFlakeDemo.snowflakeId());
????????????},?String.valueOf(i)).start();
????????}
????}
}
1251350711346790400
1251350711346790402
1251350711346790401
1251350711346790403
1251350711346790405
1251350711346790404
1251350711346790406
1251350711346790407
1251350711350984704
1251350711350984706
1251350711350984705
1251350711350984707
1251350711350984708
1251350711350984709
1251350711350984710
1251350711350984711
1251350711350984712
1251350711355179008
1251350711355179009
1251350711355179010
優(yōu)缺點(diǎn)
優(yōu)點(diǎn)
毫秒數(shù)在高維，自增序列在低位，整個(gè)ID都是趨勢遞增的 不依賴數(shù)據(jù)庫等第三方系統(tǒng)，以服務(wù)的方式部署，穩(wěn)定性更高，生成ID的性能也是非常高的 可以根據(jù)自身業(yè)務(wù)特性分配bit位，非常靈活
缺點(diǎn)
依賴機(jī)器時(shí)鐘，如果機(jī)器時(shí)鐘回?fù)埽瑫?huì)導(dǎo)致重復(fù)ID生成 在單機(jī)上是遞增的，但由于涉及到分布式環(huán)境，每臺機(jī)器上的時(shí)鐘不可能完全同步，有時(shí)候會(huì)出現(xiàn)不是全局遞增的情況，此缺點(diǎn)可以認(rèn)為無所謂，一般分布式ID只要求趨勢遞增，并不會(huì)嚴(yán)格要求遞增，90%的需求只要求趨勢遞增。
其它補(bǔ)充
為了解決時(shí)鐘回?fù)軉栴}，導(dǎo)致ID重復(fù)，后面有人專門提出了解決的方案 百度開源的分布式唯一ID生成器 UidGenerator Leaf - 美團(tuán)點(diǎn)評分布式ID生成系統(tǒng)
推薦閱讀：
內(nèi)容包含Java基礎(chǔ)、JavaWeb、MySQL性能優(yōu)化、JVM、鎖、百萬并發(fā)、消息隊(duì)列、高性能緩存、反射、Spring全家桶原理、微服務(wù)、Zookeeper、數(shù)據(jù)結(jié)構(gòu)、限流熔斷降級......等技術(shù)棧！
?戳閱讀原文領(lǐng)取！? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??朕已閱?
評論
圖片
表情