基于时钟序列解决时钟回拨

一、背景

分布式 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;
}