面試官:高併發下,如何保證分散式唯一全域性 ID 生成?

語言: CN / TW / HK

關注公眾號:IT老哥,每天閱讀一篇乾貨文章,一年後你會發現一個不一樣的自己。

前言

系統唯一ID是我們在設計一個系統的時候常常會遇見的問題,也常常為這個問題而糾結。

這篇文章就是給各位看官提供一個生成分散式唯一全域性id生成方案的思路,希望能幫助到大家。

不足之處,請多多指教!!

問題

為什麼需要分散式全域性唯一ID以及分散式ID的業務需求

在複雜分散式系統中,往往需要對大量的資料和訊息進行唯一標識,如在美團點評的金融、支付、餐飲、酒店

貓眼電影等產品的系統中資料逐漸增長,對資料庫分庫分表後需要有一個唯一ID來標識一條資料或資訊;

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

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

圖片

ID生成規則部分硬性要求

  • 全域性唯一

  • 趨勢遞增

  • 在MySQL的InnoDB引擎中使用的是聚集索引,由於多數RDBMS使用Btree的資料結構來儲存索引,在主鍵的選擇上面我們應該儘量使用有序的主鍵保證寫入效能

  • 單調遞增

  • 保證下一個ID一定大於上一個ID,例如事務版本號、IM增量訊息、排序等特殊需求

  • 資訊保安

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

  • 含時間戳

  • 一樣能夠快速在開發中瞭解這個分散式ID什麼時候生成的

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

  • 高可用

  • 釋出一個獲取分散式ID請求,伺服器就要保證99.999%的情況下給我建立一個唯一分散式ID

  • 低延遲

  • 發一個獲取分散式ID的請求,伺服器就要快,極速

  • 高QPS

  • 例如併發一口氣10萬個建立分散式ID請求同時殺過來,伺服器要頂得住且一下子成功建立10萬個分散式ID

一般通用解決方案

UUID

UUID.randomUUID(), UUID的標準型包含32個16進位制數字,以連字號分為五段,形式為 8-4-4-4-12的36個字元,效能非常高,本地生成,沒有網路消耗。

存在問題

入資料庫效能差,因為UUID是無序的

無序,無法預測他的生成順序,不能生成遞增有序的數字

首先分散式id一般都會作為逐漸,但是按照mysql官方推薦主鍵儘量越短越好,UUID每一個都很長,所以不是很推薦。

主鍵,ID作為主鍵時,在特定的環境下會存在一些問題

比如做DB主鍵的場景下,UUID就非常不適用MySQL官方有明確的說明

索引,B+樹索引的分裂

既然分散式ID是主鍵,然後主鍵是包含索引的,而mysql的索引是通過B+樹來實現的,每一次新的UUID資料的插入,為了查詢的優化,都會對索引底層的B+樹進行修改,因為UUID資料是無序的,所以每一次UUID資料的插入都會對主鍵的B+樹進行很大的修改,這一點很不好,插入完全無序,不但會導致一些中間節點產生分裂,也會白白創造出很多不飽和的節點,這樣大大降低了資料庫插入的效能。

UUID只能保證全域性唯一性,不滿足後面的趨勢遞增,單調遞增

資料庫自增主鍵

單機

在分散式裡面,資料庫的自增ID機制的主要原理是:資料庫自增ID和mysql資料庫的replace into實現的,這裡的replace into跟insert功能 類似,不同點在於:replace into首先嚐試插入資料列表中,如果發現表中已經有此行資料(根據主鍵或唯一索引判斷)則先刪除,在插入,否則直接插入新資料。

REPLACE INTO的含義是插入一條記錄,如果表中唯一索引的值遇到衝突,則替換老資料

圖片

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

```

我們每次插入的時候,發現都會把原來的資料給替換,並且ID也會增加

這就滿足了

  • 遞增性

  • 單調性

  • 唯一性

在分散式情況下,並且併發量不多的情況,可以使用這種方案來解決,獲得一個全域性的唯一ID

叢集分散式叢集

那資料庫自增ID機制適合做分散式ID嗎?答案是不太適合

系統水平擴充套件比較困難,比如定義好步長和機器臺數之後,如果要新增機器該怎麼辦,假設現在有一臺機器發號是:1,2,3,4,5,(步長是1),這個時候需要擴容機器一臺,可以這樣做:把第二胎機器的初始值設定得比第一臺超過很多,貌似還好,但是假設線上如果有100臺機器,這個時候擴容要怎麼做,簡直是噩夢,所以系統水平擴充套件方案複雜難以實現。

資料庫壓力還是很大,每次獲取ID都得讀寫一次資料庫,非常影響效能,不符合分散式ID裡面的延遲低和高QPS的規則(在高併發下,如果都去資料庫裡面獲取ID,那是非常影響效能的)

基於Redis生成全域性ID策略

單機版

因為Redis是單執行緒,天生保證原子性,可以使用原子操作INCR和INCRBY來實現

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

```

但是存在的問題是,就是Redis叢集的維護和保養比較麻煩,配置麻煩。因為要設定單點故障,哨兵值守

但是主要是的問題就是,為了一個ID,卻需要引入整個Redis叢集,有種殺雞焉用牛刀的感覺

雪花演算法

是什麼

Twitter的分散式自增ID演算法,Snowflake

最初Twitter把儲存系統從MySQL遷移到Cassandra(由Facebook開發一套開源分散式NoSQL資料庫系統)因為Cassandra沒有順序ID生成機制,所有開發了這樣一套全域性唯一ID生成服務。

Twitter的分散式雪花演算法SnowFlake,經測試SnowFlake每秒可以產生26萬個自增可排序的ID

  • twitter的SnowFlake生成ID能夠按照時間有序生成

  • SnowFlake演算法生成ID的結果是一個64Bit大小的整數,為一個Long型(轉換成字串後長度最多19)

  • 分散式系統內不會產生ID碰撞(由datacenter 和 workerID做區分)並且效率較高

分散式系統中,有一些需要全域性唯一ID的場景,生成ID的基本要求

  • 在分散式環境下,必須全域性唯一性

  • 一般都需要單調遞增,因為一般唯一ID都會存在資料庫,而InnoDB的特性就是將內容儲存在主鍵索引上的葉子節點,而且是從左往右遞增的,所有考慮到資料庫效能,一般生成ID也最好是單調遞增的。為了防止ID衝突可以使用36位UUID,但是UUID有一些缺點,首先是它相對比較長,並且另外UUID一般是無序的

  • 可能還會需要無規則,因為如果使用唯一ID作為訂單號這種,為了不讓別人知道一天的訂單量多少,就需要這種規則

結構

雪花演算法的幾個核心組成部分

圖片

在Java中64bit的證書是long型別,所以在SnowFlake演算法生成的ID就是long類儲存的

第一部分

二進位制中最高位是符號位,1表示負數,0表示正數。生成的ID一般都是用整數,所以最高位固定為0。

第二部分

第二部分是41bit時間戳位,用來記錄時間戳,毫秒級

41位可以表示 2^41 -1 個數字

如果只用來表示正整數,可以表示的範圍是:0 - 2^41 -1,減1是因為可以表示的數值範圍是從0開始計算的,而不是從1。

也就是說41位可以表示 2^41 - 1 毫秒的值,轉換成單位年則是 69.73年

第三部分

第三部分為工作機器ID,10Bit用來記錄工作機器ID

可以部署在2^10 = 1024個節點,包括5位 datacenterId(資料中心,機房) 和 5位 workerID(機器碼)

5位可以表示的最大正整數是 2 ^ 5 = 31個數字,來表示不同的資料中心 和 機器碼

第四部分

12位bit可以用來表示的正整數是 2^12 = 4095,即可以用0 1 2 … 4094 來表示同一個機器同一個時間戳內產生的4095個ID序號。

SnowFlake可以保證

所有生成的ID按時間趨勢遞增

整個分散式系統內不會產生重複ID,因為有datacenterId 和 workerId來做區分

實現

雪花演算法是由scala演算法編寫的,有人使用java實現,github地址

https://github.com/beyondfengyu/SnowFlake/blob/master/SnowFlake.java

``` /*  * twitter的snowflake演算法 -- java實現  *   * @author beyond  / public class SnowFlake {

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

/*      * 每一部分佔用的位數      /     private final static long SEQUENCE_BIT = 12; //序列號佔用的位數     private final static long MACHINE_BIT = 5;   //機器標識佔用的位數     private final static long DATACENTER_BIT = 5;//資料中心佔用的位數

/*      * 每一部分的最大值      /     private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);     private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);     private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);

/*      * 每一部分向左的位移      /     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;  //資料中心     private long machineId;     //機器標識     private long sequence = 0L; //序列號     private long lastStmp = -1L;//上一次時間戳

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;     }

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

if (currStmp == lastStmp) {             //相同毫秒內,序列號自增             sequence = (sequence + 1) & MAX_SEQUENCE;             //同一毫秒的序列數已經達到最大             if (sequence == 0L) {                 currStmp = getNextMill();             }         } else {             //不同毫秒內,序列號置為0             sequence = 0L;         }

lastStmp = currStmp;

return (currStmp - START_STMP) << TIMESTMP_LEFT //時間戳部分                 | datacenterId << DATACENTER_LEFT       //資料中心部分                 | machineId << MACHINE_LEFT             //機器標識部分                 | 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());         }

} }

```

工程落地經驗

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 {             // 將網路ip轉換成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

```

優缺點

優點
  • 毫秒數在高維,自增序列在低位,整個ID都是趨勢遞增的

  • 不依賴資料庫等第三方系統,以服務的方式部署,穩定性更高,生成ID的效能也是非常高的

  • 可以根據自身業務特性分配bit位,非常靈活

缺點
  • 依賴機器時鐘,如果機器時鐘回撥,會導致重複ID生成

  • 在單機上是遞增的,但由於涉及到分散式環境,每臺機器上的時鐘不可能完全同步,有時候會出現不是全域性遞增的情況,此缺點可以認為無所謂,一般分散式ID只要求趨勢遞增,並不會嚴格要求遞增,90%的需求只要求趨勢遞增。

其它補充
  • 為了解決時鐘回撥問題,導致ID重複,後面有人專門提出瞭解決的方案

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

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

關注公眾號:IT老哥,每天閱讀一篇乾貨文章,一年後你會發現一個不一樣的自己。