sim

package
v0.23.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Apr 10, 2024 License: Apache-2.0 Imports: 35 Imported by: 0

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

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 

type EventDeliverError struct {
	TraceID int // trace id
	SpanID  int // span id
}

EventDeliverError represents the injection of an error.

type EventDeliverReturn 

type EventDeliverReturn struct {
	TraceID int // trace id
	SpanID  int // span id
}

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 Byte 

func Byte() Generator[byte]

Byte returns a Generator that returns bytes equiprobably.

func Filter 

func Filter[T any](gen Generator[T], predicate func(T) bool) Generator[T]

Filter returns a Generator that returns values from the provided generator that satisfy the provided predicate.

func Flip 

func Flip(p float64) Generator[bool]

Flip returns a Generator that returns true with probability p. Flip panics if p is not in the range [0, 1].

func Float64 

func Float64() Generator[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 

func Int() Generator[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 

func NonNegativeInt() Generator[int]

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 

func OneOf[T any](xs ...T) Generator[T]

OneOf returns a Generator that returns one of the provided values equiprobably. OneOf panics if no values are provided.

func Range 

func Range(low, high int) Generator[int]

Range returns a Generator that returns integers equiprobably in the range [low, high). Range panics if low >= high.

func Rune 

func Rune() Generator[rune]

Rune returns a Generator that returns runes equiprobably.

func Slice 

func Slice[T any](size Generator[int], values Generator[T]) Generator[[]T]

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 

func String() Generator[string]

String returns a Generator that returns moderately sized readable strings, with a bias towards smaller strings.

func Weight 

func Weight[T any](choices []Weighted[T]) Generator[T]

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.

func (*Results) Mermaid 

func (r *Results) Mermaid() string

Mermaid returns a mermaid diagram that illustrates an execution history.

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.

func New 

func New(t testing.TB, x Workload, opts Options) *Simulator

New returns a new Simulator that simulates the provided workload.

func (*Simulator) Run 

func (s *Simulator) Run(duration time.Duration) Results

Run runs a simulation for the provided duration.

type Weighted 

type Weighted[T any] struct {
	Weight float64
	Gen    Generator[T]
}

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.

Source Files

View all Source files

Directories

Path Synopsis
internal
bank
Package bank includes an example of how to test Service Weaver applications using the sim package.
 Package bank includes an example of how to test Service Weaver applications using the sim package.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.