php网站地图,环保网页设计素材,南京百度网站推广,wordpress add_action()转载自 百度开源的分布式唯一ID生成器UidGenerator#xff0c;解决了时钟回拨问题
UidGenerator是百度开源的Java语言实现#xff0c;基于Snowflake算法的唯一ID生成器。而且#xff0c;它非常适合虚拟环境#xff0c;比如#xff1a;Docker。另外#xff0c;它通过消…转载自 百度开源的分布式唯一ID生成器UidGenerator解决了时钟回拨问题
UidGenerator是百度开源的Java语言实现基于Snowflake算法的唯一ID生成器。而且它非常适合虚拟环境比如Docker。另外它通过消费未来时间克服了雪花算法的并发限制。UidGenerator提前生成ID并缓存在RingBuffer中。 压测结果显示单个实例的QPS能超过6000,000。
依赖环境 JDK8 MySQL用于分配WorkerId
snowflake
由下图可知雪花算法的几个核心组成部分 1位sign标识位 41位时间戳 10位workId数据中心工作机器可以其他组成方式 12位自增序列 但是百度对这些组成部分稍微调整了一下 由上图可知UidGenerator的时间部分只有28位这就意味着UidGenerator默认只能承受8.5年2^28-1/86400/365。当然根据你业务的需求UidGenerator可以适当调整delta seconds、worker node id和sequence占用位数。
接下来分析百度UidGenerator的实现。需要说明的是UidGenerator有两种方式提供和DefaultUidGenerator和CachedUidGenerator。我们先分析比较容易理解的DefaultUidGenerator。
DefaultUidGenerator
delta seconds
这个值是指当前时间与epoch时间的时间差且单位为秒。epoch时间就是指集成UidGenerator生成分布式ID服务第一次上线的时间可配置也一定要根据你的上线时间进行配置因为默认的epoch时间可是2016-09-20不配置的话会浪费好几年的可用时间。
worker id
接下来说一下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)COMMENTDB WorkerID Assigner for UID Generator,ENGINE INNODB;
UidGenerator会在集成用它生成分布式ID的实例启动的时候往这个表中插入一行数据得到的id值就是准备赋给workerId的值。由于workerId默认22位那么集成UidGenerator生成分布式ID的所有实例重启次数是不允许超过4194303次即2^22-1否则会抛出异常。
这段逻辑的核心代码来自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);}
总结
通过DefaultUidGenerator的实现可知它对时钟回拨的处理比较简单粗暴。另外如果使用UidGenerator的DefaultUidGenerator方式生成分布式ID一定要根据你的业务的情况和特点调整各个字段占用的位数
property nametimeBits value28/property nameworkerBits value22/property nameseqBits value13/property nameepochStr value2016-09-20/ CachedUidGenerator
CachedUidGenerator是UidGenerator的重要改进实现。它的核心利用了RingBuffer如下图所示它本质上是一个数组数组中每个项被称为slot。UidGenerator设计了两个RingBuffer一个保存唯一ID一个保存flag。RingBuffer的尺寸是2^nn必须是正整数 RingBuffer Of Flag
其中保存flag这个RingBuffer的每个slot的值都是0或者10是CANPUTFLAG的标志位1是CANTAKEFLAG的标识位。每个slot的状态要么是CANPUT要么是CANTAKE。以某个slot的值为例初始值为0即CANPUT。接下来会初始化填满这个RingBuffer这时候这个slot的值就是1即CANTAKE。等获取分布式ID时取到这个slot的值后这个slot的值又变为0以此类推。
RingBuffer Of UID
保存唯一ID的RingBuffer有两个指针Tail指针和Cursor指针。 Tail指针表示最后一个生成的唯一ID。如果这个指针追上了Cursor指针意味着RingBuffer已经满了。这时候不允许再继续生成ID了。用户可以通过属性rejectedPutBufferHandler指定处理这种情况的策略。 Cursor指针表示最后一个已经给消费的唯一ID。如果Cursor指针追上了Tail指针意味着RingBuffer已经空了。这时候不允许再继续获取ID了。用户可以通过属性rejectedTakeBufferHandler指定处理这种异常情况的策略。
另外如果你想增强RingBuffer提升它的吞吐能力那么需要配置一个更大的boostPower值 !-- RingBuffer size扩容参数, 可提高UID生成能力.即每秒产生ID数上限能力 -- !-- 默认:3原bufferSize2^13, 扩容后bufferSize 2^13 3 65536 -- property nameboostPower value3/
CachedUidGenerator的理论讲完后接下来就是它具体是如何实现的了我们首先看它的申明它是实现了DefaultUidGenerator所以它事实上就是对DefaultUidGenerator的增强 public class CachedUidGenerator extends DefaultUidGenerator implements DisposableBean { ... ... }
worker id
CachedUidGenerator的workerId实现继承自它的父类DefaultUidGenerator即实例启动时往表WORKER_NODE插入数据后得到的自增ID值。
接下来深入解读CachedUidGenerator的核心操作即对RingBuffer的操作包括初始化、取分布式唯一ID、填充分布式唯一ID等。
初始化
CachedUidGenerator在初始化时除了给workerId赋值还会初始化RingBuffer。这个过程主要工作有 根据boostPower的值确定RingBuffer的size 构造RingBuffer默认paddingFactor为50。这个值的意思是当RingBuffer中剩余可用ID数量少于50%的时候就会触发一个异步线程往RingBuffer中填充新的唯一ID调用BufferPaddingExecutor中的paddingBuffer()方法这个线程中会有一个标志位running控制并发问题直到填满为止 判断是否配置了属性scheduleInterval这是另外一种RingBuffer填充机制, 在Schedule线程中, 周期性检查填充。默认:不配置, 即不使用Schedule线程. 如需使用, 请指定Schedule线程时间间隔, 单位:秒 初始化Put操作拒绝策略对应属性rejectedPutBufferHandler。即当RingBuffer已满, 无法继续填充时的操作策略。默认无需指定, 将丢弃Put操作, 仅日志记录. 如有特殊需求, 请实现RejectedPutBufferHandler接口(支持Lambda表达式) 初始化Take操作拒绝策略对应属性rejectedTakeBufferHandler。即当环已空, 无法继续获取时的操作策略。默认无需指定, 将记录日志, 并抛出UidGenerateException异常. 如有特殊需求, 请实现RejectedTakeBufferHandler接口 初始化填满RingBuffer中所有slot即塞满唯一ID这一步和第2步骤一样都是调用BufferPaddingExecutor中的paddingBuffer()方法 开启buffer补丁线程前提是配置了属性scheduleInterval原理就是利用ScheduledExecutorService的scheduleWithFixedDelay()方法。
说明第二步的异步线程实现非常重要也是UidGenerator解决时钟回拨的关键在满足填充新的唯一ID条件时通过时间值递增得到新的时间值lastSecond.incrementAndGet()而不是System.currentTimeMillis()这种方式而lastSecond是AtomicLong类型所以能保证线程安全问题。
取值
RingBuffer初始化有值后接下来的取值就简单了。不过由于分布式ID都保存在RingBuffer中取值过程中就会有一些逻辑判断 如果剩余可用ID百分比低于paddingFactor参数指定值就会异步生成若干个ID集合直到将RingBuffer填满。 如果获取值的位置追上了tail指针就会执行Task操作的拒绝策略。 获取slot中的分布式ID。 将这个slot的标志位只为CANPUTFLAG。
总结
通过上面对UidGenerator的分析可知CachedUidGenerator方式主要通过采取如下一些措施和方案规避了时钟回拨问题和增强唯一性 自增列UidGenerator的workerId在实例每次重启时初始化且就是数据库的自增ID从而完美的实现每个实例获取到的workerId不会有任何冲突。 RingBufferUidGenerator不再在每次取ID时都实时计算分布式ID而是利用RingBuffer数据结构预先生成若干个分布式ID并保存。 时间递增传统的雪花算法实现都是通过System.currentTimeMillis()来获取时间并与上一次时间进行比较这样的实现严重依赖服务器的时间。而UidGenerator的时间类型是AtomicLong且通过incrementAndGet()方法获取下一次的时间从而脱离了对服务器时间的依赖也就不会有时钟回拨的问题这种做法也有一个小问题即分布式ID中的时间信息可能并不是这个ID真正产生的时间点例如获取的某分布式ID的值为3200169789968523265它的反解析结果为{timestamp:2019-05-02 23:26:39,workerId:21,sequence:1}但是这个ID可能并不是在2019-05-02 23:26:39这个时间产生的。
