圖解各路分布式ID生成算法-魔扣目錄

在分布式系統(tǒng)中，通常會用到分布式ID來標(biāo)注數(shù)據(jù)的唯一性，而分布式ID的生成方式又多種多樣，今天我們就來討論一下主流的分布式ID生成策略。

分布式ID基本需求

全局唯一
趨勢遞增
信息安全

全局唯一

這是基本要求，不必解釋

趨勢遞增

為什么要趨勢遞增呢？

第一，由于我們的分布式ID，是用來標(biāo)識數(shù)據(jù)唯一性的，所以多數(shù)時候會被定義為主鍵或者唯一索引。

第二，并且絕大多數(shù)互聯(lián)網(wǎng)公司使用的數(shù)據(jù)庫是：MySQL，存儲引擎為innoDB。

對于 B+Tree這個數(shù)據(jù)結(jié)構(gòu)來講，數(shù)據(jù)以自增順序來寫入的話，b+tree的結(jié)構(gòu)不會時常被打亂重塑，存取效率是最高的。

信息安全

由于數(shù)據(jù)是遞增的，所以，惡意用戶的可以根據(jù)當(dāng)前ID推測出下一個，非常危險，所以，我們的分布式ID盡量做到不易被破解。

數(shù)據(jù)庫主鍵自增(Flicker)

基于數(shù)據(jù)庫主鍵自增的方案，名為 Flicker。

主要是利用MySQL的自增主鍵來實現(xiàn)分布式ID。

以下為 Flicker實現(xiàn)分布式ID的主流做法：

1、需要單獨建立一個數(shù)據(jù)庫實例：flicker

create database `flicker`;

2、創(chuàng)建一張表：sequence_id

create table sequence_id(
 id bigint(20) unsigned NOT NULL auto_increment, 
 stub char(10) NOT NULL default '',
 PRIMARY KEY (id),
 UNIQUE KEY stub (stub)
) ENGINE=MyISAM;

為什么用 MyISAM？不用 InnoDB？個人推測原因是： flicker算法出來的時候，MySQL的默認(rèn)引擎還依舊是 MyISAM而不是 InnoDB，作者只是想用默認(rèn)引擎而已，并無其他原因。

stub: 票根，對應(yīng)需要生成 Id 的業(yè)務(wù)方編碼，可以是項目名、表名甚至是服務(wù)器 IP 地址。
stub 要設(shè)置為唯一索引

3、使用以下SQL來獲取ID

REPLACE INTO ticket_center (stub) VALUES ('test'); 
SELECT LAST_INSERT_ID();

Replaceinto 先嘗試插入數(shù)據(jù)到表中，如果發(fā)現(xiàn)表中已經(jīng)有此行數(shù)據(jù)（根據(jù)主鍵或者唯一索引判斷）則先刪除此行數(shù)據(jù)，然后插入新的數(shù)據(jù)，否則直接插入新數(shù)據(jù)。

一般 stub為特殊的相同的值。

這樣，一個分布式ID系統(tǒng)算是可以搭建運行了。但是，有人要問：“這是一個單實例、單點的系統(tǒng)，萬一掛了，豈不是影響所有關(guān)聯(lián)的業(yè)務(wù)方？”

改進升華

是的。確實如此，因此又有人說：“可以利用MySQL主從模式，主庫掛了，使用從庫。”

這只能算是一種比較low的策略，因為如果主庫掛了，從庫沒來得及同步，就會生成重復(fù)的ID。

有沒有更好的方法呢？

我們可以使用“雙主模式“，也就是有兩個MySQL實例，這兩個都能生成ID。

如圖所示，我們原來的模式：

雙主模式是該怎么樣呢？如何保持唯一性？

我們可以讓一臺實例生成奇數(shù)ID，另一臺生成偶數(shù)ID。

奇數(shù)那一臺：

set auto_increment_offset=1;--起始值
set auto_increment_increment=2;--步長

偶數(shù)那一臺：

set auto_increment_offset=2;--起始值
set auto_increment_increment=2;--步長

當(dāng)兩臺都OK的時候，隨機取其中的一臺生成ID；若其中一臺掛了，則取另外一臺生成ID。

如圖所示：

細心會發(fā)現(xiàn)，N個節(jié)點，只要起始值為1，2，...N，然后步長為N，就會生成各不相同的ID。(PS:后文有推導(dǎo)公式)

總結(jié)

優(yōu)點：

簡單。充分利用了數(shù)據(jù)庫自增 ID 機制，生成的 ID 有序遞增。
ID遞增

缺點：

并發(fā)量不大。
水平擴展困難，系統(tǒng)定義好了起始值、步長和機器臺數(shù)，跑起來之后，添加額外的機器困難。
安全系數(shù)低

redis

Redis為單線程的，所以操作為原子操作，利用 incrby命令可以生成唯一的遞增ID。

原理

單機單點，吞吐不夠，加集群

假設(shè)N個節(jié)點，則步長為N，節(jié)點起始值為1，2，…… N。則三個節(jié)點生成的ID一定不同！

想想為什么？

以上信息條件可以轉(zhuǎn)化為數(shù)學(xué)推理： 1+x*N=2+y*N且x、y、N都為整成數(shù)且N不為1，試問等式存不存在？

答：
假設(shè)存在在起始值是1的節(jié)點上疊加x次之后等于起始值為2、疊加y次的值，
既 “1 + x * N = 2 + y * N” 等式成立
則：
x * N = 1 + y * N
x * N - y * N = 1
(x - y) * N = 1
(x - y) = 1 / N
又因為 x、y都為整成數(shù)；
所以x - y 必為整成數(shù)；
又因為只有N等于1的時候，1/N才為整成數(shù)；
與條件N為1不符合，所以不存在。

同理可證 1+x*N=3+y*N和 2+x*N=3+y*N也是如此。

優(yōu)點

性能顯然高于基于數(shù)據(jù)庫的 Flicker方案
ID遞增

缺點

水平擴展困難
Redis集群宕機可能會產(chǎn)生重復(fù)的id
易破解

UUID

想必這個大家都熟悉。 UUID是通用唯一識別碼（Universally Unique Identifier）的縮寫，是一種軟件建構(gòu)的標(biāo)準(zhǔn)，亦為開放軟件基金會組織在分布式計算環(huán)境領(lǐng)域的一部分。

原理

UUID是由一組32位數(shù)的16進制數(shù)字所構(gòu)成，是故UUID理論上的總數(shù)為16^32 = 2^128，約等于3.4 x 10^38。也就是說若每納秒產(chǎn)生1兆個UUID，要花100億年才會將所有UUID用完。

UUID是利用同一時空中的所有機器都是唯一的這一規(guī)則來確保唯一性的。

具體外形為：

通常由以下幾部分組成：

系統(tǒng)時間
時鐘序列
全局唯一的IEEE機器識別，如網(wǎng)卡mac、機器SN等

生成方式多種多樣，業(yè)界公認(rèn)的是五種，分別是uuid1,uuid2,uuid3,uuid4,uuid5。

目前使用最廣泛的UUID是微軟的 GUID。

優(yōu)點

本地生成，性能極佳。無網(wǎng)絡(luò)消耗
全局唯一

缺點

存儲麻煩。16字節(jié)128位，通常以36長度的字符串表示，很多場景不適用
通常是字符串，非自增，無序，不利于做主鍵。每次插入都會對B+tree結(jié)構(gòu)進行修改
破解相對困難，但是也不安全。參考"梅麗莎病毒事件，病毒作者制作的UUID包含Mac地址，被警方破解后，直接定位，抓捕歸案"

snowflake

snowflake即雪花算法，Twitter發(fā)明的。

原理

外形長這樣：

1位不用。二進制中最高位為1的都是負(fù)數(shù)，但是我們生成的id一般都使用整數(shù)，所以這個最高位固定是0。
41位，用來記錄毫秒的時間戳。41位可以表示的數(shù)值范圍是：0 至 2^{41}-1，減1是因為可表示的數(shù)值范圍是從0開始算的，而不是1，轉(zhuǎn)化為年則是 2^{41}-1)/(1000*60*60*24*365)=69年。
10位，用來記錄工作機器id。最多可以部署在2^{10} = 1024個節(jié)點，我們可以根據(jù)具體的業(yè)務(wù)來定制具體分配的機器數(shù)量和每臺機器1毫秒產(chǎn)生的id序號number數(shù)。例如可以把10bit分5bit給IDC，分5bit給工作機器。這樣就可以表示32個IDC，每個IDC下可以有32臺機器，可以將內(nèi)容配置在配置文件中，服務(wù)去獲取。
12位。用來表示單臺機器每毫秒生成的id序號，12位bit可以表示的最大正整數(shù)為2^12 - 1 = 4096，若超過4096，則重新從0開始。即，每臺機器1毫秒內(nèi)最多產(chǎn)生4096個ID，足夠用了。

最后將上述4段bit通過位運算拼接起來組成64位bit.

由于是64位bit,所以完全可以用數(shù)字來表示ID。

基本是根據(jù)：