• 近期将进行后台系统升级,如有访问不畅,请稍后再试!
  • 极客文库-知识库上线!
  • 极客文库小编@勤劳的小蚂蚁,为您推荐每日资讯,欢迎关注!
  • 每日更新优质编程文章!
  • 更多功能模块开发中。。。

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

分布式的 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,否则会锁住程序等噪音。
详见 JVM 上的随机数与熵池策略


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。

扩展阅读

一乐那篇《业务系统需要什么样的 ID 生成器》,其中 唯一性,时间相关,粗略有序,可反解,可制造 这个提法很好,说白了就是让大家尽量用 UUID version1 风格。

业务系统需要什么样的 ID 生成器

细聊分布式ID 生成方法


丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:分布式 Unique ID 的生成方法一览
喜欢 (0)
[247507792@qq.com]
分享 (0)
勤劳的小蚂蚁
关于作者:
温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

欢迎 注册账号 登录 发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00