改造Twitter的雪花算法(snowflake)[缩短位数]

aries 发表于 2021-04-21 60 次浏览

众所周知, 在分布式全局唯一ID生成器方案中, 由Twitter开源的SnowFlake算法,因其有性能高, 代码简单, 不依赖第三方服务, 无需独立部署服务等优点, 在一般情况下已经能满足绝大多数系统的需求
但是,它有一个对我来说最大的缺点,就是:使用原生的雪花算法其默认生成的是64bit长整型,有18位
如果以ID和前端的JS进行交互时会出现精度丢失(最后两位数字变成00) 而导致最终系统报错: 找不到ID; 废话, 最后两位都变成00了那肯定找不到啊! 究其原因是因为JS的Number类型精度最高只有53bit, 导致JS其最大安全值只有2^53 = ‭9007199254740992 算法生成的18位数字妥妥的超标了啊;
所以我们要缩短它!
缩短的方法就是

  1. 节点标识减小为5bit 最大可以有2^5=32个节点
  2. 序列数位长减小为6bit 单节点最高可支持2^6=64个ID/ms

实现代码如下:

package snowflake

import (
	"errors"
	"sync"
	"time"
)

const (
	workerBits   uint8 = 6                       // 每台机器(节点)的ID位数
	numberBits   uint8 = 6                       // 表示每个集群下的每个节点,1毫秒内可生成的id序号的二进制位数
	workerMax    int64 = -1 ^ (-1 << workerBits) // 节点ID的最大值,用于防止溢出
	numberMax    int64 = -1 ^ (-1 << numberBits) // 同上,用来表示生成id序号的最大值
	timeOffset         = workerBits + numberBits // 时间戳向左的偏移量
	workerOffset       = numberBits              // 节点ID向左的偏移量
	// 41位字节作为时间戳数值的话 大约68年就会用完
	// 假如你2010年1月1日开始开发系统 如果不减去2010年1月1日的时间戳 那么白白浪费40年的时间戳啊!
	// 这个一旦定义且开始生成ID后千万不要改了 不然可能会生成相同的ID
	period int64 = 1525705533000 // 这个是我在写period这个变量时的时间戳(毫秒)
)

var singleton sync.Once
var instance *Worker

func GetInstance(workerId int64) *Worker {
	singleton.Do(func() {
		instance, _ = NewWorker(workerId)
	})
	return instance
}

// Worker 定义一个worker工作节点所需要的基本参数
type Worker struct {
	mu        sync.Mutex // 添加互斥锁 确保并发安全
	timestamp int64      // 记录时间戳
	workerId  int64      // 该节点的ID
	number    int64      // 当前毫秒已经生成的id序列号(从0开始累加) 1毫秒内最多生成4096个ID
}

// NewWorker 实例化一个工作节点
func NewWorker(workerId int64) (*Worker, error) {
	// 要先检测workerId是否在上面定义的范围内
	if workerId < 0 || workerId > workerMax {
		return nil, errors.New("worker id 无效")
	}
	// 生成一个新节点
	return &Worker{
		timestamp: 0,
		workerId:  workerId,
		number:    0,
	}, nil
}

// GetId 接下来我们开始生成id
// 生成方法一定要挂载在某个worker下,这样逻辑会比较清晰 指定某个节点生成id
func (w *Worker) GetId() int64 {
	// 获取id最关键的一点 加锁 加锁 加锁
	w.mu.Lock()
	defer w.mu.Unlock() // 生成完成后记得 解锁 解锁 解锁

	// 获取生成时的时间戳
	now := time.Now().UnixNano() / 1e6 // 纳秒转毫秒
	if w.timestamp == now {
		w.number++

		// 这里要判断,当前工作节点是否在1毫秒内已经生成numberMax个ID
		if w.number > numberMax {
			// 如果当前工作节点在1毫秒内生成的ID已经超过上限 需要等待1毫秒再继续生成
			for now <= w.timestamp {
				now = time.Now().UnixNano() / 1e6
			}
		}
	} else {
		// 如果当前时间与工作节点上一次生成ID的时间不一致 则需要重置工作节点生成ID的序号
		w.number = 0
		w.timestamp = now // 将机器上一次生成ID的时间更新为当前时间
	}

	// 第一段 now - period 为该算法目前已经奔跑了xxx毫秒
	// 如果在程序跑了一段时间修改了period这个值 可能会导致生成相同的ID
	ID := int64((now-period)<<timeOffset | (w.workerId << workerOffset) | (w.number))
	return ID
}

调用

fmt.Println(snowflake.GetInstance(0).GetId())

输出id为:382097802702848

0条评论

如需评论,请填写表单。
换一个

记住我的信息