详解Java中雪花算法的实现

需求概述

在分布式系统中，为了保证业务数据的唯一性，需要生成唯一的ID。传统的ID生成方式可能出现因为高并发而重复的情况，而雪花算法(Snowflake)正是为了解决这个问题而出现的。

本文会详细介绍Java中雪花算法的实现，及其原理。

雪花算法的基本原理

雪花算法是Twitter开源的分布式ID生成算法，采用一个64位的long类型作为唯一ID，其中各个部分表示的含义如下：

1. 1位不用，可以用作别的标识
2. 41位表示毫秒数，可以使用69年，到最高位是2199023255551（因为使用long存储，所以需要使用L作为后缀）
3. 10位表示机器的id（5位机房id + 5位机器id），可以使用1024台机器
4. 12位表示某一毫秒内的序列号，同一毫秒内最多可以生成4096个ID

Java中雪花算法的实现

下面是Java中实现雪花算法的代码示例：

public class SnowflakeIdGenerator {

    /**
     * 雪花算法的起始时间，用于计算时间戳
     */
    private static final long START_TIME = 1609459200000L;

    private static final long WORKER_ID_BITS = 5L;
    private static final long DATACENTER_ID_BITS = 5L;
    private static final long SEQUENCE_BITS = 12L;
    private static final long MAX_WORKER_ID = ~(-1L << WORKER_ID_BITS);
    private static final long MAX_DATACENTER_ID = ~(-1L << DATACENTER_ID_BITS);

    private static final long WORKER_ID_SHIFT = SEQUENCE_BITS;
    private static final long DATACENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS;
    private static final long TIMESTAMP_LEFT_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATACENTER_ID_BITS; 

    /**
     * 工作节点ID
     */
    private final long workerId;

    /**
     * 数据中心ID
     */
    private final long datacenterId;

    /**
     * 当前毫秒生成的序列号
     */
    private long sequence = 0L;

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

    public SnowflakeIdGenerator(long workerId, long datacenterId) {
        if (workerId > MAX_WORKER_ID || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", MAX_WORKER_ID));
        }

        if (datacenterId > MAX_DATACENTER_ID || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", MAX_DATACENTER_ID));
        }

        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }

    /**
     * 生成一个唯一ID
     *
     * @return 雪花算法生成的唯一ID
     */
    public synchronized long nextId() {
        long timestamp = timeGen();

        if (timestamp < lastTimestamp) {
            throw new RuntimeException("Clock moved backwards. Refusing to generate id");
        }

        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & ~(-1L << SEQUENCE_BITS);
            if (sequence == 0L) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }

        lastTimestamp = timestamp;

        return ((timestamp - START_TIME) << TIMESTAMP_LEFT_SHIFT)
                | (datacenterId << DATACENTER_ID_SHIFT)
                | (workerId << WORKER_ID_SHIFT)
                | sequence;
    }

    /**
     * 获取当前的时间戳，并减去起始时间，保证不同数据中心和机器的时间戳序列递增
     */
    private long timeGen() {
        return System.currentTimeMillis() - START_TIME;
    }

    /**
     * 如果当前时间戳与上次生成的时间戳相同，则等待下一毫秒再生成
     */
    private long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }
}

雪花算法生成ID的过程中，通过timeGen()方法获取当前的时间戳，并减去起始时间。通过&运算保证序列号不溢出。

示例说明

下面分别是两个雪花算法的生成ID的例子：

public class SnowflakeIdGeneratorTest {

    /**
     * 单机生成ID的示例
     */
    @Test
    public void testSingleMachine() {
        SnowflakeIdGenerator idGenerator = new SnowflakeIdGenerator(1, 1);
        System.out.println(idGenerator.nextId());
    }

    /**
     * 多机房、多机器生成ID的示例
     */
    @Test
    public void testMultiMachine() {
        SnowflakeIdGenerator idGenerator = new SnowflakeIdGenerator(15, 64);
        System.out.println(idGenerator.nextId());
    }
}

其中testSingleMachine()方法是在单机器上生成ID的示例，testMultiMachine()方法是在多机器、多机房的情况下生成ID的示例。

总结

通过本文的介绍，我们了解到了雪花算法的基本原理和Java中的实现方式，同时还提供了多机房、多机器和单机器模式下的示例。

在实际开发中，我们可以根据具体的业务需求，选择合适的方式生成唯一ID，保证业务数据的唯一性。