Java精選面試題（微信小程序）：5000+道面試題和選擇題，真實(shí)面經(jīng)，簡(jiǎn)歷模版，包含Java基礎(chǔ)、并發(fā)、JVM、線程、MQ系列、Redis、Spring系列、Elasticsearch、Docker、K8s、Flink、Spark、架構(gòu)設(shè)計(jì)、大廠真題等，在線隨時(shí)刷題！

今天聊聊服務(wù)器中唯一ID生成。唯一ID生成中雪花算法大家都比較熟，那如果加一個(gè)要求呢：盡量短的數(shù)字ID

之前的項(xiàng)目有個(gè)需求：為用戶賬號(hào)生成賬號(hào)ID。最開(kāi)始用的是UUID（長(zhǎng)字符串ID），但是字符串賬號(hào)相對(duì)于數(shù)字賬號(hào)，存儲(chǔ)和傳輸性能都稍遜，也不利于記憶和傳播。

因此，生成一套業(yè)務(wù)內(nèi)的數(shù)字賬號(hào)，并且盡量簡(jiǎn)短就是當(dāng)務(wù)之急。

初始版本

我們最開(kāi)始考慮的是雪花算法方案，使用的是經(jīng)典的 twitter開(kāi)源的算法 snowflake。這個(gè)算法非常強(qiáng)大，生成的是 64bit 的數(shù)字id，天然支持分布式。

有關(guān)這個(gè)算法的詳細(xì)分析，可以移步：

https://juejin.cn/post/7386243179278041128

雪花算法看起來(lái)無(wú)懈可擊，但是唯一的問(wèn)題就是生成的64位 ID 太長(zhǎng)了。賬號(hào)ID希望能控制的盡量短，個(gè)人理解有以下原因：

• 賬號(hào)id一般顯示在個(gè)人設(shè)置里，會(huì)暴露給用戶，需要便于輸入 + 記憶，這樣客服查詢起來(lái)更方便；

• 賬號(hào)id短并且有序能提高賬號(hào)庫(kù)的寫(xiě)入性能；

于是著手改進(jìn)。

改進(jìn)版本

一個(gè)比較可行的方案是利用數(shù)據(jù)庫(kù)的自增 ID 特性。

為了便于理解，我們先來(lái)看一下業(yè)務(wù)里的賬號(hào)登錄流程：

• 客戶端上傳第三方openid及token來(lái)登錄，登錄服拿到openid后需要查詢是否已經(jīng)注冊(cè)賬號(hào)

• 如果能查到賬號(hào)ID，表明已經(jīng)注冊(cè)，再根據(jù)查到的數(shù)字賬號(hào)來(lái)做后續(xù)登錄邏輯

• 如果查不到，則需要新注冊(cè)一個(gè)賬號(hào)到賬號(hào)表

• 新建賬號(hào)首先需要生成一個(gè)數(shù)字的賬號(hào)ID，在目前的機(jī)制中，通過(guò)一張專門(mén)的ID生成表來(lái)做的。

OK，先來(lái)看我們?nèi)绾卧趍ysql中存儲(chǔ)賬號(hào)相關(guān)信息的：

賬號(hào)表，accid就是我們說(shuō)的數(shù)字賬號(hào)。考慮到賬號(hào)數(shù)量級(jí)可能到千萬(wàn)甚至上億，單表的性能肯定不理想，因此我們分了10張表。其表結(jié)構(gòu)為

CREATE TABLE`tbl_global_user_map_00` ( `account`varchar(32) NOTNULL, `accid`bigint(20) NOTNULL, `created_at` datetime DEFAULTNULL,   PRIMARY KEY (`account`) USING BTREE ) ENGINE=InnoDBDEFAULTCHARSET=utf8 

賬號(hào)ID生成表，其表結(jié)構(gòu)為

CREATE TABLE`tbl_accid` ( `id`bigint(20) NOTNULL AUTO_INCREMENT, `stub`char(1) NOTNULLDEFAULT'',   PRIMARY KEY (`id`) USING BTREE, UNIQUEKEY`UQE_tbl_accid_stub` (`stub`) USING BTREE ) ENGINE=InnoDBDEFAULTCHARSET=utf8 

數(shù)據(jù)為

整個(gè)表只有一行數(shù)據(jù)，id列為自增列，它的值就是最新生成的賬號(hào)ID值。這個(gè)ID生成的原理是：

• 設(shè)置id列為自增，這樣每插入一列id值就會(huì)自動(dòng)遞增

• 如果沒(méi)有其他限制，這張表的數(shù)據(jù)就會(huì)隨著insert的次數(shù)越來(lái)越多，假如賬號(hào)有幾千萬(wàn)，這張表就有幾千萬(wàn)行數(shù)據(jù)

• 為此，我們?cè)黾恿艘涣?stub，設(shè)置其為unique key，并且每次insert其值都是一樣的（例如設(shè)置為 'a'），這樣就保證整個(gè)表只有一行數(shù)據(jù)，而id會(huì)隨著每次insert自動(dòng)遞增。

• 如果直接用insert into語(yǔ)句來(lái)做插入，肯定每次都返回錯(cuò)誤（除了第1次），因?yàn)?stub 為 ‘a(chǎn)’ 的記錄已經(jīng)存在了，每次插入都會(huì)失敗。

• 我們改用 MySQL 擴(kuò)展的 SQL 語(yǔ)句replace into來(lái)實(shí)現(xiàn)。replace 必須要配合唯一索引來(lái)使用。

于是 SQL 語(yǔ)句就是

REPLACE INTO tbl_accid(`stub`) VALUES('a');

它的效果如下：

• 如果 stub 為 'a' 的記錄不存在，則插入，類似 insert 操作

• 如果 stub 為 'a' 的記錄已經(jīng)存在，則先 delete 該條記錄，再 insert 新記錄。由于刪除已有的記錄時(shí)，表的自增值不會(huì)變化，再新增記錄時(shí) id 會(huì)在老的自增值基礎(chǔ)上繼續(xù)遞增

有同學(xué)可能要問(wèn)了，為什么要搞一個(gè)單獨(dú)的ID生成表來(lái)生成自增id？將自增字段直接放到賬號(hào)表中不行么？

關(guān)鍵的問(wèn)題在于業(yè)務(wù)要分表。假如賬號(hào)表分了10張，要合并自增id列的話，需要?jiǎng)澐趾妹繌埍淼纳煞秶?/p>

例如我們?cè)O(shè)計(jì)每張表可以生成 100w 個(gè)id，那 10 張表的起始id 分別是 1， 1000001，2000001， ...

跨度非常大，和我們當(dāng)初的設(shè)計(jì)：簡(jiǎn)短并盡量連續(xù)的要求違背。

因此，專門(mén)的賬號(hào)ID生成表是必要的。

問(wèn)題暴露

上述方案完成之后，我就去吃火鍋唱歌去了。

然后，就出現(xiàn)了一個(gè)比較棘手的問(wèn)題。某天晚上QA同事反饋壓力測(cè)試有報(bào)錯(cuò)，登錄服會(huì)間歇性返回db錯(cuò)誤，如下：

ERROR : Deadlock found when trying to get lock; try restarting transaction

登錄服收到該返回后打印了錯(cuò)誤日志，提示客戶端服務(wù)器發(fā)生錯(cuò)誤。很明顯，這個(gè)方案有死鎖問(wèn)題。

google了一下 replace 在并發(fā)情況下的死鎖問(wèn)題，大致和 replace 被分解成 delete + insert 有關(guān)，而 innodb又是行鎖機(jī)制。詳細(xì)的原因非常復(fù)雜，有關(guān)資料為

• https://yq.aliyun.com/articles/41190

• https://techlog.cn/article/list/10183451#l

• http://blog.itpub.net/7728585/viewspace-2141409

很多博客也給出了建議：

通過(guò)幾個(gè)死鎖案例，我們強(qiáng)烈建議在生產(chǎn)環(huán)境中盡量避免使用REPLACE INTO和INSERT INTO ON DUPLICATE UPDATE語(yǔ)句，改用普通INSERT操作，并對(duì)INSER操作部分代碼加入異常加查，當(dāng)INSERT失敗時(shí)改為UPDATE操作。

為了再驗(yàn)證一次死鎖的并非語(yǔ)言或者API的bug，我用了 mysql 自帶的壓測(cè)工具 mysqlslap 做了個(gè)簡(jiǎn)單測(cè)試：

mysqlslap -uroot -p --create-schema="db_global_200" --concurrency=2 --iterations=5 --number-of-queries=500 --query="replace_innodb.sql" mysqlslap: Cannot run query REPLACE INTO tbl_yptest_innodb(`stub`) VALUES('a'); ERROR : Deadlock found when trying to get lock; try restarting transaction

結(jié)果顯示并發(fā)數(shù)為 2 時(shí)就出現(xiàn)了死鎖問(wèn)題。然后我又嘗試將表引擎改為 myisam，再次壓測(cè)，雖然沒(méi)有出現(xiàn)死鎖問(wèn)題，但是MYISAM引擎更新數(shù)據(jù)的效率比較低。因此我們不得不放棄了mysql自增ID的方案，再想其他方案。

繼續(xù)嘗試其他方案。其實(shí)，我們最新的ID生成方案參考了美團(tuán)技術(shù)團(tuán)隊(duì)的一篇文章，有興趣的可以查閱：

https://tech.meituan.com/2017/04/21/mt-leaf.html

文中提到了一種Flickr團(tuán)隊(duì)的改進(jìn)方案：

即：使用 N 個(gè)mysqlserver，來(lái)提高可用性，降低每個(gè)mysqlserver的壓力和并發(fā)數(shù)。如果replace into不支持并發(fā)，那就部署盡可能多的mysqlserver，每次replace into時(shí)串行。

然而這種方式部署限制和消耗都太大，而且我們的登錄服是多開(kāi)的，即使在單登錄服內(nèi)控制串行，多個(gè)進(jìn)程也不好控制，因此這個(gè)初始的方案只能被pass。

回到開(kāi)始的思路，能不能將自增id合并到 賬號(hào)表_xx 中，從而放棄 replace 呢？

我們可以將每個(gè)tbl_global_user_map分表類比成上圖中的mysql-01,mysql-02, ...

然后自增時(shí)，采取 間隔步長(zhǎng)N 的方式（默認(rèn)的自增步長(zhǎng)是1，每次自增加1）

舉例：

• tbl_global_user_map_00表，起始id 20000，每次加10，其生成的 id 每次是 20000, 20010, 20020, 20030...

• tbl_global_user_map_01表，起始id 20001，也是每次加10，其生成的 id 每次是 20001, 20011, 20021, 20031...

這個(gè)id看起來(lái)間隔很小，看起來(lái)非常理想。

需要做的事情就是設(shè)置auto_increment_increment和auto_increment_offset兩個(gè)mysql中的變量。

然后很可惜，這兩個(gè)變量屬于 全局 或者 session（連接會(huì)話） 級(jí)別，沒(méi)有 table 級(jí)別的設(shè)置。

如果我們?cè)O(shè)置了這兩個(gè)變量，很容易影響其他表，產(chǎn)生其他錯(cuò)誤。

其他方案2

再想其他方案。

仔細(xì)整理一下我們的需求，就會(huì)發(fā)現(xiàn)我們的賬號(hào)表一般只有新增，沒(méi)有刪除和修改。能不能利用讀寫(xiě)分離的思想，在插入新映射關(guān)系（同時(shí)生成自增賬號(hào)ID）時(shí)，只有一張表可寫(xiě)，自增id可以每次只加1；

而查詢時(shí)，屬于讀，讀的數(shù)據(jù)可以分布在10張表中。我們要做的就是定期將可寫(xiě)表中已有的一些數(shù)據(jù)遷移到只讀的這10張表中（根據(jù)賬號(hào)ID做shard），控制可寫(xiě)表的數(shù)量級(jí)不能太大。

賬號(hào)ID在寫(xiě)表中自增，相當(dāng)于自動(dòng)分配賬號(hào)ID。

這個(gè)機(jī)制有點(diǎn)類似于我們的日志滾動(dòng)，當(dāng)前正在寫(xiě)的日志文件不停被寫(xiě)入（插入日志），當(dāng)超過(guò)一定大小或者日期切換時(shí)會(huì)滾動(dòng)成只讀的文件。

這個(gè)方案理論上可行，但是有運(yùn)維復(fù)雜性：需要配合運(yùn)維來(lái)做數(shù)據(jù)遷移，維護(hù)成本比較高，因此組內(nèi)討論后我們決定pass掉。

最終方案

我之前所在的成熟項(xiàng)目也用過(guò)上述【其他方案1】中類似美團(tuán)的方案，即預(yù)申請(qǐng)一批ID的方式。

對(duì)比來(lái)看，我們之前申請(qǐng)ID都是一次自增1，而這種預(yù)申請(qǐng)一批的方式，是一次申請(qǐng)N個(gè)ID，自增N，可以減少請(qǐng)求量和并發(fā)。當(dāng)請(qǐng)求量明顯下降后，之前方案里擔(dān)憂的問(wèn)題：ID生成表插入行數(shù)過(guò)多也就不存在了。

唯一的問(wèn)題是：預(yù)申請(qǐng)的ID可能會(huì)被浪費(fèi)。如果申請(qǐng)了一段區(qū)間的id，但是沒(méi)有用完，服務(wù)器停服再啟動(dòng)后會(huì)再申請(qǐng)一段新的，原來(lái)未使用的ID就被浪費(fèi)了。

因此我們著手優(yōu)化這種算法，目的很明顯：減少浪費(fèi)的ID，去除空洞號(hào)段，并自動(dòng)兼容登錄服擴(kuò)容與容災(zāi)的情況。

如果這個(gè)目的能達(dá)成，那就完美契合了我們當(dāng)初的需求。

設(shè)計(jì)發(fā)號(hào)表tbl_account_freeid

每個(gè)登陸服要申請(qǐng)一批賬號(hào)ID時(shí)，就來(lái)表中插入一行，規(guī)定每次申請(qǐng)1000個(gè)，由于segment自增，相當(dāng)于申請(qǐng)了[(segment - 1) * 1000, segment * 1000)這段區(qū)間，申請(qǐng)時(shí)候默認(rèn) left 是 0

登錄服正常停服維護(hù)時(shí)將剩余未用完的數(shù)量寫(xiě)入 left，防止浪費(fèi)，下次啟動(dòng)時(shí)候還可以再利用。

以下分析各種case：

a) 初始tbl_account_freeid沒(méi)有數(shù)據(jù)，假如loginsvr開(kāi)3個(gè)實(shí)例，實(shí)例編號(hào)分別是1，2，3。

服務(wù)器啟動(dòng)時(shí)候需要做一次查找，要找對(duì)應(yīng) 實(shí)例編號(hào)的segment。如果找到了，且 left 不為 0，則說(shuō)明該號(hào)段還可以用；如果找不到，或者left為0，則需要新申請(qǐng)（新插入一行記錄）。

于是第一次啟服后數(shù)據(jù)為

b) 如果loginsvr發(fā)現(xiàn)內(nèi)存中號(hào)段用完了，就不用再查找，直接申請(qǐng)，往數(shù)據(jù)庫(kù)插入一行數(shù)據(jù)，假定實(shí)例編號(hào) 1 和 3 的 號(hào)段用完了，新申請(qǐng)。

然后各個(gè)登錄服正常停服，left 回寫(xiě)?？赡艿臄?shù)據(jù)情況如下：

c) 再次起服時(shí)，查找到各個(gè)編號(hào)的實(shí)例都有號(hào)段可用。無(wú)需新插入數(shù)據(jù)，但是對(duì)應(yīng)的 left 要改為0（相當(dāng)于申請(qǐng)了 left 個(gè)）

d) 如果此時(shí) loginsvr 擴(kuò)容，新增編號(hào) 4 - 10 的 svr，和初始情況類似，需要先查找，沒(méi)有則申請(qǐng)。此時(shí)數(shù)據(jù)可能為

這種方式的特點(diǎn)就是，登錄服服務(wù)過(guò)程中，對(duì)應(yīng)數(shù)據(jù)庫(kù)里的 left 為 0，如果停了，數(shù)據(jù)庫(kù)里 left 為號(hào)段內(nèi)剩余的可用數(shù)量。

如果登錄服宕機(jī)，則沒(méi)有回寫(xiě) left 的過(guò)程，則對(duì)應(yīng)號(hào)段內(nèi)沒(méi)有用完的（最多1000）會(huì)浪費(fèi)。

結(jié)尾

以上就是我們?cè)谫~號(hào)短ID生成上的探索，最終方案經(jīng)歷了長(zhǎng)時(shí)間的生產(chǎn)環(huán)境的測(cè)試，運(yùn)轉(zhuǎn)正常。如果小伙伴們有更優(yōu)秀的經(jīng)驗(yàn)歡迎一起交流。

作者：碼財(cái)同行

來(lái)源：https://juejin.cn/post/7393656776540291087

公眾號(hào)“Java精選”所發(fā)表內(nèi)容注明來(lái)源的，版權(quán)歸原出處所有（無(wú)法查證版權(quán)的或者未注明出處的均來(lái)自網(wǎng)絡(luò)，系轉(zhuǎn)載，轉(zhuǎn)載的目的在于傳遞更多信息，版權(quán)屬于原作者。如有侵權(quán)，請(qǐng)聯(lián)系，筆者會(huì)第一時(shí)間刪除處理！

最近有很多人問(wèn)，有沒(méi)有讀者交流群！加入方式很簡(jiǎn)單，公眾號(hào)Java精選，回復(fù)“加群”，即可入群！

文章有幫助的話，點(diǎn)在看，轉(zhuǎn)發(fā)吧！