百度雪花算法uid-generator解析

2024-10-03 本文已影响0人小波同学

概述

UidGenerator是一款基于Snowflake算法的分布式高性能唯一ID生成器，由百度开源。它使用Java实现，支持自定义workerId位数和初始化策略，适用于虚拟化环境下实例自动重启、漂移等场景。UidGenerator通过借用未来时间来解决sequence的并发限制，采用RingBuffer缓存生成的UID，实现无锁并行生产消费，避免了硬件级“伪共享”问题，单机QPS可达600万。

UidGenerator的主要特点包括：

高性能：UidGenerator支持高并发环境，单个实例的QPS能超过600万，适用于分布式系统中的唯一ID生成需求。
自定义配置：它支持自定义workerId位数和初始化策略，适应不同的部署环境和需求。
解决时钟回调问题：通过借用未来时间解决sequence的并发限制，确保在高并发场景下的稳定性和准确性。
缓存机制：采用RingBuffer缓存已生成的UID，无锁进行ID的生产与消费，提高了生成效率并避免了硬件级“伪共享”问题。
多线程适用：设计上考虑了多线程环境，不会有单线程瓶颈，适用于高并发场景。
灵活的ID生成器：提供DefaultUidGenerator和CachedUidGenerator两种实现方式，根据需求选择适合的生成器以提高性能或缓存生成的ID。

一、雪花算法的原理

雪花算法是 64 位的二进制，一共包含了四部分：

1bit-符号位

1位标识：最高位是符号位，正数是0，负数是1。由于 id 一般是正数，所以第一位都是0。

41bit-时间戳

接下来41位存储毫秒级时间戳，41位可以表示 2^41-1 毫秒。
转化成年则是：(2^41-1)/(1000606024356)=69 年。这个时间戳大概可以使用 69年不重复。

10bit-机器位

10位的数据机器位，包括 5 位 datacenterId 和 5 位 workerId，最多可以部署 2^10=1024 台机器。
这里的 5 位可以表示的最大整数时 2^5-1=31，即可以用 0、1、2、3、…31 这 32 个数字，来表示不同的 datacenterId 或 workerId

12bit-序列号

用来记录同毫秒内产生的不同ID，12位的计数顺序支持每个节点每毫秒（同一机器，同一时间戳）产生 4096 个ID序号。

二、UID-Generator 的实现

UID-Generator 有两种实现，一种是基于传统雪花算法实现（DefaultUidGenerator），另一种是百度基于雪环算法做的优化版本（CachedUidGenerator）。

2.1 DefaultUidGenerator

DefaultUidGenerator 依照雪花算法实现，它采用抛异常的方式来处理雪花算法的“时间回拨”问题。

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

    // 时间回拨 -> 抛异常
    if (currentSecond < lastSecond) {
        long refusedSeconds = lastSecond - currentSecond;
        throw new UidGenerateException("Clock moved backwards. Refusing for %d seconds", refusedSeconds);
    }

    // 在同一秒内，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);
        }
    // 不在同一秒：重置 sequence
    } else {
        sequence = 0L;
    }

    lastSecond = currentSecond;

    // 分配 Id
    return bitsAllocator.allocate(currentSecond - epochSeconds, workerId, sequence);
}

2.2 CachedUidGenerator

根据上面的实现，我们知道 sequence 决定了 UID-Generator 的并发能力，13 bits 的 sequence 可支持 8192/s 的并发，现实中很有可能不够用，进而诞生了 CachedUidGenerator。
CachedUidGenerator 使用 RingBuffer 缓存生成的id。RingBuffer是个环形数组，默认大小为 8192 个（可以通过boostPower参数设置大小）。

RingBuffer 的运行原理：

RingBuffer环形数组，数组每个元素成为一个 slot。
Tail 指针、Cursor 指针用于环形数组上读写 slot：
Tail 指针
表示 Producer 生产的最大序号(此序号从 0 开始，持续递增)。Tail 不能超过 Cursor，即生产者不能覆盖未消费的 slot。当 Tail 已赶上 curosr，此时可通过 rejectedPutBufferHandler 指定 PutRejectPolicy。
Cursor 指针
表示 Consumer 消费到的最小序号(序号序列与 Producer 序列相同)。Cursor 不能超过 Tail，即不能消费未生产的 slot。当 Cursor 已赶上 tail，此时可通过 rejectedTakeBufferHandler 指定 TakeRejectPolicy。

RingBuffer 填充触发机制:

程序启动时，将 RingBuffer 填充满。
在调用 getUID() 获取 id 时，检测到 RingBuffer 中的剩余 id 个数小于总个数的 50%，将 RingBuffer 填充满。
定时填充（可配置是否使用以及定时任务的周期）。

为什么 CachedUidGenerator 性能强？

根据上面的研究我们得知：

即使在同一秒内，只要触发填充条件，RingBuffer 就会立即填充。如果在 1s 内多次填充 RingBuffer，代码会自动增加 delta seconds，就像“借用”了未来的时间一样。
得益于此 UID-Generator 也突破了 8192 QPS，可以拿到 600w+ QPS 的好成绩。

三、源码分析

3.1 源码结构

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

3.2 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);
    }

3.3 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()时检测达到阈值
- 定时任务填充（如果有打开）

百度 UID-Generator 性能强劲，尤其是 CachedUidGenerator 实现了 Id 的缓冲区。
此外，对于分布式集群部署，UID-Generator 依赖 Mysql 的自增 Id 作为 WorkerId。
最后针对雪花算法的时间回拨问题，DefaultUidGenerator 采取了最简单的抛异常来解决，而 CachedUidGenerator 则是利用其“借用未来时间”特性巧妙解决了时间回拨问题。
总体来说，如果想用雪花算法作为分布式唯一 Id 生成器，那么百度 UID-Generator 是一个不错的选择。

参考：
https://segmentfault.com/a/1190000042792224

https://blog.csdn.net/m0_37626564/article/details/121263753

百度雪花算法uid-generator解析

概述

UidGenerator的主要特点包括：

一、雪花算法的原理

雪花算法是 64 位的二进制，一共包含了四部分：

二、UID-Generator 的实现

2.1 DefaultUidGenerator

2.2 CachedUidGenerator

RingBuffer 的运行原理：

RingBuffer 填充触发机制:

为什么 CachedUidGenerator 性能强？

三、源码分析

3.1 源码结构

3.2 DefaultUidGenerator

3.3 CachedUidGenerator

基本实现原理

为什么叫借助未来时间？

BitsAllocator - Bit分配器

DisposableWorkerIdAssigner - Worker ID分配器

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

RingBuffer.put(long uid)

RingBuffer.take()

BufferPaddingExecutor - RingBuffer元素填充器

其他函数式接口

CachedUidGenerator - 使用RingBuffer的UID生成器

总结

猜你喜欢

热点阅读

百度雪花算法uid-generator解析

概述

UidGenerator的主要特点包括：

一、雪花算法的原理

雪花算法是 64 位 的二进制，一共包含了四部分：

二、UID-Generator 的实现

2.1 DefaultUidGenerator

2.2 CachedUidGenerator

RingBuffer 的运行原理：

RingBuffer 填充触发机制:

为什么 CachedUidGenerator 性能强？

三、源码分析

3.1 源码结构

3.2 DefaultUidGenerator

3.3 CachedUidGenerator

基本实现原理

为什么叫借助未来时间？

BitsAllocator - Bit分配器

DisposableWorkerIdAssigner - Worker ID分配器

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

RingBuffer.put(long uid)

RingBuffer.take()

BufferPaddingExecutor - RingBuffer元素填充器

其他函数式接口

CachedUidGenerator - 使用RingBuffer的UID生成器

总结

猜你喜欢

热点阅读

雪花算法是 64 位的二进制，一共包含了四部分：