背景

分布式場景下需要一個全局 ID 來標識唯一性，比如在單數(shù)據(jù)庫時通過表唯一主鍵即可實現(xiàn)唯一 ID，分庫分表時就需要全局唯一 ID。

業(yè)務對唯一 ID 的要求如下：

• 全局唯一性

不能出現(xiàn)重復的 ID 號，既然是唯一標識，這是最基本的要求。

• 趨勢遞增、單調(diào)遞增

保證下一個 ID 一定大于上一個 ID。

• 信息安全

如果 ID 是連續(xù)的，惡意用戶的扒取工作就非常容易做了，直接按照順序下載指定 URL 即可；
如果是訂單號就更危險了，競對可以直接知道我們一天的單量。所以在一些應用場景下，會需要 ID 無規(guī)則、不規(guī)則。

同時除了對 ID 號碼自身的要求，業(yè)務還對 ID 號生成系統(tǒng)的可用性要求極高。想象一下，如果 ID 生成系統(tǒng)不穩(wěn)定，大量依賴 ID 生成系統(tǒng)，比如訂單生成等關(guān)鍵動作都無法執(zhí)行。所以一個 ID 生成系統(tǒng)還需要做到平均延遲和 TP999 延遲都要盡可能低。最好能達到可用性 5 個 9、高 QPS。

方案

UUID

UUID（Universally Unique Identifier）的標準型式包含 32 個 16 進制數(shù)字，以連字號分為五段，形式為 8-4-4-4-12 的 36 個字符，示例：550e8400-e29b-41d4-a716-446655440000，到目前為止業(yè)界一共有 5 種方式生成 UUID，詳情見 IETF 發(fā)布的 UUID 規(guī)范 A Universally Unique IDentifier (UUID) URN Namespace。

優(yōu)點：

• 性能非常高：本地生成，沒有網(wǎng)絡消耗。

缺點：

• 不易于存儲：UUID 太長，16 字節(jié) 128 位，通常以 36 長度的字符串表示，很多場景不適用。
• 信息不安全：基于 MAC 地址生成 UUID 的算法可能會造成 MAC 地址泄露，這個漏洞曾被用于尋找梅麗莎病毒的制作者位置。
• ID 作為主鍵時在特定的環(huán)境會存在一些問題，比如做 DB 主鍵的場景下，UUID 就非常不適用：

1、MySQL 官方有明確的建議主鍵要盡量越短越好[4]，36 個字符長度的 UUID 不符合要求。
2、對 MySQL 索引不利：如果作為數(shù)據(jù)庫主鍵，在 InnoDB 引擎下，UUID 的無序性可能會引起數(shù)據(jù)位置頻繁變動，嚴重影響性能。在 MySQL InnoDB 引擎中使用的是聚集索引，由于多數(shù) RDBMS 使用 B-tree 的數(shù)據(jù)結(jié)構(gòu)來存儲索引數(shù)據(jù)，在主鍵的選擇上面我們應該盡量使用有序的主鍵保證寫入性能。

可以直接使用 jdk 自帶的 UUID，原始生成的是帶中劃線的，如果不需要，可自行去除：

public class UUIDTest {public static void main(String[] args) {String uuid = UUID.randomUUID().toString();System.out.println(uuid);uuid = uuid.replaceAll("-", "");System.out.println(uuid);/*** f5d728aa-5c07-4fb5-bf58-18c232d2fae8* f5d728aa5c074fb5bf5818c232d2fae8*/}
}

雪花算法

這種方案大致來說是一種以劃分命名空間（UUID 也算，由于比較常見，所以單獨分析）來生成 ID 的一種算法，Snowflake 是 Twitter 開源的分布式 ID 生成算法。Snowflake 把 64-bit 分別劃分成多段，分開來標示機器、時間等，比如在 snowflake 中的 64-bit 分別表示如下圖所示：

第 0 位：符號位（標識正負），始終為 0，沒有用，不用管。
第 1~41 位：一共 41 位，用來表示時間戳，單位是毫秒，可以支撐 2 ^41 毫秒（約 69 年）。
第 42~52 位：一共 10 位，一般來說，前 5 位表示機房 ID，后 5 位表示機器 ID（實際項目中可以根據(jù)實際情況調(diào)整），這樣就可以區(qū)分不同集群/機房的節(jié)點，這樣就可以表示 32 個 IDC，每個 IDC 下可以有 32 臺機器。
第 53~64 位：一共 12 位，用來表示序列號。 序列號為自增值，代表單臺機器每毫秒能夠產(chǎn)生的最大 ID 數(shù)(2^12 = 4096)，也就是說單臺機器每毫秒最多可以生成 4096 個 唯一 ID。
理論上 snowflake 方案的 QPS 約為 409.6w/s，這種分配方式可以保證在任何一個 IDC 的任何一臺機器在任意毫秒內(nèi)生成的 ID 都是不同的。
有很多基于 Snowflake 算法的開源實現(xiàn)比如美團的 Leaf、百度的 UidGenerator（自 18 年后，UidGenerator 就基本沒有再維護了，[https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md](https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md))），并且這些開源實現(xiàn)對原有的 Snowflake 算法進行了優(yōu)化。在實際項目中，我們一般也會對 Snowflake 算法進行改造，最常見的就是在算法生成的 ID 中加入業(yè)務類型信息。

優(yōu)點：

• 毫秒數(shù)在高位，自增序列在低位，整個 ID 都是趨勢遞增的。
• 不依賴數(shù)據(jù)庫等第三方系統(tǒng)，以服務的方式部署，穩(wěn)定性更高，生成 ID 的性能也是非常高的。
• 可以根據(jù)自身業(yè)務特性分配 bit 位，非常靈活。

缺點：

• 強依賴機器時鐘，如果機器上時鐘回撥，會導致發(fā)號重復或者服務會處于不可用狀態(tài)。

當然，在我們自己的項目如果不想自行實現(xiàn)唯一性 ID，還可以利用外部中間件，比如 Mongdb objectID，它也可以算作是和 snowflake 類似方法，通過“時間+機器碼+pid+inc”共 12 個字節(jié)，通過 4+3+2+3 的方式最終標識成一個 24 長度的十六進制字符。
其次 Seata 內(nèi)置了一個分布式 UUID 生成器，用于輔助生成全局事務 ID 和分支事務 ID，我們同樣可以拿來使用，完整類名為：io.seata.common.util.IdWorker。

MYSQL

1） 創(chuàng)建一個數(shù)據(jù)庫表

CREATE TABLE `sequence_id` (`id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,`stub` char(10) NOT NULL DEFAULT '',PRIMARY KEY (`id`),UNIQUE KEY `stub` (`stub`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

stub 字段無意義，只是為了占位，便于我們插入或者修改數(shù)據(jù)。并且，給 stub 字段創(chuàng)建了唯一索引，保證其唯一性。
2）通過 replace into 來插入數(shù)據(jù)

BEGIN;
REPLACE INTO sequence_id (stub) VALUES ('stub');
SELECT LAST_INSERT_ID();
COMMIT;

插入數(shù)據(jù)這里，我們沒有使用 insert into 而是使用 replace into 來插入數(shù)據(jù)。replace 是 insert 的增強版，replace into 首先嘗試插入數(shù)據(jù)到表中，如果發(fā)現(xiàn)表中已經(jīng)有此行數(shù)據(jù)（根據(jù)主鍵或者唯一索引判斷）則先刪除此行數(shù)據(jù)，然后插入新的數(shù)據(jù)。否則，直接插入新數(shù)據(jù)。重復插入失敗時是會生成新的 ID 的。

優(yōu)點：

• 非常簡單，利用現(xiàn)有數(shù)據(jù)庫系統(tǒng)的功能實現(xiàn)，成本小，有 DBA 專業(yè)維護。ID 號單調(diào)自增，存儲消耗空間小。

缺點：

• 支持的并發(fā)量不大、存在數(shù)據(jù)庫單點問題（可以使用數(shù)據(jù)庫集群解決，不過增加了復雜度）
• ID 沒有具體業(yè)務含義
• 安全問題（比如根據(jù)訂單 ID 的遞增規(guī)律就能推算出每天的訂單量，商業(yè)機密啊！ ）
• 每次獲取 ID 都要訪問一次數(shù)據(jù)庫（增加了對數(shù)據(jù)庫的壓力，獲取速度也慢）

對于 MySQL 性能問題，可用如下方案解決：在分布式系統(tǒng)中我們可以多部署幾臺機器，每臺機器設置不同的初始值，且步長和機器數(shù)相等。比如有兩臺機器。設置步長 step 為 2，TicketServer1 的初始值為 1（1，3，5，7，9，11…）、TicketServer2 的初始值為 2（2，4，6，8，10…）。這是 Flickr（雅虎旗下圖片分享網(wǎng)站）團隊在 2010 年撰文介紹的一種主鍵生成策略（Ticket Servers: Distributed Unique Primary Keys on the Cheap ）。為了實現(xiàn)上述方案分別設置兩臺機器對應的參數(shù)，TicketServer1 從 1 開始發(fā)號，TicketServer2 從 2 開始發(fā)號，兩臺機器每次發(fā)號之后都遞增 2。
假設我們要部署 N 臺機器，步長需設置為 N，每臺的初始值依次為 0,1,2…N-1。
這種架構(gòu)貌似能夠滿足性能的需求，但有以下幾個缺點：
系統(tǒng)水平擴展比較困難，比如定義好了步長和機器臺數(shù)之后，如果要添加機器該怎么做？假設現(xiàn)在只有一臺機器發(fā)號是 1，2，3，4，5（步長是 1），這個時候需要擴容機器一臺?？梢赃@樣做：把第二臺機器的初始值設置得比第一臺超過很多，比如 140（假設在擴容時間之內(nèi)第一臺不可能發(fā)到 140），同時設置步長為 2，那么這臺機器下發(fā)的號碼都是 140 以后的偶數(shù)。然后摘掉第一臺，把 ID 值保留為奇數(shù)，比如 7，然后修改第一臺的步長為 2。讓它符合我們定義的號段標準，對于這個例子來說就是讓第一臺以后只能產(chǎn)生奇數(shù)。擴容方案看起來復雜嗎？貌似還好，現(xiàn)在想象一下如果我們線上有 100 臺機器，這個時候要擴容該怎么做？簡直是噩夢。所以系統(tǒng)水平擴展方案復雜難以實現(xiàn)。
ID 沒有了單調(diào)遞增的特性，只能趨勢遞增，這個缺點對于一般業(yè)務需求不是很重要，可以容忍。
數(shù)據(jù)庫壓力還是很大，每次獲取 ID 都得讀寫一次數(shù)據(jù)庫，只能靠堆機器來提高性能。

Redis

通過 Redis 的 incr 命令即可實現(xiàn)對 id 原子順序遞增，例如：

127.0.0.1:6379> incr sequence_id_biz_type
(integer) 2

為了提高可用性和并發(fā)，我們可以使用 Redis Cluster。
除了高可用和并發(fā)之外，我們知道 Redis 基于內(nèi)存，我們需要持久化數(shù)據(jù)，避免重啟機器或者機器故障后數(shù)據(jù)丟失。很明顯，Redis 方案性能很好并且生成的 ID 是有序遞增的。
不過，我們也知道，即使 Redis 開啟了持久化，不管是快照（snapshotting，RDB）、只追加文件（append-only file, AOF）還是 RDB 和 AOF 的混合持久化依然存在著丟失數(shù)據(jù)的可能，那就意味著產(chǎn)生的 ID 存在著重復的概率。

美團 Leaf

Leaf 這個名字是來自德國哲學家、數(shù)學家萊布尼茨的一句話： There are no two identical leaves in the world（世界上沒有兩片相同的樹葉）。
Leaf 分別在 MySQL 和雪花上做了相應的優(yōu)化，實現(xiàn)了 Leaf-segment 和 Leaf-snowflake 方案。

Leaf-segment

Leaf-segment 方案，在使用數(shù)據(jù)庫的方案上，做了如下改變：
原 MySQL 方案每次獲取 ID 都得讀寫一次數(shù)據(jù)庫，造成數(shù)據(jù)庫壓力大。改為批量獲取，每次獲取一個 segment（step 決定大小）號段的值。用完之后再去數(shù)據(jù)庫獲取新的號段，可以大大的減輕數(shù)據(jù)庫的壓力。
各個業(yè)務不同的發(fā)號需求用 biz_tag 字段來區(qū)分，每個 biz_tag 的 ID 獲取相互隔離，互不影響。如果以后有性能需求需要對數(shù)據(jù)庫擴容，不需要上述描述的復雜的擴容操作，只需要對 biz_tag 分庫分表就行。
數(shù)據(jù)庫表設計如下：

重要字段說明：
biz_tag：用來區(qū)分業(yè)務；
max_id：表示該 biz_tag 目前所被分配的 ID 號段的最大值；
step：表示每次分配的號段長度。
原來獲取 ID 每次都需要寫數(shù)據(jù)庫，現(xiàn)在只需要把 step 設置得足夠大，比如 1000。那么只有當 1000 個號被消耗完了之后才會去重新讀寫一次數(shù)據(jù)庫。讀寫數(shù)據(jù)庫的頻率從 1 減小到了1/step。
例如現(xiàn)在有 3 臺機器，每臺機器各取 1000 個，很明顯在第一臺 Leaf 機器上是 1~1000 的號段，當這個號段用完時，會去加載另一個長度為 step=1000 的號段，假設另外兩臺號段都沒有更新，這個時候第一臺機器新加載的號段就應該是3001~4000。同時數(shù)據(jù)庫對應的 biz_tag 這條數(shù)據(jù)的 max_id 會從 3000 被更新成4000，更新號段的 SQL 語句如下：

Begin
UPDATE table SET max_id=max_id+step WHERE biz_tag=xxx
SELECT tag, max_id, step FROM table WHERE biz_tag=xxx
Commit

優(yōu)點：

• Leaf 服務可以很方便的線性擴展，性能完全能夠支撐大多數(shù)業(yè)務場景。
• ID 號碼是趨勢遞增的 8byte 的 64 位數(shù)字，滿足上述數(shù)據(jù)庫存儲的主鍵要求。
• 容災性高：Leaf 服務內(nèi)部有號段緩存，即使 DB 宕機，短時間內(nèi) Leaf 仍能正常對外提供服務?？梢宰远x max_id 的大小，非常方便業(yè)務從原有的 ID 方式上遷移過來。

缺點：

• ID 號碼不夠隨機，能夠泄露發(fā)號數(shù)量的信息，不太安全。
• TP999 數(shù)據(jù)波動大，當號段使用完之后還是會在獲取新號段時在更新數(shù)據(jù)庫的 I/O 依然會存在著等待，tg999 數(shù)據(jù)會出現(xiàn)偶爾的尖刺。
• DB 宕機會造成整個系統(tǒng)不可用。

雙 buffer 優(yōu)化：
對于第二個缺點，Leaf-segment 做了一些優(yōu)化，簡單的說就是：
Leaf 取號段的時機是在號段消耗完的時候進行的，也就意味著號段臨界點的 ID 下發(fā)時間取決于下一次從 DB 取回號段的時間，并且在這期間進來的請求也會因為 DB 號段沒有取回來，導致線程阻塞。如果請求 DB 的網(wǎng)絡和 DB 的性能穩(wěn)定，這種情況對系統(tǒng)的影響是不大的，但是假如取 DB 的時候網(wǎng)絡發(fā)生抖動，或者 DB 發(fā)生慢查詢就會導致整個系統(tǒng)的響應時間變慢。
為此，希望 DB 取號段的過程能夠做到無阻塞，不需要在 DB 取號段的時候阻塞請求線程，即當號段消費到某個點時就異步的把下一個號段加載到內(nèi)存中。而不需要等到號段用盡的時候才去更新號段。這樣做就可以很大程度上的降低系統(tǒng)的 TP999 指標。
采用雙 buffer 的方式，Leaf 服務內(nèi)部有兩個號段緩存區(qū) segment。當前號段已下發(fā) 10%時，如果下一個號段未更新，則另啟一個更新線程去更新下一個號段。當前號段全部下發(fā)完后，如果下個號段準備好了則切換到下個號段為當前 segment 接著下發(fā)，循環(huán)往復。
通常推薦 segment 長度設置為服務高峰期發(fā)號 QPS 的 600 倍（10 分鐘），這樣即使 DB 宕機，Leaf 仍能持續(xù)發(fā)號 10-20 分鐘不受影響。
每次請求來臨時都會判斷下個號段的狀態(tài)，從而更新此號段，所以偶爾的網(wǎng)絡抖動不會影響下個號段的更新。

Leaf 高可用容災：
對于第三點“DB 可用性”問題，可以采用一主兩從的方式，同時分機房部署，Master 和 Slave 之間采用半同步方式同步數(shù)據(jù)。美團內(nèi)部使用了奇虎 360 的 Atlas 數(shù)據(jù)庫中間件（已開源，改名為 DBProxy）做主從切換。當然這種方案在一些情況會退化成異步模式，甚至在非常極端情況下仍然會造成數(shù)據(jù)不一致的情況，但是出現(xiàn)的概率非常小。如果要保證 100% 的數(shù)據(jù)強一致，可以選擇使用“類 Paxos算法”實現(xiàn)的強一致 MySQL 方案，如 MySQL 5.7 中的 MySQL Group Replication。但是運維成本和精力都會相應的增加，根據(jù)實際情況選型即可。

Leaf-snowflake

Leaf-segment 方案可以生成趨勢遞增的 ID，同時 ID 號是可計算的，不適用于訂單 ID 生成場景，比如競對在兩天中午 12 點分別下單，通過訂單 id 號相減就能大致計算出公司一天的訂單量，這個是不能忍受的。面對這一問題，美團提供了 Leaf-snowflake 方案。
Leaf-snowflake 方案完全沿用 snowflake 方案的 bit 位設計，即是“1+41+10+12”的方式組裝 ID 號。對于 workerID 的分配，當服務集群數(shù)量較小的情況下，完全可以手動配置。Leaf 服務規(guī)模較大，動手配置成本太高。所以使用 Zookeeper 持久順序節(jié)點的特性自動對 snowflake 節(jié)點配置 wokerID。Leaf-snowflake 是按照下面幾個步驟啟動的：
啟動 Leaf-snowflake 服務，連接 Zookeeper，在 leaf_forever 父節(jié)點下檢查自己是否已經(jīng)注冊過（是否有該順序子節(jié)點）。
如果有注冊過直接取回自己的 workerID（zk 順序節(jié)點生成的 int 類型 ID 號），啟動服務。
如果沒有注冊過，就在該父節(jié)點下面創(chuàng)建一個持久順序節(jié)點，創(chuàng)建成功后取回順序號當做自己的 workerID 號，啟動服務。

弱依賴 ZooKeeper：
除了每次會去 ZK 拿數(shù)據(jù)以外，也會在本機文件系統(tǒng)上緩存一個 workerID 文件。當 ZooKeeper 出現(xiàn)問題，恰好機器出現(xiàn)問題需要重啟時，能保證服務能夠正常啟動。這樣做到了對三方組件的弱依賴。

解決時鐘問題：
因為這種方案依賴時間，如果機器的時鐘發(fā)生了回撥，那么就會有可能生成重復的 ID 號，需要解決時鐘回退的問題。
首先在啟動時，服務會進行檢查：
1、新節(jié)點通過檢查綜合對比其余 Leaf 節(jié)點的系統(tǒng)時間來判斷自身系統(tǒng)時間是否準確，具體做法是取所有運行中的 Leaf-snowflake 節(jié)點的服務 IP:Port，然后通過 RPC 請求得到所有節(jié)點的系統(tǒng)時間，計算 sum(time)/nodeSize，然后看本機時間與這個平均值是否在閾值之內(nèi)來確定當前系統(tǒng)時間是否準確，準確正常啟動服務，不準確認為本機系統(tǒng)時間發(fā)生大步長偏移，啟動失敗并報警。
2、在 ZooKeeper 中登記過的老節(jié)點，同樣會比較自身系統(tǒng)時間和 ZooKeeper 上本節(jié)點曾經(jīng)的記錄時間以及所有運行中的 Leaf-snowflake 節(jié)點的時間，不準確同樣啟動失敗并報警。
另外，在運行過程中，每隔一段時間節(jié)點都會上報自身系統(tǒng)時間寫入 ZooKeeper 。
在服務運行過程中，機器的 NTP 同步也會造成秒級別的回退，由于強依賴時鐘，對時間的要求比較敏感，美團建議有三種解決方案，一是可以直接關(guān)閉 NTP 同步；二是在時鐘回撥的時候直接不提供服務直接返回 ERROR_CODE，等時鐘追上即可，三是做一層重試，然后上報報警系統(tǒng)，更或者是發(fā)現(xiàn)有時鐘回撥之后自動摘除本身節(jié)點并報警。
從美團的實際運行情況來看，在 2017 年閏秒出現(xiàn)那一次出現(xiàn)過部分機器回撥，由于 Leaf-snowflake 的策略保證，成功避免了對業(yè)務造成的影響。

美團 Leaf 現(xiàn)狀：
Leaf 在美團點評公司內(nèi)部服務包含金融、支付交易、餐飲、外賣、酒店旅游、貓眼電影等眾多業(yè)務線。目前 Leaf 的性能在 4C8G 的機器上 QPS 能壓測到近 5萬/s，TP999 1ms，已經(jīng)能夠滿足大部分的業(yè)務的需求。每天提供億數(shù)量級的調(diào)用量。