分布式系統生成唯一id常見方案

分布式系統中全局唯一id是我們經常用到的，生成全局id方法由很多，我們選擇的時候也比較糾結。每種方式都有各自的使用場景，如果我們熟悉各種方式及優缺點，使用的時候才會更方便。下面我們就一起來看一下常見的生成全局唯一id的方法

本文主要討論

常見的生成全局唯一id有哪些？
他們各有什么優缺點？

1. 使用數據庫自動增長序列實現

使用數據庫的自動增長來實現，算是常見最簡單的解決方案，數據庫內部可以確保生成id的唯一性。

優點：
1）實現簡單
2）id是有序的，對于有排序需求的比較有利

缺點：
1）依賴于數據庫數據插入，性能比較低
2）對數據庫有依賴，每種數據庫可能實現不一樣，數據庫切換時候，涉及到代碼的修改，不利于擴展

2. 使用UUID實現

也是比較常見的解決方案，uuid全球唯一。

優點：
1）代碼簡單
2）性能比較好
3）對其他無依賴，方便擴展

缺點：
1）uuid是一段很長的字符，沒有排序的，無法保證按順序遞增
2）uuid比較長，存儲在數據庫中占用的空間也比較大，不利于檢索和排序
3）生成的數據比較長，數據量大的情況下，對傳輸效率也會有影響

3. 使用redis實現

我們可以使用redis的原子操作 INCR和INCRBY來實現，redis性能也比較高，若單機存在性能瓶頸，無法滿足業務需求，可以采用集群的方式來實現。

多個集群之間增加步長來避免生成id重復的問題，如有5臺redis：
第1臺生成：1、6、11、16
第2臺生成：2、7、12、17
第3臺生成：3、8、13、18
第4臺生成：4、9、14、19
第5臺生成：5、10、15、20

redis重啟的時候，數據可能會丟失，可以在生成的id前面加上一個時間戳來做到唯一性。

優點：
1）性能比較高
2）生成的數據是有序的，對排序業務有利

缺點：
1）依賴于redis，需要系統引進redis組件，增加了系統的復雜性

4. 使用Twitter的snowflake算法實現

這個是twitter的一個全局唯一id生成器，結果是一個long型的ID。其核心思想是：使用41bit作為毫秒數，10bit作為機器的ID（5個bit是數據中心，5個bit的機器ID），12bit作為毫秒內的流水號（意味著每個節點在每毫秒可以產生 4096 個 ID），最后還有一個符號位，永遠是0。具體實現的代碼可以參看https://github.com/twitter/snowflake

直接上代碼：

package com.yjd.comm.util;/**
 * Created by pc on 2017/8/16 0016.
 */

/**
 * 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 {

    // ==============================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) {
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(1, 1);
        long startime = System.currentTimeMillis();
        for (int i = 0; i < 4000000; i++) {
            long id = idWorker.nextId();
//            System.out.println(Long.toBinaryString(id));
//            System.out.println(id);
        }
        System.out.println(System.currentTimeMillis() - startime);
    }
}

5. 使用數據庫+本地緩存實現

數據庫中存儲一個數字類型的字段cur_value，初始化為0，我們每次可以申請n個數字，過程：
1）創建表

CREATE TABLE `yjd_id_generator` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT COMMENT '編號',
  `code` varchar(64) NOT NULL DEFAULT '' COMMENT '編碼',
  `cur_value` bigint(20) NOT NULL DEFAULT '1' COMMENT '當前值',
  `description` varchar(128) NOT NULL DEFAULT '' COMMENT '說明',
  PRIMARY KEY (`id`),
  UNIQUE KEY `idx_uq_code` (`code`)
) ENGINE=InnoDB AUTO_INCREMENT=24 DEFAULT CHARSET=utf8 COMMENT='id生成器，cur_value每次遞增一定的范圍'

cur_value記錄當前已申請到的最大值。

2) 通過code查詢表yjd_id_generator中的記錄，將cur_value更新為cur_value+n，更新成功，表示(cur_value,n]范圍內的數字我們申請成功，可以使用。存在一個并發問題，需要避免多個線程同時更新的問題，我們可以通過使用cur_value作為條件進行更新，即采用樂觀鎖的方式進行更新，如果更新成功，表示申請成功，假如查詢的cur_value值為100，那么在cur_value上遞增100，此時cur_value = 200，執行如下更新操作:

update yjd_id_generator set cur_value = 200 where code = '業務編碼’ and cur_value = 100;

若上面的sql執行成功，表示更新成功，上面通過樂觀鎖保證了并發情況下只有一個請求會執行成功。如果更新失敗，表示cur_value被其他線程更新了，需要重復獲取記錄繼續執行更新操作，類似于java中的cas操作。

4) 把生成好的id放在本地內存緩存隊列中給系統使用；效率也是非常高的。

代碼如下：

public class IdGeneratorUtil {
    public interface ICode {
        String code();
    }

    private static Logger logger = Logger.getLogger(IdGeneratorUtil.class);
    private static final String SERVICE = "idGeneratorService";
    private static Long stepValue = 100L;

    /**
     * 禁止直接訪問該list的值,通過getAllDicts()來訪問
     */
    private volatile static Map<String, IdGenerator> idMap = FrameUtil.newHashMap();
    private volatile static Object idMapLock = new Object();

    public static IIdGeneratorService getService() {
        return ServiceHolder.getService(IIdGeneratorService.class, SERVICE, RpmServiceKeyEnum.RPM_PUBLIC_KEY_E.getDubboFileName(), true);
    }

    /**
     * 獲取id
     *
     * @param code
     * @return
     * @throws Exception
     */
    public static long getId0(ICode code) throws Exception {
        return getId(code.code());
    }

    /**
     * 獲取id
     *
     * @param code
     * @return
     * @throws Exception
     */
    public static long getId(String code) throws Exception {
        IdGenerator idGenerator = idMap.get(code);
        if (idGenerator == null) {
            synchronized (idMapLock) {
                idGenerator = idMap.get(code);
                if (idGenerator == null) {
                    Range range = getDbId(code);
                    idGenerator = new IdGenerator(range, new AtomicLong(range.getLeft()));
                    idMap.put(code, idGenerator);
                }
            }
        }
        long value = idGenerator.getIdValue().getAndIncrement();
        if (value > idGenerator.getRange().getRight()) {
            synchronized (idMapLock) {
                idMap.remove(code);
            }
            value = getId(code);
        }
        return value;

    }

    private static class IdGenerator {
        private Range range;
        private AtomicLong idValue;

        public IdGenerator() {
        }

        public IdGenerator(Range range, AtomicLong idValue) {
            this.range = range;
            this.idValue = idValue;
        }

        public Range getRange() {
            return range;
        }

        public void setRange(Range range) {
            this.range = range;
        }

        public AtomicLong getIdValue() {
            return idValue;
        }

        public void setIdValue(AtomicLong idValue) {
            this.idValue = idValue;
        }
    }

    private static class Range {
        private long left;
        private long right;

        private Range(Builder builder) {
            setLeft(builder.left);
            setRight(builder.right);
        }

        public static Builder newBuilder() {
            return new Builder();
        }

        public long getLeft() {
            return left;
        }

        public void setLeft(long left) {
            this.left = left;
        }

        public long getRight() {
            return right;
        }

        public void setRight(long right) {
            this.right = right;
        }

        public static final class Builder {
            private long left;
            private long right;

            private Builder() {
            }

            public Builder left(long val) {
                left = val;
                return this;
            }

            public Builder right(long val) {
                right = val;
                return this;
            }

            public Range build() {
                return new Range(this);
            }
        }
    }

    private static Range getDbId(String code) throws Exception {
        IIdGeneratorService service = getService();
        IdGeneratorModel model = service.getModelOne(FrameUtil.newHashMap("code", code), DbWREnums.WRITE);
        long left = 0, right = 0;
        if (model == null) {
            left = 1;
            right = left + stepValue - 1;
            model = new IdGeneratorModel();
            model.setCode(code);
            model.setCur_value(right);
            service.insert(model);
        } else {
            while (true) {
                Long cur_value = model.getCur_value();
                left = cur_value + 1;
                right = left + stepValue - 1;
                long where_cur_value = cur_value;
                if (service.updateByMap(FrameUtil.newHashMap("id", model.getId(), "cur_value", right, "where_cur_value", where_cur_value)) == 1) {
                    break;
                }
                model = service.getModelOne(FrameUtil.newHashMap("code", code), DbWREnums.WRITE);
            }
        }
        return Range.newBuilder().left(left).right(right).build();
    }
}

優點：
1）性能比較高
2）生成的數據是有序的，對排序業務有利

缺點：
1）依賴于數據庫

總結

本文介紹了5中方式供大家選擇，大家如果有其他方式可以分享交流。