百度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

ringbuffer环形数组
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()时检测达到阈值
  • 定时任务填充(如果有打开)
Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐