分布式系統(tǒng)的主鍵生成方案對(duì)比

來(lái)源| OSCHINA 社區(qū)

作者 |京東云開發(fā)者-京東物流 金越

UUID

UUID（通用唯一識(shí)別碼）是由 32 個(gè)十六進(jìn)制數(shù)組成的無(wú)序字符串，通過(guò)一定的算法計(jì)算出來(lái)。為了保證其唯一性，UUID 規(guī)范定義了包括網(wǎng)卡 MAC 地址、時(shí)間戳、名字空間（Namespace）、隨機(jī)或偽隨機(jī)數(shù)、時(shí)序等元素，以及從這些元素生成 UUID 的算法。一般來(lái)說(shuō)，算法可以保證任何地方產(chǎn)生的任意一個(gè) UUID 都不會(huì)相同，但這個(gè)唯一性是有限的，只在特定的范圍內(nèi)才能得到保證。 UUID 的一個(gè)非常明顯的特點(diǎn)就是本身較長(zhǎng)，格式是這樣的：

xxxxxxxx-xxxx-Mxxx-xxxx-xxxxxxxxxxxx
467e8542-2275-4163-95d6-7adc205580a9

各版本介紹

UUID 現(xiàn)有的 5 種版本，是根據(jù)不同的使用場(chǎng)景劃分的，而不是根據(jù)精度，所以 Version5 并不會(huì)比 Version1 精度高，在精度上大家都能保證唯一性，重復(fù)的概率近乎于 0。 總結(jié)：

使用 UUID，每個(gè)人都可以創(chuàng)建不與其它人沖突的唯一值，在所有空間和時(shí)間上都可以被視為唯一的標(biāo)識(shí)。

UUID 可單機(jī)自行生成，且生成速度快，QPS 高，各個(gè)語(yǔ)言都有對(duì)應(yīng)的生成供直接調(diào)用使用。

如果只是需要生成一個(gè)唯一 ID，可以使用 V1 或 V4。v1 基于時(shí)間戳和 Mac 地址，這些 ID 有一定的規(guī)律，而且會(huì)暴露你的 Mac 地址。v4 是完全隨機(jī) (偽) 的。

如果對(duì)于相同的參數(shù)需要輸出相同的 UUID, 你可以使用 V3 或 V5。

Version1: 基于時(shí)間戳及 MAC 地址的實(shí)現(xiàn)

其中包括了 48 位的 MAC 地址和 60 位的時(shí)間戳。且 v1 為了保證唯一性，當(dāng)時(shí)間精度不夠時(shí)，會(huì)使用 13~14 位的 clock sequence 來(lái)擴(kuò)展時(shí)間戳，比如：當(dāng) UUID 的生產(chǎn)成速率太快，超過(guò)了系統(tǒng)時(shí)間的精度。時(shí)間戳的低位部分會(huì)每增加一個(gè) UUID 就 + 1 的操作來(lái)模擬更高精度的時(shí)間戳，換句話說(shuō)，就是當(dāng)系統(tǒng)時(shí)間精度無(wú)會(huì)區(qū)分 2 個(gè) UUID 的時(shí)間先后時(shí)，為了保證唯一性，會(huì)在其中一個(gè) UUID 上 + 1。所以 UUID 重復(fù)的概率幾乎為 0，時(shí)間戳加擴(kuò)展的 clock sequence 一共有 74bits,(2 的 74 次方，約為 1.8 后面加 22 個(gè)零), 即在每個(gè)節(jié)點(diǎn)下，每秒可產(chǎn)生 1630 億不重復(fù)的 UUID。 但由于 v1 中最后的 12 位是網(wǎng)卡的 MAC 地址，會(huì)導(dǎo)致隱私問(wèn)題以及安全問(wèn)題，這是這個(gè)版本 UUID 受到批評(píng)的地方。

Version2: DCE 安全的 UUID

DCE（Distributed Computing Environment）安全的 UUID 和基于時(shí)間的 UUID 算法相同，但會(huì)把時(shí)間戳的前 4 位置換為 POSIX 的 UID 或 GID。這個(gè)版本的 UUID 在實(shí)際中較少用到。

Version3: 5 基于名稱空間和名字

v3 和 v5 都是通過(guò)計(jì)算 namespace 和名稱的哈希值生成的。不同的點(diǎn)在于 v3 使用的 hash 算法為 MD5，v5 使用 SHA-1。因?yàn)樗惴ㄖ袥]有不確定的部分，所以當(dāng) namespace 與名稱確定時(shí)，得到的 UUID 都是確定唯一的。比如：

$ uuid -n 3 -v3 ns:URL www.jd.com
7e963853-8fce-3085-bb2c-8424745d73a2
7e963853-8fce-3085-bb2c-8424745d73a2
7e963853-8fce-3085-bb2c-8424745d73a2

Version4: 基于隨機(jī)數(shù)

v4 的 UUID 中 4 位代表版本，2-3 位代表 variant。余下的 122-121 位都是全部隨機(jī)的。即有 2 的 122 次方 (5.3 后面 36 個(gè) 0) 個(gè) UUID。一個(gè)標(biāo)準(zhǔn)實(shí)現(xiàn)的 UUID 庫(kù)在生成了 2.71 萬(wàn)億個(gè) UUID 會(huì)產(chǎn)生重復(fù) UUID 的可能性也只有 50% 的概率。這相當(dāng)于每秒產(chǎn)生 10 億的 UUID，持續(xù) 85 年，而把這些 UUID 都存入文件，每個(gè) UUID 占 16bytes, 總需要 45EB (exabytes)，比目前最大的數(shù)據(jù)庫(kù) (PB) 還要大很多倍。 在 java 中使用 v4：

# java 1.5+ 
# java.util.UUID

for (int i = 0; i < 3; i++) {
String uuid = UUID.randomUUID().toString();
System.out.println(uuid);
}

生成的 UUID 如下：

8bca474b-214d-4ce8-8446-b99f30147f94
c38588cf-a1c4-4758-9d86-b2ee5552ae59
febf5a46-bd1b-43f8-89a8-d5606e5d1ce0

SnowFlake 算法

雪花算法，是 Twitter 開源的分布式 ID 生成算法。雪花算法中利用了時(shí)間戳，機(jī)器 ID，以及同毫秒內(nèi)的不同序列號(hào)來(lái)保證分布式生成 ID 的唯一性。 雪花算法總結(jié) 1. 時(shí)間戳在高位，自增序列在低位的特征可以保證整個(gè) ID 的趨勢(shì)是遞增有序的。 2. 但由于其依賴機(jī)器時(shí)鐘，如果機(jī)器時(shí)鐘回?fù)?，可能?huì)導(dǎo)致重復(fù) ID 生成。其在分布式環(huán)境下，每臺(tái)機(jī)器上的時(shí)鐘不可能完全同步，有時(shí)候會(huì)出現(xiàn)不是全局遞增的情況。 SnowFlake 算法生成 id 的結(jié)果是一個(gè) 64bit 大小的整數(shù)，它的結(jié)構(gòu)如下圖：

1bit，不用。二進(jìn)制中最高位為 1 的都是負(fù)數(shù)，但是我們生成的 id 一般都使用整數(shù)，所以這個(gè)最高位固定是 0

41bit，用來(lái)記錄時(shí)間戳（毫秒）。41 位可以表示 2^{41}-1 個(gè)數(shù)字，如果只用來(lái)表示正整數(shù)（計(jì)算機(jī)中正數(shù)包含 0），可以表示的數(shù)值范圍是 0 至 2^{41}-1，也就是說(shuō) 41 位可以表示 2^{41}-1 個(gè)毫秒的值，轉(zhuǎn)化成單位年則是 (2^{41} - 1) / (1000*60*60*24*365) = 69 年。

10bit，用來(lái)記錄工作機(jī)器 id?？梢圆渴鹪?2^{10} = 1024 個(gè)節(jié)點(diǎn)，包括 5 位 datacenterId 和 5 位 workerId，5 位（bit）可以表示的最大正整數(shù)是 2^{5}-1 = 31，即可以用 0、1、2、3、....、31 這 32 個(gè)數(shù)字，來(lái)表示不同的 datecenterId 或 workerId。

12 位，序列號(hào)，用來(lái)記錄同毫秒內(nèi)產(chǎn)生的不同 ID；12bit 可以表示的最大正整數(shù)是 2^{12}-1 = 4095 ，即可以用 0、1、2、3、....4094 這 4095 個(gè)數(shù)字，來(lái)表示同一機(jī)器同一時(shí)間截（毫秒) 內(nèi)產(chǎn)生的 4095 個(gè) ID 序號(hào)。

有序主鍵 or 隨機(jī)主鍵 ？

使用 UUID 這些隨機(jī) ID 生成算法作為 MySQL 主鍵的生成方案呢？答案是：不可以！ 眾所周知，當(dāng) MySQL 數(shù)據(jù)表使用 InnoDB 作為存儲(chǔ)引擎時(shí)，每一個(gè)索引都對(duì)應(yīng)一個(gè) B + 樹，若表定義了主鍵（沒有時(shí)，MySQL 則會(huì)自動(dòng)生成不可見的自增主鍵），主鍵對(duì)應(yīng)的索引就是聚簇索引，表的所有數(shù)據(jù)都存儲(chǔ)在聚簇索引上。索引中鍵值的邏輯順序決定了表中相應(yīng)行的物理順序（索引中的數(shù)據(jù)物理存放地址和索引的順序是一致的）?？梢赃@么理解：只要是索引是連續(xù)的，那么數(shù)據(jù)在存儲(chǔ)介質(zhì)上的存儲(chǔ)位置也是連續(xù)的。 基于以上特性，由于自增鍵的值是有序的，插入數(shù)據(jù)時(shí)，Innodb 會(huì)把每一條記錄都存儲(chǔ)在上一條記錄的后面。當(dāng)達(dá)到頁(yè)面的最大填充因子時(shí)候 (innodb 默認(rèn)的最大填充因子是頁(yè)大小的 15/16, 會(huì)留出 1/16 的空間留作以后的修改)，會(huì)進(jìn)行如下操作：下一條記錄就會(huì)寫入新的頁(yè)中，一旦數(shù)據(jù)按照這種順序的方式加載，主鍵頁(yè)就會(huì)近乎于順序的記錄填滿，提升了頁(yè)面的最大填充率，不會(huì)有頁(yè)的浪費(fèi)；且由于新插入的行一定會(huì)在原有的最大數(shù)據(jù)行下一行，mysql 定位和尋址很快，不會(huì)為計(jì)算新行的位置而做出額外的消耗。 而 UUID 相對(duì)于有序的自增 ID，它的值是毫無(wú)規(guī)律可言的，新行的主鍵不一定要比之前數(shù)據(jù)主鍵的值大，所以 innodb 無(wú)法做到總是把新行插入到索引的最后，而是需要為新行尋找新的合適的位置從而來(lái)分配新的空間。這個(gè)過(guò)程需要做很多額外的操作，而且最終分布散亂的數(shù)據(jù)會(huì)導(dǎo)致以下問(wèn)題：

寫入的目標(biāo)頁(yè)很可能已經(jīng)刷新到磁盤上并且從緩存上移除，或者還沒有被加載到緩存中，innodb 在插入之前不得不先找到并從磁盤讀取目標(biāo)頁(yè)到內(nèi)存中，這將導(dǎo)致大量的隨機(jī) IO；

因?yàn)閷懭胧莵y序的，innodb 不得不頻繁的做頁(yè)分裂操作，以便為新的行分配空間，頁(yè)分裂導(dǎo)致移動(dòng)大量的數(shù)據(jù)，一次插入最少需要修改三個(gè)頁(yè)以上，且由于頻頁(yè)分裂，頁(yè)會(huì)變得稀疏并被不規(guī)則的填充，最終會(huì)導(dǎo)致數(shù)據(jù)會(huì)有碎片；

在把值載入到聚簇索引 (innodb 默認(rèn)的索引類型) 以后，有時(shí)候會(huì)需要做一次 OPTIMEIZE TABLE 來(lái)重建表并優(yōu)化頁(yè)的填充，這將又需要一定的時(shí)間消耗。

審核編輯：湯梓紅