java-高并發-高并發分布式系統中生成全局唯一Id彙總

高并發分布式系統中生成全局唯一Id彙總

資料在分片時，典型的是分庫分表，就有一個全局ID生成的問題。

單純的生成全局ID并不是什麼難題，但是生成的ID通常要滿足分片的一些要求：

   1 不能有單點故障。

   2 以時間為序，或者ID裡包含時間。這樣一是可以少一個索引，二是冷熱資料容易分離。

   3 可以控制ShardingId。比如某一個使用者的文章要放在同一個分片内，這樣查詢效率高，修改也容易。

   4 不要太長，最好64bit。使用long比較好操作，如果是96bit，那就要各種移位相當的不友善，還有可能有些元件不能支援這麼大的ID。

一 twitter

twitter在把存儲系統從MySQL遷移到Cassandra的過程中由于Cassandra沒有順序ID生成機制，于是自己開發了一套全局唯一ID生成服務：Snowflake。

1 41位的時間序列（精确到毫秒，41位的長度可以使用69年）

2 10位的機器辨別（10位的長度最多支援部署1024個節點） 

3 12位的計數順序号（12位的計數順序号支援每個節點每毫秒産生4096個ID序号） 最高位是符号位，始終為0。

優點：高性能，低延遲；獨立的應用；按時間有序。 缺點：需要獨立的開發和部署。

原理

java 實作代碼

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

​ ​public​ ​  ​ ​class​ ​  ​ ​IdWorker {​ ​ ​ ​private​ ​  ​ ​final​ ​  ​ ​long​ ​  ​ ​workerId;​ ​ ​ ​private​ ​  ​ ​final​ ​  ​ ​static​ ​  ​ ​long​ ​  ​ ​twepoch = 1288834974657L;​ ​ ​ ​private​ ​  ​ ​long​ ​  ​ ​sequence = 0L;​ ​ ​ ​private​ ​  ​ ​final​ ​  ​ ​static​ ​  ​ ​long​ ​  ​ ​workerIdBits = 4L;​ ​ ​ ​public​ ​  ​ ​final​ ​  ​ ​static​ ​  ​ ​long​ ​  ​ ​maxWorkerId = -1L ^ -1L << workerIdBits;​ ​ ​ ​private​ ​  ​ ​final​ ​  ​ ​static​ ​  ​ ​long​ ​  ​ ​sequenceBits = 10L;​ ​ ​ ​private​ ​  ​ ​final​ ​  ​ ​static​ ​  ​ ​long​ ​  ​ ​workerIdShift = sequenceBits;​ ​ ​ ​private​ ​  ​ ​final​ ​  ​ ​static​ ​  ​ ​long​ ​  ​ ​timestampLeftShift = sequenceBits + workerIdBits;​ ​ ​ ​public​ ​  ​ ​final​ ​  ​ ​static​ ​  ​ ​long​ ​  ​ ​sequenceMask = -1L ^ -1L << sequenceBits;​ ​ ​ ​private​ ​  ​ ​long​ ​  ​ ​lastTimestamp = -1L;​ ​ ​ ​public​ ​  ​ ​IdWorker(​ ​ ​ ​final​ ​  ​ ​long​ ​  ​ ​workerId) {​ ​ ​ ​super​ ​ ​ ​();​ ​ ​ ​if​ ​  ​ ​(workerId > ​ ​ ​ ​this​ ​ ​ ​.maxWorkerId || workerId < ​ ​ ​ ​0​ ​ ​ ​) {​ ​ ​ ​throw​ ​  ​ ​new​ ​  ​ ​IllegalArgumentException(String.format(​ ​ ​ ​"worker Id can't be greater than %d or less than 0"​ ​ ​ ​,​ ​ ​ ​this​ ​ ​ ​.maxWorkerId));​ ​ ​ ​}​ ​ ​ ​this​ ​ ​ ​.workerId = workerId;​ ​ ​ ​}​ ​ ​ ​public​ ​  ​ ​synchronized​ ​  ​ ​long​ ​  ​ ​nextId() {​ ​ ​ ​long​ ​  ​ ​timestamp = ​ ​ ​ ​this​ ​ ​ ​.timeGen();​ ​ ​ ​if​ ​  ​ ​(​ ​ ​ ​this​ ​ ​ ​.lastTimestamp == timestamp) {​ ​ ​ ​this​ ​ ​ ​.sequence = (​ ​ ​ ​this​ ​ ​ ​.sequence + ​ ​ ​ ​1​ ​ ​ ​) & ​ ​ ​ ​this​ ​ ​ ​.sequenceMask;​ ​ ​ ​if​ ​  ​ ​(​ ​ ​ ​this​ ​ ​ ​.sequence == ​ ​ ​ ​0​ ​ ​ ​) {​ ​ ​ ​System.out.println(​ ​ ​ ​"###########"​ ​  ​ ​+ sequenceMask);​ ​ ​ ​timestamp = ​ ​ ​ ​this​ ​ ​ ​.tilNextMillis(​ ​ ​ ​this​ ​ ​ ​.lastTimestamp);​ ​ ​ ​}​ ​ ​ ​} ​ ​ ​ ​else​ ​  ​ ​{​ ​ ​ ​this​ ​ ​ ​.sequence = ​ ​ ​ ​0​ ​ ​ ​;​ ​ ​ ​}​ ​ ​ ​if​ ​  ​ ​(timestamp < ​ ​ ​ ​this​ ​ ​ ​.lastTimestamp) {​ ​ ​ ​try​ ​  ​ ​{​ ​ ​ ​throw​ ​  ​ ​new​ ​  ​ ​Exception(​ ​ ​ ​String.format(​ ​ ​ ​"Clock moved backwards. Refusing to generate id for %d milliseconds"​ ​ ​ ​,​ ​ ​ ​this​ ​ ​ ​.lastTimestamp - timestamp));​ ​ ​ ​} ​ ​ ​ ​catch​ ​  ​ ​(Exception e) {​ ​ ​ ​e.printStackTrace();​ ​ ​ ​}​ ​ ​ ​}​ ​ ​ ​this​ ​ ​ ​.lastTimestamp = timestamp;​ ​ ​ ​long​ ​  ​ ​nextId = ((timestamp - twepoch << timestampLeftShift))​ ​ ​ ​| (​ ​ ​ ​this​ ​ ​ ​.workerId << ​ ​ ​ ​this​ ​ ​ ​.workerIdShift) | (​ ​ ​ ​this​ ​ ​ ​.sequence);​ ​ ​ ​System.out.println(​ ​ ​ ​"timestamp:"​ ​  ​ ​+ timestamp + ​ ​ ​ ​",timestampLeftShift:"​ ​ ​ ​+ timestampLeftShift + ​ ​ ​ ​",nextId:"​ ​  ​ ​+ nextId + ​ ​ ​ ​",workerId:"​ ​ ​ ​+ workerId + ​ ​ ​ ​",sequence:"​ ​  ​ ​+ sequence);​ ​ ​ ​return​ ​  ​ ​nextId;​ ​ ​ ​}​ ​ ​ ​private​ ​  ​ ​long​ ​  ​ ​tilNextMillis(​ ​ ​ ​final​ ​  ​ ​long​ ​  ​ ​lastTimestamp) {​ ​ ​ ​long​ ​  ​ ​timestamp = ​ ​ ​ ​this​ ​ ​ ​.timeGen();​ ​ ​ ​while​ ​  ​ ​(timestamp <= lastTimestamp) {​ ​ ​ ​timestamp = ​ ​ ​ ​this​ ​ ​ ​.timeGen();​ ​ ​ ​}​ ​ ​ ​return​ ​  ​ ​timestamp;​ ​ ​ ​}​ ​ ​ ​private​ ​  ​ ​long​ ​  ​ ​timeGen() {​ ​ ​ ​return​ ​  ​ ​System.currentTimeMillis();​ ​ ​ ​}​ ​ ​ ​public​ ​  ​ ​static​ ​  ​ ​void​ ​  ​ ​main(String[] args){​ ​ ​ ​IdWorker worker2 = ​ ​ ​ ​new​ ​  ​ ​IdWorker(​ ​ ​ ​2​ ​ ​ ​);​ ​ ​ ​System.out.println(worker2.nextId());​ ​ ​ ​}​ ​ ​ ​}​ ​

2 來自Flicker的解決方案

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

Flicker在解決全局ID生成方案裡就采用了MySQL自增長ID的機制（auto_increment + replace into + MyISAM）。一個生成64位ID方案具體就是這樣的： 

先建立單獨的資料庫(eg:ticket)，然後建立一個表：

1 2 3 4 5 6

​ ​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 |

+-------------------+------+

在我們的應用端需要做下面這兩個操作，在一個事務會話裡送出：

1 2	​ ​REPLACE​ ​  ​ ​INTO​ ​  ​ ​Tickets64 (stub) ​ ​ ​ ​VALUES​ ​  ​ ​(​ ​ ​ ​'a'​ ​ ​ ​);​ ​ ​ ​SELECT​ ​  ​ ​LAST_INSERT_ID();​ ​

這樣我們就能拿到不斷增長且不重複的ID了。 

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

1 2 3 4 5 6 7

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

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

優點：充分借助資料庫的自增ID機制，提供高可靠性，生成的ID有序。

缺點：占用兩個獨立的MySQL執行個體，有些浪費資源，成本較高。

三 UUID

UUID生成的是length=32的16進制格式的字元串，如果回退為byte數組共16個byte元素，即UUID是一個128bit長的數字，

一般用16進制表示。

算法的核心思想是結合機器的網卡、當地時間、一個随即數來生成UUID。

從理論上講，如果一台機器每秒産生10000000個GUID，則可以保證（機率意義上）3240年不重複

優點：

（1）本地生成ID，不需要進行遠端調用，時延低

（2）擴充性好，基本可以認為沒有性能上限

缺點：

（1）無法保證趨勢遞增

（2）uuid過長，往往用字元串表示，作為主鍵建立索引查詢效率低，常見優化方案為“轉化為兩個uint64整數存儲”或者“折半存儲”（折半後不能保證唯一性）

四 基于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;

五 MongoDB文檔（Document）全局唯一ID

為了考慮分布式，“_id”要求不同的機器都能用全局唯一的同種方法友善的生成它。是以不能使用自增主鍵（需要多台伺服器進行同步，既費時又費力），

是以選用了生成ObjectId對象的方法。

ObjectId使用12位元組的存儲空間，其生成方式如下：

|0|1|2|3|4|5|6 |7|8|9|10|11|

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

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

 1 時間戳與後邊5個位元組一塊，保證秒級别的唯一性；

 2 保證插入順序大緻按時間排序；

 3 隐含了文檔建立時間；

 4 時間戳的實際值并不重要，不需要對伺服器之間的時間進行同步（因為加上機器ID和程序ID已保證此值唯一，唯一性是ObjectId的最終訴求）。

機器ID是伺服器主機辨別，通常是機器主機名的散列值。

同一台機器上可以運作多個mongod執行個體，是以也需要加入程序辨別符PID。