《游戏服务端编程实践》8.3.2 同步策略与丢帧补偿

// file: ch08/lockstep/sync.go
// tier: L1
// verify: go test ./ch08/lockstep/

package lockstep

import "errors"

var (
	ErrJitterDuplicate = errors.New("jitter: duplicate or stale frame")
	ErrJitterFull      = errors.New("jitter: buffer full")
)

// JitterBuffer 按帧号重排输入。缺口在缓冲达到 maxDepth 帧后强制跳过，
// 避免一个永久丢失的帧让整场战斗停住。
type JitterBuffer[T any] struct {
	next     Frame
	maxDepth int
	items    map[Frame]T
	skipped  []Frame
}

// NewJitterBuffer 从 start 帧开始交付，maxDepth 同时是缺口等待阈值和容量上限。
func NewJitterBuffer[T any](start Frame, maxDepth int) *JitterBuffer[T] {
	if maxDepth < 1 {
		maxDepth = 1
	}
	return &JitterBuffer[T]{next: start, maxDepth: maxDepth, items: make(map[Frame]T)}
}

// Push 写入一帧。重复帧、已经交付过的帧返回 ErrJitterDuplicate；缓冲满返回 ErrJitterFull。
func (j *JitterBuffer[T]) Push(f Frame, v T) error {
	if f != j.next && !f.After(j.next) {
		return ErrJitterDuplicate
	}
	if _, ok := j.items[f]; ok {
		return ErrJitterDuplicate
	}
	if len(j.items) >= j.maxDepth {
		return ErrJitterFull
	}
	j.items[f] = v
	return nil
}

// Pop 返回下一可交付帧。缺口尚未达到 maxDepth 时返回 ok=false，调用方应继续等待。
func (j *JitterBuffer[T]) Pop() (Frame, T, bool) {
	var zero T
	if v, ok := j.items[j.next]; ok {
		f := j.next
		delete(j.items, f)
		j.next++
		return f, v, true
	}
	if len(j.items) == 0 || len(j.items) < j.maxDepth {
		return 0, zero, false
	}
	f := j.min()
	for gap := j.next; gap != f; gap++ {
		j.skipped = append(j.skipped, gap)
	}
	v := j.items[f]
	delete(j.items, f)
	j.next = f + 1
	return f, v, true
}

// Skipped 返回因缺口超限被跳过的帧号副本，供指标和排障使用。
func (j *JitterBuffer[T]) Skipped() []Frame {
	out := make([]Frame, len(j.skipped))
	copy(out, j.skipped)
	return out
}

// Buffered 返回尚未交付的帧数。
func (j *JitterBuffer[T]) Buffered() int { return len(j.items) }

func (j *JitterBuffer[T]) min() Frame {
	var m Frame
	first := true
	for f := range j.items {
		if first || f.Sub(m) < 0 {
			m = f
			first = false
		}
	}
	return m
}

// file: ch08/lockstep/sync_test.go
// tier: L1
// verify: go test ./ch08/lockstep/

package lockstep

import (
	"errors"
	"testing"
)

func mustPush[T any](t *testing.T, j *JitterBuffer[T], f Frame, v T) {
	t.Helper()
	if err := j.Push(f, v); err != nil {
		t.Fatalf("push frame %d: %v", f, err)
	}
}

func TestJitterBufferReorders(t *testing.T) {
	j := NewJitterBuffer[string](1, 8)
	mustPush(t, j, 3, "c")
	mustPush(t, j, 1, "a")
	mustPush(t, j, 2, "b")

	for _, want := range []struct {
		f Frame
		v string
	}{{1, "a"}, {2, "b"}, {3, "c"}} {
		f, v, ok := j.Pop()
		if !ok || f != want.f || v != want.v {
			t.Fatalf("pop = %d,%q,%v; want %d,%q,true", f, v, ok, want.f, want.v)
		}
	}
	if _, _, ok := j.Pop(); ok {
		t.Fatal("empty buffer should not deliver")
	}
}

func TestJitterBufferRejectsDuplicates(t *testing.T) {
	j := NewJitterBuffer[int](10, 4)
	mustPush(t, j, 10, 1)
	if err := j.Push(10, 2); !errors.Is(err, ErrJitterDuplicate) {
		t.Fatalf("want ErrJitterDuplicate, got %v", err)
	}
	if f, v, ok := j.Pop(); !ok || f != 10 || v != 1 {
		t.Fatalf("pop = %d,%d,%v; want 10,1,true", f, v, ok)
	}
	if err := j.Push(10, 3); !errors.Is(err, ErrJitterDuplicate) {
		t.Fatalf("delivered frame accepted: %v", err)
	}
}

func TestJitterBufferGapWaitAndSkip(t *testing.T) {
	j := NewJitterBuffer[int](1, 3)
	mustPush(t, j, 1, 1)
	mustPush(t, j, 3, 3)
	mustPush(t, j, 4, 4)

	if f, v, ok := j.Pop(); !ok || f != 1 || v != 1 {
		t.Fatalf("pop = %d,%d,%v; want 1,1,true", f, v, ok)
	}
	if _, _, ok := j.Pop(); ok {
		t.Fatal("gap 2 must wait while below maxDepth")
	}
	mustPush(t, j, 5, 5)
	f, v, ok := j.Pop()
	if !ok || f != 3 || v != 3 {
		t.Fatalf("pop = %d,%d,%v; want forced 3,3,true", f, v, ok)
	}
	if got := j.Skipped(); len(got) != 1 || got[0] != 2 {
		t.Fatalf("skipped = %v, want [2]", got)
	}
}

func TestJitterBufferGapFilledAndBounds(t *testing.T) {
	j := NewJitterBuffer[int](1, 4)
	mustPush(t, j, 1, 1)
	mustPush(t, j, 3, 3)
	if _, _, ok := j.Pop(); !ok {
		t.Fatal("frame 1 should deliver")
	}
	if _, _, ok := j.Pop(); ok {
		t.Fatal("frame 2 still missing")
	}
	mustPush(t, j, 2, 2)
	for _, want := range []int{2, 3} {
		f, v, ok := j.Pop()
		if !ok || f != Frame(want) || v != want {
			t.Fatalf("pop = %d,%d,%v; want %d", f, v, ok, want)
		}
	}

	full := NewJitterBuffer[int](1, 2)
	mustPush(t, full, 1, 1)
	mustPush(t, full, 3, 3)
	if err := full.Push(4, 4); !errors.Is(err, ErrJitterFull) {
		t.Fatalf("want ErrJitterFull, got %v", err)
	}
}

cd .local/checks/gs-practice-lab && gofmt -l ch08/lockstep && go vet ./ch08/lockstep/ && go test ./ch08/lockstep/ -count=1

ok  	gspractice/ch08/lockstep	0.371s