解决Snowflake算法时钟回拨的一种方案

01 算法介绍

Snowflake是Twitter开源的分布式ID生成算法，结果是一个19位的Long型的ID。其核心思想是：使用41bit作为毫秒数，10bit作为机器的ID，12bit作为毫秒内的流水号（即每个节点在每毫秒可以产生 4096 个 ID），最后还有一个符号位，永远是0。

布局如下图所示：

二进制字符串位（64位）：

0101111001101110110111100011011101011110000000000000000000000000

该算法的优缺点在网上很容易找到。

优点：

1、整体呈递增趋势

2、不依赖第三方系统，稳定性更高

3、可以根据自身业务特性分配bit位

缺点：

1、严重依赖时钟

Snowflake算法使用时间戳，个人认为是由于时间戳为全局整体呈递增趋势，在防重上区别性比较大，同时方便获取。

02 方案介绍

今天我主要介绍的是一种时间回拨时的解决方案：

回到snowflake算法结构，仔细分析会发现：

1、10位的workId属于自定义

2、12位的顺序号主要是高并发

3、41位的时间戳本质为时间的差值，并非一定要求为当前时间。比如：System.currentTimeMillis(), 其实质为当前时间距离1970-01-01的时间差值的毫秒数。

实质上时间戳位置也可以是当前时间 - 基线时间（timeEpoch）计算之后的时间差值。而解决时间回拨的问题，入手点便在当前时间。虽然申明为当前时间，其实际上可以为任意一个大于基线时间的时间，只要保证随着时间推移，整体递增，且全局唯一。

比如41位的时间戳的值为：

41位的时间戳 = 当前基础时间 - 基线时间。

当前基础时间 = 当前系统时间 - 时钟回拨缓冲时间（比如1年 = 365 * 24 * 3600 * 1000L）。

上一次访问时间 = 上一次访问的基础时间。

当上一次访问时间 大于 当前基础时间 ，表示系统时间已经回拨。

此时通过调整时钟回拨缓冲时间，修复当前基础时间

时钟回拨调整的幅度 = 上一次访问时间 - 发生时钟回拨之后的系统时间

当前基础时间 = 当前系统时间 -（ 时间回拨缓冲时间 - 时钟回拨调整的幅度 ）

修复示例图：

注意：

1、方案中的的“上一次访问时间”需要在当前节点持久化至文件或者可持久化的位置

2、可修复的差值 = 上一次访问时间 - 发生时钟回拨之后的系统时间

从图中示例可以看出，正常情况下，“时钟回拨缓存时间”为365天，如果发生时钟回拨1天，可修复的差值 = 1，“时钟回拨缓存时间”调整为364（天） = 365（天） - 1（天）

如果时间回拨缓存时间等于1年时，就表示系统运行时，时间回拨最大的时间为1年。

反馈问题：

1、我为什么自定义基线时间即时间纪元。

经过测试，我发现时间差值在2000年左右才可以保证生成的ID为整数，如果超过则会产生负数，我修改时间纪元，主要为了延长使用的时间

2、上述时钟缓存时间为什么是1年

时钟缓存时间可以自定义，1年只是我当前的使用值

代码如下：

// 获取snowflake算法计算之后的值
public synchronized long getId() {
        long timestamp = currentBaseTime();
        if (timestamp < lastTimestamp) {
            long offset = lastTimestamp - timestamp;
            //毫秒级的时间倒退，直接等待
            if (offset <= 5) {
                try {
                    wait(offset << 1);
                } catch (Exception ex) {
                    logger.error("wait={} 异常", offset);
                }
            } else {
                //超过5ms的时间倒退，则直接修复
                this.fixStepMills = offset;
            }
            timestamp = currentBaseTime();
            //此处为两次校验，提高准确性
            if (timestamp < lastTimestamp) {
                this.fixStepMills = lastTimestamp - timestamp;
                timestamp = currentBaseTime();
            }
        }
        //最后的时间戳与当前时间相等
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                sequence = random.nextInt(100);
                timestamp = tilNextTimestamp(lastTimestamp);
            }
        } else {
            sequence = random.nextInt(100);
        }
        this.lastTimestamp = timestamp;
        return (timestamp - timeEpoch) << timestampShift | workId << workIdShift | sequence;
}


//获取当前基础时间
private long currentBaseTime() {
        // baseBackupMills:时间回拨缓冲时间
        // fixStepMills:待修复的时间，即时钟回拨的时间差值
        long baseTimeEpoch = baseBackupMills - fixStepMills;
        if (baseTimeEpoch <= 0) {
            throw new IllegalArgumentException("time back to long");
        }
        LocalDateTime currentTime = getCurrentTime();
        if (Objects.isNull(currentTime)) {
            currentTime = LocalDateTime.now();
        }
        return currentTime.minusSeconds(baseTimeEpoch / 1000).atZone(ZoneId.systemDefault()).toInstant().toEpochMilli();
}