分佈式ID生成器（CosId）的設計與實現

• 2021 年 7 月 27 日
• 筆記

分佈式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有序性的重要性，所以我們設計ID算法時應該儘可能地讓ID是單調遞增的，比如像表的自增主鍵那樣。但是很遺憾，因全局時鐘、性能等分佈式系統問題，我們通常只能選擇局部單調遞增、全局趨勢遞增的組合（就像我們在分佈式系統中不得不的選擇最終一致性那樣）以獲得多方面的權衡。下面我們來看一下什麼是單調遞增與趨勢遞增。

有序性之單調遞增

單調遞增：T表示全局絕對時點，假設有T_n+1>T_n（絕對時間總是往前進的，這裡不考慮相對論、時間機器等），那麼必然有F(T_n+1)>F(T_n)，數據庫自增主鍵就屬於這一類。
另外需要特別說明的是單調遞增跟連續性遞增（F(n+1)=F(n)+step）是不同的概念。

有序性之趨勢遞增

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

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

分佈式ID分配方案

UUID/GUID

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

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

SnowflakeId

SnowflakeId使用Long（64-bit）位分區來生成ID的一種分佈式ID算法。
通用的位分配方案為：timestamp(41-bit)+machineId(10-bit)+sequence(12-bit)=63-bit。

• 41-bittimestamp=(1L<<41)/(1000/3600/365)，約可以存儲69年的時間戳，即可以使用的絕對時間為EPOCH+69年，一般我們需要自定義EPOCH為產品開發時間，另外還可以通過壓縮其他區域的分配位數，來增加時間戳位數來延長可用時間。
• 10-bitmachineId=(1L<<10)=1024，即相同業務可以部署1024個副本(在Kubernetes概念里沒有主從副本之分，這裡直接沿用Kubernetes的定義)。一般情況下沒有必要使用這麼多位，所以會根據部署規模需要重新定義。
• 12-bitsequence=(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-bitSnowflakeId轉換為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時，將無限接近單調遞增。需要注意的是這裡是無限接近而非等於單調遞增，具體原因你可以思考一下這樣一個場景：
    • 號段分發器T₁時刻給Instance 1分發了ID=1,T₂時刻給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))
• 所有基準測試都在開發筆記本上執行。