花钱的年华

江南白衣,公众号:春天的旁边

服务化框架-分布式Unique ID的生成方法一览

| Filed under 技术

分布式的Unique ID的用途如此广泛,从业务对象Id到服务化体系里分布式调用链的TraceId,本文总结了林林总总的各种生成算法。

对于UID的要求,一乐那篇《业务系统需要什么样的ID生成器》的提法很好: 唯一性,时间相关,粗略有序,可反解,可制造。

 

1. 发号器

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

特点是准连续的自增数字,为什么说是准连续?因为性能考虑,每个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进制的字符(每个字符0-F的字符代表4bit),中间用"-"分割。

  • 时间戳+UUID版本号: 分三段占16个字符(60bit+4bit),
  • Clock Sequence号与保留字段:占4个字符(13bit+3bit),
  • 节点标识:占12个字符(48bit),

比如:

f81d4fae-7dec-11d0-a765-00a0c91e6bf6

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

  • version1: 基于时间的算法
  • version4: 基于随机数的算法

2.2 version 4 基于随机数的算法

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

JDK里的实现,用 SecureRandom生成了16个随机的Byte,用2个long来存储。记得加-Djava.security.egd=file:/dev/./urandom,
详见SecureRandom的江湖偏方与真实效果

 

2.3 version 1 基于时间的算法

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

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

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

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

但这里的顺序号并不是我们想象的自增顺序号,而是一个一次性的随机数,所以如果两个请求在同100个纳秒发生时。。。。。

还有这里的节点标识只在机器级别,没考虑过一台机器上起了两个进程。

所以严格的Version1没人实现,接着往下看各个变种吧。

 

2.4 version 1 vs version4

version4随机数的做法简单直接,但以唯一性,时间相关,粗略有序,可反解,可制造做要求的话,则不如version4,比如唯一性,因为只是两个随机long,并没有从理论上保证不会重复。
 

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位再取整数应付,不信两条线程会同时启动。

顺序号也不再是一次性的随机数而是自增序列了。

节点标识拆成机器和进程两个字段,增加了从时间戳那边改变精度节约下来的16bit。另外节点标识这64bit(1个Long)总是不变,节约了生成UID的时间。

 

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进制字符串。

 

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里做下莫道不消魂注册。

可见,因为是中央派号器,把至少40bit的节点标识都省出来了,换成10bit的派号器标识。所以整个UID能够只用一个Long表达。

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

 

6. 扩展阅读

《细聊分布式ID生成方法》

《生成全局唯一ID的3个思路,来自一个资深架构师的总结》

 

7. 扩展问题,能不能不用派号器,又一个Long搞定UUID??

这是我们服务化框架一开始的选择,TraceID设为了一个Long,而不是String,又不想用派号器的话,怎么办?

从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

继续拼了,因为traceId的唯一性要求不高,偶然重复也没大问题,所以直接拿JDK UUID.randomUUID()的低位long(按UUID规范,高位的long被置了4个默认值的bit,低位只被设置3个bit),或者不用UUID.randomUUID()了,直接SecureRandom.nextLong(),不浪费了那3个bit。

你猜我们最后选了哪种?

我的公众号: jnby1978,谢谢。

 

发表评论

您的电子邮箱不会被公开。

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>