《游戏服务端架构·规模化、全球化与成本》12.1 《裂隙战场》的赛区与延迟

input_lag = RTT / 2 + queue_ticks × tick

QUEUED
  └─ score candidates
       ├─ same region ──────────────▶ ROOM_CREATED
       ├─ cross + event window ─────▶ ROOM_CREATED (30Hz)
       └─ cross + ranked / no window ─▶ REJECTED (告知原因)

// file: internal/riftregion/region.go
// tier: L1
// verify: go test ./internal/riftregion/
package riftregion

import (
	"fmt"
	"sort"
	"time"
)

// Decision is the chosen region together with the evidence used to choose it.
type Decision struct {
	RegionID    string
	Zone        Zone
	WorstRTT    time.Duration
	WorstPlayer string
	InputLag    time.Duration
	CrossRegion bool
	Score       time.Duration
	Reasons     []string
}

// Admit picks the region with the lowest worst-player score. It rejects a
// candidate when any player would exceed the fairness cap or the input budget.
// The result is deterministic: ties are broken by region ID.
func Admit(regions []Region, players []Player, table *Table, p Policy) (Decision, error) {
	if err := p.validate(); err != nil {
		return Decision{}, err
	}
	if len(regions) == 0 || len(players) == 0 {
		return Decision{}, fmt.Errorf("%w: need regions and players", ErrBadInput)
	}
	best := Decision{}
	found := false
	for _, r := range regions {
		if err := r.validate(); err != nil {
			return Decision{}, err
		}
		if r.Free() == 0 {
			continue
		}
		d, ok, err := evaluateRegion(r, players, table, p)
		if err != nil {
			return Decision{}, err
		}
		if !ok {
			continue
		}
		if !found || d.Score < best.Score || (d.Score == best.Score && d.RegionID < best.RegionID) {
			best = d
			found = true
		}
	}
	if !found {
		return Decision{}, ErrNoRegion
	}
	return best, nil
}

func evaluateRegion(r Region, players []Player, table *Table, p Policy) (Decision, bool, error) {
	var worst time.Duration
	var worstPlayer string
	cross := false
	bonus := time.Duration(0)
	for _, pl := range players {
		rtt, err := table.RTT(pl.Zone, r.Zone)
		if err != nil {
			return Decision{}, false, err
		}
		if pl.Zone != r.Zone {
			cross = true
		}
		if rtt > worst {
			worst = rtt
			worstPlayer = pl.ID
		}
		if pl.Home == r.ID {
			bonus += p.HomeBonus
		}
	}
	if cross && !p.AllowCrossRegion {
		return Decision{}, false, nil
	}
	if worst > p.MaxWorstRTT {
		return Decision{}, false, nil
	}
	lag := InputLag(worst, p.MaxQueueTicks, p.Tick)
	if lag > p.InputBudget {
		return Decision{}, false, nil
	}
	score := worst - bonus
	if score < 0 {
		score = 0
	}
	return Decision{
		RegionID:    r.ID,
		Zone:        r.Zone,
		WorstRTT:    worst,
		WorstPlayer: worstPlayer,
		InputLag:    lag,
		CrossRegion: cross,
		Score:       score,
		Reasons:     []string{fmt.Sprintf("worst rtt %s, input lag %s", worst, lag)},
	}, true, nil
}

// RegionsNeeded returns how many identical regions a peak needs at a target
// utilization. A 100 percent target is rejected: no headroom is left for one
// region to fail.
func RegionsNeeded(peakRooms, perRegion, targetPercent int) (int, error) {
	if peakRooms <= 0 || perRegion <= 0 {
		return 0, fmt.Errorf("%w: rooms and capacity must be positive", ErrBadInput)
	}
	if targetPercent <= 0 || targetPercent >= 100 {
		return 0, fmt.Errorf("%w: target must be in (0,100)", ErrBadInput)
	}
	usable := perRegion * targetPercent / 100
	if usable == 0 {
		return 0, fmt.Errorf("%w: target leaves no usable capacity", ErrBadInput)
	}
	return (peakRooms + usable - 1) / usable, nil
}

// MergePlan suggests which regions can be drained during a low-peak window.
// It greedily removes the least-loaded region while the remaining capacity at
// the target utilization still holds every committed room. The plan is a
// starting point, not an optimal packing: drain order still has to respect
// events and network topology.
func MergePlan(regions []Region, targetPercent int) (kept, drained []string, err error) {
	if targetPercent <= 0 || targetPercent >= 100 {
		return nil, nil, fmt.Errorf("%w: target must be in (0,100)", ErrBadInput)
	}
	if len(regions) == 0 {
		return nil, nil, fmt.Errorf("%w: no regions", ErrBadInput)
	}
	active := make([]Region, 0, len(regions))
	committed := 0
	for _, r := range regions {
		if err := r.validate(); err != nil {
			return nil, nil, err
		}
		if r.Down {
			if r.Committed > 0 {
				return nil, nil, fmt.Errorf("%w: down region %s still holds rooms", ErrBadInput, r.ID)
			}
			drained = append(drained, r.ID)
			continue
		}
		active = append(active, r)
		committed += r.Committed
	}
	sort.Slice(active, func(i, j int) bool {
		if active[i].Committed != active[j].Committed {
			return active[i].Committed < active[j].Committed
		}
		return active[i].ID < active[j].ID
	})
	live := active
	for len(live) > 1 {
		capacity := 0
		for _, r := range live[1:] {
			capacity += r.Capacity
		}
		if capacity*targetPercent/100 < committed {
			break
		}
		drained = append(drained, live[0].ID)
		live = live[1:]
	}
	for _, r := range live {
		kept = append(kept, r.ID)
	}
	sort.Strings(kept)
	sort.Strings(drained)
	return kept, drained, nil
}