testsharder

README

testsharder

testsharder is a tool that takes a single list of tests and splits that list into one or more new lists ("shards") so that each shard only contains tests that run on a single device type.

Specifically, testsharder takes as input (via the -build-dir flag) a fuchsia build out directory containing a tests.json produced by the fuchsia build. tests.json contains a list of JSON objects conforming to the schema of the TestSpec struct from //tools/build/tests.go.

testsharder's output is another JSON file, whose location is specified by the -output-file flag. This file contains a list of JSON objects conforming to the schema of the Shard struct from //tools/integration/testsharder/shard.go. Each shard has a name that will end in a number if there are multiple shards with the same device type, e.g. "QEMU-(1)".

testsharder's primary consumer is the infra recipes, specifically the fuchsia/build recipe. That recipe uses testsharder's output to schedule a set of Swarming tasks, each of which runs the tests from one shard.

Sharding algorithm

testsharder has two flags to control the size of shards:

• -max-shard-size specifies a target number of tests for each shard. If set, testsharder will divide the input tests.json into shards of approximately this size.

• -target-duration-secs specifies a target duration for each shard. If set, testsharder will divide the input tests.json into shards whose tests are expected to complete in approximately this amount of time. See the "Sharding by time" section below for details on how testsharder uses this flag.

It's invalid to specify both of these flags at the same time.

testsharder also has a -max-shards-per-environment flag that sets a hard maximum on the number of shards for each device type. If it's impossible to divide the input tests.json into fewer than the maximum number of shards while satisfying -target-duration-secs or -max-shard-size, some or all of the shards will exceed -target-duration-secs or -max-shard-size.

Sharding by time

Along with tests.json, testsharder also reads a test_durations.json file from the build output directory. This file is copied into the output directory from the //integration/infra/test_durations directory, which contains a file for every infra builder that runs tests using the fuchsia/fuchsia recipe. These files are updated periodically with recent duration data for each test.

Each builder takes the path to its corresponding test duration file as an argument and passes that path into the build via the test_durations_file GN argument. The file is then renamed to test_durations.json and copied into the output directory by the test_durations target from the root //BUILD.gn.

testsharder then reads test_durations.json from the build output directory and uses the duration data to divide tests into shards of approximately equal expected duration, using a greedy approximation algorithm for static multiprocessor scheduling.

Within a shard, tests are ordered by expected duration descending (longest tests first). However, this should be considered an infra implementation detail and is subject to change.

If any test does not appear in test_durations.json (for example, because the duration files have not been updated since it was added) then testsharder will use the duration file entry with name * for that test. That entry's data is an average of all existing tests' data. So any newly added tests will be scheduled close to the middle of one of the shards.

Determinism

Given an input tests.json, test_durations.json, and -multipliers file, testsharder's output is completely deterministic.

However, adding, deleting, or renaming a test can completely change the output. For example, adding a new test that takes an average amount of time will add that test to the middle of one of the shards. This will generally push some faster tests into new shards, leading to a complete reshuffling of all faster tests between shards.

Updates to the duration files may also affect testsharder's output, so duration file updates go through CQ before landing to ensure that they don't cause any ordering-related test breakages.

Test modifiers

Testsharder has an optional -modifiers flag that allows customization of test retry strategies and sharding, such as the MULTIPLY feature and separate sharding of affected tests in CQ.

-modifiers should point to a JSON file containing a list of objects conforming to the TestModifier schema (see test_modifer.go). Each TestModifier applies to a single test or a subset of tests (in order to support fuzzy matching for MULTIPLY) and determines how many times the test should run, and whether the test must pass on every run to be considered successful, or whether it need only pass once.

Documentation

Index

• func AddImageDeps(s *Shard, images []build.Image, pave bool)
• func ApplyRealmLabel(shards []*Shard, realmLabel string)
• func ApplyTestTimeouts(shards []*Shard, perTestTimeout time.Duration)
• func ExtractDeps(shards []*Shard, fuchsiaBuildDir string) error
• func ValidateTests(specs []build.TestSpec, platforms []build.DimensionSet) error
• type Mode
  • func (m *Mode) Set(s string) error
  • func (m *Mode) String() string
• type RunAlgorithm
• type Shard
  • func MakeShards(specs []build.TestSpec, opts *ShardOptions) []*Shard
  • func MultiplyShards(ctx context.Context, shards []*Shard, multipliers []TestModifier, ...) ([]*Shard, error)
  • func ShardAffected(shards []*Shard, modTests []TestModifier, affectedOnly bool) ([]*Shard, error)
  • func WithTargetDuration(shards []*Shard, targetDuration time.Duration, ...) []*Shard
  • func (s *Shard) AddDeps(deps []string)
  • func (s *Shard) CreatePackageRepo() error
• type ShardOptions
• type Test
• type TestDurationsMap
  • func NewTestDurationsMap(durations []build.TestDuration) TestDurationsMap
  • func (m TestDurationsMap) Get(test Test) build.TestDuration
• type TestModifier
  • func AffectedModifiers(testSpecs []build.TestSpec, affectedTestsPath string, ...) ([]TestModifier, error)
  • func LoadTestModifiers(manifestPath string) ([]TestModifier, error)

Functions

func AddImageDeps

func AddImageDeps(s *Shard, images []build.Image, pave bool)

AddImageDeps selects and adds the subset of images needed by a shard to that shard's list of dependencies.

func ApplyRealmLabel

func ApplyRealmLabel(shards []*Shard, realmLabel string)

Applies the realm label to all tests on all shards provided.

func ApplyTestTimeouts

func ApplyTestTimeouts(shards []*Shard, perTestTimeout time.Duration)

ApplyTestTimeouts sets the timeout field on every test to the specified duration.

func ExtractDeps

func ExtractDeps(shards []*Shard, fuchsiaBuildDir string) error

func ValidateTests

func ValidateTests(specs []build.TestSpec, platforms []build.DimensionSet) error

ValidateTests validates a list of test specs against a list of available test platforms.

Types

type Mode

type Mode int

Mode is a mode in which the testsharder can be run.

const (
	// Normal is the default mode in which all tests are sharded, except
	// those excluded by differing tags.
	Normal Mode = iota

	// Restricted is the mode in which auth-needing tests (i.e., those that
	// specify service accounts) are ignored. This mode is useful for
	// running untrusted code.
	Restricted
)

func (*Mode) Set

func (m *Mode) Set(s string) error

Set implements flag.Var.Set.

func (*Mode) String

func (m *Mode) String() string

String implements flag.Var.String.

type RunAlgorithm

type RunAlgorithm string

RunAlgorithm describes how to run a test using the test's `Runs` field.

const (
	// KeepGoing means to run the test for as many times as `Runs`
	// regardless of the result of each test run.
	KeepGoing RunAlgorithm = "KEEP_GOING"
	// StopOnFailure means to try the test up to `Runs` times
	// and to break on the first failure.
	StopOnFailure RunAlgorithm = "STOP_ON_FAILURE"
	// StopOnSuccess means to try the test up to `Runs` times
	// and to break on the first success.
	StopOnSuccess RunAlgorithm = "STOP_ON_SUCCESS"
)

type Shard

type Shard struct {
	// Name is the identifier for the shard.
	Name string `json:"name"`

	// Tests is the set of tests to be executed in this shard.
	Tests []Test `json:"tests"`

	// Env is a generalized notion of the execution environment for the shard.
	Env build.Environment `json:"environment"`

	// Deps is the list of runtime dependencies required to be present on the host
	// at shard execution time. It is a list of paths relative to the fuchsia
	// build directory.
	Deps []string `json:"deps,omitempty"`

	// PkgRepo is the path to the shard-specific package repository. It is
	// relative to the fuchsia build directory, and is a directory itself.
	PkgRepo string `json:"pkg_repo,omitempty"`

	// TimeoutSecs is the execution timeout, in seconds, that should be set for
	// the task that runs the shard. It's computed dynamically based on the
	// expected runtime of the tests.
	TimeoutSecs int `json:"timeout_secs"`
}

Shard represents a set of tests with a common execution environment.

func MakeShards

func MakeShards(specs []build.TestSpec, opts *ShardOptions) []*Shard

MakeShards returns the list of shards associated with a given build. A single output shard will contain only tests that have the same environment.

func MultiplyShards

func MultiplyShards(
	ctx context.Context,
	shards []*Shard,
	multipliers []TestModifier,
	testDurations TestDurationsMap,

	targetDuration time.Duration,
	targetTestCount int,
) ([]*Shard, error)

MultiplyShards appends new shards to shards where each new shard contains one test repeated multiple times according to the specifications in multipliers. It also removes all multiplied tests from the input shards.

func ShardAffected

func ShardAffected(shards []*Shard, modTests []TestModifier, affectedOnly bool) ([]*Shard, error)

ShardAffected separates the affected tests into separate shards. If `affectedOnly` is true, it will only return the affected test shards.

func WithTargetDuration

func WithTargetDuration(
	shards []*Shard,
	targetDuration time.Duration,
	targetTestCount,
	maxShardsPerEnvironment int,
	testDurations TestDurationsMap,
) []*Shard

WithTargetDuration returns a list of shards such that all shards are expected to complete in approximately `targetDuration` time. If targetDuration <= 0, just returns its input. Alternatively, accepts a `targetTestCount` argument for backwards compatibility.

Each resulting shard will have a TimeoutSecs field populated dynamically based on the expected total runtime of its tests. The caller can choose to respect and enforce this timeout, or ignore it.

func (*Shard) AddDeps

func (s *Shard) AddDeps(deps []string)

AddDeps adds a set of runtime dependencies to the shard. It ensures no duplicates and a stable ordering.

func (*Shard) CreatePackageRepo

func (s *Shard) CreatePackageRepo() error

CreatePackageRepo creates a package repository for the given shard.

type ShardOptions

type ShardOptions struct {
	// Mode is a general mode in which the testsharder will be run. See mode.go
	// for more details.
	Mode Mode

	// Tags is the list of tags that the sharded Environments must match; those
	// that don't match all tags will be ignored.
	Tags []string
}

ShardOptions parametrize sharding behavior.

type Test

type Test struct {
	build.Test

	// Runs is the number of times this test should be run.
	Runs int `json:"runs,omitempty"`

	// RunAlgorithm determines how `Runs` will be used to run the test.
	RunAlgorithm RunAlgorithm `json:"run_algorithm,omitempty"`

	// RealmLabel is an optional arg passed to run-test-component to specify a
	// realm.
	RealmLabel string `json:"realm_label,omitempty"`

	// StopRepeatingAfterSecs is the duration for which to repeatedly run a
	// test.
	StopRepeatingAfterSecs int `json:"stop_repeating_after_secs,omitempty"`

	// Timeout is the timeout that should be set for each run of this test.
	Timeout time.Duration `json:"timeout_nanos,omitempty"`
}

Test is a struct used to hold information about a build.Test and how to run it.

type TestDurationsMap

type TestDurationsMap map[string]build.TestDuration

TestDurationsMap maps test names to corresponding test duration data.

func NewTestDurationsMap

func NewTestDurationsMap(durations []build.TestDuration) TestDurationsMap

func (TestDurationsMap) Get

func (m TestDurationsMap) Get(test Test) build.TestDuration

Get returns the duration data for a given test. If the test is not included in the durations map, the default duration data is returned instead.

type TestModifier

type TestModifier struct {
	// Name is the name of the test.
	Name string `json:"name"`

	// OS is the operating system in which this test must be executed. If not
	// present, this multiplier will match tests from any operating system.
	OS string `json:"os,omitempty"`

	// TotalRuns is the number of times to run the test. If not present,
	// testsharder will try to produce exactly one full shard for this test
	// using historical test duration data.
	TotalRuns int `json:"total_runs,omitempty"`

	// Affected specifies whether the test is an affected test. If affected,
	// it will be run in a separate shard than the unaffected tests.
	Affected bool `json:"affected,omitempty"`

	// MaxAttempts is the max number of times to run this test if it fails.
	// This is the max attempts per run as specified by the `TotalRuns` field.
	MaxAttempts int `json:"max_attempts,omitempty"`
}

TestModifier is the specification for a single test and the number of times it should be run.

func AffectedModifiers

func AffectedModifiers(testSpecs []build.TestSpec, affectedTestsPath string, maxAttempts, multiplyThreshold int) ([]TestModifier, error)

AffectedModifiers returns modifiers for tests that are in both testSpecs and affectedTestsPath. affectedTestsPath is the path to a file containing test names separated by `\n`. maxAttempts will be applied to any test that is not multiplied. Tests will be considered for multiplication only if num affected tests <= multiplyThreshold.

func LoadTestModifiers

func LoadTestModifiers(manifestPath string) ([]TestModifier, error)

LoadTestModifiers loads a set of test modifiers from a json manifest.