常见 ID 生成算法

分布式系统中，经常需要使用 ID 作为数据唯一标识，这时数据库自增就无法满足需求。常见的解决方案有：

• UUID：实现简单，但 32 位无序字符串，性能较差
• 分库起始步长：严重依赖数据库
• SnowFlake：无依赖，64 bit 标识，有序递增

SnowFlake

SnowFlake 是 Twitter 公司所采用的的一种算法，目的是在分布式系统中生成全局唯一且趋势递增的 ID。

SnowFlake 生成的 ID 一共可分为 4 部分：

1. 符号位
   1 bit，始终为 0；
2. 时间戳
   41 bit，精确到毫秒，总共可容纳约 69 年的时间；
3. 工作机器 ID
   10 bit，启动高 5 bit 是数据中心 ID（datacenterId），低 5 bit 是工作节点 ID（workerId），最多可以容纳 1024 个节点；
4. 序列号
   12 bit，同一毫秒同一节点多次执行该算法，从 0 开始依次递增，对多可以累加至 4095；

同一毫秒内可生成全剧唯一 ID 数量：1024 * 4096 = 4194304。

代码实现

import java.time.LocalDateTime;
import java.time.ZoneOffset;
import java.util.concurrent.TimeUnit;

public class SnowFlakeUtils {

    private static final int SERIAL_BIT = 12;
    private static final int DATA_CENTER_BIT = 5;
    private static final int WORK_BIT = 5;
    private static final int TIME_STAMP_BIT = 41;

    /**
     * 对比时间点 2019-05-20 时间戳
     */
    private static long timePoint = LocalDateTime.of(2019, 5, 20, 0, 0, 0).toInstant(ZoneOffset.of("+8")).toEpochMilli();

    /**
     * 1 bit: 符号位
     */
    private static long flag = 0;

    /**
     * 41 bit: 时间戳（毫秒）
     */
    private static long lastTimeStamp = -1L;

    /**
     * 5 bit: 工作机器 ID
     */
    private static long dataCenterId = 1;
    /**
     * 5 bit: 工作机器 ID
     */
    private static long workId = 1;

    /**
     * 12 bit: 序列号
     */
    private static long serial = 0;

    /**
     * 序列号 mask，防止溢出
     */
    private static final long SERIAL_MASK = ~(-1L << SERIAL_BIT);

    public static synchronized long uniqueId() {
        long currentTimeStamp = System.currentTimeMillis() - timePoint;
        if (lastTimeStamp == currentTimeStamp) {
            // 同一毫秒，序列号递增
            long temp = (serial + 1) & SERIAL_MASK;
            if (temp == 0) {
                // 当前毫秒内序列已满，重新获取
                sleep();
                return uniqueId();
            }
            serial = temp;
        } else {
            lastTimeStamp = currentTimeStamp;
            serial = 0L;
        }
        return serial
                | (workId << SERIAL_BIT)
                | (dataCenterId << SERIAL_BIT + WORK_BIT)
                | (lastTimeStamp << (SERIAL_BIT + WORK_BIT + DATA_CENTER_BIT))
                | (flag << (SERIAL_BIT + WORK_BIT + DATA_CENTER_BIT + TIME_STAMP_BIT));
    }

    private static void sleep() {
        try {
            TimeUnit.MILLISECONDS.sleep(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

注意序列号生成防止溢出，使用了 SERIAL_MASK，当序列值当前毫秒已经使用满时，手动休眠 1 毫秒后重复获取即可。