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

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

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

方案：

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

單機(jī)生成方式

1、UUID

UUID（Universally Unique Identifier，即通用唯一標(biāo)識碼）算法的目的是生成某種形式的全局唯一ID來標(biāo)識系統(tǒng)中的任一元素，尤其是在分布式環(huán)境下，UUID可以不依賴中心認(rèn)證即可自動生成全局唯一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ī)的，無法做到順序生成；
• 性能雖然高，但是輸出的格式不一定符合業(yè)務(wù)要求，無法比較大小；

2、Snowflake

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

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

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

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

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

第三方模塊生成方式

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

架構(gòu)

1、Mysql

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

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

2、Redis

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

3、Zookeeper

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

4、Ticket Server

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

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

號段生成方式

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

1.1 Leaf-segment

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

Leaf-segment架構(gòu)

1.2 Leaf-snowflake

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

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

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

若未寫過，證明是新服務(wù)節(jié)點(diǎn)，直接創(chuàng)建持久節(jié)點(diǎn)leaf_forever/${self}并寫入自身系統(tǒng)時(shí)間，接下來綜合對比其余Leaf節(jié)點(diǎn)的系統(tǒng)時(shí)間來判斷自身系統(tǒng)時(shí)間是否準(zhǔn)確，具體做法是取leaf_temporary下的所有臨時(shí)節(jié)點(diǎn)(所有運(yùn)行中的Leaf-snowflake節(jié)點(diǎn))的服務(wù)IP：Port，然后通過RPC請求得到所有節(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)確，正常啟動服務(wù)，同時(shí)寫臨時(shí)節(jié)點(diǎn)leaf_temporary/${self} 維持租約；

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

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

Leaf-snowflake架構(gòu)

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

2.1 滴滴Tinyid

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

Tinyid架構(gòu)

2.2 百度UidGenerator

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

百度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臺機(jī)器，同時(shí)這個(gè)數(shù)據(jù)是持久化到DB，保持每次新增或者重啟都會自增；
• 13bit序列遞增：支持每秒生成8192個(gè)自增序列號（未調(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，且通過incrementAndGet()方法獲取下一次的時(shí)間，從而脫離了對服務(wù)器時(shí)間的依賴，也就不會有時(shí)鐘回?fù)艿膯栴}；

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

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

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

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

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

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

如何解決分布式場景下的問題?

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

圖片

每秒千萬級別的QPS？

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

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

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

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

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

（1）容災(zāi)1.0

容災(zāi)1.0

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

但是上述面臨問題：

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

（2）容災(zāi)2.0

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

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

容災(zāi)2.0

總結(jié)

以上就是一些場景下生成分布式唯一ID的方案選擇，分布式唯一ID的架構(gòu)雖然簡單，但是如果要實(shí)現(xiàn)高性能高可用，還是需要根據(jù)業(yè)務(wù)場景來考慮。所以說簡單的事情要做好并非易事，但是在這些年的工作中總是會有很多人為了追求效率，總想找到捷徑而放棄架構(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