Twitter的分布式自增ID算法snowflake (Java版)

概述

分布式系統中，有一些需要使用全局唯一ID的場景，這種時候為了防止ID沖突可以使用36位的UUID，但是UUID有一些缺點，首先他相對比較長，另外UUID一般是無序的。

有些時候我們希望能使用一種簡單一些的ID，并且希望ID能夠按照時間有序生成。

而twitter的snowflake解決了這種需求，最初Twitter把存儲系統從MySQL遷移到Cassandra，因為Cassandra沒有順序ID生成機制，是以開發了這樣一套全局唯一ID生成服務。

結構

snowflake的結構如下(每部分用-分開):

0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

第一位為未使用，接下來的41位為毫秒級時間(41位的長度可以使用69年)，然後是5位datacenterId和5位workerId(10位的長度最多支援部署1024個節點） ，最後12位是毫秒内的計數（12位的計數順序号支援每個節點每毫秒産生4096個ID序号）

一共加起來剛好64位，為一個Long型。(轉換成字元串後長度最多19)

snowflake生成的ID整體上按照時間自增排序，并且整個分布式系統内不會産生ID碰撞（由datacenter和workerId作區分），并且效率較高。經測試snowflake每秒能夠産生26萬個ID。

源碼

(JAVA版本的源碼)

/**
 * 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個節點，包括5位datacenterId和5位workerId<br>
 * 12位序列，毫秒内的計數，12位的計數順序号支援每個節點每毫秒(同一機器，同一時間截)産生4096個ID序号<br>
 * 加起來剛好64位，為一個Long型。<br>
 * SnowFlake的優點是，整體上按照時間自增排序，并且整個分布式系統内不會産生ID碰撞(由資料中心ID和機器ID作區分)，并且效率較高，經測試，SnowFlake每秒能夠産生26萬ID左右。
 */
public class SnowflakeIdWorker {
       
</span><span style="color: #008000;">//</span><span style="color: #008000;"> ==============================Fields===========================================</span>
<span style="color: #008000;">/**</span><span style="color: #008000;"> 開始時間截 (2015-01-01) </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">final</span> <span style="color: #0000ff;">long</span> twepoch = <span style="font-family: Courier New;">1420041600000</span>L<span style="color: #000000;">;

</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 機器id所占的位數 </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">final</span> <span style="color: #0000ff;">long</span> workerIdBits = 5L<span style="color: #000000;">;

</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 資料辨別id所占的位數 </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">final</span> <span style="color: #0000ff;">long</span> datacenterIdBits = 5L<span style="color: #000000;">;

</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 支援的最大機器id，結果是31 (這個移位算法可以很快的計算出幾位二進制數所能表示的最大十進制數) </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">final</span> <span style="color: #0000ff;">long</span> maxWorkerId = -1L ^ (-1L &lt;&lt;<span style="color: #000000;"> workerIdBits);

</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 支援的最大資料辨別id，結果是31 </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">final</span> <span style="color: #0000ff;">long</span> maxDatacenterId = -1L ^ (-1L &lt;&lt;<span style="color: #000000;"> datacenterIdBits);

</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 序列在id中占的位數 </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">final</span> <span style="color: #0000ff;">long</span> sequenceBits = 12L<span style="color: #000000;">;

</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 機器ID向左移12位 </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">final</span> <span style="color: #0000ff;">long</span> workerIdShift =<span style="color: #000000;"> sequenceBits;

</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 資料辨別id向左移17位(12+5) </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">final</span> <span style="color: #0000ff;">long</span> datacenterIdShift = sequenceBits +<span style="color: #000000;"> workerIdBits;

</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 時間截向左移22位(5+5+12) </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">final</span> <span style="color: #0000ff;">long</span> timestampLeftShift = sequenceBits + workerIdBits +<span style="color: #000000;"> datacenterIdBits;

</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 生成序列的掩碼，這裡為4095 (0b111111111111=0xfff=4095) </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">final</span> <span style="color: #0000ff;">long</span> sequenceMask = -1L ^ (-1L &lt;&lt;<span style="color: #000000;"> sequenceBits);

</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 工作機器ID(0~31) </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">long</span><span style="color: #000000;"> workerId;

</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 資料中心ID(0~31) </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">long</span><span style="color: #000000;"> datacenterId;

</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 毫秒内序列(0~4095) </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">long</span> sequence = 0L<span style="color: #000000;">;

</span><span style="color: #008000;">/**</span><span style="color: #008000;"> 上次生成ID的時間截 </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">private</span> <span style="color: #0000ff;">long</span> lastTimestamp = -1L<span style="color: #000000;">;

</span><span style="color: #008000;">//</span><span style="color: #008000;">==============================Constructors=====================================</span>
<span style="color: #008000;">/**</span><span style="color: #008000;">
 * 構造函數
 * </span><span style="color: #808080;">@param</span><span style="color: #008000;"> workerId 工作ID (0~31)
 * </span><span style="color: #808080;">@param</span><span style="color: #008000;"> datacenterId 資料中心ID (0~31)
 </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">public</span> SnowflakeIdWorker(<span style="color: #0000ff;">long</span> workerId, <span style="color: #0000ff;">long</span><span style="color: #000000;"> datacenterId) {
    </span><span style="color: #0000ff;">if</span> (workerId &gt; maxWorkerId || workerId &lt; 0<span style="color: #000000;">) {
        </span><span style="color: #0000ff;">throw</span> <span style="color: #0000ff;">new</span> IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0"<span style="color: #000000;">, maxWorkerId));
    }
    </span><span style="color: #0000ff;">if</span> (datacenterId &gt; maxDatacenterId || datacenterId &lt; 0<span style="color: #000000;">) {
        </span><span style="color: #0000ff;">throw</span> <span style="color: #0000ff;">new</span> IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0"<span style="color: #000000;">, maxDatacenterId));
    }
    </span><span style="color: #0000ff;">this</span>.workerId =<span style="color: #000000;"> workerId;
    </span><span style="color: #0000ff;">this</span>.datacenterId =<span style="color: #000000;"> datacenterId;
}

</span><span style="color: #008000;">//</span><span style="color: #008000;"> ==============================Methods==========================================</span>
<span style="color: #008000;">/**</span><span style="color: #008000;">
 * 獲得下一個ID (該方法是線程安全的)
 * </span><span style="color: #808080;">@return</span><span style="color: #008000;"> SnowflakeId
 </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">public</span> <span style="color: #0000ff;">synchronized</span> <span style="color: #0000ff;">long</span><span style="color: #000000;"> nextId() {
    </span><span style="color: #0000ff;">long</span> timestamp =<span style="color: #000000;"> timeGen();

    </span><span style="color: #008000;">//</span><span style="color: #008000;">如果目前時間小于上一次ID生成的時間戳，說明系統時鐘回退過這個時候應當抛出異常</span>
    <span style="color: #0000ff;">if</span> (timestamp &lt;<span style="color: #000000;"> lastTimestamp) {
        </span><span style="color: #0000ff;">throw</span> <span style="color: #0000ff;">new</span><span style="color: #000000;"> RuntimeException(
                String.format(</span>"Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp -<span style="color: #000000;"> timestamp));
    }

    </span><span style="color: #008000;">//</span><span style="color: #008000;">如果是同一時間生成的，則進行毫秒内序列</span>
    <span style="color: #0000ff;">if</span> (lastTimestamp ==<span style="color: #000000;"> timestamp) {
        sequence </span>= (sequence + 1) &amp;<span style="color: #000000;"> sequenceMask;
        </span><span style="color: #008000;">//</span><span style="color: #008000;">毫秒内序列溢出</span>
        <span style="color: #0000ff;">if</span> (sequence == 0<span style="color: #000000;">) {
            </span><span style="color: #008000;">//</span><span style="color: #008000;">阻塞到下一個毫秒,獲得新的時間戳</span>
            timestamp =<span style="color: #000000;"> tilNextMillis(lastTimestamp);
        }
    }
    </span><span style="color: #008000;">//</span><span style="color: #008000;">時間戳改變，毫秒内序列重置</span>
    <span style="color: #0000ff;">else</span><span style="color: #000000;"> {
        sequence </span>= 0L<span style="color: #000000;">;
    }

    </span><span style="color: #008000;">//</span><span style="color: #008000;">上次生成ID的時間截</span>
    lastTimestamp =<span style="color: #000000;"> timestamp;

    </span><span style="color: #008000;">//</span><span style="color: #008000;">移位并通過或運算拼到一起組成64位的ID</span>
    <span style="color: #0000ff;">return</span> ((timestamp - twepoch) &lt;&lt; timestampLeftShift) <span style="color: #008000;">//
           
        


                | (datacenterId << datacenterIdShift) //

                | (workerId << workerIdShift) //

                | sequence;

}

       
</span><span style="color: #008000;">/**</span><span style="color: #008000;">
 * 阻塞到下一個毫秒，直到獲得新的時間戳
 * </span><span style="color: #808080;">@param</span><span style="color: #008000;"> lastTimestamp 上次生成ID的時間截
 * </span><span style="color: #808080;">@return</span><span style="color: #008000;"> 目前時間戳
 </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">protected</span> <span style="color: #0000ff;">long</span> tilNextMillis(<span style="color: #0000ff;">long</span><span style="color: #000000;"> lastTimestamp) {
    </span><span style="color: #0000ff;">long</span> timestamp =<span style="color: #000000;"> timeGen();
    </span><span style="color: #0000ff;">while</span> (timestamp &lt;=<span style="color: #000000;"> lastTimestamp) {
        timestamp </span>=<span style="color: #000000;"> timeGen();
    }
    </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> timestamp;
}

</span><span style="color: #008000;">/**</span><span style="color: #008000;">
 * 傳回以毫秒為機關的目前時間
 * </span><span style="color: #808080;">@return</span><span style="color: #008000;"> 目前時間(毫秒)
 </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">protected</span> <span style="color: #0000ff;">long</span><span style="color: #000000;"> timeGen() {
    </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> System.currentTimeMillis();
}

</span><span style="color: #008000;">//</span><span style="color: #008000;">==============================Test=============================================</span>
<span style="color: #008000;">/**</span><span style="color: #008000;"> 測試 </span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">public</span> <span style="color: #0000ff;">static</span> <span style="color: #0000ff;">void</span><span style="color: #000000;"> main(String[] args) {
    SnowflakeIdWorker idWorker </span>= <span style="color: #0000ff;">new</span> SnowflakeIdWorker(0, 0<span style="color: #000000;">);
    </span><span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">int</span> i = 0; i &lt; 1000; i++<span style="color: #000000;">) {
        </span><span style="color: #0000ff;">long</span> id =<span style="color: #000000;"> idWorker.nextId();
        System.out.println(Long.toBinaryString(id));
        System.out.println(id);
    }
}
           
        


}
      

參考

https://github.com/twitter/snowflake

原文位址：https://www.cnblogs.com/relucent/p/4955340.html