|
UUID
UUID(通用唯一识别码)是由32个十六进制数组成的无序字符串,通过一定的算法计算出来。为了保证其唯一性,UUID规范定义了包括网卡MAC地址、时间戳、名字空间(Namespace)、随机或伪随机数、时序等元素,以及从这些元素生成UUID的算法。一般来说,算法可以保证任何地方产生的任意一个UUID都不会相同,但这个唯一性是有限的,只在特定的范围内才能得到保证。
UUID的一个非常明显的特点就是本身较长,格式是这样的:- xxxxxxxx-xxxx-Mxxx-xxxx-xxxxxxxxxxxx
- 467e8542-2275-4163-95d6-7adc205580a9
复制代码 其中M位置,代表版本号,由于UUID的标准实现有5个版本,所以只会是1、2、3、4、5;
各版本介绍
UUID现有的5种版本,是根据不同的使用场景划分的,而不是根据精度,所以Version5并不会比Version1精度高,在精度上大家都能保证唯一性,重复的概率近乎于0。
总结:
- 使用UUID,每个人都可以创建不与其它人冲突的唯一值,在所有空间和时间上都可以被视为唯一的标识。
- UUID可单机自行生成,且生成速度快,QPS高,各个语言都有对应的生成供直接调用使用。
- 如果只是需要生成一个唯一ID,可以使用V1或V4。v1基于时间戳和Mac地址,这些ID有一定的规律,而且会暴露你的Mac地址。v4是完全随机(伪)的。
- 如果对于相同的参数需要输出相同的UUID,你可以使用V3或V5。
Version1: 基于时间戳及MAC地址的实现
其中包括了48位的MAC地址和60位的时间戳。且v1为了保证唯一性,当时间精度不够时,会使用13~14位的clock sequence来扩展时间戳,比如:当UUID的生产成速率太快,超过了系统时间的精度。时间戳的低位部分会每增加一个UUID就+1的操作来模拟更高精度的时间戳,换句话说,就是当系统时间精度无会区分2个UUID的时间先后时,为了保证唯一性,会在其中一个UUID上+1。所以UUID重复的概率几乎为0,时间戳加扩展的clock sequence一共有74bits,(2的74次方,约为1.8后面加22个零),即在每个节点下,每秒可产生1630亿不重复的UUID。
但由于v1中最后的12位是网卡的MAC地址,会导致隐私问题以及安全问题,这是这个版本UUID受到批评的地方。
Version2: DCE安全的UUID
DCE(Distributed Computing Environment)安全的UUID和基于时间的UUID算法相同,但会把时间戳的前4位置换为POSIX的UID或GID。这个版本的UUID在实际中较少用到。
Version3: 5 基于名称空间和名字
v3和v5都是通过计算namespace和名称的哈希值生成的。不同的点在于v3使用的hash算法为MD5,v5使用SHA-1。因为算法中没有不确定的部分,所以当namespace与名称确定时,得到的UUID都是确定唯一的。比如:- $ uuid -n 3 -v3 ns:URL www.jd.com
- 7e963853-8fce-3085-bb2c-8424745d73a2
- 7e963853-8fce-3085-bb2c-8424745d73a2
- 7e963853-8fce-3085-bb2c-8424745d73a2
复制代码 算法实现中会将namespace和输入参数拼接在一起,计算hash结果,再进行截断格式化等操作来保证唯一性。
Version4: 基于随机数
v4的UUID中4位代表版本,2-3位代表variant。余下的122-121位都是全部随机的。即有2的122次方(5.3后面36个0)个UUID。一个标准实现的UUID库在生成了2.71万亿个UUID会产生重复UUID的可能性也只有50%的概率。这相当于每秒产生10亿的UUID,持续85年,而把这些UUID都存入文件,每个UUID占16bytes,总需要45EB(exabytes),比目前最大的数据库(PB)还要大很多倍。
在java中使用v4:- # java 1.5+
- # java.util.UUID
- for (int i = 0; i < 3; i++) {
- String uuid = UUID.randomUUID().toString();
- System.out.println(uuid);
- }
复制代码 生成的UUID如下:- 8bca474b-214d-4ce8-8446-b99f30147f94
- c38588cf-a1c4-4758-9d86-b2ee5552ae59
- febf5a46-bd1b-43f8-89a8-d5606e5d1ce0
复制代码 由于这个版本使用非常简单,因此使用最为广泛。
SnowFlake算法
雪花算法,是 Twitter 开源的分布式 ID 生成算法。雪花算法中利用了时间戳,机器ID,以及同毫秒内的不同序列号来保证分布式生成ID的唯一性。
雪花算法总结
1.时间戳在高位,自增序列在低位的特征可以保证整个ID的趋势是递增有序的。
2.但由于其依赖机器时钟,如果机器时钟回拨,可能会导致重复ID生成。其在分布式环境下,每台机器上的时钟不可能完全同步,有时候会出现不是全局递增的情况。
SnowFlake算法生成id的结果是一个64bit大小的整数,它的结构如下图:
- 1bit,不用。二进制中最高位为1的都是负数,但是我们生成的id一般都使用整数,所以这个最高位固定是0
- 41bit,用来记录时间戳(毫秒)。41位可以表示 2^{41}-1 个数字,如果只用来表示正整数(计算机中正数包含0),可以表示的数值范围是 0 至 2^{41}-1,也就是说41位可以表示 2^{41}-1 个毫秒的值,转化成单位年则是 (2^{41} - 1) / (1000*60*60*24*365) = 69 年。
- 10bit,用来记录工作机器id。可以部署在 2^{10} = 1024 个节点,包括 5位 datacenterId 和 5位 workerId,5位(bit)可以表示的最大正整数是 2^{5}-1 = 31,即可以用 0、1、2、3、....、31 这 32 个数字,来表示不同的 datecenterId 或 workerId。
- 12位,序列号,用来记录同毫秒内产生的不同ID;12bit 可以表示的最大正整数是 2^{12}-1 = 4095 ,即可以用 0、1、2、3、....4094 这 4095 个数字,来表示同一机器同一时间截(毫秒)内产生的 4095 个 ID 序号。
有序主键 or 随机主键 ?
使用UUID这些随机ID生成算法作为MySQL主键的生成方案呢?答案是:不可以!
众所周知,当MySQL数据表使用InnoDB作为存储引擎时,每一个索引都对应一个B+树,若表定义了主键(没有时,MySQL则会自动生成不可见的自增主键),主键对应的索引就是聚簇索引,表的所有数据都存储在聚簇索引上。索引中键值的逻辑顺序决定了表中相应行的物理顺序(索引中的数据物理存放地址和索引的顺序是一致的)。可以这么理解:只要是索引是连续的,那么数据在存储介质上的存储位置也是连续的。
基于以上特性,由于自增键的值是有序的,插入数据时,Innodb 会把每一条记录都存储在上一条记录的后面。当达到页面的最大填充因子时候(innodb默认的最大填充因子是页大小的15/16,会留出1/16的空间留作以后的修改),会进行如下操作:下一条记录就会写入新的页中,一旦数据按照这种顺序的方式加载,主键页就会近乎于顺序的记录填满,提升了页面的最大填充率,不会有页的浪费;且由于新插入的行一定会在原有的最大数据行下一行,mysql定位和寻址很快,不会为计算新行的位置而做出额外的消耗。
而UUID相对于有序的自增ID,它的值是毫无规律可言的,新行的主键不一定要比之前数据主键的值大,所以innodb无法做到总是把新行插入到索引的最后,而是需要为新行寻找新的合适的位置从而来分配新的空间。这个过程需要做很多额外的操作,而且最终分布散乱的数据会导致以下问题:
- 写入的目标页很可能已经刷新到磁盘上并且从缓存上移除,或者还没有被加载到缓存中,innodb在插入之前不得不先找到并从磁盘读取目标页到内存中,这将导致大量的随机IO;
- 因为写入是乱序的,innodb不得不频繁的做页分裂操作,以便为新的行分配空间,页分裂导致移动大量的数据,一次插入最少需要修改三个页以上,且由于频页分裂,页会变得稀疏并被不规则的填充,最终会导致数据会有碎片;
- 在把值载入到聚簇索引(innodb默认的索引类型)以后,有时候会需要做一次OPTIMEIZE TABLE来重建表并优化页的填充,这将又需要一定的时间消耗。
作者:京东零售 金越
来源:京东云开发者社区 转载请注明来源
来源:https://www.cnblogs.com/jingdongkeji/p/17711470.html
免责声明:由于采集信息均来自互联网,如果侵犯了您的权益,请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容,谢谢合作! |
本帖子中包含更多资源
您需要 登录 才可以下载或查看,没有账号?立即注册
x
|