分布式Id生成器

Id生成的几种方式

• 数据库自增
  • 优势
    • 简单，无需额外操作
    • 保持定长自增
    • 保持单表唯一性
  • 劣势
    • 主键生成依赖数据库，高并发下会造成数据库服务器压力较大
    • 水平扩展困难，在分布式数据库环境下，无法保证唯一性

• UUID（GUID）

  • 优势
    • 本地生成，无需远程调用（无需网络通信）
    • 全局唯一
    • 水平扩展好
  • 劣势
    • ID 128 bits，占用空间大
    • 字符串类型，索引效率低
    • 无法保证趋势递增

• 时间戳

  略

• Twitter Snowflake 雪花算法

  • 优势
    • 本地生产，无需远程调用（无需网络通信）
    • 单机每秒可生成400w个ID
    • ID 64 bits，占用空间小
    • long类型，对索引效率有提升
    • 趋势递增
  • 劣势
    • 时间回拨问题
    • 集群部署时，集群内机器时间同步问题

基于雪花算法的分布式Id生成器实现

import java.util.Calendar;

/**
 * 该生成器采用 Twitter Snowflake 算法实现，生成 64 Bits 的 Long 型编号
 * <pre>
 *     1 bit        41 bits     10 bits     12 bits
 *     sign bit     时间戳       工作ID       序列号ID
 * </pre>
 *
 * @author YL
 */
public final class SnowflakeKeyGenerator implements KeyGenerator {
    /**
     * 基准时间：时间偏移量
     */
    private static final long EPOCH;

    static {
        // 从2017年01月01日零点开始
        Calendar calendar = Calendar.getInstance();
        calendar.set(2017, Calendar.JANUARY, 1);
        calendar.set(Calendar.HOUR_OF_DAY, 0);
        calendar.set(Calendar.MINUTE, 0);
        calendar.set(Calendar.SECOND, 0);
        calendar.set(Calendar.MILLISECOND, 0);
        EPOCH = calendar.getTimeInMillis();
    }

    /**
     * 序列号ID位数
     */
    private static final long SEQUENCE_BITS = 12L;
    /**
     * 工作ID位数
     */
    private static final long WORKER_ID_BITS = 10L;

    /**
     * 序列号ID最大值
     */
    private static final long SEQUENCE_MASK = (1 << SEQUENCE_BITS) - 1;
    /**
     * 工作ID最大值
     */
    private static final long WORKER_ID_MAX_VALUE = 1L << WORKER_ID_BITS;

    /**
     * 工作ID左移12位
     */
    private static final long WORKER_ID_LEFT_SHIFT_BITS = SEQUENCE_BITS;
    /**
     * 时间戳左移22数
     */
    private static final long TIMESTAMP_LEFT_SHIFT_BITS = WORKER_ID_LEFT_SHIFT_BITS + WORKER_ID_BITS;

    /**
     * 序列号ID
     */
    private long sequence;
    /**
     * 序列号ID偏移量
     */
    private byte sequenceOffset;
    /**
     * 最后生成编号时间戳，单位：毫秒
     */
    private long lastTime;

    /**
     * 工作ID
     */
    private long workerId;

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

    /**
     * 生成 ID
     *
     * @return 返回@{@link Long}类型的Id
     */
    @Override
    public synchronized long nextId() {
        // 保证当前时间大于最后时间。时间回退会导致产生重复id
        long currentMillis = System.currentTimeMillis();
        if (currentMillis < this.lastTime) {
            throw new IllegalArgumentException(String.format("clock moved backwards.Refusing to generate id for %d " +
                            "milliseconds",
                    (this.lastTime - currentMillis)));
        }

        // 获取序列号
        if (this.lastTime == currentMillis) {
            // 当获得序号超过最大值时，归0，并去获得新的时间
            if (0L == (this.sequence = ++this.sequence & SEQUENCE_MASK)) {
                currentMillis = tailNextMillis(currentMillis);
            }
        } else {
            // 1、在跨毫秒时，序列号总是归0，导致序列号为0的ID较多，导致生成的ID取模后不均匀
            // this.sequence = 0;
            // 2、序列号取[0-9]之间的随机数，可以初步解决【1】中的问题，也会导致ID取模不均匀
            // this.sequence = new SecureRandom().nextInt(10);
            // 3、交替使用[0-1]
            this.sequence = vibrateSequenceOffset();
        }
        // 设置最后时间戳
        this.lastTime = currentMillis;
        // 生成编号
        return ((currentMillis - EPOCH) << TIMESTAMP_LEFT_SHIFT_BITS)
                | (this.workerId << WORKER_ID_LEFT_SHIFT_BITS)
                | this.sequence;
    }

    /**
     * 不停获得时间，直到大于最后时间
     * <p>
     * 从 Snowflake 的官方文档 (https://github.com/twitter/snowflake/#system-clock-dependency) 中也可以看到, 它明确要求 "You should
     * use NTP to keep your system clock accurate". 而且最好把 NTP 配置成不会向后调整的模式. 也就是说, NTP 纠正时间时, 不会向后回拨机器时钟.
     * ntpd 和 ntpdate 的区别，使用 ntpd 影响不大
     * todo 如果时间回拨，会导致这个逻辑等待，等待时间可能会很长
     * </p>
     *
     * @param lastTime 最后时间
     *
     * @return 时间
     */
    private long tailNextMillis(final long lastTime) {
        long time = System.currentTimeMillis();
        while (time <= lastTime) {
            time = System.currentTimeMillis();
        }
        return time;
    }

    /**
     * 只会交替返回0和1
     */
    private byte vibrateSequenceOffset() {
        this.sequenceOffset = (byte) (~this.sequenceOffset & 1);
        return this.sequenceOffset;
    }
}