雪花算法Snowflake&Sonyflake

EzekielEdwiin 发布于14天前
0 条问题

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

原生Snowflake

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

雪花算法 Snowflake & Sonyflake

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

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

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

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

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

雪花算法 Snowflake & Sonyflake

Sonyflake

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

雪花算法 Snowflake & Sonyflake

  • 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<<BitLenSequence - 1)
	sf.mutex.Lock()
	defer sf.mutex.Unlock()
	current := currentElapsedTime(sf.startTime)
	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 & Sonyflake

  • greenbird
  • heavytiger
需要 登录 后回复方可回复, 如果你还没有账号你可以 注册 一个帐号。