Skip to content

Latest commit

 

History

History
80 lines (62 loc) · 5.22 KB

README.md

File metadata and controls

80 lines (62 loc) · 5.22 KB

雪花算法

参考了https://github.com/bwmarrin/snowflake的雪花算法实现,此算法是标准的twitter雪花算法。 此仓库作者可能想将一些雪花算法的meta信息存放在Node结构体中,但当Node产生出ID后, 从ID本身其实并不能倒推原来雪花算法中的各个字段的meta信息,其本质问题是ID本身就是64位整数, 能存储的信息实在有限,如果需要将一些算法相关的信息存放在ID中,本身又会缩短ID生成的有效信息范围。 按照现有算法,在每个节点上每毫秒可以产生4096个ID,总共可以切分1024个节点,如果在ID中带上节点/步长相关的信息, 那要么会让切分节点数量变少,要么让每毫秒产生的ID数变少,总之都会让产生ID的效率变低。

主要的改动

  • 去掉了原来仓库中一些不那么常用的函数
  • 对雪花算法增加了一定程度的配置灵活度:
    1. 雪花算法中的创世时间可以配置,举例来说,如果在2022年启动一个项目,可以把创世时间设为2022年, 这样会让雪花算法ID的生命周期更长。
    2. 雪花算法中节点数量可以配置成支持1024/512/256个节点的三种节点模式,标准是支持1024个节点, 如果不需要那么多节点,可以配置成512和256个节点,这样的好处是将节约下来的bit供毫秒时间戳使用, 让ID的生命周期更长久。
    3. 标准雪花算法中,步长放置在最低位,节点信息居中。这里增加了配置选项,可以让节点信息放置在最低位,步长信息居中。
    4. 添加了一对函数,CnStyle/FromChStyle,这对函数可能在中国式系统开发中有用。这两个函数主要功能是, CnStyle会将雪花算法产生的ID转换成YYYYMMDDHHMMSSMMMXXXXXXX这样总长度为24的形式, YYYY(年,4位)MM(月,2位)DD(日,2位)HH(小时,2位)MM(分,2位)SS(秒,2位)MMM(毫秒,3位)XXXXXXX(节点和步长组成的整数,7位), 每个字段都会在位数不够的情况下,补足高位的0,如果举例来说,如果月份为5,则会补为05。 FromChStyle则会将这样带日期信息的字符串转化成ID本身。

特别注意:关于雪花算法配置函数Setup

缺省配置能应付绝大多数场景,如果在某种情况下,需要修改雪花算法配置,这些配置项主要是:

  1. 节点的位数可以配置为10/9/8,即分别支持1024/512/256个节点,节点少则意味着ID的生命周期更长。比如1024个节点,ID可用69年,512个节点则可以 让ID可用138年。
  2. 节点信息可以放置在最低位,此时步长信息会居中。

如果在某种场景下修改了雪花算法的配置,务必需要记住的是,与此相关的场景都需要使用此配置。因为雪花算法中,节点位数与其放置的位置都不会存在ID中, 换句话说,相关的代码实际上就是雪花算法配置的元信息,一旦投入了某种配置,就不要再修改它了。

雪花算法的回退问题

以前我写了一篇《时间同步次生问题与定时器》的文章,其中支持雪花算法可能产生单调不递增的ID,在时间回退的情况下。现在看来当时我的结论是错误的, 相关的代码已经清楚表明,雪花算法中时间的计算用的是单调时间计算。

    //在NewNode时使用了单调时间
    var curTime = time.Now()
    // add time.Duration to curTime to make sure we use the monotonic clock if available
    n.epoch = curTime.Add(time.Unix(_epoch/SDivMs, (_epoch%SDivMs)*MsDivNs).Sub(curTime))
    //在生成ID时同样使用了单调时间计算,而不是简单粗暴把时间戳进行加减运算
    var now = time.Since(n.epoch).Nanoseconds() / MsDivNs

monotonic计时的精度问题

monotonic精度取决于计算机的时钟硬件,短期计时没有问题,但如果运行很长时间,则误差会放大,有时我们需要制造雪花ID,但同时此ID又能反映出时间,如果用monotonic的方式,则会导致如果想从ID中倒推时间会有很大的误差。

两种不同的雪花算法

  • 都实现了接口
//Node : generate id interface
type Node interface {
	Generate() int64
}
  • 使用monotonic计时的雪花算法,此雪花算法不会有ID回退问题,但如果用它产生的ID来推导时间的话,会有精度问题。
var node, err = NewMonoNode(your_spec_node_id)
//...
  • 推荐的改良雪花算法,产生ID后会记录最近一次的毫秒时间和step,如果下次获取的绝对时间小于或等于记录的毫秒时间(小于意味着时间回退),则先增加步数,如果步数溢出,再增加毫秒时间值。这样做的好处是,保证ID单调递增的同时,用绝对时间来保证产生的ID在推导时间的时候不会有太大的偏差,时间同步服务启动的情况下,回拨时间最多也就在100毫秒以内。
    与NewMonoNode不一样的是,此方法支持传入一个最近最大的ID来保证服务重启时刚好遇到时间回调导致产生ID与重启前服务产生的ID不单调增长。此id常常为启动时通过读取数据库中的某个最大ID值。
var node, err = NewNode(your_spec_node_id, last_id)
//...