《MMO 服务器开发》14.2 写缓冲与分段榜单

// file: internal/rank/buffer.go
// tier: L1
// verify: go test ./internal/rank/ -run TestService -v

package rank

import "sync"

// WriteBuffer collapses repeated score updates per player inside one flush
// window. A player's hot loop can Submit thousands of times; only the last
// score per player reaches the board, so board mutations stay bounded by the
// number of distinct players, not by the number of updates.
type WriteBuffer struct {
	mu   sync.Mutex
	pend map[uint64]int64
}

func NewWriteBuffer() *WriteBuffer {
	return &WriteBuffer{pend: make(map[uint64]int64)}
}

// Submit records the latest score for a player and reports whether this call
// coalesced into an update that was already pending.
func (w *WriteBuffer) Submit(id uint64, score int64) bool {
	w.mu.Lock()
	defer w.mu.Unlock()
	_, dup := w.pend[id]
	w.pend[id] = score
	return dup
}

// Drain returns the pending updates and clears the buffer.
func (w *WriteBuffer) Drain() map[uint64]int64 {
	w.mu.Lock()
	defer w.mu.Unlock()
	out := w.pend
	w.pend = make(map[uint64]int64)
	return out
}

// Pending reports how many distinct players have an unflushed update.
func (w *WriteBuffer) Pending() int {
	w.mu.Lock()
	defer w.mu.Unlock()
	return len(w.pend)
}

// Service is a leaderboard plus its write buffer. Flush is the only place the
// board is mutated, so a single goroutine owns it and the skip list needs no
// internal locking.
type Service struct {
	board *Board
	buf   *WriteBuffer
}

func NewService(seed1, seed2 uint64) *Service {
	return &Service{board: NewBoard(seed1, seed2), buf: NewWriteBuffer()}
}

// SubmitScore records a score update without touching the board.
func (s *Service) SubmitScore(id uint64, score int64) { s.buf.Submit(id, score) }

// Flush applies buffered updates and returns how many board mutations ran. It
// is always <= the number of SubmitScore calls since the last Flush.
func (s *Service) Flush() int {
	pend := s.buf.Drain()
	for id, score := range pend {
		s.board.Set(id, score)
	}
	return len(pend)
}

func (s *Service) Rank(id uint64) (int, bool) { return s.board.Rank(id) }
func (s *Service) TopK(k int) []Entry         { return s.board.TopK(k) }
func (s *Service) Len() int                    { return s.board.Len() }

// file: internal/rank/skiplist.go
// tier: L1
// verify: go test ./internal/rank/ -run TestBoard -v

package rank

import "math/rand/v2"

const (
	maxLevel = 16
	pFactor  = 0.25
)

// node: forward[i] is the next node on level i; width[i] is how many base-list
// nodes that hop skips. Width is what makes rank queries O(log n).
type node struct {
	e       Entry
	forward []*node
	width   []int
}

func newNode(e Entry, level int) *node {
	return &node{e: e, forward: make([]*node, level), width: make([]int, level)}
}

// Board orders entries by better(): higher score first, ties by smaller id.
type Board struct {
	head  *node
	level int // level count, 1-based
	n     int
	index map[uint64]*node
	rng   *rand.Rand
}

func NewBoard(s1, s2 uint64) *Board {
	return &Board{head: newNode(Entry{}, maxLevel), level: 1,
		index: map[uint64]*node{}, rng: rand.New(rand.NewPCG(s1, s2))}
}

func (b *Board) randomLevel() int {
	lvl := 1
	for lvl < maxLevel && b.rng.Float64() < pFactor {
		lvl++
	}
	return lvl
}

func (b *Board) insert(e Entry, level int) *node {
	update := make([]*node, maxLevel)
	rank := make([]int, maxLevel)
	x := b.head
	for i := b.level - 1; i >= 0; i-- {
		rank[i] = 0
		if i != b.level-1 {
			rank[i] = rank[i+1]
		}
		for x.forward[i] != nil && better(x.forward[i].e, e) {
			rank[i] += x.width[i]
			x = x.forward[i]
		}
		update[i] = x
	}
	if level > b.level {
		for i := b.level; i < level; i++ {
			update[i] = b.head
			update[i].width[i] = b.n
		}
		b.level = level
	}
	nd := newNode(e, level)
	for i := 0; i < level; i++ {
		nd.forward[i] = update[i].forward[i]
		update[i].forward[i] = nd
		nd.width[i] = update[i].width[i] - (rank[0] - rank[i])
		update[i].width[i] = (rank[0] - rank[i]) + 1
	}
	for i := level; i < b.level; i++ {
		update[i].width[i]++
	}
	b.n++
	return nd
}

func (b *Board) remove(e Entry) {
	update := make([]*node, maxLevel)
	x := b.head
	for i := b.level - 1; i >= 0; i-- {
		for x.forward[i] != nil && better(x.forward[i].e, e) {
			x = x.forward[i]
		}
		update[i] = x
	}
	x = x.forward[0]
	if x == nil || x.e != e {
		return
	}
	for i := 0; i < b.level; i++ {
		if update[i].forward[i] == x {
			update[i].width[i] += x.width[i] - 1
			update[i].forward[i] = x.forward[i]
		} else {
			update[i].width[i]--
		}
	}
	for b.level > 1 && b.head.forward[b.level-1] == nil {
		b.level--
	}
	b.n--
}

// Set inserts a player or moves them to a new score.
func (b *Board) Set(id uint64, score int64) {
	if old, ok := b.index[id]; ok {
		b.remove(old.e)
	}
	b.index[id] = b.insert(Entry{PlayerID: id, Score: score}, b.randomLevel())
}

// Rank returns the 1-based rank of id in O(log n), or false if absent.
func (b *Board) Rank(id uint64) (int, bool) {
	nd, ok := b.index[id]
	if !ok {
		return 0, false
	}
	x, rank := b.head, 0
	for i := b.level - 1; i >= 0; i-- {
		for x.forward[i] != nil && better(x.forward[i].e, nd.e) {
			rank += x.width[i]
			x = x.forward[i]
		}
	}
	return rank + 1, true
}

// TopK returns the best k entries, best first, in O(k).
func (b *Board) TopK(k int) []Entry {
	if k > b.n {
		k = b.n
	}
	out := make([]Entry, 0, k)
	for x := b.head.forward[0]; x != nil && len(out) < k; x = x.forward[0] {
		out = append(out, x.e)
	}
	return out
}

func (b *Board) Len() int { return b.n }

$ go test ./internal/rank/ -run TestNothing -bench BenchmarkRank -benchmem
goos: darwin  goarch: arm64  cpu: Apple M1 Pro
BenchmarkRankNaive-10          462    2459606 ns/op    327768 B/op    4 allocs/op
BenchmarkRankSkiplist-10  11559003        104.4 ns/op         0 B/op    0 allocs/op
PASS