技術文章 » 分散式ID生成方案總結整理

分散式ID生成方案總結整理

2022-10-30 06:02:59

目錄

1、為什麼需要分散式ID？

對於單體系統來說，主鍵ID可能會常用主鍵自動的方式進行設定，這種ID生成方法在單體專案是可行的，但是對於分散式系統，分庫分表之後，就不適應了，比如訂單表資料量太大了，分成了多個庫，如果還採用資料庫主鍵自增的方式，就會出現在不同庫id一致的情況，雖然是不符合業務的

2、業務系統對分散式ID有什麼要求？

  • 全域性唯一性：ID是作為唯一的標識，不能出現重複
  • 趨勢遞增：網際網路比較喜歡MySQL資料庫，而MySQL資料庫預設使用InnoDB儲存引擎，其使用的是聚集索引，使用有序的主鍵ID有利於保證寫入的效率
  • 單調遞增：保證下一個ID大於上一個ID，這種情況可以保證事務版本號，排序等特殊需求實現
  • 資訊保安：前面說了ID要遞增，但是最好不要連續，如果ID是連續的，容易被惡意爬取資料，指定一系列連續的，所以ID遞增但是不規則是最好的

3、分散式ID生成方案

  • UUID
  • 資料庫自增
  • 號段模式
  • Redis實現
  • 雪花演演算法（SnowFlake）
  • 百度Uidgenerator
  • 美團Leaf
  • 滴滴TinyID

3.1 UUID

UUID （Universally Unique Identifier），通用唯一識別碼的縮寫。UUID的標準型式包含32個16進位制數位，以連字號分為五段，形式為8-4-4-4-12的36個字元，範例： 863e254b-ae34-4371-87da-204b71d46a7b。UUID理論上的總數為1632=2128，約等於3.4 x 10^38。

  • 優點
    • 效能非常高，本地生成的，不依賴於網路
  • 缺點
    • 不易儲存，16 位元組128位元，36位元長度的字串
    • 資訊不安全，基於MAC地址生成UUID的演演算法可能會造成MAC地址洩露，暴露使用者的位置
    • uuid的無序性可能會引起資料位置頻繁變動，影響效能

3.2、資料庫自增

在分散式環境也可以使用mysql的自增實現分散式ID的生成，如果分庫分表了，當然不是簡單的設定好auto_increment_increment和 auto_increment_offset 即可，在分散式系統中我們可以多部署幾臺機器，每臺機器設定不同的初始值，且步長和機器數相等。比如有兩臺機器。設定步長step為2，Server1的初始值為1（1，3，5，7，9，11…）、Server2的初始值為2（2，4，6，8，10…）。這是Flickr團隊在2010年撰文介紹的一種主鍵生成策略（Ticket Servers: Distributed Unique Primary Keys on the Cheap ）

假設有N臺機器，step就要設定為N，如圖進行設定：

這種方案看起來是可行的，但是如果要擴容，步長step等要重新設定，假如只有一臺機器，步長就是1，比如1,2,3,4,5,6，這時候如果要進行擴容，就要重新設定，機器2可以挑一個偶數的數位，這個數位在擴容時間內，資料庫自增要達不到這個數的，然後步長就是2，機器1要重新設定step為2，然後還是以一個奇數開始進行自增。這個過程看起來不是很雜，但是，如果機器很多的話，那就要花很多時間去維護重新設定

這種實現的缺陷：

  • ID沒有了單調遞增的特性，只能趨勢遞增，有些業務場景可能不符合
  • 資料庫壓力還是比較大，每次獲取ID都需要讀取資料庫，只能通過多臺機器提高穩定性和效能

3.3、號段模式

這種模式也是現在生成分散式ID的一種方法，實現思路是會從資料庫獲取一個號段範圍，比如[1,1000]，生成1到1000的自增ID載入到記憶體中，建表結構如：

CREATE TABLE id_generator (
  id int(10) NOT NULL,
  max_id bigint(20) NOT NULL COMMENT '當前最大id',
  step int(20) NOT NULL COMMENT '號段的布長',
  biz_type	int(20) NOT NULL COMMENT '業務型別',
  version int(20) NOT NULL COMMENT '版本號',
  PRIMARY KEY (`id`)
)
  • biz_type ：不同業務型別
  • max_id ：當前最大的id
  • step ：代表號段的步長
  • version ：版本號，就像MVCC一樣，可以理解為樂觀鎖

等ID都用了，再去資料庫獲取，然後更改最大值

update id_generator set max_id = #{max_id+step}, version = version + 1 where version = # {version} and biz_type = XXX
  • 優點：有比較成熟的方案，像百度Uidgenerator，美團Leaf
  • 缺點：依賴於資料庫實現

3.4、 Redis實現

Redis分散式ID實現主要是通過提供像INCR 和 INCRBY 這樣的自增原子命令，由於Redis單執行緒的特點，可以保證ID的唯一性和有序性

這種實現方式，如果並行請求量上來後，就需要叢集，不過叢集後，又要和傳統資料庫一樣，設定分段和步長

優缺點：

  • 優點：Redis效能相對比較好，又可以保證唯一性和有序性
  • 缺點：需要依賴Redis來實現，系統需要引進Redis元件

3.4、 雪花演演算法（SnowFlake）

Snowflake，雪花演演算法是由Twitter開源的分散式ID生成演演算法，以劃分名稱空間的方式將
64-bit位分割成多個部分，每個部分代表不同的含義，64位元，在java中Long型別是64位元的，所以java程式中一般使用Long型別儲存

  • 第一部分：第一位佔用1bit，始終是0，是一個符號位，不使用

  • 第二部分：第2位開始的41位是時間戳。41-bit位可表示241個數，每個數代表毫秒，那麼雪花演演算法可用的時間年限是(241)/(1000606024365)=69 年的時間

  • 第三部分：10-bit位可表示機器數，即2^10 = 1024臺機器。通常不會部署這麼多臺機器

  • 第四部分：12-bit位是自增序列，可表示2^12 = 4096個數。覺得一毫秒個數不夠用也可以調大點

  • 優點：雪花演演算法生成的ID是趨勢遞增，不依賴資料庫等第三方系統，生成ID的效率非常高，穩定性好，可以根據自身業務特性分配bit位，比較靈活

  • 缺點：雪花演演算法強依賴機器時鐘，如果機器上時鐘回撥，會導致發號重複或者服務會處於不可用狀態。如果恰巧回退前生成過一些ID，而時間回退後，生成的ID就有可能重複。

3.5、 百度Uidgenerator

百度的UidGenerator是百度開源基於Java語言實現的唯一ID生成器，是在雪花演演算法 snowflake 的基礎上做了一些改進。
參照官網的解釋：

UidGenerator是Java實現的, 基於Snowflake演演算法的唯一ID生成器。UidGenerator以元件形式工作在應用專案中, 支援自定義workerId位數和初始化策略, 從而適用於docker等虛擬化環境下範例自動重啟、漂移等場景。 在實現上, UidGenerator通過借用未來時間來解決sequence天然存在的並行限制; 採用RingBuffer來快取已生成的UID, 並行化UID的生產和消費, 同時對CacheLine補齊，避免了由RingBuffer帶來的硬體級「偽共用」問題. 最終單機QPS可達600萬。

Snowflake演演算法描述：指定機器 & 同一時刻 & 某一併行序列，是唯一的。據此可生成一個64 bits的唯一ID（long）。預設採用上圖位元組分配方式：

  • sign(1bit)：固定1bit符號標識，即生成的UID為正數。
  • delta seconds (28 bits)：當前時間，相對於時間基點"2016-05-20"的增量值，單位：秒，最多可支援約8.7年
  • worker id (22 bits)：機器id，最多可支援約420w次機器啟動。內建實現為在啟動時由資料庫分配，預設分配策略為用後即棄，後續可提供複用策略。
  • sequence (13 bits)：每秒下的並行序列，13 bits可支援每秒8192個並行。

詳細的，可以參考官網解釋，連結：https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

3.6、 美團Leaf

Leaf這個名字是來自德國哲學家、數學家萊布尼茨的一句話： >There are no two
identical leaves in the world > 「世界上沒有兩片相同的樹葉」

Leaf 提供兩種生成的ID的方式：號段模式(Leaf-segment)和snowflake模式(Leaf-snowflake）。你可以同時開啟兩種方式，也可以指定開啟某種方式，預設兩種方式為關閉狀態。

  • Leaf­segment資料庫方案
    其實就是前面介紹的號段模式的改進，可以參照美團技術部落格的介紹：

第一種Leaf-segment方案，在使用資料庫的方案上，做了如下改變： - 原方案每次獲取ID都得讀寫一次資料庫，造成資料庫壓力大。改為利用proxy server批次獲取，每次獲取一個segment(step決定大小)號段的值。用完之後再去資料庫獲取新的號段，可以大大的減輕資料庫的壓力。 - 各個業務不同的發號需求用biz_tag欄位來區分，每個biz-tag的ID獲取相互隔離，互不影響。如果以後有效能需求需要對資料庫擴容，不需要上述描述的複雜的擴容操作，只需要對biz_tag分庫分表就行

表結構設計：

>+-------------+--------------+------+-----+-------------------+-----------------------------+
| Field       | Type         | Null | Key | Default           | Extra                       |
+-------------+--------------+------+-----+-------------------+-----------------------------+
| biz_tag     | varchar(128) | NO   | PRI |                   |                             |
| max_id      | bigint(20)   | NO   |     | 1                 |                             |
| step        | int(11)      | NO   |     | NULL              |                             |
| desc        | varchar(256) | YES  |     | NULL              |                             |
| update_time | timestamp    | NO   |     | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+-------------+--------------+------+-----+-------------------+-----------------------------+
  • Leaf­snowflake方案
    Leafsnowflake是在雪花演演算法上改進來的，參照官網技術部落格介紹：

Leaf-snowflake方案完全沿用snowflake方案的bit位設計，即是「1+41+10+12」的方式組裝ID號。對於workerID的分配，當服務叢集數量較小的情況下，完全可以手動設定。Leaf服務規模較大，動手設定成本太高。所以使用Zookeeper持久順序節點的特性自動對snowflake節點設定wokerID。Leaf-snowflake是按照下面幾個步驟啟動的：

  • 啟動Leaf-snowflake服務，連線Zookeeper，在leaf_forever父節點下檢查自己是否已經註冊過（是否有該順序子節點）。
  • 如果有註冊過直接取回自己的workerID（zk順序節點生成的int型別ID號），啟動服務。
  • 如果沒有註冊過，就在該父節點下面建立一個持久順序節點，建立成功後取回順序號當做自己的workerID號，啟動服務。


這種方案解決了前面提到的雪花演演算法的缺陷，官網沒解釋，不過Leaf­snowflake對其進行改進，官網的流程圖

詳細介紹請看官網：https://tech.meituan.com/2017/04/21/mt-leaf.html

3.7、 滴滴TinyID

Tinyid是用Java開發的一款分散式id生成系統，基於資料庫號段演演算法實現。Tinyid擴充套件了leaf-segment演演算法，支援了多資料庫和tinyid-client

Tinyid也是基於號段演演算法實現，系統實現圖如下：

  • 優點：方便整合，有成熟的方案和解決實現
  • 缺點：依賴 DB的穩定性，需要採用叢集主從備份的方式提高 DB的可用性
    滴滴TinyID wiki：https://github.com/didi/tinyid/wiki

csdn連結