一、分佈式系統帶來ID生成挑戰
在複雜的系統中,往往需要對大量的數據如訂單,賬戶進行標識,以一個有意義的有序的序列號來作為全局唯一的ID;
而分佈式系統中我們對ID生成器要求又有哪些呢?
- 全局唯一性：不能出現重複的ID號，既然是唯一標識，這是最基本的要求。
- 遞增：比較低要求的條件為趨勢遞增,即保證下一個ID一定大於上一個ID,而比較苛刻的要求是連續遞增,如1,2,3等等。
- 高可用高性能：ID生成事關重大,一旦掛掉系統崩潰;高性能是指必須要在壓測下表現良好,如果達不到要求則在高併發環境下依然會導致系統癱瘓。
二、業內方案簡介
1. UUID方案
優點：
能夠保證獨立性，程序可以在不同的數據庫間遷移，效果不受影響。
保證生成的ID不僅是表獨立的，而且是庫獨立的，這點在你想切分數據庫的時候尤為重要。
缺點：
1. 性能為題：UUID太長，通常以36長度的字符串表示,對MySQL索引不利：如果作為數據庫主鍵，在InnoDB引擎下，UUID的無序性可能會引起數據位置頻繁變動，嚴重影響性能
2. UUID無業務含義：很多需要ID能標識業務含義的地方不使用
3.不滿足遞增要求
2. snowflake方案
snowflake是twitter開源的分佈式ID生成系統。 Twitter每秒有數十萬條消息的請求，每條消息都必須分配一條唯一的id，這些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型。(轉換成字符串長度為18)
snowflake生成的ID整體上按照時間自增排序，並且整個分佈式系統內不會產生ID碰撞（由datacenter和workerId作區分），並且效率較高。snowflake的缺點是:
- 強依賴時鐘,如果主機時間回撥,則會造成重複ID,會產生
- ID雖然有序,但是不連續
snowflake現在有較好的改良方案,比如美團點評開源的分佈式ID框架：leaf，通過使用ZooKeeper解決了時鐘依賴問題。
snowflake的關鍵源碼如下：
/** * Twitter_Snowflake
* SnowFlake的結構如下(每部分用-分開):
* 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
* 1位標識，由於long基本類型在Java中是帶符號的，最高位是符號位，正數是0，負數是1，所以id一般是正數，最高位是0
* 41位時間截(毫秒級)，注意，41位時間截不是存儲當前時間的時間截，而是存儲時間截的差值（當前時間截 - 開始時間截) * 得到的值），這裡的的開始時間截，一般是我們的id生成器開始使用的時間，由我們程序來指定的（如下下面程序IdWorker類的startTime屬性）。41位的時間截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69
* 10位的數據機器位，可以部署在1024個節點，包括5位datacenterId和5位workerId
* 12位序列，毫秒內的計數，12位的計數順序號支持每個節點每毫秒(同一機器，同一時間截)產生4096個ID序號
* 加起來剛好64位，為一個Long型。
* SnowFlake的優點是，整體上按照時間自增排序，並且整個分佈式系統內不會產生ID碰撞(由數據中心ID和機器ID作區分)，並且效率較高，經測試，SnowFlake每秒能夠產生26萬ID左右。 */ public class SnowflakeIdWorker { // ==============================Fields=========================================== /** 開始時間截 (2015-01-01) */ private final long twepoch = 1420041600000L; /** 機器id所佔的位數 */ private final long workerIdBits = 5L; /** 數據標識id所佔的位數 */ private final long datacenterIdBits = 5L; /** 支持的最大機器id，結果是31 (這個移位算法可以很快的計算出幾位二進制數所能表示的最大十進制數) */ private final long maxWorkerId = -1L ^ (-1L << workerIdBits); /** 支持的最大數據標識id，結果是31 */ private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); /** 序列在id中佔的位數 */ private final long sequenceBits = 12L; /** 機器ID向左移12位 */ private final long workerIdShift = sequenceBits; /** 數據標識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); /** 工作機器ID(0~31) */ private long workerId; /** 數據中心ID(0~31) */ private long datacenterId; /** 毫秒內序列(0~4095) */ private long sequence = 0L; /** 上次生成ID的時間截 */ private long lastTimestamp = -1L; //==============================Constructors===================================== /** * 構造函數 * @param workerId 工作ID (0~31) * @param datacenterId 數據中心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; } // ==============================Methods========================================== /** * 獲得下一個ID (該方法是線程安全的) * @return SnowflakeId */ public synchronized long nextId() { long timestamp = timeGen(); //如果當前時間小於上一次ID生成的時間戳，說明系統時鐘回退過這個時候應當拋出異常 if (timestamp < 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 = 0L; } //上次生成ID的時間截 lastTimestamp = timestamp; //移位並通過或運算拼到一起組成64位的ID return ((timestamp - twepoch) << timestampLeftShift) // | (datacenterId << datacenterIdShift) // | (workerId << workerIdShift) // | sequence; } /** * 阻塞到下一個毫秒，直到獲得新的時間戳 * @param lastTimestamp 上次生成ID的時間截 * @return 當前時間戳 */ protected long tilNextMillis(long lastTimestamp) { long timestamp = timeGen(); while (timestamp <= lastTimestamp) { timestamp = timeGen(); } return timestamp; } /** * 返回以毫秒為單位的當前時間 * @return 當前時間(毫秒) */ protected long timeGen() { return System.currentTimeMillis(); } //==============================Test============================================= /** 測試 */ public static void main(String[] args) throws InterruptedException { SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0); for (int i = 0; i < 100; i++) { long id = idWorker.nextId(); //System.out.println(Long.toBinaryString(id)); Thread.sleep(1); System.out.println(id); } } } 3. 基於數據庫方案
利用數據庫生成ID是最常見的方案。能夠確保ID全數據庫唯一。其優缺點如下：
優點：
- 非常簡單，利用現有數據庫系統的功能實現，成本小，有DBA專業維護。
- ID號單調自增，可以實現一些對ID有特殊要求的業務。
缺點:
- 不同數據庫語法和實現不同，數據庫遷移的時候或多數據庫版本支持的時候需要處理。
- 在單個數據庫或讀寫分離或一主多從的情況下，只有一個主庫可以生成。有單點故障的風險。
- 在性能達不到要求的情況下，比較難於擴展。
- 如果涉及多個系統需要合併或者數據遷移會比較麻煩。
- 分表分庫的時候會有麻煩。
4.其他方案簡介
通過Redis生成ID(主要通過redis的自增函數)、ZooKeeper生成ID、MongoDB的ObjectID等均可實現唯一性的要求
三、我們在實際應用中經歷的方案
1. 方案簡介
實際業務中，除了分佈式ID全局唯一之外，還有是否趨勢/連續遞增的要求。根據具體業務需求的不同，有兩種可選方案。
一是隻保證全局唯一，不保證連續遞增。二是既保證全局唯一，又保證連續遞增。
2. 基於ZooKeeper和本地緩存的方案
基於zookeeper分佈式ID實現方案有很多種,本方案只使用ZooKeeper作為分段節點協調工具。每臺服務器首先從zookeeper緩存一段,如1-1000的id,
此時zk上保存最大值1000,每次獲取的時候都會進行判斷,如果id<=1000,則更新本地的當前值,如果為1001,則會將zk上的最大值更新至2000,本地緩存
段更新為1001-2000,更新的時候使用curator的分佈式鎖來實現。
由於ID是從本機獲取，因此本方案的優點是性能非常好。缺點是如果多主機負載均衡,則會出現不連續的id,當然將遞增區段設置為1也能保證連續的id,
但是效率會受到很大影響。
閱讀更多 程序員王哥
的文章
關鍵字:
分佈式
數據庫
Twitter
