分布式 ID 生成器

 分布式 ID 生成器是一種在分布式系統(tǒng)中生成全局唯一、有序的 ID 的算法或工具。在分布式系統(tǒng)中，由于各個(gè)節(jié)點(diǎn)之間需要共享數(shù)據(jù)或通信，因此需要一種機(jī)制來(lái)確保每個(gè)節(jié)點(diǎn)生成的 ID 是全局唯一的，以避免出現(xiàn)重復(fù)或沖突。分布式 ID 生成器就是在這種背景下應(yīng)運(yùn)而生的。

分布式 ID 生成器有很多種實(shí)現(xiàn)方案，常見(jiàn)的包括：

1. 數(shù)據(jù)庫(kù)自增長(zhǎng)序列或字段：利用數(shù)據(jù)庫(kù)的自動(dòng)遞增功能生成 ID，適用于簡(jiǎn)單的分布式系統(tǒng)。

2. UUID（通用唯一識(shí)別碼）：UUID 是一個(gè)由微軟公司開(kāi)發(fā)的 ID 生成算法，生成的 ID 具有較高的唯一性。

3. Snowflake 算法：Snowflake 是 Twitter 開(kāi)源的分布式 ID 生成算法，生成的 ID 是一個(gè) long 型的值。其核心思想是使用 41bit 作為毫秒數(shù)，10bit 作為機(jī)器 ID（5 個(gè) bit 是數(shù)據(jù)中心，5 個(gè) bit 是機(jī)器 ID），剩余的 12bit 用于序列號(hào)。

4. Redis 生成器：基于 Redis 的分布式 ID 生成器，可以通過(guò) Redis 的計(jì)數(shù)器功能生成 ID。

5. 基于開(kāi)源庫(kù)的生成器：如 Go 語(yǔ)言中的 idgenerator 庫(kù)，Java 中的 Spring Boot ID 生成器等。

分布式 ID 生成器的設(shè)計(jì)和實(shí)現(xiàn)需要考慮性能、可擴(kuò)展性、可靠性等因素，以滿足分布式系統(tǒng)的需求。

CosId 

CosId 旨在提供通用、靈活、高性能的分布式 ID 生成器。

• CosIdGenerator : 單機(jī) TPS 性能：1557W/s，三倍于 UUID.randomUUID()，基于時(shí)鐘的全局趨勢(shì)遞增ID。

  
  

• SnowflakeId : 單機(jī) TPS 性能：409W/s JMH 基準(zhǔn)測(cè)試 , 主要解決 時(shí)鐘回?fù)軉?wèn)題 、機(jī)器號(hào)分配問(wèn)題、取模分片不均勻問(wèn)題 并且提供更加友好、靈活的使用體驗(yàn)。

  
  

• SegmentId: 每次獲取一段 (Step) ID，來(lái)降低號(hào)段分發(fā)器的網(wǎng)絡(luò)IO請(qǐng)求頻次提升性能。

• RedisIdSegmentDistributor: 基于 Redis 的號(hào)段分發(fā)器。

• JdbcIdSegmentDistributor: 基于 Jdbc 的號(hào)段分發(fā)器，支持各種關(guān)系型數(shù)據(jù)庫(kù)。

• ZookeeperIdSegmentDistributor: 基于 Zookeeper 的號(hào)段分發(fā)器。

• MongoIdSegmentDistributor: 基于 MongoDB 的號(hào)段分發(fā)器。

• IdSegmentDistributor: 號(hào)段分發(fā)器（號(hào)段存儲(chǔ)器）

  
  

• SegmentChainId(推薦):SegmentChainId (lock-free) 是對(duì) SegmentId 的增強(qiáng)。性能可達(dá)到近似 AtomicLong 的 TPS 性能:12743W+/s JMH 基準(zhǔn)測(cè)試 。

• PrefetchWorker 維護(hù)安全距離(safeDistance), 并且支持基于饑餓狀態(tài)的動(dòng)態(tài)safeDistance擴(kuò)容/收縮。

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

在軟件系統(tǒng)演進(jìn)過(guò)程中，隨著業(yè)務(wù)規(guī)模的增長(zhǎng) (TPS/存儲(chǔ)容量)，我們需要通過(guò)集群化部署來(lái)分?jǐn)傆?jì)算、存儲(chǔ)壓力。應(yīng)用服務(wù)的無(wú)狀態(tài)設(shè)計(jì)使其具備了伸縮性。在使用 Kubernetes 部署時(shí)我們只需要一行命令即可完成服務(wù)伸縮 (kubectl scale --replicas=5 deployment/order-service)。

但對(duì)于有狀態(tài)的數(shù)據(jù)庫(kù)就不那么容易了，此時(shí)數(shù)據(jù)庫(kù)變成系統(tǒng)的性能瓶頸是顯而易見(jiàn)的。

分庫(kù)分表

從微服務(wù)的角度來(lái)理解垂直拆分其實(shí)就是微服務(wù)拆分。以限界上下文來(lái)定義服務(wù)邊界將大服務(wù)/單體應(yīng)用拆分成多個(gè)自治的粒度更小的服務(wù)，因?yàn)樽灾涡砸?guī)范要求，數(shù)據(jù)庫(kù)也需要進(jìn)行業(yè)務(wù)拆分。但垂直拆分后的單個(gè)微服務(wù)依然會(huì)面臨 TPS/存儲(chǔ)容量 的挑戰(zhàn)，所以這里我們重點(diǎn)討論水平拆分的方式。

數(shù)據(jù)庫(kù)分庫(kù)分表方案是邏輯統(tǒng)一，物理分區(qū)自治的方案。其核心設(shè)計(jì)在于中間層映射方案的設(shè)計(jì) (上圖 Mapping)，即分片算法的設(shè)計(jì)。幾乎所有編程語(yǔ)言都內(nèi)置實(shí)現(xiàn)了散列表(java:HashMap/csharp:Dictionary/python:dict/go:map ...)。分片算法跟散列表高度相似(hashCode)，都得通過(guò) key/shardingValue 映射到對(duì)應(yīng)的槽位(slot)。

那么 shardingValue 從哪里來(lái)呢？CosId?。?！

當(dāng)然還有很多分布式場(chǎng)景需要分布式ID，這里不再一一列舉。

分布式ID方案的核心指標(biāo)

• 全局（相同業(yè)務(wù)）唯一性：唯一性保證是ID的必要條件，假設(shè)ID不唯一就會(huì)產(chǎn)生主鍵沖突，這點(diǎn)很容易可以理解。

• 通常所說(shuō)的全局唯一性并不是指所有業(yè)務(wù)服務(wù)都要唯一，而是相同業(yè)務(wù)服務(wù)不同部署副本唯一。比如 Order 服務(wù)的多個(gè)部署副本在生成t_order這張表的Id時(shí)是要求全局唯一的。至于t_order_item生成的ID與t_order是否唯一，并不影響唯一性約束，也不會(huì)產(chǎn)生什么副作用。不同業(yè)務(wù)模塊間也是同理。即唯一性主要解決的是ID沖突問(wèn)題。

• 有序性：有序性保證是面向查詢的數(shù)據(jù)結(jié)構(gòu)算法（除了Hash算法）所必須的，是二分查找法(分而治之)的前提。

• MySq-InnoDB B+樹(shù)是使用最為廣泛的，假設(shè) Id 是無(wú)序的，B+ 樹(shù) 為了維護(hù) ID 的有序性，就會(huì)頻繁的在索引的中間位置插入而挪動(dòng)后面節(jié)點(diǎn)的位置，甚至導(dǎo)致頻繁的頁(yè)分裂，這對(duì)于性能的影響是極大的。那么如果我們能夠保證ID的有序性這種情況就完全不同了，只需要進(jìn)行追加寫操作。所以 ID 的有序性是非常重要的，也是ID設(shè)計(jì)不可避免的特性。

• 吞吐量/性能(ops/time)：即單位時(shí)間（每秒）能產(chǎn)生的ID數(shù)量。生成ID是非常高頻的操作，也是最為基本的。假設(shè)ID生成的性能緩慢，那么不管怎么進(jìn)行系統(tǒng)優(yōu)化也無(wú)法獲得更好的性能。

• 一般我們會(huì)首先生成ID，然后再執(zhí)行寫入操作，假設(shè)ID生成緩慢，那么整體性能上限就會(huì)受到限制，這一點(diǎn)應(yīng)該不難理解。

• 穩(wěn)定性(time/op)：穩(wěn)定性指標(biāo)一般可以采用每個(gè)操作的時(shí)間進(jìn)行百分位采樣來(lái)分析，比如 CosId 百分位采樣 P9999=0.208 us/op，即 0% ~ 99.99% 的單位操作時(shí)間小于等于 0.208 us/op。

• 百分位數(shù) WIKI ：統(tǒng)計(jì)學(xué)術(shù)語(yǔ)，若將一組數(shù)據(jù)從小到大排序，并計(jì)算相應(yīng)的累計(jì)百分點(diǎn)，則某百分點(diǎn)所對(duì)應(yīng)數(shù)據(jù)的值，就稱為這百分點(diǎn)的百分位數(shù)，以Pk表示第k百分位數(shù)。百分位數(shù)是用來(lái)比較個(gè)體在群體中的相對(duì)地位量數(shù)。

• 為什么不用平均每個(gè)操作的時(shí)間：馬老師的身價(jià)跟你的身價(jià)能平均么？平均后的值有意義不？

• 可以使用最小每個(gè)操作的時(shí)間、最大每個(gè)操作的時(shí)間作為參考嗎？因?yàn)樽钚?、最大值只說(shuō)明了零界點(diǎn)的情況，雖說(shuō)可以作為穩(wěn)定性的參考，但依然不夠全面。而且百分位數(shù)已經(jīng)覆蓋了這倆個(gè)指標(biāo)。

• 自治性（依賴）：主要是指對(duì)外部環(huán)境有無(wú)依賴，比如號(hào)段模式會(huì)強(qiáng)依賴第三方存儲(chǔ)中間件來(lái)獲取NexMaxId。自治性還會(huì)對(duì)可用性造成影響。

• 可用性：分布式ID的可用性主要會(huì)受到自治性影響，比如SnowflakeId會(huì)受到時(shí)鐘回?fù)苡绊?，?dǎo)致處于短暫時(shí)間的不可用狀態(tài)。而號(hào)段模式會(huì)受到第三方發(fā)號(hào)器（NexMaxId）的可用性影響。

• 可用性 WIKI ：在一個(gè)給定的時(shí)間間隔內(nèi)，對(duì)于一個(gè)功能個(gè)體來(lái)講，總的可用時(shí)間所占的比例。

• MTBF：平均故障間隔

• MDT：平均修復(fù)/恢復(fù)時(shí)間

• Availability=MTBF/(MTBF+MDT)

• 假設(shè)MTBF為1年，MDT為1小時(shí)，即Availability=(365*24)/(365*24+1)=0.999885857778792≈99.99%，也就是我們通常所說(shuō)對(duì)可用性4個(gè)9。

• 適應(yīng)性：是指在面對(duì)外部環(huán)境變化的自適應(yīng)能力，這里我們主要說(shuō)的是面對(duì)流量突發(fā)時(shí)動(dòng)態(tài)伸縮分布式ID的性能，

• SegmentChainId可以基于饑餓狀態(tài)進(jìn)行安全距離的動(dòng)態(tài)伸縮。

• SnowflakeId常規(guī)位分配方案性能恒定409.6W，雖然可以通過(guò)調(diào)整位分配方案來(lái)獲得不同的TPS性能，但是位分配方法的變更是破壞性的，一般根據(jù)業(yè)務(wù)場(chǎng)景確定位分配方案后不再變更。

• 存儲(chǔ)空間：還是用MySq-InnoDB B+樹(shù)來(lái)舉例，普通索引（二級(jí)索引）會(huì)存儲(chǔ)主鍵值，主鍵越大占用的內(nèi)存緩存、磁盤空間也會(huì)越大。Page頁(yè)存儲(chǔ)的數(shù)據(jù)越少，磁盤IO訪問(wèn)的次數(shù)會(huì)增加?？傊跐M足業(yè)務(wù)需求的情況下，盡可能小的存儲(chǔ)空間占用在絕大多數(shù)場(chǎng)景下都是好的設(shè)計(jì)原則。

不同分布式ID方案核心指標(biāo)對(duì)比

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

剛剛我們已經(jīng)討論了ID有序性的重要性，所以我們?cè)O(shè)計(jì)ID算法時(shí)應(yīng)該盡可能地讓ID是單調(diào)遞增的，比如像表的自增主鍵那樣。但是很遺憾，因全局時(shí)鐘、性能等分布式系統(tǒng)問(wèn)題，我們通常只能選擇局部單調(diào)遞增、全局趨勢(shì)遞增的組合（就像我們?cè)诜植际较到y(tǒng)中不得不的選擇最終一致性那樣）以獲得多方面的權(quán)衡。下面我們來(lái)看一下什么是單調(diào)遞增與趨勢(shì)遞增。

CosId VS 美團(tuán) Leaf

CosId (SegmentChainId) 性能是 Leaf(segment) 的 5 倍。

開(kāi)源的分布式ID

 開(kāi)源的分布式 ID 生成器有很多種，以下是一些較為知名的：

1. Twitter 的 Snowflake 算法：Snowflake 是 Twitter 開(kāi)源的分布式 ID 生成算法，生成的 ID 是一個(gè) long 型的值。其核心思想是使用 41bit 作為毫秒數(shù)，10bit 作為機(jī)器 ID（5 個(gè) bit 是數(shù)據(jù)中心，5 個(gè) bit 是機(jī)器 ID），剩余的 12bit 用于序列號(hào)。

2. 美團(tuán)的 Leaf 項(xiàng)目：Leaf 是美團(tuán)開(kāi)源的分布式 ID 生成項(xiàng)目，基于 Snowflake 算法，支持 RPC 方式調(diào)用，據(jù)官方提供的信息，其 QPS 壓測(cè)結(jié)果近 5w/s，tp999,1ms。

3. 百度的 UidGenerator：UidGenerator 是百度開(kāi)源的一款分布式高性能的唯一 ID 生成器，基于 Twitter 的 Snowflake 算法實(shí)現(xiàn)，支持自定義時(shí)間戳、工作機(jī)器 id 和序列號(hào)。

4. 滴滴的 Tinyid：Tinyid 是滴滴開(kāi)源的分布式 ID 生成器，基于 Snowflake 算法，適用于小規(guī)模的分布式系統(tǒng)。

這些開(kāi)源的分布式 ID 生成器在不同的場(chǎng)景和需求下有著各自的優(yōu)勢(shì)和特點(diǎn)，可以根據(jù)實(shí)際需求選擇適合的生成器來(lái)實(shí)現(xiàn)。