MongoDB 系列 - ObjectId-- 是如何實現的 “千萬級” 分佈式唯一 ID？
本文開始，先提個問題：“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()
下面讓我們開始實踐，參考 源碼 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);
// 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() * 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> }本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/URuY22b8Hhmjx8iq4LWr1Q