MyBatis-Plus雪花算法实现源码解析

1. 雪花算法（Snowflake Algorithm）

雪花算法（Snowflake Algorithm）是一种用于生成唯一标识符（ID）的分布式算法。最初由 Twitter 公司开发，用于生成其内部分布式系统中的唯一ID。雪花算法的设计目标是在分布式系统中生成全局唯一的ID，同时保证ID的有序性和趋势递增。

雪花算法生成的ID是64位的整数，分为以下几个部分：

1. 符号位（1位） 为了适配部分预研没有无符号整数，所以这一位空缺，并且一般为0。
2. 时间戳（41位）： 使用当前时间戳，精确到毫秒级别。这可以确保在一定时间内生成的ID是唯一的。由于使用的是41位，所以雪花算法可以支持68年的唯一ID生成（2^41毫秒，大约69.7年）。
3. 机器ID（10位）： 分配给生成ID的机器的唯一标识符。这样可以确保在同一时间戳内，不同机器生成的ID不会冲突。一般情况下，需要提前配置每台机器的唯一标识符，然后在运行时使用。
4. 序列号（12位）： 在同一时间戳内，同一机器上生成的ID的序列号。用于防止同一毫秒内生成的ID发生冲突。当在同一毫秒内生成多个ID时，通过递增序列号来区分它们。

雪花算法生成的ID具有以下特点：

• 全局唯一性： 在整个分布式系统中，每个生成的ID都是唯一的。
• 有序性： 由于时间戳占据了大部分位数，生成的ID是趋势递增的，使得生成的ID在数据库索引上有较好的性能。
• 分布式： 不同机器上生成的ID不会冲突，可以在分布式系统中使用。

2. 流程

2.1 MyBatis-Plus全局唯一ID生成器初始化

MyBatis-Plus启动后，会通过IdentifierGeneratorAutoConfiguration类进行项目的自动配置。

注意：IdentifierGeneratorAutoConfiguration类是被@Lazy注解了，所以他是懒加载，所以有的项目会在启动后往日志表插入一条记录来预热MyBatis-Plus

自动配置的内容是往项目注入Bean，该Bean主要是用于全局唯一ID的生成。其中传入的参数是第一个非回环地址的InetAddress类

注意：IdentifierGenerator是接口，DefaultIdentifierGenerator是其一个实现类

@Bean
@ConditionalOnMissingBean
public IdentifierGenerator identifierGenerator(InetUtils inetUtils) {
    return new DefaultIdentifierGenerator(inetUtils.findFirstNonLoopbackAddress());
}

会直接生成一个Sequence

public DefaultIdentifierGenerator(InetAddress inetAddress) {
    this.sequence = new Sequence(inetAddress);
}

这是Sequence的构造器。它会设置datacenterId与workerId

public Sequence(InetAddress inetAddress) {
    this.inetAddress = inetAddress;
    this.datacenterId = getDatacenterId(maxDatacenterId);
    this.workerId = getMaxWorkerId(datacenterId, maxWorkerId);
    // 打印初始化语句
    initLog();
}

这是datacenterId的获取部分，里面可以看到它主要是mac地址混淆得到

注意：这里得到的datacenterId还没有经过截取，是64位的

/**
* 数据标识id部分
*/
protected long getDatacenterId(long maxDatacenterId) {
long id = 0L;
try {
    if (null == this.inetAddress) {
        this.inetAddress = InetAddress.getLocalHost();
    }
    NetworkInterface network = NetworkInterface.getByInetAddress(this.inetAddress);
    if (null == network) {
        id = 1L;
    } else {
        // 获取mac地址
        byte[] mac = network.getHardwareAddress();
        // 混淆
        if (null != mac) {
            id = ((0x000000FF & (long) mac[mac.length - 2]) | (0x0000FF00 & (((long) mac[mac.length - 1]) << 8))) >> 6;
            id = id % (maxDatacenterId + 1);
        }
    }
} catch (Exception e) {
    logger.warn(" getDatacenterId: " + e.getMessage());
}
return id;
}

这是获取workerId的方法，可以看到workerId是由mac地址和JVM-PID共同混淆得出的

/**
 * 获取 maxWorkerId
 */
protected long getMaxWorkerId(long datacenterId, long maxWorkerId) {
    StringBuilder mpid = new StringBuilder();
    mpid.append(datacenterId);
    String name = ManagementFactory.getRuntimeMXBean().getName();
    if (StringUtils.isNotBlank(name)) {
        /*
         * GET jvmPid
         */
        mpid.append(name.split(StringPool.AT)[0]);
    }
    /*
     * MAC + PID 的 hashcode 获取16个低位
     */
    return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);
}

2.2 获取全局唯一ID流程

注意：若之前没有获取过全局唯一ID，那么它会走一遍2.1的全部流程。

如果是使用MyBatis-Plus的IdType.ASSIGN_ID会到IdWorker类中获取全局唯一ID

其中，会调用以下方法获取全局唯一ID(long)

/**
 * 获取唯一ID
 *
 * @return id
 */
public static long getId(Object entity) {
    return IDENTIFIER_GENERATOR.nextId(entity).longValue();
}

进入nextId方法的具体实现，发现它是使用sequence的nextId方法

@Override
public Long nextId(Object entity) {
    return sequence.nextId();
}

下面包含一些自己的注释

注意：nextId方法是被synchronized修饰的，是同步方法

/**
 * 获取下一个 ID
 *
 * @return 下一个 ID
 */
public synchronized long nextId() {
    long timestamp = timeGen();
    // 闰秒
    // 这里会判断是否发生时钟偏移，若偏移在5ms以内会重新尝试重新获取时间，看是否能够重新获取正确的时间。
    // 因为偶尔会有闰秒的存在
    if (timestamp < lastTimestamp) {
        long offset = lastTimestamp - timestamp;
        if (offset <= 5) {
            try {
                wait(offset << 1);
                timestamp = timeGen();
                if (timestamp < lastTimestamp) {
                    throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));
                }
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        } else {
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));
        }
    }

    if (lastTimestamp == timestamp) {
        // 相同毫秒内，序列号自增
        sequence = (sequence + 1) & sequenceMask;
        if (sequence == 0) {
            // 同一毫秒的序列数已经达到最大
            // 序列数(毫秒内自增位)为12位，最大每毫秒分配2048个
            // 序列数最大的时候会等待到下一毫秒才会分配时间戳
            timestamp = tilNextMillis(lastTimestamp);
        }
    } else {
        // 不同毫秒内，序列号置为 1 - 2 随机数
        // 这里序列号置为1-2的随机数是为了方便后续分库分表的时候hash比较均匀
        sequence = ThreadLocalRandom.current().nextLong(1, 3);
    }

    lastTimestamp = timestamp;

    // twepoch 是 时间起始标记点，作为基准，一般取系统的最近时间（一旦确定不能变动）
    // 因为前面已经说过41位的时间戳可以分配69.7年，如果从1970.1.1开始数，那么时间戳可能在未来某一天大于41位
    // 时间戳部分 | 数据中心部分 | 机器标识部分 | 序列号部分
    return ((timestamp - twepoch) << timestampLeftShift)
        | (datacenterId << datacenterIdShift)
        | (workerId << workerIdShift)
        | sequence;
}

这是生成时间的方法，其中使用了SystemClock，这是一个有趣的实现

protected long timeGen() {
    return SystemClock.now();
}

SystemClock类，这个类的主要思想就是用一个任务线程池以固定速率去获取系统时间，若在同一时间间隔内，那么直接返回，而不需要再次访问系统时间。其实主要是因为System.currentTimeMillis()是jni方法，jni方法由于存在内存复制和数据转换，所以是比较耗时的。

/**
 * 高并发场景下System.currentTimeMillis()的性能问题的优化
 *
 * <p>System.currentTimeMillis()的调用比new一个普通对象要耗时的多（具体耗时高出多少我还没测试过，有人说是100倍左右）</p>
 * <p>System.currentTimeMillis()之所以慢是因为去跟系统打了一次交道</p>
 * <p>后台定时更新时钟，JVM退出时，线程自动回收</p>
 * <p>10亿：43410,206,210.72815533980582%</p>
 * <p>1亿：4699,29,162.0344827586207%</p>
 * <p>1000万：480,12,40.0%</p>
 * <p>100万：50,10,5.0%</p>
 *
 * @author hubin
 * @since 2016-08-01
 */
public class SystemClock {
	// 定期更新时间戳的时间单位
    private final long period;
    // 记录当前时间戳的原子类，因为可能存在并发线程使用
    private final AtomicLong now;
	
    private SystemClock(long period) {
        this.period = period;
        this.now = new AtomicLong(System.currentTimeMillis());
        scheduleClockUpdating();
    }

    private static SystemClock instance() {
        return InstanceHolder.INSTANCE;
    }

    public static long now() {
        return instance().currentTimeMillis();
    }

    public static String nowDate() {
        return new Timestamp(instance().currentTimeMillis()).toString();
    }
	
    // 这里是有一个定期更新方法
    // 里面有一个定时线程池，它会以固定的时间间隔(period)在类里面更新当前的时间戳
    private void scheduleClockUpdating() {
        ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor(runnable -> {
            Thread thread = new Thread(runnable, "System Clock");
            thread.setDaemon(true);
            return thread;
        });
        scheduler.scheduleAtFixedRate(() -> now.set(System.currentTimeMillis()), period, period, TimeUnit.MILLISECONDS);
    }

    // 获取事件
    private long currentTimeMillis() {
        return now.get();
    }

    // 默认事件间隔为1ms
    private static class InstanceHolder {
        public static final SystemClock INSTANCE = new SystemClock(1);
    }
}

至此，已经介绍完MyBatis-Plus获取全局唯一ID的实现。如有错误，烦请指出。