Twitter分布式自增ID算法snowflake原理解析

存储架构 2018-05-25 阅读原文

以JAVA为例

Twitter分布式自增ID算法snowflake,生成的是Long类型的id,一个Long类型占8个字节,每个字节占8比特,也就是说一个Long类型占64个比特(0和1)。

那么一个Long类型的64个比特,

twitter是这样分配的: 正数位(占1比特)+时间戳(占41比特)+机械id(占5比特)+数据中心(占5比特)+自增值(占12比特)
,总共64比特组成的一个Long类型。

时间戳(占41个比特):毫秒数,大约可以使使用69年

机械id(占5个比特):即2的5次方等于32个机器

数据中心id(占5个比特):即2的5次方等于32个数据中心

自增值(占12比特):2的12次方等于4096。也就是说每毫秒最多可以生成4096个id,如果cpu生产id的速度大于每毫秒4096个,那么需要使线程进行等待到下一毫秒,重新计数获取自增值。

snowflake算法的好处:

# 生成的id是一个数字的Long类型

# 无需链接数据库或者redis,超高性能。

snowflake算法的弊端:

# 每毫秒只能生成4096个id。随着cpu不断的进步,每毫秒4096个id将不能满足。可以不用担心,即便cpu性能超过了这个值,那么只需等待到下一个毫秒

# 只能使用69年

#每毫秒重新计数,空闲时间会浪费很多id空间。

#系统时间不可回退,回退将会导致id重复。另:系统时间可以前进,不受影响。

以上就是对snowflake的一些总结。

snowflake算法改进1:

针对空闲时间会浪费很多id空间,改进:咱们可以把时间戳的单位改为秒。使用31个比特的时间戳(秒),节约了10个比特,2的31次方等于2,147,483,648秒,约为69年。然后我们把节约出来的10个字节交给自增值,此时自增值(12+10=22比特),即2的22次方等于4,194,304。

改进前的snowflake算法结构为: 正数位(占1比特)+时间戳(占41比特)+机械id(占5比特)+数据中心(占5比特)+自增值(占12比特)

改进后的snowflake算法结构为:
正数位(占1比特)+时间戳(占31比特)+机械id(占5比特)+数据中心(占5比特)+自增值(占22比特)

改进后的优点:

# 避免空闲时间会浪费很多id空间,支持每秒生成419万个id。

改进后的snowflake算法同样是使用69年,时间戳以秒为单位,每秒支持约419万个id生成。此时避免使用毫秒时间戳的浪费id空间的弊端。当然还可以继续改进,比如:使用分钟为单位的时间戳(要注意的是:使用分钟为单位的时间戳,如果服务器宕机,那么你需要等待1分钟后才能启动服务器,否则将会导致自增值归零重新计数,当前分钟内生成的id和宕机时生成的id会重复)。

博客园-原创精华区

责编内容by:博客园-原创精华区阅读原文】。感谢您的支持!

您可能感兴趣的

分布式软件定义存储的春天到来吗?看XSKY如何出招!... 传统存储或者说磁盘阵列就面临着被颠覆的风险,原因很简单,磁盘阵列的成本居高不下,扩展能力有限,难以满足爆炸式数据增长的需求。磁盘阵列所短,恰恰是分布式的软件定义存储所长,凭借弹性、敏捷性和易管理等特长,从ServerSAN、软件定义存储(SDS),到超融合(HCI)、对象存储,以x86标准服务...
以Dapper、Zipkin和LightStep PM为例阐述分布式跟踪的过去、现在和未来... 核心要点 在观测分布式系统和微服务时,分布式跟踪已经成为一个越来越重要的组件。现在有一些流行的开源标准和框架,比如OpenTracing API和OpenZipkin; 分布式跟踪的基本理念是非常简单直接的:在系统中,特定请求的转折点必须要识别出来并且要检测。所有的...
推荐:微服务详细入坑指南 概念:微服务就是一些可独立运行、可协同工作的小的服务。微服务是现在特别流行的服务,微服务的字面意思是大家都很好理解,就是将系统拆分成很多小的独立系统,每个系统我们看成一个服务,从存储,缓存,部署相对独立。通过服务的小型化、原子化以及分布式架构的弹性伸缩和高可用性,可以实现业务之间的松耦合、业务的灵活...
科普 | 区块链核心算法之拜占庭容错算法... 在上两篇文章中有介绍到拜占庭将军问题,于战争时,拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军,因为唯有达成一致的行动才能获致胜利。将军中若存在叛徒,叛徒可以采取行动以欺骗某些将军进行进攻行动,或致使他们无法做出决定,缺乏一致行动的结果则将注定战事的失利。 什么是拜占庭容错...
A Hitchhiker’s Guide to Consensus Algorithms A Hitchhiker’s Guide to Consensus Algorithms A quick classification of cryptocurrency consensus types Don’t Panic. Behind every great cryptoc...