java中雪花算法时钟回拨问题解决_Java

雪花算法（snowflake）是twitter开源的一种分布式唯一id生成算法，用于在分布式系统中生成全局唯一的id。雪花算法生成的id是一个64位的整数，通常表示为长整型（long）。

雪花算法的结构

雪花算法生成的id由以下几部分组成：

符号位（1位）：始终为0，保证生成的id为正数。
时间戳（41位）：记录生成id的时间戳，精确到毫秒级。可以使用大约69年的时间。
机器id（10位）：标识生成id的机器，可以支持1024台机器。
序列号（12位）：同一毫秒内生成的多个id的序列号，可以支持每毫秒生成4096个id。

时钟回拨问题

时钟回拨问题是指在分布式系统中，由于各种原因（如ntp时间同步），某些节点的系统时间可能会回退到过去的时间点。这会导致雪花算法生成的id出现重复，因为时间戳部分会重复。

解决时钟回拨问题的方法

等待机制：
- 当检测到时钟回拨时，生成器可以等待时间追上上次生成id的时间戳，然后再生成新的id。这种方法简单直接，但可能会导致生成器在等待期间无法生成新的id。
扩展位：
- 在id结构中增加额外的位来处理时钟回拨。例如，可以使用额外的位来记录时钟回拨的次数，从而避免id重复。
预留时间戳：
- 在生成id时，预留一些时间戳范围，用于处理时钟回拨。例如，可以预留一些时间戳范围，当检测到时钟回拨时，使用预留的时间戳生成新的id。
逻辑时钟：
- 使用逻辑时钟（如lamport时钟或vector时钟）代替物理时钟。逻辑时钟可以保证在分布式系统中事件的顺序，避免时钟回拨问题。

示例代码

以下是一个使用等待机制解决时钟回拨问题的雪花算法实现示例：

public class snowflakeidgenerator {
    private final long twepoch = 1288834974657l; // 起始时间戳，例如twitter的snowflake起始时间
    private final long workeridbits = 10l;
    private final long maxworkerid = -1l ^ (-1l << workeridbits);
    private final long sequencebits = 12l;
    private final long workeridshift = sequencebits;
    private final long timestampleftshift = sequencebits + workeridbits;
    private final long sequencemask = -1l ^ (-1l << sequencebits);

    private long workerid;
    private long sequence = 0l;
    private long lasttimestamp = -1l;

    public snowflakeidgenerator(long 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 synchronized long nextid() {
        long timestamp = timegen();

        if (timestamp < lasttimestamp) {
            // 时钟回拨，等待时间追上
            long offset = lasttimestamp - timestamp;
            if (offset <= 5) {
                try {
                    wait(offset << 1);
                    timestamp = timegen();
                    if (timestamp < lasttimestamp) {
                        throw new runtimeexception(string.format("clock moved backwards. refusing to generate id for %d milliseconds", offset));
                    }
                } catch (interruptedexception e) {
                    throw new runtimeexception(e);
                }
            } else {
                throw new runtimeexception(string.format("clock moved backwards. refusing to generate id for %d milliseconds", offset));
            }
        }

        if (lasttimestamp == timestamp) {
            sequence = (sequence + 1) & sequencemask;
            if (sequence == 0) {
                timestamp = tilnextmillis(lasttimestamp);
            }
        } else {
            sequence = 0l;
        }

        lasttimestamp = timestamp;

        return ((timestamp - twepoch) << timestampleftshift) |
                (workerid << workeridshift) |
                sequence;
    }

    protected long tilnextmillis(long lasttimestamp) {
        long timestamp = timegen();
        while (timestamp <= lasttimestamp) {
            timestamp = timegen();
        }
        return timestamp;
    }

    protected long timegen() {
        return system.currenttimemillis();
    }

    public static void main(string[] args) {
        snowflakeidgenerator idgenerator = new snowflakeidgenerator(1);
        system.out.println(idgenerator.nextid());
    }
}

代码解释

检测时钟回拨：
- 在生成id时，首先获取当前时间戳，并与上次生成id的时间戳进行比较。
- 如果当前时间戳小于上次生成id的时间戳，说明发生了时钟回拨。
等待机制：
- 如果时钟回拨的时间差小于等于5毫秒，生成器会等待时间追上上次生成id的时间戳。
- 如果时钟回拨的时间差大于5毫秒，抛出异常，拒绝生成id。
生成新的id：
- 如果时钟没有回拨，或者等待时间追上后，生成新的id。