一文搞定分布式系統ID生成方案

2021-12-18 java那些事

系統唯一ID是我們在設計一個系統的時候常常會遇見的問題，也常常為這個問題而糾結。生成ID的方法有很多，適應不同的場景、需求以及性能要求。所以有些比較複雜的系統會有多個ID生成的策略。下面就介紹一些常見的ID生成策略。

1. 資料庫自增長序列或欄位

最常見的方式。利用資料庫，全資料庫唯一。


優點：


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

2）數字ID天然排序，對分頁或者需要排序的結果很有幫助。


缺點：


1）不同資料庫語法和實現不同，資料庫遷移的時候或多資料庫版本支持的時候需要處理。

2）在單個資料庫或讀寫分離或一主多從的情況下，只有一個主庫可以生成。有單點故障的風險。

3）在性能達不到要求的情況下，比較難於擴展。

4）如果遇見多個系統需要合併或者涉及到數據遷移會相當痛苦。

5）分表分庫的時候會有麻煩。


優化方案：


1）針對主庫單點，如果有多個Master庫，則每個Master庫設置的起始數字不一樣，步長一樣，可以是Master的個數。比如：Master1 生成的是 1，4，7，10，Master2生成的是2,5,8,11 Master3生成的是 3,6,9,12。這樣就可以有效生成集群中的唯一ID，也可以大大降低ID生成資料庫操作的負載。


2. UUID

常見的方式。可以利用資料庫也可以利用程序生成，一般來說全球唯一。


優點：


1）簡單，代碼方便。

2）生成ID性能非常好，基本不會有性能問題。

3）全球唯一，在遇見數據遷移，系統數據合併，或者資料庫變更等情況下，可以從容應對。


缺點：


1）沒有排序，無法保證趨勢遞增。

2）UUID往往是使用字符串存儲，查詢的效率比較低。

3）存儲空間比較大，如果是海量資料庫，就需要考慮存儲量的問題。

4）傳輸數據量大

5）不可讀。


3. UUID的變種

1）為了解決UUID不可讀，可以使用UUID to Int64的方法。及


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

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

///  
/// Generate a new 
///  
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);
}

用上面的算法測試一下，得到如下的結果：作為比較，前面3個是使用COMB算法得出的結果，最後12個字符串是時間序（統一毫秒生成的3個UUID），過段時間如果再次生成，則12個字符串會比圖示的要大。後面3個是直接生成的GUID。

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

4. Redis生成ID
當使用資料庫來生成ID性能不夠要求的時候，我們可以嘗試使用Redis來生成ID。這主要依賴於Redis是單線程的，所以也可以用生成全局唯一的ID。可以用Redis的原子操作 INCR和INCRBY來實現。

可以使用Redis集群來獲取更高的吞吐量。假如一個集群中有5臺Redis。可以初始化每臺Redis的值分別是1,2,3,4,5，然後步長都是5。各個Redis生成的ID為：

A：1,6,11,16,21
B：2,7,12,17,22
C：3,8,13,18,23
D：4,9,14,19,24
E：5,10,15,20,25

這個，隨便負載到哪個機確定好，未來很難做修改。但是3-5臺伺服器基本能夠滿足器上，都可以獲得不同的ID。但是步長和初始值一定需要事先需要了。使用Redis集群也可以方式單點故障的問題。

另外，比較適合使用Redis來生成每天從0開始的流水號。比如訂單號=日期+當日自增長號。可以每天在Redis中生成一個Key，使用INCR進行累加。

優點：

1）不依賴於資料庫，靈活方便，且性能優於資料庫。
2）數字ID天然排序，對分頁或者需要排序的結果很有幫助。

缺點：

1）如果系統中沒有Redis，還需要引入新的組件，增加系統複雜度。
2）需要編碼和配置的工作量比較大。

5. Twitter的snowflake算法

snowflake是Twitter開源的分布式ID生成算法，結果是一個long型的ID。其核心思想是：使用41bit作為毫秒數，10bit作為機器的ID（5個bit是數據中心，5個bit的機器ID），12bit作為毫秒內的流水號（意味著每個節點在每毫秒可以產生 4096 個 ID），最後還有一個符號位，永遠是0。

具體實現的代碼可以參看https://github.com/twitter/snowflake。

C#代碼如下：

/// 
    /// From: https://github.com/twitter/snowflake
    /// An object that generates IDs.
    /// This is broken into a separate class in case
    /// we ever want to support multiple worker threads
    /// per process
    /// 
    public class IdWorker
    {
        private long workerId;
        private long datacenterId;
        private long sequence = 0L;

        private static long twepoch = 1288834974657L;

        private static long workerIdBits = 5L;
        private static long datacenterIdBits = 5L;
        private static long maxWorkerId = -1L ^ (-1L << (int)workerIdBits);
        private static long maxDatacenterId = -1L ^ (-1L << (int)datacenterIdBits);
        private static long sequenceBits = 12L;

        private long workerIdShift = sequenceBits;
        private long datacenterIdShift = sequenceBits + workerIdBits;
        private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
        private long sequenceMask = -1L ^ (-1L << (int)sequenceBits);

        private long lastTimestamp = -1L;
        private static object syncRoot = new object();

        public IdWorker(long workerId, long datacenterId)
        {

            // sanity check for workerId
            if (workerId > maxWorkerId || workerId < 0)
            {
                throw new ArgumentException(string.Format("worker Id can't be greater than %d or less than 0", maxWorkerId));
            }
            if (datacenterId > maxDatacenterId || datacenterId < 0)
            {
                throw new ArgumentException(string.Format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
            }
            this.workerId = workerId;
            this.datacenterId = datacenterId;
        }

        public long nextId()
        {
            lock (syncRoot)
            {
                long timestamp = timeGen();

                if (timestamp < lastTimestamp)
                {
                    throw new ApplicationException(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;
                }

                lastTimestamp = timestamp;

                return ((timestamp - twepoch) << (int)timestampLeftShift) | (datacenterId << (int)datacenterIdShift) | (workerId << (int)workerIdShift) | sequence;
            }
        }

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

        protected long timeGen()
        {
            return (long)(DateTime.UtcNow - new DateTime(1970, 1, 1, 0, 0, 0, DateTimeKind.Utc)).TotalMilliseconds;
        }
    }
測試代碼如下：
private static void TestIdWorker()
        {
            HashSet<long> set = new HashSet<long>();
            IdWorker idWorker1 = new IdWorker(0, 0);
            IdWorker idWorker2 = new IdWorker(1, 0);
            Thread t1 = new Thread(() => DoTestIdWoker(idWorker1, set));
            Thread t2 = new Thread(() => DoTestIdWoker(idWorker2, set));
            t1.IsBackground = true;
            t2.IsBackground = true;

            t1.Start();
            t2.Start();
            try
            {
                Thread.Sleep(30000);
                t1.Abort();
                t2.Abort();
            }
            catch (Exception e)
            {
            }

            Console.WriteLine("done");
        }

        private static void DoTestIdWoker(IdWorker idWorker, HashSet<long> set)
        {
            while (true)
            {
                long id = idWorker.nextId();
                if (!set.Add(id))
                {
                    Console.WriteLine("duplicate:" + id);
                }

                Thread.Sleep(1);
            }
        }

snowflake算法可以根據自身項目的需要進行一定的修改。比如估算未來的數據中心個數，每個數據中心的機器數以及統一毫秒可以能的並發數來調整在算法中所需要的bit數。

優點：

1）不依賴於資料庫，靈活方便，且性能優於資料庫。
2）ID按照時間在單機上是遞增的。

缺點：

1）在單機上是遞增的，但是由於涉及到分布式環境，每臺機器上的時鐘不可能完全同步，也許有時候也會出現不是全局遞增的情況。

6. 利用zookeeper生成唯一ID
zookeeper主要通過其znode數據版本來生成序列號，可以生成32位和64位的數據版本號，客戶端可以使用這個版本號來作為唯一的序列號。很少會使用zookeeper來生成唯一ID。主要是由於需要依賴zookeeper，並且是多步調用API，如果在競爭較大的情況下，需要考慮使用分布式鎖。因此，性能在高並發的分布式環境下，也不甚理想。

7. MongoDB的ObjectId
MongoDB的ObjectId和snowflake算法類似。它設計成輕量型的，不同的機器都能用全局唯一的同種方法方便地生成它。MongoDB 從一開始就設計用來作為分布式資料庫，處理多個節點是一個核心要求。使其在分片環境中要容易生成得多。

其格式如下：


前4 個字節是從標準紀元開始的時間戳，單位為秒。時間戳，與隨後的5 個字節組合起來，提供了秒級別的唯一性。由於時間戳在前，這意味著ObjectId 大致會按照插入的順序排列。這對於某些方面很有用，如將其作為索引提高效率。

這4 個字節也隱含了文檔創建的時間。絕大多數客戶端類庫都會公開一個方法從ObjectId 獲取這個信息。接下來的3 字節是所在主機的唯一標識符。通常是機器主機名的散列值。

這樣就可以確保不同主機生成不同的ObjectId，不產生衝突。為了確保在同一臺機器上並發的多個進程產生的ObjectId 是唯一的，接下來的兩字節來自產生ObjectId 的進程標識符（PID）。

前9 字節保證了同一秒鐘不同機器不同進程產生的ObjectId 是唯一的。

後3 字節就是一個自動增加的計數器，確保相同進程同一秒產生的ObjectId 也是不一樣的。同一秒鐘最多允許每個進程擁有2563（16 777 216）個不同的ObjectId。

實現的源碼可以到MongoDB官方網站下載。

你們用的是什麼方案？歡迎留言告訴我們！

相關焦點

  • 美團分布式ID生成服務LeafCode
    ，其實是可以反解出對應的數據量增長的，比如訂單id如果遞增，競對可以知道每日訂單量是多少了，而且一旦數據id有規則，就容易被窮舉，存在安全風險；可靠性高：全局唯一ID生成服務往往是很多業務架構的底層服務，需要保障較高的可靠性，如果全局唯一ID服務不可用，上層業務系統可能會癱瘓；總結下來一個支撐全局唯一ID生成的服務需要具備以下幾點： TP999儘可能要低，不能因此提高整個上層業務時延
  • 一文讀懂 Python 分布式任務隊列 celery
    分布式集群部署celery作為分布式的任務隊列框架，worker是可以執行在不同的伺服器上的。部署過程和單機上啟動是一樣。只要把項目代碼copy到其他伺服器，使用相同命令就可以了。可以思考下，這個是怎麼實現的？對了，就是通過共享Broker隊列。使用合適的隊列，如redis，單進程單線程的方式可以有效的避免同個任務被不同worker同時執行的情況。
  • 分布式系統(微服務架構)的一致性和冪等性問題相關概念解析
    而微服務架構下的分布式應用系統,其一致性問題主要在於如何使不同微服務的數據對同一業務狀態的描述保持一致,比如對於下單並支付這一業務操作而言,下單和支付要麼同時成功,要麼應該同時失敗,而不應該一個成功一個失敗,並且在這個過程中,某部分已經成功或失敗的數據是否應該對客戶端可見。在聯繫一下本地事務ACID中的一致性,我們可能會產生一定的混亂:它們講的一致性是一個東西嗎？
  • 一文總結:分布式一致性技術是如何演進的?
    阿里妹導讀：分布式一致性（Consensus）作為分布式系統的基石，一直都是計算機系統領域的熱點。
  • 分布式訓練的方案和效率對比
    前言在增大數據集的同時增大模型參數量(Scaling)是提高準確率的一個有效方案，見百度這篇文章。但這也意味著計算量和訓練時間的快速上升。為了縮減訓練時間，我們可以使用分布式/並行訓練。搭建一個大型的分布式系統是一個耗時耗力的大工程。在量級不那麼大的訓練場景下，通常多卡並行是一個簡單且高效的方案。
  • 打造雲原生大型分布式監控系統(三):Thanos 部署與實踐
    本文將使用基於 kube-thanos 提供的 yaml 示例（examples/all/manifests）來部署，原因是 prometheus-operator 與社區的 Helm Chart 方式部署多了一層封裝，屏蔽了許多細節，並且它們的實現都還不太成熟；直接使用 Kubernetes 的 yaml 資源文件部署更直觀，也更容易做自定義
  • 5分鐘學分布式系統理論,從放棄到入門
    分布式系統中，進行資料庫事務提交(commit transaction)、Leader選舉、序列號生成等都會遇到一致性問題。在還沒有明晰所要解決的問題前談解決方案都是一本正經地耍流氓。[8]分布式系統理論基礎 - 時間、時鐘和事件順序十六號…… 四月十六號。一九六零年四月十六號下午三點之前的一分鐘你和我在一起，因為你我會記住這一分鐘。從現在開始我們就是一分鐘的朋友，這是事實，你改變不了，因為已經過去了。我明天會再來。
  • 好文推薦!一文讀懂ICS工業控制系統架構
    本文摘自於《工業控制系統安全》一書，從架構透視的角度檢視現代工業控制系統的各個不同部分，發現它們是怎樣共同工作完成常規任務。經機械工業出版社華章公司授權發布。文末贈書哦。工業控制系統是一個包羅萬象的術語，用於各種自動化系統及其設備，如可編程邏輯控制器（PLC）、人機界面（HMI）、監控和數據採集（SCADA）系統，分布式控制系統（DCS）、安全儀表系統（SIS）等。可編程邏輯控制器，或稱為PLC，是幾乎所有工業控制系統的核心。這些設備通過輸入通道從傳感器獲取數據，通過輸出通道控制執行器。
  • 一文搞定 Linux 共享內存原理
    下面先來介紹一下Linux系統的共享內存的使用。共享內存使用1.獲取共享內存要使用共享內存，首先需要使用 shmget() 函數獲取共享內存，shmget() 函數的原型如下：int shmget(key_t key, size_t size, int shmflg);參數 key 一般由 ftok() 函數生成，用於標識系統的唯一IPC資源。
  • pytorch編程之分布式 RPC 框架入門
    [ob_id]) for ob_id in self.rewards]) self.running_reward = 0.05 * min_reward + (1 - 0.05) * self.running_reward # clear saved probs and rewards for ob_id in self.rewards:
  • 一文搞定:Linux 共享內存原理
    下面先來介紹一下Linux系統的共享內存的使用。共享內存使用1.獲取共享內存要使用共享內存，首先需要使用 shmget() 函數獲取共享內存，shmget() 函數的原型如下：int shmget(key_t key, size_t size, int shmflg);參數 key 一般由 ftok() 函數生成，用於標識系統的唯一IPC資源。
  • 分布式追蹤系統 -- Opentracing
    關於Metrics、Tracing和Logging      監控、鏈路追蹤及日誌作為實時監測系統運行監控狀況，在這三個領域都有對應的工具和解決方案，它們除負責各自的職責(prometheus、jaeger、ELK)在某些情況下可能會重疊。我們可以用維恩圖的形式，描繪出各個領域之間的可觀測性123
  • PHP 單點登錄實現方案
    單點登錄SSO（Single Sign On）說得簡單點就是在一個多系統共存的環境下，用戶在一處登錄後，就不用在其他系統中登錄，也就是用戶的一次登錄能得到其他所有系統的信任
  • 類型ID的生成及應用
    在一些類派生場景下,開發者希望能夠判斷類型,例如Qt的事件系統使用時,通過QEvent的type()接口獲取並識別類型,並通過static_cast轉換為對應類型:bool MyWidget::event(QEvent *event){ if (event-
  • 晨馭科技‖MCNet · 全分布式氣象災害指揮中心顯控系統解決方案
    晨馭科技為氣象災害防禦決策指揮中心打造音視頻一體化解決方案，採用業內領先的全IP淺壓縮分布式圖像處理技術，實現衛星雲圖、雷達圖、自動站監控畫面等多種信號的實時上屏顯示，以靈活的畫面布局，8K@60Hz全幀率無損畫質體驗， 　　項目背景 　　我國自入冬以來，接連遭遇多次寒潮來襲
  • EasyScheduler的架構原理及實現思路,大數據工作流調度系統
    其中 恢復被容錯的工作流 和 恢復等待線程 兩種命令類型是由調度內部控制使用，外部無法調用定時調度：系統採用 quartz 分布式調度器，並同時支持cron表達式可視化的生成依賴：系統不單單支持 DAG 簡單的前驅和後繼節點之間的依賴，同時還提供 任務依賴 節點，支持 流程間的自定義任務依賴優先級：支持流程實例和任務實例的優先級，如果流程實例和任務實例的優先級不設置
  • 一款強大的資料庫,自動生成 CRUD 接口!
    這個時候，你可以使用 分布式資料庫中間件（比如 ShardingSphere）對關係型單機資料庫進行分庫分表和讀寫分離或者直接使用 分布式資料庫。分布式資料庫分布式資料庫的基本思想是將單機資料庫上存儲的數據分配到多臺機器上去。
  • 「分布式KVM坐席管理系統」是什麼梗?
    在AV工程建設中，許多人習慣採用集中式音視頻矩陣，會議系統，多功能廳，智慧中心，拼接處理器，錄播系統，中央控制系統等組成會議室等功能區，而各功能區相對獨立的分布在大樓的各個角落。傳統的AV建設存在一系列的難題：多媒體信息共存難；多產商設備之間的配合難；多視頻格式的轉換難；遠距離的傳輸難；設計，施工效率低，使用維護難。分布式KVM坐席協作能有效的解決以上癥結。
  • 猿蛻變9——一文搞定SpringMVC的RESTFul套路
    今天我們來開啟新討論，講一講springMVC對那一種休閒風的支付——RestFul。每月底工廠君會根據後臺記錄篩選轉發文章前三位的朋友，給與獎勵，第一名100元，第二名50元，第三名30元的現金獎勵。行動力超強的你，關注公號，轉發文章，趕緊動起來吧！目前來看排名如下，胖子是我本人，不算的，大家多多努力噢。
  • 一文梳理聯邦學習推薦系統研究進展
    近些年來學術界以及工業界的研究者們已經對其進行了大量研究並提出了許多經典有效的推薦模型，比如UserCF、ItemCF、MF、FM、BPR、Item2vec、NCF、DIN等等，更多推薦模型介紹可參考[一文盡覽推薦系統模型演變史]。