《MMO 服务器开发》7.1 雪花算法从零实现

 63      62                              22        12         0
+--+---------------------------------------+---------+----------+
|0 |        41 位毫秒时间戳 (ts)            | 10 位   | 12 位    |
|  |                                       | worker  | 序列 seq |
+--+---------------------------------------+---------+----------+
  1                  41                        10         12

// file: internal/idgen/clock.go
// tier: L1
// verify: go test ./internal/idgen/
package idgen

import "time"

// Clock 抽象「毫秒时间源」。雪花算法与号段模式都不直接依赖 time.Now，
// 而是依赖这个接口——这样回拨、闰秒这类场景才能用假时钟注入（见 7.3）。
type Clock interface {
	NowMillis() int64
}

// RealClock 是生产环境的实现。
type RealClock struct{}

// NowMillis 返回 Unix 毫秒。
func (RealClock) NowMillis() int64 { return time.Now().UnixMilli() }

// file: internal/idgen/snowflake.go
// tier: L1
// verify: go test ./internal/idgen/
package idgen

import (
	"errors"
	"sync"
)

// 64 位布局：符号位(1) + 时间戳(41) + worker id(10) + 序列(12)
//
//	| 1 | 41 位毫秒时间戳 | 10 位 worker | 12 位序列 |
//	最高位恒为 0，保证生成的 uint64 转成 int64 后永远为正。
const (
	// Epoch 自定义纪元：2024-01-01T00:00:00Z，比 Unix 纪元更晚，
	// 41 位可覆盖 (1<<41)/1000/86400/365 ≈ 69.7 年。
	Epoch int64 = 1704067200000

	workerBits   uint = 10
	sequenceBits uint = 12

	// MaxWorkerID 10 位 worker 上限 1023。
	MaxWorkerID int64 = -1 ^ (-1 << workerBits)
	// MaxSequence 12 位序列上限 4095。
	MaxSequence int64 = -1 ^ (-1 << sequenceBits)

	workerShift    uint = sequenceBits              // 12
	timestampShift uint = sequenceBits + workerBits // 22
)

// ErrClockBackwards 表示本地时钟早于上一次生成时刻。
var ErrClockBackwards = errors.New("idgen: clock moved backwards")

// ErrWorkerRange worker id 越界。
var ErrWorkerRange = errors.New("idgen: worker id out of range")

// Snowflake 是单节点的雪花 ID 生成器。并发安全。
type Snowflake struct {
	mu       sync.Mutex
	clock    Clock
	workerID int64
	lastMs   int64
	sequence int64
}

// NewSnowflake 用给定 worker id 与时钟构造生成器。
func NewSnowflake(workerID int64, clock Clock) (*Snowflake, error) {
	if workerID < 0 || workerID > MaxWorkerID {
		return nil, ErrWorkerRange
	}
	if clock == nil {
		clock = RealClock{}
	}
	return &Snowflake{clock: clock, workerID: workerID}, nil
}

// WorkerID 由区服号（ServerID）与节点序号合成 10 位 worker id：
// 高 5 位放区服号低 5 位，低 5 位放节点序号。这样跨服全局唯一的同时，
// 出问题时也能从 ID 反推出它出自哪个区服的哪个节点。
func WorkerID(serverID uint16, nodeIndex uint8) (int64, error) {
	if nodeIndex > 31 {
		return 0, ErrWorkerRange
	}
	return (int64(serverID)&0x1F)<<5 | int64(nodeIndex), nil
}

// Next 生成下一个 ID。同一毫秒内序列耗尽时自旋到下一毫秒。
func (s *Snowflake) Next() (uint64, error) {
	s.mu.Lock()
	defer s.mu.Unlock()

	now := s.clock.NowMillis()
	if now < s.lastMs {
		return 0, ErrClockBackwards
	}
	if now == s.lastMs {
		s.sequence = (s.sequence + 1) & MaxSequence
		if s.sequence == 0 {
			for now <= s.lastMs {
				now = s.clock.NowMillis()
			}
		}
	} else {
		s.sequence = 0
	}
	s.lastMs = now
	return compose(now, s.workerID, s.sequence), nil
}

func compose(ms, workerID, sequence int64) uint64 {
	return uint64(ms-Epoch)<<timestampShift |
		uint64(workerID)<<workerShift |
		uint64(sequence)
}

// TimestampOf 从 ID 反解出毫秒时间戳（加回 Epoch）。
func TimestampOf(id uint64) int64 { return int64(id>>timestampShift) + Epoch }

// WorkerIDOf 从 ID 反解出 worker id。
func WorkerIDOf(id uint64) int64 { return int64(id>>workerShift) & MaxWorkerID }

// SequenceOf 从 ID 反解出同毫秒内的序列号。
func SequenceOf(id uint64) int64 { return int64(id) & MaxSequence }

// file: internal/idgen/snowflake_bench_test.go
// tier: B
// verify: go test ./internal/idgen/ -run TestSnowflakeThroughputUniqueness -v
package idgen

import (
	"sort"
	"sync"
	"testing"
	"time"
)

// TestSnowflakeThroughputUniqueness 是 B 级基准：并发下的吞吐 + 重复率断言。
func TestSnowflakeThroughputUniqueness(t *testing.T) {
	const (
		workers   = 8
		perWorker = 250_000
	)
	s, _ := NewSnowflake(42, RealClock{})
	all := make([][]uint64, workers)
	var wg sync.WaitGroup
	start := time.Now()
	for w := 0; w < workers; w++ {
		wg.Add(1)
		go func(w int) {
			defer wg.Done()
			buf := make([]uint64, 0, perWorker)
			for i := 0; i < perWorker; i++ {
				id, err := s.Next()
				if err != nil {
					t.Errorf("next: %v", err)
					return
				}
				buf = append(buf, id)
			}
			all[w] = buf
		}(w)
	}
	wg.Wait()
	elapsed := time.Since(start)

	total := workers * perWorker
	flat := make([]uint64, 0, total)
	for _, b := range all {
		flat = append(flat, b...)
	}
	sort.Slice(flat, func(i, j int) bool { return flat[i] < flat[j] })
	dup := 0
	for i := 1; i < len(flat); i++ {
		if flat[i] == flat[i-1] {
			dup++
		}
	}
	if dup != 0 {
		t.Fatalf("重复 ID 必须为 0，实际 %d", dup)
	}
	t.Logf("单节点 %d 个 ID / %d 并发，耗时 %s，吞吐 %.0f 万/秒，重复率 0",
		total, workers, elapsed, float64(total)/elapsed.Seconds()/1e4)
}

func BenchmarkSnowflakeNext(b *testing.B) {
	s, _ := NewSnowflake(1, RealClock{})
	b.ReportAllocs()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		if _, err := s.Next(); err != nil {
			b.Fatal(err)
		}
	}
}

单节点 2000000 个 ID / 8 并发，耗时 487ms，吞吐 410 万/秒，重复率 0
BenchmarkSnowflakeNext-10    9849972    244.6 ns/op    0 B/op    0 allocs/op