《游戏服务端架构·规模化、全球化与成本》4.1 分片键与数据模型

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

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

// Kind is the business identity a row is partitioned by. It matters more than
// the hash function: it decides which reads stay local and which become
// scatter-gather.
type Kind string

const (
	KindPlayer  Kind = "player"
	KindAccount Kind = "account"
	KindZone    Kind = "zone"
	KindGuild   Kind = "guild"
)

var (
	ErrEmptyName    = errors.New("shardkey: empty dataset name")
	ErrUnknownKind  = errors.New("shardkey: unknown key kind")
	ErrDuplicate    = errors.New("shardkey: duplicate dataset")
	ErrSelf         = errors.New("shardkey: dataset colocates with itself")
	ErrUnknown      = errors.New("shardkey: unknown colocation target")
	ErrKindMismatch = errors.New("shardkey: colocated datasets need the same key kind")
	ErrZoneMismatch = errors.New("shardkey: colocated datasets need the same zone scope")
	ErrEmptyLoad    = errors.New("shardkey: no partition load")
	ErrCapacity     = errors.New("shardkey: capacity must be positive")
	ErrNegativeLoad = errors.New("shardkey: load must not be negative")
	ErrNoCandidate  = errors.New("shardkey: no candidate key")
	ErrShare        = errors.New("shardkey: max share must be within 0..1")
)

func validKind(k Kind) bool {
	switch k {
	case KindPlayer, KindAccount, KindZone, KindGuild:
		return true
	}
	return false
}

// Dataset is one table or aggregate whose rows must be routed together.
// Colocate names datasets read in the same operation. The promise is checked
// as a whole catalog, because a target may be registered after its reader.
type Dataset struct {
	Name      string
	Kind      Kind
	ZoneBound bool
	Colocate  []string
}

type Catalog struct {
	datasets map[string]Dataset
}

func NewCatalog() *Catalog {
	return &Catalog{datasets: make(map[string]Dataset)}
}

// Add registers one dataset. Colocation targets are not resolved here so a
// catalog can be loaded in any order; Validate is the gate before use.
func (c *Catalog) Add(d Dataset) error {
	if d.Name == "" {
		return ErrEmptyName
	}
	if !validKind(d.Kind) {
		return fmt.Errorf("%w: %q", ErrUnknownKind, d.Kind)
	}
	if _, ok := c.datasets[d.Name]; ok {
		return fmt.Errorf("%w: %q", ErrDuplicate, d.Name)
	}
	for _, target := range d.Colocate {
		if target == d.Name {
			return fmt.Errorf("%w: %q", ErrSelf, d.Name)
		}
	}
	copied := d
	copied.Colocate = append([]string(nil), d.Colocate...)
	c.datasets[d.Name] = copied
	return nil
}

// Names returns registered dataset names in sorted order.
func (c *Catalog) Names() []string {
	out := make([]string, 0, len(c.datasets))
	for name := range c.datasets {
		out = append(out, name)
	}
	sort.Strings(out)
	return out
}

// Validate checks every colocation promise. A missing target is an error, not
// a warning: a promise that exists only in one dataset's comment is not a
// constraint, and the missing side is exactly the side that will fan out.
func (c *Catalog) Validate() []error {
	var errs []error
	for _, name := range c.Names() {
		d := c.datasets[name]
		for _, target := range d.Colocate {
			other, ok := c.datasets[target]
			if !ok {
				errs = append(errs, fmt.Errorf("%w: %s -> %s", ErrUnknown, name, target))
				continue
			}
			if other.Kind != d.Kind {
				errs = append(errs, fmt.Errorf("%w: %s(%s) -> %s(%s)",
					ErrKindMismatch, name, d.Kind, target, other.Kind))
			}
			if other.ZoneBound != d.ZoneBound {
				errs = append(errs, fmt.Errorf("%w: %s -> %s", ErrZoneMismatch, name, target))
			}
		}
	}
	return errs
}

// Hotspot summarises partition load. Skew is Max/Mean, not max minus mean, so
// it stays comparable as traffic grows. Overloaded is a hard capacity check,
// never an average: one hot shard can fail while the fleet looks idle.
type Hotspot struct {
	Total      int64
	Mean       float64
	Max        int64
	Hottest    int
	Skew       float64
	Overloaded bool
}

func Estimate(loads []int64, capacity int64) (Hotspot, error) {
	if len(loads) == 0 {
		return Hotspot{}, ErrEmptyLoad
	}
	if capacity <= 0 {
		return Hotspot{}, ErrCapacity
	}
	var total int64
	hottest := 0
	for i, v := range loads {
		if v < 0 {
			return Hotspot{}, fmt.Errorf("%w: partition %d has %d", ErrNegativeLoad, i, v)
		}
		total += v
		if v > loads[hottest] {
			hottest = i
		}
	}
	h := Hotspot{
		Total:   total,
		Mean:    float64(total) / float64(len(loads)),
		Max:     loads[hottest],
		Hottest: hottest,
	}
	if h.Mean > 0 {
		h.Skew = float64(h.Max) / h.Mean
	}
	h.Overloaded = h.Max > capacity
	return h, nil
}

// Candidate is one possible partition key with its observed business costs.
// MaxShare is the busiest key value's share of all traffic, in 0..1.
type Candidate struct {
	Kind        Kind
	Cardinality int64
	MaxShare    float64
	CrossShard  int
	Colocated   bool
}

// Rank orders candidates by business consequence, not hash quality:
// co-location first, then unavoidable scatter-gather, then busiest-key share,
// then cardinality. Callers take Rank[0]; there is no hidden weighted score.
func Rank(candidates []Candidate) ([]Candidate, error) {
	if len(candidates) == 0 {
		return nil, ErrNoCandidate
	}
	out := append([]Candidate(nil), candidates...)
	for _, c := range out {
		if c.MaxShare < 0 || c.MaxShare > 1 {
			return nil, fmt.Errorf("%w: %s=%v", ErrShare, c.Kind, c.MaxShare)
		}
		if c.CrossShard < 0 {
			return nil, fmt.Errorf("shardkey: negative cross-shard count for %s", c.Kind)
		}
	}
	sort.SliceStable(out, func(i, j int) bool {
		a, b := out[i], out[j]
		if a.Colocated != b.Colocated {
			return a.Colocated
		}
		if a.CrossShard != b.CrossShard {
			return a.CrossShard < b.CrossShard
		}
		if a.MaxShare != b.MaxShare {
			return a.MaxShare < b.MaxShare
		}
		if a.Cardinality != b.Cardinality {
			return a.Cardinality > b.Cardinality
		}
		return a.Kind < b.Kind
	})
	return out, nil
}