交互分布式系統(tǒng)下如何生成唯一序列

更新時(shí)間：2022年01月26日 15:07:34 作者：Brand

在分布式系統(tǒng)中，由于涉及到多個(gè)不同業(yè)務(wù)module的交互，以及高并發(fā)的場(chǎng)景。我們需要系統(tǒng)能夠生成一個(gè)跨業(yè)務(wù)module的全網(wǎng)唯一序列號(hào)，來(lái)保證我們業(yè)務(wù)操作的獨(dú)立性和唯一性

1 介紹

在常見(jiàn)的業(yè)務(wù)場(chǎng)景中，比如全局訂單Id，唯一標(biāo)識(shí)的支付編號(hào)等，都需要這個(gè)來(lái)保證。

那生成ID都有哪些解決方案呢？特別是在復(fù)雜的分布式系統(tǒng)業(yè)務(wù)場(chǎng)景中，我們應(yīng)該采用哪種解決方案來(lái)實(shí)現(xiàn)這個(gè)唯一序列呢？

一般來(lái)說(shuō)，這個(gè)唯一序號(hào)有如下幾種特征：

全局唯一性：確保生成的序列是全局唯一的，不可重復(fù)。
有序性：確保生成的ID值對(duì)于某個(gè)用戶或者業(yè)務(wù)是按一定的數(shù)字有序遞增的。
高可用性：確保生成ID功能的高可用，能夠承接較大峰值，能夠保證序列生成的有效性（不重復(fù)且有序）。
帶時(shí)間標(biāo)記：ID中有時(shí)間片段組成，可是清晰識(shí)別出操作的時(shí)間。

下面是業(yè)內(nèi)幾種常見(jiàn)的分布式唯一序列生成方案，我們一一來(lái)介紹下。

2 數(shù)據(jù)庫(kù)自增

數(shù)據(jù)庫(kù)主鍵設(shè)置自增序號(hào) auto_increment，可以按照一定的趨勢(shì)自增，保證主鍵ID的唯一性。

這個(gè)方案簡(jiǎn)單易操作，優(yōu)點(diǎn)是明顯、可控。

但由于它是在數(shù)據(jù)庫(kù)的單表上進(jìn)行操作，對(duì)數(shù)據(jù)庫(kù)性能依賴比較明顯，高并發(fā)下的壓力也很大。所以不是唯一ID生成的最佳方法。

1 create table `t_generator_id` 
2 ( 
3 `id` bigint(20) not null auto_increment,  -- 表示自增列 
4  -- 其他字段信息
5 )

3 系統(tǒng)時(shí)間毫秒數(shù)

我們可以使用當(dāng)前系統(tǒng)時(shí)間精確到毫秒數(shù)（或者時(shí)間戳）+業(yè)務(wù)屬性+用戶屬性+隨機(jī)數(shù)+...等參數(shù)組合形式來(lái)確保ID的唯一性，缺點(diǎn)是ID的有序性難以保證，如果對(duì)有序性由強(qiáng)需求的業(yè)務(wù)不建議使用。

類似京東淘寶等電商的訂單號(hào)生成。因?yàn)橛唵翁?hào)和用戶id在業(yè)務(wù)上的區(qū)別，訂單號(hào)盡可能要多些冗余的業(yè)務(wù)信息，比如

滴滴：時(shí)間+起點(diǎn)編號(hào)+車牌號(hào) ; 淘寶訂單：時(shí)間戳+用戶ID，類似滴滴訂單的唯一序號(hào)如下：

4 UUID（GUID）

Java自帶的生成UUID的方式（.Net體系下也有GUID可以對(duì)應(yīng)），生成的是Length=32的16進(jìn)制格式的字符串，如果回退為byte數(shù)組共16個(gè)byte元素，即UUID是一個(gè)128bit長(zhǎng)的數(shù)字，一般用16進(jìn)制表示。

可以保證唯一性，但缺點(diǎn)是它不包含時(shí)間標(biāo)識(shí)、業(yè)務(wù)數(shù)據(jù)可讀性太差了，而且也不能ID的有序遞增。優(yōu)點(diǎn)生成方式，簡(jiǎn)單，高效，一般業(yè)務(wù)系統(tǒng)中比較少用。

5 批量預(yù)生成ID

1、在內(nèi)存（緩存）中，按需批量生成N個(gè)ID，并將最大ID值記錄到數(shù)據(jù)庫(kù)中。比如生成 1~10000，把max=10000持久化到數(shù)據(jù)庫(kù)中，內(nèi)存中記錄的是current=1和max=10000。

2、所有的使用都在內(nèi)存中進(jìn)行，每消耗一次序號(hào)，current + 1。

3、當(dāng)current==max的時(shí)候，重復(fù)第一個(gè)步驟，再次批量生成 10001~20000的值，并將數(shù)據(jù)庫(kù)中的max改成20000。

優(yōu)點(diǎn)是避免了每次生成ID都要訪問(wèn)數(shù)據(jù)庫(kù)并帶來(lái)壓力。

缺點(diǎn)是只能是單點(diǎn)服務(wù)，如果服務(wù)重啟勢(shì)必會(huì)造成ID丟失不連續(xù)的情況，而且這種方式也不利于水平擴(kuò)展。

6 Redis生成唯一序列

Redis可以使用簡(jiǎn)易的String類型，它的 incr/decr key 語(yǔ)法，支持高效快速的增減值，能夠保證生成的ID肯定是唯一有序的。

這種方式不依賴數(shù)據(jù)庫(kù)持久化，速度快，算是比較好的辦法了。但系統(tǒng)中引入Redis這一中間件，無(wú)形中增加維護(hù)成本。在超大流量、超高并發(fā)的情況下，單實(shí)例Redis還是無(wú)法滿足的，需要橫向擴(kuò)展Redis集群來(lái)進(jìn)行支撐。

1 <strong>incr</strong>/<strong>decr key</strong> // 自增減 1
2 <strong>incrby</strong>/<strong>decrby key</strong> increment  // 自增減指定數(shù)值
3 <strong>incrbyfloat</strong>/<strong>decrbyfloat key</strong> increment  // 自增減浮點(diǎn)數(shù)

還可以利用像Zookeeper中的znode數(shù)據(jù)版本來(lái)生成序列號(hào)，及MongoDB的ObjectId等，但是性能不如Redis，不是很推薦。

7 snowflake算法

Twitter在把存儲(chǔ)系統(tǒng)從MySQL遷移到Cassandra的過(guò)程中由于Cassandra沒(méi)有順序ID生成機(jī)制，于是自己開(kāi)發(fā)了一套全局唯一ID生成服務(wù)：Snowflake。

如上圖的所示，Twitter的snowflake算法下面幾部分組成：

41位的時(shí)間序列，精確到毫秒，可以使用69年
10位的機(jī)器標(biāo)識(shí)，最多支持部署1024個(gè)節(jié)點(diǎn)
12位的序列號(hào)，支持每個(gè)節(jié)點(diǎn)每毫秒產(chǎn)生4096個(gè)ID序號(hào)，最高位是符號(hào)位始終為0。

這種方案性能好，在單機(jī)上是遞增的，但是由于涉及到分布式環(huán)境，每臺(tái)機(jī)器上的時(shí)鐘不可能完全同步，也許有時(shí)候也會(huì)出現(xiàn)不是全局遞增的情況。

而且這個(gè)項(xiàng)目在2010就停止維護(hù)了，但這個(gè)設(shè)計(jì)思路被很多廠家參考，應(yīng)用于各個(gè)業(yè)務(wù)的ID生成器及變種。

8 UidGenerator

UidGenerator是百度開(kāi)源的一款分布式高性能的唯一ID生成器，使用Java實(shí)現(xiàn)的, 基于Snowflake算法的唯一ID生成器。

在實(shí)現(xiàn)上, UidGenerator通過(guò)借用未來(lái)時(shí)間來(lái)解決sequence天然存在的并發(fā)限制; 采用RingBuffer來(lái)緩存已生成的UID, 并行化UID的生產(chǎn)和消費(fèi), 同時(shí)對(duì)CacheLine補(bǔ)齊，避免了由RingBuffer帶來(lái)的硬件級(jí)「?jìng)喂蚕怼箚?wèn)題. 最終單機(jī)QPS可達(dá)600萬(wàn)。

具體的GitHub地址如下：

https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md