ID生成器详解

时间:2022-01-11 21:14:02

概述

ID 生成器也叫发号器,它的主要目的就是“为一个分布式系统的数据object产生一个唯一的标识”,但其实在一个真实的系统里可能也可以承担更多的作用。概括起来主要有以下几点:

唯一性
时间相关
粗略有序
可反解
可制造

要唯一性,是否需要全局唯一?

说起全局唯一,通常大家都会在想到发号器服务,分布式的通常需要更大空间,中心式的则需要在一个合适的地方在会聚。这就可能涉及到锁,而锁意味着成本和性能的下降。所以当前的系统是否需要全局的唯一性,就是一个需要考虑的问题。比如在通讯系统里,聊天消息可能就未必需要全局,因为一条消息只是某一个人发出,系统只要保证一个人维度的唯一性即可。本质上而言,这里利用了用户 ID 的唯一性,因为唯一性是可以依赖的,通常我们设计系统也都是基于类似的性质,比如后面降到的使用时间唯一性的方式。

用时间来做什么?千万年太久,只争朝夕?

前面说到唯一性可以依赖,我们需要选择的是依赖什么。通常的做法可以选择数据库自增,这在很多数据库里都是可以满足ACID 的操作。但是用数据库有个缺点,就是数据库有性能问题,在多机房情况下也很难处理。当然,你可以通过调整自增的步长来设计,但对于一个发号器而言,操作和维护都略重了。

而时间是天然唯一的,因此也是很多设计的选择。但对于一个8Byte的 ID 而言,时间并没有那么多。你如果精确到秒级别,三十年都要使用30bit,到毫秒级则要再增加10bit,你也只剩下20bit 可以做其他事情了。之所以在8Byte上捣鼓,因为8Byte 是一个Long,不管在处理器和编译器还是语言层面,都是可以更好地被处理。

然而三十年够么?对于一个人来说,可能不够,但对一个系统而言,可能足够。我们经常开玩笑,互联网里能活三十年的系统有多少呢?三十年过去,你的系统可能都被重写 N 遍了。这样的信心同样来自于摩尔定律,三十年后,计算性能早就提高了上千倍,到时候更多Byte 都不会是问题了。

粗略有多粗略,秒还是毫秒?

每秒一个或者每毫秒一个ID明显是不够的,刚才说到还有20bit 可以做其他事情,就包括一个SequenceID。如果要达到精确的有序,就要对 Sequence 进行并发控制,性能上肯定会打折。所以经常会有的一个选择就是,在这个秒的级别上不再保证顺序,而整个 ID 则只保证时间上的有序。后一秒的 ID肯定比前一秒的大,但同一秒内可能后取的ID比前面的号小。

那时间用秒还是毫秒呢?其实不用毫秒的时候就可以把空出来的10bit 送给 Sequence,但整个ID 的精度就下降了。峰值速度是更现实的考虑。Sequence 的空间决定了峰值的速度,而峰值也就意味着持续的时间不会太久。这方面,每秒100万比每毫秒1000限制更小。

可反解,解开的是什么?

一个ID生成之后,就会伴随着信息终身,排错分析的时候,我们需要查验。这时候一个可反解的 ID 可以帮上很多忙,从哪里来的,什么时候出生的。 跟身份证倒有点儿相通了,其实身份证就是一个典型的分布式 ID 生成器。

如果ID里已经有了时间而且能解开,在存储层面可能不再需要timestamp一类的字段了。

可制造,为什么不用UUID?

互联网系统上可用性永远是优先指标。但由于分布式系统的脆弱,网络不稳定或者底层存储系统的不可用,业务系统随时面临着失败。为了给前端更友好的响应,我们需要能尽量容忍失败。比如在存储失败时,可能需要临时导出请求供后续处理,而后续处理时已经离开了当时的时间点,顺序跟其他系统错开了。我们需要制造出这样的ID以便系统好像一直正常运行一样,可制造的ID 让你可以控制生产日期,然后继续下面的处理。

另一个重要场景就是数据清洗。这个属于较少遇到,但并不罕见的情况,可能是原来ID设计的不合理,也可能由于底层存储的改变,都可能出现。这样一个可制造的 ID 就会带来很多操作层面的便利。

这也是我们不用UUID的一个原因。UUID标准可以保证在某时某地生成,但如果要控制生成一个特定时间的 UUID,可能需要底层库的改动。经验告诉我们,能在上层解决的问题不要透到下层,这种库的维护成本是非常高的。

其他

生成ID需考虑的元素

时间,可根据需要选择秒级或者毫秒级。
顺序号,当在时间等其他所有构成元素都相同的情况下,用于保证ID唯一性。
机器ID,可用MAC地址或者IP地址作为源,进行转换得到。
进程ID,满足一台机器上运行多个ID生成器的情况。

UUID

通用唯一识别码(Universally Unique Identifier,简称UUID)是一种软件建构的标准,亦为开放软件基金会组织在分布式计算环境领域的一部分。

UUID的目的,是让分布式系统中的所有元素,都能有唯一的辨识信息,而不需要通过*控制端来做辨识信息的指定。如此一来,每个人都可以创建不与其它人冲突的UUID。在这样的情况下,就不需考虑数据库创建时的名称重复问题。目前最广泛应用的UUID,是微软公司的全局唯一标识符(GUID),而其他重要的应用,则有Linux ext2/ext3文件系统、LUKS加密分区、GNOME、KDE、Mac OS X等等。另外我们也可以在e2fsprogs包中的UUID库找到实现。

UUID是由一组32位数的16进制数字所构成,是故UUID理论上的总数为1632=2128,约等于3.4 x 1038。也就是说若每纳秒产生1兆个UUID,要花100亿年才会将所有UUID用完。UUID的标准型式包含32个16进制数字,以连字号分为五段,形式为8-4-4-4-12的32个字元。示例:

550e8400-e29b-41d4-a716-446655440000
随机的UUID的重复概率

每秒产生10亿笔UUID,100年后只产生一次重复的概率是50%。产生重复UUID的概率非常低,是故大可不必考虑此问题。

生日问题

假设有n个人在同一房间内,如果要计算有两个人在同一日出生的概率,在不考虑特殊因素的前提下,例如闰年、双胞胎,假设一年365日出生概率是平均分布的(现实生活中,出生概率不是平均分布的)。

计算概率的方法是,首先找出p(n)表示n个人中,每个人的生日日期都不同的概率。假如n > 365,根据鸽巢原理其概率为1,假设n ≤ 365,则概率为:

ID生成器详解

因为第二个人不能跟第一个人有相同的生日(概率是364/365),第三个人不能跟前两个人生日相同(概率为363/365),依此类推。用阶乘可以写成如下形式:

ID生成器详解

p(n)表示n个人中至少2人生日相同的概率:

ID生成器详解

n≤365,根据鸽巢原理,n大于365时概率为1。

当n=23发生的概率大约是0.507。其他数字的概率用上面的算法可以近似的得出来:

n	p(n)
10 12%
20 41%
30 70%
50 97%
100 99.99996%
200 99.9999999999999999999999999998%
300 1 −(7×10−73)
350 1 −(3×10−131)
≥366 100%