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算法的好处:
# 无需链接数据库或者redis,超高性能。
snowflake算法的弊端:
# 每毫秒只能生成4096个id。随着cpu不断的进步,每毫秒4096个id将不能满足。
# 只能使用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会重复)。