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()在用户态就可以完成操作,减少了进入内核态的损耗。
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,若同一毫秒把序列号用完了,则“等待至下一毫秒”。
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可以在代码实现上有效减少锁的密度。
分享到:
相关推荐
We have retired the initial release of Snowflake and working on open sourcing the next version based on Twitter-server, in a form that can run anywhere without requiring Twitter's own infrastructure ...
Twitter的分布式自增ID算法snowflake (Java版)
Laravel开发-laravel-snowflake 为拉拉维尔雪花。
Twitter的分布式自增ID雪花算法snowflake (Java版)
Twitter Snowflake算法,php版代码; 请见博客: http://blog.csdn.net/envon123/article/details/52953872
nodejs-snowflake是一种快速可靠的方法,可以为分布式系统生成时间可排序的64位ID。 主要的ID生成功能是使用N-API用C ++编写的,这使得ID生成的过程非常快。 使用C ++进行id生成还可以确保生成的数字大小为64位。 ...
最近项目需要解决高并发分布式生成唯一ID值的问题,经过考虑,采用Snowflake算法,该算法是一个很有效的办法,具体的可以自己百度,这里是基于thinkPHP5 开发的通用的生成器,其实也是参考了网上的方法,只是增加了...
主要介绍了Java实现Twitter的分布式自增ID算法snowflake,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
开源项目-bwmarrin-snowflake.zip,bwmarrin/snowflake - A very simple package to generate or parse Twitter snowflake IDs
而twitter的snowflake解决了这种需求,最初是Twitter把存储系统从MySQL迁移到Cassandra,因为Cassandra没有顺序的ID生成机制,所以开发了这样一套唯一的ID生成服务。结构雪花的结构如下(每部分用-分开): 0 - ...
Laravel开发-laravel-snowflake .zip
Twitter的 Snowflake 推特雪花算法JAVA实现方案,用于自动生成id
雪花算法,分布式id生成算法的有很多种,Twitter的SnowFlake就是其中经典的一种。
matlab开发-Snowflake。创建雪花
资源分类:Python库 所属语言:Python 资源全名:dbt-snowflake-0.16.1.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
Twitter-Snowflake算法,java代码实现,采用默认配置,单例单机模式
Twitter_Snowflake,SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分),并且效率较高,经测试,SnowFlake每秒能够产生26万ID左右。
北大POJ3349-Snowflake Snow Snowflakes 解题报告+AC代码
基于twitter的雪花算法来生成ID,用于取代UUID那种无序、128位的字符串形式的ID,提供 一种更加高效、人性化的全局唯一ID的生成方式,目前单机CPU4核、内存8G压测的并发数可以达到 250万/每秒,即每秒最多可以生成250...