分布式唯一ID解決方案-雪花算法
閱讀大概需要3分鐘
附源碼
前言
ID生成器
數據庫自增
分布式ID生成器
方案一：UUID
方案二：snowflake(雪花算法)
前言
單體架構的服務的日子已經一去不復返了。
當前系統(tǒng)業(yè)務和數據存儲的復雜度都在提升，分布式系統(tǒng)是目前使用非常普遍的解決方案。
全局唯一 ID 幾乎是所有設計系統(tǒng)時都會遇到的，全局唯一 ID 在存儲和檢索中有至關重要的作用。
ID生成器
在應用程序中，經常需要全局唯一的ID作為數據庫主鍵。如何生成全局唯一ID？
首先，需要確定全局唯一ID是整型還是字符串？如果是字符串，那么現有的UUID就完全滿足需求，不需要額外的工作。缺點是字符串作為ID占用空間大，索引效率比整型低。
如果采用整型作為ID，那么首先排除掉32位int類型，因為范圍太小，必須使用64位long型。
采用整型作為ID時，如何生成自增、全局唯一且不重復的ID？
數據庫自增
數據庫自增 ID 是我們在數據量較小的系統(tǒng)中經常使用的，利用數據庫的自增ID，從1開始，基本可以做到連續(xù)遞增。Oracle可以用 SEQUENCE，MySQL可以用主鍵的 AUTO_INCREMENT，雖然不能保證全局唯一，但每個表唯一，也基本滿足需求。
數據庫自增ID的缺點是數據在插入前，無法獲得ID。數據在插入后，獲取的ID雖然是唯一的，但一定要等到事務提交后，ID才算是有效的。有些雙向引用的數據，不得不插入后再做一次更新，比較麻煩。
在我們開發(fā)過程中，遇到一種 主主數據庫同步（簡單可以理解為，同樣的sql再另一臺數據庫再執(zhí)行一次）的場景，如果使用數據庫自增 ID，就會出現主鍵不一致、或主鍵沖突問題。
分布式ID生成器
方案一：UUID
分布式環(huán)境不推薦使用
uuid 是我們比較先想到的方法，在 java.util;包中就有對應方法。這是一個具有rfc標準的uuid：https://www.ietf.org/rfc/rfc4122.txt
uuid 有很好的性能（本地調用），沒有網絡消耗。
但是，uuid 不易存儲（生成了字符串、存儲過長、很多場景不適用）；信息不安全（基于 MAC 地址生成、可能會造成泄露，這個漏洞曾被用于尋找梅麗莎病毒的制作者位置。 ）；無法保證遞增（或趨勢遞增）；其他博主反饋，截取前20位做唯一 ID ，在大數量（大概只有220w）情況下會有重復問題。
UUID.randomUUID().toString()
方案二：snowflake(雪花算法)
這是目前使用較多分布式ID解決方案，推薦使用
背景 Twitter 云云就不介紹了，就是前段時間封了懂王賬號的 Twitter。
算法介紹
SnowFlake算法生成id的結果是一個64bit大小的整數，它的結構如下圖：
1位，不用。二進制中最高位為1的都是負數，但是我們生成的id一般都使用整數，所以這個最高位固定是0
41位，用來記錄時間戳（毫秒）。
41位可以表示 2^{41}-1 個數字，
如果只用來表示正整數（計算機中正數包含0），可以表示的數值范圍是：0 至 ?2^{41}-1，減1是因為可表示的數值范圍是從0開始算的，而不是1。
也就是說41位可以表示 2^{41}-1 個毫秒的值，轉化成單位年則是 (2^{41}-1) / (1000 * 60 * 60 * 24 * 365) = 69 年
10位，用來記錄工作機器id。
可以部署在 2^{10} = 1024 個節(jié)點，包括 5位 datacenterId 和 5位 workerId
5位（bit）可以表示的最大正整數是 2^{5}-1 = 31 ，即可以用 0、1、2、3、....31 這 32 個數字，來表示不同的 datecenterId 或 workerId
12位，序列號，用來記錄同毫秒內產生的不同id。
12位（bit）可以表示的最大正整數是 2^{12}-1 = 4095 ，即可以用 0、1、2、3、....4094 這 4095 個數字，來表示同一機器同一時間截（毫秒)內產生的 4095 個 ID 序號。
由于在 Java 中 64bit 的整數是 long 類型，所以在 Java 中 SnowFlake 算法生成的 id 就是 long 來存儲的。
SnowFlake可以保證：
同一臺服務器所有生成的id按時間趨勢遞增
整個分布式系統(tǒng)內不會產生重復id（因為有datacenterId和workerId來做區(qū)分）
存在的問題：
機器ID（5位）和數據中心ID（5位）配置沒有解決，分布式部署的時候會使用相同的配置，任然有ID重復的風險。
使用的時候需要實例化對象，沒有形成開箱即用的工具類。
強依賴機器時鐘，如果機器上時鐘回撥，會導致發(fā)號重復或者服務會處于不可用狀態(tài)。（這點在正常情況下是不會發(fā)生的）
針對上面問題，這里提供一種解決思路，workId 使用服務器 hostName 生成，dataCenterId 使用 IP 生成，這樣可以最大限度防止 10 位機器碼重復，但是由于兩個 ID 都不能超過 32，只能取余數，還是難免產生重復，但是實際使用中，hostName 和 IP 的配置一般連續(xù)或相近，只要不是剛好相隔 32 位，就不會有問題，況且，hostName 和 IP 同時相隔 32 的情況更加是幾乎不可能的事，平時做的分布式部署，一般也不會超過 10 臺容器。
生產上使用docker配置一般是一次編譯，然后分布式部署到不同容器，不會有不同的配置。這種情況就對上面提到的出現了不確定情況，這個在評論中會再出一篇參考文章。
源碼
Java 版雪花ID生成算法
package?com.my.blog.website.utils;
?
import?org.apache.commons.lang3.RandomUtils;
import?org.apache.commons.lang3.StringUtils;
import?org.apache.commons.lang3.SystemUtils;
?
import?java.net.Inet4Address;
import?java.net.UnknownHostException;
?
/**
?*?Twitter_Snowflake<br>
?*?SnowFlake的結構如下(每部分用-分開):<br>
?*?0?-?0000000000?0000000000?0000000000?0000000000?0?-?00000?-?00000?-?000000000000?<br>
?*?1位標識，由于long基本類型在Java中是帶符號的，最高位是符號位，正數是0，負數是1，所以id一般是正數，最高位是0<br>
?*?41位時間截(毫秒級)，注意，41位時間截不是存儲當前時間的時間截，而是存儲時間截的差值（當前時間截?-?開始時間截)
?*?得到的值），這里的的開始時間截，一般是我們的id生成器開始使用的時間，由我們程序來指定的（如下下面程序IdWorker類的startTime屬性）。41位的時間截，可以使用69年，年T?=?(1L?<<?41)?/?(1000L?*?60?*?60?*?24?*?365)?=?69<br>
?*?10位的數據機器位，可以部署在1024個節(jié)點，包括5位datacenterId和5位workerId<br>
?*?12位序列，毫秒內的計數，12位的計數順序號支持每個節(jié)點每毫秒(同一機器，同一時間截)產生4096個ID序號<br>
?*?加起來剛好64位，為一個Long型。<br>
?*?SnowFlake的優(yōu)點是，整體上按照時間自增排序，并且整個分布式系統(tǒng)內不會產生ID碰撞(由數據中心ID和機器ID作區(qū)分)，并且效率較高，經測試，SnowFlake每秒能夠產生26萬ID左右。
?*/
public?class?SnowflakeIdWorker?{
?
????//?==============================Fields===========================================
????/**?開始時間截?(2015-01-01)?*/
????private?final?long?twepoch?=?1489111610226L;
?
????/**?機器id所占的位數?*/
????private?final?long?workerIdBits?=?5L;
?
????/**?數據標識id所占的位數?*/
????private?final?long?dataCenterIdBits?=?5L;
?
????/**?支持的最大機器id，結果是31?(這個移位算法可以很快的計算出幾位二進制數所能表示的最大十進制數)?*/
????private?final?long?maxWorkerId?=?-1L?^?(-1L?<<?workerIdBits);
?
????/**?支持的最大數據標識id，結果是31?*/
????private?final?long?maxDataCenterId?=?-1L?^?(-1L?<<?dataCenterIdBits);
?
????/**?序列在id中占的位數?*/
????private?final?long?sequenceBits?=?12L;
?
????/**?機器ID向左移12位?*/
????private?final?long?workerIdShift?=?sequenceBits;
?
????/**?數據標識id向左移17位(12+5)?*/
????private?final?long?dataCenterIdShift?=?sequenceBits?+?workerIdBits;
?
????/**?時間截向左移22位(5+5+12)?*/
????private?final?long?timestampLeftShift?=?sequenceBits?+?workerIdBits?+?dataCenterIdBits;
?
????/**?生成序列的掩碼，這里為4095?(0b111111111111=0xfff=4095)?*/
????private?final?long?sequenceMask?=?-1L?^?(-1L?<<?sequenceBits);
?
????/**?工作機器ID(0~31)?*/
????private?long?workerId;
?
????/**?數據中心ID(0~31)?*/
????private?long?dataCenterId;
?
????/**?毫秒內序列(0~4095)?*/
????private?long?sequence?=?0L;
?
????/**?上次生成ID的時間截?*/
????private?long?lastTimestamp?=?-1L;
?
????private?static?SnowflakeIdWorker?idWorker;
?
????static?{
????????idWorker?=?new?SnowflakeIdWorker(getWorkId(),getDataCenterId());
????}
?
????//==============================Constructors=====================================
????/**
?????*?構造函數
?????*?@param?workerId?工作ID?(0~31)
?????*?@param?dataCenterId?數據中心ID?(0~31)
?????*/
????public?SnowflakeIdWorker(long?workerId,?long?dataCenterId)?{
????????if?(workerId?>?maxWorkerId?||?workerId?<?0)?{
????????????throw?new?IllegalArgumentException(String.format("workerId?can't?be?greater?than?%d?or?less?than?0",?maxWorkerId));
????????}
????????if?(dataCenterId?>?maxDataCenterId?||?dataCenterId?<?0)?{
????????????throw?new?IllegalArgumentException(String.format("dataCenterId?can't?be?greater?than?%d?or?less?than?0",?maxDataCenterId));
????????}
????????this.workerId?=?workerId;
????????this.dataCenterId?=?dataCenterId;
????}
?
????//?==============================Methods==========================================
????/**
?????*?獲得下一個ID?(該方法是線程安全的)
?????*?@return?SnowflakeId
?????*/
????public?synchronized?long?nextId()?{
????????long?timestamp?=?timeGen();
?
????????//如果當前時間小于上一次ID生成的時間戳，說明系統(tǒng)時鐘回退過這個時候應當拋出異常
????????if?(timestamp?<?lastTimestamp)?{
????????????throw?new?RuntimeException(
????????????????????String.format("Clock?moved?backwards.??Refusing?to?generate?id?for?%d?milliseconds",?lastTimestamp?-?timestamp));
????????}
?
????????//如果是同一時間生成的，則進行毫秒內序列
????????if?(lastTimestamp?==?timestamp)?{
????????????sequence?=?(sequence?+?1)?&?sequenceMask;
????????????//毫秒內序列溢出
????????????if?(sequence?==?0)?{
????????????????//阻塞到下一個毫秒,獲得新的時間戳
????????????????timestamp?=?tilNextMillis(lastTimestamp);
????????????}
????????}
????????//時間戳改變，毫秒內序列重置
????????else?{
????????????sequence?=?0L;
????????}
?
????????//上次生成ID的時間截
????????lastTimestamp?=?timestamp;
?
????????//移位并通過或運算拼到一起組成64位的ID
????????return?((timestamp?-?twepoch)?<<?timestampLeftShift)
????????????????|?(dataCenterId?<<?dataCenterIdShift)
????????????????|?(workerId?<<?workerIdShift)
????????????????|?sequence;
????}
?
????/**
?????*?阻塞到下一個毫秒，直到獲得新的時間戳
?????*?@param?lastTimestamp?上次生成ID的時間截
?????*?@return?當前時間戳
?????*/
????protected?long?tilNextMillis(long?lastTimestamp)?{
????????long?timestamp?=?timeGen();
????????while?(timestamp?<=?lastTimestamp)?{
????????????timestamp?=?timeGen();
????????}
????????return?timestamp;
????}
?
????/**
?????*?返回以毫秒為單位的當前時間
?????*?@return?當前時間(毫秒)
?????*/
????protected?long?timeGen()?{
????????return?System.currentTimeMillis();
????}
?
????private?static?Long?getWorkId(){
????????try?{
????????????String?hostAddress?=?Inet4Address.getLocalHost().getHostAddress();
????????????int[]?ints?=?StringUtils.toCodePoints(hostAddress);
????????????int?sums?=?0;
????????????for(int?b?:?ints){
????????????????sums?+=?b;
????????????}
????????????return?(long)(sums?%?32);
????????}?catch?(UnknownHostException?e)?{
????????????//?如果獲取失敗，則使用隨機數備用
????????????return?RandomUtils.nextLong(0,31);
????????}
????}
?
????private?static?Long?getDataCenterId(){
????????int[]?ints?=?StringUtils.toCodePoints(SystemUtils.getHostName());
????????int?sums?=?0;
????????for?(int?i:?ints)?{
????????????sums?+=?i;
????????}
????????return?(long)(sums?%?32);
????}
?
?
????/**
?????*?靜態(tài)工具類
?????*
?????*?@return
?????*/
????public?static?synchronized?Long?generateId(){
????????long?id?=?idWorker.nextId();
????????return?id;
????}
?
????//==============================Test=============================================
????/**?測試?*/
????public?static?void?main(String[]?args)?{
????????System.out.println(System.currentTimeMillis());
????????long?startTime?=?System.nanoTime();
????????for?(int?i?=?0;?i?<?50000;?i++)?{
????????????long?id?=?SnowflakeIdWorker.generateId();
????????????System.out.println(id);
????????}
????????System.out.println((System.nanoTime()-startTime)/1000000+"ms");
????}
}
參考原文：https://blog.csdn.net/xiaopeng9275/article/details/72123709
分享和在看是對我最大的鼓勵。我是pub哥，我們下期見!
