分散式唯一ID的幾種生成方案

08-21

分散式唯一ID的幾種生成方案

來自專欄 Java高級開發交流

前言

在互聯網的業務系統中，涉及到各種各樣的ID，如在支付系統中就會有支付ID、退款ID等。那一般生成ID都有哪些解決方案呢？特別是在複雜的分散式系統業務場景中，我們應該採用哪種適合自己的解決方案是十分重要的。下面我們一一來列舉一下，不一定全部適合，這些解決方案僅供你參考，或許對你有用。

正文

分散式ID的特性

唯一性：確保生成的ID是全網唯一的。
有序遞增性：確保生成的ID是對於某個用戶或者業務是按一定的數字有序遞增的。
高可用性：確保任何時候都能正確的生成ID。
帶時間：ID裡面包含時間，一眼掃過去就知道哪天的交易。

分散式ID的生成方案

1. UUID

演算法的核心思想是結合機器的網卡、當地時間、一個隨記數來生成UUID。

優點：本地生成，生成簡單，性能好，沒有高可用風險
缺點：長度過長，存儲冗餘，且無序不可讀，查詢效率低

2. 資料庫自增ID

使用資料庫的id自增策略，如 MySQL 的 auto_increment。並且可以使用兩台資料庫分別設置不同步長，生成不重複ID的策略來實現高可用。

優點：資料庫生成的ID絕對有序，高可用實現方式簡單
缺點：需要獨立部署資料庫實例，成本高，有性能瓶頸

3. 批量生成ID

一次按需批量生成多個ID，每次生成都需要訪問資料庫，將資料庫修改為最大的ID值，並在內存中記錄當前值及最大值。

優點：避免了每次生成ID都要訪問資料庫並帶來壓力，提高性能
缺點：屬於本地生成策略，存在單點故障，服務重啟造成ID不連續

4. Redis生成ID

Redis的所有命令操作都是單線程的，本身提供像 incr 和 increby 這樣的自增原子命令，所以能保證生成的 ID 肯定是唯一有序的。

優點：不依賴於資料庫，靈活方便，且性能優於資料庫；數字ID天然排序，對分頁或者需要排序的結果很有幫助。
缺點：如果系統中沒有Redis，還需要引入新的組件，增加系統複雜度；需要編碼和配置的工作量比較大。

考慮到單節點的性能瓶頸，可以使用 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 集群也可以方式單點故障的問題。

另外，比較適合使用 Redis 來生成每天從0開始的流水號。比如訂單號 = 日期 + 當日自增長號。可以每天在 Redis 中生成一個 Key ，使用 INCR 進行累加。

5. Twitter的snowflake演算法

Twitter 利用 zookeeper 實現了一個全局ID生成的服務 Snowflake

如上圖的所示，Twitter 的 Snowflake 演算法由下面幾部分組成：

1位符號位：

由於 long 類型在 java 中帶符號的，最高位為符號位，正數為 0，負數為 1，且實際系統中所使用的ID一般都是正數，所以最高位為 0。

41位時間戳（毫秒級）：

需要注意的是此處的 41 位時間戳並非存儲當前時間的時間戳，而是存儲時間戳的差值（當前時間戳 - 起始時間戳），這裡的起始時間戳一般是ID生成器開始使用的時間戳，由程序來指定，所以41位毫秒時間戳最多可以使用 (1 << 41) / (1000x60x60x24x365) = 69年。

10位數據機器位：

包括5位數據標識位和5位機器標識位，這10位決定了分散式系統中最多可以部署 1 << 10 = 1024 s個節點。超過這個數量，生成的ID就有可能會衝突。

12位毫秒內的序列：

這 12 位計數支持每個節點每毫秒（同一台機器，同一時刻）最多生成 1 << 12 = 4096個ID

加起來剛好64位，為一個Long型。

優點：高性能，低延遲，按時間有序，一般不會造成ID碰撞
缺點：需要獨立的開發和部署，依賴於機器的時鐘

簡單實現

public class IdWorker {
/**
* 起始時間戳 2017-04-01
*/
private final long epoch = 1491004800000L;
/**

* 機器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 = ~(-1 << 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(12+5+5)位
*/

private final long timestampShift = sequenceBits + workerIdBits + dataCenterIdBits;
/**
* 生成序列的掩碼，這裡為4095 (0b111111111111=0xfff=4095)
*/
private final long sequenceMask = ~(-1L << sequenceBits);
/**
* 數據標識ID（0～31）
*/
private long dataCenterId;
/**

* 機器ID（0～31）
*/
private long workerId;
/**
* 毫秒內序列（0～4095）
*/
private long sequence;
/**
* 上次生成ID的時間戳
*/

private long lastTimestamp = -1L;
public IdWorker(long dataCenterId, long workerId) {
if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
throw new IllegalArgumentException(String.format("dataCenterId cant be greater than %d or less than 0", maxDataCenterId));
}
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("worker Id cant be greater than %d or less than 0", maxWorkerId));
}
this.dataCenterId = dataCenterId;
this.workerId = workerId;
}
/**
* 獲得下一個ID (該方法是線程安全的)
* @return snowflakeId
*/
public synchronized long nextId() {
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 (timestamp == lastTimestamp) {
sequence = (sequence + 1) & sequenceMask;
//毫秒內序列溢出
if (sequence == 0) {
//阻塞到下一個毫秒,獲得新的時間戳
timestamp = nextMillis(lastTimestamp);
}
} else {//時間戳改變，毫秒內序列重置
sequence = 0L;
}
lastTimestamp = timestamp;
//移位並通過按位或運算拼到一起組成64位的ID
return ((timestamp - epoch) << timestampShift) |
(dataCenterId << dataCenterIdShift) |
(workerId << workerIdShift) |
sequence;
}
/**
* 返回以毫秒為單位的當前時間
* @return 當前時間(毫秒)
*/
protected long timeGen() {
return System.currentTimeMillis();
}
/**
* 阻塞到下一個毫秒，直到獲得新的時間戳
* @param lastTimestamp 上次生成ID的時間截
* @return 當前時間戳
*/
protected long nextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = lastTimestamp;
}
return timestamp;
}
}

6. 百度UidGenerator

UidGenerator是百度開源的分散式ID生成器，基於於snowflake演算法的實現，看起來感覺還行。不過，國內開源的項目維護性真是擔憂。

7. 美團Leaf

Leaf 是美團開源的分散式ID生成器，能保證全局唯一性、趨勢遞增、單調遞增、信息安全，裡面也提到了幾種分散式方案的對比，但也需要依賴關係資料庫、Zookeeper等中間件。

小結

這篇文章和大家分享了全局id生成服務的幾種常用方案，同時對比了各自的優缺點和適用場景。在實際工作中，大家可以結合自身業務和系統架構體系進行合理選型。

希望篇文章可以幫助在這個行業發展的朋友和童鞋們，在論壇博客等地方少花些時間找資料，把有限的時間，真正花在學習上，有需要幫助或資料的朋友可以加Q號：625452324相信對於已經工作和遇到技術瓶頸或者寫博客碼友，都會有好的幫助。