一、問題

為什么需要分布式全局唯一ID以及分布式ID的業務需求

在復雜分布式系統中，往往需要對大量的數據和消息進行唯一標識

如在美團點評的金融、支付、餐飲、酒店;

貓眼電影等產品的系統中數據日漸增長，對數據分庫分表后需要有一個唯一ID來標識一條數據或消息;

特別一點的如訂單、騎手、優惠券也都需要有唯一ID做標識。

此時一個能夠生成全局唯一ID的系統是非常必要的

ID生成規則部分硬性要求

①全局唯一

即不能出現重復ID號

②趨勢遞增

在Mysql的InnoDB引擎中使用的是聚集索引，由于多數RDBMS使用的是BTree的數據結構作為存儲索引數據，在主鍵的選擇上我們應該盡量使用有序的主鍵保證寫入性能

③單調遞增

保證下一個ID一定大于上一個ID，如事務版本號、排序等特殊要求

④信息安全

如果ID是連續的，惡意用戶的扒取工作就非常容易做了，直接按照順序下載指定URL即可:如果是訂單號就更危險了，競對可以直接知道我們一天的單量。所以在一些應用場景下，需要ID無規則不規則，讓競爭對手不好猜

⑤含時間戳

在開發中能快速了解這個分布式id生成的時間

ID號生成系統的可用性要求

①高可用

發一個獲取分布式ID的請求，服務器要保證99.999%的情況下能給我返回一個分布式ID

②低延遲

返回的速度要快

③高QPS（抵抗高訪問）

比如一秒內10萬個，需要服務器能抵抗住并且生成10萬個分布式ID

二、一般通用方案

（一）UUID

jdk自帶，生成36位字符，形式為8-4-4-4-12，包含4個連號－，對于單體式僅需滿足唯一的話可以使用

好處：性能高，本地生成，無網絡消耗

壞處：無序且字符串長，存入數據庫會增大數據庫壓力，入數據庫性能差。mysql官方推薦主鍵越短越好

索引， B+樹索引的分裂

既然分布式id是主鍵，然后主鍵是包含索引的，然后mysql的索引是通過b+樹來實現的，每一次新的UUID數據的插入，為了查詢的優化，都會對索引底層的b+樹進行修改，因為UUID數據是無序的。

所以每一次UUID數據的插入都會對主鍵地的b+樹進行很大的修改，這一點很不好。插入完全無序，不但會導致一些中間節點產生分裂，也會白白創造出很多不飽和的節點，這樣大大降低了數據庫插入的性能

（二）數據庫自增主鍵

數據庫自增主鍵實現原理：數據庫自增id和replace into實現的

REPLACE INTO的含義是插入一條記錄，如果表中唯一索引的值遇到沖突，則替換老數據

那數據庫自增ID機制適合作分布式ID嗎? 答案是不太適合

系統水平擴展比較困難，比如定義好了步長和機器臺數之后，如果要添加機器該怎么做? 假設現在只有一臺機器發號是1,2.3.4.5(步長是1)，這個時候需要擴容機器一臺。可以這樣做，把第二臺機器的初始值設置得比第一臺超過很多，貌似還好，現在想象一下如果我們線上有100臺機器，這個時候要擴容該怎么做? 簡直是噩夢。所以系統水平擴展方案復雜難以實現。

數據庫壓力還是很大，每次獲取ID都得讀寫一次數據庫，非常影響性能，不符合分布式ID里面的延遲低和要高QPS的規則(在高并發下，如果都去數據庫里面獲取id，那是非常影響性能的)

（三）Redis生成全局id策略

因為Redis是單線的天生保證原子性，可以使用原子操作INCR和INCRBY來實現

注意:在Redis集群情況下，同樣和MySQL一樣需要設置不同的增長步長，同時key一定要設置有效期

可以使用Redis集群來獲取更高的吞吐量。

假如一個集群中有5臺Redis。可以初始化每臺Redis的值分別是1,2,3,4,5，然后步長都是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

三、snowflake

（一）概述

Twitter的分布式自增ID算法

特點：

① 能夠按照時間有序生成

②Snowflake算法生成id的結果是一個64bit大小的整數，為一個Long型，轉化為字符串最多19位

③分布式系統內不會產生ID碰撞(由datacenter和workerld作區分) 并且效率較高。

（二）結構

bit表示＋-，id一般為正，所以固定為0

時間戳位范圍為0-2^41次方，大概是可以使用69年（從1970算起）

工作進程位最多為2^10，即1024個節點，包括5位datacenter和5位workerld作區分

12bit-序列號，序列號，用來記錄同毫秒內產生的不同id。12位(bit) 可以表示的最大正整數是2^12-1=4059

（三）代碼

/**
*Twitter_Snowflake

*SnowFlake的結構如下(每部分用-分開):

*0-00000000000000000000000000000000000000000-00000-00000-000000000000

*1位標識，由于long基本類型在Java中是帶符號的，最高位是符號位，正數是0，負數是1，所以id一般是正數，最高位是0

*41位時間截(毫秒級)，注意，41位時間截不是存儲當前時間的時間截，而是存儲時間截的差值（當前時間截-開始時間截)
*得到的值），這里的的開始時間截，一般是我們的id生成器開始使用的時間，由我們程序來指定的（如下下面程序IdWorker類的startTime屬性）。41位的時間截，可以使用69年，年T =(1L << 41)?/?(1000L * 60?* 60?* 24 * 365)?= 69

*10位的數據機器位，可以部署在1024個節點，包括5位datacenterId和5位workerId

*12位序列，毫秒內的計數，12位的計數順序號支持每個節點每毫秒(同一機器，同一時間截)產生4096個ID序號

*加起來剛好64位，為一個Long型。

* SnowFlake的優點是，整體上按照時間自增排序，并且整個分布式系統內不會產生ID碰撞(由數據中心ID和機器ID作區分)，并且效率較高，經測試，SnowFlake每秒能夠產生26萬ID左右。
*/
publicclassSnowflakeIdWorker{
//==============================Fields===========================================
/**開始時間截(2020-08-28)*/
privatefinallongtwepoch=1598598185157L;

/**機器id所占的位數*/
privatefinallongworkerIdBits=5L;

/**數據標識id所占的位數*/
privatefinallongdatacenterIdBits=5L;

/**支持的最大機器id，結果是31(這個移位算法可以很快的計算出幾位二進制數所能表示的最大十進制數)*/
privatefinallongmaxWorkerId=-1L^(-1L<maxWorkerId||workerIdmaxDatacenterId||datacenterId

	

	（四）優缺點

	優點:

	毫秒數在高位，自增序列在低位，整個ID都是趨勢遞增的。不依賴數據庫等第三方系統，以服務的方式部署，穩定性更高，生成ID的性能也是非常高的。可以根據自身業務特性分配bit位，非常靈活。

	缺點:

	依賴機器時鐘，如果機器時鐘回撥，會導致重復ID生成在單機上是遞增的，但是由于設計到分布式環境，每臺機器上的時鐘不可能完全同步，有時候會出現不是全局遞增的情況(此缺點可以認為無所謂，一般分布式ID只要求趨勢遞增，并不會亞格要求遞增，90%的需求都只要求趨勢遞增)

	缺點的解決方案

	可以參照以下兩個來進行機器時鐘的同步

	百度開源的分布式唯一ID生成器UidGenerator

	Leaf--美團點評分布式ID生成系統

	





	審核編輯：劉清