分佈式 ID 生成方案

不管我們是不是有身份的人，我們一定是有身份證的人，身份證上面的號碼就是我們的 ID，理論上這個 ID 是全國唯一的，而且通過這個號碼，我們還可以得到一些個人信息，比如前兩位可以確定我們第一次申請身份證的時候所在的省份、接下來的四位可以確定我們所在的區縣，然後還可以知道我們出生的年月以及性別。

在我們的計算機應用中，也處處存在的 ID，比如訂單編號、商品 ID、微博 ID、微信消息 ID、書的 ISDN 號、商品條碼等等。通過 ID，可以迅速定位到對象實體、爲對象之間建立關聯、跟蹤對象在不同服務之間的流轉等等。

有的 ID 是無意義的唯一的標識，有的 ID 還能提供額外的信息，比如時間和機房信息等等。爲了確保唯一性，有的 ID 使用很長的字節數，比如 256 個字節，有的通過遞增的 long 類型，只需要 8 個字節來表示。考慮到存儲、信息包含量、性能、安全等因素，一個好的 ID 的設計至關重要。

介紹 ID 生成和分佈式的方案的文章已經非常非常多了，比如文末中的參考資料中的文章，所以我在本文中簡潔的彙總各個方案的優缺點，然後介紹一個分佈式的 ID 生成器項目 rpcxio/did[1]，它可以實現單節點百萬級的節點生成。

ID 生成方案

UUID/GUID

通用唯一識別碼（Universally Unique Identifier，縮寫：UUID）是用於計算機體系中以識別信息數目的一個 128 位標識符，也就是可以通過 16 個字節來表示。

UUID 可以根據標準方法生成，不依賴中央機構的註冊和分配，UUID 具有唯一性，這與其他大多數編號方案不同。重複 UUID 碼概率接近零，可以忽略不計。

GUID 有時專指微軟對 UUID 標準的實現（Globally Unique Identifier，縮寫：GUID），通常表示成 32 個 16 進制數字（0－9，A－F）組成的字符串，如：{21EC2020-3AEA-1069-A2DD-08002B30309D}，實質上還是是一個 128 位長的二進制整數，在 Windows 生態圈中常用。

UUID 由開放軟件基金會（OSF）標準化，作爲分佈式計算環境（DCE）的一部分。

UUID 的標準型式包含 32 個 16 進位數字，以連字號分爲五段，形式爲 8-4-4-4-12 的 32 個字元。範例：550e8400-e29b-41d4-a716-446655440000。

在其規範的文本表示中，UUID 的 16 個 8 位字節表示爲 32 個十六進制（基數 16）數字，顯示在由連字符分隔 '-' 的五個組中，"8-4-4-4-12" 總共 36 個字符（32 個字母數字字符和 4 個連字符）。例如：

1123e4567-e89b-12d3-a456-426655440000
2xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx
3

四位數字 M 表示 UUID 版本，數字 N 的一至三個最高有效位表示 UUID 變體。在例子中，M 是 1 而且 N 是 a（10xx），這意味着此 UUID 是 "變體 1"、"版本 1" UUID；即基於時間的 DCE/RFC 4122 UUID。

對於 "變體（variants）1" 和 "變體 2"，標準中定義了五個 "版本（versions）"，並且在特定用例中每個版本可能比其他版本更合適。

版本由 M 字符串中指示：

"版本 1" UUID 是根據時間和節點 ID（通常是 MAC 地址）生成；
"版本 2" UUID 是根據標識符（通常是組或用戶 ID）、時間和節點 ID 生成；
"版本 3" 和 "版本 5" 確定性 UUID 通過散列（hashing）命名空間（namespace）標識符和名稱生成；
"版本 4" UUID 使用隨機性或僞隨機性生成。

更詳細的信息可以參考 wikipedia[2] 和 RFC[3] 文檔。

優點：

容易實現，產生快
ID 唯一（幾乎不會產生重複 ID）
無需中心化的服務器
不會泄漏商業機密

缺點：

可讀性差
佔用空間太多（16 個字節）
影響數據庫的性能，比如 UUID or GUID as Primary Keys? Be Careful![4]

遞增的整數

可以通過關係型數據庫的自增主鍵產生唯一的 ID，現在流行的商業數據庫都支持自增主鍵的特性，比如 MySQL 等。

一些 NoSQL 數據庫也提供類似特性，比如 Redis。

優點：

容易產生
可讀性好，容易記住
存儲很小，比如 4 個字節

缺點：

需要中心化的服務器，並且需要處理單點的問題，而且單點有性能瓶頸的問題。
如果 ID 暴露給公共訪問，可能會泄漏商業機密。比如最近渾水報告通過統計銷售小票推斷出某商業模式的每日單量。
需要訪問一次數據庫獲取 ID。

隨機數

遞增的整數可以用在內部的服務中，如果用在外部，可能會泄漏信息，所以如果能產生隨機數就可以解決這個問題。

當然直接生成隨機數可能比較困難，你可以在遞增的整數上產生僞隨機的整數，比如使用 skip32, 它還可以直接進行反解碼，在內部反解出原來的遞增的 ID，所以在一些場景的也有廣泛的應用，比如在 PostgrepSQL 中可以實現 skip32 function。

另外一個比較常用的加密遞增 ID 方法是 hashid，它可以轉換數字比如 347 爲字符串 yr8，並且還可以反解出來，提供了很多語言的實現，比如 go-hashids、hashids-java、hashids.c 等。

對於 64 bit 的整數，你可以使用 Block ciphers 實現加密。也有把 64 bit 整數分成兩部分，分別應用 skip32 進行加密的。

優點：

可讀性高
佔用存儲小，4 個字節就可以了
隨機，不會泄漏信息

缺點：

同樣需要中心化的服務，有單點問題和性能問題
需要兩步，先產生遞增的 ID，再進行隨機加密

隨機字符串

另外一個產生隨機 ID 方法是直接產生一個小的隨機的字符串，比如短網址服務中的 ID。產生隨機字符串的方法很多，比圖 tinyurl 和 bit.ly 使用的基於 62 字符的隨機字符串，基於 hash（MD5）+base62 等，應用在 Bitcoin 地址上的可讀性更好的 Base58。

優點：

短，5 個字符（字節）就可以表示 10 億個 ID。
可讀性高
隨機，不會泄漏信息

缺點：

ID 可能不唯一，需要檢查和處理

Twitter 的 snowflake 算法

Twitter 的 snowflake 分佈式 ID 的算法是目前廣泛使用的分佈式 ID 算法，儘管有很多變種，比如位數的不同，時間片大小不同、node bit 數放在最後等各種變種，但是主要思想還是來自於 snowflake 的思想。同時訪問方法也各種個樣，比如提供 memcached 協議訪問和 Redis 協議訪問等等。

Twitter 在 2010 年兒童節的時候在官方博客上介紹了 snowflake 算法，內部用來表示每一條 tweet，儘管這個項目已經不再維護了 snowflake-2010。

snowflake 算法採用 64bit 存儲 ID，最高位備用，暫時不使用。接下來的 41 bit 做時間戳，最小時間單位爲毫秒。再接下來的 10 bit 做機器 ID（worker id），然後最後 12 bit 在單位時間（毫秒）遞增。

41 bit 表示時間戳大約可以使用 69 年（2^41 -1），爲了儘可能的表示時間，時間戳可以從第一次部署的時候開始計算，比如 2020-02-02 00:00:00，這樣 69 年內可以無虞。

10 bit 區分機器，所以可以支持 1024 臺機器。你也可以把 10 bit 分成兩部分，一部分做數據中心的 ID，一部分做機器的 ID，比如 55 分的化，可以支持 32 個數據中心，每個數據中心最多可以支持 32 臺機器。

12 bit 自增值可以表示 4096 的 ID，也就是說每臺機器每以毫秒最多產生 4096 個 ID，這是它的最大性能。

正如前面所說，時間戳、機器 ID、自增 ID 所佔的位數可以根據你實際的情況做調整。

snowflake 還有一個很好的特性就是基本保持順序性，因爲它的前幾位是時間戳，可以對 ID 按照時間進行排序。另外在微服務中直接使用 ID 就可以計算 sla。

優點：

存儲少，8 個字節
可讀性高
性能好，可以中心化的產生 ID，也可以獨立節點生成

缺點：

時間回撥會重複產生 ID
ID 生成有規律性，信息容易泄漏

MongoDB ObjectID

MongoDB 的主鍵類型 ObjectID 也是一種 ID 生成方案，比如：5349b4ddd2781d08c09890f3，它看起來是一個包含 24 個字符的字符串，實際採用 12 個字節來存儲。

它使用 4 個字節代表時間戳，3 個字節代表機器 ID，2 個字節代表機器進程 ID，然後 3 個字節代表自增值。

相對於 snowflake，它採用了更多的存儲（多了四個字節），可以容納更多的信息。

優點：

可讀性高
性能好，可以中心化的產生 ID，也可以獨立節點生成

缺點：

佔用存儲較多
時間回撥會重複產生 ID
ID 生成有規律性，信息容易泄漏

分佈式 ID 生成器服務 did

前面是一些 ID 生成的背景知識的介紹，這裏介紹一個分佈式 ID 生成器（rpcxio/did），它基於 snowflake 的算法，但是提供了可以定製的算法，支持初始化設置 worker id 和自增值的 bit 數。

因爲它是一箇中心化的 ID 生成器服務，所以每次獲取 ID 都有額外的網絡開銷，所以最好一次申請一批數據，然後 client 在本地使用，用不了丟掉即可，所以 did 服務還提供批量獲取 ID 的方法。

安裝 did 的服務需要定時的和時間服務器進行同步，這個短時間的回撥不會影響 ID 的產生。重啓服務一般也沒有問題，因爲各個節點和時間服務器的誤差在毫秒左右，而重啓至少是秒級的操作，所以不會有重複的 ID 產生。唯一怕的時候手工將時間回撥一個很長的時間（幾個小時、幾天），然後這個時候再重啓服務，一般生產環境中也不會這麼去做。

因爲可以部署多個 did 服務做集羣，所以可以提供容錯機制，少量 did 節點宕機不會影響 ID 生成服務的訪問。

因爲 snowflake 算法性能優異，所以 ID 生成服務部署的節點不需要很多，每個機房只需要幾臺機器就可以了，所以你可以壓縮 worker id 佔用的 bit 數，擴大自增值佔用的 bit 數。

測試中，單個節點可以提供 12 萬 ID / 秒的產生速度，而如果採用批量獲取 100ID 的話，可以取得接近三百萬 ID / 秒的性能。

 11、256個client併發，每次只獲取1個ID, ID的產生速度是 12萬個ID/秒。
 2
 3./bclient -addr 192.168.15.225:8972 -n 100000
 4total IDs: 25600000, duration: 3m31.581592489s, id/s: 120993
 5
 62、如果採用批量獲取，儘量減少網絡消耗，256個client併發，每次只獲取100個ID, ID的產生速度是 297萬個ID/秒。
 7
 8./bclient -addr 192.168.15.225:8972 -n 1000000 -b 100
 9total IDs: 256000000, duration: 1m26.178942509s, id/s: 2970563
10

相關鏈接：

https://github.com/rpcxio/did
https://en.wikipedia.org/wiki/Universally_unique_identifier
https://tools.ietf.org/html/rfc4122
https://tomharrisonjr.com/uuid-or-guid-as-primary-keys-be-careful-7b2aa3dcb439

原文鏈接：https://colobu.com/2020/02/21/ID-generator/

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/jnQ7LWRzLCUPaM0EReWC8g

猜你喜歡