雪花算法(snowflak)生成有序不重復ID的Java實現(xiàn)代碼
更新時間：2024年11月13日 08:24:31 作者：草青工作室
雪花算法是一種分布式系統(tǒng)中生成唯一ID的方法,由41位時間戳、10位機器碼和12位序列號組成,具有唯一性、有序性和高效率等優(yōu)點,這篇文章主要介紹了雪花算法(snowflak)生成有序不重復ID的Java實現(xiàn)的相關(guān)資料,需要的朋友可以參考下
一、引言
雪花算法（Snowflake Algorithm）是一種在分布式系統(tǒng)中生成唯一ID的方法，最初由Twitter內(nèi)部使用。它生成的是一個64位的長整型（long）數(shù)字，由以下幾部分組成：
- 最高位是符號位，通常為0，因為ID通常是正數(shù)。
- 41位用于存儲毫秒級的時間戳，這部分不是存儲當前時間的時間戳，而是存儲時間戳的差值（當前時間戳 - 開始時間戳），可以支持大約69年的時間。
- 10位用于存儲機器碼，可以支持最多1024臺機器。如果在同一毫秒內(nèi)有多個請求到達同一臺機器，機器碼可以用于區(qū)分不同的請求。
- 12位用于存儲序列號，用于同一毫秒內(nèi)的多個請求，每臺機器每毫秒可以生成最多4096（0~4095）個ID。
雪花算法的優(yōu)點包括：
- 在高并發(fā)的分布式系統(tǒng)中，能夠保證ID的唯一性。
- 基于時間戳，ID基本上是有序遞增的。
- 不依賴于第三方庫或中間件，減少了系統(tǒng)復雜性。
- 生成ID的效率非常高。
二、雪花算法圖解
使用64位long類型生成的ID，以下是一個long類型二進制的分解結(jié)構(gòu)，如下：
|0000|0000|0000|0000|0000|0000|0000|0000|0000|0000|0000|0000|0000|0000|0000|0000| |-111|1111|1111|1111|1111|1111|1111|1111|1111|1111|11--|----|----|----|----|----| |----|----|----|----|----|----|----|----|----|----|--11|1111|1111|----|----|----| |----|----|----|----|----|----|----|----|----|----|----|----|----|1111|1111|1111|
便于區(qū)分各段代表的意思，把各段獨立在不同行中表示：
- 第一行：表示一個long類型，初始值是0L；
- 因為ID通常是正數(shù)，java中最高位是符號位，0表示正數(shù)1表示負數(shù)，所以此處為0。
- 第二行：41位用于存儲毫秒級的時間戳；
- 正常的時間戳不止41位，為了用固定位數(shù)表示更長時間，需要縮短時間戳長度，這里采用的是存儲時間戳的差值（當前時間戳 - 開始時間戳）；
- 41位可以表示的最大數(shù)是2^41-1=2,199,023,255,552，一年的毫秒數(shù)為：3600x1000x24x365=31,536,000,000；
- 用2,199,023,255,552/31,536,000,000=69.73,所以41毫秒級時間戳，最長可以表示69.73年；
- 開始時間戳設置為系統(tǒng)上線時間，這個ID可以連續(xù)使用69.73年，能滿足大多數(shù)業(yè)務系統(tǒng)要求；
- 第三行：10位用于存儲機器碼；
- 可以支持編號從0~1023的1024臺機器。如果在同一毫秒內(nèi)有多個請求到達同一臺機器，機器碼可以用于區(qū)分不同的請求。
- 第四行：12位用于存儲序列號；
- 用于同一毫秒內(nèi)的多個請求，每臺機器每毫秒可以生成最多4096（編號從0~4095）個ID。
三、41位毫秒級時間戳的計算
算法中支持1.5秒以內(nèi)的時間回撥，這里毫秒順序號溢出時的邏輯，也就是getTimestamp()這個方法，在參考網(wǎng)上寫的算法時，這個方法只寫了個等待，沒有返回值。等待結(jié)束后沒有對當前的變量賦值，導致生成的ID有重復現(xiàn)象。~~~邏輯問題最不好排查了-_-!!!
/** 業(yè)務系統(tǒng)上線的時間 2024-10-01 0:0:0，41位最多可以表示約69.7年 */
private static final long twepoch = 1727712000000L;
/**
* 生成下一個唯一的ID
*
* @return 下一個唯一的ID
* @throws RuntimeException 如果系統(tǒng)時鐘回退，則拋出RuntimeException異常
*/
public synchronized long nextId() {
long now = getTimestamp(); // 獲取時間戳
// 時鐘回退處理：如果當前時間小于上一次ID生成的時間戳
if (now < lastTimestamp) {
//最多支持1.5秒以內(nèi)的回撥（1500毫秒），否則拋出異常
long offset = lastTimestamp - now;
if(offset<=1500) {
try {
offset = offset<<2;//等待2兩倍的時間
Thread.sleep(offset);
now = getTimestamp();
//還是小，拋異常
if (now < lastTimestamp) {
throw new RuntimeException(String.format("時鐘回撥，無法生成ID %d milliseconds", lastTimestamp - now));
}
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
}
// 如果是同一時間生成的，則進行毫秒內(nèi)序列
if (lastTimestamp == now) {
//毫秒級順序號，使用掩碼4095取低12位的數(shù)，限制自增取值在1~4095之間，（掩碼4095表示二進制12位均為1的值，即：1111 1111 1111）
sequence = (sequence + 1) & 4095;
//溢出
if (sequence == 0) {
//毫秒內(nèi)序列溢出，等待到下一毫秒再繼續(xù)
now = getNextMillis(now);
}
} else {
//置0之前，序列號在同一時間并發(fā)后自增到這里說明時間不同了，版本號所以置0
sequence = 0;
}
lastTimestamp = now;
/*
* 長度64位，其中：
* 1位符號位，0正數(shù)，1負數(shù)
* 41位毫秒級時間戳，41111111111111111111111111111
* 10位機器ID，11 1111 1111
* 12位序列號，1111 1111 1111
* */
long id = ((now - twepoch) << 22) | (workerId << 12) | sequence;
return id;
}
四、10機器碼的生成
真對中間這10位機器碼，有些算法中分成了2段，前5位為數(shù)據(jù)中心ID，后5位為機器碼，最多只能表示31*31=961臺機器。
如果用10位都標識機器碼，可以最多從0~1023表示1024個機器，能夠表示更多的機器，還能減少邏輯的復雜度，所以我采用了10位機器碼的形式。
而且有些高并發(fā)的業(yè)務場景，在保證異地多活下部署模式下，一個機房31臺機器也真心不夠用。
真對機器碼生成有一個思路：
- 利用ZooKeeper數(shù)據(jù)模型中的順序節(jié)點作為ID編碼；
- 使用Redis對ID編碼；
- 基于數(shù)據(jù)庫表對ID編碼；
- 本地基于IP地址位ID編碼，下面實例采用的是這個方法；
/**
* workId使用IP生成
* @return workId
*/
private int getWorkId() {
try {
String hostAddress = SystemInfo.getHostAddress();
int[] ints = StringUtils.toCodePoints(hostAddress);
int sums = 0;
for (int b : ints) {
sums = sums + b;
}
return (sums % 1024);
} catch (UnknownHostException ex) {
ex.printStackTrace();
// 失敗就隨機生成
return RandomUtils.nextInt(0, 1024);
}
}
五、12位序列號的生成
生成12位序號用的主要是這段算法，可以代表0~4095共4096個數(shù)，也可以代表毫秒級最大4096個并發(fā)。
使用4095做為掩碼，對順序號做與操作，可以得到低12位的數(shù)值。
因為qequence上來就+1，所以如果數(shù)值為0就代表值溢出了。
溢出后就需要等待下一個毫秒，重新從0開始編號。
long now = getTimestamp(); // 獲取時間戳
// 如果是同一時間生成的，則進行毫秒內(nèi)序列
if (lastTimestamp == now) {
//毫秒級順序號，使用掩碼4095取低12位的數(shù)，限制自增取值在1~4095之間，（掩碼4095表示二進制12位均為1的值，即：1111 1111 1111）
sequence = (sequence + 1) & 4095;
//溢出
if (sequence == 0) {
//毫秒內(nèi)序列溢出，等待到下一毫秒再繼續(xù)
now = getNextMillis(now);
}
} else {
//置0之前，序列號在同一時間并發(fā)后自增到這里說明時間不同了，版本號所以置0
sequence = 0;
}
lastTimestamp = now;
六、雪花算法ID最后組裝
使用了按位左移操作，最終將時間戳差值、機器碼、順序號，三個值合并到一個long中。
這個算法有個好處是，可以把ID解碼，得到時間、機器碼和順序號。
/* * 長度64位，其中： * 1位符號位，0正數(shù)，1負數(shù) * 41位毫秒級時間戳，41111111111111111111111111111 * 10位機器ID，11 1111 1111 * 12位序列號，1111 1111 1111 * */ long id = ((now - twepoch) << 22) | (workerId << 12) | sequence;
七、雪花算法ID解碼
使用了按位右移操作，將時間戳差值、機器碼、順序號，三個值從long中，拆分出來。
輸出的結(jié)果是：id:7778251575992320 -> time:1854479688 req:0 wid:584 2024-10-22 11:07:59.688
/** 業(yè)務系統(tǒng)上線的時間 2024-10-01 0:0:0，41位最多可以表示約69.7年 */
private static final long twepoch = 1727712000000L;
/**
* 將長整型ID解碼為字符串格式
*
* @param id 需要解碼的長整型ID
* @return 解碼后的字符串，格式為"時間戳\t序列號\t工作機ID\t中心ID"
*/
public static String idDecode(long id) {
long sequence = id & 4095; //取低12位的數(shù)
long workerId = (id >> 10) & 1023;//左移后取低10位的數(shù)
long time = (id >> 22); //左移后取低41位的數(shù)
return MessageFormat.format("time:{0,number,#}\treq:{1}\twid:{2}\t{3}"
, time
, sequence
, workerId
, getDataTime(time));
}
private static String getDataTime(long timeInterval) {
var timestamp = twepoch+timeInterval;
var date = new Date(timestamp);
SimpleDateFormat format = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
var dtStr = format.format(date);
return dtStr;
}
八、完整的ID生成類
import org.apache.commons.lang3.RandomUtils;
import org.apache.commons.lang3.StringUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.net.UnknownHostException;
import java.text.MessageFormat;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.concurrent.atomic.AtomicLong;
public class SnowflakeIdUtil {
private static Logger logger = LoggerFactory.getLogger(SnowflakeIdUtil.class.getName());
/** 業(yè)務系統(tǒng)上線的時間 2024-10-01 0:0:0，41位最多可以表示約69.7年 */
private static final long twepoch = 1727712000000L;
/** 毫秒內(nèi)序列 */
private long sequence = 0L;
/** 機器ID */
private int workerId;
/** 上次生成ID的時間戳 */
private long lastTimestamp = -1L;
private volatile static SnowflakeIdUtil instance = null;
public void setWorkerId(int workerId) {
if (workerId > 1023 || workerId < 0)
throw new IllegalArgumentException("workerId must be between 0 and 1023");
this.workerId = workerId;
}
/**
* SnowflakeIdUtil 類的構(gòu)造函數(shù)
*
* @throws IllegalArgumentException 如果傳入的 workerId 或 datacenterId 不在 0 到 31 的范圍內(nèi)，則拋出此異常
*/
private SnowflakeIdUtil() {
workerId = getWorkId();
}
/**
* 獲取 SnowflakeIdUtil 的單例對象。
* 此方法首先獲取工作機器ID和數(shù)據(jù)中心ID，然后使用這兩個ID調(diào)用另一個 getInstance 方法來獲取 SnowflakeIdUtil 的單例對象。
* @return 返回 SnowflakeIdUtil 的單例對象。
*/
public static SnowflakeIdUtil getInstance() {
if (instance == null) {
synchronized (SnowflakeIdUtil.class) {
if (instance == null) {
instance = new SnowflakeIdUtil();
}
}
}
return instance;
}
/**
* workId使用IP生成
* @return workId
*/
private int getWorkId() {
try {
String hostAddress = SystemInfo.getHostAddress();
int[] ints = StringUtils.toCodePoints(hostAddress);
int sums = 0;
for (int b : ints) {
sums = sums + b;
}
return (sums % 1024);
} catch (UnknownHostException ex) {
ex.printStackTrace();
// 失敗就隨機生成
return RandomUtils.nextInt(0, 1024);
}
}
/**
* 生成下一個唯一的ID
*
* @return 下一個唯一的ID
* @throws RuntimeException 如果系統(tǒng)時鐘回退，則拋出RuntimeException異常
*/
public synchronized long nextId() {
long now = getTimestamp(); // 獲取時間戳
// 時鐘回退處理：如果當前時間小于上一次ID生成的時間戳
if (now < lastTimestamp) {
//最多支持1.5秒以內(nèi)的回撥（1500毫秒），否則拋出異常
long offset = lastTimestamp - now;
if(offset<=1500) {
try {
offset = offset<<2;//等待2兩倍的時間
Thread.sleep(offset);
now = getTimestamp();
//還是小，拋異常
if (now < lastTimestamp) {
throw new RuntimeException(String.format("時鐘回撥，無法生成ID %d milliseconds", lastTimestamp - now));
}
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
}
// 如果是同一時間生成的，則進行毫秒內(nèi)序列
if (lastTimestamp == now) {
//毫秒級順序號，使用掩碼4095取低12位的數(shù)，限制自增取值在1~4095之間，（掩碼4095表示二進制12位均為1的值，即：1111 1111 1111）
sequence = (sequence + 1) & 4095;
//溢出
if (sequence == 0) {
//毫秒內(nèi)序列溢出，等待到下一毫秒再繼續(xù)
now = getNextMillis(now);
}
} else {
//置0之前，序列號在同一時間并發(fā)后自增到這里說明時間不同了，版本號所以置0
sequence = 0;
}
lastTimestamp = now;
/*
* 長度64位，其中：
* 1位符號位，0正數(shù)，1負數(shù)
* 41位毫秒級時間戳，41111111111111111111111111111
* 10位機器ID，11 1111 1111
* 12位序列號，1111 1111 1111
* */
long id = ((now - twepoch) << 22) | (workerId << 12) | sequence;
return id;
}
/**
* 將長整型ID解碼為字符串格式
*
* @param id 需要解碼的長整型ID
* @return 解碼后的字符串，格式為"時間戳\t序列號\t工作機ID\t中心ID"
*/
public static String idDecode(long id) {
long sequence = id & 4095; //取低12位的數(shù)
long workerId = (id >> 10) & 1023;//左移后取低10位的數(shù)
long time = (id >> 22); //左移后取低41位的數(shù)
return MessageFormat.format("time:{0,number,#}\treq:{1}\twid:{2}\t{3}"
, time
, sequence
, workerId
, getDataTime(time));
}
private static String getDataTime(long timeInterval) {
var timestamp = twepoch+timeInterval;
var date = new Date(timestamp);
SimpleDateFormat format = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
var dtStr = format.format(date);
return dtStr;
}
protected long getTimestamp() {
return System.currentTimeMillis();
}
// 等待下一個毫秒,直到獲得新的時間戳
protected long getNextMillis(long lastTimestamp) {
//logger.info("wait until next millis : "+lastTimestamp);
long timestamp = getTimestamp();
while (timestamp <= lastTimestamp) {
timestamp = getTimestamp();
}
return timestamp;
}
}九、多線程測試用例
import org.apache.commons.lang3.StringUtils;
import org.junit.jupiter.api.Test;
import org.openjdk.jmh.runner.RunnerException;
import org.springframework.util.Assert;
import java.text.MessageFormat;
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;
import java.util.UUID;
import java.util.concurrent.ConcurrentHashMap;
public class IdUtilTest {
/**
* 測試SnowflakeId生成器的并發(fā)性能
*
* @throws InterruptedException 如果線程在等待時被中斷，則拋出InterruptedException異常
*/
@Test
public void snowflakTest() throws InterruptedException {
var trehadCount = 30;
var loopCount = 100000;
var debug = true;
var unique = new ConcurrentHashMap<Long,String>();
var duplicates = new TreeMap<Long,String>();
System.out.println("線程："+trehadCount+"\t每個線程循環(huán)次數(shù)："+loopCount+"");
Runnable runnable = () -> {
var start = System.currentTimeMillis();
for(int i = 0; i < loopCount; i++) {
var id = SnowflakeIdUtil.getInstance().nextId();
if(debug) {
if (unique.containsKey(id)) {
duplicates.put(id, Thread.currentThread().getName());
} else {
unique.put(id, Thread.currentThread().getName());
}
}
}
var timecost = System.currentTimeMillis() - start;
System.out.println(timecost+"\t"+Thread.currentThread().getName());
};
List<Thread> threads = new ArrayList<>();
for(int i = 0; i < trehadCount; i++) {
Thread thread = new Thread(runnable);
threads.add(thread);
}
for(Thread thread : threads) {
thread.start();
thread.join();
}
System.out.println("---------------------------- 統(tǒng)計結(jié)果");
System.out.println("計劃生成個數(shù)："+trehadCount*loopCount);
System.out.println("不重復ID個數(shù)："+unique.size());
System.out.println("重復ID個數(shù)："+duplicates.size());
System.out.println("---------------------------- 重復ID");
for(var id : duplicates.keySet()) {
System.out.println(MessageFormat.format("id:{0}\t->\t| DECODE:{1}\t| thread:{2}\t{3}"
,id
,SnowflakeIdUtil.idDecode(id)
,unique.get(id)
,duplicates.get(id)));
}
Assert.isTrue(duplicates.size() == 0, "重復ID個數(shù)不為0");
}
@Test
public void snowflakIdDecodTest(){
for(var i=0;i<100;i++){
var id = SnowflakeIdUtil.getInstance().nextId();
var idDecode = SnowflakeIdUtil.idDecode(id);
System.out.println("id:" + id+"\t->\t"+idDecode);
}
}
}十、看下測試結(jié)果
30個并發(fā)生成300萬個ID，耗時1356毫秒，性能優(yōu)于300個UUID的生成。
線程：30 每個線程循環(huán)次數(shù)：100000 185 Thread-0 63 Thread-1 26 Thread-2 57 Thread-3 25 Thread-4 26 Thread-5 24 Thread-6 103 Thread-7 55 Thread-8 26 Thread-9 35 Thread-10 25 Thread-11 25 Thread-12 25 Thread-13 26 Thread-14 135 Thread-15 25 Thread-16 25 Thread-17 42 Thread-18 27 Thread-19 25 Thread-20 26 Thread-21 25 Thread-22 40 Thread-23 49 Thread-24 50 Thread-25 27 Thread-26 75 Thread-27 32 Thread-28 27 Thread-29 ---------------------------- 統(tǒng)計結(jié)果 計劃生成個數(shù)：3000000 不重復ID個數(shù)：3000000 重復ID個數(shù)：0 ---------------------------- 重復ID
總結(jié)
在后端系統(tǒng)中，使用64位long類型的ID通常不會遇到問題。但是，考慮到當前大多數(shù)服務都是Web應用，與JavaScript的交互變得極為普遍。JavaScript在處理整數(shù)時存在一個重要的限制：它能夠精確表示的最大整型數(shù)值為53位。當數(shù)值超出這個范圍時，JavaScript會出現(xiàn)精度丟失的問題。
因此，在設計系統(tǒng)時，我們必須確保ID長度不超過53位，以便JavaScript能夠直接且無誤地處理這些數(shù)值。如果ID長度超過了53位，我們必須將這些數(shù)值轉(zhuǎn)換為字符串格式，這樣才能在JavaScript中正確處理。這種轉(zhuǎn)換無疑會增加API接口的復雜度，因此在系統(tǒng)設計和開發(fā)時，我們需要對此進行周密的考慮。
為了在不轉(zhuǎn)換的情況下將Long類型ID傳遞到前端，我們可以采用53位的雪花算法。這種算法將ID分為三個部分：32位的秒級時間戳、16位的自增值和5位的機器標識。這樣的組合可以支持32臺機器每秒生成65535個序列號，從而滿足大多數(shù)系統(tǒng)的需求。
如果仍然需要使用63位的ID，我們可以在數(shù)據(jù)庫中將ID保存為varchar(64)類型的字符串，或者在實體對象中添加一個字符串類型的ID字段。在將數(shù)據(jù)返回給前端之前，我們可以直接提供這個字符串ID值，從而避免JavaScript處理整數(shù)時的精度問題。這樣的設計既保證了數(shù)據(jù)的完整性，又簡化了前端處理的復雜性。
到此這篇關(guān)于雪花算法(snowflak)生成有序不重復ID的Java實現(xiàn)的文章就介紹到這了,更多相關(guān)Java生成有序不重復ID內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
相關(guān)文章
java實現(xiàn)批量導入Excel表格數(shù)據(jù)到數(shù)據(jù)庫
這篇文章主要為大家詳細介紹了java實現(xiàn)批量導入Excel表格數(shù)據(jù)到數(shù)據(jù)庫，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-08-08
這篇文章主要介紹了JAVA 原型模式的的相關(guān)資料，文中講解非常細致，實例幫助大家更好的理解和學習，感興趣的朋友可以了解下2021-09-09
java基于雙向環(huán)形鏈表解決丟手帕問題的方法示例
這篇文章主要介紹了java基于雙向環(huán)形鏈表解決丟手帕問題的方法,簡單描述了丟手帕問題,并結(jié)合實例形式給出了Java基于雙向環(huán)形鏈表解決丟手帕問題的步驟與相關(guān)操作技巧,需要的朋友可以參考下2017-11-11
SpringBoot優(yōu)雅地實現(xiàn)全局異常處理的方法詳解
這篇文章主要為大家詳細介紹了SpringBoot如何優(yōu)雅地實現(xiàn)全局異常處理，文中的示例代碼講解詳細，感興趣的小伙伴可以跟隨小編一起學習一下2022-08-08
下面小編就為大家?guī)硪黄狫ava簡單從文件讀取和輸出的實例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-09-09
SpringBoot Web開發(fā)之系統(tǒng)任務啟動與路徑映射和框架整合
這篇文章主要介紹了SpringBoot Web開發(fā)中的系統(tǒng)任務啟動與路徑映射和Servlet、Filter、Listener框架整合，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-08-08
Springboot中登錄后關(guān)于cookie和session攔截問題的案例分析
這篇文章主要介紹了Springboot中登錄后關(guān)于cookie和session攔截案例,本文通過實例圖文相結(jié)合給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-08-08
本篇文章主要介紹了SpringBoot項目中使用AOP的方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-02-02
這篇文章主要為大家詳細介紹了java組件fileupload文件上傳demo ,具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-10-10
這篇文章主要介紹了Redis集群與SSM整合使用方法，非常不錯，具有參考借鑒價值,需要的朋友可以參考下2017-12-12