唯一ID生成算法剖析，看看这篇就够了

2022-04-07 唯一ID生成算法

【唯一ID生成算法剖析，看看这篇就够了】本文转载自腾讯技术工程
引
在业务开发中，大量场景需要唯一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)，各位分别为：

唯一ID生成算法剖析，看看这篇就够了

文章插图
时间值：在基于时间的UUID中，时间值是一个60位的整型值，对应UTC的100ns时间间隔计数，因此其支持支持一台机器每秒生成10M次。在UUID中，将这60位放置到了15~08这8-byte中（除了09位有4-bit的版本号内容）。

推荐阅读

上一篇：linux系统ncat命令详解

下一篇：长歌行谁喜欢长歌长歌行李长歌官配是阿史那隼吗