分布式id生成方案概述

code4it

发布于 2018-09-17 14:55:58

1.2K0

文章被收录于专栏：码匠的流水账码匠的流水账

序

本文主要来聊聊分布式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

UidGenerator

+———————-+————————+————————+

|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个并发。