常用UniqueID的生成方法

2016-01-24

常用UniqueID的生成方法

这几天在与其他的系统进行联调的时候,出现了对方的唯一ID使用的是Int32来存储,而我们提供的UniqueID是标准的UUID,从而导致他们无法存储的问题.由于他们是一个历史的老系统,牵扯很深,所以无法进行改造,只能我们来适应它(幸好和它们交互的数据不会太多.应该不会超过Int32的上限).从而引出了对UniqueID生成方法的思考.这里列出了几种常用的UniqueID的生成办法.

基于数据库的发号器

这个是最常见和最容易想到的生成UniqueID的方法.也就是依赖数据库的自增ID来获取唯一ID,由于在分布式系统中数据库都是做了分布式或同步的,因此能保证数据库的自增键或序列是不会重复的.

在Oracle中,可以创建一个序列,然后使用序列的nextVal来获取.
在Mysql中,由于没有序列的概念,只能创建一个表,表的主键设置为自增.要获取UniqueID的时候就不断的往这个表中插入记录,获取last_insert_id()即可.为了避免表的记录数过多,可以考虑采用使用回滚的方式来规避.
在redis中,可以使用INCR key这个命令来获取一个自增的key,每调用一次,key值增加1.如果没有这个key值,则初始化key值为0.

使用这种方案的优点就是可以满足像Int32这种短数据的唯一.而缺点就是增加了系统的复杂性.需要在系统中强依赖数据库,并且获取UniqueID是需要与数据库交互的,虽然可以一次批量的获取几个ID,但是总体来说,性能会有损失.

基于规则计算的UniqueID

这一大类就是通过某些计算的规则,在分布式的每台机器上独立计算获取UniqueID,最常见的就是UUID了.

UUID

UUID全称Universally Unique IDentifier.它是由OSF(开源软件基金会 Open Software Foundation)所颁布的一种唯一ID计算的规则.它是一个可以表示层32个16进制字符的128bit的数字.中间用-符号分隔.常见的形式为:xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx.
其中前面的16个字符表示的是时间戳和UUID版本号,接下来的4个字符表示的是时间序列以及保留字段,最后12个字符是节点标识.

目前有Version1-5 5个版本:

Version1:基于时间的UUID,这个版本的UUID可以保证在全球范围内的唯一性.
这个版本有60位的字节来表示时间,精确到纳秒,因此基本上保证了时间上的不重复,并且最后还有48位字节的节点信息,是由MAC地址等硬件信息来表达的.中间的16位时钟序列则用于避免其他信息改变(机器时间错误,MAC地址手动填写冲突等)的情况下增加的一个随机码. 基本上可以说这个版本的UUID就可以满足高并发的分布式系统下的UniqueID的唯一.
Version2:DCE安全的UUID,这个版本的UUID的算法和Version1的是相同的,但是会把时间戳的前4位置换为POSIX的UID或GID.这个版本的UUID使用的比较少.
Version3:基于名字MD5的UUID,这个版本的UUID通过计算名字和名字空间的MD5散列值而得到结果.这个版本的UUID保证了:相同命名空间中不同名字生成的UUID是唯一的,不同命名空间中的UUID的唯一性,但是相同名字空间中相同名字的UUID是可能会重复的.因此,一般不用作UniqueID的生成.
Version4:这个版本也是使用的比较多的,也是JAVA中UUID.randomUUID()方法的实现规则.它不关心UUID的各个位置上的规则,直接使用SecureRandom生成16个随机的字节.然后把第6个字节设置为Version4,把第8个字节设置为IETF标识.
Version5:基于名字SHA1的UUID,这个版本的UUID算法和Version3的是一样的,只是把名字和命名空间的散列算法改为了SHA1

从这几个版本中可以看出,Version1和Version2是最适合于分布式计算环境下,具有高度唯一性的UniqueID,而Version3和Version5适用于一定范围内名字唯一的情况.而Version4在分布式的情况下,最好不要用,虽然是随机的,但是说不准在高并发的情况下,就有可能重复.
因此,如果要在JAVA中生成Version1的UUID,可以使用以下这个jar包

<dependency>
          <groupId>com.eaio.uuid</groupId>
          <artifactId>uuid</artifactId>
          <version>3.2</version>
      </dependency>

MongoDB的ObjectID

在Mongo数据库中,每一个文档必须有一个”_id”建,默认情况下这个是一个ObjectId的值.而ObjectId就是使用了序列计算的方式来获取这个唯一值.

ObjectID使用了12个字节来进行存储,每个字节表示两位十六进制数字,是一个24位的字符串.
它的前4位表示的是时间戳,单位为秒.通过这个可以大致的保证唯一性,并且可以通过这4个字符来获取文档的创建时间.
接下来的3字节是所在主机的唯一标识符,通常是机器的主机名的散列值.
再后面的两字节表示的是生成这个ObjectID的进程的ID号(PID)
这样,前9位就保证了同一秒中不同机器不同进程产生的ObejctId是唯一的.而后3字节就是一个自增的计数器,确保相同进程同一秒内产生的ObjectId也是不一样的.这样同一秒中类允许最多每个进程拥有16777215个不同的ObjectID.这基本上是不可能重复了.

Twitter的snowflake算法

为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一个唯一的ID,这些id还需要一些大致的顺序.因此,Twitter公布了他们的Snowflake算法来生成这个唯一UniqueID.

Snowflake算法生成的唯一键是由64位组成的.在默认的情况下:分为了4组.
第一位的0预留不使用.
第二组是41位的时间戳.精确到毫秒.
第三组的10位是工作机器的Id.默认可以使用MAC地址来唯一标识,当然使用进程号也是可以的.
第四组是12位的序列号,同mongo的ObjectID相同,也是一个自增的ID.可以保证1毫秒产生4095个不重复的自增序列.
这个算法的优势就是一个Int64就可以进行存储,比UUID等的128位减少了很多

总结

基本上常见的分布式情况下的UniqueID的生成方法就分为了两大类,一类是基于分配的发号器,另外一类是基于规则计算的唯一序列.而后者的常用算法通常就是UUID以及OjbectID和SnowFlake
基于发号器的优势在于可以按照准连续的增加,可以用于Int32等的存储.但是性能和系统复杂度上存在一定的缺陷.
而基于计算规则的优势主要是分布式情况下,各机器独立运算,性能上有保证.但是通常都需要使用64位以上的空间来进行存储.
具体如何选择,需要在项目中具体的分析.