全局唯一的 ID 幾乎是所有系統(tǒng)都會遇到的剛需安吁。這個(gè) id 在搜索, 存儲數(shù)據(jù), 加快檢索速度 等等很多方面都有著重要的意義。工業(yè)上有多種策略來獲取這個(gè)全局唯一的id睛琳，針對常見的幾種場景盒蟆，我在這里進(jìn)行簡單的總結(jié)和對比。
簡單分析一下需求 [1]
所謂全局唯一的 id 其實(shí)往往對應(yīng)是生成唯一記錄標(biāo)識的業(yè)務(wù)需求师骗。
這個(gè) id 常常是數(shù)據(jù)庫的主鍵历等，數(shù)據(jù)庫上會建立聚集索引（cluster index），即在物理存儲上以這個(gè)字段排序辟癌。這個(gè)記錄標(biāo)識上的查詢寒屯，往往又有分頁或者排序的業(yè)務(wù)需求。所以往往要有一個(gè)time字段黍少，并且在time字段上建立普通索引（non-cluster index）浩螺。普通索引存儲的是實(shí)際記錄的指針，其訪問效率會比聚集索引慢仍侥，如果記錄標(biāo)識在生成時(shí)能夠基本按照時(shí)間有序要出，則可以省去這個(gè)time字段的索引查詢。
這就引出了記錄標(biāo)識生成的兩大核心需求：
全局唯一
趨勢有序
常見生成策略的優(yōu)缺點(diǎn)對比 [2]
方法一: 用數(shù)據(jù)庫的 auto_increment 來生成
優(yōu)點(diǎn)：
此方法使用數(shù)據(jù)庫原有的功能农渊，所以相對簡單
能夠保證唯一性
能夠保證遞增性
id 之間的步長是固定且可自定義的
缺點(diǎn)：
可用性難以保證：數(shù)據(jù)庫常見架構(gòu)是 一主多從 + 讀寫分離患蹂，生成自增ID是寫請求?主庫掛了就玩不轉(zhuǎn)了
擴(kuò)展性差，性能有上限：因?yàn)閷懭胧菃吸c(diǎn)砸紊，數(shù)據(jù)庫主庫的寫性能決定ID的生成性能上限传于，并且?難以擴(kuò)展
改進(jìn)方案：
冗余主庫，避免寫入單點(diǎn)
數(shù)據(jù)水平切分醉顽，保證各主庫生成的ID不重復(fù)
如上圖所述沼溜，由1個(gè)寫庫變成3個(gè)寫庫，每個(gè)寫庫設(shè)置不同的 auto_increment 初始值游添，以及相同的增長步長系草，以保證每個(gè)數(shù)據(jù)庫生成的ID是不同的（上圖中DB 01生成0,3,6,9…，DB 02生成1,4,7,10唆涝，DB 03生成2,5,8,11…）
改進(jìn)后的架構(gòu)保證了可用性找都，但缺點(diǎn)是
喪失了ID生成的“絕對遞增性”：先訪問DB 01生成0,3，再訪問DB 02生成1廊酣，可能導(dǎo)致在非常短的時(shí)間內(nèi)能耻，ID生成不是絕對遞增的（這個(gè)問題不大，目標(biāo)是趨勢遞增，不是絕對遞增
數(shù)據(jù)庫的寫壓力依然很大晓猛，每次生成ID都要訪問數(shù)據(jù)庫
為了解決這些問題饿幅，引出了以下方法：
方法二：單點(diǎn)批量ID生成服務(wù)
分布式系統(tǒng)之所以難，很重要的原因之一是“沒有一個(gè)全局時(shí)鐘戒职，難以保證絕對的時(shí)序”诫睬，要想保證絕對的時(shí)序，還是只能使用單點(diǎn)服務(wù)帕涌，用本地時(shí)鐘保證“絕對時(shí)序”。
數(shù)據(jù)庫寫壓力大续徽，是因?yàn)槊看紊蒊D都訪問了數(shù)據(jù)庫蚓曼，可以使用批量的方式降低數(shù)據(jù)庫寫壓力。
如上圖所述钦扭，數(shù)據(jù)庫使用雙master保證可用性纫版，數(shù)據(jù)庫中只存儲當(dāng)前ID的最大值，例如4客情。
ID生成服務(wù)假設(shè)每次批量拉取5個(gè)ID其弊，服務(wù)訪問數(shù)據(jù)庫，將當(dāng)前ID的最大值修改為4膀斋，這樣應(yīng)用訪問ID生成服務(wù)索要ID梭伐，ID生成服務(wù)不需要每次訪問數(shù)據(jù)庫，就能依次派發(fā)0,1,2,3,4這些ID了仰担。
當(dāng)ID發(fā)完后糊识，再將ID的最大值修改為11，就能再次派發(fā)6,7,8,9,10,11這些ID了摔蓝，于是數(shù)據(jù)庫的壓力就降低到原來的1/6赂苗。
優(yōu)點(diǎn)：
保證了ID生成的絕對遞增有序
大大的降低了數(shù)據(jù)庫的壓力，ID生成可以做到每秒生成幾萬幾十萬個(gè)
缺點(diǎn)：
服務(wù)仍然是單點(diǎn)
如果服務(wù)掛了贮尉，服務(wù)重啟起來之后拌滋，繼續(xù)生成ID可能會不連續(xù)，中間出現(xiàn)空洞（服務(wù)內(nèi)存是保存著0,1,2,3,4猜谚，數(shù)據(jù)庫中max-id是4败砂，分配到3時(shí)，服務(wù)重啟了魏铅，下次會從5開始分配吠卷，3和4就成了空洞，不過這個(gè)問題也不大）
雖然每秒可以生成幾萬幾十萬個(gè)ID沦零，但畢竟還是有性能上限祭隔，無法進(jìn)行水平擴(kuò)展
改進(jìn)方案
單點(diǎn)服務(wù)的常用高可用優(yōu)化方案是“備用服務(wù)”，也叫“影子服務(wù)”，所以我們能用以下方法優(yōu)化上述缺點(diǎn)：
如上圖疾渴，對外提供的服務(wù)是主服務(wù)千贯，有一個(gè)影子服務(wù)時(shí)刻處于備用狀態(tài)，當(dāng)主服務(wù)掛了的時(shí)候影子服務(wù)頂上搞坝。這個(gè)切換的過程對調(diào)用方是透明的搔谴，可以自動完成，常用的技術(shù)是?vip+keepalived桩撮。另外敦第，id generate service 也可以進(jìn)行水平擴(kuò)展，以解決上述缺點(diǎn)店量，但會引發(fā)一致性問題芜果。
方法三：uuid / guid
不管是通過數(shù)據(jù)庫，還是通過服務(wù)來生成ID融师，業(yè)務(wù)方Application都需要進(jìn)行一次遠(yuǎn)程調(diào)用右钾，比較耗時(shí)。uuid是一種常見的本地生成ID的方法旱爆。
UUID uuid = UUID.randomUUID();
優(yōu)點(diǎn)：
本地生成ID舀射，不需要進(jìn)行遠(yuǎn)程調(diào)用，時(shí)延低
擴(kuò)展性好怀伦，基本可以認(rèn)為沒有性能上限
缺點(diǎn)：
無法保證趨勢遞增
uuid過長脆烟，往往用字符串表示，作為主鍵建立索引查詢效率低房待，常見優(yōu)化方案為“轉(zhuǎn)化為兩個(gè)uint64整數(shù)存儲”或者“折半存儲”（折半后不能保證唯一性）
方法四：取當(dāng)前毫秒數(shù)
uuid是一個(gè)本地算法浩淘，生成性能高，但無法保證趨勢遞增吴攒，且作為字符串ID檢索效率低张抄，有沒有一種能保證遞增的本地算法呢？ - 取當(dāng)前毫秒數(shù)是一種常見方案洼怔。
優(yōu)點(diǎn)：
本地生成ID署惯，不需要進(jìn)行遠(yuǎn)程調(diào)用，時(shí)延低
生成的ID趨勢遞增
生成的ID是整數(shù)镣隶，建立索引后查詢效率高
缺點(diǎn)：
如果并發(fā)量超過1000极谊，會生成重復(fù)的ID
這個(gè)缺點(diǎn)要了命了，不能保證ID的唯一性安岂。當(dāng)然轻猖，使用微秒可以降低沖突概率，但每秒最多只能生成1000000個(gè)ID域那，再多的話就一定會沖突了咙边，所以使用微秒并不從根本上解決問題。
方法五：使用 Redis 來生成 id
當(dāng)使用數(shù)據(jù)庫來生成ID性能不夠要求的時(shí)候，我們可以嘗試使用Redis來生成ID败许。這主要依賴于Redis是單線程的王带，所以也可以用生成全局唯一的ID∈幸螅可以用Redis的原子操作?INCR和?INCRBY?來實(shí)現(xiàn)愕撰。
優(yōu)點(diǎn)：
依賴于數(shù)據(jù)庫，靈活方便醋寝，且性能優(yōu)于數(shù)據(jù)庫搞挣。
數(shù)字ID天然排序，對分頁或者需要排序的結(jié)果很有幫助音羞。
缺點(diǎn)：
如果系統(tǒng)中沒有Redis囱桨，還需要引入新的組件，增加系統(tǒng)復(fù)雜度黄选。
需要編碼和配置的工作量比較大。
方法六：Twitter 開源的 Snowflake 算法
snowflake 是 twitter 開源的分布式ID生成算法婶肩，其核心思想為办陷，一個(gè)long型的ID：
41 bit 作為毫秒數(shù) -?41位的長度可以使用69年
10 bit 作為機(jī)器編號 （5個(gè)bit是數(shù)據(jù)中心，5個(gè)bit的機(jī)器ID） -?10位的長度最多支持部署1024個(gè)節(jié)點(diǎn)
12 bit 作為毫秒內(nèi)序列號 -?12位的計(jì)數(shù)順序號支持每個(gè)節(jié)點(diǎn)每毫秒產(chǎn)生4096個(gè)ID序號
算法單機(jī)每秒內(nèi)理論上最多可以生成1000*(2^12)律歼，也就是400W的ID民镜，完全能滿足業(yè)務(wù)的需求。
該算法 java 版本的實(shí)現(xiàn)代碼如下：
public class SnowflakeIdGenerator {
//================================================Algorithm's Parameter=============================================
// 系統(tǒng)開始時(shí)間截 (UTC 2017-06-28 00:00:00)
private final long startTime = 1498608000000L;
// 機(jī)器id所占的位數(shù)
private final long workerIdBits = 5L;
// 數(shù)據(jù)標(biāo)識id所占的位數(shù)
private final long dataCenterIdBits = 5L;
// 支持的最大機(jī)器id(十進(jìn)制)险毁，結(jié)果是31 (這個(gè)移位算法可以很快的計(jì)算出幾位二進(jìn)制數(shù)所能表示的最大十進(jìn)制數(shù))
// -1L 左移 5位 (worker id 所占位數(shù)) 即 5位二進(jìn)制所能獲得的最大十進(jìn)制數(shù) - 31
private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
// 支持的最大數(shù)據(jù)標(biāo)識id - 31
private final long maxDataCenterId = -1L ^ (-1L << dataCenterIdBits);
// 序列在id中占的位數(shù)
private final long sequenceBits = 12L;
// 機(jī)器ID 左移位數(shù) - 12 (即末 sequence 所占用的位數(shù))
private final long workerIdMoveBits = sequenceBits;
// 數(shù)據(jù)標(biāo)識id 左移位數(shù) - 17(12+5)
private final long dataCenterIdMoveBits = sequenceBits + workerIdBits;
// 時(shí)間截向 左移位數(shù) - 22(5+5+12)
private final long timestampMoveBits = sequenceBits + workerIdBits + dataCenterIdBits;
// 生成序列的掩碼(12位所對應(yīng)的最大整數(shù)值)制圈，這里為4095 (0b111111111111=0xfff=4095)
private final long sequenceMask = -1L ^ (-1L << sequenceBits);
//=================================================Works's Parameter================================================
/**
* 工作機(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 SnowflakeIdGenerator(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 的方法
public synchronized long nextId() {
long timestamp = currentTime();
//如果當(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)序列溢出 即 序列 > 4095
if (sequence == 0) {
//阻塞到下一個(gè)毫秒,獲得新的時(shí)間戳
timestamp = blockTillNextMillis(lastTimestamp);
}
}
//時(shí)間戳改變畔况，毫秒內(nèi)序列重置
else {
sequence = 0L;
}
//上次生成ID的時(shí)間截
lastTimestamp = timestamp;
//移位并通過或運(yùn)算拼到一起組成64位的ID
return ((timestamp - startTime) << timestampMoveBits) //
| (dataCenterId << dataCenterIdMoveBits) //
| (workerId << workerIdMoveBits) //
| sequence;
}
// 阻塞到下一個(gè)毫秒 即 直到獲得新的時(shí)間戳
protected long blockTillNextMillis(long lastTimestamp) {
long timestamp = currentTime();
while (timestamp <= lastTimestamp) {
timestamp = currentTime();
}
return timestamp;
}
// 獲得以毫秒為單位的當(dāng)前時(shí)間
protected long currentTime() {
return System.currentTimeMillis();
}
//====================================================Test Case=====================================================
public static void main(String[] args) {
SnowflakeIdGenerator idWorker = new SnowflakeIdGenerator(0, 0);
for (int i = 0; i < 1000; i++) {
long id = idWorker.nextId();
System.out.println(Long.toBinaryString(id));
System.out.println(id);
}
}
}
如果想學(xué)習(xí)Java工程化鲸鹦、高性能及分布式、深入淺出跷跪。性能調(diào)優(yōu)馋嗜、Spring，MyBatis吵瞻，Netty源碼分析的朋友可以加我的Java高級架構(gòu)進(jìn)階群：180705916葛菇，群里有阿里大牛直播講解技術(shù)，以及Java大型互聯(lián)網(wǎng)技術(shù)的視頻免費(fèi)分享給大家
