《游戏服务端架构·规模化、全球化与成本》2.1 专用服、容器与调度器

Place(request)
   │
   ├─ 逐节点 check()
   │     unhealthy / region / version / affinity / capacity / spread / port
   │     任一不满足 → 记原因，跳过
   │
   ├─ 剩余候选按 best-fit 排序
   │     剩余 CPU 最小 → 剩余内存最小 → 节点 ID 字典序
   │
   └─ 提交：占端口 + 扣资源 + group/zone 计数 + epoch++

// file: internal/dedicatedsched/scheduler.go
// tier: L1
// verify: go test ./internal/dedicatedsched/

package dedicatedsched

import (
	"errors"
	"fmt"
	"maps"
	"sort"
	"strings"
)

var (
	ErrInvalidNode    = errors.New("dedicatedsched: invalid node")
	ErrInvalidRequest = errors.New("dedicatedsched: invalid request")
	ErrDuplicateRoom  = errors.New("dedicatedsched: room already placed")
	ErrUnknownRoom    = errors.New("dedicatedsched: unknown room")
	ErrStaleEpoch     = errors.New("dedicatedsched: stale placement epoch")
	ErrNoCapacity     = errors.New("dedicatedsched: no node satisfies the request")
)

// Node is one scheduling unit: a physical host, a VM, or a container host.
// PortStart/PortEnd describe the UDP segment the node may hand to rooms.
type Node struct {
	ID         string
	Region     string
	Zone       string
	CPUTotal   int
	MemTotalMB int
	PortStart  int
	PortEnd    int
	Versions   []string
	Labels     map[string]string
	Healthy    bool
	CPUTaken   int
	MemTaken   int
	ports      map[int]bool
}

func (n *Node) supports(version string) bool {
	for _, v := range n.Versions {
		if v == version {
			return true
		}
	}
	return false
}

func (n *Node) freePort() (int, bool) {
	if n.PortStart <= 0 || n.PortEnd < n.PortStart {
		return 0, false
	}
	for p := n.PortStart; p <= n.PortEnd; p++ {
		if !n.ports[p] {
			return p, true
		}
	}
	return 0, false
}

// Request is one room placement. Spread asks the scheduler to keep every room
// of the same Group in a different zone; Affinity pins the node labels.
type Request struct {
	RoomID   string
	Region   string
	Version  string
	Type     string
	CPU      int
	MemMB    int
	NeedUDP  bool
	Group    string
	Spread   bool
	Affinity map[string]string
}

type Placement struct {
	RoomID  string
	NodeID  string
	Zone    string
	Group   string
	CPU     int
	MemMB   int
	UDPPort int
	Epoch   uint64
}

type Scheduler struct {
	nodes  map[string]*Node
	byRoom map[string]Placement
	group  map[string]map[string]int // group -> zone -> placements
	epoch  uint64
}

func New() *Scheduler {
	return &Scheduler{
		nodes:  map[string]*Node{},
		byRoom: map[string]Placement{},
		group:  map[string]map[string]int{},
	}
}

func (s *Scheduler) AddNode(n Node) error {
	if n.ID == "" || n.Region == "" || n.Zone == "" || n.CPUTotal <= 0 || n.MemTotalMB <= 0 {
		return ErrInvalidNode
	}
	if n.PortStart <= 0 || n.PortEnd < n.PortStart {
		return ErrInvalidNode
	}
	if old, ok := s.nodes[n.ID]; ok && old.Healthy {
		return fmt.Errorf("%w: %s", ErrInvalidNode, n.ID)
	}
	n.Healthy = true
	n.CPUTaken, n.MemTaken = 0, 0
	n.Versions = append([]string(nil), n.Versions...)
	n.Labels = maps.Clone(n.Labels)
	n.ports = map[int]bool{}
	s.nodes[n.ID] = &n
	return nil
}

func (s *Scheduler) nodeIDs() []string {
	ids := make([]string, 0, len(s.nodes))
	for id := range s.nodes {
		ids = append(ids, id)
	}
	sort.Strings(ids)
	return ids
}

// check returns an empty reason when the node can host the request, otherwise
// a short machine-readable cause used by Explain and by the capacity report.
func (s *Scheduler) check(n *Node, r Request) (int, string) {
	if !n.Healthy {
		return 0, "unhealthy"
	}
	if n.Region != r.Region {
		return 0, "region"
	}
	if !n.supports(r.Version) {
		return 0, "version"
	}
	for k, v := range r.Affinity {
		if n.Labels[k] != v {
			return 0, "affinity:" + k
		}
	}
	if n.CPUTotal-n.CPUTaken < r.CPU || n.MemTotalMB-n.MemTaken < r.MemMB {
		return 0, "capacity"
	}
	if r.Spread && r.Group != "" && s.group[r.Group][n.Zone] > 0 {
		return 0, "spread"
	}
	if r.NeedUDP {
		port, ok := n.freePort()
		if !ok {
			return 0, "port"
		}
		return port, ""
	}
	return 0, ""
}

// Explain reports why each node accepts or rejects the request without
// mutating any state. It is the input of the "why did placement fail" panel.
func (s *Scheduler) Explain(r Request) map[string]string {
	out := map[string]string{}
	for _, id := range s.nodeIDs() {
		_, reason := s.check(s.nodes[id], r)
		if reason == "" {
			reason = "ok"
		}
		out[id] = reason
	}
	return out
}

// Place selects a node with a best-fit score: the node that leaves the least
// CPU (then memory, then id) after the room fits. Best-fit lowers long-run
// fragmentation at the cost of refusing a large room on a nearly empty host.
func (s *Scheduler) Place(r Request) (Placement, error) {
	if r.RoomID == "" || r.Region == "" || r.Version == "" || r.CPU <= 0 || r.MemMB <= 0 {
		return Placement{}, ErrInvalidRequest
	}
	if _, ok := s.byRoom[r.RoomID]; ok {
		return Placement{}, ErrDuplicateRoom
	}
	var best *Node
	var bestPort, bestCPU, bestMem int
	for _, id := range s.nodeIDs() {
		n := s.nodes[id]
		port, reason := s.check(n, r)
		if reason != "" {
			continue
		}
		leftCPU := n.CPUTotal - n.CPUTaken - r.CPU
		leftMem := n.MemTotalMB - n.MemTaken - r.MemMB
		if best == nil || leftCPU < bestCPU ||
			(leftCPU == bestCPU && (leftMem < bestMem ||
				(leftMem == bestMem && n.ID < best.ID))) {
			best, bestPort, bestCPU, bestMem = n, port, leftCPU, leftMem
		}
	}
	if best == nil {
		return Placement{}, fmt.Errorf("%w: %s", ErrNoCapacity, s.reasonSummary(r))
	}
	s.epoch++
	if r.NeedUDP {
		best.ports[bestPort] = true
	}
	best.CPUTaken += r.CPU
	best.MemTaken += r.MemMB
	if r.Group != "" {
		if s.group[r.Group] == nil {
			s.group[r.Group] = map[string]int{}
		}
		s.group[r.Group][best.Zone]++
	}
	p := Placement{RoomID: r.RoomID, NodeID: best.ID, Zone: best.Zone, Group: r.Group,
		CPU: r.CPU, MemMB: r.MemMB, UDPPort: bestPort, Epoch: s.epoch}
	s.byRoom[r.RoomID] = p
	return p, nil
}

func (s *Scheduler) reasonSummary(r Request) string {
	counts := map[string]int{}
	for _, reason := range s.Explain(r) {
		if reason != "ok" {
			counts[reason]++
		}
	}
	if len(counts) == 0 {
		return "no node registered"
	}
	parts := make([]string, 0, len(counts))
	for reason, n := range counts {
		parts = append(parts, fmt.Sprintf("%s=%d", reason, n))
	}
	sort.Strings(parts)
	return strings.Join(parts, ",")
}

// Release frees a room. The epoch prevents a late release from deleting a
// newer placement that reused the same room id after a crash.
func (s *Scheduler) Release(roomID string, epoch uint64) error {
	p, ok := s.byRoom[roomID]
	if !ok {
		return ErrUnknownRoom
	}
	if p.Epoch != epoch {
		return ErrStaleEpoch
	}
	s.free(p)
	delete(s.byRoom, roomID)
	return nil
}

func (s *Scheduler) free(p Placement) {
	if n := s.nodes[p.NodeID]; n != nil {
		if p.UDPPort > 0 {
			delete(n.ports, p.UDPPort)
		}
		n.CPUTaken -= p.CPU
		n.MemTaken -= p.MemMB
	}
	if p.Group != "" && s.group[p.Group] != nil {
		s.group[p.Group][p.Zone]--
		if s.group[p.Group][p.Zone] <= 0 {
			delete(s.group[p.Group], p.Zone)
		}
	}
}

// FailNode marks a node unhealthy and returns every placement that must be
// re-queued. The caller re-places them elsewhere or returns players to match.
func (s *Scheduler) FailNode(nodeID string) []Placement {
	n, ok := s.nodes[nodeID]
	if !ok {
		return nil
	}
	n.Healthy = false
	var out []Placement
	for room, p := range s.byRoom {
		if p.NodeID != nodeID {
			continue
		}
		out = append(out, p)
		s.free(p)
		delete(s.byRoom, room)
	}
	n.CPUTaken, n.MemTaken = 0, 0
	n.ports = map[int]bool{}
	sort.Slice(out, func(i, j int) bool { return out[i].RoomID < out[j].RoomID })
	return out
}