分布式id生成策略嘱吗，我和面試官扯了一個半小時

來自公眾號：非科班的科班
作者：黎杜

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

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

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

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

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

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

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

數(shù)據(jù)庫自增ID透且。
數(shù)據(jù)庫水平拆分，設(shè)置初始值和相同的自增步長豁鲤。
批量申請自增ID秽誊。
UUID生成。
Redis的方式琳骡。
雪花算法锅论。
百度UidGenerator算法
美團(tuán)Leaf算法

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

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

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

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

我：但是使用數(shù)據(jù)庫的自增ID驴剔，雖然簡單，會帶來ID重復(fù)的問題粥庄，并且單機(jī)版的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ù)的情況。

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

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

image

我：我這里假設(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破托。

面試官：若是面對再次擴(kuò)容的情況呢肪跋？

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

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

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

面試官：恩額诫龙。

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

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

image

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

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

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

我：第四種方式是使用「UUID生成」的方式生成分布式ID，UUID的核心思想是使用「機(jī)器的網(wǎng)卡白胀、當(dāng)?shù)貢r間椭赋、一個隨機(jī)數(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)系连茧，這個只是作為一個擴(kuò)展核蘸。

我：這個我只知道可以通過「當(dāng)前的時間戳及機(jī)器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宕機(jī)就采用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)行解釋钟沛。

image

我：第一位作為標(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位的機(jī)器標(biāo)識ID（workerId）」模燥，可以最多標(biāo)識1024個節(jié)點（1<<10=1024）咖祭。

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

我：雪花算法使用數(shù)據(jù)中心ID和機(jī)器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;

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

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

    /** 最大的機(jī)器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;

    /** 機(jī)器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);

    /** 工作機(jī)器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) // 計算機(jī)器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)上的資料說美團(tuán)Leaf算法需要依賴于數(shù)據(jù)庫匕积，ZK，并且也能保證去全局ID的唯一性榜跌，單項遞增。

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

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

得意洋洋中......

【文章參考】

[1] https://blog.csdn.net/chengbinbbs/article/details/80437334[2] https://blog.csdn.net/smilefyx/article/details/73511243[3] https://blog.csdn.net/heroguo007/article/details/78490278[4] https://www.cnblogs.com/relucent/p/4955340.html

分布式id生成策略寿冕，我和面試官扯了一個半小時

分布式id生成策略，我和面試官扯了一個半小時