引
在业务开发中, 大量场景需要唯一 ID 来进行标识: 用户需要唯一身份标识; 商品需要唯一标识; 消息需要唯一标识; 事件需要唯一标识... 等等, 都需要全局唯一 ID, 尤其是分布式场景下.
唯一 ID 有哪些特性或者说要求呢? 按照我的分析有以下特性:
唯一性: 生成的 ID 全局唯一, 在特定范围内冲突概率极小
有序性: 生成的 ID 按某种规则有序, 便于数据库插入及排序
可用性: 可保证高并发下的可用性
自主性: 分布式环境下不依赖中心认证即可自行生成 ID
安全性: 不暴露系统和业务的信息
一般来说, 常用的唯一 ID 生成方法有这些:
UUID:
基于时间戳 & 时钟序列生成
基于名字空间 / 名字的散列值 (MD5/SHA1) 生成
基于随机数生成
数据库自增 ID:
多台机器不同初始值, 同步长自增
批量缓存自增 ID
雪花算法
时钟回拨解决方案
本文便分别对这些算法进行讲解及分析.
UUID
UUID 全称为: Universally Unique IDentifier(通用唯一识别码), 有的地方也称作 GUID(Globally Unique IDentifier), 实际上 GUID 指微软对于 UUID 标准的实现的实现.
UUID 算法的目的是为了生成某种形式的全局唯一 ID 来标识系统中的任一元素, 尤其在分布式环境下, 该 ID 需要不依赖中心认证即可自动生成全局唯一 ID.
其优势有:
无需网络, 单机自行生成
速度快, QPS 高(支持 100ns 级并发)
各语言均有相应实现库供直接使用
而缺点为:
String 存储, 占空间, DB 查询及索引效率低
无序, 可读性差
根据实现方式不同可能泄露信息
1.UUID 的格式
UUID 的标准形式为 32 个十六进制数组成的字符串, 且分隔为五个部分, 如:
467e8542-2275-4163-95d6-7adc205580a9
各部分的数字个数为: 8-4-4-4-12
2.UUID 版本
根据需要不同, 标准提供了不同的 UUID 版本以供使用, 分别对应于不同的 UUID 生成规则:
版本 1 - 基于时间的 UUID: 主要依赖当前的时间戳及机器 Mac 地址, 因此可以保证全球唯一性
版本 2 - 分布式安全的 UUID: 将版本 1 的时间戳前四位换为 POSIX 的 UID 或 GID, 很少使用
版本 3 - 基于名字空间的 UUID(MD5 版): 基于指定的名字空间 / 名字生成 MD5 散列值得到, 标准不推荐
版本 4 - 基于随机数的 UUID: 基于随机数或伪随机数生成,
版本 5 - 基于名字空间的 UUID(SHA1 版): 将版本 3 的散列算法改为 SHA1
3.UUID 各版本优缺点
版本 1 - 基于时间的 UUID:
优点: 能基本保证全球唯一性
缺点: 使用了 Mac 地址, 因此会暴露 Mac 地址和生成时间
版本 2 - 分布式安全的 UUID:
优点: 能保证全球唯一性
缺点: 很少使用, 常用库基本没有实现
版本 3 - 基于名字空间的 UUID(MD5 版):
优点: 不同名字空间或名字下的 UUID 是唯一的; 相同名字空间及名字下得到的 UUID 保持重复.
缺点: MD5 碰撞问题, 只用于向后兼容, 后续不再使用
版本 4 - 基于随机数的 UUID:
优点: 实现简单
缺点: 重复几率可计算
版本 5 - 基于名字空间的 UUID(SHA1 版):
优点: 不同名字空间或名字下的 UUID 是唯一的; 相同名字空间及名字下得到的 UUID 保持重复.
缺点: SHA1 计算相对耗时
总得来说:
版本 1/2 适用于需要高度唯一性且无需重复的场景;
版本 3/5 适用于一定范围内唯一且需要或可能会重复生成 UUID 的环境下;
版本 4 适用于对唯一性要求不太严格且追求简单的场景.
4.UUID 结构及生成规则
以版本 1 - 基于时间的 UUID 为例先梳理 UUID 的结构:
UUID 为 32 位的十六机制数, 因此实际上是 16-byte (128-bit), 各位分别为:
时间值 : 在基于时间的 UUID 中, 时间值是一个 60 位的整型值, 对应 UTC 的 100ns 时间间隔计数, 因此其支持支持一台机器每秒生成 10M 次. 在 UUID 中, 将这 60 位放置到了 15~08 这 8-byte 中(除了 09 位有 4-bit 的版本号内容).
版本号 : 版本号即上文所说的五个版本, 在五个版本的 UUID 中, 都总是在该位置标识版本, 占据 4-bit, 分别以下列数字表示:
因此版本号这一位的取值只会是 1,2,3,4,5
变体值 : 表明所依赖的标准(X 表示可以是任意值):
时钟序列: 在基于时间的 UUID 中, 时钟序列占据了 07~06 位的 14-bit. 不同于时间值, 时钟序列实际上是表示一种逻辑序列, 用于标识事件发生的顺序. 在此, 如果前一时钟序列已知, 则可以通过自增来实现时钟序列值的改变; 否则, 通过 (伪) 随机数来设置. 主要用于避免因时间值向未来设置或节点值改变可能导致的 UUID 重复问题.
节点值: 在基于时间的 UUID 中, 节点值占据了 05~00 的 48-bit, 由机器的 Mac 地址构成. 如果机器有多个 Mac 地址, 则随机选其中一个; 如果机器没有 Mac 地址, 则采用 (伪) 随机数.
了解了基于时间的 UUID 结构及生成规则后, 再看看其他版本的 UUID 生成规则:
版本 2 - 分布式安全的 UUID:
将基于时间的 UUID 中时间戳前四位换为 POSIX 的 UID 或 GID, 其余保持一致.
版本 3/5 - 基于名字空间的 UUID (MD5/SHA1):
将命名空间 (如 DNS,URL,OID 等) 及名字转换为字节序列;
通过 MD5/SHA1 散列算法将上述字节序列转换为 16 字节哈希值 (MD5 散列不再推荐, SHA1 散列的 20 位只使用其 15~00 位);
将哈希值的 3~0 字节置于 UUID 的 15~12 位;
将哈希值的 5~4 字节置于 UUID 的 11~10 位;
将哈希值的 7~6 字节置于 UUID 的 09~08 位, 并用相应版本号覆盖第 9 位的高 4 位 (同版本 1 位置);
将哈希值的 8 字节置于 UUID 的 07 位, 并用相应变体值覆盖其高 2 位 (同版本 1 位置);
将哈希值的 9 字节置于 UUID 的 06 位 (原时钟序列位置);
将哈希值的 15~10 字节置于 UUID 的 05~00 位 (原节点值位置).
版本 4 - 基于随机数的 UUID:
生成 16byte 随机值填充 UUID. 重复机率与随机数产生器的质量有关. 若要避免重复率提高, 必须要使用基于密码学上的假随机数产生器来生成值才行;
将变体值及版本号填到相应位置.
5. 多版本伪码
- // 版本 1 - 基于时间的 UUID:
- gen_uuid() {
- struct uuid uu;
- // 获取时间戳
- get_time(&clock_mid, &uu.time_low);
- uu.time_mid = (uint16_t) clock_mid; // 时间中间位
- uu.time_hi_and_version = ((clock_mid>> 16) & 0x0FFF) | 0x1000; // 时间高位 & 版本号
- // 获取时钟序列. 在 libuuid 中, 尝试取时钟序列 + 1, 取不到则随机; 在 python 中直接使用随机
- get_clock(&uu.clock_seq);// 时钟序列 + 1 或 随机数
- uu.clock_seq |= 0x8000;// 时钟序列位 & 变体值
- // 节点值
- char node_id[6];
- get_node_id(node_id);// 根据 Mac 地址等获取节点 id
- uu.node = node_id;
- return uu;
- }
- // 版本 4 - 基于随机数的 UUID:
- gen_uuid() {
- struct uuid uu;
- uuid_t buf;
- random_get_bytes(buf, sizeof(buf));// 获取随机出来的 uuid, 如 libuuid 根据进程 id, 当日时间戳等进行 srand 随机
- uu.clock_seq = (uu.clock_seq & 0x3FFF) | 0x8000;// 变体值覆盖
- uu.time_hi_and_version = (uu.time_hi_and_version & 0x0FFF) | 0x4000;// 版本号覆盖
- return uu;
- }
- // 版本 5 - 基于名字空间的 UUID(SHA1 版):
- gen_uuid(name) {
- struct uuid uu;
- uuid_t buf;
- sha_get_bytes(name, buf, sizeof(buf));// 获取 name 的 sha1 散列出来的 uuid
- uu.clock_seq = (uu.clock_seq & 0x3FFF) | 0x8000;// 变体值覆盖
- uu.time_hi_and_version = (uu.time_hi_and_version & 0x0FFF) | 0x5000;// 版本号覆盖
- return uu;
- }
- (左滑查看完整代码)
数据库自增 ID
数据库自增 ID 可能是大家最熟悉的一种唯一 ID 生成方式, 其具有使用简单, 满足基本需求, 天然有序的优点, 但也有缺陷:
并发性不好
数据库写压力大
数据库故障后不可使用
存在数量泄露风险
因此这里给出两种优化方案.
1. 数据库水平拆分, 设置不同的初始值和相同的步长
如图所示, 可保证每台数据库生成的 ID 是不冲突的, 但这种固定步长的方式也会带来扩容的问题, 很容易想到当扩容时会出现无 ID 初始值可分的窘境, 解决方案有:
根据扩容考虑决定步长
增加其他位标记区分扩容
这其实都是在需求与方案间的权衡, 根据需求来选择最适合的方式.
2. 批量生成一批 ID
如果要使用单台机器做 ID 生成, 避免固定步长带来的扩容问题, 可以每次批量生成一批 ID 给不同的机器去慢慢消费, 这样数据库的压力也会减小到 N 分之一, 且故障后可坚持一段时间.
如图所示, 但这种做法的缺点是服务器重启, 单点故障会造成 ID 不连续. 还是那句话, 没有最好的方案, 只有最适合的方案.
雪花算法
定义一个 64bit 的数, 对指定机器 & 同一时刻 & 某一并发序列, 是唯一的, 其极限 QPS 约为 400w/s. 其格式为:
将 64 bit 分为了四部分. 其中时间戳有时间上限(69 年). 机器 id 只有 10 位, 能记录 1024 台机器, 常用前几位表示数据中心 id, 后几位表示数据中心内的机器 id. 序列号用来对同一个毫秒之内的操作产生不同的 ID, 最多 4095 个.
这种结构是雪花算法提出者 Twitter 的分法, 但实际上这种算法使用可以很灵活, 根据自身业务的并发情况, 机器分布, 使用年限等, 可以自由地重新决定各部分的位数, 从而增加或减少某部分的量级. 比如百度的 UidGenerator, 美团的 Leaf 等, 都是基于雪花算法做一些适合自身业务的变化.
由于雪花算法是强依赖于时间的, 在分布式环境下, 如果发生 时钟回拨 , 很可能会引起 id 冲突的问题. 解决方案有:
将 ID 生成交给少量服务器, 并关闭时钟同步.
直接报错, 交给上层业务处理.
如果回拨时间较短, 在耗时要求内, 比如 5ms, 那么等待回拨时长后再进行生成.
如果回拨时间很长, 那么无法等待, 可以匀出少量位 (1~2 位) 作为回拨位, 一旦时钟回拨, 将回拨位加 1, 可得到不一样的 ID,2 位回拨位允许标记三次时钟回拨, 基本够使用. 如果超出了, 可以再选择抛出异常.
方案对比
可以发现, 常用的分布式唯一 ID 生成思路 基本是利用一个长串数字或字符串, 将其分割成多个部分, 分别记录时间信息, 机器 / 名字信息, 随机信息, 序列信息等. 时间信息部分决定了该策略能使用的时长, 机器 / 名字信息支持了分布式环境下的独自生成唯一 ID 与识别能力, 序列信息保证了事件的顺序记录以及同一时间单位下的并发数, 而随机信息则加大了 ID 整体的不可识别性.
实际上如果现有的方法依然不能满足, 我们完全可以依据自身业务和发展需求, 来自行决定使用何种策略生成唯一 ID. 各种方案都有其优缺点, 技术的使用没有绝对的好坏之分, 主要在于是否适合使用场景:
要求生成全局唯一且不会重复 ID, 不关心顺序 -- 使用基于时间的 UUID(如游戏聊天室中不同用户的身份 ID)
要求生成唯一 ID, 具有名称不可变性, 可重复生成 -- 使用基于名称哈希的 UUID(如基于不可变信息生成的用户 ID, 若不小心删除, 仍可根据信息重新生成同一 ID)
要求生成有序且自然增长的 ID -- 使用数据库自增 ID(如各业务操作流水 ID, 高并发下可参考优化方案)
要求生成数值型无序定长 ID -- 使用雪花算法(如对存储空间, 查询效率, 传输数据量等有较高要求的场景)
对于最初我们定义的唯一 ID 特性, 各方案的对比如下:
从冲突率, QPS 和算法时间复杂度来比较的话:
参考
UUID 算法分析
关于 UUID 的二三事
UUID 百度百科
UUID 唯一资源命名空间的来龙去脉
UUID 是如何保证唯一性的?
如果再有人问你分布式 ID, 这篇文章丢给他
分布式唯一 ID 的几种生成方案
UidGenerator - 百度
Leaf-- 美团点评分布式 ID 生成系统
分布式系统: Lamport 逻辑时钟
来源: http://www.tuicool.com/articles/bY3Ar2a