雪花算法生成分布式 ID

前言

为了加快数据库的查询速度，主键和索引的选择也是相当重要的一部分，此文介绍几个常见的分布式 id 生成方案，并讲述几种雪花算法的实现形式。经过综合权衡，当数据量较大时，使用雪花算法生成分布式 id 能够在确保安全性的同时保持较优的查询性能，是一种比较适合目前实际应用的 id 生成算法。

分布式 ID 基本规则

1. 全局唯一性：不能出现重复的 id

2. 递增性：MySQL 的 InnoDB 使用的是聚簇索引，由于多数 RDBMS 使用 B-tree 的数据结构来存储索引数据，因此在主键的选择上我们还是应该尽可能地使用有序的主键来保证写入性能，我们保证下一个 id 一定大于上一个 id，以此来满足事务版本号、IM 增量消息或者排序的特殊需求

3. 安全性：如果 id 是连续的，那么我们在知道一些基本规则的情况下就能很轻松地推测出下一份数据，这在一些机密性较高的业务场景是很危险的。所以我们有时会希望 id 是无规则的，最好还能包含有时间戳，这样就能够在开发中快速了解这个分布式 id 的生成时间

4. 高性能高可用性：确保在任何时候都能正确地生成 id，并且在高并发的环境下也能表现良好

常见分布式 ID 方案

UUID（Universally Unique Identifier）

核心思想：基于机器网卡、当地时间和随机数生成 UUID。

优点

1. 全局唯一：UUID 可以为分布式系统提供全局唯一的标识符，避免了 id 冲突的问题；
2. 生成简单：UUID 的生成不需要中央协调机制，因此可以在任何时间和地点生成 UUID；
3. 安全性高：UUID 的生成使用了随机性或伪随机性的元素，生成的 UUID 具有高度随机性，不容易被猜测到。因此可以在安全领域中使用。

缺点

1. 存储空间大：存储 UUID 值（16 字节）比整数（4 字节）甚至大整数（8 字节）需要更多的存储空间；
2. 性能问题：UUID 的生成算法比较复杂，在一定程度上影响了性能；
3. 无序查询效率低：UUID 由于自身的随机性，每次插入新记录时，新的记录可能会被插入到索引树的不同位置，导致索引的不连续性，会造成索引叶子结点频繁分裂、合并，降低了查询性能，不适合作为索引。

数据库自增 ID

核心思想：使用数据库的自增字段，如 MySQL 的 auto_increment。

优点

1. 简单：易于实现，数据库系统可以直接生成；
2. 占用空间小：自增 id 通常存储为整数，占用空间小；
3. 天然有序：自动增长，有序索引效率高。

缺点

1. 可预测性：自增 id 的可预测性可能导致安全问题，如通过 id 猜测其他记录的存在；
2. 分布式系统中的问题：在分布式系统中，多个数据库实例可能会产生冲突的自增 id。

雪花算法

核心思想：由 Twitter 开发，使用时间戳、数据中心 id、机器 id 和序列号生成 64 位 id。

优点

1. 趋势递增：毫秒数在高位，自增序列在低位，整个 id 都是趋势递增的；
2. 生成简单：可以不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成 id 的性能也非常高；
3. 灵活：可以根据自身业务特性分配 bit 位，非常灵活。

缺点

1. 强依赖机器时钟：如果机器上时钟回拨，会导致发号重复或者服务处于不可用状态。

雪花算法原理

雪花算法共 64 bit，具体包括：

• 41bit 毫秒时间戳 (1L << 41) / (1000L * 3600 * 24 * 365)，共可以使用 69 年

• 5bit 数据中心 id（最大值为 31）

• 5bit 机器 id（最大值为 31）

• 12bit 顺序编码 （最大值为 4095）

其中，数据中心 id 与机器 id 可以合并作为 10 bit 的机器 id 使用。

实现方法

自定义实现

/**
 * Twitter_Snowflake<br>
 * SnowFlake的结构如下(每部分用-分开):<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
 * 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0<br>
 * 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)
 * 得到的值），这里的的开始时间截，一般是的id生成器开始使用的时间，由程序来指定的（如下下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
 * 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId<br>
 * 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号<br>
 * 加起来刚好64位，为一个Long型。<br>
 * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。
 */
public class SnowflakeUtil {

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

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

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

    /** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
    private static final long MAX_WORKER_ID = ~(-1L << WORKER_ID_BITS);

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

    /** 序列在id中占的位数 */
    private static final long SEQUENCE_BITS = 12L;

    /** 机器ID向左移12位 */
    private static final long WORKER_ID_SHIFT = SEQUENCE_BITS;

    /** 数据标识id向左移17位(12+5) */
    private static final long DATACENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS;

    /** 时间截向左移22位(5+5+12) */
    private static final long TIMESTAMP_LEFT_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATACENTER_ID_BITS;

    /** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */
    private static final long SEQUENCE_MASK = ~(-1L << SEQUENCE_BITS);

    /** 工作机器ID(0~31) */
    private static long workerId;

    /** 数据中心ID(0~31) */
    private static long datacenterId;

    /** 毫秒内序列(0~4095) */
    private static long sequence = 0L;

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

    //==============================Constructors=====================================
    /**
     * 构造函数
     * @param workerId 工作ID (0~31)
     * @param datacenterId 数据中心ID (0~31)
     */
    public SnowflakeUtil(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));
        }
        SnowflakeUtil.workerId = workerId;
        SnowflakeUtil.datacenterId = datacenterId;
    }

    // ==============================Methods==========================================
    /**
     * 获得下一个ID (该方法是线程安全的)
     * @return SnowflakeId
     */
    public static synchronized long nextId() {
        long timestamp = timeGen();

        //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(
                    String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }

        //如果是同一时间生成的，则进行毫秒内序列
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & SEQUENCE_MASK;
            //毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        //时间戳改变，毫秒内序列重置
        else {
            sequence = 0L;
        }

        //上次生成ID的时间截
        lastTimestamp = timestamp;

        //移位并通过或运算拼到一起组成64位的ID
        return ((timestamp - START_STAMP) << TIMESTAMP_LEFT_SHIFT) //
                | (datacenterId << DATACENTER_ID_SHIFT) //
                | (workerId << WORKER_ID_SHIFT) //
                | sequence;
    }


    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    protected static long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 返回以毫秒为单位的当前时间
     * @return 当前时间(毫秒)
     */
    protected static long timeGen() {
        return System.currentTimeMillis();
    }
}

调用静态方法 nextId() 即可获得。

使用 IdWorker 类生成

IdWorker 类在包 com.baomidou.mybatisplus.core.toolkit 中，项目中需要增加 mybatis-plus 依赖项，直接使用 IdWorker.getId() 方法即可获得。

通过 @TableId 注释生成

在使用 @TableId 设置主键映射时：

• value 映射主键字段的名字

• type 设置主键类型、主键的生成策略

  值	描述
  AUTO	数据库自增
  NONE	MP set主键，雪花算法实现
  INPUT	需要手动赋值
  ASSIGN_ID	MP分配ID，Long、Integer、String
  ASSIGN_UUID	分配UUID，String

可设定 type 为 ASSIGN_ID 自动生成雪花 id。

注意

mybatis-plus 在没有设置机器号的情况下，会通过当前物理网卡地址和 jvm 的进程 id 自动生成机器号，以保证在一个集群中生成的 id 唯一性。但仍有可能会出现自动生成的机器号相同的情况，此时为了保证唯一性，需要手动修改机器号。

参考文章

CSDN - MySQL 数据表主键设计，选择自增 id 还是 UUID 还是雪花 id？

CSDN - MySQL主键：自增ID与UUID的选择

CSDN - 深度思考：雪花算法snowflake分布式id生成原理详解

CSDN - mybatis的分布式主键冲突