一、需求緣起

幾乎所有的業(yè)務(wù)系統(tǒng)，都有生成一個記錄標(biāo)識的需求，例如：

(1)消息標(biāo)識：message-id

(2)訂單標(biāo)識：order-id

(3)帖子標(biāo)識：tiezi-id

這個記錄標(biāo)識往往就是數(shù)據(jù)庫中的唯一主鍵，數(shù)據(jù)庫上會建立聚集索引(cluster index)，即在物理存儲上以這個字段排序。

這個記錄標(biāo)識上的查詢，往往又有分頁或者排序的業(yè)務(wù)需求，例如：

(1)拉取***的一頁消息：selectmessage-id/ order by time/ limit 100

(2)拉取***的一頁訂單：selectorder-id/ order by time/ limit 100

(3)拉取***的一頁帖子：selecttiezi-id/ order by time/ limit 100

所以往往要有一個time字段，并且在time字段上建立普通索引(non-cluster index)。

我們都知道普通索引存儲的是實(shí)際記錄的指針，其訪問效率會比聚集索引慢，如果記錄標(biāo)識在生成時能夠基本按照時間有序，則可以省去這個time字段的索引查詢：

select message-id/ (order by message-id)/limit 100

再次強(qiáng)調(diào)，能這么做的前提是，message-id的生成基本是趨勢時間遞增的。

這就引出了記錄標(biāo)識生成(也就是上文提到的三個XXX-id)的兩大核心需求：

(1)全局唯一

(2)趨勢有序

這也是本文要討論的核心問題：如何高效生成趨勢有序的全局唯一ID。

二、常見方法、不足與優(yōu)化

【常見方法一：使用數(shù)據(jù)庫的 auto_increment 來生成全局唯一遞增ID】

優(yōu)點(diǎn)：

(1)簡單，使用數(shù)據(jù)庫已有的功能

(2)能夠保證唯一性

(3)能夠保證遞增性

(4)步長固定

缺點(diǎn)：

(1)可用性難以保證：數(shù)據(jù)庫常見架構(gòu)是一主多從+讀寫分離，生成自增ID是寫請求，主庫掛了就玩不轉(zhuǎn)了

(2)擴(kuò)展性差，性能有上限：因?yàn)閷懭胧菃吸c(diǎn)，數(shù)據(jù)庫主庫的寫性能決定ID的生成性能上限，并且難以擴(kuò)展

改進(jìn)方法：

(1)增加主庫，避免寫入單點(diǎn)

(2)數(shù)據(jù)水平切分，保證各主庫生成的ID不重復(fù)

如上圖所述，由1個寫庫變成3個寫庫，每個寫庫設(shè)置不同的auto_increment初始值，以及相同的增長步長，以保證每個數(shù)據(jù)庫生成的ID是不同的(上圖中庫0生成0,3,6,9…，庫1生成1,4,7,10，庫2生成2,5,8,11…)

改進(jìn)后的架構(gòu)保證了可用性，但缺點(diǎn)是：

(1)喪失了ID生成的“絕對遞增性”：先訪問庫0生成0,3，再訪問庫1生成1，可能導(dǎo)致在非常短的時間內(nèi)，ID生成不是絕對遞增的(這個問題不大，我們的目標(biāo)是趨勢遞增，不是絕對遞增)

(2)數(shù)據(jù)庫的寫壓力依然很大，每次生成ID都要訪問數(shù)據(jù)庫

為了解決上述兩個問題，引出了第二個常見的方案

【常見方法二：單點(diǎn)批量ID生成服務(wù)】

分布式系統(tǒng)之所以難，很重要的原因之一是“沒有一個全局時鐘，難以保證絕對的時序”，要想保證絕對的時序，還是只能使用單點(diǎn)服務(wù)，用本地時鐘保證“絕對時序”。數(shù)據(jù)庫寫壓力大，是因?yàn)槊看紊蒊D都訪問了數(shù)據(jù)庫，可以使用批量的方式降低數(shù)據(jù)庫寫壓力。

如上圖所述，數(shù)據(jù)庫使用雙master保證可用性，數(shù)據(jù)庫中只存儲當(dāng)前ID的***值，例如0。ID生成服務(wù)假設(shè)每次批量拉取6個ID，服務(wù)訪問數(shù)據(jù)庫，將當(dāng)前ID的***值修改為5，這樣應(yīng)用訪問ID生成服務(wù)索要ID，ID生成服務(wù)不需要每次訪問數(shù)據(jù)庫，就能依次派發(fā)0,1,2,3,4,5這些ID了，當(dāng)ID發(fā)完后，再將ID的***值修改為11，就能再次派發(fā)6,7,8,9,10,11這些ID了，于是數(shù)據(jù)庫的壓力就降低到原來的1/6了。

優(yōu)點(diǎn)：

(1)保證了ID生成的絕對遞增有序

(2)大大的降低了數(shù)據(jù)庫的壓力，ID生成可以做到每秒生成幾萬幾十萬個

缺點(diǎn)：

(1)服務(wù)仍然是單點(diǎn)

(2)如果服務(wù)掛了，服務(wù)重啟起來之后，繼續(xù)生成ID可能會不連續(xù)，中間出現(xiàn)空洞(服務(wù)內(nèi)存是保存著0,1,2,3,4,5，數(shù)據(jù)庫中max-id是5，分配到3時，服務(wù)重啟了，下次會從6開始分配，4和5就成了空洞，不過這個問題也不大)

(3)雖然每秒可以生成幾萬幾十萬個ID，但畢竟還是有性能上限，無法進(jìn)行水平擴(kuò)展

改進(jìn)方法：

單點(diǎn)服務(wù)的常用高可用優(yōu)化方案是“備用服務(wù)”，也叫“影子服務(wù)”，所以我們能用以下方法優(yōu)化上述缺點(diǎn)(1)：

如上圖，對外提供的服務(wù)是主服務(wù)，有一個影子服務(wù)時刻處于備用狀態(tài)，當(dāng)主服務(wù)掛了的時候影子服務(wù)頂上。這個切換的過程對調(diào)用方是透明的，可以自動完成，常用的技術(shù)是vip+keepalived，具體就不在這里展開。

【常見方法三：uuid】

上述方案來生成ID，雖然性能大增，但由于是單點(diǎn)系統(tǒng)，總還是存在性能上限的。同時，上述兩種方案，不管是數(shù)據(jù)庫還是服務(wù)來生成ID，業(yè)務(wù)方Application都需要進(jìn)行一次遠(yuǎn)程調(diào)用，比較耗時。有沒有一種本地生成ID的方法，即高性能，又時延低呢?

uuid是一種常見的方案：string ID =GenUUID();

優(yōu)點(diǎn)：

(1)本地生成ID，不需要進(jìn)行遠(yuǎn)程調(diào)用，時延低

(2)擴(kuò)展性好，基本可以認(rèn)為沒有性能上限

缺點(diǎn)：

(1)無法保證趨勢遞增

(2)uuid過長，往往用字符串表示，作為主鍵建立索引查詢效率低，常見優(yōu)化方案為“轉(zhuǎn)化為兩個uint64整數(shù)存儲”或者“折半存儲”(折半后不能保證唯一性)

【常見方法四：取當(dāng)前毫秒數(shù)】

uuid是一個本地算法，生成性能高，但無法保證趨勢遞增，且作為字符串ID檢索效率低，有沒有一種能保證遞增的本地算法呢?

取當(dāng)前毫秒數(shù)是一種常見方案：uint64 ID = GenTimeMS();

優(yōu)點(diǎn)：

(1)本地生成ID，不需要進(jìn)行遠(yuǎn)程調(diào)用，時延低

(2)生成的ID趨勢遞增

(3)生成的ID是整數(shù)，建立索引后查詢效率高

缺點(diǎn)：

(1)如果并發(fā)量超過1000，會生成重復(fù)的ID

我去，這個缺點(diǎn)要了命了，不能保證ID的唯一性。當(dāng)然，使用微秒可以降低沖突概率，但每秒最多只能生成1000000個ID，再多的話就一定會沖突了，所以使用微秒并不從根本上解決問題。

【常見方法五：類snowflake算法】

snowflake是twitter開源的分布式ID生成算法，其核心思想是：一個long型的ID，使用其中41bit作為毫秒數(shù)，10bit作為機(jī)器編號，12bit作為毫秒內(nèi)序列號。這個算法單機(jī)每秒內(nèi)理論上最多可以生成1000*(2^12)，也就是400W的ID，完全能滿足業(yè)務(wù)的需求。

借鑒snowflake的思想，結(jié)合各公司的業(yè)務(wù)邏輯和并發(fā)量，可以實(shí)現(xiàn)自己的分布式ID生成算法。

舉例，假設(shè)某公司ID生成器服務(wù)的需求如下：

(1)單機(jī)高峰并發(fā)量小于1W，預(yù)計(jì)未來5年單機(jī)高峰并發(fā)量小于10W

(2)有2個機(jī)房，預(yù)計(jì)未來5年機(jī)房數(shù)量小于4個

(3)每個機(jī)房機(jī)器數(shù)小于100臺

(4)目前有5個業(yè)務(wù)線有ID生成需求，預(yù)計(jì)未來業(yè)務(wù)線數(shù)量小于10個

(5)…

分析過程如下：

(1)高位取從2016年1月1日到現(xiàn)在的毫秒數(shù)(假設(shè)系統(tǒng)ID生成器服務(wù)在這個時間之后上線)，假設(shè)系統(tǒng)至少運(yùn)行10年，那至少需要10年*365天*24小時*3600秒*1000毫秒=320*10^9，差不多預(yù)留39bit給毫秒數(shù)

(2)每秒的單機(jī)高峰并發(fā)量小于10W，即平均每毫秒的單機(jī)高峰并發(fā)量小于100，差不多預(yù)留7bit給每毫秒內(nèi)序列號

(3)5年內(nèi)機(jī)房數(shù)小于4個，預(yù)留2bit給機(jī)房標(biāo)識

(4)每個機(jī)房小于100臺機(jī)器，預(yù)留7bit給每個機(jī)房內(nèi)的服務(wù)器標(biāo)識

(5)業(yè)務(wù)線小于10個，預(yù)留4bit給業(yè)務(wù)線標(biāo)識

這樣設(shè)計(jì)的64bit標(biāo)識，可以保證：

(1)每個業(yè)務(wù)線、每個機(jī)房、每個機(jī)器生成的ID都是不同的

(2)同一個機(jī)器，每個毫秒內(nèi)生成的ID都是不同的

(3)同一個機(jī)器，同一個毫秒內(nèi)，以序列號區(qū)區(qū)分保證生成的ID是不同的

(4)將毫秒數(shù)放在***位，保證生成的ID是趨勢遞增的

缺點(diǎn)：

(1)由于“沒有一個全局時鐘”，每臺服務(wù)器分配的ID是絕對遞增的，但從全局看，生成的ID只是趨勢遞增的(有些服務(wù)器的時間早，有些服務(wù)器的時間晚)

***一個容易忽略的問題：

生成的ID，例如message-id/ order-id/ tiezi-id，在數(shù)據(jù)量大時往往需要分庫分表，這些ID經(jīng)常作為取模分庫分表的依據(jù)，為了分庫分表后數(shù)據(jù)均勻，ID生成往往有“取模隨機(jī)性”的需求，所以我們通常把每秒內(nèi)的序列號放在ID的最末位，保證生成的ID是隨機(jī)的。

又如果，我們在跨毫秒時，序列號總是歸0，會使得序列號為0的ID比較多，導(dǎo)致生成的ID取模后不均勻。解決方法是，序列號不是每次都?xì)w0，而是歸一個0到9的隨機(jī)數(shù)，這個地方。

【本文為51CTO專欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請聯(lián)系原作者】