分布式 ID 生成算法用于在分布式系统中生成全局唯一的 ID 标识,而 twitter 提出的雪花算法便是其中一种知名的算法,其每次会生成一个 64 位的全局唯一整数,算法的基本思想非常巧妙:
二进制64位长整型数字:1bit保留 + 41bit时间戳 + 10bit机器(或5位数据中心ID+5位机器ID)?+ 12bit序列号
由于雪花算法重度依赖机器的当前时间,所以一旦发生时间回拨,将有可能导致生成的 ID 可能与此前已经生成的某个 ID 重复。针对这种问题,目前算法本身只是抛出异常。
if (timestamp < lastTimestamp) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
或者如果偏差比较小,则延迟等待,如美团的leaf
if (timestamp < lastTimestamp) {
long offset = lastTimestamp - timestamp;
if (offset <= 5) {
try {
wait(offset << 1);
timestamp = timeGen();
if (timestamp < lastTimestamp) {
return new Result(-1, Status.EXCEPTION);
}
} catch (InterruptedException e) {
LOGGER.error("wait interrupted");
return new Result(-2, Status.EXCEPTION);
}
} else {
return new Result(-3, Status.EXCEPTION);
}
}
如果是在一个并发不高或者请求量不大的业务系统中,抛出异常或延迟等待或者重试的策略问题不大,但是如果是在一个高并发的系统中,这种策略显得过于粗暴。
既然我已经发现了时间回拨,那我就认为原先的“时钟”已经不可用,使用一个新的“时钟”即可,并将新的当前时间认为是新时钟的时间。基于时钟序列的雪花算法:
二进制64位长整型数字:1bit保留 + 41bit时间戳 + 5位时钟序列 + 5bit机器 + 12bit序列号
分布式实例规模缩小到32, 单实例支持最多 32次回拨同一时间范围(如果时间回拨发生在互不交叠的时间段,则理论上可以完美解决时间回拨问题)。
public synchronized long nextId() {
long timestamp = timeGen();
if (timestamp < lastTimestamp) {
clockSequence = (clockSequence +1) & maxclockSequence;
//throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
if (lastTimestamp == timestamp) {
// 当前毫秒内,则+1
sequence = (sequence + 1) & sequenceMask;
if (sequence == 0) {
// 当前毫秒内计数满了,则等待下一秒
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0L;
}
lastTimestamp = timestamp;
// ID偏移组合生成最终的ID,并返回ID
long nextId = ((timestamp - twepoch) << timestampLeftShift)
| (clockSequence << clockSequenceShift)
| (workerId << workerIdShift) | sequence;
return nextId;
}