查看原文
其他

分布式 Unique ID 的生成方法一览

21CTO 2021-10-21

分布式的Unique ID的用途如此广泛,从业务对象Id到日志的TraceId,本文总结了林林总总的各种生成算法。


1. 发号器


我接触的最早的Unique ID,就是Oracle的自增ID。


特点是准连续的自增数字,为什么说是准连续?因为性能考虑,每个Client一次会领20个ID回去慢慢用,用完了再来拿。另一个Client过来,拿的就是另外20个ID了。


新浪微博里,Tim用Redis做相同的事情,Incr一下拿一批ID回去。如果有多个数据中心,那就拿高位的几个bit来区分。


只要舍得在总架构里增加额外Redis带来的复杂度,一个64bit的long就够表达了,而且不可能有重复ID。


批量是关键,否则每个ID都远程调用一次谁也吃不消。


2. UUID


2.1 概述


Universally Unique IDentifier(UUID),有着正儿八经的RFC规范,是一个128bit的数字,也可以表现为32个16进制的字符,中间用”-”分割。


- 时间戳+UUID版本号,分三段占16个字符(60bit+4bit),

- Clock Sequence号与保留字段,占4个字符(13bit+3bit),

- 节点标识占12个字符(48bit),


比如:f81d4fae-7dec-11d0-a765-00a0c91e6bf6


实际上,UUID一共有多种算法,能用于TraceId的是:


- version1: 基于时间的算法

- version4: 基于随机数的算法


version 4


先说Version4,这是最暴力的做法,也是JDK里的算法,不管原来各个位的含义了,除了少数几个位必须按规范填,其余全部用随机数表达。


JDK里的实现,用 SecureRandom生成了16个随机的Byte,用2个long来存储。记得加-Djava.security.egd=file:/dev/./urandom,否则会锁住程序等噪音。


version 1


然后是Version1,严格守着原来各个位的规矩:


因为时间戳有满满的60bit,所以可以尽情花,以100纳秒为1,从1582年10月15日算起(能撑3655年,真是位数多给烧的,1582年有意思么)


节点标识也有48bit,一般用MAC地址表达,如果有多块网卡就随便用一块。如果没网卡,就用随机数凑数,或者拿一堆尽量多的其他的信息,比如主机名什么的,拼在一起再hash一把。


顺序号这16bit则仅用于避免前面的节点标示改变(如网卡改了),时钟系统出问题(如重启后时钟快了慢了),让它随机一下避免重复。


但好像Version 1就没考虑过一台机器上起了两个进程这类的问题,也没考虑相同时间戳的并发问题,所以严格的Version1没人实现,接着往下看各个变种吧。


3. Version1变种 – Hibernate


Hibernate的CustomVersionOneStrategy.java,解决了之前version 1的两个问题


- 时间戳(6bytes, 48bit):毫秒级别的,从1970年算起,能撑8925年….

- 顺序号(2bytes, 16bit, 最大值65535): 没有时间戳过了一秒要归零的事,各搞各的,short溢出到了负数就归0。

- 机器标识(4bytes 32bit): 拿localHost的IP地址,IPV4呢正好4个byte,但如果是IPV6要16个bytes,就只拿前4个byte。

- 进程标识(4bytes 32bit): 用当前时间戳右移8位再取整数应付,不信两条线程会同时启动。


值得留意就是,机器进程和进程标识组成的64bit Long几乎不变,只变动另一个Long就够了。


4. Version1变种 – MongoDB


MongoDB的ObjectId.java


- 时间戳(4 bytes 32bit): 是秒级别的,从1970年算起,能撑136年。


- 自增序列(3bytes 24bit, 最大值一千六百万): 是一个从随机数开始(机智)的Int不断加一,也没有时间戳过了一秒要归零的事,各搞各的。因为只有3bytes,所以一个4bytes的Int还要截一下后3bytes。


- 机器标识(3bytes 24bit): 将所有网卡的Mac地址拼在一起做个HashCode,同样一个int还要截一下后3bytes。搞不到网卡就用随机数混过去。


- 进程标识(2bytes 16bits):从JMX里搞回来到进程号,搞不到就用进程名的hash或者随机数混过去。


可见,MongoDB的每一个字段设计都比Hibernate的更合理一点,比如时间戳是秒级别的。总长度也降到了12 bytes 96bit,但如果果用64bit长的Long来保存有点不上不下的,只能表达成byte数组或16进制字符串。


另外对Java版的driver在自增序列那里好像有bug。


5. Twitter的snowflake派号器


snowflake也是一个派号器,基于Thrift的服务,不过不是用redis简单自增,而是类似UUID version1,


只有一个Long 64bit的长度,所以IdWorker紧巴巴的分配成:


- 时间戳(42bit) 自从2012年以来(比那些从1970年算起的会过日子)的毫秒数,能撑139年。

- 自增序列(12bit,最大值4096), 毫秒之内的自增,过了一毫秒会重新置0。

- DataCenter ID (5 bit, 最大值32),配置值。

- Worker ID ( 5 bit, 最大值32),配置值,因为是派号器的id,所以一个数据中心里最多32个派号器就够了,还会在ZK里做下注册。


可见,因为是派号器,把机器标识和进程标识都省出来了,所以能够只用一个Long表达。


另外,这种派号器,client每次只能一个ID,不能批量取,所以额外增加的延时是问题。


6. 最后问题,能不能不用派号器,又一个Long搞定UUID??


前面说这么多都是铺垫,如果当初你的ID一开始类型设为了Long,又不用派号器的话,怎么办?

从UUID的128位压缩到Long的64位,又不用中央派号器而是本地生成,最难还是怎么来区分本地的机器+进程号。


思路一,压缩其他字段,留足够多的长度来做机器+进程号标识

时间戳是秒级别,1年要24位,两年要25位…..

自增序列,6万QPS要16位,10万要17位…

剩下20-24位,百万分之一到一千六百万分之一的重复率,然后把网卡Mac+进程号拼在一起再hash,取结果32个bit的后面20或24个bit。但假如这个标识字段重复了,后面时间戳和自增序列也很容易重复,不停的重复。


思路二,使用ZK 或 mysql 或 redis来自增管理标识号

如果workder字段只留了12位(4096),就要用ZK或etcd,当进程关闭了要回收这个号。

如果workder字段的位数留得够多,比如有20位(一百万),那用redis或mysql来自增最简单,每个进程启动时拿一个worker id。


思路三,继续Random

继续拼了,直接拿JDK UUID.randomUUID()的低位long(按UUID规范,高位的long被置了4个默认值的bit,低位只被设置3个bit),或者直接SecureRandom.nextLong(),不浪费了那3个bit。


来源:江南白衣

地址:http://calvin1978.blogcn.com/articles/uuid.html


: . Video Mini Program Like ,轻点两下取消赞 Wow ,轻点两下取消在看

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存