+0
日增长
5,544
stars
1,542
forks
245
watchers
27
prs
77
issues
0
releases
README
UidGenerator ========================== In Chinese 中文版 UidGenerator is a Java implemented, Snowflake based unique ID generator. It works as a component, and allows users to override workId bits and initialization strategy. As a result, it is much more suitable for virtualization environment, such as docker. Besides these, it overcomes concurrency limitation of Snowflake algorithm by consuming future time; parallels UID produce and consume by caching UID with RingBuffer; eliminates CacheLine pseudo sharing, which comes from RingBuffer, via padding. And finally, it can offer over 6 million QPS per single instance. Requires:Java8+, MySQL(Default implement as WorkerID assigner; If there are other implements, MySQL is not required) Snowflake ------------- !Snowflake Snowflake algorithm: An unique id consists of worker node, timestamp and sequence within that timestamp. Usually, it is a 64 bits number(long), and the default bits of that three fields are as follows: sign(1bit) The highest bit is always 0. delta seconds (28 bits) The next 28 bits, represents delta seconds since a customer epoch(2016-05-20). The maximum time will be 8.7 years. worker id (22 bits) The next 22 bits, represents the worker node id, maximum value will be 4.2 million. UidGenerator uses a build-in database based worker id assigner when startup by default, and it will dispose previous work node id after reboot. Other strategy such like 'reuse' is coming soon. sequence (13 bits) the last 13 bits, represents sequence within the one second, maximum is 8192 per second by default. The parameters above can be configured in spring bean CachedUidGenerator ------------------- RingBuffer is an array,each item of that array is called 'slot', every slot keeps a uid or a flag(Double RingBuffer). The size of RingBuffer is 2^n, where n is positive integer and equal or greater than bits of sequence. Assign bigger value to boostPower if you want to enlarge RingBuffer to improve throughput. Tail & Cursor pointer Tail Pointer Represents the latest produced UID. If it catches up with cursor, the ring buffer will be full, at that moment, no put operation should be allowed, you can specify a policy to handle it by assigning property rejectedPutBufferHandler. Cursor Pointer Represents the latest already consumed UID. If cursor catches up with tail, the ring buffer will be empty, and any take operation will be rejected. you can also specify a policy to handle it by assigning property rejectedTakeBufferHandler. !RingBuffer CachedUidGenerator used double RingBuffer,one RingBuffer for UID, another for status(if valid for take or put) Array can improve performance of reading, due to the CUP cache mechanism. At the same time, it brought the side effect of 「False Sharing」, in order to solve it, cache line padding is applied. !FalseSharing RingBuffer filling Initialization padding During RingBuffer initializing,the entire RingBuffer will
Top issues
#100注意算法中只能支持到2024-11-20 21:24:1615 comments · 2024-11-20#44双Buffer使用问题3 comments · 2019-11-21#42设计不合理2 comments · 2019-09-20#36这个是怎么算的?例如节点采取用完即弃的WorkerIdAssigner策略, 重启频率为12次/天, 那么配置成{"workerBits":23,"timeBits":31,"seqBits":9}时, 可支持28个节点以整体并发量14400 UID/s的速度持续运行68年. 时间 2的31次方-1 / 86400 / 365 = 68年2 comments · 2019-06-20#14A component required a bean of type 'com.baidu.fsg.uid.worker.dao.WorkerNodeDAO' that could not be found.2 comments · 2018-10-26#99多台服务器的时候生成的 ID 会重复。1 comments · 2024-11-01#98Why don't you use milliseconds timeBits ?1 comments · 2024-10-25#96写入Ringbuffer时,生成的ID会跳过某些时间1 comments · 2024-07-26