為什么分布式系統(tǒng)需要用到ID生成系統(tǒng)
在復(fù)雜分布式系統(tǒng)中，往往需要對大量的數(shù)據(jù)和消息進(jìn)行唯一標(biāo)識魄健。如在美團(tuán)點(diǎn)評的金融赋铝、支付、餐飲沽瘦、酒店革骨、貓眼電影等產(chǎn)品的系統(tǒng)中，數(shù)據(jù)日漸增長析恋，對數(shù)據(jù)庫的分庫分表后需要有一個(gè)唯一ID來標(biāo)識一條數(shù)據(jù)或消息良哲，數(shù)據(jù)庫的自增ID顯然不能滿足需求；特別一點(diǎn)的如訂單助隧、騎手筑凫、優(yōu)惠券也都需要有唯一ID做標(biāo)識。此時(shí)一個(gè)能夠生成全局唯一ID的系統(tǒng)是非常必要的并村。
概括下來巍实，業(yè)務(wù)系統(tǒng)對ID號的要求有哪些呢？
ID生成系統(tǒng)的需求
1.全局唯一性：不能出現(xiàn)重復(fù)的ID哩牍，最基本的要求棚潦。
2.趨勢遞增：MySQL InnoDB引擎使用的是聚集索引，由于多數(shù)RDBMS使用B-tree的數(shù)據(jù)結(jié)構(gòu)來存儲索引數(shù)據(jù)姐叁，在主鍵的選擇上面我們應(yīng)盡量使用有序的主鍵保證寫入性能瓦盛。
3.單調(diào)遞增：保證下一個(gè)ID一定大于上一個(gè)ID。
4.信息安全：如果ID是連續(xù)遞增的外潜，惡意用戶就可以很容易的窺見訂單號的規(guī)則原环，從而猜出下一個(gè)訂單號，如果是競爭對手处窥，就可以直接知道我們一天的訂單量嘱吗。所以在某些場景下，需要ID無規(guī)則滔驾。
第3谒麦、4兩個(gè)需求是互斥的，無法同時(shí)滿足哆致。
同時(shí)绕德，在大型分布式網(wǎng)站架構(gòu)中，除了需要滿足ID生成自身的需求外摊阀，還需要ID生成系統(tǒng)可用性極高耻蛇。想象以下踪蹬，如果ID生成系統(tǒng)癱瘓，那么整個(gè)業(yè)務(wù)無法進(jìn)行下去臣咖，那將是一次災(zāi)難跃捣。
因此，總結(jié)ID生成系統(tǒng)還需要滿足如下的需求：
1.高可用夺蛇，可用性達(dá)到5個(gè)9或4個(gè)9疚漆。
2.高QPS，性能不能太差刁赦，否則容易造成線程堵塞娶聘。
3.平均延遲和TP999(保證99.9%的請求都能成功的最低延遲)延遲都要盡可能低。
ID生成系統(tǒng)的類型
UUID
UUID是指在一臺機(jī)器在同一時(shí)間中生成的數(shù)字在所有機(jī)器中都是唯一的截型。按照開放軟件基金會(huì)(OSF)制定的標(biāo)準(zhǔn)計(jì)算趴荸，用到了以太網(wǎng)卡地址、納秒級時(shí)間宦焦、芯片ID碼和許多可能的數(shù)字
UUID由以下幾部分的組合：
（1）當(dāng)前日期和時(shí)間发钝。
（2）時(shí)鐘序列。
（3）全局唯一的IEEE機(jī)器識別號波闹，如果有網(wǎng)卡酝豪，從網(wǎng)卡MAC地址獲得，沒有網(wǎng)卡以其他方式獲得精堕。
標(biāo)準(zhǔn)的UUID格式為：xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx (8-4-4-4-12)孵淘，以連字號分為五段形式的36個(gè)字符，示例：550e8400-e29b-41d4-a716-446655440000
Java標(biāo)準(zhǔn)類庫中已經(jīng)提供了UUID的API歹篓。
UUID.randomUUID()
優(yōu)點(diǎn)
- 性能非常高：本地生成瘫证，沒有網(wǎng)絡(luò)消耗。
缺點(diǎn)
- 不易存儲：UUID太長庄撮，16字節(jié)128位背捌，通常以36長度的字符串表示，很多場景不適用洞斯。
- 信息不安全：基于MAC地址生成UUID的算法可能會(huì)造成MAC地址泄露毡庆，這個(gè)漏洞曾被用于尋找梅麗莎病毒的制作者位置。
- ID作為主鍵時(shí)在特定的環(huán)境會(huì)存在一些問題烙如，比如做DB主鍵的場景下么抗，UUID就非常不適用。
SnowFlake雪花算法
雪花ID生成的是一個(gè)64位的二進(jìn)制正整數(shù)亚铁，然后轉(zhuǎn)換成10進(jìn)制的數(shù)蝇刀。64位二進(jìn)制數(shù)由如下部分組成：
- 1位標(biāo)識符：始終是0，由于long基本類型在Java中是帶符號的徘溢，最高位是符號位熊泵，正數(shù)是0仰迁，負(fù)數(shù)是1甸昏，所以id一般是正數(shù)顽分，最高位是0。
- 41位時(shí)間戳：41位時(shí)間截不是存儲當(dāng)前時(shí)間的時(shí)間截施蜜，而是存儲時(shí)間截的差值（當(dāng)前時(shí)間截 - 開始時(shí)間截 )得到的值卒蘸，這里的的開始時(shí)間截，一般是我們的id生成器開始使用的時(shí)間翻默，由我們程序來指定的缸沃。
- 10位機(jī)器標(biāo)識碼：可以部署在1024個(gè)節(jié)點(diǎn)，如果機(jī)器分機(jī)房（IDC）部署修械，這10位可以由 5位機(jī)房ID + 5位機(jī)器ID 組成趾牧。
- 12位序列：毫秒內(nèi)的計(jì)數(shù)，12位的計(jì)數(shù)順序號支持每個(gè)節(jié)點(diǎn)每毫秒(同一機(jī)器肯污，同一時(shí)間截)產(chǎn)生4096個(gè)ID序號
優(yōu)點(diǎn)
- 簡單高效翘单，生成速度快。
- 時(shí)間戳在高位蹦渣，自增序列在低位哄芜，整個(gè)ID是趨勢遞增的，按照時(shí)間有序遞增柬唯。
- 靈活度高认臊，可以根據(jù)業(yè)務(wù)需求，調(diào)整bit位的劃分锄奢，滿足不同的需求失晴。
缺點(diǎn)
- 依賴機(jī)器的時(shí)鐘，如果服務(wù)器時(shí)鐘回?fù)芫醒耄瑫?huì)導(dǎo)致重復(fù)ID生成涂屁。
- 在分布式環(huán)境上，每個(gè)服務(wù)器的時(shí)鐘不可能完全同步堪滨，有時(shí)會(huì)出現(xiàn)不是全局遞增的情況胯陋。
snowflake Java實(shí)現(xiàn)
/**
* Twitter_Snowflake<br>
* SnowFlake的結(jié)構(gòu)如下(每部分用-分開):<br>
* 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
* 1位標(biāo)識，由于long基本類型在Java中是帶符號的袱箱，最高位是符號位遏乔，正數(shù)是0，負(fù)數(shù)是1发笔，所以id一般是正數(shù)盟萨，最高位是0<br>
* 41位時(shí)間截(毫秒級)，注意了讨，41位時(shí)間截不是存儲當(dāng)前時(shí)間的時(shí)間截捻激，而是存儲時(shí)間截的差值（當(dāng)前時(shí)間截 - 開始時(shí)間截)
* 得到的值）制轰，這里的的開始時(shí)間截，一般是我們的id生成器開始使用的時(shí)間胞谭，由我們程序來指定的（如下下面程序IdWorker類的startTime屬性）垃杖。
* 41位的時(shí)間截，可以使用69年丈屹，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
* 10位的數(shù)據(jù)機(jī)器位调俘，可以部署在1024個(gè)節(jié)點(diǎn)，包括5位datacenterId和5位workerId<br>
* 12位序列旺垒，毫秒內(nèi)的計(jì)數(shù)彩库，12位的計(jì)數(shù)順序號支持每個(gè)節(jié)點(diǎn)每毫秒(同一機(jī)器，同一時(shí)間截)產(chǎn)生4096個(gè)ID序號<br>
* 加起來剛好64位先蒋，為一個(gè)Long型骇钦。<br>
* SnowFlake的優(yōu)點(diǎn)是，整體上按照時(shí)間自增排序竞漾，并且整個(gè)分布式系統(tǒng)內(nèi)不會(huì)產(chǎn)生ID碰撞(由數(shù)據(jù)中心ID和機(jī)器ID作區(qū)分)眯搭，并且效率較高，
* 經(jīng)測試畴蹭，SnowFlake每秒能夠產(chǎn)生26萬ID左右坦仍。
*/
public class SnowflakeIdWorker {
// ==============================Fields===========================================
/** 開始時(shí)間截 (2015-01-01) */
private final long twepoch = 1420041600000L;
/** 機(jī)器id所占的位數(shù) */
private final long workerIdBits = 5L;
/** 數(shù)據(jù)標(biāo)識id所占的位數(shù) */
private final long datacenterIdBits = 5L;
/** 支持的最大機(jī)器id，結(jié)果是31 (這個(gè)移位算法可以很快的計(jì)算出幾位二進(jìn)制數(shù)所能表示的最大十進(jìn)制數(shù)) */
private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
/** 支持的最大數(shù)據(jù)標(biāo)識id叨襟，結(jié)果是31 */
private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
/** 序列在id中占的位數(shù) */
private final long sequenceBits = 12L;
/** 機(jī)器ID向左移12位 */
private final long workerIdShift = sequenceBits;
/** 數(shù)據(jù)標(biāo)識id向左移17位(12+5) */
private final long datacenterIdShift = sequenceBits + workerIdBits;
/** 時(shí)間截向左移22位(5+5+12) */
private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
/** 生成序列的掩碼繁扎，這里為4095 (0b111111111111=0xfff=4095) */
private final long sequenceMask = -1L ^ (-1L << sequenceBits);
/** 工作機(jī)器ID(0~31) */
private long workerId;
/** 數(shù)據(jù)中心ID(0~31) */
private long datacenterId;
/** 毫秒內(nèi)序列(0~4095) */
private long sequence = 0L;
/** 上次生成ID的時(shí)間截 */
private long lastTimestamp = -1L;
//==============================Constructors=====================================
/**
* 構(gòu)造函數(shù)
* @param workerId 工作ID (0~31)
* @param datacenterId 數(shù)據(jù)中心ID (0~31)
*/
public SnowflakeIdWorker(long workerId, long datacenterId) {
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
}
if (datacenterId > maxDatacenterId || datacenterId < 0) {
throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
}
this.workerId = workerId;
this.datacenterId = datacenterId;
}
// ==============================Methods==========================================
/**
* 獲得下一個(gè)ID (該方法是線程安全的)
* @return SnowflakeId
*/
public synchronized long nextId() {
long timestamp = timeGen();
//如果當(dāng)前時(shí)間小于上一次ID生成的時(shí)間戳，說明系統(tǒng)時(shí)鐘回退過這個(gè)時(shí)候應(yīng)當(dāng)拋出異常
if (timestamp < lastTimestamp) {
throw new RuntimeException(
String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
//如果是同一時(shí)間生成的糊闽，則進(jìn)行毫秒內(nèi)序列
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & sequenceMask;
//毫秒內(nèi)序列溢出
if (sequence == 0) {
//阻塞到下一個(gè)毫秒,獲得新的時(shí)間戳
timestamp = tilNextMillis(lastTimestamp);
}
}
//時(shí)間戳改變梳玫，毫秒內(nèi)序列重置
else {
sequence = 0L;
}
//上次生成ID的時(shí)間截
lastTimestamp = timestamp;
//移位并通過或運(yùn)算拼到一起組成64位的ID
return ((timestamp - twepoch) << timestampLeftShift) //
| (datacenterId << datacenterIdShift) //
| (workerId << workerIdShift) //
| sequence;
}
/**
* 阻塞到下一個(gè)毫秒，直到獲得新的時(shí)間戳
* @param lastTimestamp 上次生成ID的時(shí)間截
* @return 當(dāng)前時(shí)間戳
*/
protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
/**
* 返回以毫秒為單位的當(dāng)前時(shí)間
* @return 當(dāng)前時(shí)間(毫秒)
*/
protected long timeGen() {
return System.currentTimeMillis();
}
//==============================Test=============================================
/** 測試 */
public static void main(String[] args) {
SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
for (int i = 0; i < 1000; i++) {
long id = idWorker.nextId();
System.out.println(Long.toBinaryString(id));
System.out.println(id);
}
}
}
數(shù)據(jù)庫自增ID機(jī)制
主要思路是采用數(shù)據(jù)庫自增ID + replace_into實(shí)現(xiàn)唯一ID的獲取右犹。
create table t_global_id(
id bigint(20) unsigned not null auto_increment,
stub char(1) not null default '',
primary key (id),
unique key stub (stub)
) engine=MyISAM;
# 每次業(yè)務(wù)可以使用以下SQL讀寫MySQL得到ID號
replace into t_golbal_id(stub) values('a');
select last_insert_id();
replace into跟insert功能類似提澎，不同點(diǎn)在于：replace into首先嘗試插入數(shù)據(jù)列表中，如果發(fā)現(xiàn)表中已經(jīng)有此行數(shù)據(jù)（根據(jù)主鍵或唯一索引判斷）則先刪除念链，再插入盼忌。否則直接插入新數(shù)據(jù)。
當(dāng)然為了避免數(shù)據(jù)庫的單點(diǎn)故障掂墓，最少需要兩個(gè)數(shù)據(jù)庫實(shí)例谦纱，通過區(qū)分auto_increment的起始值和步長來生成奇偶數(shù)的ID。如下：
Server1：
auto-increment-increment = 2
auto-increment-offset = 1
Server2：
auto-increment-increment = 2
auto-increment-offset = 2
優(yōu)點(diǎn)
- 簡單君编。充分借助數(shù)據(jù)庫的自增ID機(jī)制跨嘉，可靠性高，生成有序的ID吃嘿。
缺點(diǎn)
- ID生成依賴數(shù)據(jù)庫單機(jī)的讀寫性能祠乃。
- 依賴數(shù)據(jù)庫梦重，當(dāng)數(shù)據(jù)庫異常時(shí)整個(gè)系統(tǒng)不可用。
對于MySQL的性能問題亮瓷，可以用如下方案解決
在分布式環(huán)境中琴拧，我們可以部署N臺數(shù)據(jù)庫實(shí)例，每臺設(shè)置成不同的初始值寺庄，自增步長為機(jī)器的臺數(shù)艾蓝。每臺的初始值分別為1,2,3...N，步長為N斗塘。
以上方案雖然解決了性能問題，但是也存在很大的局限性：
- 系統(tǒng)水平擴(kuò)容困難：系統(tǒng)定義好步長之后亮靴，增加機(jī)器之后調(diào)整步長困難馍盟。如果要添加機(jī)器怎么辦？假設(shè)現(xiàn)在只有一臺機(jī)器發(fā)號是1,2,3,4,5（步長是1）茧吊，這個(gè)時(shí)候需要擴(kuò)容機(jī)器一臺贞岭。可以這樣做：把第二臺機(jī)器的初始值設(shè)置得比第一臺超過很多搓侄，比如14（假設(shè)在擴(kuò)容時(shí)間之內(nèi)第一臺不可能發(fā)到14）瞄桨，同時(shí)設(shè)置步長為2，那么這臺機(jī)器下發(fā)的號碼都是14以后的偶數(shù)讶踪。然后摘掉第一臺芯侥，把ID值保留為奇數(shù)，比如7乳讥，然后修改第一臺的步長為2柱查。讓它符合我們定義的號段標(biāo)準(zhǔn)，對于這個(gè)例子來說就是讓第一臺以后只能產(chǎn)生奇數(shù)云石。擴(kuò)容方案看起來復(fù)雜嗎唉工？貌似還好，現(xiàn)在想象一下如果我們線上有100臺機(jī)器汹忠，這個(gè)時(shí)候要擴(kuò)容該怎么做淋硝？簡直是噩夢。
- 數(shù)據(jù)庫壓力大：每次獲取一個(gè)ID都必須讀寫一次數(shù)據(jù)庫宽菜。當(dāng)然對于這種問題谣膳，也有相應(yīng)的解決方案，就是每次獲取ID時(shí)都批量獲取一個(gè)區(qū)間的號段到內(nèi)存中赋焕，用完之后再來獲取参歹。數(shù)據(jù)庫的性能提高了幾個(gè)量級。
第三方軟件生成（Redis）
Redis實(shí)現(xiàn)了一個(gè)原子操作INCR和INCRBY實(shí)現(xiàn)遞增的操作隆判。當(dāng)使用數(shù)據(jù)庫性能不夠時(shí)犬庇，可以采用Redis來代替僧界，同時(shí)使用Redis集群來提高吞吐量〕敉欤可以初始化每臺Redis的初始值為1,2,3,4,5捂襟，然后步長為5。各個(gè)Redis生成的ID為：
A：1欢峰，6葬荷，11，16纽帖，21
B：2宠漩，7，12懊直，17扒吁，22
C：3，8室囊，13雕崩，18，23
D：4融撞，9盼铁，14，19尝偎，24
E：5饶火，10，15冬念，20趁窃，25
優(yōu)點(diǎn)
- 不依賴于數(shù)據(jù)庫，靈活方便急前，且性能優(yōu)于數(shù)據(jù)庫醒陆。
- 數(shù)字ID天然排序，對分頁或者需要排序的結(jié)果很有幫助裆针。
缺點(diǎn)：
- 如果系統(tǒng)中沒有Redis刨摩，還需要引入新的組件，增加系統(tǒng)復(fù)雜度世吨。
- 需要編碼和配置的工作量比較大澡刹。這個(gè)都不是最大的問題。
關(guān)于分布式全局唯一ID的生成耘婚，各個(gè)互聯(lián)網(wǎng)公司有很多實(shí)現(xiàn)方案罢浇，比如美團(tuán)點(diǎn)評的Leaf-snowflake，用zookeeper解決了各個(gè)服務(wù)器時(shí)鐘回?fù)艿膯栴}，弱依賴zookeeper嚷闭。以及Leaf-segment類似上面數(shù)據(jù)庫批量ID獲取的方案攒岛。
