简介：

本文介绍了snowflake算法，优缺点，以及应用场景。

传统的集中式系统中，ID 生成通常由一个单一的服务器完成，导致服务存在单点故障的问题。当系统规模扩大后，单一服务器可能无法处理高并发请求。而分布式 ID 生成算法旨在解决这一问题，其中每个节点都能并行工作独立生成ID，是去中心化的。分布式系统中，有需要使用全局唯一 ID 的场景。 UUID ,Snowflake 或 Leaf 算法独立生成ID

其中雪花算法，能按照时间生成有序的ID。

雪花算法

Snowflake 算法是 Twitter开源的分布式 ID 生成算法算法生成一个64bit 的long型数值，组成部分引入了时间戳，基本保持了自增。

优点

高性能高可用：可在内存生成ID，不依赖数据库。
高吞吐：雪花算法生成ID主要依赖简单的位移操作，速度极快。
有序性：生成的ID的高位是时间戳，可以作为索引存入缓存中。

缺点

对机器时间依赖较强：系统时钟的精度和一致性非常关键，如果服务器时钟出现回调或不同步，可能会导致ID 重复或生成顺序混乱
有时间限制：41位时间戳只能使用约69年，超过这个时间可能需要手动调整纪元时间。

雪花 ID 结构

默认的雪花算法生成64bit的ID

| 1位符号位 | 41位时间戳 | 10位机器标识 | 12位序列号 |

符号位：最高位是符号位，0表示正，1表示负，该位固定为0，用于保持生成的ID为正数。

时间戳：毫秒级的时间戳，由一个纪元时间（Epoch）开始计算到当前时间的毫秒数。从定义的纪元时间开始，最多支持69年的时间。

机器标识：用于区分分布式系统中不同的机器或者节点，10位可以支持 2^10 = 1024个不同机器或节点。通常，10位的机器标识被分为两部分，5位的数据中心ID 和 5位机器ID。这样可以支持32个数据中心中的32台机器。

序列号：用于在同一毫秒中生成多个ID，避免时间戳出现冲突。12位可以支持每台机器每毫秒中生成 2^12 = 4096个唯一ID。（当同一台机器在同一毫秒中生成的ID超过4096个，机器会等待下一毫秒继续生成新的ID。

雪花ID的长度是可以自行配置的，可以根据具体场景进行设计。希望服务运行更久，可以增加时间戳的位数。想要支持更多节点，增加标识位长度。高并发场景，增加序列号位数。

雪花ID适用场景

因为雪花算法有序自增，在MYSQL中 B+树索引可以高性能插入，所以在日常使用中，雪花算法更多是被应用在数据库的主键 ID 和业务关联主键且雪花ID每秒能生成 4096 * 1000 = 409w 个ID，适用于高并发场景

雪花ID常见问题

生成ID重复问题

服务器通过集群的方式部署，其中部分机器标识位一致
业务存在一定的并发量，没有并发量无法触发问题
同一毫秒下生成

标识位重复定义

开源框架中如MyBatis和Hutool使用雪花算法，都实现了不重复标识位的构造方法。 MyBatis-Plus v3.4.2 雪花算法实现类 Sequence，提供了两种构造方法：无参构造 -> 自动生成dataCenterId 和 workerId 有参构造 -> 创建Sequence时明确指定标识位

Sequence默认的无参构造，生成了dataCenterId和Iworkerd

public static long getDataCenterId(long maxDatacenterId) {
    long id = 1L;
    final byte[] mac = NetUtil.getLocalHardwareAddress();
    if (null != mac) {
        id = ((0x000000FF & (long) mac[mac.length - 2])
                | (0x0000FF00 & (((long) mac[mac.length - 1]) << 8))) >> 6;
        id = id % (maxDatacenterId + 1);
    }

    return id;
}

DatacenterId的取值与设备Mac地址有关

public static long getWorkerId(long datacenterId, long maxWorkerId) {
    final StringBuilder mpid = new StringBuilder();
    mpid.append(datacenterId);
    try {
    // 获取进程PID
        mpid.append(RuntimeUtil.getPid());
    } catch (UtilException igonre) {
        //ignore
    }
    return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);
}

WorkerId是MAC+PID的hashcode，获取16个低位

标识符分配

依赖MAC地址和进程PID的标识符仍然有小几率重复，为了解决这个问题，可以用 预分配和动态分配 的方法。

预分配 是在应用上线前，统计当前服务的节点数，人工的申请标识位。但是无法解决服务节点动态扩展的问题。

动态分配 将标识位存放在Redis、Zookeeper、MySQL等中间件，在服务启动时请求标识位。但要注意生成的ID是 服务内唯一 还是 全局唯一 全局唯一 可能会导致单点故障问题。

常见的实现是 Redis + Lua 脚本，在应用启动时，通过Lua脚本获取标识位。

简介：