今天的話題，要給大家分享的大廠面試題是：千萬級(jí)唯一ID如何生成？！看起來這是一個(gè)非常具體的問題，沒錯(cuò)！分布式項(xiàng)目中，無法避免這個(gè)問題，但是我想說的是，面試官通過打開這個(gè)問題，是可以從這個(gè)角度了解面試者在分布式應(yīng)用中是否有豐富經(jīng)驗(yàn)的，分布式大型項(xiàng)目才會(huì)有這個(gè)問題吧，看似一個(gè)具體的問題，背后卻是面試官密謀最佳人選的經(jīng)驗(yàn)，今天威哥就來聊一聊這個(gè)話題。

為了讓小伙伴們有身臨其境的感覺，威哥會(huì)以場(chǎng)景化的面試方式來講解，小伙伴們準(zhǔn)備好了嗎，馬上開整。

首先來看一下互聯(lián)網(wǎng)大廠必問題 ：

• 做過分布式項(xiàng)目嗎？

• 知道分布式 ID 生成策略嗎？

• 如何實(shí)現(xiàn)的？

注意面試官的預(yù)期

是否有分布式項(xiàng)目經(jīng)驗(yàn)

對(duì)分布式 ID 生成算法研究的深度

面試官老哥：

“一條大河向東流，ID 策略惹閑愁”

在分布式項(xiàng)目中，你使用的分布式 ID 策略是什么？

面試者小哥哥：

“我敬歲月三杯酒，雪花算法來出頭”

是的，我在分布式項(xiàng)目采用當(dāng)前主流的雪花算法來實(shí)現(xiàn)。

SnowFlake 算法，是 Twitter 開源的分布式 id 生成算法。其核心思想就是：使用一個(gè) 64 bit 的 long 型的數(shù)字作為全局唯一 id，在分布式系統(tǒng)中的應(yīng)用十分廣泛。

在復(fù)雜分布式系統(tǒng)中，往往需要對(duì)大量的數(shù)據(jù)和消息進(jìn)行唯一標(biāo)識(shí)。如在美團(tuán)點(diǎn)評(píng)的金融、支付、餐飲、酒店、貓眼電影等產(chǎn)品的系統(tǒng)中，數(shù)據(jù)日漸增長(zhǎng)，對(duì)數(shù)據(jù)分庫(kù)分表后需要有一個(gè)唯一ID來標(biāo)識(shí)一條數(shù)據(jù)或消息，數(shù)據(jù)庫(kù)的自增ID顯然不能滿足需求；特別一點(diǎn)的如訂單、騎手、優(yōu)惠券也都需要有唯一ID做標(biāo)識(shí)。此時(shí)一個(gè)能夠生成全局唯一ID的系統(tǒng)是非常必要的。

概括下來，那業(yè)務(wù)系統(tǒng)對(duì)ID號(hào)的要求有哪些呢？

• 全局唯一性：不能出現(xiàn)重復(fù)的ID號(hào)，既然是唯一標(biāo)識(shí)，這是最基本的要求。

• 趨勢(shì)遞增：在MySQL InnoDB引擎中使用的是聚集索引，由于多數(shù)RDBMS使用B-tree的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)索引數(shù)據(jù)，在主鍵的選擇上面我們應(yīng)該盡量使用有序的主鍵保證寫入性能。

• 單調(diào)遞增：保證下一個(gè)ID一定大于上一個(gè)ID，例如事務(wù)版本號(hào)、IM增量消息、排序等特殊需求。

• 信息安全：如果ID是連續(xù)的，惡意用戶的扒取工作就非常容易做了，直接按照順序下載指定URL即可；如果是訂單號(hào)就更危險(xiǎn)了，競(jìng)對(duì)可以直接知道我們一天的單量。所以在一些應(yīng)用場(chǎng)景下，會(huì)需要ID無規(guī)則。

常見方法生成 ID 帶來的問題？

1.UUID：示例：550e8400-e29b-41d4-a716-446655 440000

• 優(yōu)點(diǎn)：性能非常高

• 缺點(diǎn)：不易于存儲(chǔ)、信息不安全、不適合作為主鍵

2.數(shù)據(jù)庫(kù)生成：以MySQL舉例，利用給字段設(shè)置auto_increment_increment和auto_increment_offset來保證ID自增。

• 優(yōu)點(diǎn)：非常簡(jiǎn)單、ID號(hào)單調(diào)自增

• 缺點(diǎn)：強(qiáng)依賴DB、ID發(fā)號(hào)性能瓶頸限制在單臺(tái)MySQL的讀寫性能

分布式id生成器-雪花算法

JAVA實(shí)現(xiàn)雪花算法：https://github.com/beyond fengyu/SnowFlake

這 64 個(gè) bit 中：

其中1個(gè)bit是不用的，然后用其中的41 bit作為毫秒數(shù)，用10 bit作為工作機(jī)器id，12 bit作為序列號(hào)。

面試官老哥：

你們項(xiàng)目中是怎樣使用雪花算法的，可以講一講嗎？

面試者小哥哥：

關(guān)于這個(gè)問題，我們可以直接切入正題，以下以Leaf解決方案來展開，Leaf方案（https://github.com /Meituan-Dianping/Leaf）

Leaf方案實(shí)現(xiàn)

Leaf這個(gè)名字是來自德國(guó)哲學(xué)家、數(shù)學(xué)家萊布尼茨的一句話:世界上沒有兩片相同的樹葉(There are no two identical leaves in the world )

Leaf實(shí)現(xiàn)了Leaf-segment（號(hào)段模式）和Leaf-snowflake方案（雪花算法）

第一種Leaf-segment方案，在使用數(shù)據(jù)庫(kù)的方案上，做了如下改變：-原方案每次獲取ID都得讀寫一次數(shù)據(jù)庫(kù)，造成數(shù)據(jù)庫(kù)壓力大。改為利用proxy server批量獲取，每次獲取一個(gè)segment(step決定大小)號(hào)段的值。用完之后再去數(shù)據(jù)庫(kù)獲取新的號(hào)段，可以大大的減輕數(shù)據(jù)庫(kù)的壓力。各個(gè)業(yè)務(wù)不同的發(fā)號(hào)需求用biz_tag字段來區(qū)分，每個(gè)biz-tag的ID獲取相互隔離，互不影響。如果以后有性能需求需要對(duì)數(shù)據(jù)庫(kù)擴(kuò)容，不需要上述描述的復(fù)雜的擴(kuò)容操作，只需要對(duì)biz_tag分庫(kù)分表就行。

重要字段說明：biz_tag用來區(qū)分業(yè)務(wù)，max_id表示該biz_tag目前所被分配的ID號(hào)段的最大值，step表示每次分配的號(hào)段長(zhǎng)度。原來獲取ID每次都需要寫數(shù)據(jù)庫(kù)，現(xiàn)在只需要把step設(shè)置得足夠大，比如1000。那么只有當(dāng)1000個(gè)號(hào)被消耗完了之后才會(huì)去重新讀寫一次數(shù)據(jù)庫(kù)。讀寫數(shù)據(jù)庫(kù)的頻率從1減小到了1/step。

test_tag在第一臺(tái)Leaf機(jī)器上是1~1000的號(hào)段，當(dāng)這個(gè)號(hào)段用完時(shí)，會(huì)去加載另一個(gè)長(zhǎng)度為step=1000的號(hào)段，假設(shè)另外兩臺(tái)號(hào)段都沒有更新，這個(gè)時(shí)候第一臺(tái)機(jī)器新加載的號(hào)段就應(yīng)該是3001~4000。同時(shí)數(shù)據(jù)庫(kù)對(duì)應(yīng)的biz_tag這條數(shù)據(jù)的max_id會(huì)從3000被更新成4000。

Leaf 還采用雙buffer對(duì)號(hào)段模式進(jìn)行優(yōu)化

簡(jiǎn)單的說就是：Leaf 取號(hào)段的時(shí)機(jī)是在號(hào)段消耗完的時(shí)候進(jìn)行的，也就意味著號(hào)段臨界點(diǎn)的ID下發(fā)時(shí)間取決于下一次從DB取回號(hào)段的時(shí)間，并且在這期間進(jìn)來的請(qǐng)求也會(huì)因?yàn)镈B號(hào)段沒有取回來，導(dǎo)致線程阻塞。如果請(qǐng)求DB的網(wǎng)絡(luò)和DB的性能穩(wěn)定，這種情況對(duì)系統(tǒng)的影響是不大的，但是假如取DB的時(shí)候網(wǎng)絡(luò)發(fā)生抖動(dòng)，或者DB發(fā)生慢查詢就會(huì)導(dǎo)致整個(gè)系統(tǒng)的響應(yīng)時(shí)間變慢。

這樣DB取號(hào)段的過程能夠做到無阻塞，不需要在DB取號(hào)段的時(shí)候阻塞請(qǐng)求線程，即當(dāng)號(hào)段消費(fèi)到某個(gè)點(diǎn)時(shí)就異步的把下一個(gè)號(hào)段加載到內(nèi)存中。而不需要等到號(hào)段用盡的時(shí)候才去更新號(hào)段。

采用雙buffer的方式，Leaf服務(wù)內(nèi)部有兩個(gè)號(hào)段緩存區(qū)segment。當(dāng)前號(hào)段已下發(fā)10%時(shí)，如果下一個(gè)號(hào)段未更新，則另啟一個(gè)更新線程去更新下一個(gè)號(hào)段。當(dāng)前號(hào)段全部下發(fā)完后，如果下個(gè)號(hào)段準(zhǔn)備好了則切換到下個(gè)號(hào)段為當(dāng)前segment接著下發(fā)，循環(huán)往復(fù)。

Leaf-segment方案可以生成趨勢(shì)遞增的ID，同時(shí)ID號(hào)是可計(jì)算的，不適用于訂單ID生成場(chǎng)景，比如競(jìng)對(duì)在兩天中午12點(diǎn)分別下單，通過訂單id號(hào)相減就能大致計(jì)算出公司一天的訂單量，這個(gè)是不能忍受的。面對(duì)這一問題，美團(tuán)提供了 Leaf-snowflake方案。

Leaf-snowflake方案完全沿用snowflake方案的bit位設(shè)計(jì)，即是“1+41+10+12”的方式組裝ID號(hào)。對(duì)于workerID的分配，當(dāng)服務(wù)集群數(shù)量較小的情況下，完全可以手動(dòng)配置。Leaf服務(wù)規(guī)模較大，動(dòng)手配置成本太高。所以使用Zookeeper持久順序節(jié)點(diǎn)的特性自動(dòng)對(duì)snowflake節(jié)點(diǎn)配置wokerID。Leaf-snowflake是按照下面幾個(gè)步驟啟動(dòng)的：

• 啟動(dòng)Leaf-snowflake服務(wù)，連接Zookeeper，在leaf_forever父節(jié)點(diǎn)下檢查自己是否已經(jīng)注冊(cè)過（是否有該順序子節(jié)點(diǎn)）。

• 如果有注冊(cè)過直接取回自己的workerID（zk順序節(jié)點(diǎn)生成的int類型ID號(hào)），啟動(dòng)服務(wù)。

• 如果沒有注冊(cè)過，就在該父節(jié)點(diǎn)下面創(chuàng)建一個(gè)持久順序節(jié)點(diǎn)，創(chuàng)建成功后取回順序號(hào)當(dāng)做自己的workerID號(hào)，啟動(dòng)服務(wù)。

解決時(shí)鐘問題

因?yàn)檫@種方案依賴時(shí)間，如果機(jī)器的時(shí)鐘發(fā)生了回?fù)?#xff0c;那么就會(huì)有可能生成重復(fù)的ID號(hào)，需要解決時(shí)鐘回退的問題。

參見上圖整個(gè)啟動(dòng)流程圖，服務(wù)啟動(dòng)時(shí)首先檢查自己是否寫過ZooKeeper leaf_forever節(jié)點(diǎn)：

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

• 若未寫過，證明是新服務(wù)節(jié)點(diǎn)，直接創(chuàng)建持久節(jié)點(diǎn)leaf_forever/${self}并寫入自身系統(tǒng)時(shí)間，接下來綜合對(duì)比其余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請(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í)寫臨時(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í)間寫入leaf_forever/${self}。

Leaf在美團(tuán)點(diǎn)評(píng)公司內(nèi)部服務(wù)包含金融、支付交易、餐飲、外賣、酒店旅游、貓眼電影等眾多業(yè)務(wù)線。目前Leaf的性能在4C8G的機(jī)器上QPS能壓測(cè)到近5w/s，TP999 1ms，已經(jīng)能夠滿足大部分的業(yè)務(wù)的需求。每天提供億數(shù)量級(jí)的調(diào)用量。

其他ID生產(chǎn)策略

百度uid-generator

https://github.com/baidu/uid-generator

UidGenerator是Java實(shí)現(xiàn)的, 基于Snowflake算法的唯一ID生成器。UidGenerator以組件形式工作在應(yīng)用項(xiàng)目中, 支持自定義workerId位數(shù)和初始化策略, 從而適用于docker等虛擬化環(huán)境下實(shí)例自動(dòng)重啟、漂移等場(chǎng)景。在實(shí)現(xiàn)上, UidGenerator通過借用未來時(shí)間來解決sequence天然存在的并發(fā)限制; 采用RingBuffer來緩存已生成的UID, 并行化UID的生產(chǎn)和消費(fèi), 同時(shí)對(duì)CacheLine補(bǔ)齊，避免了由RingBuffer帶來的硬件級(jí)「?jìng)喂蚕怼箚栴}. 最終單機(jī)QPS可達(dá)600萬。

滴滴 Tinyid

https://github.com/didi/tinyid

Tinyid是用Java開發(fā)的一款分布式id生成系統(tǒng)，基于數(shù)據(jù)庫(kù)號(hào)段算法實(shí)現(xiàn)，關(guān)于這個(gè)算法可以參考美團(tuán)leaf或者tinyid原理介紹。Tinyid擴(kuò)展了leaf-segment算法，支持了多db(master)，同時(shí)提供了java-client(sdk)使id生成本地化，獲得了更好的性能與可用性。Tinyid在滴滴客服部門使用，均通過tinyid-client方式接入，每天生成億級(jí)別的id。

最后小結(jié)一下

本文我們一起聊了分布式 ID 生成策略，Snowflake算法的原理，實(shí)現(xiàn)方案，和國(guó)內(nèi)大廠的開源實(shí)現(xiàn)，這點(diǎn)很重要，在面試過程，可以按照這個(gè)思路：找到問題，以及如何解決問題，這個(gè)思路不僅僅是在搞技術(shù)寫代碼上，在日常工作中的任何事情都可以有這個(gè)思路，你想啊，如果只提問題，不提解決問題的方法，那就成了抱怨了，這不是一個(gè)積極努力向上的人應(yīng)該有的狀態(tài)。

代碼人生，從代碼中還能領(lǐng)悟到做事的道理，你學(xué)會(huì)了嗎？歡迎各位前進(jìn)路上的兄弟們?cè)u(píng)論關(guān)注，每天進(jìn)步一點(diǎn)點(diǎn)，威哥與你同在。

總結(jié)

以上是生活随笔為你收集整理的手把手教你千万级唯一ID如何生成的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。