高并發分布式環境中擷取全局唯一ID[分布式資料庫全局唯一主鍵生成]

需求說明

在過去單機系統中，生成唯一ID比較簡單，可以使用mysql的自增主鍵或者oracle中的sequence, 在現在的大型高并發分布式系統中，以上政策就會有問題了，因為不同的資料庫會部署到不同的機器上，一般都是多主執行個體，而且再加上高并發的話，就會有重複ID的情況了。至于為什麼會有重複就不多說了，技術人員都懂的。

本文講述的案例不僅僅局限于資料庫中的ID主鍵生産，也可以适用于其他分布式環境中的唯一标示，比如全局唯一事務ID，日志追蹤時的唯一标示等。

先列出筆者最喜歡的一種全局唯一ID的生成方式，注意：沒有完美的方案，隻有适合自己的方案，還請讀者根據具體的業務進行取舍，而且可以放到用戶端進行ID 的生成，沒有單點故障，性能也有一定保證，而且不需要獨立的伺服器。

全數字全局唯一辨別（來自于mongodb）

其實作在有很多種生成政策，也各有優缺點，使用場景不同。這裡說的是一種全數字的全局唯一ID，為什麼我比較喜歡呢，首先它是全數字，儲存和計算都比較簡單(想一下MySQL資料庫中對數字和字元串的處理效率)，而且從這個ID中可以得到一些額外的資訊，不想一些UUID、sha等字元串對我們幾乎沒有太大幫助。好了下面就說一下具體實作過程。

本算法來自于mongodb

ObjectId使用12位元組的存儲空間，每個位元組存兩位16進制數字，是一個24位的字元串。其生成方式如下：

12位生成規則：

[0,1,2,3] [4,5,6] [7,8] [9,10,11]

時間戳 |機器碼 |PID |計數器

1. 前四個位元組時間戳是從标準紀元開始的時間戳，機關為秒，有如下特性：

• 時間戳與後邊5個位元組一塊，保證秒級别的唯一性；
• 保證插入順序大緻按時間排序；
• 隐含了文檔建立時間；
• 時間戳的實際值并不重要，不需要對伺服器之間的時間進行同步（因為加上機器ID和程序ID已保證此值唯一，唯一性是ObjectId的最終訴求）。

上面牽扯到兩個分布式系統中的概念：分布式系統中全局時鐘同步很難，基本不可能實作，也沒必要；時序一緻性（順序性）無法保證。這不屬于本文範疇，感興趣讀者請自行搜尋。

1. 機器ID是伺服器主機辨別，通常是機器主機名的hash散列值。
2. 同一台機器上可以運作多個mongod執行個體，是以也需要加入程序辨別符PID。
3. 前9個位元組保證了同一秒鐘不同機器不同程序産生的ObjectId的唯一性。後三個位元組是一個自動增加的計數器（一個mongod程序需要一個全局的計數器），保證同一秒的ObjectId是唯一的。同一秒鐘最多允許每個程序擁有（256^3 = 16777216）個不同的ObjectId。

總結一下：時間戳保證秒級唯一，機器ID保證設計時考慮分布式，避免時鐘同步，PID保證同一台伺服器運作多個mongod執行個體時的唯一性，最後的計數器保證同一秒内的唯一性（選用幾個位元組既要考慮存儲的經濟性，也要考慮并發性能的上限）。

改為全數字

上面mongodb中儲存的是16進制，如果不想用16進制的話，可以修改為10進制儲存，隻不過占用空間會大一些。

後面的計數器留幾位，具體就看你們的業務量了，設計的時候要預留出以後的業務增長量。單程序内的計數器可以使用atomicInteger。

具體代碼請參考我寫的另一篇文章[Twitter的分布式自增ID算法snowflake（有改動Java版）]()

http://blog.csdn.net/liubenlong007/article/details/74354713

UUID

UUID生成的是length=32的16進制格式的字元串，如果回退為byte數組共16個byte元素，即UUID是一個128bit長的數字，
  一般用16進制表示。
  算法的核心思想是結合機器的網卡、當地時間、一個随即數來生成UUID。
  從理論上講，如果一台機器每秒産生10000000個GUID，則可以保證（機率意義上）3240年不重複
  優點：
  （1）本地生成ID，不需要進行遠端調用，時延低
  （2）擴充性好，基本可以認為沒有性能上限
  缺點：
  （1）無法保證趨勢遞增
  （2）uuid過長，往往用字元串表示，作為主鍵建立索引查詢效率低，常見優化方案為“轉化為兩個uint64整數存儲”或者“折半存儲”（折半後不能保證唯一性）
           

注：以下這幾種需要獨立的伺服器

來自Flicker的解決方案（依賴資料庫）

因為MySQL本身支援auto_increment操作，很自然地，我們會想到借助這個特性來實作這個功能。

Flicker在解決全局ID生成方案裡就采用了MySQL自增長ID的機制（auto_increment + replace into + MyISAM）。一個生成64位ID方案具體就是這樣的：
  先建立單獨的資料庫(eg:ticket)，然後建立一個表：
             

CREATE TABLE Tickets64 (
id bigint(20) unsigned NOT NULL auto_increment,
stub char(1) NOT NULL default '',
PRIMARY KEY (id),
UNIQUE KEY stub (stub)
) ENGINE=MyISAM           

當我們插入記錄後，執行SELECT * from Tickets64，查詢結果就是這樣的：

  +-------------------+------+
  | id                | stub |
  +-------------------+------+
  | 72157623227190423 | a    |
  +-------------------+------+
  在我們的應用端需要做下面這兩個操作，在一個事務會話裡送出：
           

REPLACEINTOTickets64 (stub)VALUES('a');
SELECTLAST_INSERT_ID();           

這樣我們就能拿到不斷增長且不重複的ID了。
  到上面為止，我們隻是在單台資料庫上生成ID，從高可用角度考慮，接下來就要解決單點故障問題：Flicker啟用了兩台資料庫伺服器來生成ID，通過區分auto_increment的起始值和步長來生成奇偶數的ID。           

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

最後，在用戶端隻需要通過輪詢方式取ID就可以了。

  優點：充分借助資料庫的自增ID機制，提供高可靠性，生成的ID有序。
  缺點：占用兩個獨立的MySQL執行個體，有些浪費資源，成本較高。在伺服器變更的時候要修改步長，比較麻煩。
             

基于redis的分布式ID生成器

首先，要知道redis的EVAL，EVALSHA指令：

原理

利用redis的lua腳本執行功能，在每個節點上通過lua腳本生成唯一ID。

生成的ID是64位的：

• 使用41 bit來存放時間，精确到毫秒，可以使用41年。
• 使用12 bit來存放邏輯分片ID，最大分片ID是4095

• 使用10 bit來存放自增長ID，意味着每個節點，每毫秒最多可以生成1024個ID

  比如GTM時間 Fri Mar 13 10:00:00 CST 2015 ，它的距1970年的毫秒數是 1426212000000，假定分片ID是53，自增長序列是4，則生成的ID是：

  5981966696448054276 = 1426212000000 << 22 + 53 << 10 + 41

  redis提供了TIME指令，可以取得redis伺服器上的秒數和微秒數。因些lua腳本傳回的是一個四元組。

  second, microSecond, partition, seq

  用戶端要自己處理，生成最終ID。

  ((second * 1000 + microSecond / 1000) << (12 + 10)) + (shardId << 10) + seq;