分布式--雪花算法改进版--百度的UidGenerator

系统管理员 2023-10-01 17:35 35阅读 0赞

原文网址：[分布式--雪花算法改进版--百度的UidGenerator\_IT利刃出鞘的博客-CSDN博客][--_--_UidGenerator_IT_-CSDN]

## **简介** ##

**说明**

百度的UidGenerator用来生成全局的唯一ID，是雪花算法的改进版。

**官网**

github：[https://github.com/baidu/uid-generator][https_github.com_baidu_uid-generator]

## **原理** ##

百度开源的 UidGenerator 是基于Java语言实现的唯一ID生成器，是**在雪花算法 snowflake 的基础上做了一些改进（解决了时钟回拨问题）**。

**工作形式**

UidGenerator以组件形式工作在应用项目中, 支持自定义workerId位数和初始化策略，适用于docker等虚拟化环境下实例自动重启、漂移等场景。

**实现方法**

在实现上，UidGenerator 提供了两种生成唯一ID方式，分别是 DefaultUidGenerator 和 CachedUidGenerator，官方建议如果有性能考虑的话使用 CachedUidGenerator 方式实现。

**命名空间**

UidGenerator 依然是以划分命名空间的方式将 64-bit位分割成多个部分，默认划分方式有别于雪花算法：它默认是由 1-28-22-13 的格式进行划分，可调整各个字段占用的位数。

![20200410141930413.png][]

*  第1位：标志位
    
     *  仍然占用1bit，其值始终是0：即生成的UID为正数
 *  第2位开始的28bit：时间戳（当前时间，相对于epoch时间的增量值）
    
     *  可表示2^28个数，**不再是以毫秒而是以秒为单位**，可用（1L<<28）/ (360024365) ≈ 8.51 年（最多可用8.7年，后边讲解）。
     *  epoch时间：指集成UidGenerator生成分布式ID服务第一次上线的时间，可配置，**默认的epoch时间是2016-09-20**，不配置的话，会浪费好几年的可用时间。
 *  第29位开始的22bit：中间的 workId （数据中心+工作机器，可以其他组成方式）
    
     *  可表示 2^22 = 4194304个工作ID（最多可支持约420w次机器启动）。
     *  内置实现：在启动时由数据库分配；默认分配策略：用后即弃；后续可提供复用策略。
 *  最后的13-bit位：并发序列（自增）
    
     *  表示**每秒的并发数量**，默认为2^13 = 8192个并发（即：**默认qps为8192**）。

## DefaultUidGenerator ##

**delta seconds**

这个值是指当前时间与epoch时间的时间差，且单位为秒。epoch时间就是指集成UidGenerator生成分布式ID服务第一次上线的时间，可配置，也一定要根据你的上线时间进行配置，因为默认的epoch时间可是2016-09-20，不配置的话，会浪费好几年的可用时间。

**workerId**

UidGenerator是如何给worker id赋值的？搭建UidGenerator的话，**需要创建一个表**：

DROP TABLE IF EXISTS WORKER_NODE;
    CREATE TABLE WORKER_NODE(
      ID BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY ,
      HOST_NAME VARCHAR(64) NOT NULL COMMENT 'host name',
      PORT VARCHAR(64) NOT NULL COMMENT 'port',
      TYPE INT NOT NULL COMMENT 'node type: ACTUAL or CONTAINER',
      LAUNCH_DATE DATE NOT NULL COMMENT 'launch date',
      MODIFIED DATETIME NOT NULL COMMENT 'modified time',
      CREATED DATEIMTE NOT NULL COMMENT 'created time'
    )COMMENT='DB WorkerID Assigner for UID Generator',ENGINE = INNODB;

UidGenerator会在集成用它生成分布式ID的实例启动的时候，往这个表中插入一行数据，得到的id值就是准备赋给workerId的值。由于workerId默认22位，那么，集成UidGenerator生成分布式ID的所有实例重启次数是不允许超过4194303次（即2^22-1），否则会抛出异常。

生成workerId的核心代码来自DisposableWorkerIdAssigner.java中，当然，你也可以实现WorkerIdAssigner.java接口，自定义生成workerId。

**sequence**

核心代码如下，几个实现的关键点：

*  synchronized保证线程安全；
 *  如果时间有任何的回拨，那么直接抛出异常；
 *  如果当前时间和上一次是同一秒时间，那么sequence自增。如果同一秒内自增值超过2^13-1，那么就会自旋等待下一秒（getNextSecond）；
 *  如果是新的一秒，那么sequence重新从0开始；

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);
        }
        if (currentSecond == lastSecond) {
            sequence = (sequence + 1) & bitsAllocator.getMaxSequence();
            if (sequence == 0) {
                currentSecond = getNextSecond(lastSecond);
            }
        } else {
            sequence = 0L;
        }
        lastSecond = currentSecond;
        return bitsAllocator.allocate(currentSecond - epochSeconds, workerId, sequence);
    }

## CachedUidGenerator ##

**简介**

官方建议的性能较高的 CachedUidGenerator 生成方式，是使用 RingBuffer 缓存生成的id。数组每个元素成为一个slot。RingBuffer容量，默认为Snowflake算法中sequence最大值（2^13 = 8192）。可通过 boostPower 配置进行扩容，以提高 RingBuffer 读写吞吐量。

**基本实现原理**

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

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

【UidGenerator通过借用未来时间来解决sequence天然存在的并发限制】：

因为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年。

【采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费】

使用RingBuffer缓存生成的id。RingBuffer是个环形数组，默认大小为8192个，里面缓存着生成的id。

1.  获取id
    
    1.  会从ringbuffer中拿一个id，支持并发获取
2.  填充id
    
    1.  RingBuffer填充时机
    2.  程序启动时，将RingBuffer填充满，缓存着8192个id
    3.  调用getUID()获取id时，检测到RingBuffer中的剩余id个数小于总个数的50%，将RingBuffer填充满，使其缓存8192个id
    4.  定时填充（可配置是否使用以及定时任务的周期）
3.  Tail指针、Cursor指针用于环形数组上读写slot.

**Tail指针**

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

**Cursor指针**

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

![e1be5f9a9343428db3c558f417299400.png][]

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

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

![dc1e6d844e334990b2b013799a985ca3.png][]

**RingBuffer填充时机**

初始化预填充： RingBuffer初始化时，预先填充满整个RingBuffer。

即时填充：Take消费时，即时检查剩余可用slot量(tail - cursor)，如小于设定阈值，则补全空闲slots。阈值可通过paddingFactor来进行配置，请参考Quick Start中CachedUidGenerator配置。

周期填充：通过Schedule线程，定时补全空闲slots。可通过scheduleInterval配置，以应用定时填充功能，并指定Schedule时间间隔。

## **落地** ##

[--_--_UidGenerator_IT_-CSDN]: https://knife.blog.csdn.net/article/details/122830153
[https_github.com_baidu_uid-generator]: https://github.com/baidu/uid-generator
[20200410141930413.png]: https://img-blog.csdnimg.cn/20200410141930413.png
[e1be5f9a9343428db3c558f417299400.png]: https://img-blog.csdnimg.cn/e1be5f9a9343428db3c558f417299400.png
[dc1e6d844e334990b2b013799a985ca3.png]: https://img-blog.csdnimg.cn/dc1e6d844e334990b2b013799a985ca3.png