从 MongoID 的生成讨论分布式唯一 ID 生成方案

背景

>MongoDB，想必大家都使用过，在数据落盘后，查询该条数据时，会发现其会自动生成一条"_id"，如：

>

db.test.insert({"name":"tom"})

查询结果：

{ "_id" : ObjectId("5fd049327fbb28868f4660a5"), "name" : "tom" }

>MongoID 作为主键索引，即使是集群情况下，其在整个数据库中也是全局唯一的。

那这种 ID 有什么用呢？或者说在哪些场景下会被使用呢？

当然需要满足下面两个条件：

1.数据量现在或未来比较大，处于增长状态。

2.需要用唯一 ID 来标识。

比如说订单，优惠券，消息，待检索或处理数据（地图 poi 数据，蜘蛛抓取的数据）等等。

那这些场景 ID 需要什么特性呢：

>1.全局唯一。这是肯定的，两个不同订单生成了相同的 ID，那怎么区分呢？

>2.趋势递增。生成的 ID 可能用作数据库索引，而一些数据库索引是 B+树索引，如果趋势递增，则更能使用磁盘的块读取存储特性，提高写入性能。

>3.高性能，高可用。不能成为业务瓶颈。

>4.非连续。如果该 ID 对外使用，则很容易得知一天的数据量。如果是详情 ID，也很容易被批量抓取。

>5.字节占用少。如果全由数字构成，则存储，排序更高效。如 1111111 比 aaaaaa-111111 在存储及排序方面更有优势

>

MongoID 构成

MongoID 使用 12 个字节来表示,每个字节两位十六进制。如下图：

而平时业务中需要先生成 ID 供业务方使用，那有哪些方案呢？

方案一：

使用 UUID 生成器（很多编程语言自带 UUID 生成）。生成格式为：xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx

生成的格式是长字符串，如：123e4567-e89b-12d3-a456-426655440000，如果作为主键，存储及索引性能低。

方案二：

使用自增 ID（用程序生成或借助 mysql，redis）。但是会存在下面问题：

>1.不满足特性 4 的非连续，不过如果仅内部使用，倒无所谓。

>2.我们提到的是分布式，而这种方案如果要分布式提供服务，则运营成本很大。主要表现为新增机器及机器异常重启时。

>

比如说我们现在有两个机器 A 和 B，则 A 机器可以用起始值 1，步长 2（其生成的 ID 为：1，3，5，7...）；

>

机器 B 起始值为 2，步长为 2（其生成的 ID 为：2，4，6...），来满足全局唯一性。

>

如果随着业务增长，需再增加一台机器呢？那我们步长得改为 3.起始值得设为一个比现在生成的最大值更大的值，另外两台机器都得做调整。

另外需要记录当前机器生成的最大值，在机器异常重启后进行恢复。

方案三：

使用号段。

>具体做法是在数据库中存储一个最大值字段 MaxValue，然后开始计数，仅当值到达 MaxValue 后再更新最大值（一种预先分配的思想，仅记录最大值）。

>如：数据库最大值为 10000，每次到达后步长+10000，发号机当前值为 0，则各业务从发号机取号，每次发号+1，则到达 10000 后，更新数据库，数据库中最大值变更为 20000，发号机器从 10000 逐渐增加到 20000。

>如果各业务想进行隔离，则数据库中可以存储该业务方 ID。

方案四：

基于雪花算法(Snowflake)

该算法是 twitter 公司内部分布式项目采用的 ID 生成算法。

使用了 8 字节（64 位），比 MongoID 位数少 4 字节，具体如下：

其生成的结果为 int64。其中第一位保留不用（正数），其余位具体见上图。

其中机器 ID 最大为：1024，

自增序列号最大为 4096，即 1 毫秒内最多生成 4096 个数，如果需求超过，需要等待到下一毫秒（qps 高达 4096000，一般业务基本用不到），可支持使用

2^41/(1000360024*365)=69.7 年，且无需借助数据库，可以说性能很高，而且因为其毫秒时间戳设计，如果不是 1 毫秒内连续生成，则就不会连续。

那雪花算法有什么缺点吗？

那就是时间回拨。雪花算法依赖系统时间，如果出现了时间回拨，则生成的 ID 就无法保证全局唯一了。

那还有什么更好的方案吗？

我希望在雪花算法基础上做出这样一款分布式 ID 生成：

>1.生成 ID 时不依赖系统时间，这样就不会有时间回拨.

>

>2.性能更高：毕竟每次调用系统时间也是有不少时间消耗。

>3.最小依赖，无需运营。这样在新增机器，或者机器重启时无需人工运营。

于是我设计了这样一款分布式 ID 生成器-流星算法。

先上下其和雪花算法的 benchmark 对比。

运行机器：联想小新 pro13 Ryzen 5 3550H

go 版本：1.15

goos: windows

goarch: amd64

BenchmarkSnowflake-8

4917643 244 ns/op 0 B/op 0 allocs/op

BenchmarkMeteor-8

52173231 22.6 ns/op 0 B/op 0 allocs/op

可以看出流星算法比雪花算法快 10 倍，下面介绍下流星算法。

方案五：

流星算法

也是 64 位，

算法组成：

设计初衷：

第一位同样保留（正数）

Data 位为当前 NodeID 被创建时的秒级差，这样只在 NodeID 创建时需要依赖系统时间，后续生成 ID 时就无需系统时间，就可以防止时间回拨。

NodeID 位为节点 ID，为了确保生成 ID 唯一，如果发生了新增机器或服务重启，则 NodeID 需要每次增加。这样即使发生了时间回拨，由于 NodeID 唯一，则可以保证最终生成 ID 唯一性。

自增序列号，11 位，最大 2048。每次生成，自增序列号+1，当加满后，Data 位+1。

随机数位，3 位。为什么不把自增序列号和随机数位合成为自增序列号位呢？主要是为了特性 4：非连续性。

雪花算法在生成时依赖了毫秒，时间位很细，只有都在这一毫秒内连续生成的 ID 才会连续，这种条件非常苛刻（qps 达到 4096000 生成才会连续）。

所以加了这个随机数位来保证生成的 ID 非连续。那随机数如何生成呢？大多数随机数以系统时间作为种子，但是这样就达不到去系统时间的高性能了，我希望一种不依赖系统时间的高效随机数生成算法。最终选用了Xorshift算法。

生成 10 个 ID 如下：

5016762319896585

5016762319896596

5016762319896600

5016762319896614

5016762319896616

5016762319896626

5016762319896635

5016762319896640

5016762319896651

5016762319896656

总结下来就是，

>1.NodeID 创建时依赖当前系统时间，但是生成时不需系统时间来达到去系统时间化，这样就解决了时间回拨。

>2.NodeID 每次需要跟以前不重复。这样就保证了全局唯一。

>3.随机数位保证了生成 ID 非连续。

在使用时可以使用 Mysql 自增 ID 来注册 NodeID。