百度uid-generator

划重点

1、时钟回拨
2、缓存行伪共享
3、为什么slots数组不使用PaddedAtomicLong
4、workId生成策略
5、RingBuffer的填充时机

概述

UidGenerator是Java实现的, 基于[Snowflake]算法的唯一ID生成器。UidGenerator以组件形式工作在应用项目中, 支持自定义workerId位数和初始化策略, 从而适用于[docker]等虚拟化环境下实例自动重启、漂移等场景。 在实现上, UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐，避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万

Snowflake算法

Snowflake算法描述：指定机器 & 同一时刻 & 某一并发序列，是唯一的。据此可生成一个64 bits的唯一ID（long）。默认采用上图字节分配方式：

• sign(1bit):固定1bit符号标识，即生成的UID为正数。

• delta seconds (28 bits):当前时间，相对于时间基点"2016-05-20"的增量值，单位：秒，最多可支持约8.7年

• worker id (22 bits):机器id，最多可支持约420w次机器启动。内置实现为在启动时由数据库分配，默认分配策略为用后即弃，后续可提供复用策略。

• sequence (13 bits):每秒下的并发序列，13 bits可支持每秒8192个并发。

源码分析

源码结构

com
 └── baidu
     └── fsg
         └── uid
             ├── BitsAllocator.java			- Bit分配器(C)
             ├── UidGenerator.java			- UID生成的接口(I)
             ├── buffer
             │   ├── BufferPaddingExecutor.java		- 填充RingBuffer的执行器(C)
             │   ├── BufferedUidProvider.java		- RingBuffer中UID的提供者(C)
             │   ├── RejectedPutBufferHandler.java	- 拒绝Put到RingBuffer的处理器(C)
             │   ├── RejectedTakeBufferHandler.java	- 拒绝从RingBuffer中Take的处理器(C)
             │   └── RingBuffer.java			- 内含两个环形数组(C)
             ├── exception
             │   └── UidGenerateException.java		- 运行时异常
             ├── impl
             │   ├── CachedUidGenerator.java		- RingBuffer存储的UID生成器(C)
             │   └── DefaultUidGenerator.java		- 无RingBuffer的默认UID生成器(C)
             ├── utils
             │   ├── DateUtils.java
             │   ├── DockerUtils.java
             │   ├── EnumUtils.java
             │   ├── NamingThreadFactory.java
             │   ├── NetUtils.java
             │   ├── PaddedAtomicLong.java
             │   └── ValuedEnum.java
             └── worker
                 ├── DisposableWorkerIdAssigner.java	- 用完即弃的WorkerId分配器(C)
                 ├── WorkerIdAssigner.java		- WorkerId分配器(I)
                 ├── WorkerNodeType.java		- 工作节点类型(E)
                 ├── dao
                 │   └── WorkerNodeDAO.java		- MyBatis Mapper
                 └── entity
                     └── WorkerNodeEntity.java		- MyBatis Entity

DefaultUidGenerator

DefaultUidGenerator的产生id的方法与基本上就是常见的snowflake算法实现，仅有一些不同，如以秒为为单位而不是毫秒

DefaultUidGenerator的产生id的方法如下:

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) {
                // 当前秒的sequence达到最大值，自旋等到下一秒
                currentSecond = getNextSecond(lastSecond);
            }
        // At the different second, sequence restart from zero
        } else {
            sequence = 0L;
        }
        // 上一次生成ID的秒数
        lastSecond = currentSecond;
        // Allocate bits for UID
        return bitsAllocator.allocate(currentSecond - epochSeconds, workerId, sequence);
    }

CachedUidGenerator

CachedUidGenerator支持缓存生成的id。

基本实现原理

关于CachedUidGenerator，文档上是这样介绍的。

在实现上, UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐，避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。

【采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费】
因为delta seconds部分是以秒为单位的，所以1个worker 1秒内最多生成的id书为8192个（2的13次方）。

从上可知，支持的最大qps为8192，所以通过缓存id来提高吞吐量。

为什么叫借助未来时间？

因为每秒最多生成8192个id，当1秒获取id数多于8192时，RingBuffer中的id很快消耗完毕，在填充RingBuffer时，生成的id的delta seconds 部分只能使用未来的时间。

（因为使用了未来的时间来生成id，所以上面说的是，【最多】可支持约8.7年）

BitsAllocator - Bit分配器

整个UID由64bit组成，以下图为例，1bit是符号位，其余63位由deltaSeconds、workerId和sequence组成，注意sequence被放在最后，可方便直接进行求和或自增操作。

该类主要接收上述3个用于组成UID的元素，并计算出各个元素的最大值和对应的位偏移。其申请UID时的方法如下，由这3个元素进行或操作进行拼接。

public long allocate(long deltaSeconds, long workerId, long sequence) {
    return (deltaSeconds << timestampShift) | (workerId << workerIdShift) | sequence;
}

DisposableWorkerIdAssigner - Worker ID分配器

本类用于为每个工作机器分配一个唯一的ID，目前来说是用完即弃，在初始化Bean的时候会自动向MySQL中插入一条关于该服务的启动信息，待MySQL返回其自增ID之后，使用该ID作为工作机器ID并柔和到UID的生成当中。

@Transactional
public long assignWorkerId() {
    // build worker node entity
    WorkerNodeEntity workerNodeEntity = buildWorkerNode();

    // add worker node for new (ignore the same IP + PORT)
    workerNodeDAO.addWorkerNode(workerNodeEntity);
    LOGGER.info("Add worker node:" + workerNodeEntity);

    return workerNodeEntity.getId();
}

RingBuffer - 用于存储UID的双环形数组结构

先看RingBuffer的field outline，这样能大致了解到他的工作模式：

/** * Constants */
    private static final int START_POINT = -1;
    private static final long CAN_PUT_FLAG = 0L;
    private static final long CAN_TAKE_FLAG = 1L;
	// 默认扩容阈值
    public static final int DEFAULT_PADDING_PERCENT = 50;

    /** * The size of RingBuffer's slots, each slot hold a UID * <p> * buffer的大小为2^n */
    private final int bufferSize;
    /** * 因为bufferSize为2^n，indexMask为bufferSize-1，作为被余数可快速取模 */
    private final long indexMask;
    /** * 存储UID的数组 */
    private final long[] slots;
    /** * 存储flag的数组(是否可读或者可写) */
    private final PaddedAtomicLong[] flags;

    /** * Tail: last position sequence to produce */
    private final AtomicLong tail = new PaddedAtomicLong(START_POINT);

    /** * Cursor: current position sequence to consume */
    private final AtomicLong cursor = new PaddedAtomicLong(START_POINT);

    /** * Threshold for trigger padding buffer */
    private final int paddingThreshold;

    /** * Reject putbuffer handle policy * <p> * 拒绝方式为打印日志 */
    private RejectedPutBufferHandler rejectedPutHandler = this::discardPutBuffer;
    /** * Reject take buffer handle policy * <p> * 拒绝方式为抛出异常并打印日志 */
    private RejectedTakeBufferHandler rejectedTakeHandler = this::exceptionRejectedTakeBuffer;

    /** * Executor of padding buffer * <p> * 填充RingBuffer的executor */
    private BufferPaddingExecutor bufferPaddingExecutor;

RingBuffer环形数组，数组每个元素成为一个slot。RingBuffer容量，默认为Snowflake算法中sequence最大值，且为2^N。可通过boostPower配置进行扩容，以提高RingBuffer 读写吞吐量。

Tail指针、Cursor指针用于环形数组上读写slot：

• Tail指针
  表示Producer生产的最大序号(此序号从0开始，持续递增)。Tail不能超过Cursor，即生产者不能覆盖未消费的slot。当Tail已赶上curosr，此时可通过rejectedPutBufferHandler指定PutRejectPolicy

• Cursor指针
  表示Consumer消费到的最小序号(序号序列与Producer序列相同)。Cursor不能超过Tail，即不能消费未生产的slot。当Cursor已赶上tail，此时可通过rejectedTakeBufferHandler指定TakeRejectPolicy

CachedUidGenerator采用了双RingBuffer，Uid-RingBuffer用于存储Uid、Flag-RingBuffer用于存储Uid状态(是否可填充、是否可消费)

由于数组元素在内存中是连续分配的，可最大程度利用CPU cache以提升性能。但同时会带来「伪共享」FalseSharing问题，为此在Tail、Cursor指针、Flag-RingBuffer中采用了CacheLine 补齐方式。

那为什么一个使用long而另一个使用PaddedAtomicLong呢？

• 原因是slots数组选用原生类型是为了高效地读取，数组在内存中是连续分配的，当你读取第0个元素的之后，后面的若干个数组元素也会同时被加载。分析代码即可发现slots实质是属于多读少写的变量，所以使用原生类型的收益更高。而flags则是会频繁进行写操作，为了避免伪共享问题所以手工进行补齐。如果使用的是JDK8，也可以使用注解sun.misc.Contended在类或者字段上声明，在使用JVM参数-XX:-RestrictContended时会自动进行补齐。

RingBuffer.put(long uid)

put(long)方法是一个同步方法，换句话说就是串行写，保证了填充slot和移动tail是原子操作

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
        // 添加uid到slots数组
        slots[nextTailIndex] = uid;
        // 设置状态集数组状态为可拿状态
        flags[nextTailIndex].set(CAN_TAKE_FLAG);
        // 生产者指针+1
        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;
    }

RingBuffer.take()

UID的读取是一个lock free操作，使用CAS成功将tail往后移动之后即视为线程安全。

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(); ---(a)
        }

        // 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;
    }

在(a)处可以看到当达到默认填充阈值50%时，即slots被消费大于50%的时候进行异步填充，这个填充由BufferPaddingExecutor所执行的

BufferPaddingExecutor - RingBuffer元素填充器

该用于填充RingBuffer的执行者最主要的执行方法如下

public void paddingBuffer() {
        LOGGER.info("Ready to padding buffer lastSecond:{}. {}", lastSecond.get(), ringBuffer);

        // is still running
        if (!running.compareAndSet(false, true)) {
            LOGGER.info("Padding buffer is still running. {}", ringBuffer);
            return;
        }

        // fill the rest slots until to catch the cursor
        boolean isFullRingBuffer = false;
        while (!isFullRingBuffer) {
            List<Long> uidList = uidProvider.provide(lastSecond.incrementAndGet());
            for (Long uid : uidList) {
                isFullRingBuffer = !ringBuffer.put(uid);
                if (isFullRingBuffer) {
                    break;
                }
            }
        }

        // not running now 填满收工
        running.compareAndSet(true, false);
        LOGGER.info("End to padding buffer lastSecond:{}. {}", lastSecond.get(), ringBuffer);
    }

当线程池分发多条线程来执行填充任务的时候，成功抢夺运行状态的线程会真正执行对RingBuffer填充，直至全部填满，其他抢夺失败的线程将会直接返回。

• 该类还提供定时填充功能，如果有设置开关则会生效，默认不会启用周期性填充。

/** * Start executors such as schedule */
    public void start() {
        if (bufferPadSchedule != null) {
            bufferPadSchedule.scheduleWithFixedDelay(this::paddingBuffer, scheduleInterval, scheduleInterval, TimeUnit.SECONDS);
        }
    }

• 在take()方法中检测到达到填充阈值时，会进行异步填充

 /** * Padding buffer in the thread pool */
    public void asyncPadding() {
        bufferPadExecutors.submit(this::paddingBuffer);
    }

其他函数式接口

• BufferedUidProvider- UID的提供者，在本仓库中以lambda形式出现在com.baidu.fsg.uid.impl.CachedUidGenerator#nextIdsForOneSecond
• RejectedPutBufferHandler- 当RingBuffer满时拒绝继续添加的处理者，在本仓库中的表现形式为com.baidu.fsg.uid.buffer.RingBuffer#discardPutBuffer
• RejectedTakeBufferHandler- 当RingBuffer为空时拒绝获取UID的处理者，在本仓库中的表现形式为com.baidu.fsg.uid.buffer.RingBuffer#exceptionRejectedTakeBuffer

CachedUidGenerator - 使用RingBuffer的UID生成器

该类在应用中作为Spring Bean注入到各个组件中，主要作用是初始化RingBuffer和BufferPaddingExecutor。获取ID是通过委托RingBuffer的take()方法达成的，而最重要的方法为BufferedUidProvider的提供者，即lambda表达式中的nextIdsForOneSecond(long)方法,用于生成指定秒currentSecond内的全部UID，提供给BufferPaddingExecutor进行填充

/** 生产一秒内的所有ID */
    protected List<Long> nextIdsForOneSecond(long currentSecond) {
        // Initialize result list size of (max sequence + 1)
        int listSize = (int) bitsAllocator.getMaxSequence() + 1;
        List<Long> uidList = new ArrayList<>(listSize);

        // Allocate the first sequence of the second, the others can be calculated with the offset
        long firstSeqUid = bitsAllocator.allocate(currentSecond - epochSeconds, workerId, 0L);
        for (int offset = 0; offset < listSize; offset++) {
            uidList.add(firstSeqUid + offset);
        }

        return uidList;
    }

总结

1、时钟回拨解决方式

• 机器id采用用后即弃策略，服务每次重启生成新的机器id
• 抛出异常

2、缓存行伪共享
在Tail、Cursor指针、Flag-RingBuffer中采用了CacheLine 补齐方式

3、为什么slots数组不使用PaddedAtomicLong
slots数组选用原生类型是为了高效地读取，数组在内存中是连续分配的，当你读取第0个元素的之后，后面的若干个数组元素也会同时被加载。分析代码即可发现slots实质是属于多读少写的变量，所以使用原生类型的收益更高。而flags则是会频繁进行写操作，为了避免伪共享问题所以手工进行补齐

4、RingBuffer的填充时机

• CachedUidGenerator时对RIngBuffer初始化
• RIngBuffer#take()时检测达到阈值
• 定时任务填充（如果有打开）