用java实现雪花算法

雪花算法（Snowflake）是Twitter开发的一种分布式唯一ID生成算法，其核心思想是将一个64位的Long型ID分成5个部分，每个部分可以表示不同的信息，如下表：

| 符号位 | 时间戳 | 数据中心ID | 机器ID | 序列号 |
| ------ | ------ | ---------- | ------ | ------ |
| 1位 | 41位 | 5位 | 5位 | 12位 |

其中，时间戳部分占用了41位，可以表示2^41-1个数字，即可以使用69年的时间。数据中心ID部分和机器ID部分可以自行定义，一般情况下，数据中心ID和机器ID可以使用IP地址或者机器名等信息来确定。序列号部分占用12位，可以表示4095个数字，如果在同一毫秒内生成了超过4095个ID，需要等待下一毫秒再进行生成。

下面是用Java实现雪花算法的代码：

public class SnowflakeIdGenerator {

    // 开始时间截 (2015-01-01)
    private static final long START_TIMESTAMP = 1420041600000L;

    // 机器id所占的位数
    private static final long MACHINE_BIT = 5L;

    // 数据标识id所占的位数
    private static final long DATACENTER_BIT = 5L;

    // 支持的最大机器id，结果是31
    private static final long MAX_MACHINE_ID = -1L ^ (-1L << MACHINE_BIT);

    // 支持的最大数据标识id，结果是31
    private static final long MAX_DATACENTER_ID = -1L ^ (-1L << DATACENTER_BIT);

    // 序列号所占的位数
    private static final long SEQUENCE_BIT = 12L;

    // 机器id向左移12位
    private static final long MACHINE_LEFT = SEQUENCE_BIT;

    // 数据标识id向左移17位(12+5)
    private static final long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;

    // 时间戳向左移22位(5+5+12)
    private static final long TIMESTAMP_LEFT = SEQUENCE_BIT + MACHINE_BIT + DATACENTER_BIT;

    // 生成序列的掩码，这里为4095
    private static final long SEQUENCE_MASK = -1L ^ (-1L << SEQUENCE_BIT);

    // 数据标识id
    private long datacenterId;

    // 机器id
    private long machineId;

    // 序列号
    private long sequence = 0L;

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

    public SnowflakeIdGenerator(long datacenterId, long machineId) {
        // 数据标识id的范围是0~31
        if (datacenterId > MAX_DATACENTER_ID || datacenterId < 0) {
            throw new IllegalArgumentException("datacenterId can't be greater than " + MAX_DATACENTER_ID + " or less than 0");
        }
        // 机器id的范围是0~31
        if (machineId > MAX_MACHINE_ID || machineId < 0) {
            throw new IllegalArgumentException("machineId can't be greater than " + MAX_MACHINE_ID + " or less than 0");
        }
        this.datacenterId = datacenterId;
        this.machineId = machineId;
    }

    public synchronized long nextId() {
        long timestamp = timeGen();

        // 如果当前时间小于上一次生成ID的时间戳，说明系统时钟回退过，此时需要抛出异常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException("Clock moved backwards. Refusing to generate id");
        }

        // 如果是同一时间生成的，则进行序列号累加
        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & SEQUENCE_MASK;
            // 如果序列号已经达到最大值，需要等待下一毫秒再进行生成
            if (sequence == 0L) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            // 如果是新的时间戳，则序列号重置为0
            sequence = 0L;
        }

        // 保存当前时间戳作为上一次生成ID的时间戳
        lastTimestamp = timestamp;

        // 生成ID的核心部分，将各个部分进行位运算合并
        return ((timestamp - START_TIMESTAMP) << TIMESTAMP_LEFT) |
                (datacenterId << DATACENTER_LEFT) |
                (machineId << MACHINE_LEFT) |
                sequence;
    }

    // 循环等待下一毫秒的到来
    private long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    // 获取当前的时间戳
    private long timeGen() {
        return System.currentTimeMillis();
    }

}

使用示例：

SnowflakeIdGenerator idGenerator = new SnowflakeIdGenerator(1L, 1L);
long id = idGenerator.nextId();
System.out.println(id);

输出结果：

196745649852950016