《MMO 服务器开发》9.2 时间轮从零实现

        interval = 10ms, slots = 8, span = 80ms
   ┌────┬────┬────┬────┬────┬────┬────┬────┐
   │ 0  │ 1  │ 2  │ 3  │ 4  │ 5  │ 6  │ 7  │   ← buckets[slots]
   └────┴────┴────┴────┴────┴────┴────┴────┘
     ▲cursor 每 Tick 右移一格
     落格公式：slot = (cursor + ticks) % slots，ticks = 剩余时间 / interval

// file: internal/timing/wheel.go
// tier: L1
// verify: go test ./internal/timing/

// Package timing 提供游戏服务端的三种时间设施：技能冷却与心跳看门狗（懒判定）、
// 哈希时间轮（海量短周期定时器），以及逻辑帧世界时钟（固定步长 Tick）。
//
// 核心取舍：游戏服务端的定时器数量级是「每玩家几十个」。time.AfterFunc 每个任务
// 一个堆节点 + 一个 runtime timer，挂载是 O(log n)；时间轮把挂载降成 O(1) 取模，
// 代价是精度退化到一格（tick）。短周期、精度不敏感的定时器走时间轮最划算。
package timing

import (
	"sync"
	"sync/atomic"
	"time"
)

// Task 是时间轮上的一个定时任务。
type Task struct {
	ID      uint64
	expires time.Time
	fn      func()
}

// Wheel 是按固定 tick 推进的哈希时间轮。
//
// 同一格里的任务如果到期时间超过了一圈，会在触发时被重新挂回后面的格子
// （cascade 级联），因此支持任意时长的定时，而不只是 wheel 一圈以内。
type Wheel struct {
	interval time.Duration
	slots    int
	buckets  [][]*Task
	cursor   int
	now      time.Time
	seq      atomic.Uint64
	mu       sync.Mutex
}

// New 建一个时间轮。interval 是 tick 粒度，slots 是格子数，
// 单圈跨度 Span() = interval * slots。
func New(interval time.Duration, slots int) *Wheel {
	if interval <= 0 {
		panic("timing: interval must be positive")
	}
	if slots <= 0 {
		panic("timing: slots must be positive")
	}
	return &Wheel{
		interval: interval,
		slots:    slots,
		buckets:  make([][]*Task, slots),
		now:      time.Now(),
	}
}

// Span 返回单圈跨度。
func (w *Wheel) Span() time.Duration {
	return w.interval * time.Duration(w.slots)
}

// After 在 d 之后触发 fn，返回任务 ID。d <= 0 时下一个 tick 触发。
func (w *Wheel) After(d time.Duration, fn func()) uint64 {
	w.mu.Lock()
	defer w.mu.Unlock()
	t := &Task{ID: w.seq.Add(1), expires: w.now.Add(d), fn: fn}
	w.place(t)
	return t.ID
}

// place 把任务放到它应该落的格子里。调用方必须持有锁。
//
// 这是时间轮的 O(1) 挂载：把「到期时刻」折算成「还有几格」，再对格子数取模。
// 不需要比较、不需要下沉，一个加法一个取模就定位到槽位。
func (w *Wheel) place(t *Task) {
	ticks := int(t.expires.Sub(w.now) / w.interval)
	if ticks < 1 {
		ticks = 1 // 已过期或刚好到点：落到下一格，保证至少推进一次
	}
	slot := (w.cursor + ticks) % w.slots
	w.buckets[slot] = append(w.buckets[slot], t)
}

// Tick 推进一格并触发到期任务，返回本次触发的任务数。
// 测试里手动调用以获得确定性；生产里由 Run 驱动。
func (w *Wheel) Tick() int {
	w.mu.Lock()
	w.now = w.now.Add(w.interval)
	w.cursor = (w.cursor + 1) % w.slots
	bucket := w.buckets[w.cursor]
	w.buckets[w.cursor] = nil

	var due, later []*Task
	for _, t := range bucket {
		if !t.expires.After(w.now) {
			due = append(due, t)
		} else {
			later = append(later, t)
		}
	}
	// 还没到期的任务重新挂回后面的格子（级联）。因为 place 用的是「剩余格数」，
	// 一次级联就把任务推进到它真正该到的那一圈。
	for _, t := range later {
		w.place(t)
	}
	w.mu.Unlock()

	// 回调必须在锁外执行：回调里极可能又调用 After 注册新定时器，
	// 在锁内跑回调会自死锁（sync.Mutex 不可重入）。
	for _, t := range due {
		t.fn()
	}
	return len(due)
}

// Run 按真实时钟驱动时间轮，直到 stop 关闭。
func (w *Wheel) Run(stop <-chan struct{}) {
	tk := time.NewTicker(w.interval)
	defer tk.Stop()
	for {
		select {
		case <-stop:
			return
		case <-tk.C:
			w.Tick()
		}
	}
}

// snippet: internal/timing/wheel_test.go（节选）

func TestWheelCascadeBeyondOneSpan(t *testing.T) {
	w := New(10*time.Millisecond, 8) // span = 80ms
	fired := 0
	// 270ms 远超一圈，必须靠级联才能准时触发。
	w.After(270*time.Millisecond, func() { fired++ })

	for i := 0; i < 26; i++ {
		if n := w.Tick(); n != 0 {
			t.Fatalf("tick %d fired %d, want 0", i+1, n)
		}
	}
	if n := w.Tick(); n != 1 { // 第 27 拍 now=270ms
		t.Fatalf("tick 27 fired %d, want 1", n)
	}
	if fired != 1 {
		t.Fatalf("long timer ran %d times, want 1", fired)
	}
}

   任务 expires = 270ms，interval = 10ms，slots = 8
   落格：slot = (cursor + 剩余ms/10) % 8
   ┌─ tick 3  (now=30ms)  cursor=3  剩余 24 格 → slot (3+24)%8 = 3  未到期，重挂
   ├─ tick 11 (now=110ms) cursor=3  剩余 16 格 → slot (3+16)%8 = 3  未到期，重挂
   ├─ tick 19 (now=190ms) cursor=3  剩余  8 格 → slot (3+ 8)%8 = 3  未到期，重挂
   └─ tick 27 (now=270ms) cursor=3  expires ≤ now                  ✓ 触发