简介
说明
百度的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。
- 获取id
- 会从ringbuffer中拿一个id，支持并发获取
- 填充id
- RingBuffer填充时机
- 程序启动时，将RingBuffer填充满，缓存着8192个id
- 调用getUID()获取id时，检测到RingBuffer中的剩余id个数小于总个数的50%，将RingBuffer填充满，使其缓存8192个id
- 定时填充（可配置是否使用以及定时任务的周期）
- 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时间间隔。
请先 ！