少年阿宾

那些青春的岁月

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  500 Posts :: 0 Stories :: 135 Comments :: 0 Trackbacks
    Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的id,这些id还需要一些大致的顺序(方便客户端排序),并且在分布式系统中不同机器产生的id必须不同。

生成的ID是64Bits整型数,同时满足高性能(>10K ids/s),低延迟(<2ms)和高可用。

在分布式系统中,需要生成全局UID的场合还是比较多的,twitter的snowflake解决了这种需求,实现也还是很简单的,除去配置信息,核心代码就是毫秒级时间41位+机器ID 10位+毫秒内序列12位。

该项目地址为:https://github.com/twitter/snowflake是用Scala实现的。

python版详见开源项目https://github.com/erans/pysnowflake

核心代码为其IdWorker这个类实现,其原理结构如下,我分别用一个0表示一位,用—分割开部分的作用:

0---0000000000 0000000000 0000000000 0000000000 0 --- 00000 ---00000 ---0000000000 00

在上面的字符串中,第一位为未使用(实际上也可作为long的符号位),接下来的41位为毫秒级时间,然后5位datacenter标识位,5位机器ID(并不算标识符,实际是为线程标识),然后12位该毫秒内的当前毫秒内的计数,加起来刚好64位,为一个Long型。

这样的好处是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由datacenter和机器ID作区分),并且效率较高,经测试,snowflake每秒能够产生26万ID左右,完全满足需要。

1. 41位的时间序列(精确到毫秒,41位的长度可以使用69年) 

2. 10位的机器标识(10位的长度最多支持部署1024个节点,支持多机房的分布式,需要使用zookeeper) 

3. 12位的计数顺序号(12位的计数顺序号支持每个节点每毫秒产生4096个ID序号) 最高位是符号位,始终为0。

//64--------63-----------22-----------12----------0
//符号位 |41位时间 |10位机器码 |12位自增码|

对twitter而言这样的ID生成方案满足:

1.每秒能够生成足够的ID数。 2.生成的ID按照时间大致有序。

用zookeeper的原因是需要获取一个workerId,当然你也可以给分布式节点手工指定不同的workderId,那样就不需要用zookeeper了。

一个server一个workerid, 用zookeeper做保证.


除了最高位bit标记为不可用以外,其余三组bit占位均可浮动,看具体的业务需求而定。默认情况下41bit的时间戳可以支持该算法使用到2082年,10bit的工作机器id可以支持1023台机器,序列号支持1毫秒产生4095个自增序列id
















posted on 2015-05-17 13:20 abin 阅读(1200) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航: