Entrance

• 數(shù)據(jù)在分片時，典型的是分庫分表，就有一個全局ID生成的問題。
• 單純的生成全局ID并不是什么難題，但是生成的ID通常要滿足分片的一些要求

要求

• 不能有單點故障。
• 以時間為序，或者ID里包含時間。這樣一是可以少一個索引，二是冷熱數(shù)據(jù)容易分離。
• 可以控制ShardingId。比如某一個用戶的文章要放在同一個分片內(nèi)，這樣查詢效率高，修改也容易。
• 不要太長，最好64bit。使用long比較好操作，如果是96bit，那就要各種移位相當(dāng)?shù)牟环奖?，還有可能有些組件不能支持這么大的ID。

twitter

Entrance

• twitter在把存儲系統(tǒng)從MySQL遷移到Cassandra的過程中由于Cassandra沒有順序ID生成機(jī)制，于是自己開發(fā)了一套全局唯一ID生成服務(wù)：Snowflake。
• 1. 41位的時間序列（精確到毫秒，41位的長度可以使用69年）
• 2. 10位的機(jī)器標(biāo)識（10位的長度最多支持部署1024個節(jié)點）
• 3. 12位的計數(shù)順序號（12位的計數(shù)順序號支持每個節(jié)點每毫秒產(chǎn)生4096個ID序號） 最高位是符號位，始終為0。
• 優(yōu)點：高性能，低延遲；獨立的應(yīng)用；按時間有序。 缺點：需要獨立的開發(fā)和部署。

代碼示例

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());
}

}        

來自Flicker的解決方案

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

• 因為MySQL本身支持auto_increment操作，很自然地，我們會想到借助這個特性來實現(xiàn)這個功能。
• Flicker在解決全局ID生成方案里就采用了MySQL自增長ID的機(jī)制（auto_increment + replace into + MyISAM）。一個生成64位ID方案具體就是這樣的：
  先創(chuàng)建單獨的數(shù)據(jù)庫(eg:ticket)，然后創(chuàng)建了Tickets64這個表

cluster

+-------------------+------+
| id | stub |
+-------------------+------+
| 72157623227190423 | a |
+-------------------+------+

• 當(dāng)我們插入記錄后，執(zhí)行SELECT * from Tickets64，查詢結(jié)果就是如上的

cluster

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

• 在我們的應(yīng)用端需要做下面這兩個操作，在一個事務(wù)會話里提交,這樣我們就能拿到不斷增長且不重復(fù)的ID了

cluster

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

• 到上面為止，我們只是在單臺數(shù)據(jù)庫上生成ID，從高可用角度考慮，接下來就要解決單點故障問題
• Flicker啟用了兩臺數(shù)據(jù)庫服務(wù)器來生成ID，通過區(qū)分auto_increment的起始值和步長來生成奇偶數(shù)的ID
• 最后，在客戶端只需要通過輪詢方式取ID就可以了
• 優(yōu)點：充分借助數(shù)據(jù)庫的自增ID機(jī)制，提供高可靠性，生成的ID有序
• 缺點：占用兩個獨立的MySQL實例，有些浪費資源，成本較高

UUID

• UUID生成的是length=32的16進(jìn)制格式的字符串，如果回退為byte數(shù)組共16個byte元素，即UUID是一個128bit長的數(shù)字，
• 一般用16進(jìn)制表示。
• 算法的核心思想是結(jié)合機(jī)器的網(wǎng)卡、當(dāng)?shù)貢r間、一個隨即數(shù)來生成UUID
• 從理論上講，如果一臺機(jī)器每秒產(chǎn)生10000000個GUID，則可以保證（概率意義上）3240年不重復(fù)

優(yōu)點

1. 本地生成ID，不需要進(jìn)行遠(yuǎn)程調(diào)用，時延低
2. 擴(kuò)展性好，基本可以認(rèn)為沒有性能上限

缺點

1. 無法保證趨勢遞增
2. uuid過長，往往用字符串表示，作為主鍵建立索引查詢效率低，常見優(yōu)化方案為“轉(zhuǎn)化為兩個uint64整數(shù)存儲”或者“折半存儲”（折半后不能保證唯一性）

基于redis的分布式ID生成器

entrance

redis的EVAL，EVALSHA命令的原理是利用redis的lua腳本執(zhí)行功能，在每個節(jié)點上通過lua腳本生成唯一ID

關(guān)于生成的ID##

• 使用41 bit來存放時間，精確到毫秒，可以使用41年。
• 使用12 bit來存放邏輯分片ID，最大分片ID是4095
• 使用10 bit來存放自增長ID，意味著每個節(jié)點，每毫秒最多可以生成1024個ID

舉例

• 比如GTM時間 Fri Mar 13 10:00:00 CST 2015 ，它的距1970年的毫秒數(shù)是 1426212000000，假定分片ID是53，自增長序列是4，則生成的ID是：
• 5981966696448054276 = 1426212000000 << 22 + 53 << 10 + 41

cluster

• redis提供了TIME命令，可以取得redis服務(wù)器上的秒數(shù)和微秒數(shù)。因些lua腳本返回的是一個四元組。second, microSecond, partition, seq，客戶端要自己處理，生成最終I。
• ((second * 1000 + microSecond / 1000) << (12 + 10)) + (shardId << 10) + seq;

MongoDB文檔（Document）全局唯一ID

• 為了考慮分布式，“_id”要求不同的機(jī)器都能用全局唯一的同種方法方便的生成它。因此不能使用自增主鍵（需要多臺服務(wù)器進(jìn)行同步，既費時又費力），因此選用了生成ObjectId對象的方法
• ObjectId使用12字節(jié)的存儲空間

生成方式

|0|1|2|3|4|5|6 |7|8|9|10|11|
|時間戳 |機(jī)器ID|PID|計數(shù)器 |

• 前四個字節(jié)時間戳是從標(biāo)準(zhǔn)紀(jì)元開始的時間戳，單位為秒，有如下特性：
• 1.時間戳與后邊5個字節(jié)一塊，保證秒級別的唯一性
• 2.保證插入順序大致按時間排序
• 3.隱含了文檔創(chuàng)建時間
• 4.時間戳的實際值并不重要，不需要對服務(wù)器之間的時間進(jìn)行同步（因為加上機(jī)器ID和進(jìn)程ID已保證此值唯一，唯一性是ObjectId的最終訴求）

cluster

• 機(jī)器ID是服務(wù)器主機(jī)標(biāo)識，通常是機(jī)器主機(jī)名的散列值
• 同一臺機(jī)器上可以運行多個mongod實例，因此也需要加入進(jìn)程標(biāo)識符PID
• 前9個字節(jié)保證了同一秒鐘不同機(jī)器不同進(jìn)程產(chǎn)生的ObjectId的唯一性。后三個字節(jié)是一個自動增加的計數(shù)器（一個mongod進(jìn)程需要一個全局的計數(shù)器），保證同一秒的ObjectId是唯一的。同一秒鐘最多允許每個進(jìn)程擁有（256^3 = 16777216）個不同的ObjectId

總結(jié)

• 時間戳保證秒級唯一，機(jī)器ID保證設(shè)計時考慮分布式，避免時鐘同步，PID保證同一臺服務(wù)器運行多個mongod實例時的唯一性，最后的計數(shù)器保證同一秒內(nèi)的唯一性（選用幾個字節(jié)既要考慮存儲的經(jīng)濟(jì)性，也要考慮并發(fā)性能的上限）。
• "_id"既可以在服務(wù)器端生成也可以在客戶端生成，在客戶端生成可以降低服務(wù)器端的壓力。