《MMO 服务器开发》8.2 消息序号、去重与顺序保证

// file: internal/router/seq.go
// tier: L1
// verify: go test ./internal/router/

package router

// SeqWindow tracks the highest seq accepted on one connection plus a 64-bit
// sliding window of the seq values seen just below it. It is a faithful port of
// the TCP receive-window trick: a replayed or too-old frame is rejected, and
// all comparisons are wrap-safe because seq is a uint32 counter.
type SeqWindow struct {
	size   uint32 // window width in bits, 1..64
	high   uint32
	bitmap uint64 // bit i set means high-i has been seen
	seen   bool
}

// NewSeqWindow returns a window of the given width (clamped to 1..64).
func NewSeqWindow(size uint32) *SeqWindow {
	if size < 1 {
		size = 1
	}
	if size > 64 {
		size = 64
	}
	return &SeqWindow{size: size}
}

// Accept records seq and reports whether it is new. It returns false for a
// duplicate (already in the window) or a frame so old it fell out of the window.
func (w *SeqWindow) Accept(seq uint32) bool {
	if !w.seen {
		w.seen = true
		w.high = seq
		w.bitmap = 1
		return true
	}
	// int32 subtraction makes the comparison wrap-safe: seq 0 right after
	// 0xffffffff is +1 ahead, not a huge negative number.
	diff := int32(seq - w.high)
	if diff > 0 {
		if uint32(diff) >= w.size {
			w.bitmap = 1
		} else {
			w.bitmap = (w.bitmap << uint(diff)) | 1
		}
		w.high = seq
		return true
	}
	back := uint32(-diff)
	if back >= w.size {
		return false // too old to judge; treat as duplicate to stay safe
	}
	bit := uint64(1) << back
	if w.bitmap&bit != 0 {
		return false // already seen: a replay
	}
	w.bitmap |= bit
	return true
}

// ReorderBuffer holds frames whose seq is ahead of the expected one and releases
// them in order once the gap fills. Its job is to give a connection an in-order
// view of a stream that arrived out of order; it does not retransmit, so a gap
// that never fills eventually forces a resync from the caller.
type ReorderBuffer struct {
	next    uint32
	cap     int
	pending map[uint32]Frame
	seen    bool
}

// NewReorderBuffer returns a buffer holding at most cap out-of-order frames.
func NewReorderBuffer(cap int) *ReorderBuffer {
	if cap < 1 {
		cap = 1
	}
	return &ReorderBuffer{cap: cap, pending: make(map[uint32]Frame)}
}

// Push feeds one frame in. It returns the frames that became deliverable in seq
// order, how many frames are still buffered behind a gap, and whether the
// buffer overflowed (the caller should resync when it did).
//
// The first frame anchors the baseline: whatever seq arrives first is treated as
// the expected one, because there is nothing to compare against yet.
func (b *ReorderBuffer) Push(f Frame) (ready []Frame, buffered int, overflow bool) {
	if !b.seen {
		b.seen = true
		b.next = f.Seq
	}
	switch {
	case f.Seq == b.next:
		ready = append(ready, f)
		b.next++
		for {
			g, ok := b.pending[b.next]
			if !ok {
				break
			}
			delete(b.pending, b.next)
			ready = append(ready, g)
			b.next++
		}
	case int32(f.Seq-b.next) < 0:
		// Older than expected: already delivered, drop it.
	default:
		if len(b.pending) < b.cap {
			b.pending[f.Seq] = f
		} else {
			overflow = true
		}
	}
	return ready, len(b.pending), overflow
}

// Pending reports how many frames are buffered behind a gap.
func (b *ReorderBuffer) Pending() int { return len(b.pending) }

high=5  bitmap=0b00011111     bit0..bit4 置 1，表示 5,4,3,2,1 都见过

收到 seq=8（领先 3 格）：
    bitmap = (0b00011111 << 3) | 1 = 0b11111001, high=8
    bit0=1（8 见过）；bit1、bit2 仍为 0（7、6 还没到）
收到 seq=6（落后 2 格）：bit2 为 0 → 接受，置 1
收到 seq=6 再来一次：  bit2 已为 1 → 判为重复，丢弃

// snippet: internal/router/seq_test.go（节选）

func TestSeqWindowRejectsDuplicate(t *testing.T) {
	w := NewSeqWindow(64)
	if !w.Accept(10) {
		t.Fatal("first accept of 10 should succeed")
	}
	if w.Accept(10) {
		t.Fatal("replay of 10 must be rejected")
	}
}

func TestSeqWindowWrapAround(t *testing.T) {
	w := NewSeqWindow(64)
	w.Accept(0xfffffffe)
	w.Accept(0xffffffff)
	if !w.Accept(0) { // 回绕后 0 是「下一个」，不是「很久以前」
		t.Fatal("seq 0 after 0xffffffff should be accepted")
	}
}

func TestReorderBufferEmitsInOrder(t *testing.T) {
	b := NewReorderBuffer(8)
	b.Push(Frame{Seq: 10}) // 第一帧锚定基线
	ready, buffered, _ := b.Push(Frame{Seq: 12})
	if len(ready) != 0 || buffered != 1 {
		t.Fatalf("out-of-order 12: ready=%d buffered=%d; want 0,1", len(ready), buffered)
	}
	ready, _, _ = b.Push(Frame{Seq: 11}) // 缺口补齐，11 和 12 一起放行
	if len(ready) != 2 || ready[0].Seq != 11 || ready[1].Seq != 12 {
		t.Fatalf("gap fill emitted out of order: %+v", ready)
	}
}

$ go test ./internal/router/ -run '^$' -bench 'BenchmarkSeqWindowAccept' -benchmem -count=3
BenchmarkSeqWindowAccept-10   152227797   7.259 ns/op   0 B/op   0 allocs/op
BenchmarkSeqWindowAccept-10   166896390   7.367 ns/op   0 B/op   0 allocs/op
BenchmarkSeqWindowAccept-10   164834041   7.313 ns/op   0 B/op   0 allocs/op