【Mysql】雪花算法（Snowflake）

一、基本概念

雪花算法（Snowflake）是一种生成全局唯一ID的分布式算法。它的主要功能是在分布式系统中生成一个全局唯一的ID，且ID是按照时间有序递增的。

Snowflake 中文的意思为雪花，所以 Snowflake算法 常被称为 雪花算法，是 Twitter（现“X”）开源的分布式 ID 生成算法，是一种分布式主键ID生成的解决方案。

雪花算法

生成后是一个 64bit 的 long 型的数值，组成部分引入了时间戳，基本保持了自增。

互联网大厂实现的雪花开源项目：

美团 Leaf：https://github.com/Meituan-Dianping/Leaf

百度 Uid：https://github.com/baidu/uid-generator

二、核心思想

Snowflake算法使用一个64位的二进制数字作为ID。这64位long型ID被分割成四个部分：符号位、时间戳、工作机器ID、序列号。通过这几部分来表示不同的信息，将数据映射到具有特定结构的分布式系统中，实现数据的存储和查询。

该算法由一系列节点组成，每个节点负责存储数据的一部分。这些节点通过哈希函数将数据映射到特定的位置，形成类似于雪花结构的分布式系统。通过这种方式，雪花算法能够在分布式系统中保证ID的唯一性和有序性。

**因为

雪花算法

有序自增，保障了 MySQL 中 B+ Tree 索引结构插入高性能。所以，日常业务使用中，

雪花算法

更多是被应用在数据库的主键 ID 和业务关联主键。**

上面有说过

雪花算法

会生成 64bit 的 long 型的数值，而这64bit 可以分为四个组成部分：

固定值：

1bit，最高位是符号位，0 表示正，1 表示负，固定为 0，如果是 1 就是负数了。

第一位为什么不使用

在雪花算法中，第一位是符号位，0表示整数，第一位如果是1则表示负数，我们用的ID默认就是正数，所以默认就是0，那么这一位默认就没有意义。

时间戳：

41bit，存储毫秒级时间戳（41 位的长度可以使用 69 年）。

标识位（存储机器码）：

10bit，上面中的 机器id（5bit）和 服务id（5bit）统一叫作“标识位”，两个标识位组合起来最多可以支持部署 1024 个节点。

标识位怎么用

标识位一共10 bit，如果全部表示机器，那么可以表示1024台机器，如果拆分，5 bit 表示机房，5bit表示机房里面的机器，那么可以有32个机房，每个机房可以用32台机器。

序列号：

12bit，用于表示在同一毫秒内生成的多个ID的序号。如果在同一毫秒内生成的ID超过了4096个（2的12次方），则需要等到下一毫秒再生成ID。

默认的

雪花算法

是 64 bit，具体的长度可以自行配置。

如果希望运行更久，增加时间戳的位数；如果需要支持更多节点部署，增加标识位长度；如果并发很高，增加序列号位数。

总结：

雪花算法

并不是一成不变的，可以根据系统内具体场景进行定制。

三、为何要使用雪花算法

​现在的服务基本是分布式、微服务形式的，而且大数据量也导致分库分表的产生，对于水平分表就需要保证表中 id 的全局唯一性。 对于 MySQL 而言，一个表中的主键 id 一般使用自增的方式，但是如果进行水平分表之后，多个表中会生成重复的 id 值。那么如何保证水平分表后的多张表中的 id 是全局唯一性的呢？

1，数据库主键自增：
可以让不同表初始化一个不同的初始值，然后按指定的步长进行自增。
例如有3张拆分表，初始主键值为1，2，3，自增步长为3。

2，UUID：
用 UUID 来作为主键，但是 UUID 生成的是一个无序的字符串，
对于 MySQL 推荐使用增长的数值类型值作为主键来说不适合。

3，Redis：
使用 Redis 的自增原子性来生成唯一 id，但是这种方式业内比较少用。

当然还有其他解决方案，不同互联网公司也有自己内部的实现方案。雪花算法广泛应用于分布式系统中的唯一ID生成。它可以保证在分布式环境中生成的ID是唯一且有序的。常见的应用场合包括订单号生成、分布式数据库中的数据主键、分布式锁等。通过使用雪花算法生成全局唯一ID，可以方便地进行分布式系统的数据管理和查询。

优点：

缺点：

依赖服务器时间，服务器时间回拨时可能会生成重复 id。

小小的解决方案：算法中可通过记录最后一个生成 id 时的时间戳来解决，
每次生成 id 之前比较当前服务器时钟是否被回拨，避免生成重复 id。

由于时间回拨导致的生产重复的ID的问题，其实百度和美团都有自己的解决方案了，有兴趣可以去看看。

美团 Leaf：

https://github.com/Meituan-Dianping/Leaf

百度 Uid：

https://github.com/baidu/uid-generator

四、代码实现

以下是雪花算法的Java代码实现示例：

public class SnowflakeIdWorker{
    /** 开始时间截 (2015-01-01) */
    private final long twepoch = 1288834974657L;
 
    /** 机器id所占的位数 */
    private final long workerIdBits = 5L;
 
    /** 数据标识id所占的位数 */
    private final long datacenterIdBits = 5L;
 
    /** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
 
    /** 支持的最大数据标识id，结果是31 */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
 
    /** 序列在id中占的位数 */
    private final long sequenceBits = 12L;
 
    /** 机器ID向左移12位 */
    private final long workerIdShift = sequenceBits;
 
    /** 数据标识id向左移17位(12+5) */
    private final long datacenterIdShift = sequenceBits + workerIdBits;
 
    /** 时间截向左移22位(5+5+12) */
    private final long timestampLeftShift = sequenceBits + workerIdBits
            + datacenterIdBits;
 
    /** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);
 
    /** 工作机器ID(0~31) */
    private long workerId;
 
    /** 数据中心ID(0~31) */
    private long datacenterId;
 
    /** 毫秒内序列(0~4095) */
    private long sequence = 0L;
 
    /** 上次生成ID的时间截 */
    private long lastTimestamp = -1L;
 
    /**
     * 构造函数
     *
     * @param workerId
     *            工作ID (0~31)
     * @param datacenterId
     *            数据中心ID (0~31)
     */
    public SnowflakeIdWorker(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format(
                    "worker Id can't be greater than %d or less than 0",
                    maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format(
                    "datacenter Id can't be greater than %d or less than 0",
                    maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }
 
    /**
     * 获得下一个ID (该方法是线程安全的)
     *
     * @return SnowflakeId
     */
    public 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) & sequenceMask;
            // 毫秒内序列溢出
            if (sequence == 0) {
                // 阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        // 时间戳改变，毫秒内序列重置
        else {
            sequence = 0L;
        }
 
        // 上次生成ID的时间截
        lastTimestamp = timestamp;
 
        // 移位并通过或运算拼到一起组成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (datacenterId << datacenterIdShift) //
                | (workerId << workerIdShift) //
                | sequence;
    }
 
    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     *
     * @param lastTimestamp
     *            上次生成ID的时间截
     * @return 当前时间戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }
 
    /**
     * 返回以毫秒为单位的当前时间
     *
     * @return 当前时间(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }
 
    //测试方法
    public static void main(String[] args) {
 
        // 假设我们有一个工作机器ID为1，数据中心ID为1的环境
        long workerId = 1L;
        long datacenterId = 1L;
        
        // 创建一个SnowflakeIdWorker实例
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(workerId, datacenterId);
        
        // 生成并打印10个ID作为示例
        for (int i = 0; i < 10; i++) {
            long id = idWorker.nextId();
            System.out.println(id);
        }
    }
 
}

五、总结

雪花算法

依赖于时间的一致性，如果发生时间回拨，可能会导致问题。为了解决这个问题，通常会使用拓展位来扩展时间戳的位数。原本

雪花算法

只能支持69年的时间范围，但根据实际需求，可以增加时间戳的位数来延长可使用的年限，比如使用42位可以支持139年的时间范围。然而，对于很多公司来说，首要任务是生存下来，因此可能会权衡取舍，不过度追求时间戳位数的增加。

需要注意的是，

雪花算法

也有一些缺点。在单机上，生成的ID是递增的，但在多台机器上，只能大致保持递增趋势，并不能严格保证递增。这是因为多台机器之间的时钟不一定完全同步。因此，在多机器环境下，对于严格的递增需求，需要考虑其他解决方案。

总而言之，

雪花算法

是一种常用的分布式唯一ID生成算法，但并非完美解决方案。在使用时，需要根据实际需求和限制条件进行权衡和选择，以寻找适合自己情况的解决方案。