談起分布式 ID，經(jīng)常會(huì)聊到的一些方案是使用 Twitter 的 Snowflake 算法、UUID、數(shù)據(jù)庫(kù)自增 ID 等。前些時(shí)間看了下 MongoDB ObjectId() 的實(shí)現(xiàn)原理，也不失為一種好的實(shí)現(xiàn)思路，正如標(biāo)題所描述的，本文會(huì)給大家分享下在 MongoDB 中是如何實(shí)現(xiàn)的 “千萬級(jí)” 分布式唯一 ID。

在布爾津等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供做網(wǎng)站、成都網(wǎng)站建設(shè) 網(wǎng)站設(shè)計(jì)制作按需策劃,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),營(yíng)銷型網(wǎng)站建設(shè),成都外貿(mào)網(wǎng)站建設(shè),布爾津網(wǎng)站建設(shè)費(fèi)用合理。

MongoDB 一開始的設(shè)計(jì)就是用來做為分布式數(shù)據(jù)庫(kù)，插入數(shù)據(jù)時(shí)默認(rèn)使用 _id 做為主鍵，下面這個(gè) _id 就是 MongoDB 中開源的分布式系統(tǒng) ID 算法ObjectId()生成的。

new ObjectId("632c6d93d65f74baeb22a2c9")

關(guān)于其組成需要指出一個(gè)誤區(qū)，網(wǎng)上很多介紹 MongoDB ObjectId() 的文章，都有這樣一段描述：

4 字節(jié)的時(shí)間戳 + 3 個(gè)字節(jié)機(jī)器標(biāo)識(shí)碼 + 2 個(gè)字節(jié)進(jìn)程號(hào) + 3 個(gè)字節(jié)自增數(shù)

很長(zhǎng)一段時(shí)間我也一直這樣認(rèn)為，直到前些時(shí)間看了源碼之后，發(fā)現(xiàn)中間的 3 個(gè)字節(jié)機(jī)器標(biāo)識(shí)碼 + 2 個(gè)字節(jié)進(jìn)程號(hào)已被替換為 5 個(gè)字節(jié)的進(jìn)程唯一標(biāo)識(shí)，之后翻閱了 MongoDB 官方文檔 描述也確實(shí)如此。

4 字節(jié)的時(shí)間戳（單位：秒） + 5 個(gè)字節(jié)的進(jìn)程唯一標(biāo)識(shí) + 3 個(gè)字節(jié)自增數(shù)

這個(gè)組成規(guī)則反映出幾個(gè)問題：

• 因?yàn)榍?4 個(gè)字節(jié)使用了時(shí)間戳，以 “秒” 為單位，總體上是遞增的，也就是為什么我們有時(shí)可以使用 _id 替換 創(chuàng)建時(shí)間做為排序規(guī)則的依據(jù)，另外一個(gè)疑問，如果用 _id 做為時(shí)間篩選條件，該怎么做？
• 中間 5 個(gè)字節(jié)隨機(jī)值，是進(jìn)程唯一標(biāo)識(shí)，在進(jìn)程啟動(dòng)之后，只需要生成一次。
• 在一些限定條件下談 ObjectId() 的 “唯一性”，后 3 個(gè)字節(jié)為自增數(shù)，1 個(gè)字節(jié)等于 8 位，在 1 秒之內(nèi)，可以產(chǎn)生 Math.pow(2, 24) - 1 = 16777215 個(gè)唯一 ID，因此文章開頭我用了 “千萬級(jí)” 描述，這已經(jīng)夠了，當(dāng)下突破這個(gè)限制幾乎不太可能。

實(shí)現(xiàn)自定義 UniqueId()

下面讓我們開始實(shí)踐，參考 源碼https://github.com/mongodb/js-bson/blob/HEAD/src/objectid.ts 寫一個(gè)最簡(jiǎn)化的 ObjectId()，真正理解它的實(shí)現(xiàn)原理。編程語言為 JavaScript，運(yùn)行環(huán)境 Node.js。

實(shí)現(xiàn)會(huì)用到一些 Node.js 的系統(tǒng)模塊 API 和運(yùn)算符，每一步都會(huì)對(duì)用到的知識(shí)做一個(gè)講解。

初始化

按照它的組成規(guī)則，分步實(shí)現(xiàn)，首先，創(chuàng)建一個(gè)自定義的類，這里我命名為 UniqueId，并初始化一個(gè)  12 Byte 的 Buffer。

Buffer 是 Node.js 中的一個(gè)系統(tǒng)模塊，Buffer.alloc() 按照指定字節(jié)數(shù)創(chuàng)建一段連續(xù)的內(nèi)存空間，用來處理二進(jìn)制數(shù)據(jù)，默認(rèn)使用 0 進(jìn)行填充，也可以指定字符進(jìn)行填充，參見 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;
  }
}

運(yùn)行之后輸出一個(gè) 0 填充的 12 Byte 的 buffer。

(new UniqueId()).id -> 

4 Byte 時(shí)間戳

Date.now() 獲取當(dāng)前時(shí)間毫秒數(shù)，除以 1000 精確到秒，通過 Math.floor() 函數(shù)向下取整，取到一個(gè)整數(shù)。

buffer.writeUInt32BE() 將一個(gè)無符號(hào)的 32 位整數(shù)以高位優(yōu)先（大端寫入）方式寫入到 buffer 中，32 位在這里占用的是 4 Byte，offset 設(shè)置為 0（默認(rèn) offset 就是 0），將時(shí)間戳寫入到 buffer 的前 4 個(gè)字節(jié)。

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

運(yùn)行之后可以看到 buffer 的前 4 個(gè)字節(jié)已被填充，對(duì) Node.js Buffer 模塊不太了解的，看到這個(gè)結(jié)果又迷惑了，buffer 里面存儲(chǔ)的既不是二進(jìn)制也不是十進(jìn)制，到底是啥？

(new UniqueId()).id -> 

Node.js 中的 buffer 是用來處理二進(jìn)制數(shù)據(jù)的，例如下面的 “2e” 二進(jìn)制為 00101110，那么二進(jìn)制方式在用戶這一側(cè)看起來顯然不是很方便，Node.js buffer 中我們所看到的其實(shí)是內(nèi)存實(shí)際存儲(chǔ)的值，轉(zhuǎn)換為了十六進(jìn)制表示（00 ～ ff）。

記住一點(diǎn)：“計(jì)算機(jī)底層使用的二進(jìn)制，如果是用來展示通常是 10 進(jìn)制，編程用的時(shí)候會(huì)采用 16 進(jìn)制，內(nèi)存地址編碼使用的就是 16 進(jìn)制。” 內(nèi)存管理這塊想了解更多可參考這篇文章 為什么遞歸會(huì)造成棧溢出？探索程序的內(nèi)存管理！https://github.com/qufei1993/blog/issues/44

如果想取到存進(jìn)去的時(shí)間戳，使用 buffer.readUInt32BE(offset) 方法，默認(rèn) offset 為 0，從 0 位開始讀取前 4 Byte。

5 Byte 進(jìn)程唯一標(biāo)識(shí)

中間 5 Byte 沒有規(guī)定實(shí)現(xiàn)方式，保證進(jìn)程唯一就好，使用 Node.js  系統(tǒng)模塊 crypto 提供的 randomBytes() 方法生成一個(gè)長(zhǎng)度為 5 的隨機(jī)字節(jié)。

+ 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 自增數(shù)

最后 3 Byte 為自增數(shù)，是關(guān)鍵的一部分，在 1 秒鐘內(nèi)、進(jìn)程標(biāo)識(shí)唯一的情況下，一個(gè) ObjectId() 能生成多少個(gè)不重復(fù)的 ID，由這 3 Byte 決定。

自增數(shù)不是簡(jiǎn)單的理解為 0、1、2...  這樣依次生成的，實(shí)現(xiàn)步驟為：

• Math.random() * 0xffffff? 首先生成一個(gè) 3 Byte 的隨機(jī)數(shù)做為起始值（這樣也加大了產(chǎn)生重復(fù)的機(jī)率），聲明在類的靜態(tài)屬性上（相當(dāng)于 UniqueId.index = Math.random() * 0xffffff，0xffffff?是一個(gè)十六進(jìn)制數(shù)，等價(jià)于十進(jìn)制的 16777215。
• 每次調(diào)用 getInc()? 初始的隨機(jī)數(shù)都會(huì) +1，做為當(dāng)前的隨機(jī)自增數(shù) inc，并做了取余操作，可以放心這個(gè)自增數(shù)永遠(yuǎn)都不會(huì)大于 16777215。
• buffer 中的每個(gè)字節(jié)用 16 進(jìn)制表示，一個(gè)字節(jié)等于 8 位，最大能表示的數(shù)用二進(jìn)制表示是11111111，轉(zhuǎn)為 16 進(jìn)制是 0xff，轉(zhuǎn)為十進(jìn)制是 255?，F(xiàn)在我們知道了 buffer 中的一個(gè)字節(jié)所表達(dá)的 10 進(jìn)制是不能大于 255 的，想實(shí)現(xiàn)一個(gè)字節(jié)存放的數(shù)不能大于 255 一個(gè)實(shí)現(xiàn)是做二進(jìn)制與運(yùn)算，本文用的也是這種方式，舉個(gè)與運(yùn)算的例子：

16777215 二進(jìn)制表示：11111111 11111111 11111111
255(0xff)二進(jìn)制表示： 00000000 00000000 11111111
與運(yùn)算結(jié)果：      00000000 00000000 11111111
# 與運(yùn)算是都為 1 則為 1，這里的結(jié)果最大是不會(huì)超過 255 的 

在我們的實(shí)現(xiàn)中將當(dāng)前隨機(jī)自增數(shù) inc 與 0xff 做與運(yùn)算， 等同于將 inc 按照二進(jìn)制方式把最右邊 8 位賦值給了 buffer 的最后一個(gè)字節(jié)（buffer[11] = inc & 0xff），同理將 inc 向右偏移 8 位與 0xff 做與運(yùn)算賦值給 buffer[10]，inc 向右偏移 16 位與 0xff 做與運(yùn)算賦值給 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;
  }
}

以下為最終的生成結(jié)果，可以看到每個(gè)字節(jié)都被 1 個(gè) 16 進(jìn)制數(shù)所填充。

(new UniqueId()).id -> 

總結(jié)

本文從理論到實(shí)踐，實(shí)現(xiàn)了一個(gè)自定義的 UniqueId()，這是一個(gè)最簡(jiǎn)化的 MongoDB ObjectId() 實(shí)現(xiàn)，代碼量也不多，感興趣的可以自己實(shí)現(xiàn)一遍，加深理解。

文章開頭提到了一個(gè)問題 “MongoDB ObjectId() 生成的 id 是唯一的嗎？” 答案即是 Yes 也是 No，在 1 秒鐘內(nèi)且進(jìn)程唯一標(biāo)識(shí)不重復(fù)的情況下，根據(jù)后 3 Byte 自增數(shù)可以得到生成的最大不重復(fù) id 為 2^24 - 1 = 16777215 個(gè)唯一 ID。

最后，留一個(gè)問題，為什么 MongoDB ObjectId() 可以不用 new 就能生成一個(gè) ID 呢？并且顯示的結(jié)果和上面自定義的 UniqueId() 也不一樣，關(guān)于 MongoDB ObjectId() 還有很多玩法，下一篇介紹。

console.log(ObjectId());     // 原生 ObjectId 輸出結(jié)果：new ObjectId("633304ee48d18c808c6bb23a")
console.log(new UniqueId()); // 自定義 UniqueId 輸出結(jié)果：UniqueId { [Symbol(id)]:  

網(wǎng)站標(biāo)題：MongoDB系列-ObjectId()是如何實(shí)現(xiàn)的“千萬級(jí)”分布式唯一ID？
URL地址：http://uogjgqi.cn/article/djoshjg.html