Documentation ¶
Overview ¶
Package sim implements deterministic simulation.
[Deterministic simulation]1 is a type of randomized testing in which millions of random operations are run against a system (with randomly injected failures) in an attempt to find bugs. See serviceweaver.dev/blog/testing.html for an overview of determistic simulation and its implementation in the sim package.
Generators ¶
A key component of deterministic simulation is the ability to deterministically generate "random" values. We accomplish this with the Generator interface:
type Generator[T any] interface { Generate(*rand.Rand) T }
A Generator[T] generates random values of type T. For example, the Int function returns a Generator[int] that generates random integers.
While random, a Generator is also deterministic. Given a random number generator with a particular seed, a Generator will always produce the same value:
// x and y are always equal. var gen Gen[int] = ... x := gen.Generate(rand.New(rand.NewSource(42))) y := gen.Generate(rand.New(rand.NewSource(42)))
The sim package includes generators that generate booleans, ints, floats, runes, strings, slices, and maps (e.g., Flip, Int, Float64, Rune, String, Range, Map). It also contains generator combinators that combine existing generators into new generators (e.g., OneOf, Weight, Filter). You can also implement your own custom generators by implementing the Generator interface.
Workloads ¶
Deterministic simulation verifies a system by running random operations against the system, checking for invariant violations along the way. A workload defines the set of operations to run and the set of invariants to check.
Concretely, a workload is a struct that implements the Workload interface. When a simulator executes a workload, it will randomly call the exported methods of the struct with randomly generated values. We call these methods *operations*. If an operation ever encounters an invariant violation, it returns a non-nil error and the simulation is aborted.
Consider the following workload as an example.
func even(x int) bool { return x%2 == 0 } type EvenWorkload struct { x int } func (e *EvenWorkload) Add(_ context.Context, y int) error { e.x = e.x + y if !even(e.x) { return fmt.Errorf("%d is not even", e.x) } return nil } func (e *EvenWorkload) Multiply(_ context.Context, y int) error { e.x = e.x * y if !even(e.x) { return fmt.Errorf("%d is not even", e.x) } return nil }
An EvenWorkload has an integer x as state and defines two operations: Add and Multiply. Add adds a value to x, and Multiply multiplies x. Both operations check the invariant that x is even. Of course, this invariant does not hold if we add arbitrary values to x.
However, we control the arguments on which which operations are called. Specifically, we add an Init method that registers a set of generators. The simulator will call the workload's operations on values produced by these generators.
func (e *EvenWorkload) Init(r sim.Registrar) error { r.RegisterGenerators("Add", sim.Filter(sim.Int(), even)) r.RegisterGenerators("Multiply", sim.Int()) return nil }
Note that we only call the Add operation on even integers. Finally, we can construct a simulator and simulate the EvenWorkload.
func TestEvenWorkload(t *testing.T) { s := sim.New(t, &EvenWorkload{}, sim.Options{}) r := s.Run(5 * time.Second) if r.Err != nil { t.Fatal(r.Err) } }
In this trivial example, our workload did not use any Service Weaver components, but most realistic workloads do. A workload can get a reference to a component using weaver.Ref. See serviceweaver.dev/blog/testing.html for a complete example.
Graveyard ¶
When the simulator runs a failed execution, it persists the failing inputs to disk. The collection of saved failing inputs is called a *graveyard*, and each individual entry is called a *graveyard entry*. When a simulator is created, the first thing it does is load and re-simulate all graveyard entries.
We borrow the design of go's fuzzing library's corpus with only minor changes 2. When a simulator runs as part of a test named TestFoo, it stores its graveyard entries in testdata/sim/TestFoo. Every graveyard entry is a JSON file. Filenames are derived from the hash of the contents of the graveyard entry. Here's an example testdata directory:
testdata/ └── sim ├── TestCancelledSimulation │ └── a52f5ec5f94e674d.json ├── TestSimulateGraveyardEntries │ ├── 2bfe847328319dae.json │ └── a52f5ec5f94e674d.json └── TestUnsuccessfulSimulation ├── 2bfe847328319dae.json └── a52f5ec5f94e674d.json
As with go's fuzzing library, graveyard entries are never garbage collected. Users are responsible for manually deleting graveyard entries when appropriate.
TODO(mwhittaker): Move things to the weavertest package.
Index ¶
- type Event
- type EventCall
- type EventDeliverCall
- type EventDeliverError
- type EventDeliverReturn
- type EventOpFinish
- type EventOpStart
- type EventPanic
- type EventReturn
- type FakeComponent
- type Generator
- func Byte() Generator[byte]
- func Filter[T any](gen Generator[T], predicate func(T) bool) Generator[T]
- func Flip(p float64) Generator[bool]
- func Float64() Generator[float64]
- func Int() Generator[int]
- func Map[K comparable, V any](size Generator[int], keys Generator[K], values Generator[V]) Generator[map[K]V]
- func NonNegativeInt() Generator[int]
- func OneOf[T any](xs ...T) Generator[T]
- func Range(low, high int) Generator[int]
- func Rune() Generator[rune]
- func Slice[T any](size Generator[int], values Generator[T]) Generator[[]T]
- func String() Generator[string]
- func Weight[T any](choices []Weighted[T]) Generator[T]
- type Options
- type Registrar
- type Results
- type Simulator
- type Weighted
- type Workload
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Event ¶
type Event interface {
// contains filtered or unexported methods
}
An Event represents an atomic step of a execution.
type EventCall ¶
type EventCall struct { TraceID int // trace id SpanID int // span id Caller string // calling component (or "op") Replica int // calling component replica (or op number) Component string // component being called Method string // method being called Args []string // method arguments }
EventCall represents a component method call.
type EventDeliverCall ¶
type EventDeliverCall struct { TraceID int // trace id SpanID int // span id Component string // component being called Replica int // component replica being called }
EventDeliverCall represents a component method call being delivered.
type EventDeliverError ¶
EventDeliverError represents the injection of an error.
type EventDeliverReturn ¶
EventDeliverReturn represents the delivery of a method return.
type EventOpFinish ¶
type EventOpFinish struct { TraceID int // trace id SpanID int // span id Error string // returned error message }
EventOpFinish represents the finish of an op.
type EventOpStart ¶
type EventOpStart struct { TraceID int // trace id SpanID int // span id Name string // op name Args []string // op arguments }
EventOpStart represents the start of an op.
type EventPanic ¶
type EventPanic struct { TraceID int // trace id SpanID int // span id Panicker string // panicking component (or "op") Replica int // panicking component replica (or op number) Error string // panic error Stack string // stack trace }
EventPanic represents a panic.
type EventReturn ¶
type EventReturn struct { TraceID int // trace id SpanID int // span id Component string // component returning Replica int // component replica returning Returns []string // return values }
EventReturn represents a component method call returning.
type FakeComponent ¶
type FakeComponent struct {
// contains filtered or unexported fields
}
FakeComponent is a copy of weavertest.FakeComponent. It's needed to access the unexported fields.
TODO(mwhittaker): Remove this once we merge with weavertest.
func Fake ¶
func Fake[T any](impl any) FakeComponent
Fake is a copy of weavertest.Fake.
TODO(mwhittaker): Remove this once we merge with the weavertest package.
type Generator ¶
type Generator[T any] interface { // Generate returns a randomly generated value of type T. While Generate is // "random", it must be deterministic. That is, given the same instance of // *rand.Rand, Generate must always return the same value. // // TODO(mwhittaker): Generate should maybe take something other than a // *rand.Rand? Generate(*rand.Rand) T }
A Generator[T] generates random values of type T.
func Filter ¶
Filter returns a Generator that returns values from the provided generator that satisfy the provided predicate.
func Flip ¶
Flip returns a Generator that returns true with probability p. Flip panics if p is not in the range [0, 1].
func Float64 ¶
Float64 returns a Generator that returns 64-bit floats. Note that Float64 does not return all floats equiprobably. Instead, it biases towards numbers closer to zero and other pathological numbers that are more likely to induce bugs (e.g., NaN, infinity, -infinity, -0).
func Int ¶
Int returns a Generator that returns integers. Note that Int does not return all integers equiprobably. Instead, it biases towards numbers closer to zero and other pathological numbers that are more likely to induce bugs (e.g., math.MaxInt, math.MinInt).
func Map ¶
func Map[K comparable, V any](size Generator[int], keys Generator[K], values Generator[V]) Generator[map[K]V]
Map returns a Generator that returns maps from K to V. The size and contents of the the generated maps are determined by the provided generators.
func NonNegativeInt ¶
NonNegativeInt returns a Generator that returns non-negative integers. Note that NonNegativeInt does not return all numbers. Instead, it biases towards numbers closer to zero and other pathological numbers that are more likely to induce bugs (e.g., math.MaxInt).
func OneOf ¶
OneOf returns a Generator that returns one of the provided values equiprobably. OneOf panics if no values are provided.
func Range ¶
Range returns a Generator that returns integers equiprobably in the range [low, high). Range panics if low >= high.
func Slice ¶
Slice returns a Generator that returns slices of T. The size and contents of the generated slices are determined by the provided generators.
func String ¶
String returns a Generator that returns moderately sized readable strings, with a bias towards smaller strings.
func Weight ¶
Weight returns a Generator that generates values using the provided generators. A generator is chosen with probability proportional to its weight. For example, given the following choices:
- Weighted{1.0, OneOf("a")}
- Weighted{2.0, OneOf("b")}
Weight returns "b" twice as often as it returns "a". Note that the provided weights do not have to sum to 1.
Weight panics if no choices are provided, if any weight is negative, or if the sum of all weight is 0.
type Options ¶
type Options struct { // TOML config file contents. Config string // The number of executions to run in parallel. If Parallelism is 0, the // simulator picks the degree of parallelism. Parallelism int }
Options configure a Simulator.
type Registrar ¶
type Registrar interface { // RegisterFake registers a fake implementation of a component. RegisterFake(FakeComponent) // RegisterGenerators registers generators for a workload method, one // generator per method argument. The number and type of the registered // generators must match the method. For example, given the method: // // Foo(context.Context, int, bool) error // // we must register a Generator[int] and a Generator[bool]: // // var r Registrar = ... // var i Generator[int] = ... // var b Generator[bool] = ... // r.RegisterGenerators("Foo", i, b) // // TODO(mwhittaker): Allow people to register a func(*rand.Rand) T instead // of a Generator[T] for convenience. RegisterGenerators(method string, generators ...any) }
A Registrar is used to register fakes and generators with a Simulator.
type Results ¶
type Results struct { Err error // first non-nil error returned by an op History []Event // a history of the error inducing run, if Err is not nil NumExecutions int // number of executions ran NumOps int // number of ops ran Duration time.Duration // duration of simulation }
Results are the results of simulating a workload.
type Simulator ¶
type Simulator struct {
// contains filtered or unexported fields
}
A Simulator deterministically simulates a Service Weaver application. See the package documentation for instructions on how to use a Simulator.
type Workload ¶
type Workload interface { // Init initializes a workload. The Init method must also register // generators for every exported method. Init(Registrar) error }
A Workload defines the set of operations to run as part of a simulation. Every workload is defined as a named struct. To execute a workload, a simulator constructs an instance of the struct, calls the struct's Init method, and then randomly calls the struct's exported methods. For example, the following is a simple workload:
type myWorkload struct {} func (w *myWorkload) Init(r sim.Registrar) {...} func (w *myWorkload) Foo(context.Context, int) error {...} func (w *myWorkload) Bar(context.Context, bool, string) error {...} func (w *myWorkload) baz(context.Context) error {...}
When this workload is executed, its Foo and Bar methods will be called with random values generated by the generators registered in the Init method (see Registrar for details). Note that unexported methods, like baz, are ignored.
Note that every exported workload method must receive a context.Context as its first argument and must return a single error value. A simulation is aborted when a method returns a non-nil error.
TODO(mwhittaker): For now, the Init method is required. In the future, we could make it optional and use default generators for methods.