2023-04-17 算法 软件工程

概述

分布式唯一 ID 是指在分布式系统中生成的全局唯一标识符。在分布式系统中，由于多个节点同时操作数据可能会导致数据冲突或者重复，因此需要为每个数据对象赋予一个唯一的标识符，以便在系统范围内进行区分。

本文主要介绍 三种 常见类型的实现方案，并简要概述各个方案的优缺点，并在附录部分给出 Go 语言的几个开源组件，读者可以根据自己的业务场景进行技术选型。

1.完全依赖三方组件

ID 的生成规则和读写操作完全由第三方组件控制，例如常见的 MySQL 自增 ID, Redis Incr 序列号, MongoDB ObjectId 等。

下面对 MySQL, Redis, MongoDB 方案做一个简单的概括，读者了解即可 (因为生产环境中不会这么使用)。

2.不完全依赖三方组件

ID 的生成规则有部分因子取决于数据源或配置信息，例如常见的 Snowflake 雪花算法。

Snowflake (雪花算法) 是一种生成分布式全局唯一 ID 的算法，生成的 ID 称为 Snowflake IDs 或 snowflakes。这种算法由 Twitter 创建， 并用于推文的 ID, Go 语言生态可以看看 这个组件。

Snowflake 算法的 ID 理论生成速度峰值为:

2^10 * 2^12 = 2^22 = 4194304/秒

实际应用中，可以进行具体的 bit 调整，例如可以将服务器标识中的一部分 bit 取出作为数据中心标识。

优点

• 生成速度快，不依赖其他组件，独立生成
• 高可用，不依赖于单点，每个服务器都可以独立生成 ID
• ID 辨识度高，天然支持排序
• 扩展性强

缺点

• 时钟回拨 (很严重)
• 能够表达的时间有限，最多 ≈ 70 年
• 生成的 ID 可以根据时间往后推算和预测

时钟回拨是指在特定的情况下，系统时钟或者计算机的时间被意外地向后调整了一段时间，导致系统中某些时间相关的操作出现异常。

时钟回拨通常发生在网络时间同步出现故障或者手动修改系统时间的情况下，如果发生时钟回拨，整个 uuid 可能会出现重复，直接影响到一些和时间相关的关键程序的正确运行，比如金融交易、时间序列、安全协议等。 针对上述 Snowflake 算法存在的缺点和问题，百度开源了解决方案 UidGenerator。

3.完全独立实现

ID 的生成规则由运行进程独立完成，不依赖任何第三方组件和配置信息，例如 UUID, GUID 等，本文以 UUID 为例分析下，对 GUID 感兴趣的读者，可以参考附录列表的 GUID 开源组件。

UUID 是通用唯一识别码（Universally Unique Identifier) 的缩写，开放软件基金会 (OSF) 规范定义了使用网卡、 MAC 地址、时间戳、命名空间（Namespace）、随机或伪随机数、序列号等元素来生成 UUID。

UUID 有 5 个版本，每个版本都有不同的生成规则:

1. V1: 基于时间戳和 MAC 地址生成，MAC 地址包括网卡的物理地址和一个伪随机数
2. V2: 将版本 V1 的时间戳前四位换为 POSIX 的 UID 或 GID，基本不使用
3. V3: 基于命名空间和名称生成，使用 MD5 哈希算法，不推荐使用
4. V4: 使用伪随机数完全随机生成，重复概率与随机数种子、生成器质量相关
5. V5: 类似于版本 V3，使用 SHA-1 哈希算法代替 MD5

目前主流使用的是版本 4，Go 语言生态可以看看 这个组件。

在 Linux 系统中，可以直接使用命令生成 uuid:

$ uuidgen

a6ba6a13-c5ee-4eef-a7d4-3410b1fc7098

也可以使用 这个网站 在线生成。

优点

• 生成速度快，不依赖其他组件，独立生成
• 无序，避免按照时间顺序递增或递减 (当然这也可以被认为是一个缺点)
• 扩展性强

缺点

• 存储空间占用多 (128 bit) 以及写入时的性能较低
• 可读性低，常见的业务场景需要二次转换 (例如邀请拉新活动需要根据二维码中的 UUID 找到对应的用户 ID)
• 应用服务容器化后，主机名、网卡可能高度相似，提高了重复概率

小结

本文主要介绍了关于 分布式唯一 ID 三种实现方案以及各自的优缺点，综上所述，笔者比较推荐的方案是 Snowflake 算法，毕竟大多数服务还是运行在云服务商提供的基础设施上， 时钟回拨 这个问题基本可以被完全规避。最后，希望这篇文章可以帮助读者在做对应的技术选型时提供帮助。

附录

• bwmarrin/snowflake
• google/uuid
• satori/go.uuid
• lithammer/shortuuid
• oklog/ulid
• sony/sonyflake
• kjk/betterguid
• rs/xid
• segmentio/ksuid
• pborman/uuid

Reference

• A brief history of the UUID
• Twitter snowflake approach is cool
• 雪花算法
• 通用唯一识别码