分布式系統(tǒng)中生成唯一ID在后臺(tái)開(kāi)發(fā)是經(jīng)常遇到的架構(gòu)設(shè)計(jì)，當(dāng)然方案有很多，比如通過(guò)redis或者數(shù)據(jù)庫(kù)實(shí)現(xiàn)自增。但是如果依賴redis或者數(shù)據(jù)庫(kù)，會(huì)導(dǎo)致單點(diǎn)問(wèn)題，在架構(gòu)上反而需要考慮點(diǎn)更多，那怎么解決呢？

首先分布式唯一ID需要支持如下：

• 全局唯一：必須保證生成的ID是全局性唯一的；
• 有序性：生成的ID是有序，方便追溯和排序操作；
• 可用性：需要保證高并發(fā)下的可用性，除了對(duì)ID號(hào)碼自身的要求，業(yè)務(wù)還對(duì)ID生成系統(tǒng)的可用性要求極高；
• 自主性：分布式環(huán)境下不依賴中心認(rèn)證即可自行生成ID；
• 安全性：不暴露系統(tǒng)和業(yè)務(wù)的信息；

方案：

• 單機(jī)生成方式
• 第三方模塊生成方式
• 號(hào)段生成方式

單機(jī)生成方式

1、UUID

UUID（Universally Unique Identifier，即通用唯一標(biāo)識(shí)碼）算法的目的是生成某種形式的全局唯一ID來(lái)標(biāo)識(shí)系統(tǒng)中的任一元素，尤其是在分布式環(huán)境下，UUID可以不依賴中心認(rèn)證即可自動(dòng)生成全局唯一ID。UUID的標(biāo)準(zhǔn)形式為32個(gè)十六進(jìn)制數(shù)組成的字符串，且分割為五個(gè)部分，例如：執(zhí)行：cat /proc/sys/kernel/random/uuid，輸出：70048d49-6ef3-4ba6-84c4-1e6e37ec2f4a。

缺點(diǎn)：

• 生成是隨機(jī)的，無(wú)法做到順序生成；
• 性能雖然高，但是輸出的格式不一定符合業(yè)務(wù)要求，無(wú)法比較大??；

2、Snowflake

snowflake(雪花算法)是一個(gè)開(kāi)源的分布式ID生成算法，結(jié)果是一個(gè)long型的ID。snowflake算法將64bit劃分為多段，分開(kāi)來(lái)標(biāo)識(shí)機(jī)器、時(shí)間等信息，其中格式如下：

0   |00000...0000|000...0000|000000000000|
1bit| 41bit時(shí)間戳 |10bit機(jī)器號(hào)|12bit序列遞增|

• 1bit保留位：方便擴(kuò)展；
• 41bit時(shí)間戳：可以標(biāo)識(shí)毫秒時(shí)間戳（最長(zhǎng)支持69年），結(jié)合遞增bit使用，可以保證有序，不過(guò)我覺(jué)得如果qps沒(méi)有超過(guò)4000，使用秒時(shí)間戳也可以；
• 10bit機(jī)器號(hào)：可以支持1024個(gè)機(jī)器ID，用于標(biāo)識(shí)不同的機(jī)器；
• 12bit序列遞增：支持4096個(gè)序列遞增，可以支持同一臺(tái)機(jī)器同一毫秒內(nèi)生成4096個(gè)ID；

snowflake算法優(yōu)勢(shì)是支持遞增，可以根據(jù)自己的算法改造使用bit位，不過(guò)存在如下缺點(diǎn)：

• 強(qiáng)依賴時(shí)間同步，如果某臺(tái)機(jī)器的時(shí)鐘出現(xiàn)回?fù)埽f增就不準(zhǔn)確；
• ID不能完全支持全局遞增，需要依賴定義的機(jī)器號(hào)；

第三方模塊生成方式

通過(guò)mysql，redis，zk或者ticket server實(shí)現(xiàn)架構(gòu)如下：

架構(gòu)

1、Mysql

前面提到依賴mysql也可以實(shí)現(xiàn)序列號(hào)，mysql的auto_increment可以保證全局唯一，不過(guò)需要依賴數(shù)據(jù)庫(kù)，性能上會(huì)有影響。

當(dāng)然提升性能的方式就是將mysql設(shè)置主從模式，但是只是為了序列號(hào)生成，部署多個(gè)mysql實(shí)例確實(shí)有些浪費(fèi)。

2、Redis

redis同樣可以實(shí)現(xiàn)遞增，而且可以保證原子，比如通過(guò)incr或者incrby，雖然性能比mysql要好很多，我測(cè)試下來(lái)4c8g情況下可以支持10W+qps，不過(guò)存在單點(diǎn)維護(hù)問(wèn)題。

3、Zookeeper

利用zookeeper的znode也可以生成序列號(hào)，可以生成32位和64位的數(shù)據(jù)版本號(hào)，客戶端可以使用這個(gè)版本號(hào)來(lái)作為唯一的序列號(hào)，不過(guò)zk的性能比較差，在高并發(fā)場(chǎng)景下基本不建議采用。

4、Ticket Server

Ticket Server類似單獨(dú)的票據(jù)服務(wù)，可以通過(guò)自己的邏輯生成唯一序列號(hào)，比如實(shí)現(xiàn)上可以使用原子遞增，或者根據(jù)各個(gè)業(yè)務(wù)的特性進(jìn)行適配。

不過(guò)要實(shí)現(xiàn)完整的容災(zāi)體系下可持久的服務(wù)工作量是不小的，對(duì)于沒(méi)有太多特殊需求的場(chǎng)景，更建議依賴redis或者mysql。

號(hào)段生成方式

1、大廠方案：美團(tuán)Leaf-segment和Leaf-snowflake方案

1.1 Leaf-segment

具體技術(shù)介紹：https://tech.meituan.com/2017/04/21/mt-leaf.html。Leaf-segment主要解決思路是：對(duì)直接用數(shù)據(jù)庫(kù)自增ID充當(dāng)分布式ID的一種優(yōu)化，減少對(duì)數(shù)據(jù)庫(kù)的訪問(wèn)頻率，每次獲取不是獲取一個(gè)ID，而是獲取一個(gè)號(hào)段，同時(shí)獲取號(hào)段以后，將數(shù)據(jù)持久化到數(shù)據(jù)庫(kù)中，這樣可以解決分布式的搶占或者持久化問(wèn)題，即使DB出現(xiàn)問(wèn)題，也可以通過(guò)Master-Slave來(lái)解決。

Leaf-segment架構(gòu)

1.2 Leaf-snowflake

Leaf-snowflake繼續(xù)使用snowflake方案，主要解決了時(shí)鐘不同步的問(wèn)題，其中中間10bit機(jī)器號(hào)定義為WorkerID，Leaf-snowflake是按照下面幾個(gè)步驟啟動(dòng)的：

• 啟動(dòng)Leaf-snowflake服務(wù)，連接Zookeeper，在leaf_forever父節(jié)點(diǎn)下檢查自己是否已經(jīng)注冊(cè)過(guò)（是否有該順序子節(jié)點(diǎn)）；
• 如果有注冊(cè)過(guò)直接取回自己的workerID（zk順序節(jié)點(diǎn)生成的int類型ID號(hào)），啟動(dòng)服務(wù)；
• 如果沒(méi)有注冊(cè)過(guò)，就在該父節(jié)點(diǎn)下面創(chuàng)建一個(gè)持久順序節(jié)點(diǎn)，創(chuàng)建成功后取回順序號(hào)當(dāng)做自己的workerID號(hào)，啟動(dòng)服務(wù)；
• 檢查服務(wù)啟動(dòng)是否寫(xiě)過(guò)ZooKeeper leaf_forever節(jié)點(diǎn)，并進(jìn)行如下處理：

若寫(xiě)過(guò)，則用自身系統(tǒng)時(shí)間與leaf_forever/節(jié)點(diǎn)記錄時(shí)間做比較，若小于{self}時(shí)間則認(rèn)為機(jī)器時(shí)間發(fā)生了大步長(zhǎng)回?fù)?，服?wù)啟動(dòng)失敗并報(bào)警；

若未寫(xiě)過(guò)，證明是新服務(wù)節(jié)點(diǎn)，直接創(chuàng)建持久節(jié)點(diǎn)leaf_forever/${self}并寫(xiě)入自身系統(tǒng)時(shí)間，接下來(lái)綜合對(duì)比其余Leaf節(jié)點(diǎn)的系統(tǒng)時(shí)間來(lái)判斷自身系統(tǒng)時(shí)間是否準(zhǔn)確，具體做法是取leaf_temporary下的所有臨時(shí)節(jié)點(diǎn)(所有運(yùn)行中的Leaf-snowflake節(jié)點(diǎn))的服務(wù)IP：Port，然后通過(guò)RPC請(qǐng)求得到所有節(jié)點(diǎn)的系統(tǒng)時(shí)間，計(jì)算sum(time)/nodeSize；

若abs( 系統(tǒng)時(shí)間-sum(time)/nodeSize ) < 閾值，認(rèn)為當(dāng)前系統(tǒng)時(shí)間準(zhǔn)確，正常啟動(dòng)服務(wù)，同時(shí)寫(xiě)臨時(shí)節(jié)點(diǎn)leaf_temporary/${self} 維持租約；

否則認(rèn)為本機(jī)系統(tǒng)時(shí)間發(fā)生大步長(zhǎng)偏移，啟動(dòng)失敗并報(bào)警；

每隔一段時(shí)間(3s)上報(bào)自身系統(tǒng)時(shí)間寫(xiě)入leaf_forever/${self}；

Leaf-snowflake架構(gòu)

2、大廠方案：滴滴Tinyid和百度UidGenerator

2.1 滴滴Tinyid

開(kāi)源方案：https://github.com/didi/tinyid。Tinyid和美團(tuán)的Leaf-segment方案類似，從數(shù)據(jù)庫(kù)批量的獲取自增ID，每次從數(shù)據(jù)庫(kù)取出一個(gè)號(hào)段范圍，例如：(1,1000]代表1000個(gè)ID，業(yè)務(wù)服務(wù)將號(hào)段在本地生成1~1000的自增ID并加載到內(nèi)存。Tinyid會(huì)將可用號(hào)段加載到內(nèi)存中，并在內(nèi)存中生成ID，可用號(hào)段在首次獲取ID時(shí)加載，如當(dāng)前號(hào)段使用達(dá)到一定比例時(shí)，系統(tǒng)會(huì)異步的去加載下一個(gè)可用號(hào)段，以此保證內(nèi)存中始終有可用號(hào)段，以便在發(fā)號(hào)服務(wù)宕機(jī)后一段時(shí)間內(nèi)還有可用ID。

Tinyid架構(gòu)

2.2 百度UidGenerator

百度UidGenerator是基于snowflake方案改造，旨在解決時(shí)鐘回?fù)埽瑆orkerid不夠等問(wèn)題。

百度UidGenerator

• 1bit保留位：方便擴(kuò)展；
• 28bit時(shí)間戳：指當(dāng)前時(shí)間與epoch時(shí)間的時(shí)間差，單位為秒，比如2024-01-01 00:00:00上線，那時(shí)間就是當(dāng)前時(shí)間戳-1704038400；
• 22bit節(jié)點(diǎn)id：22bit可以支持4194304臺(tái)機(jī)器，同時(shí)這個(gè)數(shù)據(jù)是持久化到DB，保持每次新增或者重啟都會(huì)自增；
• 13bit序列遞增：支持每秒生成8192個(gè)自增序列號(hào)（未調(diào)整boostPower情況下）；
• UidGenerator優(yōu)化點(diǎn)還包括：

RingBuffer：UidGenerator不再在每次取ID時(shí)都實(shí)時(shí)計(jì)算分布式ID，而是利用RingBuffer數(shù)據(jù)結(jié)構(gòu)預(yù)先生成若干個(gè)分布式ID并保存，引入boostPower可以控制每秒生成ID的上限能力；

時(shí)間遞增：UidGenerator的時(shí)間類型是AtomicLong，且通過(guò)incrementAndGet()方法獲取下一次的時(shí)間，從而脫離了對(duì)服務(wù)器時(shí)間的依賴，也就不會(huì)有時(shí)鐘回?fù)艿膯?wèn)題；

3、大廠方案：容災(zāi)

微信內(nèi)部也是通過(guò)獨(dú)立的seqsvr提供序列號(hào)生成，主要面對(duì)場(chǎng)景是微信中的消息版本，其中特性和挑戰(zhàn)如下。

（1）兩個(gè)特性：

• 遞增的32位整型；
• 每個(gè)用戶都有自己的32位sequence空間；

（2）面臨兩個(gè)挑戰(zhàn)：

• 1、分布式場(chǎng)景；
• 2、每秒千萬(wàn)級(jí)別的QPS；
• 3、每個(gè)Uin都需要存儲(chǔ)max-seqid，存儲(chǔ)量大，也帶來(lái)容災(zāi)問(wèn)題；

如何解決分布式場(chǎng)景下的問(wèn)題?

提供兩層：StoreSvr和AllocSvr，分別是存儲(chǔ)層和緩存中間層，分層后就能利用堆機(jī)器就可以解決問(wèn)題；

圖片

每秒千萬(wàn)級(jí)別的QPS？

實(shí)現(xiàn)方案和美團(tuán)Leaf-segment類似，每次提供一批seqid，這樣從千萬(wàn)級(jí)別的qps就變成千級(jí)別的qps，不過(guò)不保證序列號(hào)是連續(xù)的，但是能保證是遞增的。

每個(gè)Uin都需要存儲(chǔ)max-seqid，存儲(chǔ)量大？

每個(gè)用戶需要加載一個(gè)max_seq（32bit），如果uin是2^32個(gè)，則需要存儲(chǔ)數(shù)據(jù)大小為16GB，這樣系統(tǒng)啟動(dòng)時(shí)候加載就會(huì)很慢，微信如何解決？通過(guò)區(qū)分Set，同一批共享同一個(gè)max_seqid，這樣就減少加載的數(shù)據(jù)量。

容災(zāi)如何實(shí)現(xiàn)？

seqsvr服務(wù)雖然簡(jiǎn)單，解決了上述高性能的問(wèn)題，但是要保證高可靠性還是非常難，我查了一下內(nèi)部資料和infoQ一樣，實(shí)現(xiàn)架構(gòu)可以參考：https://www.infoq.cn/article/wechat-serial-number-generator-architecture。seqsvr最核心的點(diǎn)是什么呢？每個(gè) uin 的sequence申請(qǐng)要遞增不回退，但是約束條件是：任意時(shí)刻任意 uin 有且僅有一臺(tái) AllocSvr 提供服務(wù)，就可以比較容易地實(shí)現(xiàn)sequence遞增不回退的要求。

（1）容災(zāi)1.0

容災(zāi)1.0

• 一主一備：每個(gè)Set都是一主一備兩臺(tái) AllocSvr ，主機(jī)出故障時(shí)，仲裁服務(wù)切換主備，原來(lái)的主機(jī)下線變成備機(jī)，原備機(jī)變成主機(jī)后加載 uid 號(hào)段提供服務(wù)；
• 引入仲裁服務(wù)：探測(cè) AllocSvr 的狀態(tài)，決定每個(gè) uin 走到哪一臺(tái) AllocSvr ，同時(shí)解決備機(jī)切換的問(wèn)題；

但是上述面臨問(wèn)題：

• 主從容災(zāi)擴(kuò)縮容麻煩；
• 單個(gè)Set的資源不一定能支撐高并發(fā)請(qǐng)求；

（2）容災(zāi)2.0

通過(guò)提供 Client 路由表方式解決訪問(wèn) AllocSvr 切換的問(wèn)題，執(zhí)行步驟如下：

• Client 根據(jù)本地共享內(nèi)存緩存的路由表，選擇對(duì)應(yīng)的 AllocSvr，如果路由表不存在，隨機(jī)選擇一臺(tái) AllocSvr；
• 對(duì)選中的 AllocSvr 發(fā)起請(qǐng)求，請(qǐng)求帶上本地路由表的版本號(hào)；
• AllocSvr 收到請(qǐng)求，除了處理 sequence 邏輯外，判斷 Client 帶上版本號(hào)是否最新，如果是舊版則在響應(yīng)包中附上最新的路由表；
• Client 收到響應(yīng)包，除了處理 sequence 邏輯外，判斷響應(yīng)包是否帶有新路由表，如果有，更新本地路由表，并決策是否返回第 1 步重試；

容災(zāi)2.0

總結(jié)

以上就是一些場(chǎng)景下生成分布式唯一ID的方案選擇，分布式唯一ID的架構(gòu)雖然簡(jiǎn)單，但是如果要實(shí)現(xiàn)高性能高可用，還是需要根據(jù)業(yè)務(wù)場(chǎng)景來(lái)考慮。所以說(shuō)簡(jiǎn)單的事情要做好并非易事，但是在這些年的工作中總是會(huì)有很多人為了追求效率，總想找到捷徑而放棄架構(gòu)的基本演進(jìn)路徑方法論....

參考

（1）https://learning-guide.gitbook.io/system-design-interview/chapter-07-design-a-unique-id-generator-in-distributed-systems（2）https://tech.meituan.com/2017/04/21/mt-leaf.html（3）https://www.infoq.cn/article/wechat-serial-number-generator-architecture