百度uid-generator源码
https://github.com/baidu/uid-generator
snowflake算法
uid-generator是基于Twitter开源的snowflake算法实现的。
snowflake将long的64位分为了3部分,时间戳、工作机器id和序列号,位数分配如下。
其中,时间戳部分的时间单位一般为毫秒。也就是说1台工作机器1毫秒可产生4096个id(2的12次方)。
源码实现分析
与原始的snowflake算法不同,uid-generator支持自定义时间戳、工作机器id和序列号等各部分的位数,以应用于不同场景。默认分配方式如下。
sign(1bit)
固定1bit符号标识,即生成的UID为正数。delta seconds (28 bits)
当前时间,相对于时间基点"2016-05-20"的增量值,单位:秒,最多可支持约8.7年(注意:1. 这里的单位是秒,而不是毫秒! 2.注意这里的用词,是“最多”可支持8.7年,为什么是“最多”,后面会讲)worker id (22 bits)
机器id,最多可支持约420w次机器启动。内置实现为在启动时由数据库分配,默认分配策略为用后即弃,后续可提供复用策略。sequence (13 bits)
每秒下的并发序列,13 bits可支持每秒8192个并发。(注意下这个地方,默认支持qps最大为8192个)
DefaultUidGenerator
DefaultUidGenerator的产生id的方法与基本上就是常见的snowflake算法实现,仅有一些不同,如以秒为为单位而不是毫秒。
DefaultUidGenerator的产生id的方法如下。
CachedUidGenerator
CachedUidGenerator支持缓存生成的id。
基本实现原理
关于CachedUidGenerator,文档上是这样介绍的。
在实现上, UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐,避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。
【采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费】
使用RingBuffer缓存生成的id。RingBuffer是个环形数组,默认大小为8192个,里面缓存着生成的id。
获取id
会从ringbuffer中拿一个id,支持并发获取
填充id
RingBuffer填充时机
程序启动时,将RingBuffer填充满,缓存着8192个id
在调用getUID()获取id时,检测到RingBuffer中的剩余id个数小于总个数的50%,将RingBuffer填充满,使其缓存8192个id
定时填充(可配置是否使用以及定时任务的周期)
【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年)
源码剖析
获取id
RingBuffer缓存已生成的id
(注意:这里的RingBuffer不是Disruptor框架中的RingBuffer,但是借助了很多Disruptor中RingBuffer的设计思想,比如使用缓存行填充解决伪共享问题)
RingBuffer为环形数组,默认容量为sequence可容纳的最大值(8192个),可以通过boostPower参数设置大小。
tail指针、Cursor指针用于环形数组上读写slot:
Tail指针
表示Producer生产的最大序号(此序号从0开始,持续递增)。Tail不能超过Cursor,即生产者不能覆盖未消费的slot。当Tail已赶上curosr,此时可通过rejectedPutBufferHandler指定PutRejectPolicyCursor指针
表示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填充满,缓存着8192个id
在调用getUID()获取id时,检测到RingBuffer中的剩余id个数小于总个数的50%,将RingBuffer填充满,使其缓存8192个id
定时填充(可配置是否使用以及定时任务的周期)
填充RingBuffer
生成id(上面代码中的uidProvider.provide调用的就是这个方法)
填充缓存行解决“伪共享”
关于伪共享,可以参考这篇文章《伪共享(false sharing),并发编程无声的性能杀手》
PaddedAtomicLong为什么要这么设计?
可以参考下面文章
一个Java对象到底占用多大内存?https://www.cnblogs.com/magialmoon/p/3757767.html
写Java也得了解CPU--伪共享 https://www.cnblogs.com/techyc/p/3625701.html
最新文章
- Android 图片的颜色处理
- iOS-SVN、Git
- MySQL 如何修改字符集 utf8 改为 utf8mb4
- 无法为数据库 XXX 中的对象XXX 分配空间,因为 'PRIMARY' 文件组已满。请删除不需要的文件、删除文件组中的对象、将其他文件添加到文件组或为文件组中的现有文件启用自动增长,以便增加可用磁盘空间。
- 当你还在争夺移动支付的时候,我已经统一了IC卡市场
- [转载] RED-BLACK(红黑)树的实现TreeMap源码阅读
- 页面输入的数据格式转换类:BaseAction(经常使用于Struts框架中)
- PMP知识点(五)——配置管理
- VS 测试printf 多参数 输出 i++ 和++i 结果
- 【题解】Luogu P1471 方差
- css学习_css常见属性用法
- 【CSS】自定义checkbox样式
- spring boot + es
- mingw 设置python 设置git环境变量
- iOS 优秀开源框架 开源包 开发包 from : Podfile of chatsecure ---待完善
- FPGA内部动态可重置PLL讲解(二)
- 【CF886D】Restoration of string 乱搞
- linux下命令行工具gcp显示拷贝进度条
- mysql 操作符
- HDU 4522 (恶心建图)