《游戏服务端架构·品类、状态与拓扑》11.3 故障域与爆炸半径

爆炸半径 = 单个故障域失效时损失的容量 / 总容量

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

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

// Level runs from the smallest failure domain to the largest.
type Level int

const (
	LevelProcess Level = iota
	LevelNode
	LevelRack
	LevelZone
	LevelRegion
	levelCount
)

var levelNames = [...]string{"process", "node", "rack", "zone", "region"}

func (l Level) String() string { return levelNames[l] }

var (
	ErrBlankID          = errors.New("faultdomain: node id must not be blank")
	ErrBadLevel         = errors.New("faultdomain: level out of range")
	ErrNegativeCapacity = errors.New("faultdomain: capacity must not be negative")
	ErrDuplicateNode    = errors.New("faultdomain: duplicate node id")
	ErrUnknownParent    = errors.New("faultdomain: parent does not exist")
	ErrUnknownNode      = errors.New("faultdomain: unknown node")
	ErrLevelOrder       = errors.New("faultdomain: child level must be finer than parent level")
)

// Node is a container in the fault-domain tree. Only leaves should carry a
// non-zero capacity; internal nodes describe how leaves fail together.
type Node struct {
	ID       string
	Level    Level
	Parent   string
	Capacity int
}

type Tree struct {
	nodes map[string]Node
}

func NewTree() *Tree {
	return &Tree{nodes: make(map[string]Node)}
}

func (t *Tree) Add(n Node) error {
	if strings.TrimSpace(n.ID) == "" {
		return ErrBlankID
	}
	if n.Level < LevelProcess || n.Level >= levelCount {
		return ErrBadLevel
	}
	if n.Capacity < 0 {
		return ErrNegativeCapacity
	}
	if _, ok := t.nodes[n.ID]; ok {
		return ErrDuplicateNode
	}
	if n.Parent != "" {
		parent, ok := t.nodes[n.Parent]
		if !ok {
			return ErrUnknownParent
		}
		if n.Level >= parent.Level {
			return fmt.Errorf("%w: %s(%s) under %s(%s)", ErrLevelOrder,
				n.ID, n.Level, parent.ID, parent.Level)
		}
	}
	t.nodes[n.ID] = n
	return nil
}

// Impact is one failure: dead nodes, lost capacity and its share of the total.
type Impact struct {
	Failed   string
	Level    Level
	Nodes    []string
	Capacity int
	Ratio    float64
}

func (t *Tree) ImpactOf(id string) (Impact, error) {
	node, ok := t.nodes[id]
	if !ok {
		return Impact{}, ErrUnknownNode
	}
	children := make(map[string][]string, len(t.nodes))
	total := 0
	for nodeID, candidate := range t.nodes {
		total += candidate.Capacity
		if candidate.Parent != "" {
			children[candidate.Parent] = append(children[candidate.Parent], nodeID)
		}
	}
	var nodes []string
	var walk func(string)
	walk = func(nodeID string) {
		nodes = append(nodes, nodeID)
		for _, child := range children[nodeID] {
			walk(child)
		}
	}
	walk(id)
	sort.Strings(nodes)
	capacity := 0
	for _, nodeID := range nodes {
		capacity += t.nodes[nodeID].Capacity
	}
	ratio := 0.0
	if total > 0 {
		ratio = float64(capacity) / float64(total)
	}
	return Impact{id, node.Level, nodes, capacity, ratio}, nil
}

// Workload is a set of instances placed on domains. Shared marks a component
// other workloads depend on, such as a session store.
type Workload struct {
	Name      string
	Instances []string
	Shared    bool
}

// Policy is the blast-radius budget. ImpactLevels defaults to process..zone;
// region-wide failure is usually accepted as a business-level risk.
type Policy struct {
	MaxImpactRatio float64
	MinDistinct    map[Level]int
	ImpactLevels   []Level
}

const (
	RuleBlankName       = "blank_name"
	RuleNoInstances     = "no_instances"
	RuleUnknownDomain   = "unknown_domain"
	RuleDomainSpread    = "domain_spread"
	RuleImpactBudget    = "impact_budget"
	RuleSharedSingleton = "shared_singleton"
)

type Issue struct {
	Workload string
	Rule     string
	Detail   string
}

func Validate(t *Tree, workloads []Workload, policy Policy) []Issue {
	var issues []Issue
	for _, workload := range workloads {
		name := strings.TrimSpace(workload.Name)
		if name == "" {
			issues = append(issues, Issue{"<unnamed>", RuleBlankName, ""})
			continue
		}
		domains := make([]string, 0, len(workload.Instances))
		domainSeen := make(map[string]bool, len(workload.Instances))
		for _, raw := range workload.Instances {
			domain := strings.TrimSpace(raw)
			if domain == "" {
				continue
			}
			if _, ok := t.nodes[domain]; !ok {
				issues = append(issues, Issue{name, RuleUnknownDomain, domain})
				continue
			}
			if !domainSeen[domain] {
				domainSeen[domain] = true
				domains = append(domains, domain)
			}
		}
		if len(domains) == 0 {
			issues = append(issues, Issue{name, RuleNoInstances, ""})
			continue
		}

		if workload.Shared && distinctAncestors(t, domains, LevelNode) < 2 {
			issues = append(issues, Issue{name, RuleSharedSingleton,
				"shared component has no independent node failure domain"})
		}
		for _, level := range []Level{LevelProcess, LevelNode, LevelRack, LevelZone, LevelRegion} {
			if required := policy.MinDistinct[level]; required > 0 {
				if got := distinctAncestors(t, domains, level); got < required {
					issues = append(issues, Issue{name, RuleDomainSpread,
						fmt.Sprintf("level=%s got=%d want>=%d", level, got, required)})
				}
			}
		}
		if policy.MaxImpactRatio <= 0 {
			continue
		}
		levels := policy.ImpactLevels
		if len(levels) == 0 {
			levels = []Level{LevelProcess, LevelNode, LevelRack, LevelZone}
		}
		for _, level := range levels {
			groups := make(map[string]int)
			for _, domain := range domains {
				if ancestor, ok := t.ancestorAt(domain, level); ok {
					groups[ancestor]++
				}
			}
			worst, worstCount := "", 0
			for ancestor, count := range groups {
				if count > worstCount || (count == worstCount && ancestor < worst) {
					worst, worstCount = ancestor, count
				}
			}
			if worstCount == 0 {
				continue
			}
			ratio := float64(worstCount) / float64(len(domains))
			if ratio > policy.MaxImpactRatio {
				issues = append(issues, Issue{name, RuleImpactBudget,
					fmt.Sprintf("level=%s ancestor=%s replicas=%d/%d ratio=%.2f",
						level, worst, worstCount, len(domains), ratio)})
			}
		}
	}
	sort.Slice(issues, func(i, j int) bool {
		if issues[i].Workload != issues[j].Workload {
			return issues[i].Workload < issues[j].Workload
		}
		if issues[i].Rule != issues[j].Rule {
			return issues[i].Rule < issues[j].Rule
		}
		return issues[i].Detail < issues[j].Detail
	})
	return issues
}

// ancestorAt walks up until it finds level, or reports that level is finer.
func (t *Tree) ancestorAt(id string, level Level) (string, bool) {
	node, ok := t.nodes[id]
	if !ok {
		return "", false
	}
	for {
		if node.Level == level {
			return node.ID, true
		}
		if node.Level > level || node.Parent == "" {
			return "", false
		}
		node = t.nodes[node.Parent]
	}
}

func distinctAncestors(t *Tree, domains []string, level Level) int {
	seen := make(map[string]bool, len(domains))
	for _, domain := range domains {
		if ancestor, ok := t.ancestorAt(domain, level); ok {
			seen[ancestor] = true
		}
	}
	return len(seen)
}

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