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

這個ID，在數(shù)據(jù)庫中往往用作主鍵，且有排序與分頁的查詢需求。這也是分布式ID生成算法的兩大核心需求：

• 全局唯一;
• 趨勢遞增;

如何高效生成趨勢有序的全局唯一ID，是每一個工程師都會遇到的問題。

方法一：數(shù)據(jù)庫auto-inc-id法

借助數(shù)據(jù)庫的auto_increment來生成全局唯一遞增ID。

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

• 簡單，使用數(shù)據(jù)庫已有的功能;
• 能夠保證唯一性;
• 能夠保證遞增性;
• 步長固定;

不足：

• 可用性難以保證，需要依賴數(shù)據(jù)庫的高可用;
• 擴(kuò)展性差，性能有上限，數(shù)據(jù)庫主庫的寫性能決定ID的生成性能上限;

改進(jìn)方法：

• 冗余主庫，避免寫入單點(diǎn);
• 數(shù)據(jù)水平切分，保證各主庫生成的ID不重復(fù);

改進(jìn)后，數(shù)據(jù)庫的寫壓力依然很大，每次生成ID都要訪問數(shù)據(jù)庫。為了解決這個問題，引出了第二個常見的方案。

方法二：批量ID生成服務(wù)

數(shù)據(jù)庫寫壓力大，是因?yàn)槊看紊蒊D都訪問了數(shù)據(jù)庫，可以使用批量的方式降低數(shù)據(jù)庫寫壓力。

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)：

• 保證了ID生成的絕對遞增有序;
• 大大的降低了數(shù)據(jù)庫的壓力，ID生成可以做到每秒生成幾萬幾十萬個;

同時，服務(wù)也可以做集群化，只是稍微要注意數(shù)據(jù)一致性問題，具體CAS優(yōu)化方案在《巧用CAS實(shí)現(xiàn)分布式ID生成器!》中有詳細(xì)介紹，不再展開。

方法三：uuid/guid法

不管是通過數(shù)據(jù)庫，還是通過服務(wù)來生成ID，業(yè)務(wù)方都需要進(jìn)行一次遠(yuǎn)程調(diào)用，比較耗時。有沒有一種本地生成ID的方法，即高性能，又時延低呢?

uuid是一種常見的方案：

string ID =GenUUID();

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

• 本地生成ID，不需要進(jìn)行遠(yuǎn)程調(diào)用，時延低;
• 擴(kuò)展性好，基本可以認(rèn)為沒有性能上限;

不足：

• 無法保證趨勢遞增
• uuid過長，往往用字符串表示，作為主鍵建立索引查詢效率低，常見優(yōu)化方案為“轉(zhuǎn)化為兩個uint64整數(shù)存儲”。

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

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

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

uint64 ID = GenTimeMS();

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

• 本地生成ID，不需要進(jìn)行遠(yuǎn)程調(diào)用，時延低;
• 生成的ID趨勢遞增;
• 生成的ID是整數(shù)，建立索引后查詢效率高;

缺點(diǎn)：如果并發(fā)量超過1000，會生成重復(fù)的ID。

當(dāng)然，使用微秒可以降低沖突概率，但每秒最多只能生成1000000個ID，再多的話就一定會沖突了，所以使用微秒并不從根本上解決問題。

方法五：類snowflake算法

snowflake是twitter開源的分布式ID生成算法，其核心思想為，一個long型的ID：

• 41bit作為毫秒數(shù);
• 10bit作為機(jī)器(服務(wù))編號;
• 12bit作為毫秒內(nèi)序列號;

算法單機(jī)每秒內(nèi)理論上最多可以生成1000*(2^12)，也就是400W的ID，1024臺機(jī)器(服務(wù))每秒能生活40Y的ID，完全能滿足業(yè)務(wù)的需求。

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

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

• 單機(jī)高峰并發(fā)量小于1W，預(yù)計(jì)未來10年單機(jī)高峰并發(fā)量小于10W;
• 有2個機(jī)房，預(yù)計(jì)未來10年機(jī)房數(shù)量小于4個;
• 每個機(jī)房機(jī)器數(shù)小于100臺;
• 目前有5個業(yè)務(wù)線有ID生成需求，預(yù)計(jì)未來業(yè)務(wù)線數(shù)量小于10個;
• …

我們應(yīng)該怎么來設(shè)計(jì)公司獨(dú)特的ID生成算法呢?

其一，毫秒位數(shù)考慮。

假設(shè)系統(tǒng)至少運(yùn)行10年，那至少需要10年*365天*24小時*3600秒*1000毫秒=320*10^9，差不多預(yù)留39bit給毫秒數(shù)。

其二，1毫秒內(nèi)序列號考慮。

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

其三，機(jī)房數(shù)少于4個，預(yù)留2bit給機(jī)房標(biāo)識。

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

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

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

• 每個業(yè)務(wù)線、每個機(jī)房、每個機(jī)器生成的ID都是不同的;
• 同一個機(jī)器，每個毫秒內(nèi)生成的ID都是不同的;
• 同一個機(jī)器，同一個毫秒內(nèi)，以序列號區(qū)區(qū)分保證生成的ID是不同的;
• 將毫秒數(shù)放在最高位，保證生成的ID是趨勢遞增的;

以上，希望大家有收獲。

知其然，知其所以然。思路比結(jié)論更重要。

擴(kuò)展閱讀：https://github.com/twitter-archive/snowflake