雪花算法 Snowflake & Sonyflake

标签: 雪花 算法 snowflake | 发表时间:2020-01-06 14:24 | 作者:li_peng
出处:https://juejin.im/welcome/backend

唯一ID算法 Snowflake相信大家都不墨生,他是Twitter公司提出来的算法。非常广泛的应用在各种业务系统里。也因为 Snowflake的灵活性和缺点,对他的改造层出不穷,比百度的 UidGenerator、美团的 Leaf、索尼的 Sonyflake等等。这篇帖子主要是讲一下原生的 Snowflake算法、缺点及改造方案,并分析索尼的 Sonyflake源码对原生 Snowflake的改造,

原生Snowflake

原生 Snowflake算法使用一个 64 bit的整型数据,根据当前的时间来生成ID。 原生 Snowflake结构如下:

  • 因为最高位是标识位,为1表示为负数,所以最高位不使用。
  • 41bit 保存时间戳,精确到毫秒。也就是说最大可使用的年限是69年。
  • 10bit 的机器位,能部属在1024台机器节点来生成ID。
  • 12bit 的序列号,一毫秒最大生成唯一ID的数量为4096个。

原生的 Snowflake算法是完全依赖于时间的,如果有时钟回拨的情况发生,会生成重复的ID,市场上的解决方案也是非常多的:

  • 最简单的方案,就是关闭生成唯一ID机器的时间同步。
  • 使用阿里云的的时间服务器进行同步,2017年1月1日的闰秒调整,阿里云服务器NTP系统24小时“消化”闰秒,完美解决了问题。
  • 如果发现有时钟回拨,时间很短比如 5毫秒,就等待,然后再生成。或者就直接报错,交给业务层去处理。
  • 可以找2bit位作为时钟回拨位,发现有时钟回拨就将回拨位加1,达到最大位后再从0开始进行循环。

个人比较推荐的是最后一个方案

找2bit位作为时钟回拨位,发现有时钟回拨就将回拨位加1,达到最大位后再从0开始进行循环。

比如下图这样,从机器位上,均出来2位做回拨位:

Sonyflake

Snowflake算法是相当灵活的,我们可以根据自己的业务需要,对63 bit的的各个部分进行增减。索尼公司的 Sonyflake对原生的 Snowflake进行改进,重新分配了各部分的bit位:

  • 39bit 来保存时间戳,与原生的 Snowflake不同的地方是, Sonyflake是以10毫秒为单位来保存时间的。这样的话,可以使用的年限为 174年Snowflake长太多了。
  const sonyflakeTimeUnit = 1e7 // nsec, i.e. 10 msec
func toSonyflakeTime(t time.Time) int64 {
return t.UTC().UnixNano() / sonyflakeTimeUnit
}
func currentElapsedTime(startTime int64) int64 {
return toSonyflakeTime(time.Now()) - startTime
}
复制代码
  • 8bit 做为序列号,每10毫最大生成256个,1秒最多生成25600个,比原生的 Snowflake少好多,如果感觉不够用,目前的解决方案是跑多个实例生成同一业务的ID来弥补。

  • 16bit 做为机器号,默认的是当前机器的私有IP的最后两位

  sf.machineID, err = lower16BitPrivateIP()
复制代码
  func lower16BitPrivateIP() (uint16, error) {
ip, err := privateIPv4()
if err != nil {
return 0, err
}
return uint16(ip[2])<<8 + uint16(ip[3]), nil
}
复制代码

对于时间回拨的问题 Sonyflake简单暴力,就是直接等待 :

  func (sf *Sonyflake) NextID() (uint64, error) {
const maskSequence = uint16(1<if sf.elapsedTime < current {
sf.elapsedTime = current
sf.sequence = 0
} else { // sf.elapsedTime >= current
sf.sequence = (sf.sequence + 1) & maskSequence
if sf.sequence == 0 {
sf.elapsedTime++
overtime := sf.elapsedTime - current
time.Sleep(sleepTime((overtime)))
}
}
return sf.toID()
}
复制代码

相关 [雪花 算法 snowflake] 推荐:

雪花算法 Snowflake & Sonyflake

- - 掘金后端
唯一ID算法 Snowflake相信大家都不墨生,他是Twitter公司提出来的算法. 非常广泛的应用在各种业务系统里. 也因为 Snowflake的灵活性和缺点,对他的改造层出不穷,比百度的 UidGenerator、美团的 Leaf、索尼的 Sonyflake等等. 这篇帖子主要是讲一下原生的 Snowflake算法、缺点及改造方案,并分析索尼的 Sonyflake源码对原生 Snowflake的改造,.

Twitter的分布式自增ID算法Snowflake

- - 企业架构 - ITeye博客
Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的id,这些id还需要一些大致的顺序(方便客户端排序),并且在分布式系统中不同机器产生的id必须不同. Snowflake算法核心. 把 时间戳, 工作机器id, 序列号组合在一起.

SnowFlake 分布式ID生成算法Java实现

- - ITeye博客
SnowFlake 分布式ID生成Java实现. SnowFlake不依赖第三方介质,不像基于ZK,Redis等,每次用完一个区间还得通过网络去获取下一个区间,效率较低,基于SnowFlake的分布式ID生成是目前我见过的最快的. SnowFlake生成的是一个64位的数字,其中42位时间戳,接下来10位是自定义的数,其作用就是区分集群中的所有机器,最后12位是毫秒内序列,集群内每个机器能够在1毫秒内生成2^12 - 1个ID.

缓存算法

- lostsnow - 小彰
没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率. 我是LRU缓存算法,我把最近最少使用的缓存对象给踢走. 我总是需要去了解在什么时候,用了哪个缓存对象.

BFPRT算法

- zii - 小彰
BFPRT算法的作者是5位真正的大牛(Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan),该算法入选了在StackExchange上进行的当今世界十大经典算法,而算法的简单和巧妙颇有我们需要借鉴学习之处. BFPRT解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度.

贪心算法

- Shan - 博客园-首页原创精华区
顾名思义,贪心算法总是作出在当前看来最好的选择. 也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择. 当然,希望贪心算法得到的最终结果也是整体最优的. 虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解. 如单源最短路经问题,最小生成树问题等.

缓存算法

- 成 - FeedzShare
来自: 小彰 - FeedzShare  . 发布时间:2011年09月25日,  已有 2 人推荐. 没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率.

K-Means 算法

- - 酷壳 - CoolShell.cn
最近在学习一些数据挖掘的算法,看到了这个算法,也许这个算法对你来说很简单,但对我来说,我是一个初学者,我在网上翻看了很多资料,发现中文社区没有把这个问题讲得很全面很清楚的文章,所以,把我的学习笔记记录下来,分享给大家. k-Means 算法是一种  cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法.

查找算法:

- - CSDN博客推荐文章
从数组的第一个元素开始查找,并将其与查找值比较,如果相等则停止,否则继续下一个元素查找,直到找到匹配值. 注意:要求被查找的数组中的元素是无序的、随机的. 比如,对一个整型数组的线性查找代码:. // 遍历整个数组,并分别将每个遍历元素与查找值对比. 要查找的值在数组的第一个位置. 也就是说只需比较一次就可达到目的,因此最佳情况的大O表达式为:O(1).