個人中心
退出
算法：第一章：SnowFlake算法（分布式系統(tǒng)中生成唯一的ID的算法）SnowFlake每秒能夠產(chǎn)生26萬ID左右
不廢話了，直接上代碼：
package cn.springboot.config.db.pk.local.impl;
/**
* The class Snowflake id generator. Created by paascloud.net@gmail.com
* Twitter雪花ID算法
* 概述
* - SnowFlake算法是Twitter設(shè)計(jì)的一個可以在分布式系統(tǒng)中生成唯一的ID的算法，它可以滿足Twitter每秒上萬條消息ID分配的請求，這些消息ID是唯一的且有大致的遞增順序
*
* 原理
* - SnowFlake算法產(chǎn)生的ID是一個64位的整型，結(jié)構(gòu)如下（每一部分用“-”符號分隔）：
* 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
* - 1位標(biāo)識部分，在java中由于long的最高位是符號位，正數(shù)是0，負(fù)數(shù)是1，一般生成的ID為正數(shù)，所以為0
* - 41位時間戳部分，這個是毫秒級的時間，一般實(shí)現(xiàn)上不會存儲當(dāng)前的時間戳，而是時間戳的差值（當(dāng)前時間-固定的開始時間），這樣可以使產(chǎn)生的ID從更小值開始；41位的時間戳可以使用69年，(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年
* - 10位節(jié)點(diǎn)部分，Twitter實(shí)現(xiàn)中使用前5位作為數(shù)據(jù)中心標(biāo)識，后5位作為機(jī)器標(biāo)識，可以部署1024個節(jié)點(diǎn)
* - 12位序列號部分，12位的計(jì)數(shù)順序號支持每個節(jié)點(diǎn)每毫秒(同一機(jī)器，同一時間戳)產(chǎn)生4096個ID序號，加起來剛好64位，為一個Long型
*
* 優(yōu)點(diǎn)
* - SnowFlake的優(yōu)點(diǎn)是，整體上按照時間自增排序，并且整個分布式系統(tǒng)內(nèi)不會產(chǎn)生ID碰撞(由數(shù)據(jù)中心ID和機(jī)器ID作區(qū)分)，并且效率較高，經(jīng)測試，SnowFlake每秒能夠產(chǎn)生26萬ID左右
*
* 使用
* - SnowFlake算法生成的ID大致上是按照時間遞增的，用在分布式系統(tǒng)中時，需要注意數(shù)據(jù)中心標(biāo)識和機(jī)器標(biāo)識必須唯一，這樣就能保證每個節(jié)點(diǎn)生成的ID都是唯一的。
* 或許我們不一定都需要像上面那樣使用5位作為數(shù)據(jù)中心標(biāo)識，5位作為機(jī)器標(biāo)識，可以根據(jù)我們業(yè)務(wù)的需要，靈活分配節(jié)點(diǎn)部分，如：若不需要數(shù)據(jù)中心，完全可以使用全部10位作為機(jī)器標(biāo)識；若數(shù)據(jù)中心不多，也可以只使用3位作為數(shù)據(jù)中心，7位作為機(jī)器標(biāo)識
*/
public class SnowflakeIdGenerator {
/**
* 每一部分占用的位數(shù)
*/
private final static long DATA_CENTER_ID_BITS = 5L; // 數(shù)據(jù)中心標(biāo)識在ID中占用的位數(shù)
private final static long MACHINE_ID_BITS = 5L; // 機(jī)器標(biāo)識在ID中占用的位數(shù)
private final static long SEQUENCE_BITS = 12L; // 序列號在ID中占用的位數(shù)
/**
* 每一部分的最大值
*/
private final static long MAX_DATA_CENTER_ID = -1L ^ (-1L << DATA_CENTER_ID_BITS); // 支持的最大數(shù)據(jù)中心標(biāo)識ID為31
private final static long MAX_MACHINE_ID = -1L ^ (-1L << MACHINE_ID_BITS); // 支持的最大機(jī)器標(biāo)識ID為31(這個移位算法可以很快的計(jì)算出幾位二進(jìn)制數(shù)所能表示的最大十進(jìn)制數(shù))
private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BITS); // 支持的最大序列(掩碼), 這里為4095 (0b111111111111=0xfff=4095)
/**
* 每一部分向左的位移
*/
private final static long DATA_CENTER_ID_SHIFT = SEQUENCE_BITS + MACHINE_ID_BITS; // 數(shù)據(jù)中心標(biāo)識ID向左移17位(12+5)
private final static long MACHINE_ID_SHIFT = SEQUENCE_BITS; // 機(jī)器標(biāo)識ID向左移12位
private final static long TIMESTAMP_SHIFT = SEQUENCE_BITS + MACHINE_ID_BITS + DATA_CENTER_ID_BITS; // 時間戳向左移22位(5+5+12)
/**
* 批量獲取的最大數(shù)目(10萬)
*/
private final static int MAX_BATCH_COUNT = 100_000;
/**
* 變量部分
*/
private long dataCenterId; // 數(shù)據(jù)中心標(biāo)識ID(0~31)
private long machineId; // 機(jī)器標(biāo)識ID(0~31)
private long sequence = 0L; // 毫秒內(nèi)序列(0~4095)
private long startTimestamp = -1L; // 開始時間戳
private long lastTimestamp = -1L; // 上次生成ID的時間戳
/**
* 構(gòu)造方法
* @param startTimestamp 開始時間戳，不可大于當(dāng)前時間
* @param dataCenterId 數(shù)據(jù)中心標(biāo)識ID(0~31)
* @param machineId 機(jī)器標(biāo)識ID(0~31)
*/
public SnowflakeIdGenerator(long startTimestamp, long dataCenterId, long machineId) {
long currentTimestamp = getCurrentTimestamp();
if (startTimestamp > currentTimestamp) {
throw new RuntimeException(String.format("Start timestamp can't be greater than %d", currentTimestamp));
}
if (dataCenterId > MAX_DATA_CENTER_ID || dataCenterId < 0) {
throw new RuntimeException(String.format("Data center id can't be greater than %d or less than 0", MAX_DATA_CENTER_ID));
}
if (machineId > MAX_MACHINE_ID || machineId < 0) {
throw new RuntimeException(String.format("Machine id can't be greater than %d or less than 0", MAX_MACHINE_ID));
}
// 當(dāng)初始時間跟當(dāng)前時間相等，減1毫秒，否則會導(dǎo)致溢出
this.startTimestamp = (startTimestamp == currentTimestamp ? startTimestamp - 1 : startTimestamp);
this.dataCenterId = dataCenterId;
this.machineId = machineId;
}
/**
* 批量獲取下一組ID
* @param count 批量條數(shù)
* @return
*/
public String[] nextIds(int count) {
if (count <= 0 || count > MAX_BATCH_COUNT) {
throw new RuntimeException(String.format("Count can't be greater than %d or less than 0", MAX_BATCH_COUNT));
}
String[] ids = new String[count];
for (int i = 0; i < count; i++) {
ids[i] = nextId();
}
return ids;
}
/**
* 獲得下一個ID (該方法是線程安全的)
* @return
*/
public synchronized String nextId() {
long currentTimestamp = getCurrentTimestamp();
// 如果當(dāng)前時間小于上一次ID生成的時間戳, 說明系統(tǒng)時鐘回退過這個時候應(yīng)當(dāng)拋出異常
if (currentTimestamp < lastTimestamp) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - currentTimestamp));
}
// 如果是同一時間生成的, 則進(jìn)行毫秒內(nèi)序列自增
if (lastTimestamp == currentTimestamp) {
// 相同毫秒內(nèi)，序列號自增
sequence = (sequence + 1) & MAX_SEQUENCE;
// 同一毫秒的序列數(shù)已經(jīng)達(dá)到最大，則毫秒內(nèi)序列溢出
if (sequence == 0) {
// 阻塞到下一個毫秒，獲得新的時間戳
currentTimestamp = getNextTimestamp(lastTimestamp);
}
} else {
// 不同毫秒內(nèi)，序列號置為0
sequence = 0L;
}
// 上次生成ID的時間戳
lastTimestamp = currentTimestamp;
// 移位并通過或運(yùn)算拼到一起組成64位的ID
long id = ((currentTimestamp - startTimestamp) << TIMESTAMP_SHIFT) // 時間戳部分
| (dataCenterId << DATA_CENTER_ID_SHIFT) // 數(shù)據(jù)中心標(biāo)識ID部分
| (machineId << MACHINE_ID_SHIFT) // 機(jī)器標(biāo)識ID部分
| sequence; // 序列號部分
return String.valueOf(id);
}
/**
* 阻塞到下一個毫秒, 直到獲得新的時間戳
* @param lastTimestamp 上次生成ID的時間戳
* @return 當(dāng)前時間戳
*/
private long getNextTimestamp(long lastTimestamp) {
long currentTimestamp = getCurrentTimestamp();
while (currentTimestamp <= lastTimestamp) {
currentTimestamp = getCurrentTimestamp();
}
return currentTimestamp;
}
/**
* 返回以毫秒為單位的當(dāng)前時間
* @return 當(dāng)前時間(毫秒)
*/
private long getCurrentTimestamp() {
return System.currentTimeMillis();
}
public static void main(String[] args) {
SnowflakeIdGenerator generator = new SnowflakeIdGenerator(1483200000000L, 2, 3);
for (int i = 0; i < 1000; i++) {
System.out.println(generator.nextId());
}
}
}
分類導(dǎo)航