基于snowflake算法实现了一个Sequence的REST 服务

首先简单讲讲Snowflake,snowflake是来自于Twitter的一个开源算法,github上有,但是找不到源代码,现在好像是一个公有的服务,然并卵,别人在墙外,我们还是来讲讲其算法,snowflake是用int64来表示一个序列号的,看上去和我们的时间戳很像,但是它的起始元年不是1970年,而是自定义的,你没看错,就是自定义的,然后时间戳里面只是记录下了当前毫秒与自定义的元年时间差,这样起始就用不到64位的bit来记录整个时间戳,多的来的几位就可以做其他的事情,来看下面的结构

1
2
3
4
5
00000.....000 00000 00000 000000000000
|___________| |___| |___| |__________|
| | | |
42bit 5bit 5bit 12bit

第一段:42bit 时间标记

记录的是当前时间与元年的时间差,我们拿到sequence之后,只要知道元年的时间,就可以推算出sequence的生成时间,也算隐含了createTime,当然用于做排序也是相当不错的

第二段:5bit 数据中心Id标记

记录的是数据中心的Id,5bit最大可以表示32个数据中心,这么多数据中心能保证全球范围内服务可用

第三段:5bit 节点标记

记录的是单个数据中心里面服务节点的Id,同理也是最大可以有32个节点,这个除非是整个数据中心离线,否则可以保证服务永远可用

第四段:12bit 单毫秒内自增流水

用于单个服务节点应对高并发情况下,一毫秒内被多次请求sequence的情况,因此在单毫秒内增加一个自增区间来做缓冲,12bit最多可以最大表示到4095,这个基本上单个节点每毫秒被并发4000多次,这种并发情况下,公司应该也会加大投入了吧.所以基本上也不用担心这个问题.

以上就是snowflake的数据结构的核心了,四段组合起来正好64bit,一个长整型数据,既能表达时间,也方便用于排序,当然绝对排序是做不到的,相对排序,基本上颗粒度到毫秒级的话,都能容忍的.另外42位的时间戳可以保证170多年的时间差可用,按照现在的软件周期来看,能用10年已经灰常不错的,100之后,谁知道计算机已经是什么样了呢,至少保证现在够用,大不了以后扩展为128位也没什么问题.

我自己的实现将这个结构进行了一点小小的改动,结构如下:

1
2
3
4
000000....00000 0000000000 00000000
|_____________| |________| |______|
| | |
46bit 10bit 8bit
  1. 第一部分还是时间戳,只是范围更大了
  2. 标示的单毫秒内的自增流水,我缩小为10bit,最大一毫秒内可以支持生成1024个流水号,其实也很高了
  3. 去掉了数据中心的Id标记,保留并扩大了节点标记,最多支持255个节点

具体的代码在cfsequence,可以自行下载,并编译使用,具体的REST API,可以参考README.md

欢迎多提意见

坚持原创技术分享,您的支持将鼓励我继续创作!