轉(zhuǎn)載:細(xì)聊分布式ID生成方法
一似谁、需求緣起
幾乎所有的業(yè)務(wù)系統(tǒng)胁勺，都有生成一個(gè)記錄標(biāo)識(shí)的需求檐晕，例如：
（1）消息標(biāo)識(shí)：message-id
（2）訂單標(biāo)識(shí)：order-id
（3）帖子標(biāo)識(shí)：tiezi-id
這個(gè)記錄標(biāo)識(shí)往往就是數(shù)據(jù)庫中的唯一主鍵仇箱，數(shù)據(jù)庫上會(huì)建立聚集索引（cluster index）奖唯，即在物理存儲(chǔ)上以這個(gè)字段排序惨缆。
這個(gè)記錄標(biāo)識(shí)上的查詢，往往又有分頁或者排序的業(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
所以往往要有一個(gè)time字段坯墨，并且在time字段上建立普通索引（non-cluster index）。
我們都知道普通索引存儲(chǔ)的是實(shí)際記錄的指針病往，其訪問效率會(huì)比聚集索引慢捣染，如果記錄標(biāo)識(shí)在生成時(shí)能夠基本按照時(shí)間有序，則可以省去這個(gè)time字段的索引查詢：
select message-id/ (order by message-id)/limit 100
再次強(qiáng)調(diào)停巷，能這么做的前提是耍攘，message-id的生成基本是趨勢時(shí)間遞增的榕栏。
這就引出了記錄標(biāo)識(shí)生成（也就是上文提到的三個(gè)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個(gè)寫庫變成3個(gè)寫庫，每個(gè)寫庫設(shè)置不同的auto_increment初始值卖氨，以及相同的增長步長会烙，以保證每個(gè)數(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)致在非常短的時(shí)間內(nèi)五嫂，ID生成不是絕對遞增的（這個(gè)問題不大，我們的目標(biāo)是趨勢遞增肯尺，不是絕對遞增）
（2）數(shù)據(jù)庫的寫壓力依然很大沃缘，每次生成ID都要訪問數(shù)據(jù)庫
為了解決上述兩個(gè)問題，引出了第二個(gè)常見的方案
【常見方法二：單點(diǎn)批量ID生成服務(wù)】
分布式系統(tǒng)之所以難则吟，很重要的原因之一是“沒有一個(gè)全局時(shí)鐘槐臀，難以保證絕對的時(shí)序”，要想保證絕對的時(shí)序氓仲，還是只能使用單點(diǎn)服務(wù)水慨，用本地時(shí)鐘保證“絕對時(shí)序”。數(shù)據(jù)庫寫壓力大敬扛，是因?yàn)槊看紊蒊D都訪問了數(shù)據(jù)庫晰洒，可以使用批量的方式降低數(shù)據(jù)庫寫壓力。
如上圖所述舔哪，數(shù)據(jù)庫使用雙master保證可用性欢顷，數(shù)據(jù)庫中只存儲(chǔ)當(dāng)前ID的最大值槽棍，例如0捉蚤。ID生成服務(wù)假設(shè)每次批量拉取6個(gè)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生成可以做到每秒生成幾萬幾十萬個(gè)
缺點(diǎn)：
（1）服務(wù)仍然是單點(diǎn)
（2）如果服務(wù)掛了拼岳，服務(wù)重啟起來之后枝誊，繼續(xù)生成ID可能會(huì)不連續(xù)，中間出現(xiàn)空洞（服務(wù)內(nèi)存是保存著0,1,2,3,4,5惜纸，數(shù)據(jù)庫中max-id是5叶撒，分配到3時(shí)，服務(wù)重啟了耐版，下次會(huì)從6開始分配祠够，4和5就成了空洞，不過這個(gè)問題也不大）
（3）雖然每秒可以生成幾萬幾十萬個(gè)ID粪牲，但畢竟還是有性能上限古瓤，無法進(jìn)行水平擴(kuò)展
改進(jìn)方法：
單點(diǎn)服務(wù)的常用高可用優(yōu)化方案是“備用服務(wù)”，也叫“影子服務(wù)”腺阳，所以我們能用以下方法優(yōu)化上述缺點(diǎn)（1）：
如上圖湿滓，對外提供的服務(wù)是主服務(wù)，有一個(gè)影子服務(wù)時(shí)刻處于備用狀態(tài)舌狗，當(dāng)主服務(wù)掛了的時(shí)候影子服務(wù)頂上叽奥。這個(gè)切換的過程對調(diào)用方是透明的，可以自動(dòng)完成痛侍，常用的技術(shù)是vip+keepalived朝氓，具體就不在這里展開。
【常見方法三：uuid】
上述方案來生成ID主届，雖然性能大增赵哲，但由于是單點(diǎn)系統(tǒng)，總還是存在性能上限的君丁。同時(shí)枫夺，上述兩種方案，不管是數(shù)據(jù)庫還是服務(wù)來生成ID绘闷，業(yè)務(wù)方Application都需要進(jìn)行一次遠(yuǎn)程調(diào)用橡庞，比較耗時(shí)较坛。有沒有一種本地生成ID的方法，即高性能扒最，又時(shí)延低呢丑勤？
uuid是一種常見的方案：string ID =GenUUID();
優(yōu)點(diǎn)：
（1）本地生成ID，不需要進(jìn)行遠(yuǎn)程調(diào)用吧趣，時(shí)延低
（2）擴(kuò)展性好法竞，基本可以認(rèn)為沒有性能上限
缺點(diǎn)：
（1）無法保證趨勢遞增
（2）uuid過長，往往用字符串表示强挫，作為主鍵建立索引查詢效率低岔霸，常見優(yōu)化方案為“轉(zhuǎn)化為兩個(gè)uint64整數(shù)存儲(chǔ)”或者“折半存儲(chǔ)”（折半后不能保證唯一性）
【常見方法四：取當(dāng)前毫秒數(shù)】
uuid是一個(gè)本地算法，生成性能高俯渤，但無法保證趨勢遞增秉剑，且作為字符串ID檢索效率低，有沒有一種能保證遞增的本地算法呢稠诲？
取當(dāng)前毫秒數(shù)是一種常見方案：uint64 ID = GenTimeMS();
優(yōu)點(diǎn)：
（1）本地生成ID侦鹏，不需要進(jìn)行遠(yuǎn)程調(diào)用，時(shí)延低
（2）生成的ID趨勢遞增
（3）生成的ID是整數(shù)臀叙，建立索引后查詢效率高
缺點(diǎn)：
（1）如果并發(fā)量超過1000略水，會(huì)生成重復(fù)的ID
我去，這個(gè)缺點(diǎn)要了命了劝萤，不能保證ID的唯一性渊涝。當(dāng)然，使用微秒可以降低沖突概率床嫌，但每秒最多只能生成1000000個(gè)ID跨释，再多的話就一定會(huì)沖突了，所以使用微秒并不從根本上解決問題厌处。
【常見方法五：類snowflake算法】
snowflake是twitter開源的分布式ID生成算法鳖谈，其核心思想是：一個(gè)long型的ID，使用其中41bit作為毫秒數(shù)阔涉，10bit作為機(jī)器編號(hào)缆娃，12bit作為毫秒內(nèi)序列號(hào)。這個(gè)算法單機(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個(gè)機(jī)房葫掉，預(yù)計(jì)未來5年機(jī)房數(shù)量小于4個(gè)
（3）每個(gè)機(jī)房機(jī)器數(shù)小于100臺(tái)
（4）目前有5個(gè)業(yè)務(wù)線有ID生成需求，預(yù)計(jì)未來業(yè)務(wù)線數(shù)量小于10個(gè)
（5）…
分析過程如下：
（1）高位取從2016年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ù)
（2）每秒的單機(jī)高峰并發(fā)量小于10W兽肤，即平均每毫秒的單機(jī)高峰并發(fā)量小于100，差不多預(yù)留7bit給每毫秒內(nèi)序列號(hào)
（3）5年內(nèi)機(jī)房數(shù)小于4個(gè)绪抛，預(yù)留2bit給機(jī)房標(biāo)識(shí)
（4）每個(gè)機(jī)房小于100臺(tái)機(jī)器资铡，預(yù)留7bit給每個(gè)機(jī)房內(nèi)的服務(wù)器標(biāo)識(shí)
（5）業(yè)務(wù)線小于10個(gè)，預(yù)留4bit給業(yè)務(wù)線標(biāo)識(shí)
這樣設(shè)計(jì)的64bit標(biāo)識(shí)幢码，可以保證：
（1）每個(gè)業(yè)務(wù)線笤休、每個(gè)機(jī)房、每個(gè)機(jī)器生成的ID都是不同的
（2）同一個(gè)機(jī)器症副，每個(gè)毫秒內(nèi)生成的ID都是不同的
（3）同一個(gè)機(jī)器店雅，同一個(gè)毫秒內(nèi)，以序列號(hào)區(qū)區(qū)分保證生成的ID是不同的
（4）將毫秒數(shù)放在最高位贞铣，保證生成的ID是趨勢遞增的
缺點(diǎn)：
（1）由于“沒有一個(gè)全局時(shí)鐘”闹啦，每臺(tái)服務(wù)器分配的ID是絕對遞增的，但從全局看辕坝，生成的ID只是趨勢遞增的（有些服務(wù)器的時(shí)間早窍奋，有些服務(wù)器的時(shí)間晚）
最后一個(gè)容易忽略的問題：
生成的ID，例如message-id/ order-id/ tiezi-id酱畅，在數(shù)據(jù)量大時(shí)往往需要分庫分表琳袄，這些ID經(jīng)常作為取模分庫分表的依據(jù)，為了分庫分表后數(shù)據(jù)均勻纺酸，ID生成往往有“取模隨機(jī)性”的需求窖逗，所以我們通常把每秒內(nèi)的序列號(hào)放在ID的最末位，保證生成的ID是隨機(jī)的餐蔬。
又如果滑负，我們在跨毫秒時(shí)，序列號(hào)總是歸0用含，會(huì)使得序列號(hào)為0的ID比較多矮慕，導(dǎo)致生成的ID取模后不均勻。解決方法是啄骇，序列號(hào)不是每次都?xì)w0痴鳄，而是歸一個(gè)0到9的隨機(jī)數(shù)，這個(gè)地方缸夹。
如果有收獲痪寻，幫忙轉(zhuǎn)發(fā)哈螺句。
歡迎評(píng)論，有問必答橡类。
===【招聘】===
58到家正在招聘技術(shù)總監(jiān)蛇尚，測試總監(jiān)，技術(shù)經(jīng)理顾画，測試經(jīng)理取劫，架構(gòu)師（Java，測試研侣，運(yùn)維谱邪，數(shù)據(jù)庫），高級(jí)技術(shù)職位（研發(fā)庶诡，測試惦银，運(yùn)維，數(shù)據(jù)）末誓，PMO扯俱，SCM，ERP總監(jiān)/產(chǎn)品經(jīng)理/研發(fā)工程師
===【完】===
回【微信】微信為啥這么省流量
回【秒殺】秒殺系統(tǒng)架構(gòu)優(yōu)化思路
回【百度】百度咋做長文本去重（一分鐘系列）
