分布式ID必要性。

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

分布式ID需滿足那些條件

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

1. UUID

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

import JAVA.util.UUID;
 public static void main(String[] args) {
  String uuid = UUID.randomUUID().toString().replaceAll("-","");
  System.out.println(uuid);
 }
復(fù)制代碼

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

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

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

基于數(shù)據(jù)庫(kù)的auto_increment自增ID完全可以充當(dāng)分布式ID，具體實(shí)現(xiàn)：需要一個(gè)單獨(dú)的MySQL實(shí)例用來(lái)生成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');
復(fù)制代碼

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

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

缺點(diǎn)：DB單點(diǎn)存在宕機(jī)風(fēng)險(xiǎn)，無(wú)法扛住高并發(fā)場(chǎng)景

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

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

MySQL_1 配置：

set @@auto_increment_offset = 1;     -- 起始值
set @@auto_increment_increment = 2;  -- 步長(zhǎng)
復(fù)制代碼

MySQL_2 配置：

set @@auto_increment_offset = 2;     -- 起始值
set @@auto_increment_increment = 2;  -- 步長(zhǎng)
復(fù)制代碼

這樣兩個(gè)MySQL實(shí)例的自增ID分別就是：

1、3、5、7、9 
2、4、6、8、10
復(fù)制代碼

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

優(yōu)點(diǎn)：解決DB單點(diǎn)問(wèn)題

缺點(diǎn)：不利于后續(xù)擴(kuò)容，而且實(shí)際上單個(gè)數(shù)據(jù)庫(kù)自身壓力還是大，依舊無(wú)法滿足高并發(fā)場(chǎng)景。

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

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

CREATE TABLE id_generator (
  `id` int(10) NOT NULL,
  `max_id` bigint(20) NOT NULL COMMENT '當(dāng)前最大id',
  `step` int(20) NOT NULL COMMENT '號(hào)段的步長(zhǎng)',
  `biz_type`    int(20) NOT NULL COMMENT '業(yè)務(wù)類型',
  `version` int(20) NOT NULL COMMENT '版本號(hào)',
  PRIMARY KEY (`id`)
)
復(fù)制代碼

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

id biz_type max_id step version 1 101 1000 2000 0

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

update id_generator set max_id = {max_id+step}, version = version + 1
 where version =  {version} and biz_type = XX
復(fù)制代碼

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

5. 基于redis模式

Redis 也同樣可以實(shí)現(xiàn)，原理就是Redis 是單線程的，因此我們可以利用redis的incr命令實(shí)現(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
復(fù)制代碼

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

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

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

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

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

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

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

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

最后再判斷一下，當(dāng)前這臺(tái)機(jī)房的這臺(tái)機(jī)器上這一毫秒內(nèi)，這是第幾個(gè)請(qǐng)求，給這次生成 id 的請(qǐng)求累加一個(gè)序號(hào)，作為最后的 12 個(gè) bit。最終一個(gè) 64 個(gè) bit 的 id 就出來(lái)了，類似于：

這個(gè)算法可以保證一個(gè)機(jī)房的一臺(tái)機(jī)器在同一毫秒內(nèi)，生成了一個(gè)唯一的 id。可能一個(gè)毫秒內(nèi)會(huì)生成多個(gè) id，但是有最后 12 個(gè) bit 的序號(hào)來(lái)區(qū)分開來(lái)。

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

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

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

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

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

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

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

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

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

 /**
  * 機(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;

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

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

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

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

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

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

 /**
  * 構(gòu)造函數(shù)
  *
  * @param workerId     工作ID (0~31)
  * @param dataCenterId 機(jī)房中心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==========================================

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

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

  }

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

  //上次生成ID的時(shí)間截
  lastTimestamp = timestamp;

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

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

 /**
  * 返回以毫秒為單位的當(dāng)前時(shí)間
  * @return 當(dāng)前時(shí)間(毫秒)
  */
 private long timeGen()
 {
  return System.currentTimeMillis();
 }
}
復(fù)制代碼

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

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

SnowFlake算法的缺點(diǎn)：

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

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

7. 百度uid-generator

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

uid-generator需要與數(shù)據(jù)庫(kù)配合使用，需要新增一個(gè)WORKER_NODE表。當(dāng)應(yīng)用啟動(dòng)時(shí)會(huì)向數(shù)據(jù)庫(kù)表中去插入一條數(shù)據(jù)，插入成功后返回的自增ID就是該機(jī)器的workId數(shù)據(jù)由host，port組成。

由上圖可知，UidGenerator的時(shí)間部分只有28位，這就意味著UidGenerator默認(rèn)只能承受8.5年（2^28-1/86400/365）。當(dāng)然，根據(jù)你業(yè)務(wù)的需求，UidGenerator可以適當(dāng)調(diào)整delta seconds、worker node id和sequence占用位數(shù)。

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

DefaultUidGenerator

delta seconds 這個(gè)值是指當(dāng)前時(shí)間與epoch時(shí)間的時(shí)間差，且單位為秒。epoch時(shí)間就是指集成UidGenerator生成分布式ID服務(wù)第一次上線的時(shí)間，可配置，也一定要根據(jù)你的上線時(shí)間進(jìn)行配置，因?yàn)槟J(rèn)的epoch時(shí)間可是2016-09-20，不配置的話，會(huì)浪費(fèi)好幾年的可用時(shí)間。

worker id 接下來(lái)說(shuō)一下UidGenerator是如何給worker id賦值的，搭建UidGenerator的話，需要?jiǎng)?chuàng)建一個(gè)表：

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

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

• synchronized保證線程安全。
• 如果時(shí)間有任何的回?fù)埽敲粗苯訏伋霎惓！?/li>
• 如果當(dāng)前時(shí)間和上一次是同一秒時(shí)間，那么sequence自增。如果同一秒內(nèi)自增值超過(guò)2^13-1，那么就-- 會(huì)自旋等待下一秒（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);
    }
復(fù)制代碼

總結(jié) 通過(guò)DefaultUidGenerator的實(shí)現(xiàn)可知，它對(duì)時(shí)鐘回?fù)艿奶幚肀容^簡(jiǎn)單粗暴。另外如果使用UidGenerator的DefaultUidGenerator方式生成分布式ID，一定要根據(jù)你的業(yè)務(wù)的情況和特點(diǎn)，調(diào)整各個(gè)字段占用的位數(shù)：

<property name="timeBits" value="28"/>
<property name="workerBits" value="22"/>
<property name="seqBits" value="13"/>
<property name="epochStr" value="2016-09-20"/>
復(fù)制代碼

CachedUidGenerator

CachedUidGenerator是UidGenerator的重要改進(jìn)實(shí)現(xiàn)。它的核心利用了RingBuffer，如下圖所示，它本質(zhì)上是一個(gè)數(shù)組，數(shù)組中每個(gè)項(xiàng)被稱為slot。UidGenerator設(shè)計(jì)了兩個(gè)RingBuffer，一個(gè)保存唯一ID，一個(gè)保存flag。RingBuffer的尺寸是2^n，n必須是正整數(shù)：

?Ivm?^

具體細(xì)節(jié)閱讀Git源碼即可，可以直接通過(guò) SpringBoot 集成開發(fā)使用。

8. 美團(tuán)（Leaf）

Leaf由美團(tuán)開發(fā)，github地址：github.com/Meituan-Dia…，Leaf同時(shí)支持號(hào)段模式和snowflake算法模式，可以 切換使用。

號(hào)段模式

先導(dǎo)入源碼 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è)務(wù)key',
  `max_id` bigint(20) NOT NULL DEFAULT '1' COMMENT '當(dāng)前已經(jīng)分配了的最大id',
  `step` int(11) NOT NULL COMMENT '初始步長(zhǎng)，也是動(dòng)態(tài)調(diào)整的最小步長(zhǎng)',
  `description` varchar(256)  DEFAULT NULL COMMENT '業(yè)務(wù)key的描述',
  `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '數(shù)據(jù)庫(kù)維護(hù)的更新時(shí)間',
  PRIMARY KEY (`biz_tag`)
) ENGINE=InnoDB;
復(fù)制代碼

然后在項(xiàng)目中開啟號(hào)段模式，配置對(duì)應(yīng)的數(shù)據(jù)庫(kù)信息，并關(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=
復(fù)制代碼

啟動(dòng)leaf-server 模塊的 LeafServerApplication項(xiàng)目就跑起來(lái)了 號(hào)段模式獲取分布式自增ID的測(cè)試url ：http：//localhost：8080/api/segment/get/leaf-segment-test 監(jiān)控號(hào)段模式：http://localhost:8080/cache

snowflake模式

Leaf的snowflake模式依賴于ZooKeeper，不同于原始snowflake算法也主要是在workId的生成上，Leaf中workId是基于ZooKeeper的順序Id來(lái)生成的，每個(gè)應(yīng)用在使用Leaf-snowflake時(shí)，啟動(dòng)時(shí)都會(huì)都在Zookeeper中生成一個(gè)順序Id，相當(dāng)于一臺(tái)機(jī)器對(duì)應(yīng)一個(gè)順序節(jié)點(diǎn)，也就是一個(gè)workId。

leaf.snowflake.enable=true
leaf.snowflake.zk.address=127.0.0.1
leaf.snowflake.port=2181
復(fù)制代碼

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

9. 滴滴（Tinyid）

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

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

Tinyid教程 的原理非常簡(jiǎn)單，通過(guò)數(shù)據(jù)庫(kù)表中的數(shù)據(jù)基本是就能猜出個(gè)八九不離十，就是經(jīng)典的segment模式，和美團(tuán)的leaf原理幾乎一致。原理圖如下所示，以同一個(gè)bizType為例，每個(gè)tinyid-server會(huì)分配到不同的segment，例如第一個(gè)tinyid-server分配到(1000, 2000]，第二個(gè)tinyid-server分配到(2000, 3000]，第3個(gè)tinyid-server分配到(3000, 4000]：

再以第一個(gè)tinyid-server為例，當(dāng)它的segment用了20%（核心源碼：segmentId.setLoadingId(segmentId.getCurrentId().get() + idInfo.getStep() * Constants.LOADING_PERCENT / 100);，LOADING_PERCENT的值就是20），即設(shè)定loadingId為20%的閾值，例如當(dāng)前id是10000，步長(zhǎng)為10000，那么loadingId=12000。那么當(dāng)請(qǐng)求分布式ID分配到12001時(shí)（或者重啟后），即超過(guò)loadingId，就會(huì)返回一個(gè)特殊code：new Result(ResultCode.LOADING, id);tinyid-server根據(jù)ResultCode.LOADING這個(gè)響應(yīng)碼就會(huì)異步分配下一個(gè)segment(4000, 5000]，以此類推。

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