vlambda博客
学习文章列表

唯一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的版本号内容）。
版本号 ：版本号即上文所说的五个版本，在五个版本的UUID中，都总是在该位置标识版本，占据 4-bit，分别以下列数字表示：
唯一ID生成算法剖析


因此版本号这一位的取值只会是1,2,3,4,5


变体值：表明所依赖的标准（X表示可以是任意值）：
唯一ID生成算法剖析

时钟序列：在基于时间的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)：
  1. 将命名空间 (如DNS、URL、OID等) 及名字转换为字节序列；
  2. 通过MD5/SHA1散列算法将上述字节序列转换为16字节哈希值 (MD5散列不再推荐，SHA1散列的20位只使用其15~00位)；
  3. 将哈希值的 3~0 字节置于UUID的15~12位；
  4. 将哈希值的 5~4 字节置于UUID的11~10位；
  5. 将哈希值的 7~6 字节置于UUID的09~08位，并用相应版本号覆盖第9位的高4位 (同版本1位置)；
  6. 将哈希值的 8 字节置于UUID的07位，并用相应变体值覆盖其高2位 (同版本1位置)；
  7. 将哈希值的 9 字节置于UUID的06位 (原时钟序列位置)；
  8. 将哈希值的 15~10 字节置于UUID的05~00位 (原节点值位置)。

  • 版本4 - 基于随机数的UUID：
  1. 生成16byte随机值填充UUID。重复机率与随机数产生器的质量有关。若要避免重复率提高，必须要使用基于密码学上的假随机数产生器来生成值才行；
  2. 将变体值及版本号填到相应位置。


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是不冲突的，但这种固定步长的方式也会带来扩容的问题，很容易想到当扩容时会出现无ID初始值可分的窘境，解决方案有：
  • 根据扩容考虑决定步长
  • 增加其他位标记区分扩容


这其实都是在需求与方案间的权衡，根据需求来选择最适合的方式。


2.批量生成一批ID

如果要使用单台机器做ID生成，避免固定步长带来的扩容问题，可以每次批量生成一批ID给不同的机器去慢慢消费，这样数据库的压力也会减小到N分之一，且故障后可坚持一段时间。
唯一ID生成算法剖析

如图所示，但这种做法的缺点是服务器重启、单点故障会造成ID不连续。还是那句话，没有最好的方案，只有最适合的方案。


雪花算法
定义一个64bit的数，对指定机器 & 同一时刻 & 某一并发序列，是唯一的，其极限QPS约为400w/s。其格式为：
唯一ID生成算法剖析
唯一ID生成算法剖析


将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特性，各方案的对比如下：
唯一ID生成算法剖析


从冲突率、QPS和算法时间复杂度来比较的话：


参考



推荐阅读

[5.05] 暗喻幻想港中35周年限定版1.03+DLC+金手指+王中王存档 [5.05] 暗喻幻想港中35周年限定版1.03+DLC+金手指+王中王存档
服务器维护小常识(win+linux) 服务器维护小常识(win+linux)

相关文章