程序员研究有意思

唯一ID生成算法剖析

2019-09-19  本文已影响0人  Cloudox_

引

在业务开发中，大量场景需要唯一ID来进行标识：用户需要唯一身份标识；商品需要唯一标识；消息需要唯一标识；事件需要唯一标识...等等，都需要全局唯一ID，尤其是分布式场景下。

唯一ID有哪些特性或者说要求呢？按照我的分析有以下特性：

一般来说，常用的唯一ID生成方法有这些：

本文便分别对这些算法进行讲解及分析。

UUID

UUID全称为：Universally Unique IDentifier（通用唯一识别码），有的地方也称作GUID（Globally Unique IDentifier），实际上GUID指微软对于UUID标准的实现的实现。

UUID算法的目的是为了生成某种形式的全局唯一ID来标识系统中的任一元素，尤其在分布式环境下，该ID需要不依赖中心认证即可自动生成全局唯一ID。

其优势有：

而缺点为：

1.UUID的格式

UUID的标准形式为32个十六进制数组成的字符串，且分隔为五个部分，如：

467e8542-2275-4163-95d6-7adc205580a9

各部分的数字个数为：8-4-4-4-12

2.UUID版本

根据需要不同，标准提供了不同的UUID版本以供使用，分别对应于不同的UUID生成规则：

3.UUID各版本优缺点

总得来说：
版本 1/2 适用于需要高度唯一性且无需重复的场景；
版本 3/5 适用于一定范围内唯一且需要或可能会重复生成UUID的环境下；
版本 4 适用于对唯一性要求不太严格且追求简单的场景。

4.UUID结构及生成规则

以版本1 - 基于时间的UUID为例先梳理UUID的结构：

UUID为32位的十六机制数，因此实际上是16-byte（128-bit），各位分别为：

位置 内容 说明
15 – 12 TimeLow 时间值的低位 4-byte
11 – 10 TimeMid 时间值的中位 2-byte
09 VersionAndTimeHigh 版本号 4-bit + 时间值高位 4-bit
08 TimeHigh 时间值的高位 1-byte
07 VariantAndClockSeqHigh 变体值 2-bit + 时钟序列高位 6-bit
06 ClockSeqLow 时钟序列低位 1-byte
05 – 00 Node 节点值 6-byte

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

版本号：版本号即上文所说的五个版本，在五个版本的UUID中，都总是在该位置标识版本，占据 4-bit，分别以下列数字表示：

7 6 5 4 版本 说明
0 0 0 1 1 基于时间的UUID
0 0 1 0 2 分布式安全的UUID
0 0 1 1 3 基于名字空间的UUID（MD5版）
0 1 0 0 4 基于随机数的UUID
0 1 0 1 5 基于名字空间的UUID（SHA1版）

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

变体值：表明所依赖的标准（X表示可以是任意值）：

7 6 5 说明
0 X X NCS向后兼容
1 0 X 本标准
1 1 0 Microsoft向后兼容
1 1 1 ITU-T Rec. X.667保留

时钟序列：在基于时间的UUID中，时钟序列占据了07~06位的14-bit。不同于时间值，时钟序列实际上是表示一种逻辑序列，用于标识事件发生的顺序。在此，如果前一时钟序列已知，则可以通过自增来实现时钟序列值的改变；否则，通过（伪）随机数来设置。主要用于避免因时间值向未来设置或节点值改变可能导致的UUID重复问题。

节点值：在基于时间的UUID中，节点值占据了05~00的48-bit，由机器的MAC地址构成。如果机器有多个MAC地址，则随机选其中一个；如果机器没有MAC地址，则采用（伪）随机数。

了解了基于时间的UUID结构及生成规则后，再看看其他版本的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。其格式为：

1 bit 41 bit 10 bit 12 bit
符号位，不用 时间戳(最长69年) 机器id 序列号

将64 bit分为了四部分。其中时间戳有时间上限（69年）。机器id只有10位，能记录1024台机器，常用前几位表示数据中心id，后几位表示数据中心内的机器id。序列号用来对同一个毫秒之内的操作产生不同的ID，最多4095个。

这种结构是雪花算法提出者Twitter的分法，但实际上这种算法使用可以很灵活，根据自身业务的并发情况、机器分布、使用年限等，可以自由地重新决定各部分的位数，从而增加或减少某部分的量级。比如百度的UidGenerator、美团的Leaf等，都是基于雪花算法做一些适合自身业务的变化。

由于雪花算法是强依赖于时间的，在分布式环境下，如果发生时钟回拨，很可能会引起id冲突的问题。解决方案有：

方案对比

可以发现，常用的分布式唯一ID生成思路基本是利用一个长串数字或字符串，将其分割成多个部分，分别记录时间信息、机器/名字信息、随机信息、序列信息等。时间信息部分决定了该策略能使用的时长，机器/名字信息支持了分布式环境下的独自生成唯一ID与识别能力，序列信息保证了事件的顺序记录以及同一时间单位下的并发数，而随机信息则加大了ID整体的不可识别性。

实际上如果现有的方法依然不能满足，我们完全可以依据自身业务和发展需求，来自行决定使用何种策略生成唯一ID。各种方案都有其优缺点，技术的使用没有绝对的好坏之分，主要在于是否适合使用场景：

对于最初我们定义的唯一ID特性，各方案的对比如下：

方案 唯一性 有序性 可用性 自主性 安全性
基于时间的UUID 强唯一性 时间序+逻辑序 高并发可用 自主生成 暴露时间及MAC
基于随机值的UUID 依赖随机算法 无序 依赖随机算法 自主生成 安全
基于名字哈希的UUID 强唯一性 无序 高可用 自主生成 较安全
数据库自增ID 强唯一性 有序 较高可用 依赖中心主机 暴露数量
数据库批量ID 强唯一性 批量内有序 较高可用 依赖中心主机 暴露数量
雪花算法 较强唯一性 时间序+逻辑序 高并发可用 自主生成 暴露时间

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

方案 冲突率/最高不冲突QPS 时间复杂度
基于时间的UUID 10M/s 下不冲突 时间戳与时钟序列的获取为固定时间
基于随机值的UUID 依赖随机算法 依赖随机数生成算法
基于名字哈希的UUID SHA1有 1 / 10 ^ 48 的机率冲突 SHA1算法时间复杂度为固定时间
数据库自增ID 不冲突 InnoDB直接增加内存中计数器的值
数据库批量ID 不冲突 O(n)，n为批量值大小
雪花算法 400W/s（取决于序列号位数） 各部分数值的获取为固定时间

参考

UUID算法分析
关于UUID的二三事
UUID百度百科
UUID唯一资源命名空间的来龙去脉
UUID是如何保证唯一性的？
如果再有人问你分布式 ID，这篇文章丢给他
分布式唯一ID的几种生成方案
UidGenerator-百度
Leaf——美团点评分布式ID生成系统
分布式系统：Lamport 逻辑时钟

上一篇下一篇

猜你喜欢

热点阅读