---

title: 關(guān)于新版雪花算法的答疑
author: selfishlover
keywords: [Seata, snowflake, UUID, page split]
date: 2021/06/21

本文來(lái)自 Apache Seata官方文檔，歡迎訪問(wèn)官網(wǎng)，查看更多深度文章。

關(guān)于新版雪花算法的答疑

在上一篇關(guān)于新版雪花算法的解析中，我們提到新版算法所做出的2點(diǎn)改變：

1. 時(shí)間戳不再時(shí)刻追隨系統(tǒng)時(shí)鐘。
2. 節(jié)點(diǎn)ID和時(shí)間戳互換位置。由原版的：
   

改成：

有細(xì)心的同學(xué)提出了一個(gè)問(wèn)題：新版算法在單節(jié)點(diǎn)內(nèi)部確實(shí)是單調(diào)遞增的，但是在多實(shí)例部署時(shí)，它就不再是全局單調(diào)遞增了啊！因?yàn)轱@而易見(jiàn)，節(jié)點(diǎn)ID排在高位，那么節(jié)點(diǎn)ID大的，生成的ID一定大于節(jié)點(diǎn)ID小的，不管時(shí)間上誰(shuí)先誰(shuí)后。而原版算法，時(shí)間戳在高位，并且始終追隨系統(tǒng)時(shí)鐘，可以保證早生成的ID小于晚生成的ID，只有當(dāng)2個(gè)節(jié)點(diǎn)恰好在同一時(shí)間戳生成ID時(shí)，2個(gè)ID的大小才由節(jié)點(diǎn)ID決定。這樣看來(lái)，新版算法是不是錯(cuò)的？

這是一個(gè)很好的問(wèn)題！能提出這個(gè)問(wèn)題的同學(xué)，說(shuō)明已經(jīng)深入思考了標(biāo)準(zhǔn)版雪花算法和新版雪花算法的本質(zhì)區(qū)別，這點(diǎn)值得鼓勵(lì)！在這里，我們先說(shuō)結(jié)論：新版算法的確不具備全局的單調(diào)遞增性，但這不影響我們的初衷(減少數(shù)據(jù)庫(kù)的頁(yè)分裂)。這個(gè)結(jié)論看起來(lái)有點(diǎn)違反直覺(jué)，但可以被證明。

在證明之前，我們先簡(jiǎn)單回顧一下數(shù)據(jù)庫(kù)關(guān)于頁(yè)分裂的知識(shí)。以經(jīng)典的mysql innodb為例，innodb使用B+樹索引，其中，主鍵索引的葉子節(jié)點(diǎn)還保存了數(shù)據(jù)行的完整記錄，葉子節(jié)點(diǎn)之間以雙向鏈表的形式串聯(lián)起來(lái)。葉子節(jié)點(diǎn)的物理存儲(chǔ)形式為數(shù)據(jù)頁(yè)，一個(gè)數(shù)據(jù)頁(yè)內(nèi)最多可以存儲(chǔ)N條行記錄(N與行的大小成反比)。如圖所示：

B+樹的特性要求，左邊的節(jié)點(diǎn)應(yīng)小于右邊的節(jié)點(diǎn)。如果此時(shí)要插入一條ID為25的記錄，會(huì)怎樣呢(假設(shè)每個(gè)數(shù)據(jù)頁(yè)只夠存放4條記錄)？答案是會(huì)引起頁(yè)分裂，如圖：

頁(yè)分裂是IO不友好的，需要新建數(shù)據(jù)頁(yè)，拷貝轉(zhuǎn)移舊數(shù)據(jù)頁(yè)的部分記錄等，我們應(yīng)盡量避免。

理想的情況下，主鍵ID最好是順序遞增的(例如把主鍵設(shè)置為auto_increment)，這樣就只會(huì)在當(dāng)前數(shù)據(jù)頁(yè)放滿了的時(shí)候，才需要新建下一頁(yè)，雙向鏈表永遠(yuǎn)是順序尾部增長(zhǎng)的，不會(huì)有中間的節(jié)點(diǎn)發(fā)生分裂的情況。

最糟糕的情況下，主鍵ID是隨機(jī)無(wú)序生成的(例如java中一個(gè)UUID字符串)，這種情況下，新插入的記錄會(huì)隨機(jī)分配到任何一個(gè)數(shù)據(jù)頁(yè)，如果該頁(yè)已滿，就會(huì)觸發(fā)頁(yè)分裂。

如果主鍵ID由標(biāo)準(zhǔn)版雪花算法生成，最好的情況下，是每個(gè)時(shí)間戳內(nèi)只有一個(gè)節(jié)點(diǎn)在生成ID，這時(shí)候算法的效果等同于理想情況的順序遞增，即跟auto_increment無(wú)差。最壞的情況下，是每個(gè)時(shí)間戳內(nèi)所有節(jié)點(diǎn)都在生成ID，這時(shí)候算法的效果接近于無(wú)序(但仍比UUID的完全無(wú)序要好得多，因?yàn)閣orkerId只有10位決定了最多只有1024個(gè)節(jié)點(diǎn))。實(shí)際生產(chǎn)中，算法的效果取決于業(yè)務(wù)流量，并發(fā)度越低，算法越接近理想情況。

那么，換成新版算法又會(huì)如何呢？
新版算法從全局角度來(lái)看，ID是無(wú)序的，但對(duì)于每一個(gè)workerId，它生成的ID都是嚴(yán)格單調(diào)遞增的，又因?yàn)閣orkerId是有限的，所以最多可劃分出1024個(gè)子序列，每個(gè)子序列都是單調(diào)遞增的。
對(duì)于數(shù)據(jù)庫(kù)而言，也許它初期接收的ID都是無(wú)序的，來(lái)自各個(gè)子序列的ID都混在一起，就像這樣：

如果這時(shí)候來(lái)了個(gè)worker1-seq2，顯然會(huì)造成頁(yè)分裂：

但分裂之后，有趣的事情發(fā)生了，對(duì)于worker1而言，后續(xù)的seq3，seq4不會(huì)再造成頁(yè)分裂(因?yàn)檫€裝得下)，seq5也只需要像順序增長(zhǎng)那樣新建頁(yè)進(jìn)行鏈接(區(qū)別是這個(gè)新頁(yè)不是在雙向鏈表的尾部)。注意，worker1的后續(xù)ID，不會(huì)排到worker2及之后的任意節(jié)點(diǎn)(因而不會(huì)造成后邊節(jié)點(diǎn)的頁(yè)分裂)，因?yàn)樗鼈兛偙葁orker2的ID小；也不會(huì)排到worker1當(dāng)前節(jié)點(diǎn)的前邊(因而不會(huì)造成前邊節(jié)點(diǎn)的頁(yè)分裂)，因?yàn)閣orker1的子序列總是單調(diào)遞增的。在這里，我們稱worker1這樣的子序列達(dá)到了穩(wěn)態(tài)，意為這條子序列已經(jīng)"穩(wěn)定"了，它的后續(xù)增長(zhǎng)只會(huì)出現(xiàn)在子序列的尾部，而不會(huì)造成其它節(jié)點(diǎn)的頁(yè)分裂。

同樣的事情，可以推廣到各個(gè)子序列上。無(wú)論前期數(shù)據(jù)庫(kù)接收到的ID有多亂，經(jīng)過(guò)有限次的頁(yè)分裂后，雙向鏈表總能達(dá)到這樣一個(gè)穩(wěn)定的終態(tài)：

到達(dá)終態(tài)后，后續(xù)的ID只會(huì)在該ID所屬的子序列上進(jìn)行順序增長(zhǎng)，而不會(huì)造成頁(yè)分裂。該狀態(tài)下的順序增長(zhǎng)與auto_increment的順序增長(zhǎng)的區(qū)別是，前者有1024個(gè)增長(zhǎng)位點(diǎn)(各個(gè)子序列的尾部)，后者只有尾部一個(gè)。

到這里，我們可以回答開頭所提出的問(wèn)題了：新算法從全局來(lái)看的確不是全局遞增的，但該算法是收斂的，達(dá)到穩(wěn)態(tài)后，新算法同樣能達(dá)成像全局順序遞增一樣的效果。

---

擴(kuò)展思考

以上只提到了序列不停增長(zhǎng)的情況，而實(shí)踐生產(chǎn)中，不光有新數(shù)據(jù)的插入，也有舊數(shù)據(jù)的刪除。而數(shù)據(jù)的刪除有可能會(huì)導(dǎo)致頁(yè)合并(innodb若發(fā)現(xiàn)相鄰2個(gè)數(shù)據(jù)頁(yè)的空間利用率都不到50%，就會(huì)把它倆合并)，這對(duì)新算法的影響如何呢？

經(jīng)過(guò)上面的流程，我們可以發(fā)現(xiàn)，新算法的本質(zhì)是利用前期的頁(yè)分裂，把不同的子序列逐漸分離開來(lái)，讓算法不斷收斂到穩(wěn)態(tài)。而頁(yè)合并則恰好相反，它有可能會(huì)把不同的子序列又合并回同一個(gè)數(shù)據(jù)頁(yè)里，妨礙算法的收斂。尤其是在收斂的前期，頻繁的頁(yè)合并甚至可以讓算法永遠(yuǎn)無(wú)法收斂(你剛分離出來(lái)我就又把它們合并回去，一夜回到解放前~)！但在收斂之后，只有在各個(gè)子序列的尾節(jié)點(diǎn)進(jìn)行的頁(yè)合并，才有可能破壞穩(wěn)態(tài)(一個(gè)子序列的尾節(jié)點(diǎn)和下一個(gè)子序列的頭節(jié)點(diǎn)進(jìn)行合并)。而在子序列其余節(jié)點(diǎn)上的頁(yè)合并，不影響穩(wěn)態(tài)，因?yàn)樽有蛄腥匀皇怯行虻?#xff0c;只不過(guò)長(zhǎng)度變短了而已。

以seata的服務(wù)端為例，服務(wù)端那3張表的數(shù)據(jù)的生命周期都是比較短的，一個(gè)全局事務(wù)結(jié)束之后，它們就會(huì)被清除了，這對(duì)于新算法是不友好的，沒(méi)有給時(shí)間它進(jìn)行收斂。不過(guò)已經(jīng)有延遲刪除的PR在review中，搭配這個(gè)PR，效果會(huì)好很多。比如定期每周清理一次，前期就有足夠的時(shí)間給算法進(jìn)行收斂，其余的大部分時(shí)間，數(shù)據(jù)庫(kù)就能從中受益了。到期清理時(shí)，最壞的結(jié)果也不過(guò)是表被清空，算法從頭再來(lái)。

如果您希望把新算法應(yīng)用到業(yè)務(wù)系統(tǒng)當(dāng)中，請(qǐng)務(wù)必確保算法有時(shí)間進(jìn)行收斂。比如用戶表之類的，數(shù)據(jù)本就打算長(zhǎng)期保存的，算法可以自然收斂。或者也做了延遲刪除的機(jī)制，給算法足夠的時(shí)間進(jìn)行收斂。

如果您有更好的意見(jiàn)和建議，也歡迎跟seata社區(qū)聯(lián)系！