《游戏服务端架构·品类、状态与拓扑》10.1 无缝世界的分片与边界

// file: internal/seamless/seamless.go
// tier: L1
// verify: go test ./internal/seamless/
package seamless

import (
	"errors"
	"fmt"
	"time"
)

var (
	ErrBadChunkSize = errors.New("seamless: chunk size must be positive")
	ErrBadWorldSize = errors.New("seamless: world needs at least one chunk")
	ErrBadWindow    = errors.New("seamless: mirror window must be positive")
	ErrEmptyShard   = errors.New("seamless: empty shard id")
	ErrEmptyEntity  = errors.New("seamless: empty entity id")
	ErrEntityExists = errors.New("seamless: entity already spawned")
	ErrNoEntity     = errors.New("seamless: unknown entity")
	ErrChunkOutside = errors.New("seamless: chunk outside world")
	ErrCoverageGap  = errors.New("seamless: chunk has no owner")
	ErrOutOfBounds  = errors.New("seamless: outside world or one-chunk step")
	ErrNotAuthority = errors.New("seamless: shard is not the writer")
	ErrOutOfOrder   = errors.New("seamless: sequence not increasing")
	ErrFrozen       = errors.New("seamless: entity frozen during handoff")
	ErrNoTransfer   = errors.New("seamless: no open handoff")
	ErrStaleEpoch   = errors.New("seamless: stale handoff epoch")
)

type Point struct{ X, Y int }

type Chunk struct{ X, Y int }

// Layout assigns every chunk to one shard; a hole is rejected at construction.
type Layout struct {
	size  int
	cols  int
	rows  int
	owner map[Chunk]string
}

func floorDiv(a, b int) int {
	q := a / b
	if a%b != 0 && (a < 0) != (b < 0) {
		q--
	}
	return q
}

func NewLayout(chunkSize, cols, rows int, assign map[Chunk]string) (*Layout, error) {
	if chunkSize <= 0 {
		return nil, fmt.Errorf("%w: %d", ErrBadChunkSize, chunkSize)
	}
	if cols <= 0 || rows <= 0 {
		return nil, fmt.Errorf("%w: %dx%d", ErrBadWorldSize, cols, rows)
	}
	l := &Layout{size: chunkSize, cols: cols, rows: rows,
		owner: make(map[Chunk]string, cols*rows)}
	for c, shard := range assign {
		if shard == "" {
			return nil, fmt.Errorf("%w: %v", ErrEmptyShard, c)
		}
		if c.X < 0 || c.X >= cols || c.Y < 0 || c.Y >= rows {
			return nil, fmt.Errorf("%w: %v", ErrChunkOutside, c)
		}
		l.owner[c] = shard
	}
	for y := 0; y < rows; y++ {
		for x := 0; x < cols; x++ {
			if _, ok := l.owner[Chunk{x, y}]; !ok {
				return nil, fmt.Errorf("%w: (%d,%d)", ErrCoverageGap, x, y)
			}
		}
	}
	return l, nil
}

func (l *Layout) ChunkOf(p Point) (Chunk, bool) {
	c := Chunk{floorDiv(p.X, l.size), floorDiv(p.Y, l.size)}
	if c.X < 0 || c.X >= l.cols || c.Y < 0 || c.Y >= l.rows {
		return Chunk{}, false
	}
	return c, true
}

func (l *Layout) Owner(p Point) (string, Chunk, bool) {
	c, ok := l.ChunkOf(p)
	if !ok {
		return "", Chunk{}, false
	}
	shard, ok := l.owner[c]
	return shard, c, ok
}

// Transfer records one handoff. FrozenUntil bounds command rejection;
// VisibleUntil bounds the read-only mirror kept by the source shard.
type Transfer struct {
	Entity, From, To          string
	Epoch, Seq                uint64
	FrozenUntil, VisibleUntil time.Time
}

type Placement struct {
	Entity, Shard string
	Chunk         Chunk
	Seq, Epoch    uint64
	Transfer      *Transfer
}

type entityState struct {
	pos           Point
	shard, mirror string
	epoch, seq    uint64
	frozenUntil   time.Time
	mirrorUntil   time.Time
}

// World keeps one writer per entity; the source mirror is never writable.
type World struct {
	layout   *Layout
	window   time.Duration
	now      func() time.Time
	entities map[string]*entityState
}

func NewWorld(layout *Layout, window time.Duration, now func() time.Time) (*World, error) {
	if layout == nil {
		return nil, errors.New("seamless: nil layout")
	}
	if window <= 0 {
		return nil, fmt.Errorf("%w: %s", ErrBadWindow, window)
	}
	if now == nil {
		now = time.Now
	}
	return &World{layout: layout, window: window, now: now,
		entities: make(map[string]*entityState)}, nil
}

func (w *World) Spawn(id string, p Point) (Placement, error) {
	if id == "" {
		return Placement{}, ErrEmptyEntity
	}
	if _, ok := w.entities[id]; ok {
		return Placement{}, ErrEntityExists
	}
	shard, chunk, ok := w.layout.Owner(p)
	if !ok {
		return Placement{}, fmt.Errorf("%w: (%d,%d)", ErrOutOfBounds, p.X, p.Y)
	}
	e := &entityState{pos: p, shard: shard, epoch: 1}
	w.entities[id] = e
	return Placement{Entity: id, Shard: shard, Chunk: chunk, Epoch: e.epoch}, nil
}

// Submit rejects a stale, foreign or teleporting request and opens a handoff
// when the target chunk belongs to another shard.
func (w *World) Submit(id, shard string, to Point, seq uint64) (Placement, error) {
	e, ok := w.entities[id]
	if !ok {
		return Placement{}, ErrNoEntity
	}
	if shard != e.shard {
		return Placement{}, fmt.Errorf("%w: %s owns %s", ErrNotAuthority, e.shard, id)
	}
	if w.now().Before(e.frozenUntil) {
		return Placement{}, fmt.Errorf("%w: until %s", ErrFrozen, e.frozenUntil)
	}
	if seq <= e.seq {
		return Placement{}, fmt.Errorf("%w: %d <= %d", ErrOutOfOrder, seq, e.seq)
	}
	from, ok := w.layout.ChunkOf(e.pos)
	if !ok {
		return Placement{}, fmt.Errorf("%w: from (%d,%d)", ErrOutOfBounds, e.pos.X, e.pos.Y)
	}
	target, ok := w.layout.ChunkOf(to)
	if !ok {
		return Placement{}, fmt.Errorf("%w: to (%d,%d)", ErrOutOfBounds, to.X, to.Y)
	}
	if dx, dy := target.X-from.X, target.Y-from.Y; dx < -1 || dx > 1 || dy < -1 || dy > 1 {
		return Placement{}, fmt.Errorf("%w: chunk %v -> %v", ErrOutOfBounds, from, target)
	}
	dest, _, _ := w.layout.Owner(to)
	e.seq = seq
	e.pos = to
	out := Placement{Entity: id, Shard: dest, Chunk: target, Seq: seq, Epoch: e.epoch}
	if dest == e.shard {
		return out, nil
	}
	now := w.now()
	e.mirror = e.shard
	e.shard = dest
	e.epoch++
	e.frozenUntil = now.Add(w.window)
	e.mirrorUntil = now.Add(w.window)
	out.Epoch = e.epoch
	out.Transfer = &Transfer{Entity: id, From: e.mirror, To: dest, Epoch: e.epoch,
		Seq: seq, FrozenUntil: e.frozenUntil, VisibleUntil: e.mirrorUntil}
	return out, nil
}

type Sweep struct {
	Unfrozen []string
	Released []string
}

// Sweep expires the command freeze and the source mirror.
func (w *World) Sweep() Sweep {
	now := w.now()
	var out Sweep
	for id, e := range w.entities {
		if !e.frozenUntil.IsZero() && !now.Before(e.frozenUntil) {
			e.frozenUntil = time.Time{}
			out.Unfrozen = append(out.Unfrozen, id)
		}
		if e.mirror != "" && !now.Before(e.mirrorUntil) {
			e.mirror = ""
			out.Released = append(out.Released, id)
		}
	}
	return out
}

func (w *World) Authoritative(id, shard string) bool {
	e, ok := w.entities[id]
	return ok && e.shard == shard
}

func (w *World) Visible(id, shard string) bool {
	e, ok := w.entities[id]
	if !ok {
		return false
	}
	return e.shard == shard || (e.mirror == shard && w.now().Before(e.mirrorUntil))
}

type Interaction int

const (
	Move Interaction = iota
	Combat
	Trade
	Loot
	Chat
)

// Move has a handoff and Chat a message bus; combat, trade and loot must be
// co-located because they have no safe split-brain version.
func (k Interaction) MayCrossShard() bool {
	return k == Move || k == Chat
}

func CoLocated(a, b string, k Interaction) bool {
	return a == b || k.MayCrossShard()
}

$ cd .local/checks/gsarch-lab
$ gofmt -l internal/seamless
$ go test -count=1 ./internal/seamless/
ok  	gsarchlab/internal/seamless	0.267s