porcupine

README

Porcupine

Porcupine is a fast linearizability checker used in both academia and industry for testing the correctness of distributed systems. It takes a sequential specification as executable Go code, along with a concurrent history, and it determines whether the history is linearizable with respect to the sequential specification. Porcupine also implements a visualizer for histories and linearization points.

(click for interactive version)

Porcupine implements the algorithm described in Faster linearizability checking via P-compositionality, an optimization of the algorithm described in Testing for Linearizability.

Porcupine is faster and can handle more histories than Knossos's linearizability checker. Testing on the data in test_data/jepsen/, Porcupine is generally 1,000x-10,000x faster and has a much smaller memory footprint. On histories where it can take advantage of P-compositionality, Porcupine can be millions of times faster.

Usage

Porcupine takes an executable model of a system along with a history, and it runs a decision procedure to determine if the history is linearizable with respect to the model. Porcupine supports specifying history in two ways, either as a list of operations with given call and return times, or as a list of call/return events in time order. Porcupine can also visualize histories, along with partial linearizations, which may aid in debugging.

See the documentation for how to write a model and specify histories. You can also check out some example implementations of models from the tests.

Once you've written a model and have a history, you can use the CheckOperations and CheckEvents functions to determine if your history is linearizable. If you want to visualize a history, along with partial linearizations, you can use the Visualize function.

Testing linearizability

Suppose we're testing linearizability for operations on a read/write register that's initialized to 0. We write a sequential specification for the register like this:

type registerInput struct {
    op    bool // false = put, true = get
    value int
}

// a sequential specification of a register
registerModel := porcupine.Model{
    Init: func() interface{} {
        return 0
    },
    // step function: takes a state, input, and output, and returns whether it
    // was a legal operation, along with a new state
    Step: func(state, input, output interface{}) (bool, interface{}) {
        regInput := input.(registerInput)
        if regInput.op == false {
            return true, regInput.value // always ok to execute a put
        } else {
            readCorrectValue := output == state
            return readCorrectValue, state // state is unchanged
        }
    },
    // computes a hash for a state (optional field, improves performance)
    Hash: func(state interface{}) uint64 {
        return uint64(state.(int))
    },
}

Suppose we have the following concurrent history from a set of 3 clients. In a row, the first | is when the operation was invoked, and the second | is when the operation returned.

C0:  |-------- put('100') --------|
C1:     |--- get() -> '100' ---|
C2:        |- get() -> '0' -|

We encode this history as follows:

events := []porcupine.Event{
    // C0: put('100')
    {Kind: porcupine.CallEvent, Value: registerInput{false, 100}, Id: 0, ClientId: 0},
    // C1: get()
    {Kind: porcupine.CallEvent, Value: registerInput{true, 0}, Id: 1, ClientId: 1},
    // C2: get()
    {Kind: porcupine.CallEvent, Value: registerInput{true, 0}, Id: 2, ClientId: 2},
    // C2: Completed get() -> '0'
    {Kind: porcupine.ReturnEvent, Value: 0, Id: 2, ClientId: 2},
    // C1: Completed get() -> '100'
    {Kind: porcupine.ReturnEvent, Value: 100, Id: 1, ClientId: 1},
    // C0: Completed put('100')
    {Kind: porcupine.ReturnEvent, Value: 0, Id: 0, ClientId: 0},
}

We can have Porcupine check the linearizability of the history as follows:

ok := porcupine.CheckEvents(registerModel, events)
// returns true

Porcupine can visualize the linearization points as well:

Now, suppose we have another history:

C0:  |---------------- put('200') ----------------|
C1:    |- get() -> '200' -|
C2:                           |- get() -> '0' -|

We can check the history with Porcupine and see that it's not linearizable:

events := []porcupine.Event{
    // C0: put('200')
    {Kind: porcupine.CallEvent, Value: registerInput{false, 200}, Id: 0, ClientId: 0},
    // C1: get()
    {Kind: porcupine.CallEvent, Value: registerInput{true, 0}, Id: 1, ClientId: 1},
    // C1: Completed get() -> '200'
    {Kind: porcupine.ReturnEvent, Value: 200, Id: 1, ClientId: 1},
    // C2: get()
    {Kind: porcupine.CallEvent, Value: registerInput{true, 0}, Id: 2, ClientId: 2},
    // C2: Completed get() -> '0'
    {Kind: porcupine.ReturnEvent, Value: 0, Id: 2, ClientId: 2},
    // C0: Completed put('200')
    {Kind: porcupine.ReturnEvent, Value: 0, Id: 0, ClientId: 0},
}

ok := porcupine.CheckEvents(registerModel, events)
// returns false

See porcupine_test.go for more examples on how to write models and histories.

Visualizing histories

Porcupine provides functionality to visualize histories, along with the linearization (or partial linearizations and illegal linearization points, in the case of a non-linearizable history). The result is an HTML page that draws an interactive visualization using JavaScript. The output looks like this:

You can see the full interactive version here.

The visualization is by partition: all partitions are essentially independent, so with the key-value store example above, operations related to each unique key are in a separate partition.

Statically, the visualization shows all history elements, along with linearization points for each partition. If a partition has no full linearization, the visualization shows the longest partial linearization. It also shows, for each history element, the longest partial linearization containing that event, even if it's not the longest overall partial linearization; these are greyed out by default. It also shows illegal linearization points, history elements that were checked to see if they could occur next but which were illegal to linearize at that point according to the model.

When a history element is hovered over, the visualization highlights the most relevant partial linearization. When it exists, the longest partial linearization containing the event is shown. Otherwise, when it exists, the visualization shows the longest partial linearization that ends with an illegal LP that is the event being hovered over. Hovering over an event also shows a tooltip showing extra information, such as the previous and current states of the state machine, as well as the time the operation was invoked and when it returned. This information is derived from the currently selected linearization.

Clicking on a history element selects it, which highlights the event with a bold border. This has the effect of making the selection of a partial linearization "sticky", so it's possible to move around the history without de-selecting it. Clicking on another history element will select that one instead, and clicking on the background will deselect.

All that's needed to visualize histories is the CheckOperationsVerbose / CheckEventsVerbose functions, which return extra information that's used by the visualization, and the Visualize function, which produces the visualization. For the visualization to be good, it's useful to fill out the DescribeOperation and DescribeState fields of the model. See visualization_test.go for an end-to-end example of how to visualize a history using Porcupine.

You can also add custom annotations to visualizations, as shown in the example above. This can be helpful for attaching debugging information, for example, from servers or the test framework. You can do this using the AddAnnotations method.

Notes

• If Porcupine runs really slowly on your model/history, it may be inevitable, due to state space explosion. See this issue for a discussion of this challenge in the context of a particular model and history.
• When recording timestamps for operations, especially on ARM and other weakly-ordered architectures, you may need to use memory barriers or atomic operations to ensure accurate measurements and avoid spurious linearizability violations. See this issue for details.

Users

Porcupine is used in both academia and industry. It can be helpful to look at existing uses of Porcupine to learn how you can design a robust testing framework with linearizability checking at its core.

• etcd. etcd uses Porcupine's linearizability checker and visualizer in its robustness tests [KubeCon 2023eu talk].
• PingCAP TiPocket. PingCAP uses Porcupine to test the TiDB distributed database.
• Amazon MemoryDB (SIGMOD'24). Amazon uses Porcupine to test MemoryDB consistency.
• S2 Stream Store. S2 uses Porcupine's linearizability checker and visualizer in its linearizability tests.
• LEGOStore (VLDB'22). Porcupine is used to test the linearizability of LEGOStore.
• Resonate. Resonate's test harness uses Porcupine as its linearizability checker.
• MIT 6.5840 (Distributed Systems) key-value store. Porcupine was originally developed for use in MIT's distributed systems class to test the linearizability of the Raft-based distributed key-value store.
• IIT Delhi COL733 (Cloud computing technology fundamentals) object store. The testing harness uses Porcupine to test the linearizability of the strongly-consistent variant of CRAQ.

Does your system use Porcupine? Send a PR to add it to this list!

Citation

@misc{athalye2017porcupine,
  author = {Anish Athalye},
  title = {Porcupine: A fast linearizability checker in {Go}},
  year = {2017},
  howpublished = {\url{https://github.com/anishathalye/porcupine}}
}

License

Copyright (c) Anish Athalye. Released under the MIT License. See LICENSE.md for details.

Documentation

Index

• func CheckEvents(model Model, history []Event) bool
• func CheckEventsVerbose(model Model, history []Event, timeout time.Duration) (CheckResult, LinearizationInfo)
• func CheckOperations(model Model, history []Operation) bool
• func CheckOperationsVerbose(model Model, history []Operation, timeout time.Duration) (CheckResult, LinearizationInfo)
• func Visualize(model Model, info LinearizationInfo, output io.Writer) error
• func VisualizePath(model Model, info LinearizationInfo, path string) error
• type Annotation
• type CheckResult
  • func CheckEventsTimeout(model Model, history []Event, timeout time.Duration) CheckResult
  • func CheckOperationsTimeout(model Model, history []Operation, timeout time.Duration) CheckResult
• type Event
• type EventKind
• type LinearizationInfo
  • func (li *LinearizationInfo) AddAnnotations(annotations []Annotation)
  • func (li *LinearizationInfo) PartialLinearizations() [][][]int
  • func (li *LinearizationInfo) PartialLinearizationsOperations() [][][]Operation
• type Model
• type NondeterministicModel
  • func (nm *NondeterministicModel) ToModel() Model
• type Operation

Functions

func CheckEvents

func CheckEvents(model Model, history []Event) bool

CheckEvents checks whether a history is linearizable.

func CheckEventsVerbose

func CheckEventsVerbose(model Model, history []Event, timeout time.Duration) (CheckResult, LinearizationInfo)

CheckEventsVerbose checks whether a history is linearizable while computing data that can be used to visualize the history and linearization.

The returned LinearizationInfo can be used with Visualize.

func CheckOperations

func CheckOperations(model Model, history []Operation) bool

CheckOperations checks whether a history is linearizable.

func CheckOperationsVerbose

func CheckOperationsVerbose(model Model, history []Operation, timeout time.Duration) (CheckResult, LinearizationInfo)

CheckOperationsVerbose checks whether a history is linearizable while computing data that can be used to visualize the history and linearization.

The returned LinearizationInfo can be used with Visualize.

func Visualize

func Visualize(model Model, info LinearizationInfo, output io.Writer) error

Visualize produces a visualization of a history and (partial) linearization as an HTML file that can be viewed in a web browser.

If the history is linearizable, the visualization shows the linearization of the history. If the history is not linearizable, the visualization shows partial linearizations and illegal linearization points.

To get the LinearizationInfo that this function requires, you can use CheckOperationsVerbose / CheckEventsVerbose.

This function writes the visualization, an HTML file with embedded JavaScript and data, to the given output.

func VisualizePath

func VisualizePath(model Model, info LinearizationInfo, path string) error

VisualizePath is a wrapper around Visualize to write the visualization to a file path.

Types

type Annotation

type Annotation struct {
	ClientId        int
	Tag             string
	Start           int64
	End             int64
	Description     string
	Details         string
	TextColor       string
	BackgroundColor string
	// contains filtered or unexported fields
}

Annotations to add to histories.

Either a ClientId or Tag must be supplied. The End is optional, for "point in time" annotations. If the end is left unspecified, the framework interprets it as Start. The text given in Description is shown in the main visualization, and the text given in Details (optional) is shown in the tooltip for the annotation. TextColor and BackgroundColor are both optional; if specified, they should be valid CSS colors, e.g., "#efaefc".

To attach annotations to a visualization, use LinearizationInfo.AddAnnotations.

type CheckResult

type CheckResult string

A CheckResult is the result of a linearizability check.

Checking for linearizability is decidable, but it is an NP-hard problem, so the checker might take a long time. If a timeout is not given, functions in this package will always return Ok or Illegal, but if a timeout is supplied, then some functions may return Unknown. Depending on the use case, you can interpret an Unknown result as Ok (i.e., the tool didn't find a linearizability violation within the given timeout).

const (
	Unknown CheckResult = "Unknown" // timed out
	Ok      CheckResult = "Ok"
	Illegal CheckResult = "Illegal"
)

func CheckEventsTimeout

func CheckEventsTimeout(model Model, history []Event, timeout time.Duration) CheckResult

CheckEventsTimeout checks whether a history is linearizable, with a timeout.

A timeout of 0 is interpreted as an unlimited timeout.

func CheckOperationsTimeout

func CheckOperationsTimeout(model Model, history []Operation, timeout time.Duration) CheckResult

CheckOperationsTimeout checks whether a history is linearizable, with a timeout.

A timeout of 0 is interpreted as an unlimited timeout.

type Event

type Event struct {
	ClientId int // optional, unless you want a visualization; zero-indexed
	Kind     EventKind
	Value    interface{}
	Id       int
	// Metadata contains arbitrary metadata associated with the operation.
	// It is not used for linearizability checking but can be used for visualization.
	// Can be set on CallEvent or ReturnEvent. If both have metadata, ReturnEvent metadata takes precedence.
	Metadata interface{}
	// contains filtered or unexported fields
}

An Event is an element of a history, a function call event or a return event.

This package supports two different representations of histories, as a sequence of Event or Operation. In the Event representation, function calls and returns are only relatively ordered and do not have absolute timestamps.

The Id field is used to match a function call event with its corresponding return event.

type EventKind

type EventKind bool

An EventKind tags an Event as either a function call or a return.

const (
	CallEvent   EventKind = false
	ReturnEvent EventKind = true
)

type LinearizationInfo

type LinearizationInfo struct {
	// contains filtered or unexported fields
}

func (*LinearizationInfo) AddAnnotations

func (li *LinearizationInfo) AddAnnotations(annotations []Annotation)

AddAnnotations adds extra annotations to a visualization.

This can be used to add extra client operations or it can be used to add standalone annotations with arbitrary tags, e.g., associated with "servers" rather than clients, or even a "test framework".

See documentation on Annotation for what kind of annotations you can add.

func (*LinearizationInfo) PartialLinearizations

func (li *LinearizationInfo) PartialLinearizations() [][][]int

PartialLinearizations returns partial linearizations found during the linearizability check, as sets of operation IDs.

For each partition, it returns a set of possible linearization histories, where each history is represented as a sequence of operation IDs. If the history is linearizable, this will contain a complete linearization. If not linearizable, it contains the maximal partial linearizations found.

func (*LinearizationInfo) PartialLinearizationsOperations

func (li *LinearizationInfo) PartialLinearizationsOperations() [][][]Operation

PartialLinearizationsOperations returns partial linearizations found during the linearizability check, as sets of sequences of Operation.

For each partition, it returns a set of possible linearization histories, where each history is represented as a sequence of Operation. If the history is linearizable, this will contain a complete linearization. If not linearizable, it contains the maximal partial linearizations found.

type Model

type Model struct {
	// Partition functions, such that a history is linearizable if and only
	// if each partition is linearizable. If left nil, this package will
	// skip partitioning.
	Partition      func(history []Operation) [][]Operation
	PartitionEvent func(history []Event) [][]Event
	// Initial state of the system.
	Init func() interface{}
	// Step function for the system. Returns whether or not the system
	// could take this step with the given inputs and outputs and also
	// returns the new state. This function must be a pure function: it
	// cannot mutate the given state.
	Step func(state interface{}, input interface{}, output interface{}) (bool, interface{})
	// StepContext is an optional context-aware Step function. If set, the
	// checker and visualization replay call StepContext instead of Step,
	// allowing the model to stop work promptly when a timeout expires.
	StepContext func(ctx context.Context, state interface{}, input interface{}, output interface{}) (bool, interface{})
	// Equality on states. If left nil, this package will use == as a
	// fallback ([ShallowEqual]).
	Equal func(state1, state2 interface{}) bool
	// Hash returns a hash of the given state. If non-nil, the checker uses
	// it to reduce the number of [Equal] comparisons. Must satisfy the
	// invariant that [Equal] states have equal hashes.
	Hash func(state interface{}) uint64
	// For visualization, describe an operation as a string. For example,
	// "Get('x') -> 'y'". Can be omitted if you're not producing
	// visualizations.
	DescribeOperation func(input interface{}, output interface{}) string
	// For visualization purposes, describe a state as a string. For
	// example, "{'x' -> 'y', 'z' -> 'w'}". Can be omitted if you're not
	// producing visualizations.
	DescribeState func(state interface{}) string
	// For visualization purposes, describe metadata as a string. Can be
	// omitted if you're not producing visualizations.
	DescribeOperationMetadata func(info interface{}) string
	// contains filtered or unexported fields
}

A Model is a sequential specification of a system.

Note: models in this package are expected to be purely functional. That is, the model Step function should not modify the given state (or input or output), but return a new state.

Only the Init, Step (or StepContext), and Equal functions are necessary to specify if you just want to test histories for linearizability.

Implementing the partition functions can greatly improve performance. If you're implementing the partition function, the model Init and Step functions can be per-partition. For example, if your specification is for a key-value store and you partition by key, then the per-partition state representation can just be a single value rather than a map.

Implementing DescribeOperation and DescribeState will produce nicer visualizations.

It may be helpful to look at this package's test code for examples of how to write models, including models that include partition functions.

type NondeterministicModel

type NondeterministicModel struct {
	// Partition functions, such that a history is linearizable if and only
	// if each partition is linearizable. If left nil, this package will
	// skip partitioning.
	Partition      func(history []Operation) [][]Operation
	PartitionEvent func(history []Event) [][]Event
	// Initial states of the system.
	Init func() []interface{}
	// Step function for the system. Returns all possible next states for
	// the given state, input, and output. If the system cannot step with
	// the given state/input to produce the given output, this function
	// should return an empty slice.
	Step func(state interface{}, input interface{}, output interface{}) []interface{}
	// StepContext is an optional context-aware Step function. If set, the
	// checker calls StepContext instead of Step, allowing the model to stop
	// work promptly when a timeout expires.
	StepContext func(ctx context.Context, state interface{}, input interface{}, output interface{}) []interface{}
	// Equality on states. If left nil, this package will use == as a
	// fallback ([ShallowEqual]).
	Equal func(state1, state2 interface{}) bool
	// Hash returns a hash of the given state. If non-nil, the checker uses
	// it to reduce the number of [Equal] comparisons. Must satisfy the
	// invariant that [Equal] states have equal hashes.
	Hash func(state interface{}) uint64
	// For visualization, describe an operation as a string. For example,
	// "Get('x') -> 'y'". Can be omitted if you're not producing
	// visualizations.
	DescribeOperation func(input interface{}, output interface{}) string
	// For visualization purposes, describe a state as a string. For
	// example, "{'x' -> 'y', 'z' -> 'w'}". Can be omitted if you're not
	// producing visualizations.
	DescribeState func(state interface{}) string
	// For visualization purposes, describe metadata as a string. Can be
	// omitted if you're not producing visualizations.
	DescribeOperationMetadata func(info interface{}) string
	// contains filtered or unexported fields
}

A NondeterministicModel is a nondeterministic sequential specification of a system.

For basics on models, see the documentation for Model. In contrast to Model, NondeterministicModel has a step function that returns a set of states, indicating all possible next states. It can be converted to a Model using the NondeterministicModel.ToModel function.

It may be helpful to look at this package's test code for examples of how to write and use nondeterministic models.

func (*NondeterministicModel) ToModel

func (nm *NondeterministicModel) ToModel() Model

ToModel converts a NondeterministicModel to a Model using a power set construction.

This makes it suitable for use in linearizability checking operations like CheckOperations. This is a general construction that can be used for any nondeterministic model. It relies on the NondeterministicModel's Equal function to merge states. You may be able to achieve better performance by implementing a Model directly.

type Operation

type Operation struct {
	ClientId int // optional, unless you want a visualization; zero-indexed
	Input    interface{}
	Call     int64 // invocation timestamp
	Output   interface{}
	Return   int64 // response timestamp
	// Metadata contains arbitrary metadata associated with the operation.
	// It is not used for linearizability checking but can be used for visualization.
	Metadata interface{}
	// contains filtered or unexported fields
}

An Operation is an element of a history.

This package supports two different representations of histories, as a sequence of Operation or Event. In the Operation representation, function call/returns are packaged together, along with timestamps of when the function call was made and when the function call returned.

The interval [Call, Return] is interpreted as a closed interval, so an operation with interval [10, 20] is concurrent with another operation with interval [20, 30].