序
本文主要来聊聊分布式id的生成方案。
目标
业务系统需要什么样的ID生成器中提出了几点目标：
- 唯一性
- 时间相关
- 粗略有序
- 可反解
- 可制造
主要思路
对于每个标识，都需要有一个命名空间（namespace），来保证其相对唯一性。
分布式的ID生成，以Twitter Snowflake为代表的， Flake 系列算法采用的就是划分命名空间并行生成的思路。
UUID
UUID(Universally Unique Identifier)的标准型式包含32个16进制数字(每个字符0-F的字符代表4bit,共128bit)，以连字号分为五段，形式为8-4-4-4-12的32+4个字符。
比如bc96c351-bea3-4e53-b0a8-d9806763dd69。
主要的格式如下：
- 时间戳＋UUID版本号，分三段占16个字符(60bit+4bit)，
- Clock Sequence号与保留字段，占4个字符(13bit＋3bit)，
- 节点标识占12个字符(48bit)，
version 4 基于随机数的算法，也是JDK里的算法，不管原来各个位的含义了，除了少数几个位必须按规范填，其余全部用随机数表达。
mongo object id
通过“时间+机器码+pid+inc”共12个字节，通过4+3+2+3的方式最终标识成一个24长度的十六进制字符。ObjectId是一个12字节 BSON 类型数据，有以下格式：
- 4个字节表示的Unix timestamp
- 3个字节表示的机器的ID
- 2个字节表示的进程ID
- 3个字节表示的计数器
snow flake算法
个64 bits的唯一long型的ID，使用其中41bit作为毫秒数，10bit作为机器编号，12bit作为毫秒内序列号。IdWorker
+---------------+----------------+----------------+
|timestamp(ms)42 | worker id(10) | sequence(12) |
+---------------+----------------+----------------+
id = timestamp | workerid | sequence (eg. 1451063443347648410)
默认采用上图字节分配方式：
- 第一位为未使用，接下来的41位为毫秒级时间(41位的长度可以使用69年)
- 5位datacenterId和5位workerId(10位的长度最多支持部署1024个节点）
- 12位是毫秒内的计数（12位的计数顺序号支持每个节点每毫秒产生4096个ID序号）
snowflake生成的ID整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞（由datacenter和workerId作区分），并且效率较高。这个算法单机每秒内理论上最多可以生成1000*(2^12)，也就是400W的ID。
snow flake算法变种
Boundary flake
Boundary flakeID 长度扩展到 128 bits:
+---------------+----------------+----------------+
|timestamp(ms)64 | worker id(48) | sequence(16) |
+---------------+----------------+----------------+
id = timestamp | workerid | sequence
- 最高 64 bits 时间戳;
- 然后是 48 bits 的 Worker 号 (和 Mac 地址一样长);
- 最后是 16 bits 的 Seq Number
由于它用 48 bits 作为 Worker ID, 和 Mac 地址的长度一样, 这样启动时不需要和 Zookeeper 通讯获取 Worker ID. 做到了完全的去中心化
它这样做的目的是用更多的 bits 实现更小的冲突概率, 这样就支持更多的 Worker 同时工作. 同时, 每毫秒能分配出更多的 ID
Simple flake
simpleflake取消 Worker 号, 保留 41 bits 的 Timestamp, 同时把 sequence number 扩展到 22 bits
+---------------+----------------+
|timestamp(ms)42 | sequence(22)
+---------------+----------------+
id = timestamp | sequence
Simpleflake 的特点:
- sequence number 完全靠随机产生 (这样也导致了生成的 ID 可能出现重复)
- 没有 Worker 号, 也就不需要和 Zookeeper 通讯, 实现了完全去中心化
- Timestamp 保持和 Snowflake 一致, 今后可以无缝升级到 Snowflake
缺点： - 生成的 ID 重复的可能. 这个生成 ID 重复的概率随着每秒生成的 ID 数的增长而增长。
- 每秒生成的 ID 不能太多 (最好小于 100次/秒, 如果大于 100次/秒的场景, Simpleflake 就不适用
百度唯一id
+---------------+----------------+----------------+
|timestamp(ms)29 | worker id(22) | sequence(13) |
+---------------+----------------+----------------+
id = sign + delta seconds | workerid | sequence (eg. 1451063443347648410)
- timestap
sign(1bit)固定1bit符号标识，即生成的UID为正数。
delta seconds (28 bits)前时间，相对于时间基点"2016-05-20"的增量值，单位：秒，最多可支持约8.7年 - worker id (22 bits)
机器id，最多可支持约420w次机器启动。内置实现为在启动时由数据库分配，默认分配策略为用后即弃，后续可提供复用策略。 - sequence (13 bits)
每秒下的并发序列，13 bits可支持每秒8192个并发。
