一、Java原生API提供UUID生成方法^[1]

說明：

public final class UUID extends Object implements Serializable, Comparable<UUID>

一個表示不可變的通用唯一標(biāo)識符（UUID）的類践惑。UUID表示128位值腹泌。

這些全局標(biāo)識符存在不同的變體。 該類的方法是用于操縱Leach-Salz變體尔觉，盡管構(gòu)造函數(shù)允許創(chuàng)建UUID的任何變體（如下所述）凉袱。

變體2（Leach-Salz）UUID的布局如下：最重要的長度包括以下無符號字段：

0xFFFFFFFF00000000 time_low
0x00000000FFFF0000 time_mid
0x000000000000F000 version
0x0000000000000FFF time_hi 

最不重要的長度包括以下無符號字段：

0xC000000000000000 variant
0x3FFF000000000000 clock_seq
0x0000FFFFFFFFFFFF node 

變量字段包含一個標(biāo)識UUID的布局的UUID 。上述的位布局僅用于有效UUID為2的變體值，其指示里奇- SALZ變體专甩。

版本字段保存描述此類型的值UUID钟鸵。UUID有四種不同的基本類型：基于時間，DCE安全性涤躲，基于名稱和隨機(jī)生成的UUID棺耍。 這些類型的版本值分別為1，2篓叶，3和4烈掠。

public static UUID randomUUID()

靜態(tài)工廠檢索一個類型4（偽隨機(jī)生成）的UUID。  `UUID`是使用加密強(qiáng)偽隨機(jī)數(shù)生成器生成的缸托。

Example Code:

import java.util.UUID;

public class Util {
    public static void main(String args[]) {
        UUID uuid = UUID.randomUUID();
        String strUUID = uuid.toString();
        System.out.println(uuid + strUUID);
    }
}

//UUID字符串表示形式由此BNF描述： 

 UUID                   = <time_low> "-" <time_mid> "-"
                          <time_high_and_version> "-"
                          <variant_and_sequence> "-"
                          <node>
 time_low               = 4*<hexOctet>
 time_mid               = 2*<hexOctet>
 time_high_and_version  = 2*<hexOctet>
 variant_and_sequence   = 2*<hexOctet>
 node                   = 6*<hexOctet>
 hexOctet               = <hexDigit><hexDigit>
 hexDigit               =
       "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
       | "a" | "b" | "c" | "d" | "e" | "f"
       | "A" | "B" | "C" | "D" | "E" | "F"

優(yōu)點(diǎn)：

1左敌、本地生成ID，不需要進(jìn)行遠(yuǎn)程調(diào)用俐镐，時延低矫限。

2、擴(kuò)展性好佩抹，基本可以人為沒有性能上限叼风。

3、全球唯一棍苹。

4无宿、在遇見數(shù)據(jù)遷移、系統(tǒng)數(shù)據(jù)合并或者數(shù)據(jù)庫變更的情況下可以從容應(yīng)對枢里。

缺點(diǎn)：

1孽鸡、沒有排序，無法保證趨勢遞增

2栏豺、UUID過長彬碱，往往用字符串表示（數(shù)據(jù)庫主鍵基本用整型類型表示），作為主鍵建立索引查詢效率低奥洼，常見優(yōu)化方案為轉(zhuǎn)化兩個uint64整數(shù)存儲或者折半存儲（折半后不能保證唯一性）

3巷疼、存儲空間比較大，如果是海量數(shù)據(jù)庫灵奖，就需要考慮存儲量的問題嚼沿。

4、傳輸數(shù)據(jù)量大瓷患。

5伏尼、不可讀。

?

二尉尾、UUID的變種

1爆阶、UUID to int64

Example Code :

/// <summary>
/// 根據(jù)GUID獲取唯一數(shù)字序列
/// </summary>
public static long GuidToInt64()
{
    byte[] bytes = Guid.NewGuid().ToByteArray();
    return BitConverter.ToInt64(bytes, 0);
}

2、解決UUID無序問題

為了解決UUID無序的問題，NHibernate在其主鍵生成方式中提供了Comb算法（combined guid/timestamp）辨图。保留GUID的10個字節(jié)班套，用另6個字節(jié)表示GUID生成的時間（DateTime）。

Example Code :

/// <summary> 
/// Generate a new <see cref="Guid"/> using the comb algorithm. 
/// </summary> 
private Guid GenerateComb()
{
    byte[] guidArray = Guid.NewGuid().ToByteArray();
 
    DateTime baseDate = new DateTime(1900, 1, 1);
    DateTime now = DateTime.Now;
 
    // Get the days and milliseconds which will be used to build    
    //the byte string    
    TimeSpan days = new TimeSpan(now.Ticks - baseDate.Ticks);
    TimeSpan msecs = now.TimeOfDay;
 
    // Convert to a byte array        
    // Note that SQL Server is accurate to 1/300th of a    
    // millisecond so we divide by 3.333333    
    byte[] daysArray = BitConverter.GetBytes(days.Days);
    byte[] msecsArray = BitConverter.GetBytes((long)
      (msecs.TotalMilliseconds / 3.333333));
 
    // Reverse the bytes to match SQL Servers ordering    
    Array.Reverse(daysArray);
    Array.Reverse(msecsArray);
 
    // Copy the bytes into the guid    
    Array.Copy(daysArray, daysArray.Length - 2, guidArray,
      guidArray.Length - 6, 2);
    Array.Copy(msecsArray, msecsArray.Length - 4, guidArray,
      guidArray.Length - 4, 4);
 
    return new Guid(guidArray);
}

用上面的算法測試一下故河，得到如下的結(jié)果：作為比較吱韭，前面3個是使用COMB算法得出的結(jié)果，最后12個字符串是時間序（統(tǒng)一毫秒生成的3個UUID）鱼的，過段時間如果再次生成理盆，則12個字符串會比圖示的要大。后面3個是直接生成的GUID凑阶。

如果想把時間序放在前面猿规，可以生成后改變12個字符串的位置，也可以修改算法類的最后兩個Array.Copy宙橱。

?

三姨俩、時間戳

說明：

直接取當(dāng)前毫秒時間戳，用整型類型表示师郑。

優(yōu)點(diǎn)：

效率高环葵，為整型數(shù)據(jù)

缺點(diǎn)：

如果并發(fā)量超過1000，會生成重復(fù)ID宝冕，對于高并發(fā)的場景無法勝任

四张遭、獨(dú)立的ID生成服務(wù)

說明：

專門搭建一個系統(tǒng)用來給各個接入系統(tǒng)分配唯一ID，每個系統(tǒng)每次來請求的時候返回一段ID地梨，系統(tǒng)拿到自己用帝璧，用完后，再來申請湿刽，再次分配下一區(qū)段的，以此類推褐耳。

優(yōu)點(diǎn)：

性能效率沒問題诈闺，區(qū)間分配，效率很高

缺點(diǎn)：

可靠性要求非常高铃芦，如果ID生成服務(wù)出現(xiàn)故障雅镊，那對其它所有系統(tǒng)來說都是災(zāi)難

?

五、SnowFlake算法（雪花算法）

說明：

這是twitter的一個id生成算法

Twitter-Snowflake算法產(chǎn)生的背景相當(dāng)簡單刃滓，為了滿足Twitter每秒上萬條消息的請求仁烹，每條消息都必須分配一條唯一的id，這些id還需要一些大致的順序（方便客戶端排序）咧虎，并且在分布式系統(tǒng)中不同機(jī)器產(chǎn)生的id必須不同卓缰。

首先我們需要一個long類型的變量來保存這個生成的id，第一位固定為0，因?yàn)閕d都是正數(shù)嘛征唬，還剩63位捌显，用x位表示毫秒時間戳，用y位表示進(jìn)程id总寒，用z位表示同一個時間戳下的序列號扶歪，x+y+z=63。

原理圖如下：

算法解釋：

1摄闸、第一部分善镰，1位為標(biāo)識位，不用年枕。

2炫欺、第二部分，41位画切，用來記錄當(dāng)前時間與標(biāo)記時間twepoch的毫秒數(shù)的差值竣稽，41位的時間截，可以使用69年霍弹，T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69

3毫别、第三部分，10位典格，用來記錄當(dāng)前節(jié)點(diǎn)的信息岛宦，支持2的10次方臺機(jī)器

4、第四部分耍缴，12位砾肺，用來支持每個節(jié)點(diǎn)每毫秒(同一機(jī)器，同一時間截)產(chǎn)生4096個ID序號

Example Code :

/**
 * Twitter_Snowflake<br>
 * SnowFlake的結(jié)構(gòu)如下(每部分用-分開):<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
 * SnowFlake的優(yōu)點(diǎn)是防嗡，整體上按照時間自增排序变汪，并且整個分布式系統(tǒng)內(nèi)不會產(chǎn)生ID碰撞(由數(shù)據(jù)中心ID和機(jī)器ID作區(qū)分)
 */
public class SnowflakeIdWorker {
 
    /** 開始時間截 (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 (這個移位算法可以很快的計(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;
 
    /** 時間截向左移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的時間截 */
    private long lastTimestamp = -1L;
 
    /**
     * 構(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;
    }
 
    /**
     * 獲得下一個ID (該方法是線程安全的)
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();
 
        //如果當(dāng)前時間小于上一次ID生成的時間戳，說明系統(tǒng)時鐘回退過這個時候應(yīng)當(dāng)拋出異常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(
                    String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }
 
        //如果是同一時間生成的他嫡，則進(jìn)行毫秒內(nèi)序列
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            //毫秒內(nèi)序列溢出
            if (sequence == 0) {
                //阻塞到下一個毫秒,獲得新的時間戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        //時間戳改變番官，毫秒內(nèi)序列重置
        else {
            sequence = 0L;
        }
 
        //上次生成ID的時間截
        lastTimestamp = timestamp;
 
        //移位并通過或運(yùn)算拼到一起組成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (datacenterId << datacenterIdShift) //
                | (workerId << workerIdShift) //
                | sequence;
    }
 
    /**
     * 阻塞到下一個毫秒，直到獲得新的時間戳
     * @param lastTimestamp 上次生成ID的時間截
     * @return 當(dāng)前時間戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }
 
    /**
     * 返回以毫秒為單位的當(dāng)前時間
     * @return 當(dāng)前時間(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }
}

評價(jià)：

41的時間戳钢属，存儲當(dāng)前時間戳與開始時間戳的差值徘熔，大概可以用69年，當(dāng)然x,y,z可以自己根據(jù)情況分配淆党，不是固定的酷师。

此方法同樣是本地生成讶凉，效率非常高，唯一性滿足度很高窒升，只需要以上一個類就行了缀遍，每個進(jìn)程啟動時，分配不同的processId即可饱须。

?

六域醇、數(shù)據(jù)庫自增序列或字段

說明：

最常見的方式。利用數(shù)據(jù)庫蓉媳，全數(shù)據(jù)庫唯一譬挚。

優(yōu)點(diǎn)：

1）簡單，代碼方便酪呻，性能可以接受减宣。

2）數(shù)字ID天然排序，對分頁或者需要排序的結(jié)果很有幫助玩荠。

缺點(diǎn)：

1漆腌、不同數(shù)據(jù)庫語法和實(shí)現(xiàn)不同，數(shù)據(jù)庫遷移的時候或多數(shù)據(jù)庫版本支持的時候需要處理阶冈。

2闷尿、在單個數(shù)據(jù)庫或讀寫分離或一主多從的情況下，只有一個主庫可以生成女坑。有單點(diǎn)故障的風(fēng)險(xiǎn)填具。

3、在性能達(dá)不到要求的情況下匆骗，比較難于擴(kuò)展劳景。

4、如果遇見多個系統(tǒng)需要合并或者涉及到數(shù)據(jù)遷移會相當(dāng)痛苦碉就。

5盟广、分表分庫的時候會有麻煩。

優(yōu)化方案：

針對主庫單點(diǎn)瓮钥，如果有多個Master庫筋量，則每個Master庫設(shè)置的起始數(shù)字不一樣，步長一樣骏庸，可以是Master的個數(shù)。比如：Master1 生成的是 1年叮，4具被，7，10只损，Master2生成的是2,5,8,11 Master3生成的是 3,6,9,12一姿。這樣就可以有效生成集群中的唯一ID七咧，也可以大大降低ID生成數(shù)據(jù)庫操作的負(fù)載。

?

七叮叹、參考文章

【JAVA】系統(tǒng)唯一ID生成方案討論

常見分布式全局唯一ID生成策略及算法的對比

全局唯一ID生成器(SnowFlakeId算法JAVA實(shí)現(xiàn))

分布式系統(tǒng)唯一ID生成方案匯總

雪花算法-全局唯一ID生成器

?

更多內(nèi)容查看：

分布式ID生成器

全局唯一ID生成策略

分布式系統(tǒng)里用戶ID生成有什么好的方法和規(guī)則能滿足“唯一艾栋、盡量短、不能直接看出規(guī)則”這幾個條件?

十位用戶唯一ID生成策略

?

八蛉顽、引用

1. JDK v1.8 API java.util.UUID ?