[[428490]]

介紹

在很多業務系統中，我們經常會遇到生成全局唯一的分布式ID的需求，如IM系統，訂單系統等。那么生成全局唯一的分布式ID的方法有哪些呢?

UUID

// 3eece1c6-5b57-4bce-a306-6c49e44a1f90 
UUID.randomUUID().toString() 

「本地生成，生成速度快，但識別性差，沒有順序性」

可以用來標識圖片等，不能用作數據庫主鍵

數據庫自增主鍵

「我們原來剛開始做IM系統的時候就單獨建了一個表來獲取自增id作為消息的ID」，單獨開一張表來獲取自增id也不會影響對消息分庫分表

Zookeeper

「每次要生成一個新Id時，創建一個持久順序節點，創建操作返回的節點序號，即為新Id，然后把比自己節點小的刪除即可」

這種方式能生成的Id比較少，因為數字位數比較少

Redis

「用incr命令即可實現」

設置一個key為userId，值為0，每次獲取userId的時候，對userId加1再獲取

set userId 0 
incr usrId //返回1 

每獲取一次id都會和redis有一個網絡交互的過程，因此可以改進為如下形式

直接獲取一段userId的最大值，緩存到本地慢慢累加，快到了userId的最大值時，再去獲取一段，一個用戶服務宕機了，也頂多一小段userId沒有用到

set userId 0 
incr usrId //返回1 
incrby userId 1000 //返回10001 

雪花算法

「雪花算法是最常見的解決方案，滿足全局唯一，趨勢遞增，因此可以用來作為數據庫主鍵」

雪花算法是由Twitter公布的分布式主鍵生成算法，它能夠保證不同進程主鍵的不重復性，以及相同進程主鍵的有序性。

在同一個進程中，它首先是通過時間位保證不重復，如果時間相同則是通過序列位保證。同時由于時間位是單調遞增的，且各個服務器如果大體做了時間同步，那么生成的主鍵在分布式環境可以認為是總體有序的，這就保證了對索引字段的插入的高效性。例如MySQL的Innodb存儲引擎的主鍵。

使用雪花算法生成的主鍵，二進制表示形式包含4部分，從高位到低位分表為：1bit符號位、41bit時間戳位、10bit工作進程位以及12bit序列號位。

「符號位(1bit)」

預留的符號位，恒為零。

「時間戳位(41bit)」

41位的時間戳可以容納的毫秒數是2的41次冪，一年所使用的毫秒數是：365 * 24 * 60 * 60 * 1000。通過計算可知：

Math.pow(2, 41) / (365 * 24 * 60 * 60 * 1000L); 

結果約等于69.73年。ShardingSphere的雪花算法的時間紀元從2016年11月1日零點開始，可以使用到2086年，相信能滿足絕大部分系統的要求。

「工作進程位(10bit)」

該標志在Java進程內是唯一的，如果是分布式應用部署應保證每個工作進程的id是不同的。該值默認為0，可通過屬性設置。

「一般情況這10bit會拆分為2個5bit」

前5個bit代表機房id，最多代表 2 ^ 5 個機房(32 個機房) 后5個bit代表機器id，每個機房里可以代表 2 ^ 5 個機器(32 臺機器)

「因此這個服務最多可以部署在 2^10 臺機器上，也就是1024臺機器」

「序列號位(12bit)」

該序列是用來在同一個毫秒內生成不同的ID。如果在這個毫秒內生成的數量超過4096(2的12次冪)，那么生成器會等待到下個毫秒繼續生成。

理解了實現思路，我們來把算法實現一遍

public class SnowFlake { 
 
    /** 
     * 起始的時間戳 
     */ 
    private final static long START_STMP = 1480166465631L; 
 
    /** 
     * 每一部分占用的位數 
     */ 
    private final static long SEQUENCE_BIT = 12; //序列號占用的位數 
    private final static long MACHINE_BIT = 5;   //機器標識占用的位數 
    private final static long DATACENTER_BIT = 5;//數據中心占用的位數 
 
    /** 
     * 每一部分的最大值 
     */ 
    private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT); 
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT); 
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT); 
 
    /** 
     * 每一部分向左的位移 
     */ 
    private final static long MACHINE_LEFT = SEQUENCE_BIT; 
    private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT; 
    private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT; 
 
    private long datacenterId;  //數據中心 
    private long machineId;     //機器標識 
    private long sequence = 0L; //序列號 
    private long lastStmp = -1L;//上一次時間戳 
 
    public SnowFlake(long datacenterId, long machineId) { 
        if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) { 
            throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0"); 
        } 
        if (machineId > MAX_MACHINE_NUM || machineId < 0) { 
            throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0"); 
        } 
        this.datacenterId = datacenterId; 
        this.machineId = machineId; 
    } 
 
    /** 
     * 產生下一個ID 
     * 
     * @return 
     */ 
    public synchronized long nextId() { 
        long currStmp = getNewstmp(); 
        // 發生時鐘回撥 
        if (currStmp < lastStmp) { 
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id"); 
        } 
 
        if (currStmp == lastStmp) { 
            //相同毫秒內，序列號自增 
            sequence = (sequence + 1) & MAX_SEQUENCE; 
            //同一毫秒的序列數已經達到最大 
            if (sequence == 0L) { 
                currStmp = getNextMill(); 
            } 
        } else { 
            //不同毫秒內，序列號置為0 
            sequence = 0L; 
        } 
 
        lastStmp = currStmp; 
 
        return (currStmp - START_STMP) << TIMESTMP_LEFT //時間戳部分 
                | datacenterId << DATACENTER_LEFT       //數據中心部分 
                | machineId << MACHINE_LEFT             //機器標識部分 
                | sequence;                             //序列號部分 
    } 
 
    private long getNextMill() { 
        long mill = getNewstmp(); 
        while (mill <= lastStmp) { 
            mill = getNewstmp(); 
        } 
        return mill; 
    } 
 
    private long getNewstmp() { 
        return System.currentTimeMillis(); 
    } 
 
    public static void main(String[] args) { 
        SnowFlake snowFlake = new SnowFlake(2, 3); 
 
        for (int i = 0; i < (1 << 12); i++) { 
            System.out.println(snowFlake.nextId()); 
        } 
 
    } 
} 

「這端代碼將workerid分為datacenterId和machineId，如果我們業務上不需要做區分的話，直接使用10位的workerid即可。」

workerid生成

我們可以通過zookeeper的有序節點保證id的全局唯一性，比如我通過以下命令創建一個永久有序節點

# 創建一個根節點 
create  /test '' 
# 創建永久有序節點 
create -s /test/ip-port- '' 
# 返回 Created /test/ip-port-0000000000 

「ip和port可以為應用的ip和port，規則你來定，別重復就行」

其中/test/ip-port-0000000000中的0000000000就是我們的workerid

說一個我們原來生產環境遇到的一個workerid重復的問題，生成workid的方式那叫一個簡潔

// uid為zookeeper中的一個有序持久節點 
List<String> pidListNode = zkClient.getChildren("uid"); 
String workerId = String.valueOf(pidListNode.size()); 
zkClient.create("uid", new byte[0], CreateMode.PERSISTENT_SEQUENTIAL); 

「你能看出來這段代碼為什么會造成workid重復嗎?」

它把uid子節點的數量作為workid，當2個應用同時執行到第一行代碼時，子節點數量是一樣的，得到的workerId就會重復。

有意思的是這段代碼跑了好幾年都沒有問題，直到運維把應用的發版效率提高了一點，線上就開始報錯了。因為剛開始應用是串行發版，后來改為并行發版

「當使用雪花算法的時候，有可能發生時鐘回撥，建議使用開源的框架，如美團的Leaf?！?/p>

雪花算法在很多中間件中都被使用過，如seata用來生成全局唯一的事務id

本文轉載自微信公眾號「Java識堂」，作者李立敏。轉載本文請聯系Java識堂公眾號。