`
javafan_303
  • 浏览: 957072 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

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

 
阅读更多

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可以在代码实现上有效减少锁的密度。

 

转自

http://www.lanindex.com/twitter-snowflake,64位自增id算法详解/

参考代码

https://github.com/twitter/snowflake

 

分享到:
评论

相关推荐

    Laravel开发-laravel-snowflake

    `laravel-snowflake` 是一个专门为 Laravel 设计的扩展包,它引入了 Twitter 的 Snowflake ID 生成算法,旨在为 Laravel 应用提供高效且具有时间序列性质的全局唯一 ID。 **1. Snowflake 算法介绍** Snowflake 算法...

    snowflake-C语言实现分布式自增有序的唯一ID生成算法

    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

    雪花算法是Twitter开源的一种分布式ID生成算法,它能够生成全局唯一、递增且无碰撞的64位整数ID。这个算法在分布式系统中非常适用,因为传统的序列号生成方式在分布式环境中往往难以解决冲突问题。下面我们将详细...

    Laravel开发-laravel-snowflake .zip

    laravel-snowflake就是Laravel对这个算法的实现,它能够生成类似于Twitter Snowflake的64位ID,这些ID由时间戳、工作节点ID和序列号三部分组成,确保了全局唯一性。 1. **雪花算法(Snowflake)详解** - **时间戳*...

    nodejs-snowflake:为分布式系统生成时间可排序的64位唯一ID(灵感来自Twitter雪花)

    nodejs-snowflake是一种快速可靠的方法,可以为分布式系统生成时间可排序的64位ID。 主要的ID生成功能是使用N-API用C ++编写的,这使得ID生成的过程非常快。 使用C ++进行id生成还可以确保生成的数字大小为64位。 ...

    Twitter的分布式自增ID算法Snowflake的PHP实现,Snowflake PHP版本,高并发唯一id,全局唯一id,不重复id

    Twitter Snowflake算法,php版代码; 请见博客: http://blog.csdn.net/envon123/article/details/52953872

    Java实现Twitter的分布式自增ID算法snowflake

    【Java实现Twitter的分布式自增ID算法snowflake】 在分布式系统设计中,生成全局唯一ID是一个常见的需求。Twitter的Snowflake算法就是为了解决这个问题而诞生的,它提供了一种高效、有序且不会冲突的ID生成策略。...

    PHP Snowflake(雪花算法)生成唯一ID值

    最近项目需要解决高并发分布式生成唯一ID值的问题,经过考虑,采用Snowflake算法,该算法是一个很有效的办法,具体的可以自己百度,这里是基于thinkPHP5 开发的通用的生成器,其实也是参考了网上的方法,只是增加了...

    Python库 | dbnd-snowflake-0.45.3.tar.gz

    **Python库dbnd-snowflake 0.45.3详解** 在IT行业中,Python以其简洁易读的语法和丰富的库支持,成为了数据科学、后端开发和自动化任务的首选语言之一。`dbnd-snowflake`是这样一个专门针对Snowflake数据库的Python...

    开源项目-bwmarrin-snowflake.zip

    开源项目-bwmarrin-snowflake.zip,bwmarrin/snowflake - A very simple package to generate or parse Twitter snowflake IDs

    PyPI 官网下载 | dbnd-snowflake-0.32.3.tar.gz

    《PyPI官网下载的dbnd-snowflake-0.32.3.tar.gz:Python库在分布式云原生环境中的应用》 PyPI(Python Package Index)是Python开发者的重要资源库,提供各种Python库的下载服务。本次我们将关注的是名为"dbnd-...

    Python库 | dagster-snowflake-0.8.2.tar.gz

    标题中的“Python库 | dagster-snowflake-0.8.2.tar.gz”指的是一个针对Python编程语言的特定库,名为“dagster-snowflake”,其版本为0.8.2,封装在tar.gz格式的压缩包文件中。这种文件格式通常用于在Linux和Unix...

    PyPI 官网下载 | dbnd-snowflake-0.32.7.tar.gz

    《PyPI官网下载 | dbnd-snowflake-0.32.7.tar.gz》 PyPI(Python Package Index)是Python社区广泛使用的软件仓库,它为开发者提供了分享和下载Python库的平台。在这个场景中,我们关注的是一个名为"dbnd-snowflake...

    PyPI 官网下载 | dagster-snowflake-0.11.5rc0.tar.gz

    标题中的“PyPI 官网下载 | dagster-snowflake-0.11.5rc0.tar.gz”表明这是一个从Python Package Index (PyPI) 官方网站获取的软件包,名为“dagster-snowflake”,版本号为0.11.5的候选发布版(release candidate)...

    donkeyid, php扩展,64位自增id生成器.zip

    1. **分布式一致性**:`donkeyid`可能采用了类似于Twitter的Snowflake算法,将64位ID分为多个部分,如时间戳、工作节点标识和序列号,确保在分布式环境中全局唯一。 2. **时间戳**:前几位用于存储当前时间戳,这样...

    snowflake-net-master_snowflake_算法_

    雪花算法是由Twitter开源的一种分布式ID生成算法,它能够为分布式系统中的每个实体生成全局唯一的、单调递增的64位整数ID。这种算法在大数据和分布式环境下广泛应用于主键生成,因为它解决了在分布式环境下的ID唯一...

    PyPI 官网下载 | dagster-snowflake-0.11.7rc13.tar.gz

    标题中的“PyPI 官网下载 | dagster-snowflake-0.11.7rc13.tar.gz”指的是在Python的包索引平台PyPI(Python Package Index)上下载的名为“dagster-snowflake”的软件包,版本为0.11.7的预发布版rc13(Release ...

    Twitter的 Snowflake 推特雪花算法JAVA实现方案

    Twitter的 Snowflake 推特雪花算法JAVA实现方案,用于自动生成id

    php-snowflake.tar.gz 随机生成ID,一直安装用的tar包

    Snowflake算法是一种分布式ID生成策略,最初由Twitter开源,它能生成具有时间戳、工作节点ID和序列号的64位无符号整数ID,确保ID的全局唯一性。 在描述中,我们看到一系列编译和安装PHP扩展的步骤,这通常适用于...

Global site tag (gtag.js) - Google Analytics