目錄

前言

回顧二進(jìn)制

二進(jìn)制概念

運(yùn)算法則

位（Bit）

字節(jié)（Byte）

字符

字符集

二進(jìn)制原碼、反碼、補(bǔ)碼

有符號(hào)數(shù)和無符號(hào)數(shù)

疑問：為什么不是-127 ～ 127 ？

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

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

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

通用解決方案

1. UUID

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

缺點(diǎn)

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

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

缺點(diǎn)

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

單機(jī)版

集群分布式

缺點(diǎn)

SnowFlake雪花算法

雪花算法結(jié)構(gòu)

雪花算法的優(yōu)缺點(diǎn)

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

缺點(diǎn)

雪花算法的具體實(shí)現(xiàn)

SpringtBoot整合雪花算法 (基于hutool工具類)

第三方基于SnowFlake算法生成的唯一ID

雪花算法相關(guān)問題以及解決方案

1. 時(shí)間回?fù)軉栴}

2.工作機(jī)器ID可能會(huì)重復(fù)的問題

3.?-1L ^ (-1L << x) 表示什么？

4.前端直接使用發(fā)生精度丟失

前言

? ? ? ? 本文章首先回顧一下二進(jìn)制相關(guān)知識(shí)點(diǎn)，方便猿友們閱讀的更清晰，不至于讀完還是一臉懵的狀態(tài)；其次，現(xiàn)階段為什么需要分布式全局唯一ID以及分布式ID的業(yè)務(wù)需求，進(jìn)行詳細(xì)描述一下；以及此問題提出后一般通用的解決方案和優(yōu)缺點(diǎn)；最后詳細(xì)描述一下本文章的核心功能點(diǎn)——雪花算法（SnowFlake）。

????????吾在寫本文章時(shí)也是處于不是太懂具體實(shí)現(xiàn)以及優(yōu)劣勢(shì)，才下決定好好研究一波，希望能夠幫助到還不明白的猿友們，若本文有不足之處，歡迎大佬點(diǎn)評(píng)?。?！

回顧二進(jìn)制

二進(jìn)制概念

二進(jìn)制是計(jì)算技術(shù)中廣泛采用的一種數(shù)制。二進(jìn)制數(shù)據(jù)是用0和1兩個(gè)數(shù)碼來表示的數(shù)。

它的基數(shù)位2，進(jìn)位規(guī)則是“逢二進(jìn)一”，借位規(guī)則是“借一當(dāng)二”，由18世紀(jì)德國(guó)數(shù)理哲學(xué)大師萊布尼茲發(fā)現(xiàn)。

當(dāng)前的計(jì)算機(jī)系統(tǒng)使用的基本上是二進(jìn)制系統(tǒng)，數(shù)據(jù)在計(jì)算機(jī)中主要是以補(bǔ)碼的形式存儲(chǔ)的。

計(jì)算機(jī)中的二進(jìn)制則是一個(gè)非常微小的開關(guān)，用“開”來表示1，“關(guān)”來表示0。

運(yùn)算法則

二進(jìn)制的運(yùn)算算術(shù)運(yùn)算

二進(jìn)制的加法(+)：0+0=0，0+1=1，1+0=1，1+1=10（向高位進(jìn)位）；例：7=111；10=1010；3=11

二進(jìn)制的減法(-)：0-0=0，0-1=1（先高位錯(cuò)位）1-0=1，1-1=0（模二加運(yùn)算或異或運(yùn)算）；

二進(jìn)制的乘法(*)：0*0=0；0*1=0；1*0=0；1*1=1；

二進(jìn)制的除法(/)：0/0=0，0/1=0，1/0=0（無意義），1/1=1；

邏輯運(yùn)算二進(jìn)制的或(|)運(yùn)算：遇1得1

邏輯運(yùn)算二進(jìn)制的與(&)運(yùn)算：遇0得0

邏輯運(yùn)算二進(jìn)制得非(!)運(yùn)算：各位取反。

位（Bit）

數(shù)據(jù)存儲(chǔ)得最小單位。每個(gè)二進(jìn)制數(shù)字0或者1就是1個(gè)位。

字節(jié)（Byte）

8個(gè)位構(gòu)成一個(gè)字節(jié)；即1byte（字節(jié)）= 8bit（位）

• 1KB = 1024B（字節(jié)）；
• 1MB = 1024KB；（2^10 B）
• 1GB = 1024MB；（2^20 B）
• 1TB? = 1024GB； （2^30 B）

字符

a、A、中、+、*、@……均表示一個(gè)字符；

? ? ? ? 一般utf-8編碼下，一個(gè)漢字 字符 占用3個(gè)字節(jié)；

? ? ? ? 一般gbk編碼下，一個(gè)漢字 字符 占用2個(gè)字節(jié)。

字符集

即各種各個(gè)字符的集合，也就是說哪些漢字，字母（A、b、c）和符號(hào)（空格、引號(hào)..）會(huì)被收入標(biāo)準(zhǔn)中

二進(jìn)制原碼、反碼、補(bǔ)碼

有符號(hào)數(shù)和無符號(hào)數(shù)

無符號(hào)數(shù)中，所有的位都用于直接表示該值的大小。

有符號(hào)數(shù)中，最高位用于表示正負(fù)。

例：

???????? 8位2進(jìn)制表示的:

????????????????無符號(hào)數(shù)的范圍為0(00000000B) ～ 255 (11111111B);

????????????????有符號(hào)數(shù)的范圍為-128(10000000B) ～ 127 (01111111B);

????????????????255 = 1*2^7 + 1*2^6 + 1*2^5 +1*2^4 +1*2^3 +1*2^2 +1*2^1 +1*2^0;

????????????????127 = 1*2^6 + 1*2^5 +1*2^4 +1*2^3 +1*2^2 +1*2^1 +1*2^0;

疑問：為什么不是-127 ～ 127 ？

補(bǔ)碼比其它碼多一位，這是為什么呢？問題出在0上。

[+0]原碼=0000 0000， [-0]原碼=1000 0000

[+0]反碼=0000 0000， [-0]反碼=1111 1111

[+0]補(bǔ)碼=0000 0000， [-0]補(bǔ)碼=0000 0000

反碼表示法規(guī)定：正數(shù)的反碼與其原碼相同。負(fù)數(shù)的反碼是對(duì)其原碼逐位取反，但符號(hào)位除外。

在規(guī)定中，8位二進(jìn)制碼能表示的反碼范圍是-127~127。

-128沒有反碼。

為什么規(guī)定-128沒有反碼呢?

首先看-0，[-0]原碼=1000 000，其中1是符號(hào)位，根據(jù)反碼規(guī)定，算出[-0]反碼=1111 1111， 再看-128，[-128]原碼=1000 000，假如讓-128也有反碼，根據(jù)反碼規(guī)定，則[-128]反碼=1111 1111，

-128的反碼和-0的反碼相同，所以為了避免面混淆，有了-0，便不能有-128，這是反碼規(guī)則決定的

因此八位二進(jìn)制表示的范圍為：-128～0～127。此處的0為正0，負(fù)0表示了-128。

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

在復(fù)雜分布式系統(tǒng)中，往往需要對(duì)大量得數(shù)據(jù)和消息進(jìn)行唯一標(biāo)識(shí)，如美團(tuán)點(diǎn)評(píng)得金融、支付、餐飲、酒店、訂單、優(yōu)惠券都需要由唯一ID做標(biāo)識(shí)

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

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

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

• 高可用
  • 發(fā)布一個(gè)獲取分布式ID請(qǐng)求，服務(wù)器就要保證99.999%的情況下給我創(chuàng)建一個(gè)唯一分布式ID
• 低延遲
  • 發(fā)一個(gè)獲取分布式ID的請(qǐng)求，服務(wù)器就要快，極速
• 高QPS
  • (每秒查詢率（QPS，Queries-per-second）是對(duì)一個(gè)特定的查詢服務(wù)器在規(guī)定時(shí)間內(nèi)所處理流量多少的衡量標(biāo)準(zhǔn))。
    • 例如并發(fā)一口氣10萬個(gè)創(chuàng)建分布式ID請(qǐng)求同時(shí)殺過來，服務(wù)器要頂?shù)米∏乙幌伦映晒?chuàng)建10萬個(gè)分布式ID

通用解決方案

1. UUID

UUID.randomUUID()，UUID的標(biāo)準(zhǔn)型包含32個(gè)16進(jìn)制數(shù)字，以連字號(hào)分為五段，形式位 8-4-4-4-12的36個(gè)字符，性能非常高，本地生成，沒有網(wǎng)絡(luò)消耗。

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

• 能夠保證獨(dú)立性，程序可以在不同的數(shù)據(jù)庫(kù)間遷移，效果不受影響。
• 保證生成的ID不僅是表獨(dú)立的，而且是庫(kù)獨(dú)立的，這點(diǎn)在你想切分?jǐn)?shù)據(jù)庫(kù)的時(shí)候尤為重要。

缺點(diǎn)

• 入數(shù)據(jù)庫(kù)性能差，因?yàn)閁UID是無序的

? ? ? ? 無序，無法預(yù)測(cè)他的生成順序，不能生成遞增有序的數(shù)字

? ? ? ? 首先分布式id一般都會(huì)作為主鍵，但是按照mysql官方推薦主鍵盡量越短越好，UUID每一個(gè)都很長(zhǎng)，所以不是很推薦。

• 主鍵，ID最為主鍵時(shí)，在特定的環(huán)境下會(huì)存在一些問題

? ? ? ? 比如做DB主鍵的場(chǎng)景下，UUID就非常不適用MySQL官方明確的說明

• 索引，B+樹索引的分裂

? ? ? ? 既然分布式ID是主鍵，然后主鍵是包含索引的，而mysql的索引是通過B+樹來實(shí)現(xiàn)的，每一次新的UUID數(shù)據(jù)的插入，為了查詢的優(yōu)化，都會(huì)對(duì)索引底層的B+樹進(jìn)行修改，因?yàn)閁UID數(shù)據(jù)是無序的，所以每一次UUID數(shù)據(jù)的插入都會(huì)對(duì)主鍵的B+樹進(jìn)行很大的修改，這一點(diǎn)很不好，插入完全無序，不但會(huì)導(dǎo)致一些中間節(jié)點(diǎn)產(chǎn)生分裂，也會(huì)白白創(chuàng)造出很多不飽和的節(jié)點(diǎn)，這樣大大降低了數(shù)據(jù)庫(kù)插入的性能。

UUID只能保證全局唯一性，不滿足后買你的趨勢(shì)遞增，單調(diào)遞增

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

在分布式里面，數(shù)據(jù)庫(kù)的自增ID機(jī)制的主要原理是：數(shù)據(jù)庫(kù)自增ID和mysql數(shù)據(jù)庫(kù)的replace into實(shí)現(xiàn)的，這里的replace into跟insert功能類似，不同點(diǎn)在于：replace into首先嘗試插入數(shù)據(jù)列表中，如果發(fā)現(xiàn)表中已經(jīng)有此行數(shù)據(jù)（根據(jù)主機(jī)那或者唯一索引判斷）則先刪除，在插入，否則直接插入新數(shù)據(jù)。

REPLCAE INTO的含義是插入一條記錄，如果表中唯一索引的值遇到?jīng)_突，則替換老數(shù)據(jù)

create table t_test(
    id bigint(20) unsigned not null auto_increment primary key,
    stub char(1) not null default '',
    unique key stub (stub)
)

REPLACE into t_test(stub) values('b');
select LAST_INSERT_ID();

每次插入的時(shí)候，發(fā)現(xiàn)都會(huì)把原來的數(shù)據(jù)給替換，并且ID也會(huì)增加。

滿足了：遞增性、單調(diào)性、唯一性

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

• 非常簡(jiǎn)單，利用現(xiàn)有數(shù)據(jù)庫(kù)系統(tǒng)的功能實(shí)現(xiàn)，成本小，有DBA專業(yè)維護(hù)。
• ID號(hào)單調(diào)自增，可以實(shí)現(xiàn)一些對(duì)ID有特殊要求的業(yè)務(wù)。

缺點(diǎn)

• 不適合做分布式ID，系統(tǒng)水平擴(kuò)展比較困難

? ? ? ? 比如定義好步長(zhǎng)和機(jī)器臺(tái)數(shù)之后，如果要添加機(jī)器該怎么辦，假設(shè)現(xiàn)在有一臺(tái)機(jī)器發(fā)號(hào)是：1，2，3，4（步長(zhǎng)是1），這個(gè)時(shí)候需要擴(kuò)容機(jī)器一臺(tái)，可以這樣做：把第二臺(tái)機(jī)器的初始值設(shè)置得比第一臺(tái)超過很多，貌似還好，但是假設(shè)線上如果有100臺(tái)機(jī)器，這個(gè)時(shí)候擴(kuò)容要怎么做，簡(jiǎn)直是噩夢(mèng)，所以系統(tǒng)水平擴(kuò)展方案復(fù)雜難以實(shí)現(xiàn)。

• 數(shù)據(jù)庫(kù)壓力大

? ? ? ? 每次獲取ID都得讀寫一次數(shù)據(jù)庫(kù)，非常影響性能，不符合分布式ID里面得延遲低和高QPS得規(guī)則（在高并發(fā)下，如果都去數(shù)據(jù)庫(kù)里面獲取ID，那是非常影響性能的）

• 數(shù)據(jù)庫(kù)遷移以及分表分庫(kù)困難
  • 不同數(shù)據(jù)庫(kù)語法和實(shí)現(xiàn)不同，數(shù)據(jù)庫(kù)遷移的時(shí)候或多數(shù)據(jù)庫(kù)版本支持的時(shí)候需要處理。
  • 在單個(gè)數(shù)據(jù)庫(kù)或讀寫分離或一主多從的情況下，只有一個(gè)主庫(kù)可以生成。
  • 如果涉及多個(gè)系統(tǒng)需要合并或者數(shù)據(jù)遷移比較麻煩。
  • 分表分庫(kù)的時(shí)候麻煩。

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

單機(jī)版

因?yàn)镽edis是單線程，天生保證原子性，可以使用原子操作INCR和INCEBY來實(shí)現(xiàn)、

• INCRBY：設(shè)置增長(zhǎng)步長(zhǎng)。key是redis中的鍵，將key所存儲(chǔ)的值加上增量integer。如果key不存在，那么key的值就會(huì)被初始化為0，然后在執(zhí)行incrby命令。
• INCR：key是redis中的鍵，只是每次都是默認(rèn)自增1。

集群分布式

? ? ? ? 注意：在Redis集群情況下，同樣和MySQL一樣需要設(shè)置不同的增長(zhǎng)步長(zhǎng)，同時(shí)key一定要設(shè)置有效期，可以使用Redis集群來獲取更高的吞吐量。

假設(shè)一個(gè)集群中有5臺(tái)Redis，可以初始化每臺(tái)Redis的值分別是1，2，3，4，5，然后設(shè)置步長(zhǎng)都是5

各個(gè)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

缺點(diǎn)

• Redis集群的維護(hù)和保養(yǎng)比較麻煩，配置麻煩。
• 要設(shè)置單點(diǎn)故障，哨兵值守。

SnowFlake雪花算法

SnowFlake是Twitter開源的分布式ID生成算法，結(jié)果是一個(gè)long型的ID。

核心組成：使用41bit作為毫秒數(shù)，10bit作為機(jī)器的ID（5個(gè)bit是數(shù)據(jù)中心，5個(gè)bit是機(jī)器ID），12bit作為毫秒內(nèi)的流水號(hào)（意味著每個(gè)節(jié)點(diǎn)在每毫秒可以產(chǎn)生4096個(gè)ID），最后還有一個(gè)符號(hào)位，永遠(yuǎn)是0.?

核心思想：分布式、唯一。

雪花算法結(jié)構(gòu)

?結(jié)構(gòu)格式（64bit）：1bit保留 + 41bit時(shí)間戳 + 10bit機(jī)器 + 12bit序列號(hào)

<1> 1bit-保留不用

????????因?yàn)槎M(jìn)制中最高位是符號(hào)位，1標(biāo)識(shí)負(fù)數(shù)，0標(biāo)識(shí)正數(shù)，生成的id一般都是用整數(shù)，所以最高位固定為0.

<2> ?41bit-用來記錄時(shí)間戳（毫秒）

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

?(2^41?1)/(1000?60?60?24?365)=69年 ，也就是說這個(gè)時(shí)間戳可以使用69年不重復(fù)

注意：其時(shí)間戳的算法是1970年1月1日到指點(diǎn)時(shí)間所經(jīng)過的毫秒或秒數(shù)，那咱們把開始時(shí)間從2021年開始，就可以延長(zhǎng)41位時(shí)間戳能表達(dá)的最大時(shí)間，所以這里實(shí)際指的是相對(duì)自定義開始時(shí)間的時(shí)間戳。

<3>?10bit-用來記錄工作機(jī)器id

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

<4>?12bit-序列號(hào)，用來記錄同毫秒內(nèi)產(chǎn)生的不同id

• 12位（bit）可以表示的最大正整數(shù)是2^12-1=4095，即可以用0、1、2、3、……4095這4096個(gè)數(shù)字，來表示同一機(jī)器同一時(shí)間戳（毫秒）內(nèi)產(chǎn)生的4096個(gè)ID序號(hào)
• SnowFlake算法在同一毫秒內(nèi)最多可以生成多少個(gè)全局唯一ID？

? ? ? ? 同一毫秒的ID數(shù)量 = 1024 * 4096 = 4194304，所以最大可以支持單應(yīng)用差不多四百萬的并發(fā)量。

注意：上面總體是64位，具體位數(shù)可自行配置，

????????若想運(yùn)行更久，需要增加時(shí)間戳位數(shù)；

? ? ? ? 若想支持更多節(jié)點(diǎn)，可增加工作機(jī)器Id位數(shù)；

? ? ? ? 若想支持更高并發(fā)，增加序列號(hào)位數(shù)。

雪花算法的優(yōu)缺點(diǎn)

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

• 系統(tǒng)環(huán)境ID不重復(fù)

? ? ? ? 能滿足高并發(fā)分布式系統(tǒng)環(huán)境ID不重復(fù)，比如大家熟知的分布式場(chǎng)景下的數(shù)據(jù)庫(kù)表的ID生成。

• 生成效率極高

? ? ? ? 在高并發(fā)，以及分布式環(huán)境下，除了生成不重復(fù)id，每秒可生成百萬個(gè)不重復(fù)id，生成效率極高。

• 保證基本有序遞增

? ? ? ? 基于時(shí)間戳，可以保證基本有序遞增，很多業(yè)務(wù)場(chǎng)景都有這個(gè)需求。

• 不依賴第三方庫(kù)

? ? ? ? 不依賴第三方的庫(kù)，或者中間件，算法簡(jiǎn)單，在內(nèi)存中進(jìn)行。

缺點(diǎn)

• 強(qiáng)依賴系統(tǒng)時(shí)鐘，如果主機(jī)時(shí)間回?fù)?，則會(huì)造成重復(fù)ID
• 在單機(jī)上是遞增的，但由于涉及到分布式環(huán)境，每臺(tái)機(jī)器上的時(shí)鐘不可能完全同步，有時(shí)候會(huì)出現(xiàn)不是全局遞增的情況，此缺點(diǎn)可以認(rèn)為無所謂，一般分布式ID只要求趨勢(shì)遞增，并不會(huì)嚴(yán)格要求遞增，90%的需求只要求趨勢(shì)遞增。

雪花算法的具體實(shí)現(xiàn)

注意！注意！注意！以下代碼親測(cè)過，并有詳細(xì)的注釋解說，直接拿走，不謝?。?！

public class SnowFlakeUtil {

    /**
     * 初始時(shí)間戳，可以根據(jù)業(yè)務(wù)需求更改時(shí)間戳
     */
    private final long twepoch = 11681452025134L;

    /**
     * 機(jī)器ID所占位數(shù)，長(zhǎng)度為5位
     */
    private final long workerIdBits = 5L;

    /**
     * 數(shù)據(jù)標(biāo)識(shí)ID所占位數(shù)，長(zhǎng)度位5位
     */
    private final long datacenterIdBits = 5L;

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

    /**
     * 支持的最大數(shù)據(jù)標(biāo)識(shí)id，結(jié)果是31
     */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    /**
     * 序列在id中占的位數(shù)
     */
    private final long sequenceBits = 12L;

    /**
     * 工作機(jī)器ID向左移12位
     */
    private final long workerIdShift = sequenceBits;

    /**
     * 數(shù)據(jù)標(biāo)識(shí)id向左移17位(12+5)
     */
    private final long dataCenterIdShift = sequenceBits + workerIdBits;

    /**
     * 時(shí)間截向左移22位(5+5+12)
     */
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    /**
     * 序列號(hào)最大值; 生成序列的掩碼，這里為4095 (0b111111111111=0xfff=4095)
     */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /**
     * 工作機(jī)器ID(0~31)，2進(jìn)制5位  32位減掉1位 31個(gè)
     */
    private volatile long workerId;

    /**
     * 數(shù)據(jù)中心ID(0~31)，2進(jìn)制5位  32位減掉1位 31個(gè)
     */
    private volatile long datacenterId;

    /**
     * 毫秒內(nèi)序列(0~4095)，2進(jìn)制12位 4096 - 1 = 4095個(gè)
     */
    private volatile long sequence = 0L;

    /**
     * 上次時(shí)間戳，初始值為負(fù)數(shù)
     */
    private volatile long lastTimestamp = -1L;


    // ==============================Constructors=====================================

    /**
     * 有參構(gòu)造
     * @param workerId 工作機(jī)器ID(0~31)
     * @param datacenterId 數(shù)據(jù)中心ID(0~31)
     * @param sequence 毫秒內(nèi)序列(0~4095)
     */
    public SnowFlakeUtil(long workerId, long datacenterId, long sequence){
        // sanity check for workerId
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0",maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0",maxDatacenterId));
        }
        System.out.printf("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
                timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);

        this.workerId = workerId;
        this.datacenterId = datacenterId;
        this.sequence = sequence;
    }

    // ==============================Methods==========================================

    /**
     * 獲得下一個(gè)ID (該方法是線程安全的)
     *  如果一個(gè)線程反復(fù)獲取Synchronized鎖，那么synchronized鎖將變成偏向鎖。
     * @return 生成的ID
     */
    public synchronized long nextId() {
        // 獲取當(dāng)前時(shí)間的時(shí)間戳，單位（毫秒）
        long timestamp = timeGen();

        // 獲取當(dāng)前時(shí)間戳如果小于上次時(shí)間戳，則表示時(shí)間戳獲取出現(xiàn)異常
        if (timestamp < lastTimestamp) {
            System.err.printf("當(dāng)前時(shí)間戳不能小于上次時(shí)間戳，上次時(shí)間戳為： %d.", lastTimestamp);
            throw new RuntimeException(String.format("當(dāng)前時(shí)間戳不能小于上次時(shí)間戳，生成ID失敗. 時(shí)間戳差值： %d milliseconds",
                    lastTimestamp - timestamp));
        }

        // 獲取當(dāng)前時(shí)間戳如果等于上次時(shí)間戳（同一毫秒內(nèi)），則在序列號(hào)加一；否則序列號(hào)賦值為0，從0開始。
        if (lastTimestamp == timestamp) {
            /* 邏輯：意思是說一個(gè)毫秒內(nèi)最多只能有4096個(gè)數(shù)字，無論你傳遞多少進(jìn)來，
                    這個(gè)位運(yùn)算保證始終就是在4096這個(gè)范圍內(nèi)，避免你自己傳遞個(gè)sequence超過了4096這個(gè)范圍 */
            // sequence：毫秒內(nèi)序列(0~4095);  sequenceMask: 序列號(hào)最大值;
            sequence = (sequence + 1) & sequenceMask;
            /* 邏輯：當(dāng)某一毫秒的時(shí)間，產(chǎn)生的id數(shù) 超過4095，系統(tǒng)會(huì)進(jìn)入等待，直到下一毫秒，系統(tǒng)繼續(xù)產(chǎn)生ID */
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0;
        }

        // 將上次時(shí)間戳值刷新（邏輯：記錄一下最近一次生成id的時(shí)間戳，單位是毫秒）
        lastTimestamp = timestamp;

        /* 核心邏輯：生成一個(gè)64bit的id；
                  先將當(dāng)前時(shí)間戳左移，放到41 bit那兒；
                  將機(jī)房id左移放到5 bit那兒；
                  將機(jī)器id左移放到5 bit那兒；
                  將序號(hào)放最后12 bit
                  最后拼接起來成一個(gè)64 bit的二進(jìn)制數(shù)字，轉(zhuǎn)換成10進(jìn)制就是個(gè)long型 */
        /*
         * 返回結(jié)果：
         * (timestamp - twepoch) << timestampLeftShift) 表示將時(shí)間戳減去初始時(shí)間戳，再左移相應(yīng)位數(shù)
         * (datacenterId << datacenterIdShift) 表示將數(shù)據(jù)id左移相應(yīng)位數(shù)
         * (workerId << workerIdShift) 表示將工作id左移相應(yīng)位數(shù)
         * | 是按位或運(yùn)算符，例如：x | y，只有當(dāng)x，y不為0的時(shí)候結(jié)果才為0，其它情況結(jié)果都為1。
         * 因?yàn)閭€(gè)部分只有相應(yīng)位上的值有意義，其它位上都是0，所以將各部分的值進(jìn)行 | 運(yùn)算就能得到最終拼接好的id
         */
        return ((timestamp - twepoch) << timestampLeftShift) |
                (datacenterId << dataCenterIdShift) |
                (workerId << workerIdShift) |
                sequence;
    }

    /**
     * 上次時(shí)間戳與當(dāng)前時(shí)間戳進(jìn)行比較
     * 邏輯：當(dāng)某一毫秒的時(shí)間，產(chǎn)生的id數(shù) 超過4095，系統(tǒng)會(huì)進(jìn)入等待，直到下一毫秒，系統(tǒng)繼續(xù)產(chǎn)生ID
     * @param lastTimestamp 上次時(shí)間戳
     * @return 若當(dāng)前時(shí)間戳小于等于上次時(shí)間戳（時(shí)間回?fù)芰耍瑒t返回最新當(dāng)前時(shí)間戳； 否則，返回當(dāng)前時(shí)間戳
     */
    private long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 獲取系統(tǒng)時(shí)間戳
     * @return 當(dāng)前時(shí)間的時(shí)間戳 14位
     */
    private long timeGen(){
        return System.currentTimeMillis();
    }

    public static void main(String[] args) {
        SnowFlakeUtil snowFlakeUtil = new SnowFlakeUtil(1,1,0);
        System.out.println(snowFlakeUtil.timeGen());
        for (int i = 0; i < 100; i++) {
            System.out.println("雪花算法生成第【"+(i+1)+"】個(gè)ID:"+ snowFlakeUtil.nextId());
        }

    }

}

以上代碼執(zhí)行結(jié)果：

雪花算法生成第【1】個(gè)ID:-5049534853385416704
雪花算法生成第【2】個(gè)ID:-5049534853385416703
雪花算法生成第【3】個(gè)ID:-5049534853385416702
雪花算法生成第【4】個(gè)ID:-5049534853385416701
雪花算法生成第【5】個(gè)ID:-5049534853385416700
雪花算法生成第【6】個(gè)ID:-5049534853385416699
雪花算法生成第【7】個(gè)ID:-5049534853385416698
雪花算法生成第【8】個(gè)ID:-5049534853385416697
雪花算法生成第【9】個(gè)ID:-5049534853385416696
雪花算法生成第【10】個(gè)ID:-5049534853385416695
……
……
…… （之后的結(jié)果就不一一展示了）

SpringtBoot整合雪花算法 (基于hutool工具類)

第一步：引入hutool工具依賴包

<!-- hutool工具類 -->
<dependency>
    <groupId>cn.hutool</groupId>
    <artifactId>hutool-all</artifactId>
    <version>5.3.1</version>
</dependency>

第二步：Springboot整合具體代碼實(shí)現(xiàn)

import cn.hutool.core.lang.Snowflake;
import cn.hutool.core.net.NetUtil;
import cn.hutool.core.util.IdUtil;

import javax.annotation.PostConstruct;

/**
 * SpringtBoot整合雪花算法 (基于hutool工具類)
 */
public class SnowFlakeHutoolTestController {
    /**
     * 工作機(jī)器ID(0~31)，2進(jìn)制5位  32位減掉1位 31個(gè)
     */
    private long workerId = 0;
    /**
     * 數(shù)據(jù)中心ID(0~31)，2進(jìn)制5位  32位減掉1位 31個(gè)
     */
    private long datacenterId = 1;

    /**
     * 雪花算法對(duì)象
     */
    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，默認(rèn)使用網(wǎng)絡(luò)IP作為工作機(jī)器ID
     * @return ID
     */
    public synchronized long snowflakeId() {
        return this.snowFlake.nextId();
    }

    /**
     * 獲取雪花ID
     * @param workerId 工作機(jī)器ID
     * @param datacenterId 數(shù)據(jù)中心ID
     * @return ID
     */
    public synchronized long snowflakeId(long workerId, long datacenterId) {
        Snowflake snowflake = IdUtil.createSnowflake(workerId, datacenterId);
        return snowflake.nextId();
    }

    public static void main(String[] args) {
        SnowFlakeHutoolTestController snowFlakeDemo = new SnowFlakeHutoolTestController();
        for (int i = 0; i < 20; i++) {
            int finalI = i;
            new Thread(() -> {
                System.out.println("雪花算法生成第【"+(finalI +1)+"】個(gè)ID:"+ snowFlakeDemo.snowflakeId());
            }, String.valueOf(i)).start();
        }
    }

}

以上代碼執(zhí)行結(jié)果：

雪花算法生成第【2】個(gè)ID:1646777064113700865
雪花算法生成第【5】個(gè)ID:1646777064113700868
雪花算法生成第【3】個(gè)ID:1646777064113700866
雪花算法生成第【4】個(gè)ID:1646777064113700867
雪花算法生成第【1】個(gè)ID:1646777064113700864
雪花算法生成第【11】個(gè)ID:1646777064113700873
雪花算法生成第【10】個(gè)ID:1646777064113700872
雪花算法生成第【8】個(gè)ID:1646777064113700871
雪花算法生成第【7】個(gè)ID:1646777064113700870
雪花算法生成第【6】個(gè)ID:1646777064113700869
雪花算法生成第【16】個(gè)ID:1646777064113700877
雪花算法生成第【13】個(gè)ID:1646777064113700876
雪花算法生成第【12】個(gè)ID:1646777064113700875
雪花算法生成第【9】個(gè)ID:1646777064113700874
雪花算法生成第【17】個(gè)ID:1646777064113700881
雪花算法生成第【19】個(gè)ID:1646777064113700880
雪花算法生成第【15】個(gè)ID:1646777064113700879
雪花算法生成第【14】個(gè)ID:1646777064113700878
雪花算法生成第【20】個(gè)ID:1646777064113700883
雪花算法生成第【18】個(gè)ID:1646777064113700882

第三方基于SnowFlake算法生成的唯一ID

• 百度UIDGenerator：https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md
  • UidGenerator是Java實(shí)現(xiàn)的，基于SnowFlake算法的唯一ID生成器。UidGenerator以組件形式工作在應(yīng)用項(xiàng)目中，支持自定義workerId位數(shù)和初始化策略，從而適用于docker等虛擬化環(huán)境下實(shí)例自動(dòng)重啟、漂移等場(chǎng)景。在實(shí)現(xiàn)上, UidGenerator通過借用未來時(shí)間來解決sequence天然存在的并發(fā)限制; 采用RingBuffer來緩存已生成的UID, 并行化UID的生產(chǎn)和消費(fèi), 同時(shí)對(duì)CacheLine補(bǔ)齊，避免了由RingBuffer帶來的硬件級(jí)「?jìng)喂蚕怼箚栴}. 最終單機(jī)QPS可達(dá)600萬。
• 美團(tuán)Leaf：https://tech.meituan.com/2019/03/07/open-source-project-leaf.html
  • leaf-segment 方案
    • 優(yōu)化：雙buffer + 預(yù)分配
    • 容災(zāi)：Mysql DB 一主兩從，異地機(jī)房，半同步方式
    • 缺點(diǎn)：如果用segment號(hào)段式方案：id是遞增，可計(jì)算的，不適用于訂單ID生成場(chǎng)景，比如競(jìng)對(duì)在兩天中午12點(diǎn)分別下單，通過訂單id號(hào)相減就能大致計(jì)算出公司一天的訂單量，這個(gè)是不能忍受的。
• leaf-snowflake方案
  • 使用Zookeeper持久順序節(jié)點(diǎn)的特性自動(dòng)對(duì)snowflake節(jié)點(diǎn)配置workerID
    • 1.啟動(dòng)Leaf-snowflake服務(wù)，連接Zookeeper，在leaf_forever父節(jié)點(diǎn)下檢查自己是否已經(jīng)注冊(cè)過（是否有該順序子節(jié)點(diǎn)）。
    • 2.如果有注冊(cè)過直接取回自己的workerID（zk順序節(jié)點(diǎn)生成的int類型ID號(hào)），啟動(dòng)服務(wù)。
    • 3.如果沒有注冊(cè)過，就在該父節(jié)點(diǎn)下面創(chuàng)建一個(gè)持久順序節(jié)點(diǎn)，創(chuàng)建成功后取回順序號(hào)當(dāng)做自己的workerID號(hào)，啟動(dòng)服務(wù)。

雪花算法相關(guān)問題以及解決方案

1. 時(shí)間回?fù)軉栴}

問題

????????在獲取時(shí)間的時(shí)候，可能會(huì)出現(xiàn)時(shí)間回?fù)艿膯栴}，什么是時(shí)間回?fù)苣兀?/p>

原因

????????時(shí)間回?fù)芫褪欠?wù)器上的時(shí)間突然倒退到之前的時(shí)間。

• 認(rèn)為原因，把系統(tǒng)環(huán)境的時(shí)間改了
• 有時(shí)候不同的機(jī)器上需要同步時(shí)間，可能不同機(jī)器之間存在誤差，那么可能會(huì)出現(xiàn)時(shí)間回?fù)軉栴}

解決方案

• 回?fù)軙r(shí)間小的時(shí)候，不生成ID，循環(huán)等待到時(shí)間點(diǎn)到達(dá)。（只適合時(shí)鐘回?fù)茌^小的）
• 利用拓展位，回?fù)苤笤贁U(kuò)展位上加1就可以了，這樣ID依然可以保持唯一。但是找個(gè)要求我們提前預(yù)留出位數(shù)，要么從機(jī)器id中，要么從序列號(hào)中，騰出一定的位，在時(shí)間回?fù)艿臅r(shí)候，這個(gè)位置+1.
• 緩存workerID，減少第三方組件的依賴
• 由于強(qiáng)依賴時(shí)鐘，對(duì)時(shí)間的要求比較敏感，在機(jī)器工作時(shí)NTP同步也會(huì)造成秒級(jí)別的回退，建議可以直接關(guān)閉NTP同步。要么在時(shí)鐘回?fù)艿臅r(shí)候直接不提供服務(wù)直接返回ERROR_CODE，等時(shí)鐘追上即可。或者做一層重試，然后上報(bào)報(bào)警系統(tǒng)，更或者是發(fā)現(xiàn)有時(shí)鐘回?fù)苤笞詣?dòng)摘除本身節(jié)點(diǎn)并報(bào)警

2.工作機(jī)器ID可能會(huì)重復(fù)的問題

機(jī)器 ID（5 位）和數(shù)據(jù)中心 ID（5 位）配置沒有解決（不一定各是5位，可自行配置），分布式部署的時(shí)候會(huì)使用相同的配置，仍然有 ID 重復(fù)的風(fēng)險(xiǎn)。

解決方案

• workId 使用服務(wù)器?hostName?生成，dataCenterId 使用 IP 生成，這樣可以最大限度防止 10 位機(jī)器碼重復(fù)，但是由于兩個(gè) ID 都不能超過 32，只能取余數(shù)，還是難免產(chǎn)生重復(fù)，但是實(shí)際使用中，hostName 和 IP 的配置一般連續(xù)或相近，只要不是剛好相隔 32 位，就不會(huì)有問題，況且，hostName 和 IP 同時(shí)相隔 32 的情況更加是幾乎不可能的事，平時(shí)做的分布式部署，一般也不會(huì)超過 10 臺(tái)容器

注意：使用ip地址時(shí)要考慮到使用docker容器部署時(shí)ip可能會(huì)相同的情況。

• 所有的節(jié)點(diǎn)共用一個(gè)數(shù)據(jù)庫(kù)配置，每次節(jié)點(diǎn)重啟，往mysql某個(gè)自建的表中新增一條數(shù)據(jù)，主鍵id自增并且自增id 要和 2^10-1 做按位與操作，防止總計(jì)重啟次數(shù)超過 2^10 后溢出。使用這個(gè)自增的id作為機(jī)器碼，這樣能保證機(jī)器碼絕對(duì)不重復(fù)。如果是TiDB這種分布式數(shù)據(jù)庫(kù)（id自增分片不連續(xù)），按位與操作后，還要注意不能拿到相同的workId。

3.?-1L ^ (-1L << x) 表示什么？

表示 x 位二進(jìn)制可以表示多少個(gè)數(shù)值，假設(shè)x為3：

在計(jì)算機(jī)中，第一位是符號(hào)位，負(fù)數(shù)的反碼是除了符號(hào)位，1變0，0變1, 而補(bǔ)碼則是反碼+1：

-1L 原碼：1000 0001
-1L 反碼：1111 1110
-1L 補(bǔ)碼：1111 1111 ????????????

從上面的結(jié)果可以知道，-1L其實(shí)在二進(jìn)制里面其實(shí)就是全部為1,那么 -1L 左移動(dòng) 3位，其實(shí)得到?1111 1000，也就是最后3位是0，再與-1L異或計(jì)算之后，其實(shí)得到的，就是后面3位全是1。-1L ^ (-1L << x)表示的其實(shí)就是x位全是1的值，也就是x位的二進(jìn)制能表示的最大數(shù)值。

4.前端直接使用發(fā)生精度丟失

????????如果前端直接使用服務(wù)端生成的long 類型 id，會(huì)發(fā)生精度丟失的問題，因?yàn)?JS 中Number是16位的（指的是十進(jìn)制的數(shù)字），而雪花算法計(jì)算出來最長(zhǎng)的數(shù)字是19位的，這個(gè)時(shí)候需要用 String 作為中間轉(zhuǎn)換，輸出到前端即可。

作者：筱白愛學(xué)習(xí)！！

歡迎關(guān)注轉(zhuǎn)發(fā)評(píng)論點(diǎn)贊溝通，您的支持是筱白的動(dòng)力！

???????文章來源地址http://www.zghlxwxcb.cn/news/detail-671739.html

到了這里，關(guān)于分布式Id生成之雪花算法（SnowFlake）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！