雪花算法原理讲解

雪花算法（Snowflake）是一种由 Twitter 开发的分布式唯一 ID 生成算法。它解决了在分布式系统中生成唯一标识符的问题，具有高效、顺序性、分布式可扩展等优点。雪花算法生成的 ID 是一个 64 位的整数（Golang中的int64类型）。

雪花算法的组成

雪花算法组成

符号位（1位）：最高位，始终为 0，用于确保生成的 ID 是正数。
时间戳（41位）：表示毫秒值时间戳，41 位长度可以表示约 69 年的时间范围（$2^{41}$ 毫秒 ≈ 69 年）。这个时间可以从项目上线时间开始计算，保证了项目可以稳定运行69年。
机器码（10位）：用于标识不同机器，10位机器码最多可以支持 1024 台机器。
序列号（12位）：在同一毫秒内生成的多个 ID 的区分符。12 位长度的序列号可以在同一毫秒内生成最多 4096 个不同的 ID。

雪花算法的优点

全局唯一性：通过时间戳、数据中心 ID、机器 ID 和序列号的组合，保证了每个生成的 ID 都是唯一的。
高效：生成 ID 的过程是本地操作，依赖于机器的时钟，所以生成速度非常快。
有序性：由于时间戳占据了较高的位数，生成的 ID 大致上是按照时间递增的。

雪花算法的缺点

时钟依赖：如果机器的时钟发生回拨，会导致 ID 冲突或无法生成 ID 的问题。
固定位长度：每个部分的位数是固定的，无法动态调整。例如，当需要更多的数据中心或机器时，位数的限制可能成为瓶颈。

改进雪花算法

弱依赖时间戳

我们可以通过弱依赖时间戳，解决时钟回拨问题。操作如下：

当启动程序时，记录此时的时间毫秒值，并将序列号设置为0
当需要生成id时，根据此时的时间戳、机器码、序列号生成id。如果序列号达到最大值4096，就将时间戳增加1，将序列号设置为0；否则将序列号增加1

这种方式只有在程序启动时才会依赖操作系统的时间，只有恰好在程序启动时发生小时级的时钟回拨，才会出现时钟回拨问题，而大多数时钟回拨问题都是毫秒级的。因此，这种方式可以在一定程度上解决时钟回拨问题，只会有极小概率出现id重复。

Golang代码

源码位置：Golang实现雪花算法
定义 Worker 结构体，里面包含生成雪花id的各种参数和一个互斥锁。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


type Worker struct {
	mtx             sync.Mutex
	timestamp       int64 // 生成id的时间戳，可以指定起始值
	timestampMax    int64 // 时间戳最大值
	timestampOffset uint8 // 时间戳的偏移量，方便进行位运算
	machineId       int64 // 机器码
	machineIdOffset uint8 // 机器码偏移量
	seq             int64 // 序列号
	seqMax          int64 // 序列号最大值
	seqOffset       uint8 // 偏移量
}

创建一个雪花算法的工作节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


func NewWorker(c SnowFlakeConfig, machineId int64) (*Worker, error) {
	// 检查配置
	sumBits := c.TimestampBits + c.MachineIdBits + c.SeqBits
	if sumBits != 63 {
		return nil, BitsSumError
	}

	// 检查机器码
	var machineMax int64 = (1 << c.MachineIdBits) - 1
	if machineId < 0 || machineId > machineMax {
		return nil, MachineIdIllegal
	}

	return &Worker{
		mtx:             sync.Mutex{},
        // 时间戳，为程序启动时的时间毫秒值-自定义的起始时间
		timestamp:       time.Now().UnixMilli() - c.StartTimestamp,
		timestampMax:    (1 << c.TimestampBits) - 1,
		timestampOffset: c.SeqBits + c.MachineIdBits,
		machineId:       machineId,
		machineIdOffset: c.SeqBits,
		seq:             0,
		seqMax:          (1 << c.SeqBits) - 1,
		seqOffset:       0,
	}, nil
}

生成id

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


// 私有方法，根据参数生成id
func (w *Worker) getId() (int64, error) {
	// 先校验参数
	if w.timestamp < 0 || w.timestamp > w.timestampMax {
		return 0, TimestampIllegal
	}
	if w.seq < 0 || w.seq > w.seqMax {
		return 0, SeqIllegal
	}

	// 生成id
	var id int64
	id |= w.timestamp << w.timestampOffset
	id |= w.machineId << w.machineIdOffset
	id |= w.seq << w.seqOffset

	return id, nil
}

// GenerateId 生成雪花id
func (w *Worker) GenerateId() (int64, error) {
	// 加锁
	w.mtx.Lock()
	defer w.mtx.Unlock()

	// 生成id
	id, err := w.getId()
	if err != nil {
		return 0, err
	}

	// 更新参数
	if w.seq == w.seqMax {
		w.seq = 0
		w.timestamp++
	} else {
		w.seq++
	}

	return id, err
}