生成全局唯一 ID 的 3 個思路

837427098 8年前發布 | 45K 次閱讀 數據庫 分布式系統 MongoDB 分布式/云計算/大數據

標識（ID / Identifier）是無處不在的，生成標識的主體是人，那么它就是一個命名過程，如果是計算機，那么它就是一個生成過程。如何保證分布式系統下，并行生成標識的唯一與標識的命名空間有著密不可分的關系。在世界里，「潛意識下的命名空間里，相對的唯一標識」是普遍存在的，例如：

  1. 每個人出生的時候，就獲得了一個「相對的唯一標識」——姓名。

  2. 城市的道路，都基本上采用了唯一的命名（當然這也需要一個 過程 ）。

顯然，對于每個標識，都需要有一個命名空間（namespace），來保證其相對唯一性。

可以說，在人的意識里，對于的實體的描述是基于名字進行的，人們并不希望同名的出現太多，這會在溝通過程中的產生理解困難。

對于人來說，在家庭里會有小名，在社會中會有正式名字，在社交過程中還會產生綽號。

在中國，對于企業來說，除了企業有名稱之外，還有組織機構代碼證、有稅務登記證、有工商營業執照，并分別對應三個編號。（當然，目前五證合一也在進行中）。

回到計算機領域，圍繞主機在網絡上的地址，在不同的命名空間中，都會存在一個「相對的唯一標識」用來描述一個實體：

  1. 每個以太網網卡，都有一個48-bit 的MAC地址

  2. 每個MAC地址，可能有一個或者多個IP地址

  3. 每個網卡，都可能有一個或者多個IP地址

  4. 每個IP地址，都可能有多個域名

  5. 當然，每個主機，都會有一個主機名

接續上面的例子，事實上，MAC地址是由 IEEE Standards Association Registration Authority 完成地址段的分配。

對于目前的 1530 個頂級根域（gTLD），以及 IPv4 / IPv6 地址，都由IANA對其進行管理。

上面我通過類比的方式簡單介紹了標識，總結來說它是無處不在的。我們在理解技術里的ID的同時，一定要聯系生活中的場景，對比著琢磨和分析。

  • 標識是從一個典型的場景，對客觀事物進行統一編碼的過程。

  • 采用 半集中與半自主相結合 的方法，是一種實現「分而治之」十分普遍和有效的設計模式。

  • 標識的唯一性是根據命名空間緊密相關的。

標識的使用

在不同命名空間中實現標識的轉換

在中國，對于人名，通常是由公安局出入境管理局完成中文至英文的翻譯，同時，他們會把翻譯結果寫到數據庫中，印到護照上。 這中間的翻譯規則，通常是根據中文與漢語拼音、漢語拼音與英文字母的兩次轉換關系完成的。

對于計算機網絡，則會有 NAT完成IP地址間的轉換，RAP/RARP完成IP地址與MAC地址的雙向轉換，DNS完成域名至IP地址的轉換。

可是，為什么需要那么多不同命名空間的標識標識一個實體？可能最直觀的回答通常是這樣：

  • 域名為了方便人的記憶與使用

  • IP地址是為了更廣范圍的計算機互聯

  • MAC則是為了在物理上保證唯一

  • OSI開放系統互聯7層模型決定的

人們會在不同的領域（也是命名空間）中定義自己的命名規范，這可以認為是領域主權的體現，同時伴生的會是一套與相關領域標識的轉換協議。

結構化與別名效應

結構化是把數據的元信息以位置的方式固化是數據中。也就是說，代表某個意義的信息，一定會出現在一個約定好的位置上。

由于標識是被人經常使用的，那么在使用過程中會對大腦形成一定的訓練。

人在看到了010-XXXXXXXX，021-XXXXXXXX號碼之后，自然而言會產生條件反射，認為兩者分別代表了北京和上海；同樣的人在看到了139和186之后，分別產生了中國移動以及中國聯通的運營商聯想。

對于使用者，這種場景，數字類似是一個名稱別名。對于程序員，這十分接近「數據字典」的設計模式。

標識轉換過程的兩面性

別名和正名，同樣是來自于兩個不同命名空間的標識，之間自然而然的會進行轉換。

當然，人們也不會忘記去Hack這些轉換協議的設計。

一些是有益的，是實現了更為便利的應用場景。例如：將不同的域名指向相同的IP地址（使用A或者CNAME記錄），并結合相關軟硬件實現「虛擬主機」，達到資源復用的目的。

一些卻是有害的，例如，詐騙電話也經常采用改號的方法，讓接聽者誤以為那是來自某個官方的外呼電話。

同樣的，在計算機領域，一樣有DNS劫持、DNS污染。

有矛就有盾，進行安全性擴展的 DNSSEC 就是為了對DNS結果，驗證不存在性和校驗數據完整性驗證，不過依然沒有實現全面部署。

小結

  • 在關注如何生成標識的同時，還需要關注標識的易用性和直觀性

    不同命名空間的標識，在互通時需要進行轉換

  • 轉換的過程，可能是一個簡單的規則，也可能是一個獨立第三方服務

  • 標識的唯一性是基本訴求，同時嵌入其他維度的信息是減少實時關聯查詢的有效手段

思路一：基于數據庫生成

標識的生成方法有很多，有集中式的，分布式的；有后端的，前端的，當然還有人工的。 并沒有一種通用的生成方法來適應各種應用場景。

人工生成的確是一種方式，比如電子郵箱，微信ID，各種論壇的賬號。在人想出標識的那一刻，是無法判斷是否是唯一的，對這種生成方式的結果，顯然在錄入時都需要進行唯一性校驗。所以，下面描述的幾種生成方式，是在生成的那一刻就在一個命名空間內唯一，而不再需要進行唯一性校驗。

而基于數據庫生成，一般包含以下幾種：

  • MySQL(5.6) AUTO_INCREMENT 特性

  • Postgres(REL 9.6 Stable) SEQUENCE 特性

  • Oracle 數據庫的 SEQUENCE 特性，有知道這一特性如何實現的，可以在 知乎 做一下解答。

  • Flickr Ticket Servers ，同時支持Sharding (文章發表于2010年2月8日，算法上線于2006年1月13日)。

一般地，這種類型的生成方案，都可以設置其實初始值，以及增量步長。

思路二：基于分布式集群協調器生成

在不使用數據庫的情況下，通過一個后臺服務對外提供高可用的、固定步長標識生成，則需要分布式的集群協調器進行。

一般的，主流協調器有兩類：

  • 以強一致性為目標的：ZooKeeper為代表

  • 以最終一致性為目標的：Consul為代表

ZooKeeper的強一致性，是由Paxos協議保證的；Consul的最終一致性，是由Gossip協議保證的。

在步長累計型生成算法中，最核心的就是保持一個累計值在整個集群中的「強一致性」。同時，這也會為唯一性標識的生成帶來新的形成瓶頸。

思路三：劃分命名空間并行生成

似乎對于分布式的ID生成，以推ter Snowflake為代表的， Flake 系列算法，經常可以被搜索引擎找到，但似乎MongoDB的ObjectId算法，更早地采用了這種思路。MongoDB 1.0 是在2009年8月27日 發布 的，并且0.9.10(2009年8月24日發布)和1.0兩個版本沒有差異。

在StackOverflow上，最早的一個關于ObjectId的問題（ http://stackoverflow.com/questions/2138687/whats-mongodb-hashs-size/2146071 ），時間是2010年1月27日。不知道推ter的同學，是不是受此啟發呢？

MongoDB ObjectId

12-byte MongoDB ObjectId 的結構是：

  • a 4-byte value representing the seconds since the Unix epoch,

  • a 3-byte machine identifier,

  • a 2-byte process id, and

  • a 3-byte counter, starting with a random value.

可以看出，這個方案所支持的最小劃分粒度是「秒 * 進程實例」，單進程實例的每秒容量是 3-byte (24-bit)，也就是接近16777216個ID。

有興趣的，還可以進一步 看代碼（MonogoDB 3.3.x Java Driver） 研究：Timestamp, Machine Identifier、Process Identifier、計數器的初始值分別是如何獲得的：

1. Timestamp

2. Machine Identifier

3. Process ID

4. COUNTER

此處需要注意的是MongoDB的 NEXT_COUNTER 其初始值是一個隨機數，這是有利于分庫分表的。因為在小并發的條件下，非隨機數的初始值，容易產生 偏庫偏表， 不均勻的現象。

推ter Snowflake

推ter在2010年6月1日（在Flickr那篇文章發布不到4個月之后），Ryan King 在推ter的Blog 撰文 寫道：

  • Ticket Servers方案缺乏順序的保證

  • 考慮過采用UUID，不過128-bit太長了

  • 也考慮過采用ZooKeeper所提供的 *Unique Naming* Seuence Nodes 所提供的 Unique Naming 特性，但是性能不能滿足。(個人認為，Sequence Nodes的設計目標是解決分布式鎖的問題，但不解決性能要求極高的ID生成問題，直接應用是一種Hack行為)

在這種情況下，推ter給出了 64-bit 長的 Snowflake ，它的結構是：

  • 1-bit reserved

  • 41-bit timestamp

  • 10-bit machine id

  • 12-bit sequence

在過了不到4年，2014年的5月31日，推ter 更新了 Snowflake 的 README，其中陳述了兩個容易被忽視的事實:

  • "We have retired the initial release of Snowflake ..."

  • "... heavily relies on existing infrastructure at 推ter to run. "

可以看出，這個方案所支持的最小劃分粒度是「毫秒 * 線程」，單線程（Snowflake 里對應的概念是 Worker）的每秒容量是12-bit，也就是接近4096。

翻一下Snowflake的 歸檔代碼 (Scala)，可以看到：

1. 關于初始化Sequence的處理

可以看到此處Snowflake對于 sequence 的賦值為0。

2. 關于每秒超過4096個ID生成請求的處理

noeqd

2011年11月23日，用Go語言實現的，基于Snowflake的 neoqd 出現了。

它的特點是，除了使用Go語言進行了實現，更是把ID生成做成了一個網絡服務。支持客戶端向ID生成服務申請ID。它還支持：

  • 簡單預共享Token的客戶端身份證認證（只是加強了那么一點點的安全性，可以忽略）

  • 支持批量獲取ID，最多256個（因為使用一個byte表示申請個數）

同時，作者還建議使用 Doozerd 一個用Go語言寫的 -- a highly-available, completely consistent store for small amounts of extremely important data. 進行Machine ID的分配。

(關于 ZooKeeper / Etcd / Consul / Doozerd 的比較，也是可以期待下)

Boundary Flake

2012年1月， Boundary Flake 同樣的，用Erlang語言把Snowflake，變成了一個網絡服務，提供128-bit長的ID生成服務。

不過，根據其RoadMap的描述，這個項目并沒100%完成。例如，批量的ID生成，HTTP 接口，客戶端Library都列在里面待實現。

CruftFlake

2012年7月， CruftFlake 更顯然的，是想以一個PHP變種身份出現。

它在結構上與Snowflake基本一致，存在兩個區別：

  • 在timestamp上的取值略有區別

  • 可以自行決定是否采用ZooKeeper作為協調器

基于LableOrg/java-uniqueid

2014年7月18日，LableOrg 寫了一個通過ZooKeeper進行協調的，128-bit長的算法 java-uniqueid。其 結構組成 依然十分相似：

  • Timestamp

  • Sequence counter

  • Generator IDs

  • Cluster IDs

前臺瀏覽器生成

這里的前臺，主要是指以「瀏覽器」為代表的客戶端。

2015年2月16日，Sudhanshu Yadav (看面相像印度人)，用Javascript寫了Flake的又一個變種實現 FlakeId 。其核心代碼是：

它的Machine Identifier則是作為構造函數的選項參數 options.mid 傳入。

沒思路，全自主隨機生成？

選擇UUID？

可以說，成熟的、全自主生成方案，可能只有 128-bit UUID 一種，具體的說，是UUID Version 4。另外，微軟對它實現，稱之為 GUID 。

一般的，使用的最多的是UUID Version 4，很大程度上是因為其依賴的其他服務最少。

這里，通過python (2.5+) 對UUID的實現，體驗一下UUID的生成效果：

另外，我們看一下網卡的MAC地址：

(因為UUID Version 1會泄露網卡的MAC地址，所以我對MAC地址做了下小手術)

可以看到UUID Version 1 最后一組數值 985aeb899615 與網卡的 MAC地址是一樣一樣的 98:5a:eb:89:96:15。

個人一直認為，采用UUID Version 4是一種偷懶的，沒有針對具體應用場景，缺乏必要設計的做法。

一方面，它是依據概率確保無碰撞的，計算的過程與概率上的「生日問題」是一樣的，不再展開。

另一方面，從使用的角度，UUID還有以下缺點：

  • 太長，即便是轉換成36個字符，不利于輸入

  • 過于隨機，沒有規律，在開發調試、線上故障定位，都容易看花眼。

  • 如果作為數據庫主鍵，對索引不利。

基于Hash算法？

眾多的Hash算法，例如「MD5 / SHA-1 / SHA-2 / SHA-3」，都看可以對內容進行摘要計算，形成一個定長的Hash值。

這些Hash算法，都會存在一個Hash沖突的問題，以及碰撞攻擊的問題。

以UUID類似，其文本化之后的隨機特征，不太適合應用在ID生成方面。

標識生成總結

  • 人工生成的標識，在相同的命名空間里，需要后續唯一性驗證才能保證唯一

  • 由計算機生成，在低并發的場景下，適合通過一個服務集中生成，并保障此服務的高可用性

  • 由計算機生成，在高并發的場景下，適合通過一個保障命名空間獨立的命名規范下，由多個服務并行生成。

  • 采用步長和增長相結合的生成算法，本質上都是對某個狀態進行累積的結果。

  • 對于取模進行分庫分表的場景，初始化值隨機有利于均勻分布。

  • （MongoDB 的 ObjectId 更是Flake系列算法的鼻祖，并在初始值上進行了隨機化處理）

設計一個「合適」的標識

1. 區分實體和關系

實體是點，而關系是線。

一般而言，面向實體的標識生成速度，要小于面向關系的生成速度。

具體的例子，以電商為例：買家、賣家、商品這些實體的錄入速度，要遠比訂單生成小的多。也因此，主數據要比交易數據穩定的多。

并且，關系還可能包含層次關系，進而體現為一個依賴樹。

面向實體的標識

面向實體的標識，更多的與概念相關（名稱）、與形態相關（型號），有很多的人為因素參與，隨機因素有限，命名的主體也來自于人。

對于實體制造，為任意一個產品進行標識，大致會分為六個方面：品牌、品類、品名，型號、批號、產品序列號。

對于前四者，更多的是人為的進行命名。例如，給定中文，找到對應英文，再進行縮寫。

對于批號，則會增加一些時間因素，以關聯到產品的生產時間。例如，采用20160925表示具體某一天，或者采用201640表示具體某一周。（一般來說，同一個批號的產品，所使用的原材料是也是同一批。）

對于產品序列號，最簡單的是采用自然數法進行編號。

這一類的標識，在分布式系統下，在系統并發量小，集群規模小的情況下，可以采用基于數據庫或者協調器的生成方案。

面向關系的標識

自然的，關系源于兩個或兩個以上的實體之間所進行的某一個活動，并且具有一定的時效性。

常見的關系的表現形式有：交易流水號，會話標識等等。

這一類的標識，在分布式系統下，在系統并發量大，應當采用基于服務的內置生成方案。唯一依賴的是在實例部署時、啟動前，為期分配唯一的Machine Identifier。這個Machine Identifier可以交由以強一致性保證的協調器完成。

當然，在系統并發量小的情況下，任然可以采用基于數據庫的生成方案，因為沒有協調器集群的參與，系統整體的復雜度更低，更利于維護。

2. 標識的容量

任何采用文字所表達的標識，最終在計算機里，都會根據一定的格式，被轉換為字節byte進行處理，這個過程稱之為「序列化」。 這種序列化方式，本質上是一種編碼方式。

變長編碼

一般來說，采用變長的編碼方式，主要的目的是為了應對不可預期大小的信息量。

常見的有 TLV(Type-Length-Value) 方式。 Google的 Protocol Buffers 非常有意思地采用了 Base 128 Varints 的編碼方式。

本質上，一個 URI 也是一個變長標識，它可以標識一個功能，也可以標識一個虛擬實體。

RESTful是對此類命名方式的一種實踐方式，也是對 URI和HTTP協議組合之后，「表征力」的一個深入挖掘。

定長編碼

在回顧一下前文所提到的IPv4地址，它似乎、可能、或許會在2019年 完全枯竭， 因為它只有32-bit。相比之下，MAC地址有48-bit，IPv6有128-bit。即便是它們都沒那么容易枯竭，但也不代表由于人為因素，導致無法有效使用。

再回想下，每個人的身份證、手機號碼，都是采用定長的形式進行編碼。

選擇定長有利于預先分配計算機資源，不管是內存、文件系統，還是數據庫。同時，對于人的心理來說，可預期性大大增強了。

標識的命名空間

命名空間有三個層面：

  • 異構切分：對于不同的場景和視角，以樹形進行層次劃分。

  • 同構切分：對于異構切分的結果，切分出不同的分片。

  • 時間切分：對于同一個分片，在不同時間點上的狀態。

一般地：

  • 首先，采用并行無狀態的生成算法，一般都采用時間作為首要的命名空間，并且此命名空間的實效性小于生成者的重啟時間

  • 其次，采用生成器實例自身的標識作為次要命名空間，以保證各個生成器的時間即便是不同步也不會產生重復標識

同時，需要注意的是，這可能導致唯一標識產生，大段跳躍，原因有：

  • 單位時間的并發量遠小于子命名空間的容量

  • 生成器重啟

  • 標識的冗余

不管標識是在運行時的內存出現，還是記錄到數據庫中或者文件里，它都需要占用硬件資源。

還是拿身份證舉例，一方面，一個18個字符長度的身份證，那么需要18個字節進行存儲。18個字節意味著144-bit，比IPv6的128bit還長。

如果簡單的標識全世界每個人，以目前全地球超過70億人口的總量，那么33個bit就足夠了。

采用這種冗余設計的原因，一方面是「半集中，半自主」和現實的行政、地域結構對齊，另一方面是實現關聯信息的集成。

小結

  • 標識編碼后的長度，則決定了一個標識方案的整體容量。

  • 在一個統一的命名空間內，有多個標識生成者并行生成時，需要劃分獨立的子命名空間，以保證生成的標識在整個命名空間內唯一。

  • 單個命名空間的標識，承載的信息量有限，在標識的使用過程中，需要擴展與包含一些其他視角的信息以進行冗余。

3. 標識的文本兼容

和人工取名字不一樣，自動生成ID的主體，是計算機本身，但使用這個ID的主體，有兩個：人和計算機。

對于計算機，最擅長處理的是結構化數組、條形碼或者二維碼；而對人，最擅長使用的是文本、圖形或者視頻。

一般而言，在大量的RESTful設計的應用，其URI中會包含大量的ID，用來標識用戶、商品、訂單等等，它們經常會出現在URI中。

以ASCII編碼為基礎的各種文本化編碼算法，從Base16開始，正常的有Base32，Base64，Base58，Base85等等。

其中，Base16是最為「字節友好」的，因為不需要進行任何Padding操作，就可以以把 4-bit/half-byte 轉換為 [0-9a-f] 這十六個字符，因此Base16還有別名：Hex。另外對于鍵盤輸入，這16個英文字母，又是相對純數字之外，最方便的。

而Base32, Base64等等，都需要Padding。因為Base32是每 5-bit 進行分組編碼，Base64則是 6-bit ，都無法直接對齊一個 byte(8-bit)。

另外，Base16還對 URI 友好，不需要進行任何的 URLEncode/Decode操作。

以64-bit長的ID為例，它既可以轉化為 long，也可以Base16成為16個字符的``HexString``，同時它大小寫不敏感。

相比之下，如果采用Base64的文本化方案，其長度雖然少了5個字符，為11個，但其大小寫敏感，不利于人機交互的輸入，還會包含URI不友好，還會被轉義為「 %3D」的符號「=」。

一個精巧的標識文本化算法，并不應該簡單的把一個二進制值轉為HexString。在日志里，應該有相應的解碼算法，解析出符合人類閱讀的字符，比如：精確到秒、且帶格式時間，生成改標識的主體，等等。

4. 標識的安全性

標識的信息泄露

采用連續，或者固定步長的標識，容易從一個標識猜測其他標識的存在性。

常見的例子有：

  • 通過局域網掃描工具，掃描某個子網的活動的IP地址

  • 通過端口掃描工具，掃描一個目標主機開放的端口，以初步確定主機操作系統類型

另外，在物聯網領域，如果采用的EPC編碼，那么很容易通過連續編碼，估計某個產品的具體產量。

標識的自校驗能力

還是使用身份證號這個例子，根據國家標準（GB11643-1999），身份證號的前17位為本體碼，最后1位為校驗碼。也就是說，它是通過前17位進行數學公式計算之后獲得，主要目的是用于檢驗錄入過程是否產生差錯。

這樣設計的好處是，每當輸入完18位身份證號后，可以直接判斷一個身份證號，是否在邏輯上是「合規的」，對于系統而言不用查詢數據庫，可以減少IO操作。不過，這不代表這個身份證號是有效的，也有可能是一個無效，但符合校驗規則的身份證號。

由于標識的長度有限，能夠加入的冗余信息較少，一般的基于公鑰密碼體制的簽名機制，都難以在一個短標識中嵌入。

 

 

 

來自：http://mp.weixin.qq.com/s?__biz=MzA5Nzc4OTA1Mw==&mid=2659598286&idx=1&sn=3172172ccea316b0ed83429ae718b54d&chksm=8be9eadcbc9e63caa10d708274b4fa34ceffa416ef4527e10e6b7a1a2d2f32cf8592d65bf728&scene=0

 

 本文由用戶 837427098 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
 轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
 本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！