點擊關(guān)注公眾號，Java干貨及時送達

轉(zhuǎn)自公眾號：SoWhat1412

分布式ID必要性。

業(yè)務量小于500W或數(shù)據(jù)容量小于2G的時候單獨一個mysql即可提供服務，再大點的時候就進行讀寫分離也可以應付過來。但當主從同步也扛不住的是就需要分表分庫了，但分庫分表后需要有一個唯一ID來標識一條數(shù)據(jù)，數(shù)據(jù)庫的自增ID顯然不能滿足需求；特別一點的如訂單、優(yōu)惠券也都需要有唯一ID做標識。此時一個能夠生成全局唯一ID的系統(tǒng)是非常必要的。那么這個全局唯一ID就叫分布式ID。

分布式ID需滿足那些條件

全局唯一：基本要求就是必須保證ID是全局性唯一的。
高性能：高可用低延時，ID生成響應要快。
高可用：無限接近于100%的可用性
好接入：遵循拿來主義原則，在系統(tǒng)設(shè)計和實現(xiàn)上要盡可能的簡單
趨勢遞增：最好趨勢遞增，這個要求就得看具體業(yè)務場景了，一般不嚴格要求

1. UUID

UUID 是指Universally Unique Identifier，翻譯為中文是通用唯一識別碼，UUID 的目的是讓分布式系統(tǒng)中的所有元素都能有唯一的識別信息。形式為 8-4-4-4-12，總共有 36個字符。用起來非常簡單

import java.util.UUID;
 public static void main(String[] args) {
  String uuid = UUID.randomUUID().toString().replaceAll("-","");
  System.out.println(uuid);
 }

輸出結(jié)果99a7d0925b294a53b2f4db9d5a3fb798，但UUID卻并不適用于實際的業(yè)務需求。訂單號用UUID這樣的字符串沒有絲毫的意義，看不出和訂單相關(guān)的有用信息；而對于數(shù)據(jù)庫來說用作業(yè)務主鍵ID，它不僅是太長還是字符串，存儲性能差查詢也很耗時，所以不推薦用作分布式ID。

優(yōu)點：生成足夠簡單，本地生成無網(wǎng)絡(luò)消耗，具有唯一性缺點：無序的字符串，不具備趨勢自增特性，沒有具體的業(yè)務含義。如此長的字符串當MySQL主鍵并非明智選擇。

2. 基于數(shù)據(jù)庫自增ID

基于數(shù)據(jù)庫的auto_increment自增ID完全可以充當分布式ID，具體實現(xiàn)：需要一個單獨的MySQL實例用來生成ID，建表結(jié)構(gòu)如下：

CREATE DATABASE `SoWhat_ID`;
CREATE TABLE SoWhat_ID.SEQUENCE_ID (
    `id` bigint(20) unsigned NOT NULL auto_increment, 
    `value` char(10) NOT NULL default '',
    `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
    PRIMARY KEY (id),
) ENGINE=MyISAM;
insert into SEQUENCE_ID(value) VALUES ('values');

當我們需要一個ID的時候，向表中插入一條記錄返回主鍵ID，但這種方式有一個比較致命的缺點，訪問量激增時MySQL本身就是系統(tǒng)的瓶頸，用它來實現(xiàn)分布式服務風險比較大，不推薦！

優(yōu)點：實現(xiàn)簡單，ID單調(diào)自增，數(shù)值類型查詢速度快

缺點：DB單點存在宕機風險，無法扛住高并發(fā)場景

3. 基于數(shù)據(jù)庫集群模式

前邊說了單點數(shù)據(jù)庫方式不可取，那對上邊的方式做一些高可用優(yōu)化，換成主從模式集群。害怕一個主節(jié)點掛掉沒法用，那就做雙主模式集群，也就是兩個Mysql實例都能單獨的生產(chǎn)自增ID。那這樣還會有個問題，兩個MySQL實例的自增ID都從1開始，會生成重復的ID怎么辦？解決方案：設(shè)置起始值和自增步長

MySQL_1 配置：

set @@auto_increment_offset = 1;     -- 起始值
set @@auto_increment_increment = 2;  -- 步長

MySQL_2 配置：

set @@auto_increment_offset = 2;     -- 起始值
set @@auto_increment_increment = 2;  -- 步長

這樣兩個MySQL實例的自增ID分別就是：

1、3、5、7、9 
2、4、6、8、10

但是如果兩個還是無法滿足咋辦呢？增加第三臺MySQL實例需要人工修改一、二兩臺MySQL實例的起始值和步長，把第三臺機器的ID起始生成位置設(shè)定在比現(xiàn)有最大自增ID的位置遠一些，但必須在一、二兩臺MySQL實例ID還沒有增長到第三臺MySQL實例的起始ID值的時候，否則自增ID就要出現(xiàn)重復了，必要時可能還需要停機修改。

優(yōu)點：解決DB單點問題

缺點：不利于后續(xù)擴容，而且實際上單個數(shù)據(jù)庫自身壓力還是大，依舊無法滿足高并發(fā)場景。

4. 基于數(shù)據(jù)庫的號段模式

號段模式是當下分布式ID生成器的主流實現(xiàn)方式之一，號段模式可以理解為從數(shù)據(jù)庫批量的獲取自增ID，每次從數(shù)據(jù)庫取出一個號段范圍，例如 (1,1000] 代表1000個ID，具體的業(yè)務服務將本號段，生成1~1000的自增ID并加載到內(nèi)存。表結(jié)構(gòu)如下：

CREATE TABLE id_generator (
  `id` int(10) NOT NULL,
  `max_id` bigint(20) NOT NULL COMMENT '當前最大id',
  `step` int(20) NOT NULL COMMENT '號段的步長',
  `biz_type`    int(20) NOT NULL COMMENT '業(yè)務類型',
  `version` int(20) NOT NULL COMMENT '版本號',
  PRIMARY KEY (`id`)
)

max_id ：當前最大的可用id
step ：代表號段的長度
biz_type ：代表不同業(yè)務類型
version ：是一個樂觀鎖，每次都更新version，保證并發(fā)時數(shù)據(jù)的正確性

id	biz_type	max_id	step	version
1	101	1000	2000	0

等這批號段ID用完，再次向數(shù)據(jù)庫申請新號段，對max_id字段做一次update操作，update max_id= max_id + step，update成功則說明新號段獲取成功，新的號段范圍是(max_id ,max_id +step]。

update id_generator set max_id = {max_id+step}, version = version + 1
 where version =  {version} and biz_type = XX

由于多業(yè)務端可能同時操作，所以采用版本號 version樂觀鎖方式更新，這種分布式ID生成方式不強依賴于數(shù)據(jù)庫，不會頻繁的訪問數(shù)據(jù)庫，對數(shù)據(jù)庫的壓力小很多。但是如果遇到了雙十一或者秒殺類似的活動還是會對數(shù)據(jù)庫有比較高的訪問。

5. 基于Redis模式

Redis 也同樣可以實現(xiàn)，原理就是Redis 是單線程的，因此我們可以利用redis的incr命令實現(xiàn)ID的原子性自增。

127.0.0.1:6379> set seq_id 1     // 初始化自增ID為1
OK
127.0.0.1:6379> incr seq_id      // 增加1，并返回遞增后的數(shù)值
(integer) 2

用redis實現(xiàn)需要注意一點，要考慮到redis持久化的問題。redis有兩種持久化方式RDB和AOF。

6. 基于雪花算法（Snowflake）模式

SnowFlake 算法，是 Twitter 開源的分布式 id 生成算法。其核心思想就是：使用一個 64 bit 的 long 型的數(shù)字作為全局唯一 id。在分布式系統(tǒng)中的應用十分廣泛，且ID 引入了時間戳，為什么叫雪花算法呢？私以為眾所周知世界上沒有一對相同的雪花。雪花算法基本上保持自增的，后面的代碼中有詳細的注解。這 64 個 bit 中，其中 1 個 bit 是不用的，然后用其中的 41 bit 作為毫秒數(shù)，用 10 bit 作為工作機器 id，12 bit 作為序列號。舉例如上圖：

第一個部分是 1 個 bit：0，這個是無意義的。因為二進制里第一個 bit 位如果是 1，那么都是負數(shù)，但是我們生成的 id 都是正數(shù)，所以第一個 bit 統(tǒng)一都是 0。
第二個部分是 41 個 bit：表示的是時間戳。單位是毫秒。41 bit 可以表示的數(shù)字多達 2^41 - 1，也就是可以標識 2 ^ 41 - 1 個毫秒值，換算成年就是表示69年的時間。
第三個部分是 5 個 bit：表示的是機房 id 5 個 bit 代表機器 id。意思就是最多代表 2 ^ 5 個機房（32 個機房）
第四個部分是 5 個 bit：表示的是機器 id。每個機房里可以代表 2 ^ 5 個機器（32 臺機器），也可以根據(jù)自己公司的實際情況確定。
第五個部分是 12 個 bit：表示的序號，就是某個機房某臺機器上這一毫秒內(nèi)同時生成的 id 的序號。12 bit 可以代表的最大正整數(shù)是 2 ^ 12 - 1 = 4096，也就是說可以用這個 12 bit 代表的數(shù)字來區(qū)分同一個毫秒內(nèi)的 4096 個不同的 id。

總結(jié)：簡單來說，你的某個服務假設(shè)要生成一個全局唯一 id，那么就可以發(fā)送一個請求給部署了 SnowFlake 算法的系統(tǒng)，由這個 SnowFlake 算法系統(tǒng)來生成唯一 id。

這個 SnowFlake 算法系統(tǒng)首先肯定是知道自己所在的機房和機器的，比如機房 id = 17，機器 id = 12。

接著 SnowFlake 算法系統(tǒng)接收到這個請求之后，首先就會用二進制位運算的方式生成一個 64 bit 的 long 型 id，64 個 bit 中的第一個 bit 是無意義的。

接著 41 個 bit，就可以用當前時間戳（單位到毫秒），然后接著 5 個 bit 設(shè)置上這個機房 id，還有 5 個 bit 設(shè)置上機器 id。

最后再判斷一下，當前這臺機房的這臺機器上這一毫秒內(nèi)，這是第幾個請求，給這次生成 id 的請求累加一個序號，作為最后的 12 個 bit。最終一個 64 個 bit 的 id 就出來了，類似于：這個算法可以保證一個機房的一臺機器在同一毫秒內(nèi)，生成了一個唯一的 id。可能一個毫秒內(nèi)會生成多個 id，但是有最后 12 個 bit 的序號來區(qū)分開來。

總結(jié)：就是用一個 64 bit 的數(shù)字中各個 bit 位來設(shè)置不同的標志位，區(qū)分每一個 id。

SnowFlake 算法的實現(xiàn)代碼如下：

/**
 * 雪花算法相對來說如果思緒捋順了實現(xiàn)起來比較簡單，前提熟悉位運算。
 */
public class SnowFlake
{
 /**
  * 開始時間截 (2015-01-01)
  */
 private final long twepoch = 1420041600000L;

 /**
  * 機器id所占的位數(shù)
  */
 private final long workerIdBits = 5L;

 /**
  * 數(shù)據(jù)標識id所占的位數(shù)
  */
 private final long dataCenterIdBits = 5L;

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

 /**
  * 支持的最大機房標識id，結(jié)果是31
  */
 private final long maxDataCenterId = ~(-1L << dataCenterIdBits);

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

 /**
  * 機器ID向左移12位
  */
 private final long workerIdShift = sequenceBits;

 /**
  * 機房標識id向左移17位(12+5)
  */
 private final long dataCenterIdShift = sequenceBits + workerIdBits;

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

 /**
  * 生成序列的掩碼，這里為4095 (0b111111111111=0xfff=4095)
  */
 private final long sequenceMask = ~(-1L << sequenceBits);

 /**
  * 工作機器ID(0~31)
  */
 private volatile long workerId;

 /**
  * 機房中心ID(0~31)
  */
 private volatile long dataCenterId;

 /**
  * 毫秒內(nèi)序列(0~4095)
  */
 private volatile long sequence = 0L;

 /**
  * 上次生成ID的時間截
  */
 private volatile long lastTimestamp = -1L;

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

 /**
  * 構(gòu)造函數(shù)
  *
  * @param workerId     工作ID (0~31)
  * @param dataCenterId 機房中心ID (0~31)
  */

 public SnowFlake(long workerId, long dataCenterId)
 {
  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));
  }
  this.workerId = workerId;
  this.dataCenterId = dataCenterId;
 }

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

 /**
  * 獲得下一個ID (該方法是線程安全的)
  * 如果一個線程反復獲取Synchronized鎖，那么synchronized鎖將變成偏向鎖。
  *
  * @return SnowflakeId
  */
 public synchronized long nextId() throws RuntimeException
 {
  long timestamp = timeGen();

  //如果當前時間小于上一次ID生成的時間戳，說明系統(tǒng)時鐘回退過這個時候應當拋出異常
  if (timestamp < lastTimestamp)
  {
   throw new RuntimeException((String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp)));

  }

  //如果是毫秒級別內(nèi)是同一時間生成的，則進行毫秒內(nèi)序列生成
  if (lastTimestamp == timestamp)
  {
   sequence = (sequence + 1) & sequenceMask;
   //毫秒內(nèi)序列溢出，一毫秒內(nèi)超過了4095個
   if (sequence == 0)
   {
    //阻塞到下一個毫秒,獲得新的時間戳
    timestamp = tilNextMillis(lastTimestamp);
   }
  }
  else
  {
   //時間戳改變，毫秒內(nèi)序列重置
   sequence = 0L;
  }

  //上次生成ID的時間截
  lastTimestamp = timestamp;

  //移位并通過或運算拼到一起組成64位的ID
  return ((timestamp - twepoch) << timestampLeftShift)
    | (dataCenterId << dataCenterIdShift)
    | (workerId << workerIdShift)
    | sequence;
 }

 /**
  * 阻塞到下一個毫秒，直到獲得新的時間戳
  * @param lastTimestamp 上次生成ID的時間截
  * @return 當前時間戳
  */
 private long tilNextMillis(long lastTimestamp)
 {
  long timestamp = timeGen();
  while (timestamp <= lastTimestamp)
  {
   timestamp = timeGen();
  }
  return timestamp;
 }

 /**
  * 返回以毫秒為單位的當前時間
  * @return 當前時間(毫秒)
  */
 private long timeGen()
 {
  return System.currentTimeMillis();
 }
}

SnowFlake算法的優(yōu)點：

高性能高可用：生成時不依賴于數(shù)據(jù)庫，完全在內(nèi)存中生成。
容量大：每秒中能生成數(shù)百萬的自增ID。
ID自增：存入數(shù)據(jù)庫中，索引效率高。

SnowFlake算法的缺點：

依賴與系統(tǒng)時間的一致性，如果系統(tǒng)時間被回調(diào)，或者改變，可能會造成id沖突或者重復。

實際中我們的機房并沒有那么多，我們可以改進改算法，將10bit的機器id優(yōu)化成業(yè)務表或者和我們系統(tǒng)相關(guān)的業(yè)務。

7. 百度uid-generator

項目GitHub地址：https://github.com/baidu/uid-generator，uid-generator是由百度技術(shù)部開發(fā)，基于Snowflake算法實現(xiàn)的，與原始的snowflake算法不同在于，uid-generator支持自定義時間戳、工作機器ID和序列號等各部分的位數(shù)，而且uid-generator中采用用戶自定義workId的生成策略。

uid-generator需要與數(shù)據(jù)庫配合使用，需要新增一個WORKER_NODE表。當應用啟動時會向數(shù)據(jù)庫表中去插入一條數(shù)據(jù)，插入成功后返回的自增ID就是該機器的workId數(shù)據(jù)由host，port組成。由上圖可知，UidGenerator的時間部分只有28位，這就意味著UidGenerator默認只能承受8.5年（2^28-1/86400/365）。當然，根據(jù)你業(yè)務的需求，UidGenerator可以適當調(diào)整delta seconds、worker node id和sequence占用位數(shù)。

接下來分析百度UidGenerator的實現(xiàn)。需要說明的是UidGenerator有兩種方式提供：和DefaultUidGenerator和CachedUidGenerator。我們先分析比較容易理解的DefaultUidGenerator。

DefaultUidGenerator

delta seconds這個值是指當前時間與epoch時間的時間差，且單位為秒。epoch時間就是指集成UidGenerator生成分布式ID服務第一次上線的時間，可配置，也一定要根據(jù)你的上線時間進行配置，因為默認的epoch時間可是2016-09-20，不配置的話，會浪費好幾年的可用時間。

worker id接下來說一下UidGenerator是如何給worker id賦值的，搭建UidGenerator的話，需要創(chuàng)建一個表：UidGenerator會在集成用它生成分布式ID的實例啟動的時候，往這個表中插入一行數(shù)據(jù)，得到的id值就是準備賦給workerId的值。由于workerId默認22位，那么，集成UidGenerator生成分布式ID的所有實例重啟次數(shù)是不允許超過4194303次（即2^22-1），否則會拋出異常。

這段邏輯的核心代碼來自DisposableWorkerIdAssigner.java中，當然，你也可以實現(xiàn)WorkerIdAssigner.java接口，自定義生成workerId。sequence核心代碼如下，幾個實現(xiàn)的關(guān)鍵點：

synchronized保證線程安全。
如果時間有任何的回撥，那么直接拋出異常。
如果當前時間和上一次是同一秒時間，那么sequence自增。如果同一秒內(nèi)自增值超過2^13-1，那么就-- 會自旋等待下一秒（getNextSecond）。
如果是新的一秒，那么sequence重新從0開始。

/**
     * Get UID
     *
     * @return UID
     * @throws UidGenerateException in the case: Clock moved backwards; Exceeds the max timestamp
     */
    protected synchronized long nextId() {
        long currentSecond = getCurrentSecond();
        // Clock moved backwards, refuse to generate uid
        if (currentSecond < lastSecond) {
            long refusedSeconds = lastSecond - currentSecond;
            throw new UidGenerateException("Clock moved backwards. Refusing for %d seconds", refusedSeconds);
        }
        // At the same second, increase sequence
        if (currentSecond == lastSecond) {
            sequence = (sequence + 1) & bitsAllocator.getMaxSequence();
            // Exceed the max sequence, we wait the next second to generate uid
            if (sequence == 0) {
                currentSecond = getNextSecond(lastSecond);
            }
        // At the different second, sequence restart from zero
        } else {
            sequence = 0L;
        }
        lastSecond = currentSecond;
        // Allocate bits for UID
        return bitsAllocator.allocate(currentSecond - epochSeconds, workerId, sequence);
    }

總結(jié)通過DefaultUidGenerator的實現(xiàn)可知，它對時鐘回撥的處理比較簡單粗暴。另外如果使用UidGenerator的DefaultUidGenerator方式生成分布式ID，一定要根據(jù)你的業(yè)務的情況和特點，調(diào)整各個字段占用的位數(shù)：

<property name="timeBits" value="28"/>
<property name="workerBits" value="22"/>
<property name="seqBits" value="13"/>
<property name="epochStr" value="2016-09-20"/>

CachedUidGenerator

CachedUidGenerator是UidGenerator的重要改進實現(xiàn)。它的核心利用了RingBuffer，如下圖所示，它本質(zhì)上是一個數(shù)組，數(shù)組中每個項被稱為slot。UidGenerator設(shè)計了兩個RingBuffer，一個保存唯一ID，一個保存flag。RingBuffer的尺寸是2^n，n必須是正整數(shù)：具體細節(jié)閱讀Git源碼即可，可以直接通過 SpringBoot 集成開發(fā)使用。

8. 美團（Leaf）

Leaf由美團開發(fā)，github地址：https://github.com/Meituan-Dianping/Leaf，Leaf同時支持號段模式和snowflake算法模式，可以切換使用。

號段模式

先導入源碼 https://github.com/Meituan-Dianping/Leaf ，在建一張表leaf_alloc

DROP TABLE IF EXISTS `leaf_alloc`;
CREATE TABLE `leaf_alloc` (
  `biz_tag` varchar(128)  NOT NULL DEFAULT '' COMMENT '業(yè)務key',
  `max_id` bigint(20) NOT NULL DEFAULT '1' COMMENT '當前已經(jīng)分配了的最大id',
  `step` int(11) NOT NULL COMMENT '初始步長，也是動態(tài)調(diào)整的最小步長',
  `description` varchar(256)  DEFAULT NULL COMMENT '業(yè)務key的描述',
  `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '數(shù)據(jù)庫維護的更新時間',
  PRIMARY KEY (`biz_tag`)
) ENGINE=InnoDB;

然后在項目中開啟號段模式，配置對應的數(shù)據(jù)庫信息，并關(guān)閉snowflake模式

leaf.name=com.sankuai.leaf.opensource.test
leaf.segment.enable=true
leaf.jdbc.url=jdbc:mysql://localhost:3306/leaf_test?useUnicode=true&characterEncoding=utf8&characterSetResults=utf8
leaf.jdbc.username=root
leaf.jdbc.password=root

leaf.snowflake.enable=false
#leaf.snowflake.zk.address=
#leaf.snowflake.port=

啟動leaf-server 模塊的 LeafServerApplication項目就跑起來了號段模式獲取分布式自增ID的測試url ：http：//localhost：8080/api/segment/get/leaf-segment-test 監(jiān)控號段模式：http://localhost:8080/cache

snowflake模式

Leaf的snowflake模式依賴于ZooKeeper，不同于原始snowflake算法也主要是在workId的生成上，Leaf中workId是基于ZooKeeper的順序Id來生成的，每個應用在使用Leaf-snowflake時，啟動時都會都在Zookeeper中生成一個順序Id，相當于一臺機器對應一個順序節(jié)點，也就是一個workId。

leaf.snowflake.enable=true
leaf.snowflake.zk.address=127.0.0.1
leaf.snowflake.port=2181

snowflake模式獲取分布式自增ID的測試url：http://localhost:8080/api/snowflake/get/test

9. 滴滴（Tinyid）

Tinyid由滴滴開發(fā)，Github地址：https://github.com/didi/tinyid

Tinyid是一個ID生成器服務，它提供了REST API和Java客戶端兩種獲取方式，如果使用Java客戶端獲取方式的話，官方宣稱能單實例能達到1kw QPS（Over10 million QPSper single instance when using the java client.）

Tinyid教程的原理非常簡單，通過數(shù)據(jù)庫表中的數(shù)據(jù)基本是就能猜出個八九不離十，就是經(jīng)典的segment模式，和美團的leaf原理幾乎一致。原理圖如下所示，以同一個bizType為例，每個tinyid-server會分配到不同的segment，例如第一個tinyid-server分配到(1000, 2000]，第二個tinyid-server分配到(2000, 3000]，第3個tinyid-server分配到(3000, 4000]：再以第一個tinyid-server為例，當它的segment用了20%（核心源碼：segmentId.setLoadingId(segmentId.getCurrentId().get() + idInfo.getStep() * Constants.LOADING_PERCENT / 100);，LOADING_PERCENT的值就是20），即設(shè)定loadingId為20%的閾值，例如當前id是10000，步長為10000，那么loadingId=12000。那么當請求分布式ID分配到12001時（或者重啟后），即超過loadingId，就會返回一個特殊code：new Result(ResultCode.LOADING, id);tinyid-server根據(jù)ResultCode.LOADING這個響應碼就會異步分配下一個segment(4000, 5000]，以此類推。