所有分类
  • 所有分类
  • 未分类

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

简介

说明

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

官网

github: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 的格式进行划分,可调整各个字段占用的位数。

  • 第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。

解决时钟回拨

核心代码如下,几个实现的关键点:

  • 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在初始化时除了给workerId赋值,还会初始化RingBuffer。这个过程主要工作有:

1、根据boostPower的值确定RingBuffer的size;

2、构造RingBuffer,默认paddingFactor为50。这个值的意思是当RingBuffer中剩余可用ID数量少于50%的时候,就会触发一个异步线程往RingBuffer中填充新的唯一ID(调用BufferPaddingExecutor中的paddingBuffer()方法,这个线程中会有一个标志位running控制并发问题),直到填满为止;

3、判断是否配置了属性scheduleInterval,这是另外一种RingBuffer填充机制, 在Schedule线程中, 周期性检查填充。默认:不配置, 即不使用Schedule线程. 如需使用, 请指定Schedule线程时间间隔, 单位:秒;

4、初始化Put操作拒绝策略,对应属性rejectedPutBufferHandler。即当RingBuffer已满, 无法继续填充时的操作策略。默认无需指定, 将丢弃Put操作, 仅日志记录. 如有特殊需求, 请实现RejectedPutBufferHandler接口(支持Lambda表达式);

5、初始化Take操作拒绝策略,对应属性rejectedTakeBufferHandler。即当环已空, 无法继续获取时的操作策略。默认无需指定, 将记录日志, 并抛出UidGenerateException异常. 如有特殊需求, 请实现RejectedTakeBufferHandler接口;

6、初始化填满RingBuffer中所有slot(即塞满唯一ID,这一步和第2步骤一样都是调用BufferPaddingExecutor中的paddingBuffer()方法);

7、开启buffer补丁线程(前提是配置了属性scheduleInterval),原理就是利用ScheduledExecutorService的scheduleWithFixedDelay()方法。

说明:第二步的异步线程实现非常重要,是UidGenerator解决时钟回拨的关键:在满足填充新的唯一ID条件时,通过时间值递增得到新的时间值(lastSecond.incrementAndGet()),而不是System.currentTimeMillis()这种方式,而lastSecond是AtomicLong类型,所以能保证线程安全问题。

取值

RingBuffer初始化有值后,接下来的取值就简单了。不过,由于分布式ID都保存在RingBuffer中,取值过程中就会有一些逻辑判断:

1、如果剩余可用ID百分比低于paddingFactor参数指定值,就会异步生成若干个ID集合,直到将RingBuffer填满。

2、如果获取值的位置追上了tail指针,就会执行Task操作的拒绝策略。

3、获取slot中的分布式ID。

4、将这个slot的标志位只为CAN_PUT_FLAG。

原理详述

关于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。

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

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

RingBuffer填充时机

初始化预填充: RingBuffer初始化时,预先填充满整个RingBuffer。

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

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

0

评论0

请先

显示验证码
没有账号?注册  忘记密码?

社交账号快速登录