唯一ID生成算法
前言
唯一ID在互联网大厂的业务线中广泛使用，比如订单号、数据库主键、IM消息序号、交易流水号等等，这些ID的共同特点是唯一标记某一个业务记录或者消息、部分ID自增、全局有序或者局部有序。
UUID作为是一种全局唯一的方案是可供使用的选择之一，但在实际操作中大家一般使用的很少，几个原因：
- 16个字节128位占用太多的存储空间不适合用来作为主键；
- UUID的版本1基于MAC地址和时间戳，可保证全局唯一，但容易被硬件追踪;
- 后续版本使用伪随机数、SHA1又没有前向兼容，用在特定业务的一定范围内使用没有问题，但作为分布式系统的唯一ID不适合。
所以就有了各个互联网大厂分享的各自业务中实现唯一ID的不同算法和系统部署方案，唯一ID算法主要核心聚焦在以下几点：
- ID位数
- ID算法原理
- 全局唯一
- 全局(局部)趋势有序
- 时钟回拨问题
- 外部系统依赖
技术实现汇总
从大厂分享的技术实现汇总如下：
| 厂牌 | 技术方案 | ID位数 | 全局唯一 | 有序 | 时钟回拨 | 外部系统依赖 |
|---|---|---|---|---|---|---|
| SnowFlake | 64 | 全局唯一 | 局部有序 | block wait | ||
| MongoDB | ObjectId，与SnowFlake类似 | 96 | 全局唯一 | 局部有序 | \ | None |
| 百度 | UidGenerator，与SnowFlake类似 | 64 | 全局唯一 | 局部有序 | 兼容 | None |
| 微信 | 与SnowFlake类似 | 64 | 全局唯一 | 场景有序 | \ | None |
| 美团 | Leaf-segment | 64 | 全局唯一 | 全局有序 | \ | MySQL |
| 美团 | Leaf-snowerFlake ，与SnowFlake类似 | 64 | 全局唯一 | 局部有序 | fixed or interrupt | Zookeeper |
| 融云 | 自定义 | 80 | 全局唯一 | 场景有序 | \ | None |
技术细节
算法
- 1bit - 默认为0
- 41bit - 毫秒时间戳
- 10bit - 机器ID
- 12bit - 自增序列号
最多支持69年，1024台机器，QPS 409.6w/s
参考
MongoDB
算法
- 32bit - unix timestamp second
- 24bit - 机器ID
- 16bit - 进程ID
- 24bit - 序列号，随机数开始
参考
百度
算法
- 1bit - 默认为0
- 28bit - 基于服务启动时间的增加时间，秒
- 22bit - 服务启动次数
- 13bit - 自增序列号，QPS 4096/s
参考
微信
算法
uid用户空间内独立自增的64bit ID，支持分区读取、持久化。
参考
美团
算法
Leaf-snowflake，参考SnowerFlaker设计。
Leaf-segment，类似微信方案，bid业务空间内独立自增，支持双buffer预读取、DB持久化。
参考
融云
算法
- 42bit - 时间戳，毫秒
- 12bit - 序列号
- 4bit - 会话类型
- 12bit - 会话ID
因为融云本身的业务就是IM消息，所以ID强耦合了他们的IM系统服务，IM消息系统可以参考。