UUID（通用唯一識別碼）是由32個十六進位數組成的無序字元串，通過一定的演算法計算出來。為了保證其唯一性，UUID規範定義了包括網卡MAC地址、時間戳、名字空間（Namespace）、隨機或偽隨機數、時序等元素，以及從這些元素生成UUID的演算法。一般來說，演算法可以保證任何地方產生的任意一個UUID都... ...

UUID

UUID（通用唯一識別碼）是由32個十六進位數組成的無序字元串，通過一定的演算法計算出來。為了保證其唯一性，UUID規範定義了包括網卡MAC地址、時間戳、名字空間（Namespace）、隨機或偽隨機數、時序等元素，以及從這些元素生成UUID的演算法。一般來說，演算法可以保證任何地方產生的任意一個UUID都不會相同，但這個唯一性是有限的，只在特定的範圍內才能得到保證。

UUID的一個非常明顯的特點就是本身較長，格式是這樣的：

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

其中M位置，代表版本號，由於UUID的標準實現有5個版本，所以只會是1、2、3、4、5；

各版本介紹

UUID現有的5種版本，是根據不同的使用場景劃分的，而不是根據精度，所以Version5並不會比Version1精度高，在精度上大家都能保證唯一性，重覆的概率近乎於0。

總結：

使用UUID，每個人都可以創建不與其它人衝突的唯一值，在所有空間和時間上都可以被視為唯一的標識。
UUID可單機自行生成，且生成速度快，QPS高，各個語言都有對應的生成供直接調用使用。
如果只是需要生成一個唯一ID，可以使用V1或V4。v1基於時間戳和Mac地址,這些ID有一定的規律，而且會暴露你的Mac地址。v4是完全隨機(偽)的。
如果對於相同的參數需要輸出相同的UUID,你可以使用V3或V5。

Version1: 基於時間戳及MAC地址的實現

其中包括了48位的MAC地址和60位的時間戳。且v1為了保證唯一性，當時間精度不夠時，會使用13~14位的clock sequence來擴展時間戳，比如：當UUID的生產成速率太快，超過了系統時間的精度。時間戳的低位部分會每增加一個UUID就+1的操作來模擬更高精度的時間戳，換句話說，就是當系統時間精度無會區分2個UUID的時間先後時，為了保證唯一性，會在其中一個UUID上+1。所以UUID重覆的概率幾乎為0，時間戳加擴展的clock sequence一共有74bits,(2的74次方，約為1.8後面加22個零),即在每個節點下，每秒可產生1630億不重覆的UUID。

但由於v1中最後的12位是網卡的MAC地址，會導致隱私問題以及安全問題，這是這個版本UUID受到批評的地方。

Version2: DCE安全的UUID

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

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

v3和v5都是通過計算namespace和名稱的哈希值生成的。不同的點在於v3使用的hash演算法為MD5，v5使用SHA-1。因為演算法中沒有不確定的部分，所以當namespace與名稱確定時，得到的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

演算法實現中會將namespace和輸入參數拼接在一起，計算hash結果，再進行截斷格式化等操作來保證唯一性。

Version4: 基於隨機數

v4的UUID中4位代表版本，2-3位代表variant。餘下的122-121位都是全部隨機的。即有2的122次方(5.3後面36個0)個UUID。一個標準實現的UUID庫在生成了2.71萬億個UUID會產生重覆UUID的可能性也只有50%的概率。這相當於每秒產生10億的UUID，持續85年，而把這些UUID都存入文件，每個UUID占16bytes,總需要45EB(exabytes)，比目前最大的資料庫(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 生成演算法。雪花演算法中利用了時間戳，機器ID，以及同毫秒內的不同序列號來保證分散式生成ID的唯一性。

雪花演算法總結

1.時間戳在高位，自增序列在低位的特征可以保證整個ID的趨勢是遞增有序的。

2.但由於其依賴機器時鐘，如果機器時鐘回撥，可能會導致重覆ID生成。其在分散式環境下，每台機器上的時鐘不可能完全同步，有時候會出現不是全局遞增的情況。

SnowFlake演算法生成id的結果是一個64bit大小的整數，它的結構如下圖：

1bit，不用。二進位中最高位為1的都是負數，但是我們生成的id一般都使用整數，所以這個最高位固定是0
41bit，用來記錄時間戳（毫秒）。41位可以表示 2^{41}-1 個數字，如果只用來表示正整數（電腦中正數包含0），可以表示的數值範圍是 0 至 2^{41}-1，也就是說41位可以表示 2^{41}-1 個毫秒的值，轉化成單位年則是 (2^{41} - 1) / (1000*60*60*24*365) = 69 年。
10bit，用來記錄工作機器id。可以部署在 2^{10} = 1024 個節點，包括 5位 datacenterId 和 5位 workerId，5位（bit）可以表示的最大正整數是 2^{5}-1 = 31，即可以用 0、1、2、3、....、31 這 32 個數字，來表示不同的 datecenterId 或 workerId。
12位，序列號，用來記錄同毫秒內產生的不同ID；12bit 可以表示的最大正整數是 2^{12}-1 = 4095 ，即可以用 0、1、2、3、....4094 這 4095 個數字，來表示同一機器同一時間截（毫秒)內產生的 4095 個 ID 序號。

有序主鍵 or 隨機主鍵？

使用UUID這些隨機ID生成演算法作為MySQL主鍵的生成方案呢？答案是：不可以！

眾所周知，當MySQL數據表使用InnoDB作為存儲引擎時，每一個索引都對應一個B+樹，若表定義了主鍵（沒有時，MySQL則會自動生成不可見的自增主鍵），主鍵對應的索引就是聚簇索引，表的所有數據都存儲在聚簇索引上。索引中鍵值的邏輯順序決定了表中相應行的物理順序（索引中的數據物理存放地址和索引的順序是一致的）。可以這麼理解：只要是索引是連續的，那麼數據在存儲介質上的存儲位置也是連續的。

基於以上特性，由於自增鍵的值是有序的，插入數據時，Innodb 會把每一條記錄都存儲在上一條記錄的後面。當達到頁面的最大填充因數時候(innodb預設的最大填充因數是頁大小的15/16,會留出1/16的空間留作以後的修改)，會進行如下操作：下一條記錄就會寫入新的頁中，一旦數據按照這種順序的方式載入，主鍵頁就會近乎於順序的記錄填滿，提升了頁面的最大填充率，不會有頁的浪費；且由於新插入的行一定會在原有的最大數據行下一行，mysql定位和定址很快，不會為計算新行的位置而做出額外的消耗。

而UUID相對於有序的自增ID，它的值是毫無規律可言的，新行的主鍵不一定要比之前數據主鍵的值大，所以innodb無法做到總是把新行插入到索引的最後，而是需要為新行尋找新的合適的位置從而來分配新的空間。這個過程需要做很多額外的操作，而且最終分佈散亂的數據會導致以下問題：

寫入的目標頁很可能已經刷新到磁碟上並且從緩存上移除，或者還沒有被載入到緩存中，innodb在插入之前不得不先找到並從磁碟讀取目標頁到記憶體中，這將導致大量的隨機IO；
因為寫入是亂序的,innodb不得不頻繁的做頁分裂操作，以便為新的行分配空間,頁分裂導致移動大量的數據，一次插入最少需要修改三個頁以上，且由於頻頁分裂，頁會變得稀疏並被不規則的填充，最終會導致數據會有碎片；
在把值載入到聚簇索引(innodb預設的索引類型)以後，有時候會需要做一次OPTIMEIZE TABLE來重建表並優化頁的填充，這將又需要一定的時間消耗。

作者：京東零售金越

來源：京東雲開發者社區轉載請註明來源

分散式系統的主鍵生成方案對比