常見 ID 生成算法
分布式系統(tǒng)中属韧，經(jīng)常需要使用 ID 作為數(shù)據(jù)唯一標(biāo)識(shí)楼镐，這時(shí)數(shù)據(jù)庫自增就無法滿足需求忿族。常見的解決方案有：
- UUID：實(shí)現(xiàn)簡(jiǎn)單扼劈，但 32 位無序字符串驻啤，性能較差
- 分庫起始步長(zhǎng)：嚴(yán)重依賴數(shù)據(jù)庫
- SnowFlake：無依賴，64 bit 標(biāo)識(shí)荐吵，有序遞增
SnowFlake
SnowFlake 是 Twitter 公司所采用的的一種算法骑冗，目的是在分布式系統(tǒng)中生成全局唯一且趨勢(shì)遞增的 ID。
SnowFlake 生成的 ID 一共可分為 4 部分：
- 符號(hào)位
1 bit先煎，始終為 0贼涩； - 時(shí)間戳
41 bit，精確到毫秒薯蝎，總共可容納約 69 年的時(shí)間遥倦； - 工作機(jī)器 ID
10 bit，啟動(dòng)高 5 bit 是數(shù)據(jù)中心 ID（datacenterId）占锯，低 5 bit 是工作節(jié)點(diǎn) ID（workerId）袒哥，最多可以容納 1024 個(gè)節(jié)點(diǎn)缩筛； - 序列號(hào)
12 bit，同一毫秒同一節(jié)點(diǎn)多次執(zhí)行該算法堡称，從 0 開始依次遞增瞎抛，對(duì)多可以累加至 4095；
同一毫秒內(nèi)可生成全劇唯一 ID 數(shù)量：1024 * 4096 = 4194304却紧。
代碼實(shí)現(xiàn)
import java.time.LocalDateTime;
import java.time.ZoneOffset;
import java.util.concurrent.TimeUnit;
public class SnowFlakeUtils {
private static final int SERIAL_BIT = 12;
private static final int DATA_CENTER_BIT = 5;
private static final int WORK_BIT = 5;
private static final int TIME_STAMP_BIT = 41;
/**
* 對(duì)比時(shí)間點(diǎn) 2019-05-20 時(shí)間戳
*/
private static long timePoint = LocalDateTime.of(2019, 5, 20, 0, 0, 0).toInstant(ZoneOffset.of("+8")).toEpochMilli();
/**
* 1 bit: 符號(hào)位
*/
private static long flag = 0;
/**
* 41 bit: 時(shí)間戳（毫秒）
*/
private static long lastTimeStamp = -1L;
/**
* 5 bit: 工作機(jī)器 ID
*/
private static long dataCenterId = 1;
/**
* 5 bit: 工作機(jī)器 ID
*/
private static long workId = 1;
/**
* 12 bit: 序列號(hào)
*/
private static long serial = 0;
/**
* 序列號(hào) mask桐臊，防止溢出
*/
private static final long SERIAL_MASK = ~(-1L << SERIAL_BIT);
public static synchronized long uniqueId() {
long currentTimeStamp = System.currentTimeMillis() - timePoint;
if (lastTimeStamp == currentTimeStamp) {
// 同一毫秒，序列號(hào)遞增
long temp = (serial + 1) & SERIAL_MASK;
if (temp == 0) {
// 當(dāng)前毫秒內(nèi)序列已滿啄寡，重新獲取
sleep();
return uniqueId();
}
serial = temp;
} else {
lastTimeStamp = currentTimeStamp;
serial = 0L;
}
return serial
| (workId << SERIAL_BIT)
| (dataCenterId << SERIAL_BIT + WORK_BIT)
| (lastTimeStamp << (SERIAL_BIT + WORK_BIT + DATA_CENTER_BIT))
| (flag << (SERIAL_BIT + WORK_BIT + DATA_CENTER_BIT + TIME_STAMP_BIT));
}
private static void sleep() {
try {
TimeUnit.MILLISECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
注意序列號(hào)生成防止溢出豪硅，使用了 SERIAL_MASK，當(dāng)序列值當(dāng)前毫秒已經(jīng)使用滿時(shí)挺物，手動(dòng)休眠 1 毫秒后重復(fù)獲取即可懒浮。
