分布式ID生成算法

分布式Unique ID在分布式系统使用很广泛，常用的用途有：

  1. 请求的ID，用于跟踪请求链路。
  2. 消息队列中的unique id。
  3. 业务对象的id。

总结下生成分布式ID常用算法。

数据库自增id

通过MySQL中的auto_increment特性来实现数据库唯一的ID。问题是扩展性差，性能受限于一台机器。可以做的优化是使用多个数据库实例，设置相同的步长和不同的起始值，避免重复产生ID。通过一个这种方式可以利用多台机器的资源。同时，还有一个优化是获取ID的时候可以批量获取ID，这样可以减少DB的操作，减少响应时间。

基于Redis，Postgres，Oracle也有类似的方案。

UUID

UUID由[0-9a-f-]字符组成，总共16个字节，转换成16进制的格式为：XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX。

数据由5个部分组成：

  1. 时间戳，占60位。
  2. 时钟序列，占13位。
  3. 结点编号，占48位。
  4. 版本号，版本不同以上1-3个字段的数据来源也不一样，占4位。
  5. UUID类型，用于解析UUID数据中的意义，占3位。

每个数据的位置：

    0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                          time_low                             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |       time_mid                |         time_hi_and_version   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |clk_seq_hi_res |  clk_seq_low  |         node (0-1)            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                         node (2-5)                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

time_hi_and_version的第4-7位是版本号，clk_seq_hi_res的第5-7位是UUID类型编号。

UUID类型常用的有是IETF和微软兼容的类型，UUID类型编号分别是10x和110，x是任意值。以下讨论的是IETF。

UUID总共有5个版本，每个版本数据源和算法各有差异。

版本 时间戳 时钟序列 结点编号 版本号
1 自1582年10月15号，100纳秒数 随机数。
如果时间戳回退，这个值需要在上一个序列上面递增		 mac地址 1
2 自1582年10月15号，100纳秒数，同时会把低4个字节替换成GID或者UID（根据domain值） 随机数。但是最低位会被替换成domain mac地址 2
3 给定命名空间和字符串通过MD5计算散列值 散列值 散列值 3
4 随机数 随机数 随机数 4
5 给定命名空间和字符串通过SHA-1计算散列值 散列值 散列值 5

最常用的还是版本1和4。显然，两个版本都无法保证绝对唯一。版本1在100纳秒里面就会重复，而版本4就是概率问题了。

mongodb的ObjectID

ObjectID是UUID版本1的变种。总共12个字节。

  1. 4个字节时间戳，unix时间，秒。
  2. 3个字节机器标识。
  3. 2个字节进程id。
  4. 3个字节计数，起始值是一个随机数，过秒不归零。

每秒能支持2^24-1个不同的id，千万级别。

twitter snowflake派号器

snowflake占8个字节。

  1. 1个bit保留。
  2. 41个bit的时间戳，unix时间，毫秒。
  3. 10个bit机器标识，5 bit是data center标识，5 bit是work标识。
  4. 12个bit的序号，过毫秒归零，保证id的递增。

没毫秒支持2^12=4096个不同的id。

UID要求

文章《业务系统需要什么样的ID生成器》的提法很好： 唯一性，时间相关，粗略有序，可反解，可制造。

扩展阅读

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

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

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

← 限流 mongodb索引 →
存档 关于