分布式ID生成

在看代碼的時(shí)候遇到一個(gè)snowflake算法，查了一下發(fā)現(xiàn)是Twitter的一個(gè)分布式ID生成算法，能夠在分布式環(huán)境中生成一個(gè)全局唯一的ID，然后上網(wǎng)找了一些業(yè)界的做法，目前看到了攜程和美團(tuán)的方案，做一下筆記。

背景1

在復(fù)雜分布式系統(tǒng)中，往往需要對(duì)大量的數(shù)據(jù)和消息進(jìn)行唯一標(biāo)識(shí)。如在美團(tuán)點(diǎn)評(píng)的金融、支付、餐飲、酒店、貓眼電影等產(chǎn)品的系統(tǒng)中，數(shù)據(jù)日漸增長(zhǎng)，對(duì)數(shù)據(jù)分庫(kù)分表后需要有一個(gè)唯一ID來(lái)標(biāo)識(shí)一條數(shù)據(jù)或消息，數(shù)據(jù)庫(kù)的自增ID顯然不能滿足需求；特別一點(diǎn)的如訂單、騎手、優(yōu)惠券也都需要有唯一ID做標(biāo)識(shí)。此時(shí)一個(gè)能夠生成全局唯一ID的系統(tǒng)是非常必要的。
概括下來(lái)，那業(yè)務(wù)系統(tǒng)對(duì)ID號(hào)的要求有哪些呢？

需求1

1、全局唯一性：不能出現(xiàn)重復(fù)的ID號(hào)，既然是唯一標(biāo)識(shí)，這是最基本的要求。
2、趨勢(shì)遞增：在MySQL InnoDB引擎中使用的是聚集索引，由于多數(shù)RDBMS使用B-tree的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)索引數(shù)據(jù)，在主鍵的選擇上面我們應(yīng)該盡量使用有序的主鍵保證寫(xiě)入性能。
3、單調(diào)遞增：保證下一個(gè)ID一定大于上一個(gè)ID，例如事務(wù)版本號(hào)、IM增量消息、排序等特殊需求。
4、信息安全：如果ID是連續(xù)的，惡意用戶的扒取工作就非常容易做了，直接按照順序下載指定URL即可；如果是訂單號(hào)就更危險(xiǎn)了，競(jìng)對(duì)可以直接知道我們一天的單量。所以在一些應(yīng)用場(chǎng)景下，會(huì)需要ID無(wú)規(guī)則、不規(guī)則。
上述123對(duì)應(yīng)三類不同的場(chǎng)景，3和4需求還是互斥的，無(wú)法使用同一個(gè)方案滿足。

同時(shí)除了對(duì)ID號(hào)碼自身的要求，業(yè)務(wù)還對(duì)ID號(hào)生成系統(tǒng)的可用性要求極高，想象一下，如果ID生成系統(tǒng)癱瘓，整個(gè)美團(tuán)點(diǎn)評(píng)支付、優(yōu)惠券發(fā)券、騎手派單等關(guān)鍵動(dòng)作都無(wú)法執(zhí)行，這就會(huì)帶來(lái)一場(chǎng)災(zāi)難。

由此總結(jié)下一個(gè)ID生成系統(tǒng)應(yīng)該做到如下幾點(diǎn)：
全局唯一
支持高并發(fā)
能夠體現(xiàn)一定屬性
高可靠，容錯(cuò)單點(diǎn)故障
高性能

平均延遲和TP999延遲都要盡可能低；
可用性5個(gè)9；
高QPS。

業(yè)界方案1

UUID
UUID(Universally Unique Identifier)的標(biāo)準(zhǔn)型式包含32個(gè)16進(jìn)制數(shù)字，以連字號(hào)分為五段，形式為8-4-4-4-12的36個(gè)字符，示例：550e8400-e29b-41d4-a716-446655440000，到目前為止業(yè)界一共有5種方式生成UUID，詳情見(jiàn)IETF發(fā)布的UUID規(guī)范 A Universally Unique IDentifier (UUID) URN Namespace。

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

性能非常高：本地生成，沒(méi)有網(wǎng)絡(luò)消耗。
缺點(diǎn)：

不易于存儲(chǔ)：UUID太長(zhǎng)，16字節(jié)128位，通常以36長(zhǎng)度的字符串表示，很多場(chǎng)景不適用。
信息不安全：基于MAC地址生成UUID的算法可能會(huì)造成MAC地址泄露，這個(gè)漏洞曾被用于尋找梅麗莎病×××者位置。
ID作為主鍵時(shí)在特定的環(huán)境會(huì)存在一些問(wèn)題，比如做DB主鍵的場(chǎng)景下，UUID就非常不適用：

① MySQL官方有明確的建議主鍵要盡量越短越好[4]，36個(gè)字符長(zhǎng)度的UUID不符合要求。

All indexes other than the clustered index are known as secondary indexes. In InnoDB, each record in a secondary index contains the primary key columns for the row, as well as the columns specified for the secondary index. InnoDB uses this primary key value to search for the row in the clustered index. If the primary key is long, the secondary indexes use more space, so it is advantageous to have a short primary key.

② 對(duì)MySQL索引不利：如果作為數(shù)據(jù)庫(kù)主鍵，在InnoDB引擎下，UUID的無(wú)序性可能會(huì)引起數(shù)據(jù)位置頻繁變動(dòng)，嚴(yán)重影響性能。

類snowflake方案
這種方案大致來(lái)說(shuō)是一種以劃分命名空間（UUID也算，由于比較常見(jiàn)，所以單獨(dú)分析）來(lái)生成ID的一種算法，這種方案把64-bit分別劃分成多段，分開(kāi)來(lái)標(biāo)示機(jī)器、時(shí)間等，比如在snowflake中的64-bit分別表示如下圖（圖片來(lái)自網(wǎng)絡(luò)）所示：

image

41-bit的時(shí)間可以表示（1L<<41）/(1000L360024*365)=69年的時(shí)間，10-bit機(jī)器可以分別表示1024臺(tái)機(jī)器。如果我們對(duì)IDC劃分有需求，還可以將10-bit分5-bit給IDC，分5-bit給工作機(jī)器。這樣就可以表示32個(gè)IDC，每個(gè)IDC下可以有32臺(tái)機(jī)器，可以根據(jù)自身需求定義。12個(gè)自增序列號(hào)可以表示2^12個(gè)ID，理論上snowflake方案的QPS約為409.6w/s，這種分配方式可以保證在任何一個(gè)IDC的任何一臺(tái)機(jī)器在任意毫秒內(nèi)生成的ID都是不同的。

這種方式的優(yōu)缺點(diǎn)是：

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

毫秒數(shù)在高位，自增序列在低位，整個(gè)ID都是趨勢(shì)遞增的。
不依賴數(shù)據(jù)庫(kù)等第三方系統(tǒng)，以服務(wù)的方式部署，穩(wěn)定性更高，生成ID的性能也是非常高的。
可以根據(jù)自身業(yè)務(wù)特性分配bit位，非常靈活。
缺點(diǎn)：

強(qiáng)依賴機(jī)器時(shí)鐘，如果機(jī)器上時(shí)鐘回?fù)?，?huì)導(dǎo)致發(fā)號(hào)重復(fù)或者服務(wù)會(huì)處于不可用狀態(tài)。
應(yīng)用舉例Mongdb objectID
MongoDB官方文檔 ObjectID可以算作是和snowflake類似方法，通過(guò)“時(shí)間+機(jī)器碼+pid+inc”共12個(gè)字節(jié)，通過(guò)4+3+2+3的方式最終標(biāo)識(shí)成一個(gè)24長(zhǎng)度的十六進(jìn)制字符。

數(shù)據(jù)庫(kù)生成
以MySQL舉例，利用給字段設(shè)置auto_increment_increment和auto_increment_offset來(lái)保證ID自增，每次業(yè)務(wù)使用下列SQL讀寫(xiě)MySQL得到ID號(hào)。

begin;
REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();
commit;
image

這種方案的優(yōu)缺點(diǎn)如下：

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

非常簡(jiǎn)單，利用現(xiàn)有數(shù)據(jù)庫(kù)系統(tǒng)的功能實(shí)現(xiàn)，成本小，有DBA專業(yè)維護(hù)。
ID號(hào)單調(diào)自增，可以實(shí)現(xiàn)一些對(duì)ID有特殊要求的業(yè)務(wù)。
缺點(diǎn)：

強(qiáng)依賴DB，當(dāng)DB異常時(shí)整個(gè)系統(tǒng)不可用，屬于致命問(wèn)題。配置主從復(fù)制可以盡可能的增加可用性，但是數(shù)據(jù)一致性在特殊情況下難以保證。主從切換時(shí)的不一致可能會(huì)導(dǎo)致重復(fù)發(fā)號(hào)。
ID發(fā)號(hào)性能瓶頸限制在單臺(tái)MySQL的讀寫(xiě)性能。
對(duì)于MySQL性能問(wèn)題，可用如下方案解決：在分布式系統(tǒng)中我們可以多部署幾臺(tái)機(jī)器，每臺(tái)機(jī)器設(shè)置不同的初始值，且步長(zhǎng)和機(jī)器數(shù)相等。比如有兩臺(tái)機(jī)器。設(shè)置步長(zhǎng)step為2，TicketServer1的初始值為1（1，3，5，7，9，11...）、TicketServer2的初始值為2（2，4，6，8，10...）。這是Flickr團(tuán)隊(duì)在2010年撰文介紹的一種主鍵生成策略（Ticket Servers: Distributed Unique Primary Keys on the Cheap ）。如下所示，為了實(shí)現(xiàn)上述方案分別設(shè)置兩臺(tái)機(jī)器對(duì)應(yīng)的參數(shù)，TicketServer1從1開(kāi)始發(fā)號(hào)，TicketServer2從2開(kāi)始發(fā)號(hào)，兩臺(tái)機(jī)器每次發(fā)號(hào)之后都遞增2。

TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1

TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2
假設(shè)我們要部署N臺(tái)機(jī)器，步長(zhǎng)需設(shè)置為N，每臺(tái)的初始值依次為0,1,2...N-1那么整個(gè)架構(gòu)就變成了如下圖所示：

image

這種架構(gòu)貌似能夠滿足性能的需求，但有以下幾個(gè)缺點(diǎn)：

系統(tǒng)水平擴(kuò)展比較困難，比如定義好了步長(zhǎng)和機(jī)器臺(tái)數(shù)之后，如果要添加機(jī)器該怎么做？假設(shè)現(xiàn)在只有一臺(tái)機(jī)器發(fā)號(hào)是1,2,3,4,5（步長(zhǎng)是1），這個(gè)時(shí)候需要擴(kuò)容機(jī)器一臺(tái)?？梢赃@樣做：把第二臺(tái)機(jī)器的初始值設(shè)置得比第一臺(tái)超過(guò)很多，比如14（假設(shè)在擴(kuò)容時(shí)間之內(nèi)第一臺(tái)不可能發(fā)到14），同時(shí)設(shè)置步長(zhǎng)為2，那么這臺(tái)機(jī)器下發(fā)的號(hào)碼都是14以后的偶數(shù)。然后摘掉第一臺(tái)，把ID值保留為奇數(shù)，比如7，然后修改第一臺(tái)的步長(zhǎng)為2。讓它符合我們定義的號(hào)段標(biāo)準(zhǔn)，對(duì)于這個(gè)例子來(lái)說(shuō)就是讓第一臺(tái)以后只能產(chǎn)生奇數(shù)。擴(kuò)容方案看起來(lái)復(fù)雜嗎？貌似還好，現(xiàn)在想象一下如果我們線上有100臺(tái)機(jī)器，這個(gè)時(shí)候要擴(kuò)容該怎么做？簡(jiǎn)直是噩夢(mèng)。所以系統(tǒng)水平擴(kuò)展方案復(fù)雜難以實(shí)現(xiàn)。
ID沒(méi)有了單調(diào)遞增的特性，只能趨勢(shì)遞增，這個(gè)缺點(diǎn)對(duì)于一般業(yè)務(wù)需求不是很重要，可以容忍。
數(shù)據(jù)庫(kù)壓力還是很大，每次獲取ID都得讀寫(xiě)一次數(shù)據(jù)庫(kù)，只能靠堆機(jī)器來(lái)提高性能。

4、Redis生成ID [貌似我們用的這個(gè)]

當(dāng)使用數(shù)據(jù)庫(kù)來(lái)生成ID性能不夠要求的時(shí)候，我們可以嘗試使用Redis來(lái)生成ID。這主要依賴于Redis是單線程的，所以也可以用生成全局唯一的ID?？梢杂肦edis的原子操作INCR和INCRBY來(lái)實(shí)現(xiàn)。

可以使用Redis集群來(lái)獲取更高的吞吐量。假如一個(gè)集群中有5臺(tái)Redis?？梢猿跏蓟颗_(tái)Redis的值分別是1,2,3,4,5，然后步長(zhǎng)都是5。各個(gè)Redis生成的ID為：

A：1,6,11,16,21

B：2,7,12,17,22

C：3,8,13,18,23

D：4,9,14,19,24

E：5,10,15,20,25

比較適合使用Redis來(lái)生成每天從0開(kāi)始的流水號(hào)。比如訂單號(hào)=日期+當(dāng)日自增長(zhǎng)號(hào)?？梢悦刻煸赗edis中生成一個(gè)Key，使用INCR進(jìn)行累加。

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

不依賴于數(shù)據(jù)庫(kù)，靈活方便，且性能優(yōu)于數(shù)據(jù)庫(kù)。

數(shù)字ID天然排序，對(duì)分頁(yè)或者需要排序的結(jié)果很有幫助。

使用Redis集群也可以防止單點(diǎn)故障的問(wèn)題。

缺點(diǎn)：

如果系統(tǒng)中沒(méi)有Redis，還需要引入新的組件，增加系統(tǒng)復(fù)雜度。

需要編碼和配置的工作量比較大，多環(huán)境運(yùn)維很麻煩，

在開(kāi)始時(shí)，程序?qū)嵗?fù)載到哪個(gè)redis實(shí)例一旦確定好，未來(lái)很難做修改。

6．還有其他一些方案，比如京東淘寶等電商的訂單號(hào)生成。因?yàn)橛唵翁?hào)和用戶id在業(yè)務(wù)上的區(qū)別，訂單號(hào)盡可能要多些冗余的業(yè)務(wù)信息，比如：

滴滴：時(shí)間+起點(diǎn)編號(hào)+車(chē)牌號(hào)

淘寶訂單：時(shí)間戳+用戶ID

其他電商：時(shí)間戳+下單渠道+用戶ID，有的會(huì)加上訂單第一個(gè)商品的ID。

而用戶ID，則要求含義簡(jiǎn)單明了，包含注冊(cè)渠道即可，盡量短。

總結(jié)一下：
1、競(jìng)對(duì)竟然還可以通過(guò)分析訂單號(hào)得到大約一天得量。。。
2、snowflake的問(wèn)題是時(shí)鐘回退問(wèn)題。。。

source1--美團(tuán)
source2--攜程