SnowFlake
Twitter 的 雪花算法 算法的 Java 实现版本。
算法思路
8字节（64位）占位的模式
主要分为以下四个部分：时间序列|数据中心序列|机器序列|自增序列
在当前代码中的大小设置如下：
- 时间序列：42 位，每 139 年开始重复
- 数据中心序列：5 位，共能承载 32 个数据中心
- 机器序列：5 位，共能承载 32 台机器（ID 生成机器）
- 自增序列：12 位，值的范围为：0 ～ 4095
算法调整说明
在实际开发中可以根据自己的需要去调整每个序列的占位比，如 DC 可能不会有那么多，而机器会偏多，此时可扩宽机器序列位，减少 DC 序列位。同样的，可以为了简便，采用 int 型（4 字节，32 位）来处理，或者采用 String 灵活调节字节数。
测试运行
- 编译：
javac SnowFlake.java - 运行：
java SnowFlake
注意事项
注意不同机器、不同 DC 需要配置不同的值序列号，如果配置了相同的值，就会造成长生相同 ID。
PS: 很多人在灰度发布、或者实例扩容的时候容易忘记更改机器的序列号。
实现
import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.atomic.LongAdder;
/**
* twitter的snowflake算法 雪花算法，用于生成long型ID ID为64位Long。 从高位算起，第一部分为 毫米时间戳， 占 64 - 22
* = 42 位。其次数据中心5位，机器标识5位，最后同一毫秒内的序列号12位。
*/
public class SnowFlake {
/**
* 起始的时间戳 2018-08-20
*/
private static final long START_TIMESTAMP = 1534694400000L;
/**
* 每一部分占用的位数
*/
private static final long SEQUENCE_BIT = 12; // 序列号占用的位数
private static final long MACHINE_BIT = 5; // 机器标识占用的位数
private static final long DATA_CENTER_BIT = 5;// 数据中心占用的位数
/**
* 每一部分的最大值
*/
private static final long MAX_DATA_CENTER_NUM = (1L << DATA_CENTER_BIT) - 1;
private static final long MAX_MACHINE_NUM = (1L << MACHINE_BIT) - 1;
private static final long MAX_SEQUENCE = (1L << SEQUENCE_BIT) - 1;
/**
* 每一部分向左的位移
*/
private static final long MACHINE_LEFT = SEQUENCE_BIT;
private static final long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
private static final long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT;
private final long dataCenterId; // 数据中心
private final long machineId; // 机器标识
private long sequence = 0l; // 序列号
private long lastTimestamp = -1L;// 上一次时间戳
/**
* constructor
*
* @param dataCenterId
* @param machineId
*/
public SnowFlake(long dataCenterId, long machineId) {
if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) {
throw new IllegalArgumentException("dataCenterId 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 curStamp = getNewTimestamp();
if (curStamp < lastTimestamp) {
throw new RuntimeException("Clock moved backwards. Refusing to generate id");
}
if (curStamp == lastTimestamp) {
// 相同毫秒内，序列号自增
sequence++;
// 同一毫秒的序列数已经达到最大，则等待下一毫秒，且重制sequence
if (sequence > MAX_SEQUENCE) {
curStamp = getNextMill();
sequence = 0L;
}
} else {
// 不同毫秒内，序列号置为0
sequence = 0L;
}
lastTimestamp = curStamp;
return (curStamp - START_TIMESTAMP) << TIMESTAMP_LEFT // 时间戳部分
| dataCenterId << DATA_CENTER_LEFT // 数据中心部分
| machineId << MACHINE_LEFT // 机器标识部分
| sequence; // 序列号部分
}
private long getNextMill() {
long mill = getNewTimestamp();
while (mill <= lastTimestamp) {
mill = getNewTimestamp();
}
return mill;
}
private long getNewTimestamp() {
return System.currentTimeMillis();
}
public static void main(String[] args) {
SnowFlake snowFlake = new SnowFlake(1, 1);
Set<String> ids = new HashSet<>();
for (int i = 0; i < 1000000; i++) {
long id = snowFlake.nextId();
ids.add(String.valueOf(id));
System.out.println(id);
}
System.out.println(ids.size());
}
}
可参见： source code
