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

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

分布式ID基本需求

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

全局唯一

這是基本要求，不必解釋

趨勢遞增

為什么要趨勢遞增呢？

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

第二，并且絕大多數互聯網公司使用的數據庫是：MySQL，存儲引擎為innoDB。

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

信息安全

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

數據庫主鍵自增(Flicker)

基于數據庫主鍵自增的方案，名為 Flicker。

主要是利用MySQL的自增主鍵來實現分布式ID。

以下為 Flicker實現分布式ID的主流做法：

1、需要單獨建立一個數據庫實例：flicker

create database `flicker`;

2、創建一張表：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的默認引擎還依舊是 MyISAM而不是 InnoDB，作者只是想用默認引擎而已，并無其他原因。

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

3、使用以下SQL來獲取ID

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

Replaceinto 先嘗試插入數據到表中，如果發現表中已經有此行數據（根據主鍵或者唯一索引判斷）則先刪除此行數據，然后插入新的數據，否則直接插入新數據。

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

這樣，一個分布式ID系統算是可以搭建運行了。但是，有人要問：“這是一個單實例、單點的系統，萬一掛了，豈不是影響所有關聯的業務方？”

改進升華

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

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

有沒有更好的方法呢？

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

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

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

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

奇數那一臺：

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

偶數那一臺：

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

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

如圖所示：

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

總結

優點：

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

缺點：

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

redis

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

原理

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

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

想想為什么？

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

答：
假設存在在起始值是1的節點上疊加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都為整成數；
所以x - y 必為整成數；
又因為只有N等于1的時候，1/N才為整成數；
與條件N為1不符合，所以不存在。

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

優點

性能顯然高于基于數據庫的 Flicker方案
ID遞增

缺點

水平擴展困難
Redis集群宕機可能會產生重復的id
易破解

UUID

想必這個大家都熟悉。 UUID是通用唯一識別碼（Universally Unique Identifier）的縮寫，是一種軟件建構的標準，亦為開放軟件基金會組織在分布式計算環境領域的一部分。

原理

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

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

具體外形為：

通常由以下幾部分組成：

系統時間
時鐘序列
全局唯一的IEEE機器識別，如網卡mac、機器SN等

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

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

優點

本地生成，性能極佳。無網絡消耗
全局唯一

缺點

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

snowflake

snowflake即雪花算法，Twitter發明的。

原理

外形長這樣：

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

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

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

基本是根據：