分布式ID必要性。

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

分布式ID需滿足那些條件

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

1. UUID

UUID 是指Universally Unique Identifier，翻譯為中文是通用唯一識別碼，UUID 的目的是讓分布式系統中的所有元素都能有唯一的識別信息。形式為 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);
 }
復制代碼

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

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

2. 基于數據庫自增ID

基于數據庫的auto_increment自增ID完全可以充當分布式ID，具體實現：需要一個單獨的MySQL實例用來生成ID，建表結構如下：

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本身就是系統的瓶頸，用它來實現分布式服務風險比較大，不推薦！

優點：實現簡單，ID單調自增，數值類型查詢速度快

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

3. 基于數據庫集群模式

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

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起始生成位置設定在比現有最大自增ID的位置遠一些，但必須在一、二兩臺MySQL實例ID還沒有增長到第三臺MySQL實例的起始ID值的時候，否則自增ID就要出現重復了，必要時可能還需要停機修改。

優點：解決DB單點問題

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

4. 基于數據庫的號段模式

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

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 '業務類型',
  `version` int(20) NOT NULL COMMENT '版本號',
  PRIMARY KEY (`id`)
)
復制代碼

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

id biz_type max_id step version 1 101 1000 2000 0

等這批號段ID用完，再次向數據庫申請新號段，對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
復制代碼

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

5. 基于redis模式

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

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

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

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

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

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

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

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

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

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

最后再判斷一下，當前這臺機房的這臺機器上這一毫秒內，這是第幾個請求，給這次生成 id 的請求累加一個序號，作為最后的 12 個 bit。最終一個 64 個 bit 的 id 就出來了，類似于：

這個算法可以保證一個機房的一臺機器在同一毫秒內，生成了一個唯一的 id。可能一個毫秒內會生成多個 id，但是有最后 12 個 bit 的序號來區分開來。

總結：就是用一個 64 bit 的數字中各個 bit 位來設置不同的標志位，區分每一個 id。

SnowFlake 算法的實現代碼如下：

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

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

 /**
  * 數據標識id所占的位數
  */
 private final long dataCenterIdBits = 5L;

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

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

 /**
  * 序列在id中占的位數
  */
 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;

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

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

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

 /**
  * 構造函數
  *
  * @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生成的時間戳，說明系統時鐘回退過這個時候應當拋出異常
  if (timestamp < lastTimestamp)
  {
   throw new RuntimeException((String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp)));

  }

  //如果是毫秒級別內是同一時間生成的，則進行毫秒內序列生成
  if (lastTimestamp == timestamp)
  {
   sequence = (sequence + 1) & sequenceMask;
   //毫秒內序列溢出，一毫秒內超過了4095個
   if (sequence == 0)
   {
    //阻塞到下一個毫秒,獲得新的時間戳
    timestamp = tilNextMillis(lastTimestamp);
   }
  }
  else
  {
   //時間戳改變，毫秒內序列重置
   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算法的優點：

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

SnowFlake算法的缺點：

• 依賴與系統時間的一致性，如果系統時間被回調，或者改變，可能會造成id沖突或者重復。

實際中我們的機房并沒有那么多，我們可以改進改算法，將10bit的機器id優化成業務表或者和我們系統相關的業務。

7. 百度uid-generator

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

uid-generator需要與數據庫配合使用，需要新增一個WORKER_NODE表。當應用啟動時會向數據庫表中去插入一條數據，插入成功后返回的自增ID就是該機器的workId數據由host，port組成。

由上圖可知，UidGenerator的時間部分只有28位，這就意味著UidGenerator默認只能承受8.5年（2^28-1/86400/365）。當然，根據你業務的需求，UidGenerator可以適當調整delta seconds、worker node id和sequence占用位數。

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

DefaultUidGenerator

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

worker id 接下來說一下UidGenerator是如何給worker id賦值的，搭建UidGenerator的話，需要創建一個表：

UidGenerator會在集成用它生成分布式ID的實例啟動的時候，往這個表中插入一行數據，得到的id值就是準備賦給workerId的值。由于workerId默認22位，那么，集成UidGenerator生成分布式ID的所有實例重啟次數是不允許超過4194303次（即2^22-1），否則會拋出異常。

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

• synchronized保證線程安全。
• 如果時間有任何的回撥，那么直接拋出異常。
• 如果當前時間和上一次是同一秒時間，那么sequence自增。如果同一秒內自增值超過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);
    }
復制代碼

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

<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的重要改進實現。它的核心利用了RingBuffer，如下圖所示，它本質上是一個數組，數組中每個項被稱為slot。UidGenerator設計了兩個RingBuffer，一個保存唯一ID，一個保存flag。RingBuffer的尺寸是2^n，n必須是正整數：

?Ivm?^

具體細節閱讀Git源碼即可，可以直接通過 SpringBoot 集成開發使用。

8. 美團（Leaf）

Leaf由美團開發，github地址：github.com/Meituan-Dia…，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 '業務key',
  `max_id` bigint(20) NOT NULL DEFAULT '1' COMMENT '當前已經分配了的最大id',
  `step` int(11) NOT NULL COMMENT '初始步長，也是動態調整的最小步長',
  `description` varchar(256)  DEFAULT NULL COMMENT '業務key的描述',
  `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '數據庫維護的更新時間',
  PRIMARY KEY (`biz_tag`)
) ENGINE=InnoDB;
復制代碼

然后在項目中開啟號段模式，配置對應的數據庫信息，并關閉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 監控號段模式：http://localhost:8080/cache

snowflake模式

Leaf的snowflake模式依賴于ZooKeeper，不同于原始snowflake算法也主要是在workId的生成上，Leaf中workId是基于ZooKeeper的順序Id來生成的，每個應用在使用Leaf-snowflake時，啟動時都會都在Zookeeper中生成一個順序Id，相當于一臺機器對應一個順序節點，也就是一個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 由滴滴開發，Github地址：github.com/didi/tinyid

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

Tinyid教程 的原理非常簡單，通過數據庫表中的數據基本是就能猜出個八九不離十，就是經典的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），即設定loadingId為20%的閾值，例如當前id是10000，步長為10000，那么loadingId=12000。那么當請求分布式ID分配到12001時（或者重啟后），即超過loadingId，就會返回一個特殊code：new Result(ResultCode.LOADING, id);tinyid-server根據ResultCode.LOADING這個響應碼就會異步分配下一個segment(4000, 5000]，以此類推。

原文鏈接：https://juejin.im/post/5f200842f265da22c9672b01