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

发布时间:2023年12月26日

一、背景

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

文章来源:https://blog.csdn.net/DUBO160/article/details/135217201
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。