likes
comments
collection
share

Go：雪花算法实现详解

作者站长头像
站长
· 阅读数 128

引言

在高并发系统中，生成唯一的、时间有序的ID是常见需求。Twitter的Snowflake算法是一个经典的解决方案。本文将详细介绍由bwmarrin/snowflake Go包实现的雪花算法，并分析其核心代码。

Go：雪花算法实现详解

什么是雪花算法

雪花算法是一种分布式唯一ID生成算法，它生成的ID是64位的整型数，结构如下：

  • 符号位 (1 bit)：永远为0。
  • 时间戳 (41 bits)：记录时间戳，与生成时间有关。
  • 数据中心ID (5 bits)：表示数据中心。
  • 机器ID (5 bits)：表示机器或节点。
  • 序列号 (12 bits)：记录同一毫秒内的生成顺序。

代码实现分析

在bwmarrin/snowflake包中，snowflake.go实现了核心功能。以下是主要功能的详细讲解：

Go：雪花算法实现详解

初始化

NewNode函数是bwmarrin/snowflake包中创建新的Node实例的构造函数。Node负责生成唯一的ID。

函数定义

func NewNode(node int64) (*Node, error) {
    // 重新计算以防设置了自定义的NodeBits或StepBits
    // DEPRECATED: 以下代码块将在未来版本中移除。
    mu.Lock()
    nodeMax = -1 ^ (-1 << NodeBits)
    nodeMask = nodeMax << StepBits
    stepMask = -1 ^ (-1 << StepBits)
    timeShift = NodeBits + StepBits
    nodeShift = StepBits
    mu.Unlock()
    
    n := Node{}
    n.node = node
    n.nodeMax = -1 ^ (-1 << NodeBits)
    n.nodeMask = n.nodeMax << StepBits
    n.stepMask = -1 ^ (-1 << StepBits)
    n.timeShift = NodeBits + StepBits
    n.nodeShift = StepBits
    
    if n.node < 0 || n.node > n.nodeMax {
        return nil, errors.New("Node number must be between 0 and " + strconv.FormatInt(n.nodeMax, 10))
    }
    
    var curTime = time.Now()
    // 添加time.Duration以确保使用单调时钟（如果可用）
    n.epoch = curTime.Add(time.Unix(Epoch/1000, (Epoch%1000)*1000000).Sub(curTime))
    
    return &n, nil
}

结构体定义

type Node struct {
    mu        sync.Mutex
    epoch     time.Time
    time      int64
    node      int64
    step      int64
    nodeMax   int64
    nodeMask  int64
    stepMask  int64
    timeShift uint8
    nodeShift uint8
}

解析

初始化及全局参数设置

mu.Lock()
nodeMax = -1 ^ (-1 << NodeBits)
nodeMask = nodeMax << StepBits
stepMask = -1 ^ (-1 << StepBits)
timeShift = NodeBits + StepBits
nodeShift = StepBits
mu.Unlock()
  • 锁定和解锁：使用全局互斥锁mu保护共享变量。
  • 计算nodeMax：nodeMax是节点ID的最大值，公式为-1 ^ (-1 << NodeBits)。
  • 计算nodeMask：nodeMask用于位操作，公式为nodeMax << StepBits。
  • 计算stepMask：stepMask用于限制序列号范围，公式为-1 ^ (-1 << StepBits)。
  • 设置移位量：
    • timeShift用于时间戳左移的位数，等于NodeBits + StepBits。
    • nodeShift用于节点ID左移的位数，等于StepBits。

Node实例的初始化

n := Node{}
n.node = node
n.nodeMax = -1 ^ (-1 << NodeBits)
n.nodeMask = n.nodeMax << StepBits
n.stepMask = -1 ^ (-1 << StepBits)
n.timeShift = NodeBits + StepBits
n.nodeShift = StepBits
  • 创建新实例：声明并初始化Node结构体n。
  • 设置节点ID：将输入参数node赋值给n.node。
  • 重新计算和设置：
    • nodeMax：节点ID的最大值。
    • nodeMask：节点掩码，用于位操作。
    • stepMask：序列号掩码，用于限制序列号范围。
    • timeShift和nodeShift：与全局变量相同的移位量。

节点ID有效性检查

if n.node < 0 || n.node > n.nodeMax {
    return nil, errors.New("Node number must be between 0 and " + strconv.FormatInt(n.nodeMax, 10))
}
  • 范围检查：确保节点ID在0到nodeMax之间。
  • 错误处理：如果不在范围内，返回错误信息。

时间戳初始化

var curTime = time.Now()
// 添加time.Duration以确保使用单调时钟（如果可用）
n.epoch = curTime.Add(time.Unix(Epoch/1000, (Epoch%1000)*1000000).Sub(curTime))
  • 获取当前时间：使用time.Now()获取当前系统时间。
  • 计算初始时间戳epoch：
    • Epoch转换为时间对象：使用time.Unix将Epoch转换为时间对象。
    • 调整epoch：确保使用单调时钟（提高时间戳生成的稳定性和准确性）。

单调时钟（monotonic clock）是一种 只增不减 的时间计数器。它不受系统时间调整（例如闰秒）的影响，始终以恒定的速率递增。

闰秒是偶尔添加到协调世界时（UTC）中的一秒，以使其与地球自转的平均速率保持同步。地球的自转速率并不是恒定的，而是会受到潮汐、大气和地质过程等因素的影响。随着时间的推移，UTC与地球自转的平均速率之间会出现偏差。为了消除这种偏差，国际地球自转服务（IERS）会定期评估地球的自转速率，并在必要时插入闰秒。 自1972年以来，已经插入了29个闰秒。最近一次闰秒的插入是在2022年6月30日

返回实例
return &n, nil
  • 返回Node指针：成功创建Node实例后，返回指针和nil错误。

NewNode函数通过精心设计的初始化过程和参数设置，确保了Node实例的有效性和稳定性，为分布式ID的生成提供了坚实基础。

ID生成

Generate函数生成唯一ID的核心函数。它在高并发环境下生成唯一且时间有序的ID。

函数定义

func (n *Node) Generate() ID {
	n.mu.Lock()
	now := time.Since(n.epoch).Nanoseconds() / 1000000
	if now == n.time {
		n.step = (n.step + 1) & n.stepMask

		if n.step == 0 {
			for now <= n.time {
				now = time.Since(n.epoch).Nanoseconds() / 1000000
			}
		}
	} else {
		n.step = 0
	}
	n.time = now
	r := ID((now)<<n.timeShift |
		(n.node << n.nodeShift) |
		(n.step),
	)
	n.mu.Unlock()
	return r
}

解析

锁定节点

n.mu.Lock()
  • 锁定节点：使用互斥锁n.mu确保ID生成过程的线程安全，防止并发访问导致数据不一致。

获取当前时间戳

now := time.Since(n.epoch).Nanoseconds() / 1000000
  • 计算当前时间戳：
    • 时间差：使用time.Since(n.epoch)计算当前时间与epoch之间的差值。
    • 纳秒转换为毫秒：将纳秒转换为毫秒。

序列号处理

if now == n.time {
	n.step = (n.step + 1) & n.stepMask

	if n.step == 0 {
		for now <= n.time {
			now = time.Since(n.epoch).Nanoseconds() / 1000000
		}
	}
} else {
	n.step = 0
}
  • 同一时间戳的处理：
    • 序列号增加：n.step = (n.step + 1) & n.stepMask，通过与stepMask进行与操作，保证序列号在范围内循环。
    • 序列号溢出处理：如果n.step等于0，表示当前毫秒内的序列号已用尽，进入循环等待下一个毫秒。
  • 不同时间戳的处理：
    • 重置序列号：n.step = 0。

更新时间戳

n.time = now
  • 更新节点时间戳：将当前时间戳now赋值给n.time。

生成ID

r := ID((now)<<n.timeShift |
	(n.node << n.nodeShift) |
	(n.step),
)

  • ID组成部分：

    • 时间戳部分：(now)<<n.timeShift，将当前时间戳左移timeShift位。
    • 节点ID部分：(n.node << n.nodeShift)，将节点ID左移nodeShift位。
    • 序列号部分：n.step。

  • ID拼接：通过按位或操作，将时间戳、节点ID和序列号组合成64位的ID。

解锁节点

n.mu.Unlock()
  • 解锁节点：释放互斥锁n.mu，允许其他线程访问节点。

返回ID

return r
  • 返回生成的ID：返回最终生成的唯一ID。

代码流程图

Go：雪花算法实现详解

Generate函数通过使用互斥锁和精确的时间戳计算，确保在高并发环境下生成唯一且有序的ID。它通过灵活的位操作将时间戳、节点ID和序列号组合成一个64位的唯一ID，确保在分布式系统中能够高效生成ID。

总结

bwmarrin/snowflake包提供了高效的分布式唯一ID生成方案，适用于需要高并发ID生成的系统。通过清晰的代码结构和详细的注释，开发者可以轻松理解和扩展此算法。

参考

转载自:https://juejin.cn/post/7367175713894907956
评论
请登录