MongoDB 一开始的设计就是用来做为分布式数据库,插入数据时默认使用 _id 做为主键,下面这个 _id 就是 MongoDB 中开源的分布式系统 ID 算法ObjectId()生成的。
new ObjectId("632c6d93d65f74baeb22a2c9")
关于其组成需要指出一个误区,网上很多介绍 MongoDB ObjectId() 的文章,都有这样一段描述:
4 字节的时间戳 + 3 个字节机器标识码 + 2 个字节进程号 + 3 个字节自增数
很长一段时间我也一直这样认为,直到前些时间看了源码之后,发现中间的 3 个字节机器标识码 + 2 个字节进程号已被替换为 5 个字节的进程唯一标识,之后翻阅了 MongoDB 官方文档 描述也确实如此。
4 字节的时间戳(单位:秒) + 5 个字节的进程唯一标识 + 3 个字节自增数
这个组成规则反映出几个问题:
- 因为前 4 个字节使用了时间戳,以 “秒” 为单位,总体上是递增的,也就是为什么我们有时可以使用 _id 替换 创建时间做为排序规则的依据,另外一个疑问,如果用 _id 做为时间筛选条件,该怎么做?
- 中间 5 个字节随机值,是进程唯一标识,在进程启动之后,只需要生成一次。
- 在一些限定条件下谈 ObjectId() 的 “唯一性”,后 3 个字节为自增数,1 个字节等于 8 位,在 1 秒之内,可以产生 Math.pow(2, 24) - 1 = 16777215 个唯一 ID,因此文章开头我用了 “千万级” 描述,这已经够了,当下突破这个限制几乎不太可能。
实现自定义 UniqueId()
下面让我们开始实践,参考 源码https://github.com/mongodb/js-bson/blob/HEAD/src/objectid.ts 写一个最简化的 ObjectId(),真正理解它的实现原理。编程语言为 JavaScript,运行环境 Node.js。
实现会用到一些 Node.js 的系统模块 API 和运算符,每一步都会对用到的知识做一个讲解。
初始化
按照它的组成规则,分步实现,首先,创建一个自定义的类,这里我命名为 UniqueId,并初始化一个 12 Byte 的 Buffer。
Buffer 是 Node.js 中的一个系统模块,Buffer.alloc() 按照指定字节数创建一段连续的内存空间,用来处理二进制数据,默认使用 0 进行填充,也可以指定字符进行填充,参见 API Buffer.alloc(size[, fill[, encoding]])。
const kId = Symbol('id');
class UniqueId {
constructor() {
this[kId] = UniqueId.generate()
}
get id() {
return this[kId];
}
static generate() {
const buffer = Buffer.alloc(12);
return buffer;
}
}
运行之后输出一个 0 填充的 12 Byte 的 buffer。
(new UniqueId()).id -> <Buffer 00 00 00 00 00 00 00 00 00 00 00 00>
4 Byte 时间戳
Date.now() 获取当前时间毫秒数,除以 1000 精确到秒,通过 Math.floor() 函数向下取整,取到一个整数。
buffer.writeUInt32BE() 将一个无符号的 32 位整数以高位优先(大端写入)方式写入到 buffer 中,32 位在这里占用的是 4 Byte,offset 设置为 0(默认 offset 就是 0),将时间戳写入到 buffer 的前 4 个字节。
const kId = Symbol('id');
class UniqueId {
constructor() {
this[kId] = UniqueId.generate()
}
get id() {
return this[kId];
}
static generate() {
const buffer = Buffer.alloc(12);
+ const time = Math.floor(Date.now() / 1000);
+ buffer.writeUInt32BE(time, 0);
+ return buffer;
}
}
运行之后可以看到 buffer 的前 4 个字节已被填充,对 Node.js Buffer 模块不太了解的,看到这个结果又迷惑了,buffer 里面存储的既不是二进制也不是十进制,到底是啥?
(new UniqueId()).id -> <Buffer 63 2e 90 c0 00 00 00 00 00 00 00 00>
Node.js 中的 buffer 是用来处理二进制数据的,例如下面的 “2e” 二进制为 00101110,那么二进制方式在用户这一侧看起来显然不是很方便,Node.js buffer 中我们所看到的其实是内存实际存储的值,转换为了十六进制表示(00 ~ ff)。
记住一点:“计算机底层使用的二进制,如果是用来展示通常是 10 进制,编程用的时候会采用 16 进制,内存地址编码使用的就是 16 进制。” 内存管理这块想了解更多可参考这篇文章 为什么递归会造成栈溢出?探索程序的内存管理!https://github.com/qufei1993/blog/issues/44
如果想取到存进去的时间戳,使用 buffer.readUInt32BE(offset) 方法,默认 offset 为 0,从 0 位开始读取前 4 Byte。
5 Byte 进程唯一标识
中间 5 Byte 没有规定实现方式,保证进程唯一就好,使用 Node.js 系统模块 crypto 提供的 randomBytes() 方法生成一个长度为 5 的随机字节。
+ const crypto = require('crypto');
+ let PROCESS_UNIQUE = null;
const kId = Symbol('id');
class UniqueId {
constructor() {
this[kId] = UniqueId.generate()
}
get id() {
return this[kId];
}
static generate() {
const buffer = Buffer.alloc(12);
const time = Math.floor(Date.now() / 1000);
buffer.writeUInt32BE(time, 0);
+
+ if (PROCESS_UNIQUE === null) {
+ PROCESS_UNIQUE = crypto.randomBytes(5);
+ }
+ buffer[4] = PROCESS_UNIQUE[0];
+ buffer[5] = PROCESS_UNIQUE[1];
+ buffer[6] = PROCESS_UNIQUE[2];
+ buffer[7] = PROCESS_UNIQUE[3];
+ buffer[8] = PROCESS_UNIQUE[4];
return buffer;
}
}
3 Byte 自增数
最后 3 Byte 为自增数,是关键的一部分,在 1 秒钟内、进程标识唯一的情况下,一个 ObjectId() 能生成多少个不重复的 ID,由这 3 Byte 决定。
自增数不是简单的理解为 0、1、2... 这样依次生成的,实现步骤为:
- Math.random() * 0xffffff 首先生成一个 3 Byte 的随机数做为起始值(这样也加大了产生重复的机率),声明在类的静态属性上(相当于 UniqueId.index = Math.random() * 0xffffff,0xffffff是一个十六进制数,等价于十进制的 16777215。
- 每次调用 getInc() 初始的随机数都会 +1,做为当前的随机自增数 inc,并做了取余操作,可以放心这个自增数永远都不会大于 16777215。
- buffer 中的每个字节用 16 进制表示,一个字节等于 8 位,最大能表示的数用二进制表示是11111111,转为 16 进制是 0xff,转为十进制是 255。现在我们知道了 buffer 中的一个字节所表达的 10 进制是不能大于 255 的,想实现一个字节存放的数不能大于 255 一个实现是做二进制与运算,本文用的也是这种方式,举个与运算的例子:
16777215 二进制表示:11111111 11111111 11111111
255(0xff)二进制表示: 00000000 00000000 11111111
与运算结果: 00000000 00000000 11111111
# 与运算是都为 1 则为 1,这里的结果最大是不会超过 255 的
在我们的实现中将当前随机自增数 inc 与 0xff 做与运算, 等同于将 inc 按照二进制方式把最右边 8 位赋值给了 buffer 的最后一个字节(buffer[11] = inc & 0xff),同理将 inc 向右偏移 8 位与 0xff 做与运算赋值给 buffer[10],inc 向右偏移 16 位与 0xff 做与运算赋值给 buffer[9]。
const crypto = require('crypto');
let PROCESS_UNIQUE = null;
const kId = Symbol('id');
class UniqueId {
+ static index = Math.floor(Math.random() * 0xffffff);
constructor() {
this[kId] = UniqueId.generate()
}
get id() {
return this[kId];
}
+ static getInc() {
+ return (UniqueId.index = (UniqueId.index + 1) % 0xffffff);
+ }
static generate() {
const buffer = Buffer.alloc(12);
// 4-byte timestamp
const time = Math.floor(Date.now() / 1000);
buffer.writeUInt32BE(time, 0);
// 5-byte process unique
if (PROCESS_UNIQUE === null) {
PROCESS_UNIQUE = crypto.randomBytes(5);
}
buffer[4] = PROCESS_UNIQUE[0];
buffer[5] = PROCESS_UNIQUE[1];
buffer[6] = PROCESS_UNIQUE[2];
buffer[7] = PROCESS_UNIQUE[3];
buffer[8] = PROCESS_UNIQUE[4];
+ // 3-byte counter
+ const inc = UniqueId.getInc();
+ buffer[11] = inc & 0xff;
+ buffer[10] = (inc >> 8) & 0xff;
+ buffer[9] = (inc >> 16) & 0xff;
+ return buffer;
}
}
以下为最终的生成结果,可以看到每个字节都被 1 个 16 进制数所填充。
(new UniqueId()).id -> <Buffer 63 33 01 c2 55 58 38 cf e0 be 75 46>
总结
本文从理论到实践,实现了一个自定义的 UniqueId(),这是一个最简化的 MongoDB ObjectId() 实现,代码量也不多,感兴趣的可以自己实现一遍,加深理解。
文章开头提到了一个问题 “MongoDB ObjectId() 生成的 id 是唯一的吗?” 答案即是 Yes 也是 No,在 1 秒钟内且进程唯一标识不重复的情况下,根据后 3 Byte 自增数可以得到生成的最大不重复 id 为 2^24 - 1 = 16777215 个唯一 ID。
最后,留一个问题,为什么 MongoDB ObjectId() 可以不用 new 就能生成一个 ID 呢?并且显示的结果和上面自定义的 UniqueId() 也不一样,关于 MongoDB ObjectId() 还有很多玩法,下一篇介绍。
console.log(ObjectId()); // 原生 ObjectId 输出结果:new ObjectId("633304ee48d18c808c6bb23a")
console.log(new UniqueId()); // 自定义 UniqueId 输出结果:UniqueId { [Symbol(id)]: <Buffer 63 33 04 ee f0 b2 b8 1f c3 15 53 2c>