一、背景：
清分系统需要一套id生成器服务，保证分布式情况下全局唯一。
二、算法描述：
1、原始算法：
（1）snowflake是twitter开源的分布式ID生成算法，其核心思想是：一个long型的ID，使用其中43bit作为毫秒数，3bit作为机房编号，5bit作为机器编码，12bit作为毫秒内序列号。这个算法单机每毫秒内理论上最多可以生成2^12，也就是4096个ID，完全能满足业务的需求。
（2）snowflake的结构如下(每部分用-分开):
0 - 0000000000 0000000000 0000000000 0000000000 000 - 000 - 00000 - 000000000000
一共加起来刚好64位，为一个Long型。(转换成字符串长度为18)
snowflake生成的ID整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞（由datacenter和workerId作区分），并且效率较高。
2、算法变形：
（1）long类型最大值是9,223,372,036,854,775,807（2^63 -1），即19位十进制数。取前13位作为毫秒数，1位作为毫秒内序列号，2位作为机器编号，3位作为数据库表尾号。这个算法单机每毫秒内理论最多可以生产10个id(每秒内理论最多可以生产1w个id)，完全满足业务需求。
（2）结构如下(每部分用 - 分开)：
0000000000000 - 0 - 00 -000
加起来正好19位。生成的ID整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞。
3、清分系统中的id样例：
（1）服务器分配机器编码
（2）现清分系统中，tradeFlowId和summaryTradeFlowId前4位为YYMM，即1611开头的19位数。
新的snowflake id生成器生成的id是1613开头的19位数。如1613024787541981316，1613024787541为当前时间 (毫秒+偏移量1345400000000)，9为序列号，81为机器编码，316为数据库尾号。
（3）现清分系统中，batchid为26开头的10位数。
batchid不涉及数据库尾号，所以可以减少id的位数，保证batchid大于26开头的10位数就可以。生成id如1478484776931281，1478484776931为当前时间，2为序列号，81为机器编码。
三、代码描述：
1、加锁实现：
public class IdWorker {
// 按照清分系统现在的id生成速度，2016-10-01之前，最大id小于1609040000000。
// 时间戳1473000000000对应北京时间2016-9-4 22:40:00
// twepoch = 1609040000000 - 1473000000000 = 136040000000，所以 2016-9-4以后的时间戳 + 136040000000 肯定大于 1609040000000，只要在2016-10-01之前上线服务，生成的id就不会与目前库中id冲突。
private final long twepoch = 136040000000L;
// 机器编号，十进制两位，0-99
private final int workerIdBits = 2;
private final int maxWorkerId = 99;
// 毫秒内序列号
private final int sequenceBits = 1;
private final int sequenceMask = 10;
// 数据库表尾号0-999，共3位
private final int tableIndexBits = 3;
// 十进制偏移量
private final int sequenceShift = tableIndexBits;
private final int workerIdShift = sequenceBits + tableIndexBits;
private final int timestampLeftShift = workerIdBits + sequenceBits + tableIndexBits;
private final Random random = new Random();
private int workerId;
private int sequence = 0;
private long lastTimestamp = -1L;
public IdWorker(int workerId) {
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
}
this.workerId = workerId;
}
public long nextId() {
lock.lock();
// 偏移的倍数
long timestampShiftValue;
long workerShiftValue;
long sequenceShiftValue;
// 随机获取数据库表尾号
int tableIndex;
try {
long timestamp = timeGen();
if (timestamp < lastTimestamp) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) % sequenceMask;
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0;
}
lastTimestamp = timestamp;
timestampShiftValue = new Double(Math.pow(10, timestampLeftShift)).longValue();
workerShiftValue = new Double(Math.pow(10, workerIdShift)).longValue();
sequenceShiftValue = new Double(Math.pow(10, sequenceShift)).longValue();
tableIndex = random.nextInt(1000);
} finally {
lock.unlock();
}
return (timestamp + twepoch) * timestampShiftValue + workerId * workerShiftValue + sequence * sequenceShiftValue + tableIndex;
}
protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
protected long timeGen() {
return System.currentTimeMillis() / 10;
}
}2、无锁实现：
public class IdWorker2 {
// 时间基准
private final long twepoch = 136040000000L;
private final long workerIdBits = 5L;
private final long datacenterIdBits = 3L;
private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
private final long sequenceBits = 12L;
private final long workerIdShift = sequenceBits;
private final long datacenterIdShift = sequenceBits + workerIdBits;
private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
private final long sequenceMask = -1L ^ (-1L << sequenceBits);
private long workerId;
private long datacenterId;
private AtomicLong sequence = new AtomicLong(0);
private volatile long lastTimestamp = -1L;
public IdWorker2(long workerId, long datacenterId) {
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
}
if (datacenterId > maxDatacenterId || datacenterId < 0) {
throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
}
this.workerId = workerId;
this.datacenterId = datacenterId;
}
public long nextId() {
long currentSeq, seq, timestamp;
timestamp = timeGen();
if (timestamp < lastTimestamp) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds",
lastTimestamp - timestamp));
}
for (; ; ) {
if (lastTimestamp == timestamp) {
currentSeq = sequence.incrementAndGet();
if (currentSeq > sequenceMask) { //当前毫秒的已经用完，计数器清0，等到下一个毫秒
timestamp = tilNextMillis(lastTimestamp);
sequence.compareAndSet(currentSeq, -1);
continue;
} else {
seq = currentSeq & sequenceMask;
break;
}
}
lastTimestamp = timestamp;
}
return ((timestamp + twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | seq;
}
protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
protected long timeGen() {
return System.currentTimeMillis();
}
}四、结果分析
1、对比与选择
通过对比加锁和无锁两种算法，发现并发数为100-10000的区间中，两者差别甚微。由于twitter选取的是加锁算法，我们也选择经过考证的加锁算法。
2、算法特点分析
- 算法支持单机qps为10000(自己mac上跑的结果)，目前业务情况是单台机器qps为50左右。
- 单台机器生成的id为单调递增。
- 算法支持的时间截止日期为2262年(取long型最高13位9223372036850作为时间戳)。
- 算法支持99台机器。
- 针对业务需求，机器号需要额外获取。
3、异常情况
（1）获取机器号出错。
- 服务启动时获取机器编号，获取失败则服务启动失败。
（2）在获取当前 Timestamp 时, 如果获取到的时间戳比前一个已生成 ID 的 Timestamp 还要小怎么办?
- 继续获取当前机器的时间, 直到获取到更大的 Timestamp 才能继续工作；
- 把 NTP 配置成不会向后调整的模式，也就是说, NTP 纠正时间时, 不会向后回拨机器时钟。
版权声明：本文为lianhuazy167原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。