Skip to content

Git designed for AI agents.

22.1 KB
Raw Blame
package main

import (
	"cmp"
	"context"
	"errors"
	"fmt"
	"math"
	"math/rand"
	"regexp"
	"slices"
	"sort"
	"strings"
	"sync"
	"time"
)

// Mode selects how the agents land their changes.
type Mode string

const (
	// ModeLand lands every change with UserLand (rebase). A change that
	// conflicts with the tip fails.
	ModeLand Mode = "land"
	// ModeLandResolve lands with UserLand and asks the server to resolve
	// merge conflicts through the configured resolver.
	ModeLandResolve Mode = "land-resolve"
	// ModeLandBatch lands like ModeLand, but the server is expected to batch
	// the concurrent lands of one branch into a single reference update (the
	// land lanes of phase 3). The client sends the same requests; the batch
	// placement of every land is reported in the result.
	ModeLandBatch Mode = "land-batch"
	// ModeQueue simulates a serialized merge queue: one change at a time is
	// landed, then tested for TestDuration before the next one starts.
	ModeQueue Mode = "queue"
)

// Config describes one benchmark run.
type Config struct {
	// Agents is the number of concurrent agents (goroutines).
	Agents int
	// ChangesPerAgent is the number of changes each agent commits and lands.
	ChangesPerAgent int
	// ConflictRate is the fraction of changes that also touch the shared
	// region of the shared file. Such changes append to the same place and
	// conflict with each other.
	ConflictRate float64
	// Mode selects the landing mode.
	Mode Mode
	// TestDuration is the simulated test time per change in queue mode.
	TestDuration time.Duration
	// Branch is the branch every change lands on. With Branches greater than
	// one it is the prefix of the branch names (see BranchName).
	Branch string
	// Branches is the number of target branches. The agents are spread over
	// them round robin, so each branch has its own contention. Zero means one.
	Branches int
	// Repos is the number of repositories of a multi-node run (see
	// MultiBackend). Agent a works on repository a modulo Repos, and the agents
	// of each repository are spread over the branches round robin (see
	// TargetOf), so every repository lands on every branch. Zero means one.
	Repos int
	// Seed makes the change plan (which changes conflict) reproducible.
	Seed int64
	// MaxAttempts bounds the server-side compare-and-swap retries of a land.
	// Zero means the server default.
	MaxAttempts int32
}

// Defaults for the benchmark flags.
const (
	DefaultAgents          = 50
	DefaultChangesPerAgent = 10
	// DefaultBranch is not main: main is usually a protected branch (see
	// examples/graft/config.toml), and a run needs a branch of its own.
	DefaultBranch = "bench"
	// agentsDir holds the file of every change (Change.Path).
	agentsDir        = "agents"
	sharedFilePath   = "shared/log.txt"
	sharedFileHeader = "# graft-bench shared log\n"
)

// Validate reports the first invalid field of c.
func (c Config) Validate() error {
	switch {
	case c.Agents < 1:
		return errors.New("agents must be at least 1")
	case c.ChangesPerAgent < 1:
		return errors.New("changes per agent must be at least 1")
	case c.ConflictRate < 0 || c.ConflictRate > 1:
		return errors.New("conflict rate must be between 0 and 1")
	case c.TestDuration < 0:
		return errors.New("test duration must not be negative")
	case c.Branch == "":
		return errors.New("branch must not be empty")
	case c.Branches < 0:
		return errors.New("branches must not be negative")
	case c.BranchCount() > c.Agents:
		return fmt.Errorf("branches (%d) must not exceed agents (%d): a branch without agents is never landed on", c.BranchCount(), c.Agents)
	case c.Repos < 0:
		return errors.New("repos must not be negative")
	case c.BranchCount() > c.Agents/c.RepoCount():
		// The repository with the fewest agents has Agents/RepoCount of them.
		return fmt.Errorf("branches (%d) times repos (%d) must not exceed agents (%d): every repository needs an agent on every branch",
			c.BranchCount(), c.RepoCount(), c.Agents)
	case c.MaxAttempts < 0:
		return errors.New("max attempts must not be negative")
	}

	switch c.Mode {
	case ModeLand, ModeLandResolve, ModeLandBatch, ModeQueue:
	default:
		return fmt.Errorf("unknown mode %q, want land, land-resolve, land-batch or queue", c.Mode)
	}

	if c.TestDuration > 0 && c.Mode != ModeQueue {
		return errors.New("test duration is only used in queue mode")
	}

	return nil
}

// BranchCount is the number of target branches of the run.
func (c Config) BranchCount() int {
	if c.Branches < 1 {
		return 1
	}
	return c.Branches
}

// BranchName is the name of target branch i, from 0 to BranchCount-1. A
// single branch keeps the name Branch.
func (c Config) BranchName(i int) string {
	if c.BranchCount() == 1 {
		return c.Branch
	}
	return fmt.Sprintf("%s-%02d", c.Branch, i)
}

// RepoCount is the number of repositories of the run.
func (c Config) RepoCount() int {
	if c.Repos < 1 {
		return 1
	}
	return c.Repos
}

// TargetOf is the branch the changes of agent land on. The agents of one
// repository are spread over the branches round robin by their index within
// the repository, agent / RepoCount. Spreading them by agent alone would
// correlate the branch with the repository whenever the numbers of
// repositories and branches share a factor: with 2 of each, every repository
// would only ever land on one branch.
func (c Config) TargetOf(agent int) string {
	return c.BranchName((agent / c.RepoCount()) % c.BranchCount())
}

// Change is one planned change of one agent.
type Change struct {
	Agent int
	Seq   int
	// Target is the branch the change lands on. It names the private branches
	// of the change, so runs on different branches never collide.
	Target string
	// Shared is true if the change also touches the shared file region.
	Shared bool
}

// Path is the file the change adds. Every change has its own path, so only
// the shared region can conflict.
func (c Change) Path() string {
	return fmt.Sprintf("%s/agent-%03d/change-%04d.txt", agentsDir, c.Agent, c.Seq)
}

// Content is the content of the file the change adds.
func (c Change) Content() []byte {
	return []byte(fmt.Sprintf("agent %d change %d\n", c.Agent, c.Seq))
}

// SharedContent is the content of the shared file after the change. It
// appends one line to the shared header, so two shared changes made from the
// same base conflict unless the server resolves them.
func (c Change) SharedContent() []byte {
	return []byte(fmt.Sprintf("%sagent %d change %d\n", sharedFileHeader, c.Agent, c.Seq))
}

// plan decides, deterministically from the seed, which changes are shared.
func plan(cfg Config, agent int) []Change {
	rng := rand.New(rand.NewSource(cfg.Seed + int64(agent)*7919))

	changes := make([]Change, 0, cfg.ChangesPerAgent)
	for seq := 1; seq <= cfg.ChangesPerAgent; seq++ {
		changes = append(changes, Change{
			Agent:  agent,
			Seq:    seq,
			Target: cfg.TargetOf(agent),
			Shared: rng.Float64() < cfg.ConflictRate,
		})
	}

	return changes
}

// Backend performs the server calls of a benchmark run. The sdk backend is
// used by the command; tests use fakes.
type Backend interface {
	// Prepare makes sure the branch cfg.Branch exists and returns its tip.
	Prepare(ctx context.Context, cfg Config) (base string, err error)
	// Commit writes the change on top of base and returns the commit OID.
	Commit(ctx context.Context, c Change, base string) (commit string, err error)
	// Land lands commit on the branch c.Target.
	Land(ctx context.Context, cfg Config, c Change, commit string) (LandOutcome, error)
}

// LandOutcome is what a successful or failed land reports back.
type LandOutcome struct {
	Attempts      int32
	Rewritten     bool
	AlreadyLanded bool
	// Conflict is true if the land failed on a merge conflict.
	Conflict bool
	// Resolved is the number of conflicting paths the server resolved.
	Resolved int
	// BatchSize is the number of lands in the batch of this land, and
	// BatchPosition its place in the batch (from 1). Both are zero when the
	// server does not batch.
	BatchSize     int
	BatchPosition int
	// UnavailableRetries is the number of Unavailable answers the client
	// retried before the land succeeded (sdk.UnavailableRetry).
	UnavailableRetries int
}

// Sample is the measurement of one change.
type Sample struct {
	Latency  time.Duration
	Landed   bool
	Conflict bool
	Err      error
	Outcome  LandOutcome
	// Agent is the agent that made the change. Multi-node runs group the
	// samples by the node that serves the agent.
	Agent int
	// CommitLatency is the time of the Commit call, one UserCommitFiles, and
	// Committed reports that it succeeded. LandLatency is the time of the Land
	// call, one UserLand, without the wait of queue mode; it is zero when the
	// change did not get to land.
	CommitLatency time.Duration
	Committed     bool
	LandLatency   time.Duration
}

// The RPCs whose latency a run reports (Result.RPCs).
const (
	rpcCommitFiles = "commit_files"
	rpcLand        = "land"
)

// RPCLatency is the latency of one RPC of a run, as the client measures it
// around each call.
type RPCLatency struct {
	Calls  int `json:"calls"`
	Failed int `json:"failed"`
	// P50MS, P95MS and P99MS are the latency percentiles of the calls that
	// succeeded.
	P50MS float64 `json:"p50_ms"`
	P95MS float64 `json:"p95_ms"`
	P99MS float64 `json:"p99_ms"`
}

// Result is the aggregated outcome of a run. Its JSON form is the output of
// --format json.
//
// The latency percentiles cover the landed changes only: the time a failed
// change spent before it failed is not the time a landed change takes. The
// failed changes have their own percentile, FailedP95MS.
type Result struct {
	// Label names the run in reports, such as "batching-on-50". Empty if the
	// run had no --label.
	Label           string  `json:"label,omitempty"`
	Mode            Mode    `json:"mode"`
	Agents          int     `json:"agents"`
	ChangesPerAgent int     `json:"changes_per_agent"`
	Branches        int     `json:"branches"`
	ConflictRate    float64 `json:"conflict_rate"`
	TestDurationMS  float64 `json:"test_duration_ms"`

	Changes       int   `json:"changes"`
	Landed        int   `json:"landed"`
	AlreadyLanded int   `json:"already_landed"`
	Failed        int   `json:"failed"`
	Conflicts     int   `json:"conflicts"`
	Resolutions   int   `json:"resolutions"`
	Attempts      int64 `json:"attempts"`
	// UnavailableRetries counts the Unavailable answers that the client
	// retried, over the landed changes (a failed land reports none).
	UnavailableRetries int `json:"unavailable_retries"`

	// Contention. ObservedConflictRate is the share of the changes that
	// failed on a merge conflict.
	//
	// Attempts counts the server attempts (compare-and-swap rounds) of every
	// change, landed or failed: a land that gave up because the branch kept
	// moving reports the attempts it made (see failedLandOutcome). Other
	// failed lands report none, since the server does not say. AttemptsPerLand
	// is Attempts divided by the landed changes, so the attempts wasted on
	// failed changes raise it. MaxAttempts is the largest number of attempts
	// of any change, landed or failed.
	ObservedConflictRate float64 `json:"observed_conflict_rate"`
	AttemptsPerLand      float64 `json:"attempts_per_land"`
	MaxAttempts          int32   `json:"max_attempts"`
	// AttemptsHistogram counts the landed changes by their number of server
	// attempts (key: attempts, value: changes). Landed changes that report no
	// attempts are not counted.
	AttemptsHistogram map[int]int `json:"attempts_histogram,omitempty"`
	// FailedAttemptsHistogram counts the failed changes that report attempts
	// by their number of attempts, such as the lands that gave up after
	// max_attempts rounds.
	FailedAttemptsHistogram map[int]int `json:"failed_attempts_histogram,omitempty"`

	// Batching, over the landed changes that report a batch. BatchSizeMax is
	// zero when no land was batched. BatchSizeHistogram counts the landed
	// changes by the size of the batch they landed in (key: size, value:
	// changes); an unbatched server reports size 1.
	BatchSizeMean      float64     `json:"batch_size_mean"`
	BatchSizeMax       int         `json:"batch_size_max"`
	BatchSizeHistogram map[int]int `json:"batch_size_histogram,omitempty"`

	DurationSeconds float64 `json:"duration_seconds"`
	LandsPerMinute  float64 `json:"lands_per_minute"`
	// P50MS, P95MS and P99MS are the latency percentiles of the landed changes.
	P50MS float64 `json:"p50_ms"`
	P95MS float64 `json:"p95_ms"`
	P99MS float64 `json:"p99_ms"`
	// FailedP95MS is the p95 latency of the failed changes, zero if none failed.
	FailedP95MS float64 `json:"failed_p95_ms"`
	// RPCs holds the latency of each RPC of the run by name: commit_files (the
	// UserCommitFiles of every change) and land (the UserLand of every change
	// that was committed).
	RPCs map[string]RPCLatency `json:"rpcs,omitempty"`

	// FailureClasses counts the failed changes by the kind of their failure
	// message, with the object IDs removed (see errorKind).
	FailureClasses map[string]int `json:"failure_classes,omitempty"`
	// Errors holds the first distinct failure messages, for diagnosis.
	Errors []string `json:"errors,omitempty"`

	// Repos is the number of repositories of a multi-node run and Nodes the
	// result of each node (see runMultiNode). Both are empty for a single-node run.
	Repos int          `json:"repos,omitempty"`
	Nodes []NodeResult `json:"nodes,omitempty"`
}

// maxReportedErrors bounds Result.Errors.
const maxReportedErrors = 5

// Run executes the benchmark against be and aggregates the samples.
// Changes are committed concurrently by every agent. Latency runs from the
// start of the commit to the end of the land, so queue waiting is included.
func Run(ctx context.Context, cfg Config, be Backend) (Result, error) {
	if err := cfg.Validate(); err != nil {
		return Result{}, fmt.Errorf("invalid config: %w", err)
	}

	ex, err := execute(ctx, cfg, be)
	if err != nil {
		return Result{}, err
	}

	return ex.summarize(ctx, cfg)
}

// execution is the raw outcome of a run: every sample and the wall time of the
// run.
type execution struct {
	samples []Sample
	elapsed time.Duration
}

// summarize aggregates the samples of the run. It returns an error when ctx
// ended before every change had run.
func (ex execution) summarize(ctx context.Context, cfg Config) (Result, error) {
	res := aggregate(cfg, ex.samples, ex.elapsed)
	if ctx.Err() != nil {
		// The run was interrupted or timed out. The samples are returned, but
		// the run is not a complete measurement even when every change has a
		// sample: a change in flight when the context ended is recorded as a
		// failure, so the samples may be cut short.
		total := cfg.Agents * cfg.ChangesPerAgent
		return res, fmt.Errorf("run stopped after %d of %d changes: %w", len(ex.samples), total, ctx.Err())
	}

	return res, nil
}

// execute prepares the branches of cfg on be and runs every agent of cfg. The
// config must be valid. It fails only when a branch cannot be prepared.
func execute(ctx context.Context, cfg Config, be Backend) (execution, error) {
	bases := make(map[string]string, cfg.BranchCount())
	for i := 0; i < cfg.BranchCount(); i++ {
		branch := cfg.BranchName(i)
		branchCfg := cfg
		branchCfg.Branch = branch
		base, err := be.Prepare(ctx, branchCfg)
		if err != nil {
			return execution{}, fmt.Errorf("prepare branch %s: %w", branch, err)
		}
		bases[branch] = base
	}

	var (
		mu      sync.Mutex
		samples = make([]Sample, 0, cfg.Agents*cfg.ChangesPerAgent)
		// queueMu serializes landing in queue mode, across all branches.
		queueMu sync.Mutex
		wg      sync.WaitGroup
	)

	start := time.Now()
	for agent := 0; agent < cfg.Agents; agent++ {
		wg.Add(1)
		go func(agent int) {
			defer wg.Done()
			for _, c := range plan(cfg, agent) {
				if ctx.Err() != nil {
					return
				}
				s := runChange(ctx, cfg, be, c, bases[c.Target], &queueMu)

				mu.Lock()
				samples = append(samples, s)
				mu.Unlock()
			}
		}(agent)
	}
	wg.Wait()

	return execution{samples: samples, elapsed: time.Since(start)}, nil
}

func runChange(ctx context.Context, cfg Config, be Backend, c Change, base string, queueMu *sync.Mutex) Sample {
	began := time.Now()

	commit, err := be.Commit(ctx, c, base)
	commitLatency := time.Since(began)
	if err != nil {
		return Sample{Latency: commitLatency, CommitLatency: commitLatency, Err: fmt.Errorf("commit: %w", err), Agent: c.Agent}
	}

	if cfg.Mode == ModeQueue {
		queueMu.Lock()
		defer queueMu.Unlock()
	}

	landStart := time.Now()
	outcome, err := be.Land(ctx, cfg, c, commit)
	landLatency := time.Since(landStart)
	if cfg.Mode == ModeQueue && cfg.TestDuration > 0 && err == nil {
		// The simulated test runs while the queue is still held.
		timer := time.NewTimer(cfg.TestDuration)
		select {
		case <-timer.C:
		case <-ctx.Done():
			timer.Stop()
		}
	}

	s := Sample{
		Latency:       time.Since(began),
		Outcome:       outcome,
		Agent:         c.Agent,
		CommitLatency: commitLatency,
		Committed:     true,
		LandLatency:   landLatency,
	}
	switch {
	case err != nil:
		s.Err = fmt.Errorf("land: %w", err)
		s.Conflict = outcome.Conflict
	default:
		s.Landed = true
	}

	return s
}

func aggregate(cfg Config, samples []Sample, elapsed time.Duration) Result {
	res := Result{
		Mode:            cfg.Mode,
		Agents:          cfg.Agents,
		ChangesPerAgent: cfg.ChangesPerAgent,
		Branches:        cfg.BranchCount(),
		ConflictRate:    cfg.ConflictRate,
		TestDurationMS:  float64(cfg.TestDuration) / float64(time.Millisecond),
		Changes:         len(samples),
		DurationSeconds: elapsed.Seconds(),
	}

	var landedMS, failedMS []float64
	var batchSum, batchCount int
	seen := map[string]bool{}
	rpcs := map[string]*rpcSamples{rpcCommitFiles: {}, rpcLand: {}}
	for _, s := range samples {
		ms := float64(s.Latency) / float64(time.Millisecond)
		rpcs[rpcCommitFiles].add(s.CommitLatency, s.Committed)
		if s.Committed {
			rpcs[rpcLand].add(s.LandLatency, s.Landed)
		}
		res.Attempts += int64(s.Outcome.Attempts)
		res.Resolutions += s.Outcome.Resolved
		res.UnavailableRetries += s.Outcome.UnavailableRetries
		if s.Outcome.Attempts > res.MaxAttempts {
			res.MaxAttempts = s.Outcome.Attempts
		}

		if s.Landed {
			res.Landed++
			if s.Outcome.AlreadyLanded {
				res.AlreadyLanded++
			}
			landedMS = append(landedMS, ms)
			if n := s.Outcome.Attempts; n > 0 {
				addCount(&res.AttemptsHistogram, int(n))
			}
			if size := s.Outcome.BatchSize; size > 0 {
				batchSum += size
				batchCount++
				addCount(&res.BatchSizeHistogram, size)
				if size > res.BatchSizeMax {
					res.BatchSizeMax = size
				}
			}
			continue
		}

		res.Failed++
		failedMS = append(failedMS, ms)
		if n := s.Outcome.Attempts; n > 0 {
			addCount(&res.FailedAttemptsHistogram, int(n))
		}
		if s.Conflict {
			res.Conflicts++
		}
		if s.Err != nil {
			// Messages differ by commit ID, so distinct kinds are compared
			// with the IDs removed.
			key := errorKind(s.Err.Error())
			addStringCount(&res.FailureClasses, key)
			if len(res.Errors) < maxReportedErrors && !seen[key] {
				seen[key] = true
				res.Errors = append(res.Errors, s.Err.Error())
			}
		}
	}

	if elapsed > 0 {
		res.LandsPerMinute = float64(res.Landed) / elapsed.Minutes()
	}
	if res.Changes > 0 {
		res.ObservedConflictRate = float64(res.Conflicts) / float64(res.Changes)
	}
	if res.Landed > 0 {
		res.AttemptsPerLand = float64(res.Attempts) / float64(res.Landed)
	}
	if batchCount > 0 {
		res.BatchSizeMean = float64(batchSum) / float64(batchCount)
	}
	res.P50MS = percentile(landedMS, 50)
	res.P95MS = percentile(landedMS, 95)
	res.P99MS = percentile(landedMS, 99)
	res.FailedP95MS = percentile(failedMS, 95)

	for name, r := range rpcs {
		if r.calls == 0 {
			continue
		}
		if res.RPCs == nil {
			res.RPCs = map[string]RPCLatency{}
		}
		res.RPCs[name] = RPCLatency{
			Calls:  r.calls,
			Failed: r.failed,
			P50MS:  percentile(r.succeededMS, 50),
			P95MS:  percentile(r.succeededMS, 95),
			P99MS:  percentile(r.succeededMS, 99),
		}
	}

	return res
}

// rpcSamples collects the calls of one RPC of a run.
type rpcSamples struct {
	calls, failed int
	succeededMS   []float64
}

func (r *rpcSamples) add(latency time.Duration, succeeded bool) {
	r.calls++
	if !succeeded {
		r.failed++
		return
	}
	r.succeededMS = append(r.succeededMS, float64(latency)/float64(time.Millisecond))
}

// formatRPCLatency formats the latency of an RPC of a run for a report.
func formatRPCLatency(r RPCLatency) string {
	return fmt.Sprintf("p50 %.1fms, p95 %.1fms, p99 %.1fms (%d calls, %d failed)", r.P50MS, r.P95MS, r.P99MS, r.Calls, r.Failed)
}

// objectIDPattern matches a SHA-1 or SHA-256 object ID as a whole word.
var objectIDPattern = regexp.MustCompile(`\b[0-9a-f]{40}(?:[0-9a-f]{24})?\b`)

// errorKind returns msg without the object IDs it names, so that the same
// failure on different commits has one kind.
func errorKind(msg string) string {
	return objectIDPattern.ReplaceAllString(msg, "<oid>")
}

// addCount increments the count of key in *counts, creating the map if needed.
func addCount(counts *map[int]int, key int) {
	if *counts == nil {
		*counts = map[int]int{}
	}
	(*counts)[key]++
}

// addStringCount is addCount for string keys.
func addStringCount(counts *map[string]int, key string) {
	if *counts == nil {
		*counts = map[string]int{}
	}
	(*counts)[key]++
}

// formatHistogram renders a histogram as "key: count" pairs in key order, or
// "-" if it is empty.
func formatHistogram(h map[int]int) string {
	if len(h) == 0 {
		return "-"
	}

	parts := make([]string, 0, len(h))
	for _, k := range sortedKeys(h) {
		parts = append(parts, fmt.Sprintf("%d: %d", k, h[k]))
	}

	return strings.Join(parts, ", ")
}

// sortedKeys returns the keys of m in ascending order.
func sortedKeys[K cmp.Ordered, V any](m map[K]V) []K {
	keys := make([]K, 0, len(m))
	for k := range m {
		keys = append(keys, k)
	}
	slices.Sort(keys)

	return keys
}

// percentile returns the nearest-rank p-th percentile of values, or 0 if
// there are none. values is not modified.
//
// The nearest rank of p percent of n values is ceil(p*n/100): the smallest
// value such that at least p percent of the values are less than or equal to
// it. For whole percentages p*n is exact, so the ceiling has no rounding error.
func percentile(values []float64, p float64) float64 {
	if len(values) == 0 {
		return 0
	}

	sorted := append([]float64(nil), values...)
	sort.Float64s(sorted)

	rank := int(math.Ceil(p*float64(len(sorted))/100)) - 1
	if rank < 0 {
		rank = 0
	}
	if rank >= len(sorted) {
		rank = len(sorted) - 1
	}

	return sorted[rank]
}