Snowflake ID 算法

背景

假设我们有一个分布式系统，系统中需要维护全局 id 字段，我们可以把它认为是唯一的标识，不能够重复出现，那么问题来了，我们应该如何生成这样的 id 呢？

其实很容易想到的一种解决方式就是使用 Redis 的键值对了，每次更新的时候直接调用 incr，生成的 id 也是唯一的，还有一种方式就是使用 MySQL 或者其他的数据库，因为我们知道 MySQL 中可以生成自增主键，使用这个主键作为一个分布式 id 也是可行的。

但是上面的这两种方式效率不会特别高，并且依赖于第三方，我们如果想要更高效的生成分布式 id，那么最好的方式就是尽量本地生成，不需要和其他节点进行协商，但是有一个问题出现了，如何保证 id 不重复？，我们可以使用 Snowflake 算法来解决该问题。

概念

Snowflake 可用于在分布式系统中生成唯一的 id，由 Twitter 提出，目前存在很多不同的版本，但是基本的思想是一致的，只不过不同版本不同结构采用的位数不一致。

Snowflakes 使用 64 比特， 但是只有 63 位被使用，第一个比特位为符号位，大体结构如下：

timestamp 占 41 bits，是生成 ID 的时间戳，也可以是相对某一个特定时间的时间戳差，machine id 为分布式系统每一个机器分配到的 id 号，10 bits 表示最多 1024 台机器，sequence number 表示序列号，因为同一个时间戳可能分配多个 id。

ID 生成

每一台机器的 machine id 都是事先配置好的，可以由数据中心 id 和数据中心的机器 id 组成，直接可以获取到。当我们需要生成一个 id 的时候，首先我们需要获取当前的时间戳，判断是否和上一次的时间戳一致，如果说和上一次的时间戳一致，那么我们应该增加序列号，然后通过移位操作构造对应的一个 64 bits 的 id 号返回。 如果说当前的时间戳与上一次的不同，那么我们直接修改时间戳，然后序列号取零，进行拼接即可。

代码实现

算法的实现挺简单的，下面给出核心代码：

func (s *Snowflake) GetID() int64 {
	// 首先获取当前的时间戳
	timestamp := time.Now().UnixMilli()
	// 相同的时间戳序列号+1
	if timestamp == s.LastTimestamp {
		s.Sequence = (s.Sequence + 1) & sequenceMask
		// 重新绕了一圈
		// 同一个时间戳里面生成了很多 id
		if s.Sequence == 0 {
			for timestamp <= s.LastTimestamp {
				timestamp = time.Now().UnixMilli()
			}
		}
	} else {
		s.Sequence = 0
	}
	// 重新设置
	s.LastTimestamp = timestamp

	// 进行拼接
	return (timestamp-epoch)<<timestampShift | (s.DatacenterID << datacenterIDShift) | (s.WorkerID << workerIDShift) | s.Sequence
}

测试

写了一个很简单的基准测试：

func BenchmarkGetID(b *testing.B) {
	s := New(10, 10)
	for i := 0; i < b.N; i++ {
		s.GetID()
	}
}

下面是它的结果，表现还不错吧，这样算起来，假设每次需要 250 ns，那么 1s 也可以生成 4,000,000 个不同的 id 。

goos: windows
goarch: amd64
pkg: snowflake
cpu: Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz
BenchmarkGetID-8         4897538               246.0 ns/op
PASS
ok      snowflake       2.069s

Twitter 其实也提供了自己的 Scala 实现方式，具体的可以参见 GitHub， 本文的实现方式可以参见 我的仓库。