一、需求緣起
幾乎所有的業(yè)務(wù)系統(tǒng)，都有生成一個(gè)唯一記錄標(biāo)識(shí)的需求，例如：
-
消息標(biāo)識(shí)：message-id
-
訂單標(biāo)識(shí)：order-id
-
帖子標(biāo)識(shí)：tiezi-id
這個(gè)記錄標(biāo)識(shí)往往就是數(shù)據(jù)庫(kù)中的主鍵，數(shù)據(jù)庫(kù)上會(huì)建立聚集索引（cluster index），即在物理存儲(chǔ)上以這個(gè)字段排序。
這個(gè)記錄標(biāo)識(shí)上的查詢，往往又有分頁(yè)或者排序的業(yè)務(wù)需求，例如：
-
拉取最新的一頁(yè)消息
select message-id/ order by time/ limit 100
-
拉取最新的一頁(yè)訂單
select order-id/ order by time/ limit 100
-
拉取最新的一頁(yè)帖子
select tiezi-id/ order by time/ limit 100
所以往往要有一個(gè)time字段，并且在time字段上建立普通索引（non-cluster index）。
普通索引存儲(chǔ)的是實(shí)際記錄的指針，其訪問(wèn)效率會(huì)比聚集索引慢，如果記錄標(biāo)識(shí)在生成時(shí)能夠基本按照時(shí)間有序，則可以省去這個(gè)time字段的索引查詢：
select message-id/ (order by message-id)/limit 100
強(qiáng)調(diào)，能這么做的前提是，message-id的生成基本是趨勢(shì)時(shí)間遞增的。
這就引出了記錄標(biāo)識(shí)生成（也就是上文提到的三個(gè)XXX-id）的兩大核心需求：
-
全局唯一
-
趨勢(shì)有序
這也是本文要討論的核心問(wèn)題：如何高效生成趨勢(shì)有序的全局唯一ID。
二、常見(jiàn)方法、不足與優(yōu)化
方法一：使用數(shù)據(jù)庫(kù)的 auto_increment 來(lái)生成全局唯一遞增ID
優(yōu)點(diǎn)：
-
簡(jiǎn)單，使用數(shù)據(jù)庫(kù)已有的功能
-
能夠保證唯一性
-
能夠保證遞增性
-
步長(zhǎng)固定
缺點(diǎn)：
-
可用性難以保證：數(shù)據(jù)庫(kù)常見(jiàn)架構(gòu)是一主多從+讀寫分離，生成自增ID是寫請(qǐng)求，主庫(kù)掛了就玩不轉(zhuǎn)了
-
擴(kuò)展性差，性能有上限：因?yàn)閷懭胧菃吸c(diǎn)，數(shù)據(jù)庫(kù)主庫(kù)的寫性能決定ID的生成性能上限，并且難以擴(kuò)展
改進(jìn)方法：
-
冗余主庫(kù)，避免寫入單點(diǎn)
-
數(shù)據(jù)水平切分，保證各主庫(kù)生成的ID不重復(fù)
如上圖所述，由1個(gè)寫庫(kù)變成3個(gè)寫庫(kù)，每個(gè)寫庫(kù)設(shè)置不同的auto_increment初始值，以及相同的增長(zhǎng)步長(zhǎng)，以保證每個(gè)數(shù)據(jù)庫(kù)生成的ID是不同的（上圖中庫(kù)0生成0,3,6,9…，庫(kù)1生成1,4,7,10，庫(kù)2生成2,5,8,11…）
改進(jìn)后的架構(gòu)保證了可用性，但缺點(diǎn)是：
-
喪失了ID生成的“絕對(duì)遞增性”：先訪問(wèn)庫(kù)0生成0,3，再訪問(wèn)庫(kù)1生成1，可能導(dǎo)致在非常短的時(shí)間內(nèi)，ID生成不是絕對(duì)遞增的（這個(gè)問(wèn)題不大，目標(biāo)是趨勢(shì)遞增，不是絕對(duì)遞增）
-
數(shù)據(jù)庫(kù)的寫壓力依然很大，每次生成ID都要訪問(wèn)數(shù)據(jù)庫(kù)
為了解決上述兩個(gè)問(wèn)題，引出了第二個(gè)常見(jiàn)的方案。
方法二：?jiǎn)吸c(diǎn)批量ID生成服務(wù)
分布式系統(tǒng)之所以難，很重要的原因之一是“沒(méi)有一個(gè)全局時(shí)鐘，難以保證絕對(duì)的時(shí)序”，要想保證絕對(duì)的時(shí)序，還是只能使用單點(diǎn)服務(wù)，用本地時(shí)鐘保證“絕對(duì)時(shí)序”。
數(shù)據(jù)庫(kù)寫壓力大，是因?yàn)槊看紊?/span>ID都訪問(wèn)了數(shù)據(jù)庫(kù)，可以使用批量的方式降低數(shù)據(jù)庫(kù)寫壓力。
如上圖所述，數(shù)據(jù)庫(kù)使用雙master保證可用性，數(shù)據(jù)庫(kù)中只存儲(chǔ)當(dāng)前ID的最大值，例如0。
ID生成服務(wù)假設(shè)每次批量拉取6個(gè)ID，服務(wù)訪問(wèn)數(shù)據(jù)庫(kù)，將當(dāng)前ID的最大值修改為5，這樣應(yīng)用訪問(wèn)ID生成服務(wù)索要ID，ID生成服務(wù)不需要每次訪問(wèn)數(shù)據(jù)庫(kù)，就能依次派發(fā)0,1,2,3,4,5這些ID了。
當(dāng)ID發(fā)完后，再將ID的最大值修改為11，就能再次派發(fā)6,7,8,9,10,11這些ID了，于是數(shù)據(jù)庫(kù)的壓力就降低到原來(lái)的1/6。
優(yōu)點(diǎn)：
-
保證了ID生成的絕對(duì)遞增有序
-
大大的降低了數(shù)據(jù)庫(kù)的壓力，ID生成可以做到每秒生成幾萬(wàn)幾十萬(wàn)個(gè)
缺點(diǎn)：
-
服務(wù)仍然是單點(diǎn)
-
如果服務(wù)掛了，服務(wù)重啟起來(lái)之后，繼續(xù)生成ID可能會(huì)不連續(xù)，中間出現(xiàn)空洞（服務(wù)內(nèi)存是保存著0,1,2,3,4,5，數(shù)據(jù)庫(kù)中max-id是5，分配到3時(shí)，服務(wù)重啟了，下次會(huì)從6開(kāi)始分配，4和5就成了空洞，不過(guò)這個(gè)問(wèn)題也不大）
-
雖然每秒可以生成幾萬(wàn)幾十萬(wàn)個(gè)ID，但畢竟還是有性能上限，無(wú)法進(jìn)行水平擴(kuò)展
改進(jìn)方法：
單點(diǎn)服務(wù)的常用高可用優(yōu)化方案是“備用服務(wù)”，也叫“影子服務(wù)”，所以我們能用以下方法優(yōu)化上述缺點(diǎn)（1）：
如上圖，對(duì)外提供的服務(wù)是主服務(wù)，有一個(gè)影子服務(wù)時(shí)刻處于備用狀態(tài)，當(dāng)主服務(wù)掛了的時(shí)候影子服務(wù)頂上。
這個(gè)切換的過(guò)程對(duì)調(diào)用方是透明的，可以自動(dòng)完成，常用的技術(shù)是vip+keepalived，具體就不在這里展開(kāi)。
另外，ID-gen-service也可以實(shí)施水平擴(kuò)展，以解決上述缺點(diǎn)（3），但會(huì)引發(fā)一致性問(wèn)題，具體解決方案詳見(jiàn)《淺談CAS在分布式ID生成方案上的應(yīng)用》。
方法三：uuid/guid
不管是通過(guò)數(shù)據(jù)庫(kù)，還是通過(guò)服務(wù)來(lái)生成ID，業(yè)務(wù)方Application都需要進(jìn)行一次遠(yuǎn)程調(diào)用，比較耗時(shí)。
有沒(méi)有一種本地生成ID的方法，即高性能，又時(shí)延低呢？
uuid是一種常見(jiàn)的方案：
string ID =GenUUID();
優(yōu)點(diǎn)：
-
本地生成ID，不需要進(jìn)行遠(yuǎn)程調(diào)用，時(shí)延低
-
擴(kuò)展性好，基本可以認(rèn)為沒(méi)有性能上限
缺點(diǎn)：
-
無(wú)法保證趨勢(shì)遞增
-
uuid過(guò)長(zhǎng)，往往用字符串表示，作為主鍵建立索引查詢效率低，常見(jiàn)優(yōu)化方案為“轉(zhuǎn)化為兩個(gè)uint64整數(shù)存儲(chǔ)”或者“折半存儲(chǔ)”（折半后不能保證唯一性）
方法四：取當(dāng)前毫秒數(shù)
uuid是一個(gè)本地算法，生成性能高，但無(wú)法保證趨勢(shì)遞增，且作為字符串ID檢索效率低，有沒(méi)有一種能保證遞增的本地算法呢？
取當(dāng)前毫秒數(shù)是一種常見(jiàn)方案：
uint64 ID = GenTimeMS();
優(yōu)點(diǎn)：
-
本地生成ID，不需要進(jìn)行遠(yuǎn)程調(diào)用，時(shí)延低
-
生成的ID趨勢(shì)遞增
-
生成的ID是整數(shù)，建立索引后查詢效率高
缺點(diǎn)：
-
如果并發(fā)量超過(guò)1000，會(huì)生成重復(fù)的ID
這個(gè)缺點(diǎn)要了命了，不能保證ID的唯一性。當(dāng)然，使用微秒可以降低沖突概率，但每秒最多只能生成1000000個(gè)ID，再多的話就一定會(huì)沖突了，所以使用微秒并不從根本上解決問(wèn)題。
方法五：類snowflake算法
snowflake是twitter開(kāi)源的分布式ID生成算法，其核心思想為，一個(gè)long型的ID：
-
41bit作為毫秒數(shù)
-
10bit作為機(jī)器編號(hào)
-
12bit作為毫秒內(nèi)序列號(hào)
算法單機(jī)每秒內(nèi)理論上最多可以生成1000*(2^12)，也就是400W的ID，完全能滿足業(yè)務(wù)的需求。
借鑒snowflake的思想，結(jié)合各公司的業(yè)務(wù)邏輯和并發(fā)量，可以實(shí)現(xiàn)自己的分布式ID生成算法。
舉例，假設(shè)某公司ID生成器服務(wù)的需求如下：
-
單機(jī)高峰并發(fā)量小于1W，預(yù)計(jì)未來(lái)5年單機(jī)高峰并發(fā)量小于10W
-
有2個(gè)機(jī)房，預(yù)計(jì)未來(lái)5年機(jī)房數(shù)量小于4個(gè)
-
每個(gè)機(jī)房機(jī)器數(shù)小于100臺(tái)
-
目前有5個(gè)業(yè)務(wù)線有ID生成需求，預(yù)計(jì)未來(lái)業(yè)務(wù)線數(shù)量小于10個(gè)
-
…
分析過(guò)程如下：
-
高位取從2017年1月1日到現(xiàn)在的毫秒數(shù)（假設(shè)系統(tǒng)ID生成器服務(wù)在這個(gè)時(shí)間之后上線），假設(shè)系統(tǒng)至少運(yùn)行10年，那至少需要10年*365天*24小時(shí)*3600秒*1000毫秒=320*10^9，差不多預(yù)留39bit給毫秒數(shù)
-
每秒的單機(jī)高峰并發(fā)量小于10W，即平均每毫秒的單機(jī)高峰并發(fā)量小于100，差不多預(yù)留7bit給每毫秒內(nèi)序列號(hào)
-
5年內(nèi)機(jī)房數(shù)小于4個(gè)，預(yù)留2bit給機(jī)房標(biāo)識(shí)
-
每個(gè)機(jī)房小于100臺(tái)機(jī)器，預(yù)留7bit給每個(gè)機(jī)房?jī)?nèi)的服務(wù)器標(biāo)識(shí)
-
業(yè)務(wù)線小于10個(gè)，預(yù)留4bit給業(yè)務(wù)線標(biāo)識(shí)
這樣設(shè)計(jì)的64bit標(biāo)識(shí)，可以保證：
-
每個(gè)業(yè)務(wù)線、每個(gè)機(jī)房、每個(gè)機(jī)器生成的ID都是不同的
-
同一個(gè)機(jī)器，每個(gè)毫秒內(nèi)生成的ID都是不同的
-
同一個(gè)機(jī)器，同一個(gè)毫秒內(nèi)，以序列號(hào)區(qū)區(qū)分保證生成的ID是不同的
-
將毫秒數(shù)放在最高位，保證生成的ID是趨勢(shì)遞增的
缺點(diǎn)：
-
由于“沒(méi)有一個(gè)全局時(shí)鐘”，每臺(tái)服務(wù)器分配的ID是絕對(duì)遞增的，但從全局看，生成的ID只是趨勢(shì)遞增的（有些服務(wù)器的時(shí)間早，有些服務(wù)器的時(shí)間晚）
