歡迎光臨
每天分享高質量文章

如果再有人問你分佈式ID,這篇文章丟給他

來自:咖啡拿鐵(微信號:close_3092860495)

1.背景

在我們的業務需求中通常有需要一些唯一的ID,來記錄我們某個資料的標識:

  • 某個用戶的ID

  • 某個訂單的單號

  • 某個信息的ID

通常我們會調研各種各樣的生成策略,根據不同的業務,採取最合適的策略,下麵我會討論一下各種策略/演算法,以及他們的一些優劣點。

2.UUID

UUID是通用唯一識別碼(Universally Unique Identifier)的縮寫,開放軟體基金會(OSF)規範定義了包括網卡MAC地址、時間戳、名字空間(Namespace)、隨機或偽隨機數、時序等元素。利用這些元素來生成UUID。

UUID是由128位二進制組成,一般轉換成十六進制,然後用String表示。在java中有個UUID類,在他的註釋中我們看見這裡有4種不同的UUID的生成策略:

  • randomly: 基於隨機數生成UUID,由於Java中的隨機數是偽隨機數,其重覆的概率是可以被計算出來的。這個一般我們用下麵的代碼獲取基於隨機數的UUID:

  • time-based:基於時間的UUID,這個一般是通過當前時間,隨機數,和本地Mac地址來計算出來,自帶的JDK包並沒有這個演算法的我們在一些UUIDUtil中,比如我們的log4j.core.util,會重新定義UUID的高位和低位。

  • DCE security:DCE安全的UUID。

  • name-based:基於名字的UUID,通過計算名字和名字空間的MD5來計算UUID。

UUID的優點:

  • 通過本地生成,沒有經過網絡I/O,性能較快

  • 無序,無法預測他的生成順序。(當然這個也是他的缺點之一)

UUID的缺點:

  • 128位二進制一般轉換成36位的16進制,太長了只能用String儲存,空間占用較多。

  • 不能生成遞增有序的數字

適用場景:UUID的適用場景可以為不擔心過多的空間占用,以及不需要生成有遞增趨勢的數字。在Log4j裡面他在UuidPatternConverter中加入了UUID來標識每一條日誌。

3.資料庫主鍵自增

大家對於唯一標識最容易想到的就是主鍵自增,這個也是我們最常用的方法。例如我們有個訂單服務,那麼把訂單id設置為主鍵自增即可。

優點:

  • 簡單方便,有序遞增,方便排序和分頁

缺點:

  • 分庫分表會帶來問題,需要進行改造。

  • 併發性能不高,受限於資料庫的性能。

  • 簡單遞增容易被其他人猜測利用,比如你有一個用戶服務用的遞增,那麼其他人可以根據分析註冊的用戶ID來得到當天你的服務有多少人註冊,從而就能猜測出你這個服務當前的一個大概狀況。

  • 資料庫宕機服務不可用。

適用場景:
根據上面可以總結出來,當資料量不多,併發性能不高的時候這個很適合,比如一些to B的業務,商家註冊這些,商家註冊和用戶註冊不是一個數量級的,所以可以資料庫主鍵遞增。如果對順序遞增強依賴,那麼也可以使用資料庫主鍵自增。

4.Redis

熟悉Redis的同學,應該知道在Redis中有兩個命令Incr,IncrBy,因為Redis是單執行緒的所以能保證原子性。

優點:

  • 性能比資料庫好,能滿足有序遞增。

缺點:

  • 由於redis是記憶體的KV資料庫,即使有AOF和RDB,但是依然會存在資料丟失,有可能會造成ID重覆。

  • 依賴於redis,redis要是不穩定,會影響ID生成。

適用:由於其性能比資料庫好,但是有可能會出現ID重覆和不穩定,這一塊如果可以接受那麼就可以使用。也適用於到了某個時間,比如每天都掃清ID,那麼這個ID就需要重置,通過(Incr Today),每天都會從0開始加。

5.Zookeeper

利用ZK的Znode資料版本如下麵的代碼,每次都不獲取期望版本號也就是每次都會成功,那麼每次都會傳回最新的版本號:

Zookeeper這個方案用得較少,嚴重依賴Zookeeper集群,並且性能不是很高,所以不予推薦。

6.資料庫分段+服務快取ID

這個方法在美團的Leaf中有介紹,詳情可以參考美團技術團隊的發佈的技術文章:Leaf——美團點評分佈式ID生成系統,這個方案是將資料庫主鍵自增進行優化。

biz_tag代表每個不同的業務,max_id代表每個業務設置的大小,step代表每個proxyServer快取的步長。
之前我們的每個服務都訪問的是資料庫,現在不需要,每個服務直接和我們的ProxyServer做交互,減少了對資料庫的依賴。我們的每個ProxyServer回去資料庫中拿出步長的長度,比如server1拿到了1-1000,server2拿到來 1001-2000。如果用完會再次去資料庫中拿。

優點:

  • 比主鍵遞增性能高,能保證趨勢遞增。

  • 如果DB宕機,proxServer由於有快取依然可以堅持一段時間。

缺點:

  • 和主鍵遞增一樣,容易被人猜測。

  • DB宕機,雖然能支撐一段時間但是仍然會造成系統不可用。

適用場景:需要趨勢遞增,並且ID大小可控制的,可以使用這套方案。

當然這個方案也可以通過一些手段避免被人猜測,把ID變成是無序的,比如把我們生成的資料是一個遞增的long型,把這個Long分成幾個部分,比如可以分成幾組三位數,幾組四位數,然後在建立一個映射表,將我們的資料變成無序。

7.雪花演算法-Snowflake

Snowflake是Twitter提出來的一個演算法,其目的是生成一個64bit的整數:

  • 1bit:一般是符號位,不做處理

  • 41bit:用來記錄時間戳,這裡可以記錄69年,如果設置好起始時間比如今年是2018年,那麼可以用到2089年,到時候怎麼辦?要是這個系統能用69年,我相信這個系統早都重構了好多次了。

  • 10bit:10bit用來記錄機器ID,總共可以記錄1024台機器,一般用前5位代表資料中心,後面5位是某個資料中心的機器ID

  • 12bit:迴圈位,用來對同一個毫秒之內產生不同的ID,12位可以最多記錄4095個,也就是在同一個機器同一毫秒最多記錄4095個,多餘的需要進行等待下毫秒。

上面只是一個將64bit劃分的標準,當然也不一定這麼做,可以根據不同業務的具體場景來劃分,比如下麵給出一個業務場景:

  • 服務目前QPS10萬,預計幾年之內會發展到百萬。

  • 當前機器三地部署,上海,北京,深圳都有。

  • 當前機器10台左右,預計未來會增加至百台。

這個時候我們根據上面的場景可以再次合理的劃分62bit,QPS幾年之內會發展到百萬,那麼每毫秒就是千級的請求,目前10台機器那麼每台機器承擔百級的請求,為了保證擴展,後面的迴圈位可以限制到1024,也就是2^10,那麼迴圈位10位就足夠了。

機器三地部署我們可以用3bit總共8來表示機房位置,當前的機器10台,為了保證擴展到百台那麼可以用7bit 128來表示,時間位依然是41bit,那麼還剩下64-10-3-7-41-1 = 2bit,還剩下2bit可以用來進行擴展。

適用場景:當我們需要無序不能被猜測的ID,並且需要一定高性能,且需要long型,那麼就可以使用我們雪花演算法。比如常見的訂單ID,用雪花演算法別人就發猜測你每天的訂單量是多少。

7.1一個簡單的Snowflake

public class IdWorker{

    private long workerId;
    private long datacenterId;
    private long sequence = 0;
    /**
     * 2018/9/29日,從此時開始計算,可以用到2089年
     */

    private long twepoch = 1538211907857L;

    private long workerIdBits = 5L;
    private long datacenterIdBits = 5L;
    private long sequenceBits = 12L;

    private long workerIdShift = sequenceBits;
    private long datacenterIdShift = sequenceBits + workerIdBits;
    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    // 得到0000000000000000000000000000000000000000000000000000111111111111
    private long sequenceMask = -1L ^ (-1L <
    private long lastTimestamp = -1L;


    public IdWorker(long workerId, long datacenterId){
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }
    public synchronized long nextId() {
        long timestamp = timeGen();
        //時間回撥,丟擲異常
        if (timestamp             System.err.printf("clock is moving backwards.  Rejecting requests until %d.", 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 = 0;
        }

        lastTimestamp = timestamp;
        return ((timestamp - twepoch) <                (datacenterId <                (workerId <                sequence;
    }

    /**
     * 當前ms已經滿了
     * @param lastTimestamp
     * @return
     */

    private long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    private long timeGen(){
        return System.currentTimeMillis();
    }

    public static void main(String[] args) {
        IdWorker worker = new IdWorker(1,1);
        for (int i = 0; i 30
; i++) {
            System.out.println(worker.nextId());
        }
    }

}

上面定義了雪花演算法的實現,在nextId中是我們生成雪花演算法的關鍵。

7.2防止時鐘回撥

因為機器的原因會發生時間回撥,我們的雪花演算法是強依賴我們的時間的,如果時間發生回撥,有可能會生成重覆的ID,在我們上面的nextId中我們用當前時間和上一次的時間進行判斷,如果當前時間小於上一次的時間那麼肯定是發生了回撥,普通的演算法會直接丟擲異常,這裡我們可以對其進行優化,一般分為兩個情況:

  • 如果時間回撥時間較短,比如配置5ms以內,那麼可以直接等待一定的時間,讓機器的時間追上來。

  • 如果時間的回撥時間較長,我們不能接受這麼長的阻塞等待,那麼又有兩個策略:

  1. 直接拒絕,丟擲異常,打日誌,通知RD時鐘回滾。

  2. 利用擴展位,上面我們討論過不同業務場景位數可能用不到那麼多,那麼我們可以把擴展位數利用起來了,比如當這個時間回撥比較長的時候,我們可以不需要等待,直接在擴展位加1。2位的擴展位允許我們有3次大的時鐘回撥,一般來說就夠了,如果其超過三次我們還是選擇丟擲異常,打日誌。

通過上面的幾種策略可以比較的防護我們的時鐘回撥,防止出現回撥之後大量的異常出現。下麵是修改之後的代碼,這裡修改了時鐘回撥的邏輯:

最後

本文分析了各種生產分佈式ID的演算法的原理,以及他們的適用場景,相信你已經能為自己的專案選擇好一個合適的分佈式ID生成策略了。沒有一個策略是完美的,只有適合自己的才是最好的。


編號810,輸入編號直達本文

●輸入m獲取文章目錄

推薦↓↓↓

Web開發

更多推薦18個技術類微信公眾號

涵蓋:程式人生、演算法與資料結構、黑客技術與網絡安全、大資料技術、前端開發、Java、Python、Web開發、安卓開發、iOS開發、C/C++、.NET、Linux、資料庫、運維等。

赞(0)

分享創造快樂