Skip to main content

雪花算法集群环境重复生成问题？

作者：程序员马丁

在线博客：https://open8gu.com

note

大话面试，技术同学面试必备的八股文小册，以精彩回答应对深度问题，助力你在面试中拿个offer。

面试话术​

1. 为什么会重复？​

在分布式环境下，可能因为部署环境的复杂、部署应用节点数过多以及应用并发访问较高，多种组合情况下，就有可能产生雪花算法重复的可能性。

假设一个订单微服务，通过雪花算法生成 ID，共部署三个节点，其中任意两个节点标识位一致。此时有一定的并发，均匀散布三个节点，标识位一致的两个节点同一毫秒同一序列号下生成 ID，那么就会产生重复 ID。

通过上述假设场景，可以知道雪花算法生成 ID 冲突存在一定的前提条件：

  1. 服务通过集群的方式部署，其中部分机器标识位一致。
  2. 业务存在一定的并发量，没有并发量无法触发重复问题。
  3. 生成 ID 的时机：同一毫秒下的序列号一致。

2. 如何实现不重复？​

为了实现服务内或全局唯一的雪花算法 ID 分配，通常将雪花算法标识位存储在中间件如 Redis、Zookeeper 或 MySQL 中。在服务启动时，系统会请求一个标识位，并在成功后更新为下一个可用的位。

这里引出一个重要问题：雪花算法生成的 ID 是服务内唯一还是全局唯一？答案取决于如何管理和分配标识位。

以 Redis 为例，如果需求是服务内唯一，那么只需确保使用的 Redis 节点是当前项目内的即可。但如果要求全局唯一，那么所有使用雪花算法的应用都必须共享同一个 Redis 节点。

两者的主要区别在于是否跨服务共用 Redis。在没有全局唯一需求的情况下，服务内唯一更为推荐，因为这样可以避免单点故障。

在具体实现方面，可以使用 Redis 的 Hash 结构来存储 dataCenterId 和 workerId。启动应用时，通过 Lua 脚本从 Redis 获取并初始化这些标识位。该脚本的逻辑确保了在 1024 节点内，每个 ID 都是唯一的。如果达到 1024，该系统会重新从开始位置继续循环分配。

然而，如果服务节点数量超过 1024，就需要进一步考虑如何扩展。一种方法是增加标识位的位数，例如使用 10 bit 标识位。另一种更为高效的方式是选择使用开源的分布式 ID 框架。

为什么不能超过 1024？因为雪花算法标识位只有 10bit 长度，最多支持 0-1023 的取值。

问题详解​

1. 标识位如何定义​

如果能保证标识位不重复，那么雪花 ID 也不会重复。

通过上面的案例，知道了 ID 重复的必要条件。如果要避免服务内产生重复的 ID，那么就需要从标识位上动文章。

我们先看看开源框架中使用雪花算法，如何定义标识位。

Mybatis-Plus v3.4.2 雪花算法实现类 Sequence，提供了两种构造方法：无参构造，自动生成 dataCenterId 和 workerId；有参构造，创建 Sequence 时明确指定标识位。

Hutool v5.7.9 参照了 Mybatis-Plus dataCenterId 和 workerId 生成方案，提供了默认实现。

一起看下 Sequence 的创建默认无参构造，如何生成 dataCenterId 和 workerId。

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;
}

入参 maxDatacenterId 是一个固定值，代表数据中心 ID 最大值，默认值 31。

为什么最大值要是 31？因为 5bit 的二进制最大是 11111，对应十进制数值 31。

获取 dataCenterId 时存在两种情况，一种是网络接口为空，默认取 1L；另一种不为空，通过 Mac 地址获取 dataCenterId。

可以得知，dataCenterId 的取值与 Mac 地址有关。

接下来再看看 workerId。

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

入参 maxWorkderId 也是一个固定值，代表工作机器 ID 最大值，默认值 31；datacenterId 取自上述的 getDatacenterId 方法。

name 变量值为 PID@IP，所以 name 需要根据 @ 分割并获取下标 0，得到 PID。

通过 MAC + PID 的 hashcode 获取 16 个低位，进行运算，最终得到 workerId。

2. 分配标识位​

Mybatis-Plus 标识位的获取依赖 Mac 地址和进程 PID，虽然能做到尽量不重复，但仍有小几率。

标识位如何定义才能不重复？有两种方案：预分配和动态分配。

2.1. 预分配​

应用上线前，统计当前服务的节点数，人工去申请标识位。

这种方案，没有代码开发量，在服务节点固定或者项目少可以使用，但是解决不了服务节点动态扩容性问题。

2.2. 动态分配​

通过将标识位存放在 Redis、Zookeeper、MySQL 等中间件，在服务启动的时候去请求标识位，请求后标识位更新为下一个可用的。

通过存放标识位，延伸出一个问题：雪花算法的 ID 是 服务内唯一还是全局唯一。

以 Redis 举例，如果要做服务内唯一，存放标识位的 Redis 节点使用自己项目内的就可以；如果是全局唯一，所有使用雪花算法的应用，要用同一个 Redis 节点。

两者的区别仅是 不同的服务间是否公用 Redis。如果没有全局唯一的需求，最好使 ID 服务内唯一，因为这样可以避免单点问题。

服务的节点数超过 1024，则需要做额外的扩展；可以扩展 10 bit 标识位，或者选择开源分布式 ID 框架。

2.3. 动态分配实现方案​

Redis 存储一个 Hash 结构 Key，包含两个键值对：dataCenterId 和 workerId。

在应用启动时，通过 Lua 脚本去 Redis 获取标识位。dataCenterId 和 workerId 的获取与自增在 Lua 脚本中完成，调用返回后就是可用的标示位。

具体 Lua 脚本逻辑如下：

  1. 第一个服务节点在获取时，Redis 可能是没有 snowflake_work_id_key 这个 Hash 的，应该先判断 Hash 是否存在，不存在初始化 Hash，dataCenterId、workerId 初始化为 0；
  2. 如果 Hash 已存在，判断 dataCenterId、workerId 是否等于最大值 31，满足条件初始化 dataCenterId、workerId 设置为 0 返回；
  3. dataCenterId 和 workerId 的排列组合一共是 1024，在进行分配时，先分配 workerId；
  4. 判断 workerId 是否 != 31，条件成立对 workerId 自增，并返回；如果 workerId = 31，自增 dataCenterId 并将 workerId 设置为 0。

dataCenterId、workerId 是一直向下推进的，总体形成一个环状。通过 Lua 脚本的原子性，保证 1024 节点下的雪花算法生成不重复。如果标识位等于 1024，则从头开始继续循环推进。

3. 开源分布式 ID 框架​

Leaf 和 Uid 都有实现雪花算法，Leaf 额外提供了号段模式生成 ID。

雪花算法可以满足大部分场景，如无必要，不建议引入开源方案增加系统复杂度。

4. 回顾总结​

关于雪环算法生成 ID 冲突问题，文中给了一种方案：分配标示位；通过分配雪花算法的组成标识位，来达到默认 1024 节点下 ID 生成唯一。

可以去看 Hutool 或者 Mybatis-Plus 雪花算法的具体实现，帮助大家更好的理解。

雪花算法不是万能的，并不能适用于所有场景。如果 ID 要求全局唯一并且服务节点超出 1024 节点，可以选择修改算法本身的组成，即扩展标识位，或者选择开源方案：Leaf、Uid。

Table of Contents