在实现上, UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐,避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万
Snowflake算法描述:指定机器 & 同一时刻 & 某一并发序列,是唯一的。据此可生成一个64 bits的唯一ID(long)。默认采用上图字节分配方式:
- sign(1bit)
固定1bit符号标识,即生成的UID为正数。 - delta seconds (28 bits)
当前时间,相对于时间基点”2016-05-20”的增量值,单位:秒,最多可支持约8.7年 - worker id (22 bits)
机器id,最多可支持约420w次机器启动。内置实现为在启动时由数据库分配,默认分配策略为用后即弃,后续可提供复用策略。 - sequence (13 bits)
每秒下的并发序列,13 bits可支持每秒8192个并发。
采用RingBuffer环形数组的方式,开启高并发,存在生产者/消费者。CachedUidGenerator采用了双RingBuffer,Uid-RingBuffer用于存储Uid、Flag-RingBuffer用于存储Uid状态(是否可填充、是否可消费)
RingBuffer填充时机
- 初始化预填充
RingBuffer初始化时,预先填充满整个RingBuffer. - 即时填充
Take消费时,即时检查剩余可用slot量(tail
-cursor
),如小于设定阈值,则补全空闲slots。阈值可通过paddingFactor
来进行配置,请参考Quick Start中CachedUidGenerator配置 - 周期填充
通过Schedule线程,定时补全空闲slots。可通过scheduleInterval
配置,以应用定时填充功能,并指定Schedule时间间隔