雪花算法ID重复问题的解决方案

1、雪花算法生成的Id由：1bit 不用 + 41bit时间戳+10bit工作机器id+12bit序列号，如下图：

集群部署的微服务，当随机的机器ID相同，刚好在同一毫秒生成ID，时间戳相同，并且序列号也相同时，那么雪花算法的ID就会出现重复的问题。

2、如何解决重复问题

工作机器id：10bit，表示工作机器id，用于处理分布式部署id不重复问题，可支持2^10 = 1024个节点
我们只需要给同一个微服务分配不同的工作机器ID即可，在redis中存储一个当前workerId的最大值
每次生成workerId时，从redis中获取到当前workerId最大值，并+1作为当前workerId，并存入redis

3、雪花ID生成样例

public class SnowflakeIdWorker {
    /** 开始时间截 (建议用服务第一次上线的时间，到毫秒级的时间戳) */
    private final long twepoch = 687888001020L;

    /** 机器id所占的位数 */
    private final long workerIdBits = 10L;

    /** 支持的最大机器id，结果是1023 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /** 序列在id中占的位数 */
    private final long sequenceBits = 12L;

    /** 机器ID向左移12位 */
    private final long workerIdShift = sequenceBits;

    /** 时间截向左移22位(10+12) */
    private final long timestampLeftShift = sequenceBits + workerIdBits;

    /** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095)
     * <<为左移，每左移动1位，则扩大1倍
     * */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /** 工作机器ID(0~1024) */
    private long workerId;

    /** 毫秒内序列(0~4095) */
    private long sequence = 0L;

    /** 上次生成ID的时间截 */
    private long lastTimestamp = -1L;

    //==============================Constructors=====================================
    /**
     * 构造函数
     * @param workerId 工作ID (0~1023)
     */
    public SnowflakeIdWorker(long workerId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("workerId can't be greater than %d or less than 0", maxWorkerId));
        }
        this.workerId = workerId;
    }

    // ==============================Methods==========================================
    /**
     * 获得下一个ID (该方法是线程安全的)
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();
        //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(
                    String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }

        //如果是同一时间生成的，则进行毫秒内序列
        if (lastTimestamp == timestamp) {
            //如果毫秒相同，则从0递增生成序列号
            sequence = (sequence + 1) & sequenceMask;
            //毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        //时间戳改变，毫秒内序列重置
        else {
            sequence = 0L;
        }

        //上次生成ID的时间截
        lastTimestamp = timestamp;

        //移位并通过或运算拼到一起组成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (workerId << workerIdShift) //
                | sequence;
    }

    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 返回以毫秒为单位的当前时间，从1970-01-01 08:00:00算起
     * @return 当前时间(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }
}

• timestamp ：当前时间毫秒级别的时间戳
• twepoch：开始时间毫秒级别的时间截
• timestampLeftShift：时间需要左移位数，这里为sequenceBits + workerIdBits，这里为序列号位数+工作机器id位数，即12+10 = 22
• workerId ：工作机器id，用于解决分布式Id重复的问题，这里为外部传入的参数
• workerIdShift：工作机器id左移位数，这里为sequenceBits，即12
• sequence：序列，这里为0~4095中的一个数值

假设twepoch为当前时间，timestamp为twepoch之后1000ms，即（timestamp - twepoch）=1000；
工作机器id为1，即workerId = 1；
当前毫秒值第一次生成，即sequence = 0，则ID为：
((1000) << 22)
| (1 << 12)
| 0
即生成的Id：4194308096

• 此时，假设同一毫秒值，又生成了一次id，则：
  ((1000) << 22)
  | (1 << 12)
  | 1
  生成的Id：4194308097，所以同一台机器人上基本保证了递增

工作机器Id的作用，就是用于解决分布式Id重复的问题，这个workerId是通过构造方法传入的，如果我们用10位来存储这个值，那就是最多支持1024个节点。

如果不是容器化部署，部署是固定的机器，我们用机器的唯一名来做key，那我们可以对这些机器名和workerId建立一个对应关系，如果存在就用之前的workerId，不存在就往上累加比如我们用计算机名做key：

但是如果是容器化部署，需要支持动态增加节点，并且每次部署的机器不一定一样时，就会有问题，如果发现不同，就往上累加，经过多次发版，就可能会超过1023，这个时候生成雪花Id时，工作机器id左移12位后，当进行或运算时，时间戳的位置就会被影响，比如workerId=1024，我们拿之前的举例第1000ms，那它和第1001ms、workerId=0配置，可能生成重复的Id

上述代码有2个问题：

1、hashcode对32取模，本身就可能会重复，比如460141958和3164804对32取模都是4，那生成的workerId就重复了
2、如果hashcode>15,随机取一个，那每次都有1/16的概率重复

解决方案

1、在redis中存储一个当前workerId的最大值,每次生成workerId时，从redis中获取到当前workerId最大值，并+1作为当前workerId，并存入redis。如果workerId为1023，自增为1024，则重置0，作为当前workerId，并存入redis。

2、上述逻辑，其实可以参考序列号的位运算，简化为：
workerId= (workerId+ 1) & (-1L ^ (-1L << workerIdBits))
其中：workerIdBits为机器人Id所占的位数
如果workerIdBits = 10，则为0增长到1023后，继续从0开始自增

private Long getWorkerId(String key) {
        String luaStr = "local isExist = redis.call('exists', KEYS[1])\n" +
                "if isExist == 1 then\n" +
                "    local workerId = redis.call('get', KEYS[1])\n" +
                "    workerId = (workerId + 1) % 1024\n" +
                "    redis.call('set', KEYS[1], workerId)\n" +
                "    return workerId\n" +
                "else\n" +
                "    redis.call('set', KEYS[1], 0)\n" +
                "    return 0\n" +
                "end";
        DefaultRedisScript<Long> redisScript = new DefaultRedisScript<>();
        // 以下两种二选一即可
        redisScript.setScriptText(luaStr);
        //redisScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("redis/redis_worker_id.lua")));
        redisScript.setResultType(Long.class);
        return redisTemplate.execute(redisScript, Collections.singletonList(key));
    }

如果选第二种需要建立redis_worker_id.lua文件，内容如下

local isExist = redis.call('exists', KEYS[1])
if isExist == 1 then
    local workerId = redis.call('get', KEYS[1])
    workerId = (workerId + 1) % 1024
    redis.call('set', KEYS[1], workerId)
    return workerId
else
    redis.call('set', KEYS[1], 0)
    return 0
end

参考文章

雪花算法（snowflake）生成Id重复问题——唐江旭
雪花算法ID重复的分析与在项目中的解决——汤同学、