《游戏服务端架构·品类、状态与拓扑》3.3 分区、分服与全球同服

// file: internal/shard/router.go
// tier: L1
// verify: go test ./internal/shard/
package shard

import (
	"errors"
	"fmt"
	"sort"
)

type Region string

const (
	RegionCN Region = "cn"
	RegionEU Region = "eu"
	RegionNA Region = "na"
)

var (
	ErrOverlap      = errors.New("shard: overlapping ranges")
	ErrBadRange     = errors.New("shard: start must not exceed end")
	ErrDuplicateID  = errors.New("shard: duplicate shard id")
	ErrEmptyID      = errors.New("shard: empty shard id")
	ErrCoverageLost = errors.New("shard: rebalance plan loses map cells")
)

// Shard owns an inclusive map-cell range inside one region; no cell has two owners.
type Shard struct {
	ID     string
	Region Region
	Start  int
	End    int
}

func (s Shard) Size() int { return s.End - s.Start + 1 }

type Router struct {
	byRegion map[Region][]Shard
}

func NewRouter(layout []Shard) (*Router, error) {
	if err := validate(layout); err != nil {
		return nil, err
	}
	r := &Router{byRegion: make(map[Region][]Shard)}
	for _, s := range layout {
		r.byRegion[s.Region] = append(r.byRegion[s.Region], s)
	}
	for region := range r.byRegion {
		list := r.byRegion[region]
		sort.Slice(list, func(i, j int) bool { return list[i].Start < list[j].Start })
	}
	return r, nil
}

// Route resolves an inclusive cell inside one region; it never falls back to
// another region, because that would cross a data-residency boundary.
func (r *Router) Route(region Region, cell int) (Shard, bool) {
	list := r.byRegion[region]
	i := sort.Search(len(list), func(i int) bool { return list[i].End >= cell })
	if i < len(list) && list[i].Start <= cell {
		return list[i], true
	}
	return Shard{}, false
}

func validate(layout []Shard) error {
	ids := make(map[string]bool, len(layout))
	byRegion := make(map[Region][]Shard)
	for _, s := range layout {
		if s.ID == "" {
			return ErrEmptyID
		}
		if ids[s.ID] {
			return fmt.Errorf("%w: %s", ErrDuplicateID, s.ID)
		}
		ids[s.ID] = true
		if s.Start > s.End {
			return fmt.Errorf("%w: %s [%d,%d]", ErrBadRange, s.ID, s.Start, s.End)
		}
		byRegion[s.Region] = append(byRegion[s.Region], s)
	}
	for region, list := range byRegion {
		sort.Slice(list, func(i, j int) bool { return list[i].Start < list[j].Start })
		for i := 1; i < len(list); i++ {
			if list[i].Start <= list[i-1].End {
				return fmt.Errorf("%w: %s and %s in %s",
					ErrOverlap, list[i-1].ID, list[i].ID, region)
			}
		}
	}
	return nil
}

// Migration copies an inclusive overlap from one shard to another.
type Migration struct {
	From, To   string
	Start, End int
}

func (m Migration) Size() int { return m.End - m.Start + 1 }

type Plan struct {
	Migrations []Migration
	Retained   []Shard
}

func (p Plan) Cells() int {
	total := 0
	for _, m := range p.Migrations {
		total += m.Size()
	}
	for _, s := range p.Retained {
		total += s.Size()
	}
	return total
}

// BuildPlan proves every old cell is retained or migrated; a gap returns
// ErrCoverageLost instead of a partial plan.
func BuildPlan(from, to []Shard) (Plan, error) {
	if err := validate(from); err != nil {
		return Plan{}, fmt.Errorf("from layout: %w", err)
	}
	if err := validate(to); err != nil {
		return Plan{}, fmt.Errorf("to layout: %w", err)
	}
	byRegion := make(map[Region][]Shard)
	for _, s := range to {
		byRegion[s.Region] = append(byRegion[s.Region], s)
	}
	for region := range byRegion {
		list := byRegion[region]
		sort.Slice(list, func(i, j int) bool { return list[i].Start < list[j].Start })
	}

	var plan Plan
	for _, old := range from {
		covered := 0
		for _, next := range byRegion[old.Region] {
			lo, hi := max(old.Start, next.Start), min(old.End, next.End)
			if lo > hi {
				continue
			}
			covered += hi - lo + 1
			if next.ID == old.ID {
				plan.Retained = append(plan.Retained, Shard{
					ID: old.ID, Region: old.Region, Start: lo, End: hi})
				continue
			}
			plan.Migrations = append(plan.Migrations, Migration{
				From: old.ID, To: next.ID, Start: lo, End: hi})
		}
		if covered != old.Size() {
			return Plan{}, fmt.Errorf("%w: old shard %s has %d cells, new layout covers %d",
				ErrCoverageLost, old.ID, old.Size(), covered)
		}
	}
	sort.Slice(plan.Migrations, func(i, j int) bool {
		if plan.Migrations[i].From != plan.Migrations[j].From {
			return plan.Migrations[i].From < plan.Migrations[j].From
		}
		return plan.Migrations[i].Start < plan.Migrations[j].Start
	})
	sort.Slice(plan.Retained, func(i, j int) bool { return plan.Retained[i].ID < plan.Retained[j].ID })
	return plan, nil
}

// file: internal/shard/router_test.go
// tier: L1
// verify: go test ./internal/shard/
package shard

import (
	"errors"
	"testing"
)

func testLayout() []Shard {
	return []Shard{
		{ID: "cn-1", Region: RegionCN, Start: 0, End: 99},
		{ID: "cn-2", Region: RegionCN, Start: 100, End: 199},
		{ID: "eu-1", Region: RegionEU, Start: 0, End: 149},
	}
}

func TestRouteHitsInclusiveBoundaries(t *testing.T) {
	r, err := NewRouter(testLayout())
	if err != nil {
		t.Fatalf("NewRouter: %v", err)
	}
	cases := []struct {
		region Region
		cell   int
		want   string
		ok     bool
	}{
		{RegionCN, 0, "cn-1", true},
		{RegionCN, 99, "cn-1", true},
		{RegionCN, 100, "cn-2", true},
		{RegionCN, 199, "cn-2", true},
		{RegionCN, 200, "", false},
		{RegionCN, -1, "", false},
		{RegionEU, 149, "eu-1", true},
		{RegionEU, 150, "", false},
		{RegionNA, 0, "", false},
	}
	for _, c := range cases {
		got, ok := r.Route(c.region, c.cell)
		if ok != c.ok || got.ID != c.want {
			t.Fatalf("Route(%s,%d)=(%q,%v), want (%q,%v)",
				c.region, c.cell, got.ID, ok, c.want, c.ok)
		}
	}
}

func TestRouterRejectsOverlapAndBadRanges(t *testing.T) {
	_, err := NewRouter([]Shard{
		{ID: "a", Region: RegionCN, Start: 0, End: 50},
		{ID: "b", Region: RegionCN, Start: 50, End: 99},
	})
	if !errors.Is(err, ErrOverlap) {
		t.Fatalf("overlap error = %v", err)
	}
	_, err = NewRouter([]Shard{{ID: "bad", Region: RegionCN, Start: 10, End: 9}})
	if !errors.Is(err, ErrBadRange) {
		t.Fatalf("bad-range error = %v", err)
	}
}

func TestPlanSplitKeepsEveryCell(t *testing.T) {
	from := []Shard{{ID: "cn-1", Region: RegionCN, Start: 0, End: 99}}
	to := []Shard{
		{ID: "cn-1", Region: RegionCN, Start: 0, End: 49},
		{ID: "cn-2", Region: RegionCN, Start: 50, End: 99},
	}
	plan, err := BuildPlan(from, to)
	if err != nil {
		t.Fatalf("BuildPlan: %v", err)
	}
	if len(plan.Migrations) != 1 || len(plan.Retained) != 1 {
		t.Fatalf("plan = %+v", plan)
	}
	m := plan.Migrations[0]
	if m.From != "cn-1" || m.To != "cn-2" || m.Start != 50 || m.End != 99 {
		t.Fatalf("migration = %+v", m)
	}
	if plan.Cells() != 100 {
		t.Fatalf("plan cells = %d, want 100", plan.Cells())
	}
}

func TestPlanRejectsCoverageLoss(t *testing.T) {
	from := []Shard{{ID: "cn-1", Region: RegionCN, Start: 0, End: 99}}
	to := []Shard{{ID: "cn-1", Region: RegionCN, Start: 0, End: 49}}
	if _, err := BuildPlan(from, to); !errors.Is(err, ErrCoverageLost) {
		t.Fatalf("error = %v, want ErrCoverageLost", err)
	}
	from = append(from, Shard{ID: "eu-1", Region: RegionEU, Start: 0, End: 99})
	if _, err := BuildPlan(from, to); !errors.Is(err, ErrCoverageLost) {
		t.Fatalf("lost region error = %v", err)
	}
}

$ cd .local/checks/gsarch-lab
$ gofmt -l .
$ go vet ./...
$ go test -count=1 -v ./internal/shard/
=== RUN   TestRouteHitsInclusiveBoundaries
--- PASS: TestRouteHitsInclusiveBoundaries (0.00s)
=== RUN   TestRouterRejectsOverlapAndBadRanges
--- PASS: TestRouterRejectsOverlapAndBadRanges (0.00s)
=== RUN   TestPlanSplitKeepsEveryCell
--- PASS: TestPlanSplitKeepsEveryCell (0.00s)
=== RUN   TestPlanRejectsCoverageLoss
--- PASS: TestPlanRejectsCoverageLoss (0.00s)
PASS
ok  	gsarchlab/internal/shard	0.615s