“我正在参与「启航计划」”

本文开端,先提个问题:“MongoDB ObjectId() 生成的 id 是仅有的吗?”,答案在下文揭晓。

谈起分布式 ID,经常会聊到的一些计划是运用 Twitter 的 Snowflake 算法、UUID、数据库自增 ID 等。前些时刻看了下 MongoDB ObjectId() 的完成原理,也不失为一种好的完成思路,正如标题所描绘的,本文会给咱们共享下在 MongoDB 中是如何完成的 “千万级” 分布式仅有 ID。

MongoDB 一开端的规划便是用来做为分布式数据库,刺进数据时默许运用 _id 做为主键,下面这个 _id 便是 MongoDB 中开源的分布式体系 ID 算法ObjectId()生成的。

new ObjectId("632c6d93d65f74baeb22a2c9")

关于其组成需求指出一个误区,网上很多介绍 MongoDB ObjectId() 的文章,都有这样一段描绘:

// 过时的规矩,现在现已不用 机器标识 + 进程号
// 一种猜测,现在大多运用容器化,在容器内有独立的进程空间,它的进程号永久可能都为 1,还有创建几台虚拟机,其中的 hostname 可能也都为 localhost
4 字节的时刻戳 + 3 个字节机器标识码 + 2 个字节进程号 + 3 个字节自增数

很长一段时刻我也一直这样以为,直到前些时刻看了源码之后,发现中心的 3 个字节机器标识码 + 2 个字节进程号已被替换为 5 个字节的进程仅有标识,之后翻阅了 MongoDB 官方文档 描绘也的确如此。

// 当时 ObjectId 完成规矩
4 字节的时刻戳(单位:秒) + 5 个字节的进程仅有标识 + 3 个字节自增数

这个组成规矩反映出几个问题:

  • 由于前 4 个字节运用了时刻戳,以 “秒” 为单位,总体上是递增的,也便是为什么咱们有时能够运用 _id 替换 创建时刻做为排序规矩的根据,别的一个疑问,如果用 _id 做为时刻筛选条件,该怎么做?
  • 中心 5 个字节随机值,是进程仅有标识,在进程发动之后,只需求生成一次。
  • 在一些约束条件下谈 ObjectId() 的 “仅有性”,后 3 个字节为自增数,1 个字节等于 8 位,在 1 秒之内,能够发生 Math.pow(2, 24) - 1 = 16777215 个仅有 ID,因此文章最初我用了 “千万级” 描绘,这现已够了,当下突破这个约束简直不太可能。

完成自定义 UniqueId()

下面让咱们开端实践,参阅 源码 写一个最简化的 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);
    // 4-byte timestamp
+    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);
    // 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];
    return buffer;
  }
}

3 Byte 自增数

最终 3 Byte 为自增数,是要害的一部分,在 1 秒钟内、进程标识仅有的情况下,一个 ObjectId() 能生成多少个不重复的 ID,由这 3 Byte 决议。

自增数不是简单的了解为 0、1、2… 这样顺次生成的,完成步骤为:

  • Math.random() * 0xffffff 首要生成一个 3 Byte 的随机数做为起始值(这样也加大了发生重复的机率),声明在类的静态属性上(相当于 UniqueId.index = Math.random() * 0xffffff0xffffff是一个十六进制数,等价于十进制的 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> }

本文首发于个人 Blog,欢迎重视!