MongoDB 系列 - ObjectId() 是如何实现的 “千万级” 分布式唯一 ID？

*** 系列 - ObjectId() 是如何实现的 “千万级” 分布式唯一 ID？

谈起分布式 ID，经常会聊到的一些方案是使用 Twitter 的 Snowflake 算法、UUID、数据库自增 ID 等。前些时间看了下 *** ObjectId() 的实现原理，也不失为一种好的实现思路，正如标题所描述的，本文会给大家分享下在 *** 中是如何实现的 “千万级” 分布式唯一 ID。

*** 一开始的设计就是用来做为分布式数据库，插入数据时默认使用 _id 做为主键，下面这个 _id 就是 *** 中开源的分布式系统 ID 算法ObjectId()生成的。

new ObjectId("632c6d93d65f74baeb22a2c9")

关于其组成需要指出一个误区，网上很多介绍 *** ObjectId() 的文章，都有这样一段描述：

4 字节的时间戳 + 3 个字节机器标识码 + 2 个字节进程号 + 3 个字节自增数

很长一段时间我也一直这样认为，直到前些时间看了源码之后，发现中间的 3 个字节机器标识码 + 2 个字节进程号已被替换为 5 个字节的进程唯一标识，之后翻阅了 *** 官方文档 描述也确实如此。

4 字节的时间戳（单位：秒） + 5 个字节的进程唯一标识 + 3 个字节自增数

这个组成规则反映出几个问题：

因为前 4 个字节使用了时间戳，以 “秒” 为单位，总体上是递增的，也就是为什么我们有时可以使用 _id 替换 创建时间做为排序规则的依据，另外一个疑问，如果用 _id 做为时间筛选条件，该怎么做？中间 5 个字节随机值，是进程唯一标识，在进程启动之后，只需要生成一次。在一些限定条件下谈 ObjectId() 的 “唯一性”，后 3 个字节为自增数，1 个字节等于 8 位，在 1 秒之内，可以产生 Math.pow(2, 24) - 1 = 16777215 个唯一 ID，因此文章开头我用了 “千万级” 描述，这已经够了，当下突破这个限制几乎不太可能。

实现自定义 UniqueId()

实现会用到一些 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 ->

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 ->

Node.js 中的 buffer 是用来处理二进制数据的，例如下面的 “2e” 二进制为 00101110，那么二进制方式在用户这一侧看起来显然不是很方便，Node.js buffer 中我们所看到的其实是内存实际存储的值，转换为了十六进制表示（00 ～ ff）。

如果想取到存进去的时间戳，使用 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...  这样依次生成的，实现步骤为：

16777215 二进制表示：11111111 11111111 11111111255(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 ->

总结

本文从理论到实践，实现了一个自定义的 UniqueId()，这是一个最简化的 *** ObjectId() 实现，代码量也不多，感兴趣的可以自己实现一遍，加深理解。

文章开头提到了一个问题 “*** ObjectId() 生成的 id 是唯一的吗？” 答案即是 Yes 也是 No，在 1 秒钟内且进程唯一标识不重复的情况下，根据后 3 Byte 自增数可以得到生成的最大不重复 id 为 2^24 - 1 = 16777215 个唯一 ID。

最后，留一个问题，为什么 *** ObjectId() 可以不用 new 就能生成一个 ID 呢？并且显示的结果和上面自定义的 UniqueId() 也不一样，关于 *** ObjectId() 还有很多玩法，下一篇介绍。

console.log(ObjectId()); // 原生 ObjectId 输出结果：new ObjectId("633304ee48d18c808c6bb23a")console.log(new UniqueId()); // 自定义 UniqueId 输出结果：UniqueId { [Symbol(id)]:

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。