分布式 ID的 9 種生成方式

一、為什么要用分布式 ID？

在說分布式 ID 的具體實現之前，我們來簡單分析一下為什么用分布式 ID？分布式 ID 應該滿足哪些特征？

1、什么是分布式 ID？

拿 MySQL 數據庫舉個栗子：

在我們業務數據量不大的時候，單庫單表完全可以支撐現有業務，數據再大一點搞個 MySQL 主從同步讀寫分離也能對付。

但隨著數據日漸增長，主從同步也扛不住了，就需要對數據庫進行分庫分表，但分庫分表后需要有一個唯一 ID 來標識一條數據，數據庫的自增 ID 顯然不能滿足需求；特別一點的如訂單、優惠券也都需要有唯一 ID做標識。此時一個能夠生成全局唯一 ID的系統是非常必要的。那么這個全局唯一 ID就叫分布式 ID。

2、那么分布式 ID 需要滿足那些條件？

全局唯一：必須保證 ID 是全局性唯一的，基本要求
高性能：高可用低延時，ID 生成響應要塊，否則反倒會成為業務瓶頸
高可用：100%的可用性是騙人的，但是也要無限接近于 100%的可用性
好接入：要秉著拿來即用的設計原則，在系統設計和實現上要盡可能的簡單
趨勢遞增：最好趨勢遞增，這個要求就得看具體業務場景了，一般不嚴格要求

分布式 ID 都有哪些生成方式？

今天主要分析一下以下 9 種，分布式 ID 生成器方式以及優缺點：

UUID
數據庫自增 ID
數據庫多主模式
號段模式
Redis
雪花算法（SnowFlake）
滴滴出品（TinyID）
百度（Uidgenerator）
美團（Leaf）

那么它們都是如何實現？以及各自有什么優缺點？

1、基于 UUID

在 Java 的世界里，想要得到一個具有唯一性的 ID，首先被想到可能就是UUID，畢竟它有著全球唯一的特性。那么UUID可以做分布式 ID嗎？答案是可以的，但是并不推薦！

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

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

優點：

生成足夠簡單，本地生成無網絡消耗，具有唯一性

缺點：

無序的字符串，不具備趨勢自增特性
沒有具體的業務含義
長度過長 16 字節 128 位，36 位長度的字符串，存儲以及查詢對 MySQL 的性能消耗較大，MySQL 官方明確建議主鍵要盡量越短越好，作為數據庫主鍵?UUID?的無序性會導致數據位置頻繁變動，嚴重影響性能。

2、基于數據庫自增 ID

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

CREATE DATABASE `SEQ_ID`;
CREATE TABLE SEQID.SEQUENCE_ID (id bigint(20) unsigned NOT NULL auto_increment, value char(10) NOT NULL default '',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 擴容增加節點，這是一個比較麻煩的事。

水平擴展的數據庫集群，有利于解決數據庫單點壓力的問題，同時為了 ID 生成特性，將自增步長按照機器數量來設置。

增加第三臺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`)
)

biz_type ：代表不同業務類型

max_id ：當前最大的可用 id

step ：代表號段的長度

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 = XXX

由于多業務端可能同時操作，所以采用版本號version樂觀鎖方式更新，這種分布式 ID生成方式不強依賴于數據庫，不會頻繁的訪問數據庫，對數據庫的壓力小很多。

5、基于 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

RDB會定時打一個快照進行持久化，假如連續自增但redis沒及時持久化，而這會 Redis 掛掉了，重啟 Redis 后會出現 ID 重復的情況。
AOF會對每條寫命令進行持久化，即使Redis掛掉了也不會出現 ID 重復的情況，但由于 incr 命令的特殊性，會導致Redis重啟恢復的數據時間過長。

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

雪花算法（Snowflake）是 twitter 公司內部分布式項目采用的 ID 生成算法，開源后廣受國內大廠的好評，在該算法影響下各大公司相繼開發出各具特色的分布式生成器。

Snowflake生成的是 Long 類型的 ID，一個 Long 類型占 8 個字節，每個字節占 8 比特，也就是說一個 Long 類型占 64 個比特。

Snowflake ID 組成結構：正數位（占 1 比特）+?時間戳（占 41 比特）+?機器 ID（占 5 比特）+?數據中心（占 5 比特）+?自增值（占 12 比特），總共 64 比特組成的一個 Long 類型。

第一個 bit 位（1bit）：Java 中 long 的最高位是符號位代表正負，正數是 0，負數是 1，一般生成 ID 都為正數，所以默認為 0。
時間戳部分（41bit）：毫秒級的時間，不建議存當前時間戳，而是用（當前時間戳 - 固定開始時間戳）的差值，可以使產生的 ID 從更小的值開始；41 位的時間戳可以使用 69 年，(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69 年
工作機器 id（10bit）：也被叫做workId，這個可以靈活配置，機房或者機器號組合都可以。
序列號部分（12bit），自增值支持同一毫秒內同一個節點可以生成 4096 個 ID

根據這個算法的邏輯，只需要將這個算法用 Java 語言實現出來，封裝為一個工具方法，那么各個業務應用可以直接使用該工具方法來獲取分布式 ID，只需保證每個業務應用有自己的工作機器 id 即可，而不需要單獨去搭建一個獲取分布式 ID 的應用

Java 版本的Snowflake算法實現：

/*** Twitter 的 SnowFlake 算法,使用 SnowFlake 算法生成一個整數，然后轉化為 62 進制變成一個短地址 URL** https://github.com/beyondfengyu/SnowFlake*/
public class SnowFlakeShortUrl {/*** 起始的時間戳*/private final static long START_TIMESTAMP = 1480166465631L;/*** 每一部分占用的位數*/private final static long SEQUENCE_BIT = 12;   //序列號占用的位數private final static long MACHINE_BIT = 5;     //機器標識占用的位數private final static long DATA_CENTER_BIT = 5; //數據中心占用的位數/*** 每一部分的最大值*/private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);private final static long MAX_DATA_CENTER_NUM = -1L ^ (-1L << DATA_CENTER_BIT);/*** 每一部分向左的位移*/private final static long MACHINE_LEFT = SEQUENCE_BIT;private final static long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;private final static long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT;private long dataCenterId;  //數據中心private long machineId;     //機器標識private long sequence = 0L; //序列號private long lastTimeStamp = -1L;  //上一次時間戳private long getNextMill() {long mill = getNewTimeStamp();while (mill <= lastTimeStamp) {mill = getNewTimeStamp();}return mill;}private long getNewTimeStamp() {return System.currentTimeMillis();}/*** 根據指定的數據中心 ID 和機器標志 ID 生成指定的序列號** @param dataCenterId 數據中心 ID* @param machineId    機器標志 ID*/public SnowFlakeShortUrl(long dataCenterId, long machineId) {if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) {throw new IllegalArgumentException("DtaCenterId can't be greater than MAX_DATA_CENTER_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 currTimeStamp = getNewTimeStamp();if (currTimeStamp < lastTimeStamp) {throw new RuntimeException("Clock moved backwards.  Refusing to generate id");}if (currTimeStamp == lastTimeStamp) {//相同毫秒內，序列號自增sequence = (sequence + 1) & MAX_SEQUENCE;//同一毫秒的序列數已經達到最大if (sequence == 0L) {currTimeStamp = getNextMill();}} else {//不同毫秒內，序列號置為 0sequence = 0L;}lastTimeStamp = currTimeStamp;return (currTimeStamp - START_TIMESTAMP) << TIMESTAMP_LEFT //時間戳部分| dataCenterId << DATA_CENTER_LEFT       //數據中心部分| machineId << MACHINE_LEFT             //機器標識部分| sequence;                             //序列號部分}public static void main(String[] args) {SnowFlakeShortUrl snowFlake = new SnowFlakeShortUrl(2, 3);for (int i = 0; i < (1 << 4); i++) {//10 進制System.out.println(snowFlake.nextId());}}
}

7、百度（uid-generator）

uid-generator是由百度技術部開發，項目 GitHub 地址 https://github.com/baidu/uid-generator

uid-generator是基于Snowflake算法實現的，與原始的snowflake算法不同在于，uid-generator支持自定義時間戳、工作機器 ID和?序列號?等各部分的位數，而且uid-generator中采用用戶自定義workId的生成策略。

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

對于uid-generator?ID 組成結構：

workId，占用了 22 個 bit 位，時間占用了 28 個 bit 位，序列化占用了 13 個 bit 位，需要注意的是，和原始的snowflake不太一樣，時間的單位是秒，而不是毫秒，workId也不一樣，而且同一應用每次重啟就會消費一個workId。

參考文獻 https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

8、美團（Leaf）

Leaf由美團開發，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 '業務 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=rootleaf.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 地址：https://github.com/didi/tinyid。

Tinyid是基于號段模式原理實現的與Leaf如出一轍，每個服務獲取一個號段（1000,2000]、（2000,3000]、（3000,4000] 在這里插入圖片描述 ?Tinyid提供http和tinyid-client兩種方式接入

Http 方式接入

（1）導入 Tinyid 源碼：

git clone https://github.com/didi/tinyid.git

（2）創建數據表：

CREATE TABLE `tiny_id_info` (`id` bigint(20) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增主鍵',`biz_type` varchar(63) NOT NULL DEFAULT '' COMMENT '業務類型，唯一',`begin_id` bigint(20) NOT NULL DEFAULT '0' COMMENT '開始 id，僅記錄初始值，無其他含義。初始化時 begin_id 和 max_id 應相同',`max_id` bigint(20) NOT NULL DEFAULT '0' COMMENT '當前最大 id',`step` int(11) DEFAULT '0' COMMENT '步長',`delta` int(11) NOT NULL DEFAULT '1' COMMENT '每次 id 增量',`remainder` int(11) NOT NULL DEFAULT '0' COMMENT '余數',`create_time` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '創建時間',`update_time` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '更新時間',`version` bigint(20) NOT NULL DEFAULT '0' COMMENT '版本號',PRIMARY KEY (`id`),UNIQUE KEY `uniq_biz_type` (`biz_type`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8 COMMENT 'id 信息表';CREATE TABLE `tiny_id_token` (`id` int(11) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增 id',`token` varchar(255) NOT NULL DEFAULT '' COMMENT 'token',`biz_type` varchar(63) NOT NULL DEFAULT '' COMMENT '此 token 可訪問的業務類型標識',`remark` varchar(255) NOT NULL DEFAULT '' COMMENT '備注',`create_time` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '創建時間',`update_time` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '更新時間',PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8 COMMENT 'token 信息表';INSERT INTO `tiny_id_info` (`id`, `biz_type`, `begin_id`, `max_id`, `step`, `delta`, `remainder`, `create_time`, `update_time`, `version`)
VALUES(1, 'test', 1, 1, 100000, 1, 0, '2018-07-21 23:52:58', '2018-07-22 23:19:27', 1);INSERT INTO `tiny_id_info` (`id`, `biz_type`, `begin_id`, `max_id`, `step`, `delta`, `remainder`, `create_time`, `update_time`, `version`)
VALUES(2, 'test_odd', 1, 1, 100000, 2, 1, '2018-07-21 23:52:58', '2018-07-23 00:39:24', 3);INSERT INTO `tiny_id_token` (`id`, `token`, `biz_type`, `remark`, `create_time`, `update_time`)
VALUES(1, '0f673adf80504e2eaa552f5d791b644c', 'test', '1', '2017-12-14 16:36:46', '2017-12-14 16:36:48');INSERT INTO `tiny_id_token` (`id`, `token`, `biz_type`, `remark`, `create_time`, `update_time`)
VALUES(2, '0f673adf80504e2eaa552f5d791b644c', 'test_odd', '1', '2017-12-14 16:36:46', '2017-12-14 16:36:48');

（3）配置數據庫：

datasource.tinyid.names=primary
datasource.tinyid.primary.driver-class-name=com.mysql.jdbc.Driver
datasource.tinyid.primary.url=jdbc:mysql://ip:port/databaseName?autoReconnect=true&useUnicode=true&characterEncoding=UTF-8
datasource.tinyid.primary.username=root
datasource.tinyid.primary.password=123456

（4）啟動tinyid-server后測試

獲取分布式自增 ID: http://localhost:9999/tinyid/id/nextIdSimple?bizType=test&token=0f673adf80504e2eaa552f5d791b644c'
返回結果: 3批量獲取分布式自增 ID:
http://localhost:9999/tinyid/id/nextIdSimple?bizType=test&token=0f673adf80504e2eaa552f5d791b644c&batchSize=10'
返回結果:  4,5,6,7,8,9,10,11,12,13

Java 客戶端方式接入

重復 Http 方式的（2）（3）操作

引入依賴

       <dependency><groupId>com.xiaoju.uemc.tinyid</groupId><artifactId>tinyid-client</artifactId><version>${tinyid.version}</version></dependency>

配置文件

tinyid.server =localhost:9999
tinyid.token =0f673adf80504e2eaa552f5d791b644c

test?、tinyid.token是在數據庫表中預先插入的數據，test?是具體業務類型，tinyid.token表示可訪問的業務類型

// 獲取單個分布式自增 ID
Long id =  TinyId . nextId( " test " );// 按需批量分布式自增 ID
List< Long > ids =  TinyId . nextId( " test " , 10 );