分布式ID生成器（CosId）的設計與實作

分布式ID生成器（​​CosId​​）設計與實作

​​CosId​​ 簡介

​​CosId​​ 旨在提供通用、靈活、高性能的分布式 ID 生成器。 目前提供了倆類 ID 生成器：

• ​

  ​SnowflakeId​

  ​ : 單機 TPS 性能：409W/s ​​JMH 基準測試​​ , 主要解決 時鐘回撥問題 、機器号配置設定問題 并且提供更加友好、靈活的使用體驗。

• ​SegmentId​

  ​: 每次擷取一段 (​

  ​Step​

  ​) ID，來降低号段分發器的網絡IO請求頻次提升性能。

• ​IdSegmentDistributor​

  ​: 号段分發器（号段存儲器）

• ​RedisIdSegmentDistributor​

  ​: 基于 Redis 的号段分發器。

• ​JdbcIdSegmentDistributor​

  ​: 基于 Jdbc 的号段分發器，支援各種關系型資料庫。

• ​SegmentChainId​

  ​(推薦):​

  ​SegmentChainId​

  ​ (lock-free) 是對 ​

  ​SegmentId​

  ​ 的增強。性能可達到近似 ​

  ​AtomicLong​

  ​ 的 TPS 性能:12743W+/s​JMH 基準測試​​ 。

• ​PrefetchWorker​

  ​ 維護安全距離(​

  ​safeDistance​

  ​), 并且支援基于饑餓狀态的動态​

  ​safeDistance​

  ​擴容/收縮。

背景（為什麼需要分布式ID）

在軟體系統演進過程中，随着業務規模的增長，我們需要進行叢集化部署來分攤計算、存儲壓力，應用服務我們可以很輕松做到無狀态、彈性伸縮。

但是僅僅增加服務副本數就夠了嗎？顯然不夠，因為性能瓶頸往往是在資料庫層面，那麼這個時候我們就需要考慮如何進行資料庫的擴容、伸縮、叢集化，通常使用分庫、分表的方式來處理。

那麼我如何分片(水準分片，當然還有垂直分片不過不是本文需要讨論的内容)呢，分片得前提是我們得先有一個ID，然後才能根據分片算法來分片。（比如比較簡單常用的ID取模分片算法，這個跟Hash算法的概念類似，我們得先有key才能進行Hash取得插入槽位。）

當然還有很多分布式場景需要分布式ID，這裡不再一一列舉。

分布式ID方案的核心名額

• 全局（相同業務）唯一性：唯一性保證是ID的必要條件，假設ID不唯一就會産生主鍵沖突，這點很容易可以了解。

• 通常所說的全局唯一性并不是指所有業務服務都要唯一，而是相同業務服務不同部署副本唯一。

  比如 Order 服務的多個部署副本在生成​

  ​t_order​

  ​這張表的​

  ​Id​

  ​時是要求全局唯一的。至于​

  ​t_order_item​

  ​生成的​

  ​ID​

  ​與​

  ​t_order​

  ​是否唯一，并不影響唯一性限制，也不會産生什麼副作用。

  不同業務子產品間也是同理。即唯一性主要解決的是ID沖突問題。

• 有序性：有序性保證是面向查詢的資料結構算法（除了Hash算法）所必須的，是二分查找法(分而治之)的前提。

• MySq-InnoDB B+樹是使用最為廣泛的，假設 Id 是無序的，B+ 樹 為了維護 ID 的有序性，就會頻繁的在索引的中間位置插入而挪動後面節點的位置，甚至導緻頻繁的頁分裂，這對于性能的影響是極大的。那麼如果我們能夠保證ID的有序性這種情況就完全不同了，隻需要進行追加寫操作。是以 ID 的有序性是非常重要的，也是ID設計不可避免的特性。

• 吞吐量/性能(ops/time)：即機關時間（每秒）能産生的ID數量。生成ID是非常高頻的操作，也是最為基本的。假設ID生成的性能緩慢，那麼不管怎麼進行系統優化也無法獲得更好的性能。

• 一般我們會首先生成ID，然後再執行寫入操作，假設ID生成緩慢，那麼整體性能上限就會受到限制，這一點應該不難了解。

• 穩定性(time/op)：穩定性名額一般可以采用每個操作的時間進行百分位采樣來分析，比如 ​​CosId​​ 百分位采樣 P9999=0.208 us/op，即 0% ~ 99.99% 的機關操作時間小于等于 0.208 us/op。

• ​​百分位數 WIKI​​ ：統計學術語，若将一組資料從小到大排序，并計算相應的累計百分點，則某百分點所對應資料的值，就稱為這百分點的百分位數，以Pk表示第k百分位數。百分位數是用來比較個體在群體中的相對地位量數。
• 為什麼不用平均每個操作的時間：馬老師的身價跟你的身價能平均麼？平均後的值有意義不？
• 可以使用最小每個操作的時間、最大每個操作的時間作為參考嗎？因為最小、最大值隻說明了零界點的情況，雖說可以作為穩定性的參考，但依然不夠全面。而且百分位數已經覆寫了這倆個名額。

• 自治性（依賴）：主要是指對外部環境有無依賴，比如号段模式會強依賴第三方存儲中間件來擷取​

  ​NexMaxId​

  ​。自治性還會對可用性造成影響。
• 可用性：分布式ID的可用性主要會受到自治性影響，比如SnowflakeId會受到時鐘回撥影響，導緻處于短暫時間的不可用狀态。而号段模式會受到第三方發号器（​

  ​NexMaxId​

  ​）的可用性影響。

• ​​可用性 WIKI​​：在一個給定的時間間隔内，對于一個功能個體來講，總的可用時間所占的比例。
• MTBF：平均故障間隔
• MDT：平均修複/恢複時間
• Availability=MTBF/(MTBF+MDT)
• 假設MTBF為1年，MDT為1小時，即​

  ​Availability=(365*24)/(365*24+1)=0.999885857778792≈99.99%​

  ​，也就是我們通常所說對可用性4個9。

• 适應性：是指在面對外部環境變化的自适應能力，這裡我們主要說的是面對流量突發時動态伸縮分布式ID的性能，

• SegmentChainId可以基于饑餓狀态進行安全距離的動态伸縮。
• SnowflakeId正常位配置設定方案性能恒定409.6W，雖然可以通過調整位配置設定方案來獲得不同的TPS性能，但是位配置設定方法的變更是破壞性的，一般根據業務場景确定位配置設定方案後不再變更。

• 存儲空間：還是用MySq-InnoDB B+樹來舉例，普通索引（二級索引）會存儲主鍵值，主鍵越大占用的記憶體緩存、磁盤空間也會越大。Page頁存儲的資料越少，磁盤IO通路的次數會增加。總之在滿足業務需求的情況下，盡可能小的存儲空間占用在絕大多數場景下都是好的設計原則。

不同分布式ID方案核心名額對比

分布式ID	全局唯一性	有序性	吞吐量	穩定性（1s=1000,000us）	自治性	可用性	适應性	存儲空間
UUID/GUID	是	完全無序	3078638(ops/s)	P9999=0.325(us/op)	完全自治	100%	否	128-bit
SnowflakeId		本地單調遞增，全局趨勢遞增(受全局時鐘影響)	4096000(ops/s)	P9999=0.244(us/op)	依賴時鐘	時鐘回撥會導緻短暫不可用		64-bit
SegmentId		本地單調遞增，全局趨勢遞增(受Step影響)	29506073(ops/s)	P9999=46.624(us/op)	依賴第三方号段分發器	受号段分發器可用性影響
SegmentChainId		本地單調遞增，全局趨勢遞增(受Step、安全距離影響)	127439148(ops/s)	P9999=0.208(us/op)		受号段分發器可用性影響，但因安全距離存在，預留ID段，是以高于SegmentId

有序性(要想分而治之·二分查找法，必須要維護我)

剛剛我們已經讨論了ID有序性的重要性，是以我們設計ID算法時應該盡可能地讓ID是單調遞增的，比如像表的自增主鍵那樣。但是很遺憾，因全局時鐘、性能等分布式系統問題，我們通常隻能選擇局部單調遞增、全局趨勢遞增的組合（就像我們在分布式系統中不得不的選擇最終一緻性那樣）以獲得多方面的權衡。下面我們來看一下什麼是單調遞增與趨勢遞增。

有序性之單調遞增

單調遞增：T表示全局絕對時點，假設有Tn+1>Tn（絕對時間總是往前進的，這裡不考慮相對論、時間機器等），那麼必然有F(Tn+1)>F(Tn)，資料庫自增主鍵就屬于這一類。

另外需要特别說明的是單調遞增跟連續性遞增（F(n+1)=F(n)+step）是不同的概念。

有序性之趨勢遞增

趨勢遞增：Tn>Tn-s，那麼大機率有F(Tn)>F(Tn-s)。雖然在一段時間間隔内有亂序，但是整體趨勢是遞增。從上圖上看，是有上升趨勢的（趨勢線）。

• 在SnowflakeId中n-s受到全局時鐘同步影響。
• 在号段模式(SegmentId)中n-s受到号段可用區間(​

  ​Step​

  ​)影響。

分布式ID配置設定方案

• ????不依賴任何第三方中間件
• ????性能高
• ????完全無序
• ????空間占用大，需要占用128位存儲空間。

UUID最大的缺陷是随機的、無序的，當用于主鍵時會導緻資料庫的主鍵索引效率低下（為了維護索引樹，頻繁的索引中間位置插入資料，而不是追加寫）。這也是UUID不适用于資料庫主鍵的最為重要的原因。

SnowflakeId使用​

​Long​

​（64-bit）位分區來生成ID的一種分布式ID算法。

通用的位配置設定方案為：​

​timestamp​

​(41-bit)+​

​machineId​

​(10-bit)+​

​sequence​

​(12-bit)=63-bit。

• 41-bit​

  ​timestamp​

  ​=(1L<<41)/(1000/3600/365)，約可以存儲69年的時間戳，即可以使用的絕對時間為​

  ​EPOCH​

  ​+69年，一般我們需要自定義​

  ​EPOCH​

  ​為産品開發時間，另外還可以通過壓縮其他區域的配置設定位數，來增加時間戳位數來延長可用時間。
• 10-bit​

  ​machineId​

  ​=(1L<<10)=1024，即相同業務可以部署1024個副本(在Kubernetes概念裡沒有主從副本之分，這裡直接沿用Kubernetes的定義)。一般情況下沒有必要使用這麼多位，是以會根據部署規模需要重新定義。
• 12-bit​

  ​sequence​

  ​=(1L<<12)*1000=4096000，即單機每秒可生成約409W的ID，全局同業務叢集可産生​

  ​4096000*1024=419430W=41.9億(TPS)​

  ​。

從 SnowflakeId 設計上可以看出:

• ????​

  ​timestamp​

  ​在高位，單執行個體SnowflakeId是會保證時鐘總是向前的（校驗本機時鐘回撥），是以是本機單調遞增的。受全局時鐘同步/時鐘回撥影響SnowflakeId是全局趨勢遞增的。
• ????SnowflakeId不對任何第三方中間件有強依賴關系，并且性能也非常高。
• ????位配置設定方案可以按照業務系統需要靈活配置，來達到最優使用效果。
• ????強依賴本機時鐘，潛在的時鐘回撥問題會導緻ID重複、處于短暫的不可用狀态。

• ​machineId​

  ​需要手動設定，實際部署時如果采用手動配置設定​

  ​machineId​

  ​，會非常低效。

SnowflakeId之機器号配置設定問題

在SnowflakeId中根據業務設計的位配置設定方案确定了基本上就不再有變更了，也很少需要維護。但是​

​machineId​

​總是需要配置的，而且叢集中是不能重複的，否則分區原則就會被破壞而導緻ID唯一性原則破壞，當叢集規模較大時​

​machineId​

​的維護工作是非常繁瑣，低效的。

有一點需要特别說明的，SnowflakeId的MachineId是邏輯上的概念，而不是實體概念。

想象一下假設MachineId是實體上的，那麼意味着一台機器擁有隻能擁有一個MachineId，那會産生什麼問題呢？

目前 ​​CosId​​ 提供了以下三種 ​

​MachineId​

​ 配置設定器。

• ManualMachineIdDistributor: 手動配置​

  ​machineId​

  ​，一般隻有在叢集規模非常小的時候才有可能使用，不推薦。
• StatefulSetMachineIdDistributor: 使用​

  ​Kubernetes​

  ​的​

  ​StatefulSet​

  ​提供的穩定的辨別ID（HOSTNAME=service-01）作為機器号。
• RedisMachineIdDistributor: 使用Redis作為機器号的分發存儲，同時還會存儲​

  ​MachineId​

  ​的上一次時間戳，用于啟動時時鐘回撥的檢查。

SnowflakeId之時鐘回撥問題

時鐘回撥的緻命問題是會導緻ID重複、沖突（這一點不難了解），ID重複顯然是不能被容忍的。

在SnowflakeId算法中，按照MachineId分區ID，我們不難了解的是不同MachineId是不可能産生相同ID的。是以我們解決的時鐘回撥問題是指目前MachineId的時鐘回撥問題，而不是所有叢集節點的時鐘回撥問題。

MachineId時鐘回撥問題大體可以分為倆種情況：

• 運作時時鐘回撥：即在運作時擷取的目前時間戳比上一次擷取的時間戳小。這個場景的時鐘回撥是很容易處理的，一般SnowflakeId代碼實作時都會存儲​

  ​lastTimestamp​

  ​用于運作時時鐘回撥的檢查，并抛出時鐘回撥異常。

• 時鐘回撥時直接抛出異常是不太好地實踐，因為下遊使用方幾乎沒有其他處理方案（噢，我還能怎麼辦呢，等吧），時鐘同步是唯一的選擇，當隻有一種選擇時就不要再讓使用者選擇了。

• ​ClockSyncSnowflakeId​

  ​是​

  ​SnowflakeId​

  ​的包裝器，當發生時鐘回撥時會使用​

  ​ClockBackwardsSynchronizer​

  ​主動等待時鐘同步來重新生成ID，提供更加友好的使用體驗。

• 啟動時時鐘回撥：即在啟動服務執行個體時擷取的目前時鐘比上次關閉服務時小。此時的​

  ​lastTimestamp​

  ​是無法存儲在程序記憶體中的。當擷取的外部存儲的機器狀态大于目前時鐘時鐘時，會使用​

  ​ClockBackwardsSynchronizer​

  ​主動同步時鐘。

• LocalMachineStateStorage：使用本地檔案存儲​

  ​MachineState​

  ​(機器号、最近一次時間戳)。因為使用的是本地檔案是以隻有當執行個體的部署環境是穩定的，​

  ​LocalMachineStateStorage​

  ​才适用。
• RedisMachineIdDistributor：将​

  ​MachineState​

  ​存儲在Redis分布式緩存中，這樣可以保證總是可以擷取到上次服務執行個體停機時機器狀态。

SnowflakeId之JavaScript數值溢出問題

​JavaScript​

​Number.MAX_SAFE_INTEGER​

​隻有53-bit，如果直接将63位的​

​SnowflakeId​

​傳回給前端，那麼會産生值溢出的情況（是以這裡我們應該知道後端傳給前端的​

​long​

​值溢出問題，遲早會出現，隻不過SnowflakeId出現得更快而已）。

很顯然溢出是不能被接受的，一般可以使用以下倆種處理方案：

• 将生成的63-bit​

  ​SnowflakeId​

  ​轉換為​

  ​String​

  ​類型。

• 直接将​

  ​long​

  ​轉換成​

  ​String​

• 使用​

  ​SnowflakeFriendlyId​

  ​将​

  ​SnowflakeId​

  ​轉換成比較友好的字元串表示：​

  ​{timestamp}-{machineId}-{sequence} -> 20210623131730192-1-0​

• 自定義​

  ​SnowflakeId​

  ​位配置設定來縮短​

  ​SnowflakeId​

  ​的位數（53-bit）使 ​

  ​ID​

  ​ 提供給前端時不溢出

• ​SafeJavaScriptSnowflakeId​

  ​(​

  ​JavaScript​

  ​ 安全的 ​

  ​SnowflakeId​

  ​)

号段模式（SegmentId）

從上面的設計圖中，不難看出号段模式基本設計思路是通過每次擷取一定長度（Step）的可用ID（Id段/号段），來降低網絡IO請求次數，提升性能。

• ????強依賴第三方号段分發器，可用性受到第三方分發器影響。
• ????每次号段用完時擷取​

  ​NextMaxId​

  ​需要進行網絡IO請求，此時的性能會比較低。
• 單執行個體ID單調遞增，全局趨勢遞增。

• 從設計圖中不難看出Instance 1每次擷取的​

  ​NextMaxId​

  ​，一定比上一次大，意味着下一次的号段一定比上一次大，是以從單執行個體上來看是單調遞增的。
• 多執行個體各自持有的不同的号段，意味着同一時刻不同執行個體生成的ID是亂序的，但是整體趨勢的遞增的，是以全局趨勢遞增。

• ID亂序程度受到Step長度以及叢集規模影響（從趨勢遞增圖中不難看出）。

• 假設叢集中隻有一個執行個體時号段模式就是單調遞增的。

• ​Step​

  ​越小，亂序程度越小。當​

  ​Step=1​

  ​時，将無限接近單調遞增。需要注意的是這裡是無限接近而非等于單調遞增，具體原因你可以思考一下這樣一個場景：

• 号段分發器T1時刻給Instance 1分發了​

  ​ID=1​

  ​,T2時刻給Instance 2分發了​

  ​ID=2​

  ​。因為機器性能、網絡等原因，​

  ​Instance 2​

  ​網絡IO寫請求先于​

  ​Instance 1​

  ​到達。那麼這個時候對于資料庫來說，ID依然是亂序的。

号段鍊模式（SegmentChainId）

SegmentChainId是SegmentId增強版，相比于SegmentId有以下優勢：

• 穩定性：SegmentId的穩定性問題（P9999=46.624(us/op)）主要是因為号段用完之後同步進行​

  ​NextMaxId​

  ​的擷取導緻的（會産生網絡IO）。

• SegmentChainId （P9999=0.208(us/op)）引入了新的角色PrefetchWorker用以維護和保證安全距離，理想情況下使得擷取ID的線程幾乎完全不需要進行同步的等待​

  ​NextMaxId​

  ​擷取，性能可達到近似 ​

  ​AtomicLong​

  ​ 的 TPS 性能:12743W+/s ​​JMH 基準測試​​ 。

• 适應性：從SegmentId介紹中我們知道了影響ID亂序的因素有倆個：叢集規模、​

  ​Step​

  ​大小。叢集規模是我們不能控制的，但是​

  ​Step​

  ​是可以調節的。

• ​Step​

  ​應該近可能小才能使得ID單調遞增的可能性增大。

• ​Step​

  ​太小會影響吞吐量，那麼我們如何合理設定​

  ​Step​

  ​呢？答案是我們無法準确預估所有時點的吞吐量需求，那麼最好的辦法是吞吐量需求高時，Step自動增大，吞吐量低時Step自動收縮。
• SegmentChainId引入了饑餓狀态的概念，PrefetchWorker會根據饑餓狀态檢測目前安全距離是否需要膨脹或者收縮，以便獲得吞吐量與有序性之間的權衡，這便是SegmentChainId的自适應性。

SegmentChainId-吞吐量 (ops/s)

SegmentChainId-每次操作耗時的百分位數

基準測試報告運作環境說明

• 基準測試運作環境：筆記本開發機(MacBook-Pro-(M1))
• 所有基準測試都在開發筆記本上執行。