文档章节

Twitter-Snowflake,64位自增ID算法详解

挨踢猿
 挨踢猿
发布于 2016/09/07 17:52
字数 857
阅读 51
收藏 0

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

Snowflake算法核心

时间戳工作机器id序列号组合在一起。

 

snowflake-64bit

 

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

 

Snowflake – 时间戳

这里时间戳的细度是毫秒级,具体代码如下,建议使用64位linux系统机器,因为有vdso,gettimeofday()在用户态就可以完成操作,减少了进入内核态的损耗。

1

2

3

4

5

6

uint64_t generateStamp()

{

    timeval tv;

    gettimeofday(&tv, 0);

    return (uint64_t)tv.tv_sec * 1000 + (uint64_t)tv.tv_usec / 1000;

}

默认情况下有41个bit可以供使用,那么一共有T(1llu << 41)毫秒供你使用分配,年份 = T / (3600 * 24 * 365 * 1000) = 69.7年。如果你只给时间戳分配39个bit使用,那么根据同样的算法最后年份 = 17.4年。

Snowflake – 工作机器id

严格意义上来说这个bit段的使用可以是进程级,机器级的话你可以使用MAC地址来唯一标示工作机器工作进程级可以使用IP+Path来区分工作进程。如果工作机器比较少,可以使用配置文件来设置这个id是一个不错的选择,如果机器过多配置文件的维护是一个灾难性的事情。

这里的解决方案是需要一个工作id分配的进程,可以使用自己编写一个简单进程来记录分配id,或者利用Mysql auto_increment机制也可以达到效果。

snowflake - 工作id

 

工作进程与工作id分配器只是在工作进程启动的时候交互一次,然后工作进程可以自行将分配的id数据落文件,下一次启动直接读取文件里的id使用。

PS:这个工作机器id的bit段也可以进一步拆分,比如用前5个bit标记进程id,后5个bit标记线程id之类:D

Snowflake – 序列号

序列号就是一系列的自增id(多线程建议使用atomic),为了处理在同一毫秒内需要给多条消息分配id,若同一毫秒把序列号用完了,则“等待至下一毫秒”。

1

2

3

4

5

6

7

8

uint64_t waitNextMs(uint64_t lastStamp)

{

    uint64_t cur = 0;

    do {

        cur = generateStamp();

    } while (cur <= lastStamp);

    return cur;

}

 

总体来说,是一个很高效很方便的GUID产生算法,一个int64_t字段就可以胜任,不像现在主流128bit的GUID算法,即使无法保证严格 的id序列性,但是对于特定的业务,比如用做游戏服务器端的GUID产生会很方便。另外,在多线程的环境下,序列号使用atomic可以在代码实现上有效 减少锁的密度。

java版本地址:http://www.oschina.net/code/snippet_147955_25122

本文转载自:http://www.lanindex.com/twitter-snowflake

共有 人打赏支持
挨踢猿
粉丝 0
博文 6
码字总数 1253
作品 0
南京
私信 提问
Twitter-Snowflake,64位自增ID算法详解

Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的id,这些id还需要一些大致的顺序(方便客户端排序),并且在分布式系统中不同...

毛爷爷夸我帅
2016/05/10
448
0
分布式高效有序 ID 生产--dsequence

高性能(理论QPS > 400w/s)GUID产生算法(sequence),基于Snowflake实现64位自增ID算法。 Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分...

李景枫
2017/04/27
287
0
李景枫/sequence

分布式高效ID生产黑科技(sequence) 开源产品介绍(微服务基础设施QQ交流群:191958521) 配置中心(mconf) GITHUB:https://github.com/yu120/mconf 码云:https://git.oschina.net/yu120/mco...

李景枫
2016/07/08
0
0
对新UUID算法的说明

原来的算法产生36位的字符串类型的UUID,当数据量比较大时有很大可能会成为性能瓶颈。另外算法本身完全基于时间产生的随机数,还是有小概率生成不唯一的ID。基于以上两点原因,我又搜索了一下...

sieg
2015/03/01
4
3
基于Snowflake算法的分布式ID-黑科技

基于Twitter的Snowflake算法(俗称雪花算法)实现64位自增ID算法,性能高达:QPS>400w/s。为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的ID,这些ID还需要一些大致的顺...

李景枫
2018/03/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

C++随笔(四)Nuget打包

首先把自己编译好的包全部准备到一个文件夹 像这样 接下来新建一个文本文档,后缀名叫.nuspec 填写内容 <?xml version="1.0"?><package xmlns="http://schemas.microsoft.com/packaging/201......

Pulsar-V
29分钟前
0
0
再谈使用开源软件搭建数据分析平台

三年前,我写了这篇博客使用开源软件快速搭建数据分析平台, 当时收到了许多的反馈,有50个点赞和300+的收藏。到现在我还能收到一些关于dataplay2的问题。在过去的三年,开源社区和新技术的发...

naughty
今天
3
0
Python3的日期和时间

python 中处理日期时间数据通常使用datetime和time库 因为这两个库中的一些功能有些重复,所以,首先我们来比较一下这两个库的区别,这可以帮助我们在适当的情况下时候合适的库。 在Python文...

编程老陆
今天
2
0
分布式面试整理

并发和并行 并行是两个任务同时进行,而并发呢,则是一会做一个任务一会又切换做另一个任务。 临界区 临界区用来表示一种公共资源或者说是共享数据,可以被多个线程使用,但是每一次,只能有...

群星纪元
今天
3
0
手机通过wifi遥控arduino

手机下载Blinker 从Blinker官网下载手机App,安装到手机。 手机连接WiFi。 点击我的设备右上角的"+"添加设备,选择Arduino -> wifi接入,复制密钥以备后续使用。 点击新建的设备,可以在新界...

davidwbnu
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部