snowflake算法时钟回拨问题: 基于逻辑时钟解决方案

问题

1. 时间的生成完全依赖于本地时钟, 在开启NTP协议的情况下, 可能出现时钟回拨现象, 此时服务不可用
2. 为了防止ID被顺序破解, 通常自增值不会 递增1, 可以更加随机的添加递增值

解决方案

我们需要知道, 时钟回拨问题是一个对于分布式服务影响非常大的环节. 我们需要做的事情就是尽可能的削弱时钟回拨带来的影响.

可是, 怎么削弱?

只要时钟不回拨就能够解决这个问题, 或者说只要逻辑时钟不回拨就不会出现这个问题

func (worker *idWorker) Generate() (value int64) {
	mutex.Lock()
	defer mutex.Unlock()
	t := time.Now().UnixMilli()

	// 如果当前时间比上一次时间大, 则sequence归零, 直接生成
	if t > worker.lastTimestamp {
		// fmt.Printf("lastTimestamp: %d\n", worker.lastTimestamp)
		worker.sequence = 0
		goto Generate
	}
	// 设置当前时间至少 >= 上一次时间
	t = worker.lastTimestamp
	worker.sequence += 1
	// fmt.Printf("sequence: %d\n", worker.sequence)
	// 如果超出了本次序列的最大值，借用后一ms的时间, 直接生成
	if worker.sequence >= seqMax {
		worker.sequence = 0
		t = worker.lastTimestamp + 1
		goto Generate
	}

Generate:
	worker.lastTimestamp = t
	// 时间左移 12+5+5, // 机器码ID左移10位，中间的12位是machine和dc, // 最后10位 是序列号
	value = worker.lastTimestamp<<22 | (worker.machineAndDC << 10) | worker.sequence
	return
}

在这个实现方案里, 表示序列号的用了 10bit 约 1024 个

在每次序列号将耗尽时, 不再等待时钟追回, 而是直接租借下一个 ms 的配额, 因为在大多数的场景下, 没有业务会需要 10Wqps 的发号器, 所以我们可以认为, 只要时间足够, 逻辑时钟 ​会最终追回 物理时钟​

效果

唯一性

测试思路

以 $并发度 * 连续请求次数$ 来测试是否能够满足唯一性

经测试, 在并发度为40000​, 连续请求次数 10​的环境下, 可以充分保证其唯一性

但需要注意的是, ms配额使用完毕后, 会尝试向后租借配额, 会导致生成器时间与实际时间产生差别.

在上述的测试环境下

=== RUN TestUniqueParallel
snowflake_test.go:101: generate 400000 unique ids, timeOffset: -283
--- PASS: TestUniqueParallel (0.11s)

如果在0.11s内生成40个ID, 可能会导致283ms的偏差, 此偏差会随着请求的并发度降低而逐渐拨正.

考虑到目前的实际场景, 我们可以暂时性的忽略此偏差.

func TestUniqueParallel(t *testing.T) {
	// 测试在并发40W的情况下，生成的id是否唯一
	conf := Config{1}
	gene := NewIDWorker(conf)

	m := make(map[int64]bool)
	const (
		times       = 40000
		repeatTimes = 10
	)
	ch := make(chan int64, times*repeatTimes)
	wg := sync.WaitGroup{}
	wg.Add(times)
	// parallel generate
	for j := 0; j < times; j++ {
		go func() {
			defer wg.Done()
			for i := 0; i < repeatTimes; i++ {
				ch <- gene.Generate()
			}
		}()
	}
	wg.Wait()
	close(ch)
	for id := range ch {
		if _, ok := m[id]; ok {
			t.Fatal("not unique")
		}
		m[id] = true
	}
	t.Logf("generate %d unique ids, timeOffset: %d \n", len(m), gene.(*idWorker).getTimeOffset())
}

性能基准测试

goos: windows
goarch: amd64
pkg: member/internal/snowflake
cpu: AMD Ryzen 7 7840HS w/ Radeon 780M Graphics
BenchmarkGenParallel10
BenchmarkGenParallel10-16               29599464                38.84 ns/op
BenchmarkGenParallel100
BenchmarkGenParallel100-16              28018810                44.38 ns/op
BenchmarkGenParallel1000
BenchmarkGenParallel1000-16             21572800                50.74 ns/op
BenchmarkGenParallel10000
BenchmarkGenParallel10000-16            27123960                45.15 ns/op
BenchmarkGenParallel100000
BenchmarkGenParallel100000-16           21775533                54.94 ns/op

并发量的分布从10 逐步增加至100000, 每操作耗时略有增加, 但仍处于比较健康的状态.

考虑到目前单机的生成QPS量级, 完全满足需求