摘要：結(jié)合對(duì)做如下調(diào)整的毫秒時(shí)間戳的數(shù)據(jù)邏輯分區(qū)以及的自增序列。為了解決這個(gè)問題，便引入了邏輯分區(qū)。參考文章批量插入返回自增的問題美團(tuán)點(diǎn)評(píng)分布式生成系統(tǒng)

這里的博客版本都不會(huì)被更新維護(hù)。查看最新的版本請(qǐng)移步：http://neojos.com

全稱Universally Unique Identifier，UUID占128bit，也就是16個(gè)英文字符的長(zhǎng)度（16byte），需要強(qiáng)調(diào)的是，它的生成無需中心處理程序。

UUID被用來標(biāo)識(shí)URN(Uniform Resource Names)，對(duì)于Transaction ID以及其他需要唯一標(biāo)志的場(chǎng)景都可以使用它。

UUID是空間和時(shí)間上的唯一標(biāo)識(shí)，它長(zhǎng)度固定，內(nèi)部中包含時(shí)間信息。如果服務(wù)器時(shí)間存在不同步的情況，UUID可能會(huì)出現(xiàn)重復(fù)。

基本格式，由6部分組成：

time-low - time-mide - time-high-and-version - clock-seq-and-reserved & clock-seq-low - node

一個(gè)URN示例：f81d4fae-7dec-11d0-a765-00a0c91e6bf6。

因?yàn)?b>UUID占128bit，16進(jìn)制數(shù)占4bit，所以轉(zhuǎn)換成16進(jìn)制0-f的字符串總共有32位。組成的各個(gè)部分具體由幾位16進(jìn)制表示，請(qǐng)查閱 Namespace Registration Template

因?yàn)?b>UUID太長(zhǎng)且無序，導(dǎo)致其不適合做MySQL的主鍵索引。而且MySQL自帶的auto-increment功能，選擇bigint的話也只占用64bit。

All indexes other than the clustered index are known as secondary indexes. In InnoDB, each record in a secondary index contains the primary key columns for the row, as well as the columns specified for the secondary index. InnoDB uses this primary key value to search for the row in the clustered index.
If the primary key is long, the secondary indexes use more space, so it is advantageous to have a short primary key.

ObjectId由占4-byte的時(shí)間戳、3-byte的機(jī)器標(biāo)識(shí)、2-byte的進(jìn)程ID以及3-byte的計(jì)數(shù)組成，總共還是占用96bit。

這些ID組成包括時(shí)間、機(jī)器標(biāo)識(shí)、隨機(jī)數(shù)，在UUID生成時(shí)還使用到MAC地址。這些參數(shù)中時(shí)間是關(guān)鍵，保證集群服務(wù)器的時(shí)鐘準(zhǔn)確非常重要。

Twitter Snowflake生成的ID占64bit，跟bigint大小一致。由41 bit毫秒精度的時(shí)間戳、10bit的機(jī)器ID以及12 bit的序列號(hào)組成（計(jì)數(shù)每4096就重新開始一輪），剩下的1 bit奉獻(xiàn)給未來。

作者修改了它的原始設(shè)定，將剩下的1 bit給了時(shí)間戳。使用機(jī)器MAC地址的HASH值作為當(dāng)前機(jī)器的ID。

服務(wù)全局保存最近一次生成ID的時(shí)間戳lastTimestamp，作為生成新ID的判斷依據(jù)，避免時(shí)間回溯。詳細(xì)代碼請(qǐng)參照[1]。

// Block and wait till next millisecond
private long waitNextMillis(long currentTimestamp) {
    while (currentTimestamp == lastTimestamp) {
        currentTimestamp = timestamp();
    }
    return currentTimestamp;
}

同時(shí)將sequence也聲明為全局變量，每間隔4096次就重新開始計(jì)數(shù)。主要用于應(yīng)對(duì)：當(dāng)時(shí)間戳相同時(shí)保證生成的ID是不同的。

if (currentTimestamp == lastTimestamp) {
    sequence = (sequence + 1) & maxSequence;
    if(sequence == 0) {
        // Sequence Exhausted, wait till next millisecond.
        currentTimestamp = waitNextMillis(currentTimestamp);
    }
} else {
    // reset sequence to start with zero for the next millisecond
    sequence = 0;
}

該方式通過中心的DB服務(wù)來生成唯一自增ID，但DB服務(wù)的寫操作會(huì)成為系統(tǒng)的瓶頸。如果后臺(tái)是單個(gè)DB服務(wù)的話，存在單點(diǎn)問題。

參考Flickr的方法，后臺(tái)使用兩個(gè)DB來生成ID，其中auto-increment一個(gè)按照奇數(shù)步長(zhǎng)增長(zhǎng)，另一個(gè)按照偶數(shù)步長(zhǎng)增長(zhǎng)。MySQL內(nèi)部使用REPLACE來實(shí)現(xiàn)，通過一條沖突的記錄，來持續(xù)生成自增的主鍵ID。

REPLACE makes sense only if a table has a PRIMARY KEY or UNIQUE index. Otherwise, it becomes equivalent to INSERT, because there is no index to be used to determine whether a new row duplicates another.

結(jié)合Twitter Snowflake對(duì)ID做如下調(diào)整：41-bit的毫秒時(shí)間戳、13-bit的數(shù)據(jù)邏輯分區(qū)以及10-bit的自增序列。自增序列對(duì)1024取余，每個(gè)分區(qū)每毫秒內(nèi)能生成1024個(gè)自增ID。

Flickr中各個(gè)數(shù)據(jù)表按照不同的步長(zhǎng)增長(zhǎng)，當(dāng)需要分表的時(shí)候就會(huì)存在巨復(fù)雜的數(shù)據(jù)遷移問題。為了解決這個(gè)問題，便引入了邏輯分區(qū)Shard ID。通過邏輯上的Shard，將數(shù)據(jù)分散在不同的數(shù)據(jù)表中。這樣后續(xù)的分庫(kù)分表都可以通過操作邏輯上Shard來實(shí)現(xiàn)，將DB從具體的實(shí)現(xiàn)中解脫出來。

關(guān)于獲取MySQL自增ID，代碼無法批量獲取插入的全部自增ID列表，MySQL只會(huì)返回第一條記錄的自增ID。因?yàn)樽栽?b>ID是連續(xù)的，所以可以通過計(jì)算的方式來計(jì)算出ID列表。

If you insert multiple rows using a single INSERT statement, LAST_INSERT_ID() returns the value generated for the first inserted row only. The reason for this is to make it possible to reproduce easily the same INSERT statement against some other server.

關(guān)于Shard可以查看本地緩存BigCache，很有參考意義（我覺得）。

文中介紹了ID的兩種生成方式，核心的區(qū)別在于：整個(gè)系統(tǒng)的ID是否支持單調(diào)遞增。Twitter Snowflake以及UUID可以保證生成的數(shù)據(jù)唯一，但多臺(tái)服務(wù)器的話，無法保證生成的數(shù)據(jù)有序。而Ticket Servers通過結(jié)合MySQL的auto-increment解決了這個(gè)問題。

參考文章：

Generating unique IDs in a distributed environment at high scale

A Universally Unique IDentifier (UUID) URN Namespace

Clustered and Secondary Indexes

Sharding & IDs at Instagram

Ticket Server: Distributed Unique Primary Keys on the Cheap

MySQL批量插入返回自增ID的問題

Leaf——美團(tuán)點(diǎn)評(píng)分布式ID生成系統(tǒng)