UidGenerator是什么

UidGenerator是百度開源的一款分布式高性能的唯一ID生成器，更詳細(xì)的情況可以查看github:uid-generator，里面有更詳細(xì)的介紹文檔說明，其也是基于snowflake模型的一種ID生成器，我們再來回顧以下雪花模型。

sign(1bit)
固定1bit符號標(biāo)識，即生成的UID為正數(shù)。

delta seconds (28 bits)
當(dāng)前時(shí)間，相對于時(shí)間基點(diǎn)"2016-05-20"的增量值，單位：秒，最多可支持約8.7年

worker id (22 bits)
機(jī)器id，最多可支持約420w次機(jī)器啟動。內(nèi)置實(shí)現(xiàn)為在啟動時(shí)由數(shù)據(jù)庫分配，默認(rèn)分配策略為用后即棄，后續(xù)可提供復(fù)用策略。

sequence (13 bits)
每秒下的并發(fā)序列，13 bits可支持每秒8192個(gè)并發(fā)。

這些字段的長度可以根據(jù)具體的應(yīng)用需要進(jìn)行動態(tài)的調(diào)整，滿足總長度為64位即可
百度的worker id的生成策略和美團(tuán)的生成策略不太一樣，美團(tuán)的snowflake主要利用本地配置的port和IP來唯一確定一個(gè)workid，美團(tuán)的這種生成方式還是可以由于手工配置錯(cuò)誤造成port重復(fù)，最終產(chǎn)生重復(fù)ID的風(fēng)險(xiǎn)，百度的這種生成方式每次都是新增的，可能會一段時(shí)間后worker id用完的情況，人工配置錯(cuò)誤的可能性很小了。

DefaultUidGenerator

nextId方法主要負(fù)責(zé)ID的生成，這種實(shí)現(xiàn)方式很簡單，如果毫秒數(shù)未發(fā)生變化，在序列號加一即可，毫秒數(shù)發(fā)生變化，重置Sequence為0（Leaf文章中講過，重置為0會造成如果利用這個(gè)ID分表的時(shí)候，并發(fā)量不大的時(shí)候，sequence字段會一直為0等，會出現(xiàn)數(shù)據(jù)傾斜）

 protected synchronized long nextId() {
        long currentSecond = getCurrentSecond();

        // Clock moved backwards, refuse to generate uid
        if (currentSecond < lastSecond) {
            long refusedSeconds = lastSecond - currentSecond;
            throw new UidGenerateException("Clock moved backwards. Refusing for %d seconds", refusedSeconds);
        }

        // At the same second, increase sequence
        if (currentSecond == lastSecond) {
            sequence = (sequence + 1) & bitsAllocator.getMaxSequence();
            // Exceed the max sequence, we wait the next second to generate uid
            if (sequence == 0) {
                currentSecond = getNextSecond(lastSecond);
            }

        // At the different second, sequence restart from zero
        } else {
            sequence = 0L;
        }

        lastSecond = currentSecond;

        // Allocate bits for UID
        return bitsAllocator.allocate(currentSecond - epochSeconds, workerId, sequence);
    }

CachedUidGenerator

正如名字體現(xiàn)的那樣，這是一種緩存型的ID生成方式，當(dāng)剩余ID不足的時(shí)候，會異步的方式重新生成一批ID緩存起來，后續(xù)請求的時(shí)候直接的時(shí)候直接返回現(xiàn)成的ID即可。
我們來看一下這種方式下幾個(gè)重要的數(shù)據(jù)結(jié)構(gòu)，采用了RingBuffer的方式來緩存相關(guān)UID信息。
Tail: 指向當(dāng)前最后一個(gè)可用的UID位置
Cursor: 指向下一個(gè)獲取UID的位置，其一定是小于Tail
Tail - Cursor表示的是現(xiàn)在可用的UID數(shù)量，當(dāng)可用UID數(shù)量小于一定閾值的時(shí)候會重新添加一批新的UID在RingBuffer中。

多核處理器處理相互獨(dú)立的變量時(shí)，一旦這些變量處于同一個(gè)緩存行，不同變量的操作均會造成這一個(gè)緩存行失效，影響緩存的實(shí)際效果，造成很大的緩存失效的性能問題。下面圖中線程處理不同的兩個(gè)變量，但這兩個(gè)變量的修改都會造成整個(gè)整個(gè)緩存行的失效，導(dǎo)致無效的加載、失效，出現(xiàn)了偽共享的問題

RingBuffer中通過定義一個(gè)PaddedAtomicLong來獨(dú)占一個(gè)緩存行，代碼中的實(shí)現(xiàn)填充可能需要根據(jù)具體的執(zhí)行系統(tǒng)做一些調(diào)整，保證其獨(dú)占一個(gè)緩存行即可。
下面我們來看下如何獲取相關(guān)的UID

public long take() {
        // spin get next available cursor
        long currentCursor = cursor.get();
        long nextCursor = cursor.updateAndGet(old -> old == tail.get() ? old : old + 1);

        // check for safety consideration, it never occurs
        Assert.isTrue(nextCursor >= currentCursor, "Curosr can't move back");

        // trigger padding in an async-mode if reach the threshold
        long currentTail = tail.get();
        if (currentTail - nextCursor < paddingThreshold) {
            LOGGER.info("Reach the padding threshold:{}. tail:{}, cursor:{}, rest:{}", paddingThreshold, currentTail,
                    nextCursor, currentTail - nextCursor);
            bufferPaddingExecutor.asyncPadding();
        }

        // cursor catch the tail, means that there is no more available UID to take
        if (nextCursor == currentCursor) {
            rejectedTakeHandler.rejectTakeBuffer(this);
        }

        // 1. check next slot flag is CAN_TAKE_FLAG
        int nextCursorIndex = calSlotIndex(nextCursor);
        Assert.isTrue(flags[nextCursorIndex].get() == CAN_TAKE_FLAG, "Curosr not in can take status");

        // 2. get UID from next slot
        // 3. set next slot flag as CAN_PUT_FLAG.
        long uid = slots[nextCursorIndex];
        flags[nextCursorIndex].set(CAN_PUT_FLAG);

        // Note that: Step 2,3 can not swap. If we set flag before get value of slot, the producer may overwrite the
        // slot with a new UID, and this may cause the consumer take the UID twice after walk a round the ring
        return uid;
    }

1. 通過AtomicLong.updateAndGet來避免對整個(gè)方法進(jìn)行加鎖，獲取一個(gè)可以訪問的UID的游標(biāo)值，根據(jù)這個(gè)下標(biāo)獲取slots中相關(guān)的uid直接返回
2. 緩存中可用的uid(Tail - Cursor)小于一定閾值的時(shí)候，需要啟動另外一個(gè)線程來生成一批UID

UID 的生成

public synchronized boolean put(long uid) {
        long currentTail = tail.get();
        long currentCursor = cursor.get();

        // tail catches the cursor, means that you can't put any cause of RingBuffer is full
        long distance = currentTail - (currentCursor == START_POINT ? 0 : currentCursor);
        if (distance == bufferSize - 1) {
            rejectedPutHandler.rejectPutBuffer(this, uid);
            return false;
        }

        // 1. pre-check whether the flag is CAN_PUT_FLAG
        int nextTailIndex = calSlotIndex(currentTail + 1);
        if (flags[nextTailIndex].get() != CAN_PUT_FLAG) {
            rejectedPutHandler.rejectPutBuffer(this, uid);
            return false;
        }

        // 2. put UID in the next slot
        // 3. update next slot' flag to CAN_TAKE_FLAG
        // 4. publish tail with sequence increase by one
        slots[nextTailIndex] = uid;
        flags[nextTailIndex].set(CAN_TAKE_FLAG);
        tail.incrementAndGet();

        // The atomicity of operations above, guarantees by 'synchronized'. In another word,
        // the take operation can't consume the UID we just put, until the tail is published(tail.incrementAndGet())
        return true;
    }

1. 獲取Tail的下標(biāo)值，如果緩存區(qū)滿的話直接調(diào)用RejectedPutHandler.rejectPutBuffer方法
2. 未滿的話將UID放置在slots數(shù)組相應(yīng)的位置上，同時(shí)將Flags數(shù)組相應(yīng)的位置改為CAN_TAKE_FLAG

CachedUidGenerator通過緩存的方式預(yù)先生成一批UID列表，可以解決UID獲取時(shí)候的耗時(shí)，但這種方式也有不好點(diǎn)，一方面需要耗費(fèi)內(nèi)存來緩存這部分?jǐn)?shù)據(jù)，另外如果訪問量不大的情況下，提前生成的UID中的時(shí)間戳可能是很早之前的，DefaultUidGenerator應(yīng)該在大部分的場景中就可以滿足相關(guān)的需求了。