本文转载自腾讯技术工程
引
在业务开发中,大量场景需要唯一ID来进行标识:用户需要唯一身份标识;商品需要唯一标识;消息需要唯一标识;事件需要唯一标识…等等,都需要全局唯一ID,尤其是分布式场景下。
唯一ID有哪些特性或者说要求呢?按照我的分析有以下特性:
一般来说,常用的唯一ID生成方法有这些:
UUID:
数据库自增ID:
雪花算法
UUID
UUID全称为:Universally Unique IDentifier(通用唯一识别码),有的地方也称作GUID(Globally Unique IDentifier),实际上GUID指微软对于UUID标准的实现的实现。
UUID算法的目的是为了生成某种形式的全局唯一ID来标识系统中的任一元素,尤其在分布式环境下,该ID需要不依赖中心认证即可自动生成全局唯一ID。
其优势有:
而缺点为:
UUID的标准形式为32个十六进制数组成的字符串,且分隔为五个部分,如:
467e8542-2275-4163-95d6-7adc205580a9
各部分的数字个数为:8-4-4-4-12
根据需要不同,标准提供了不同的UUID版本以供使用,分别对应于不同的UUID生成规则:
版本1 - 基于时间的UUID:
版本2 - 分布式安全的UUID:
版本3 - 基于名字空间的UUID(MD5版):
版本4 - 基于随机数的UUID:
版本5 - 基于名字空间的UUID(SHA1版):
总得来说:
以版本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生成规则:
将基于时间的UUID中时间戳前四位换为POSIX的UID或GID,其余保持一致。
// 版本 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生成方式,其具有使用简单,满足基本需求,天然有序的优点,但也有缺陷:
因此这里给出两种优化方案。
如图所示,可保证每台数据库生成的ID是不冲突的,但这种固定步长的方式也会带来扩容的问题,很容易想到当扩容时会出现无ID初始值可分的窘境,解决方案有:
这其实都是在需求与方案间的权衡,根据需求来选择最适合的方式。
如果要使用单台机器做ID生成,避免固定步长带来的扩容问题,可以每次批量生成一批ID给不同的机器去慢慢消费,这样数据库的压力也会减小到N分之一,且故障后可坚持一段时间。
如图所示,但这种做法的缺点是服务器重启、单点故障会造成ID不连续。还是那句话,没有最好的方案,只有最适合的方案。
雪花算法
定义一个64bit的数,对指定机器 & 同一时刻 & 某一并发序列,是唯一的,其极限QPS约为400w/s。其格式为:
将64 bit分为了四部分。其中时间戳有时间上限(69年)。机器id只有10位,能记录1024台机器,常用前几位表示数据中心id,后几位表示数据中心内的机器id。序列号用来对同一个毫秒之内的操作产生不同的ID,最多4095个。
这种结构是雪花算法提出者Twitter的分法,但实际上这种算法使用可以很灵活,根据自身业务的并发情况、机器分布、使用年限等,可以自由地重新决定各部分的位数,从而增加或减少某部分的量级。比如百度的UidGenerator、美团的Leaf等,都是基于雪花算法做一些适合自身业务的变化。
由于雪花算法是强依赖于时间的,在分布式环境下,如果发生时钟回拨,很可能会引起id冲突的问题。解决方案有:
方案对比
可以发现,常用的分布式唯一ID生成思路基本是利用一个长串数字或字符串,将其分割成多个部分,分别记录时间信息、机器/名字信息、随机信息、序列信息等。时间信息部分决定了该策略能使用的时长,机器/名字信息支持了分布式环境下的独自生成唯一ID与识别能力,序列信息保证了事件的顺序记录以及同一时间单位下的并发数,而随机信息则加大了ID整体的不可识别性。
实际上如果现有的方法依然不能满足,我们完全可以依据自身业务和发展需求,来自行决定使用何种策略生成唯一ID。各种方案都有其优缺点,技术的使用没有绝对的好坏之分,主要在于是否适合使用场景:
对于最初我们定义的唯一ID特性,各方案的对比如下:
从冲突率、QPS和算法时间复杂度来比较的话:
参考
UUID算法分析
关于UUID的二三事
UUID百度百科
UUID唯一资源命名空间的来龙去脉
UUID是如何保证唯一性的?
如果再有人问你分布式 ID,这篇文章丢给他
分布式唯一ID的几种生成方案
UidGenerator-百度
Leaf——美团点评分布式ID生成系统
分布式系统:Lamport 逻辑时钟