面試官：小伙子，你還記得我嗎？我是上次面試你的那個面試官。

我心想：我去，怎么會不記得，我又不是青年癡呆，上次害我畫了那么多圖，還使勁敲了一個多鐘的電腦，滿腦子都是你的陰影。

我：記得記得，您好，很高興能通過二面，能夠繼續(xù)和您交流技術(shù)問題。

我違背良心說這話真的好嗎，姑且就那么一次吧，面?zhèn)€試都那么難？

面試官又快速的掃了一下的簡歷，可能上次看過一次，都快過了一個多星期了，估計他都都忘了我的簡歷了吧。

面試官：我看你簡歷上面寫著深入了解分布式，并且也做過分布式項目，挺好的，那你知道分布式項目中生成分布式ID的方法有哪些嗎？

我：這個我知道，生成分布式Id的方法主要有以下幾種：

1. 數(shù)據(jù)庫自增ID。
2. 數(shù)據(jù)庫水平拆分，設(shè)置初始值和相同的自增步長。
3. 批量申請自增ID。
4. UUID生成。
5. Redis的方式。
6. 雪花算法。
7. 百度UidGenerator算法
8. 美團Leaf算法

面試官：哦，不錯能說出那么多，你能說一說對于上面的每一種方式的分析和理解嗎？

我心想：我去，這下可糗大了，那么多，我只是大概知道主要的，怎么可能每一種都去了解和深入，一下子說了那么多不是給自己挖坑嗎？

哎，沒辦法出來混，總是要還的，只能說自己知道的吧？不知道的大概粗糙的略過。

我：嗯嗯，好的。數(shù)據(jù)庫的自增，很容易理解，開發(fā)過的人員都知道，在創(chuàng)建表的時候，指定主鍵auto_increment（自增）便可以實現(xiàn)。

我：但是使用數(shù)據(jù)庫的自增ID，雖然簡單，會帶來ID重復(fù)的問題，并且單機版的ID自增，并且每次生成一個ID都會訪問數(shù)據(jù)庫一次，DB的壓力也很大，并沒有什么并發(fā)性能可言。

面試官：恩額。

我看看面試官正聽著有味，時不時摸摸他稀少的發(fā)量額頭，深邃的目光透露出他的沉穩(wěn)，這可能就是一個成熟架構(gòu)師的魅力吧，讓多少碼渣苦讀《Java編程思想》《Java核心技術(shù)》《Effectice java》《Java并發(fā)編程實戰(zhàn)》《代碼整潔之道》《重構(gòu): 改善既有代碼的設(shè)計》......，都無法達(dá)到的境界，我乘熱打鐵，接著下面的回答。

我：針對上面的數(shù)據(jù)庫自增ID出現(xiàn)的問題：ID重復(fù)、性能不好。就出現(xiàn)了集群版的生成分布式ID方案。「數(shù)據(jù)庫水平拆分，設(shè)置初始值和相同的自增步長」和「批量申請自增ID」。

我：「數(shù)據(jù)庫水平拆分，設(shè)置初始值和相同的自增步長」是指在DB集群的環(huán)境下，將數(shù)據(jù)庫進(jìn)行水平劃分，然后每個數(shù)據(jù)庫設(shè)置「不同的初始值」和「相同的步長」，這樣就能避免ID重復(fù)的情況。

面試官：小伙子，不好意思打斷一下，你可以畫個圖嗎，這個我有點沒明白你講的意思？

我能有什么辦法啊，完全沒辦法，只能從褲兜里拿出筆和紙，快速的畫了一張圖。

我：我這里假設(shè)有三個數(shù)據(jù)庫，為每一個數(shù)據(jù)庫設(shè)置初始值，設(shè)置初始值可以通過下面的sql進(jìn)行設(shè)置：

set @@auto_increment_offset = 1;     // 設(shè)置初始值
set @@auto_increment_increment = 2;  // 設(shè)置步長

我：三個數(shù)據(jù)的初始值分別設(shè)置為1、2、3，一般步長設(shè)置為數(shù)據(jù)庫的數(shù)據(jù)，這里數(shù)據(jù)庫數(shù)量為3，所以步長也設(shè)置為3。

面試官：若是面對再次擴容的情況呢？

我：恩額，擴容的情況是這種方法的一個缺點，上面我說的步長一般設(shè)置為數(shù)據(jù)庫的數(shù)量，這是在確保后期不會擴容的情況下，若是確定后期會有擴容情況，在前期設(shè)計的的時候可以將步長設(shè)置長一點，「預(yù)留一些初始值給后續(xù)擴容使用」。

我：總之，這種方案還是優(yōu)缺點的，但是也有自己的優(yōu)點，缺點就是：「后期可能會面對無ID初始值可分的窘境，數(shù)據(jù)庫總歸是數(shù)據(jù)庫，抗高并發(fā)也是有限的」。

我：它的優(yōu)點就是算是解決了「DB單點的問題」。

面試官：恩額。

我：「批量申請自增ID」的解決方案可以解決無ID可分的問題，它的原理就是一次性給對應(yīng)的數(shù)據(jù)庫上分配一批的id值進(jìn)行消費，使用完了，再回來申請。

這次我很自覺的從褲兜里拿出筆和紙，畫出了下面的這張圖，歷史總是那么驚人的相似。

我：在設(shè)計的初始階段可以設(shè)計一個有初始值字段，并有步長字段的表，當(dāng)每次要申請批量ID的時候，就可以去該表中申請，每次申請后「初始值=上一次的初始值+步長」。

我：這樣就能保持初始值是每一個申請的ID的最大值，避免了ID的重復(fù)，并且每次都會有ID使用，一次就會生成一批的id來使用，這樣訪問數(shù)據(jù)庫的次數(shù)大大減少。

我：但是這一種方案依舊有自己的缺點，依然不能抗真正意義上的高并發(fā)。

我：第四種方式是使用「UUID生成」的方式生成分布式ID，UUID的核心思想是使用「機器的網(wǎng)卡、當(dāng)?shù)貢r間、一個隨機數(shù)」來生成UUID。

我：使用UUID的方式只需要調(diào)用UUID.randomUUID().toString()就可以生成，這種方式方便簡單，本地生成，不會消耗網(wǎng)絡(luò)。

我：當(dāng)時簡單的東西，出現(xiàn)的問題就會越多，不利于存儲，16字節(jié)128位，通常是以36位長度的字符串表示，很多的場景都不適合。

我：并且UUID生成的無序的字符串，查詢效率低下，沒有實際的業(yè)務(wù)含義，不具備自增特性，所以都不會使用UUID作為分布式ID來使用。

面試官：恩額，那你知道生成UUID的方式有幾種嗎？不知道沒關(guān)系，這個只是作為一個擴展。

我：這個我只知道可以通過「當(dāng)前的時間戳及機器mac地址」來生成，可以確保生成的UUID全球唯一，其它的沒有了解過。

面試官：嗯嗯，沒關(guān)系的。

我：為了解決上面純關(guān)系型數(shù)據(jù)庫生成分布式ID無法抗高并發(fā)的問題，可以使用Redis的方式來生成分布式ID。

我：Redis本身有incr和increby 這樣自增的命令，保證原子性，生成的ID也是有序的。

我：Redis基于內(nèi)存操作，性能高效，不依賴于數(shù)據(jù)庫，數(shù)據(jù)天然有序，利于分頁和排序。

我：但是這個方案也會有自己的缺點，因為增加了中間件，需要自己編碼實現(xiàn)工作量增大，增加復(fù)雜度。

我：使用Redis的方式還要考慮持久化，Redis的持久化有兩種「RDB和AOF」，「RDB是以快照的形式進(jìn)行持久化，會丟失上一次快照至此時間的數(shù)據(jù)」。

我：「AOF可以設(shè)置一秒持久化一次，丟失的數(shù)據(jù)是秒內(nèi)的」，也會存在可能上一次自增后的秒內(nèi)的ID沒有持久化的問題。

我：但是這種方法相對于上面的關(guān)系型數(shù)據(jù)庫生成分布式ID的方法而言，已經(jīng)優(yōu)越了許多。

我：若是數(shù)據(jù)量比較大的話，重啟Redis的時間也會比較長，可以采用Redis的集群方式。

面試官：你能手寫一下Redis的生成分布式ID的工具類代碼嗎？

我奔潰了，我最怕手寫了，因為工具類這種東西，基本就是項目開始的時候?qū)懸淮?，后面對后市重?fù)使用，記不住，還要手寫，這也太難為我怕虎了吧。

我：手寫應(yīng)該不行，因為有些API記不住，工具類基本就是項目開始的時候?qū)懸恍罄m(xù)都沒有去看過了，沒有專門去記它。

我：我可以使用您的電腦嗎？使用電腦應(yīng)該可以敲出這些工具類。

面試官：可以的，這邊電腦給你，你在這個測試項目下吧。

我：好的，謝謝。

時間流逝中........

大概敲了幾分鐘，廢了九牛二虎之力，終于敲出來了，有好多API記不住，只能慢慢的找了，寫了主要兩種方式來生成分布式ID。

第一種是使用RedisAtomicLong 原子類使用CAS操作來生成ID。

@Service
public class RedisSequenceFactory {
    @Autowired
    RedisTemplate<String, String> redisTemplate;

    public void setSeq(String key, int value, Date expireTime) {
        RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
        counter.set(value);
        counter.expireAt(expireTime);
    }

    public void setSeq(String key, int value, long timeout, TimeUnit unit) {
        RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
        counter.set(value);
        counter.expire(timeout, unit);
    }

    public long generate(String key) {
        RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
        return counter.incrementAndGet();
    }

    public long incr(String key, Date expireTime) {
        RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
        counter.expireAt(expireTime);
        return counter.incrementAndGet();
    }

    public long incr(String key, int increment) {
        RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
        return counter.addAndGet(increment);
    }

    public long incr(String key, int increment, Date expireTime) {
        RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
        counter.expireAt(expireTime);
        return counter.addAndGet(increment);
    }
}

第二種是使用redisTemplate.opsForHash()和結(jié)合UUID的方式來生成生成ID。

public Long getSeq(String key,String hashKey,Long delta) throws BusinessException{
        try {
            if (null == delta) {
                delta=1L;
            }
            return redisTemplate.opsForHash().increment(key, hashKey, delta);
        } catch (Exception e) {  // 若是redis宕機就采用uuid的方式
            int first = new Random(10).nextInt(8) + 1;
            int randNo=UUID.randomUUID().toString().hashCode();
            if (randNo < 0) {
                randNo=-randNo;
            }
            return Long.valueOf(first + String.format("%16d", randNo));
        }
    }

我把電腦移回給面試官，他很快的掃了一下我的代碼，說了一句。

面試官：小伙子，不寫注釋哦，這個習(xí)慣不好哦。

我：哦哦，謝謝提醒，不好意思，下次我會注意的。

我：第六種方式是「雪花算法」，也是現(xiàn)在市面上比較流行的生成分布式ID的方法。

說著說著，我知道畫圖又是必不可少的了，于是在桌子上又畫了起來，面試官好奇的看看我，知道了我在干啥，又耐心的等了等。

我：他是采用64bit作為id生成類型，并且將64bit劃分為，如下圖的幾段。

我順手把我畫的圖遞給他看了看，接著對著這個圖進(jìn)行解釋。

我：第一位作為標(biāo)識位，因為Java中l(wèi)ong類型的時代符號的，因為ID位正數(shù)，所以第一位位0。

我：接著的41bit是時間戳，毫秒級位單位，注意這里的時間戳并不是指當(dāng)前時間的時間戳，而是值之間差（「當(dāng)前時間-開始時間」）。

我：這里的開始時間一般是指ID生成器的開始時間，是由我們程序自己指定的。

我：接著后面的10bit：包括5位的「數(shù)據(jù)中心標(biāo)識ID（datacenterId）和5位的機器標(biāo)識ID（workerId）」，可以最多標(biāo)識1024個節(jié)點（1<<10=1024）。

我：最后12位是序列號，12位的計數(shù)順序支持每個節(jié)點每毫秒差生4096序列號（1<<12=4096）。

我：雪花算法使用數(shù)據(jù)中心ID和機器ID作為標(biāo)識，不會產(chǎn)生ID的重復(fù)，并且是在本地生成，不會消耗網(wǎng)絡(luò)，效率高，有數(shù)據(jù)顯示，每秒能生成26萬個ID。

我：但是雪花算法也是有自己的缺點，因為雪花算法的計算依賴于時間，若是系統(tǒng)時間回?fù)埽蜁a(chǎn)生重復(fù)ID的情況。

面試官：那對于時間回?fù)墚a(chǎn)生重復(fù)ID的情況，你有什么比較好的解決方案嗎？

我：在雪花算法的實現(xiàn)中，若是其前置的時間等于當(dāng)前的時間，就拋出異常，也可以關(guān)閉掉時間回?fù)堋?/p>

我：對于回?fù)軙r間比較短的，可以等待回?fù)軙r間過后再生成ID。

面試官：你可以幫我敲一個雪花算法嗎？我這鍵盤給你。

我：。。。

我：好的。

時間流逝中......

過了幾分鐘時間，也總算是把雪花算法給敲出來了，真正要老命，面?zhèn)€試怎么就那么難呢？

/**
 * 雪花算法
 * @author：黎杜
 */
public class SnowflakeIdWorker {

    /** 開始時間截 */
    private final long twepoch = 1530051700000L;

    /** 機器id的位數(shù) */
    private final long workerIdBits = 5L;

    /** 數(shù)據(jù)標(biāo)識id的位數(shù) */
    private final long datacenterIdBits = 5L;

    /** 最大的機器id，結(jié)果是31 */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /** 最大的數(shù)據(jù)標(biāo)識id，結(jié)果是31 */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    /** 序列的位數(shù) */
    private final long sequenceBits = 12L;

    /** 機器ID向左移12位 */
    private final long workerIdShift = sequenceBits;

    /** 數(shù)據(jù)標(biāo)識id向左移17位 */
    private final long datacenterIdShift = sequenceBits + workerIdBits;

    /** 時間截向左移22位*/
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    /** 生成序列的掩碼 */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /** 工作機器ID(0~31) */
    private long workerId;

    /** 數(shù)據(jù)中心ID(0~31) */
    private long datacenterId;

    /** 毫秒內(nèi)序列(0~4095) */
    private long sequence = 0L;

    /** 上次生成ID的時間截 */
    private long lastTimestamp = -1L;

    /**
     * 構(gòu)造函數(shù)
     * @param workerId 工作ID (0~31)
     * @param datacenterId 數(shù)據(jù)中心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;
    }

    /**
     * 獲得下一個ID (該方法是線程安全的)
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = getCurrentTime();

        //如果當(dāng)前時間小于上一次生成的時間戳，說明系統(tǒng)時鐘回退過就拋出異常
        if (timestamp < lastTimestamp) {
            throw new BusinessionException("回?fù)艿臅r間為："+lastTimestamp - timestamp);
        }

        //如果是同一時間生成的，則進(jìn)行毫秒內(nèi)序列
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            //毫秒內(nèi)序列溢出
            if (sequence == 0) {
                //獲得新的時間戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {  //時間戳改變，毫秒內(nèi)序列重置
            sequence = 0L;
        }

        //上次生成ID的時間截
        lastTimestamp = timestamp;

        //移位并通過或運算拼到一起組成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) // 計算時間戳
                | (datacenterId << datacenterIdShift) // 計算數(shù)據(jù)中心
                | (workerId << workerIdShift) // 計算機器ID
                | sequence; // 序列號
    }

    /**
     *獲得新的時間戳
     * @param lastTimestamp 上次生成ID的時間截
     * @return 當(dāng)前時間戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = getCurrentTime();
        // 若是當(dāng)前時間等于上一次的1時間就一直阻塞，知道獲取到最新的時間（回?fù)芎蟮臅r間）
        while (timestamp <= lastTimestamp) {
            timestamp = getCurrentTime();
        }
        return timestamp;
    }

    /**
     * 獲取當(dāng)前時間
     * @return 當(dāng)前時間(毫秒)
     */
    protected long getCurrentTime() {
        return System.currentTimeMillis();
    }

為了給面試官留下個好印象，這下也寫上了注解，免得他又說我，敲完我又把電腦移回給他，他快速的看了看，點了點頭，嘴角露出一絲絲的笑意。

面試官：嗯，你的底子還算比價扎實，面試之前早有準(zhǔn)備吧，看了很多的面試資料。

我心想怎么是面試之前準(zhǔn)備呢？我是一直在準(zhǔn)備，從工作到現(xiàn)在都在總結(jié)自己的知識點，形成自己的知識體系，為了迎合他，也只能說是。

我：嗯嗯，是的，準(zhǔn)備了很久，算是比較充分。

面試官：嗯，最后的兩種算法，你還深入了解嗎？

我：最后兩種確實沒有深入了解，之前有看網(wǎng)上的資料說美團Leaf算法需要依賴于數(shù)據(jù)庫，ZK，并且也能保證去全局ID的唯一性，單項遞增。

我：而百度UidGenerator算法是基于雪花算法進(jìn)行實現(xiàn)的，也是需要借助于數(shù)據(jù)庫，與雪花算法不同的是，「UidGenerator支持自定義時間戳、主句中心ID和機器ID、序列號的位數(shù)」。

面試官：嗯嗯，好的，小伙子今天的面試就到這里，下次我們再見吧。

得意洋洋中......

【文章參考】

特別推薦一個分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒關(guān)注的小伙伴，可以長按關(guān)注一下：

長按訂閱更多精彩▼
如有收獲，點個在看，誠摯感謝