fsm

package
v1.0.0 Latest Latest
Warning

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

 Go to latest Published: Mar 29, 2021 License: Apache-2.0, MIT Imports: 14 Imported by: 11

README

go-statemachine FSM Module

A well defined DSL for constructing finite state machines for use in Filecoin.

Table of Contents

Background Reading

Wikipedia - Finite State Machines Wikipedia - UML State Machine

Description

This library provides a way to model a Filecoin process that operates on a specific data structure as a series of state transitions. It is used in the storage and retrieval markets in go-fil-markets repository to model the lifecycle of a storage or retrieval deal. It may be used for other parts of Filecoin in the future.

A state machine is defined in terms of

  • StateType -- the type of data structure we are tracking (should be a struct)
  • StateKeyField -- the field in the data structure that represents the unique identifier for the current state. Must be a field that is comparable in golang (i.e. not an array or map)
  • Events -- Events are the list of inputs that trigger transitions in state. An event is defined in terms of:
    • An identifier
    • A mapping between source states and destination states -- events can apply to one, many, or all source states. When there is more than one source state, the source states can share or have different destination states
    • An Action - this a function that applies updates to the underlying data structure in fields that are not StateKeyField
  • StateEntryFuncs - State entry functions are handlers that get called when the FSM enters a specific state. Where Actions are associated with specific events, state entry funcs are associated with specific states. Actions can modify the underlying data structure. StateEntryFuncs can only trigger additional events if they wish to modify the state (a state entry func receives a dereferenced value for the data structure, rather than the pointer)
  • Environment - This is a single interface that is used to access external dependencies. It is available to a StateEntryFunc
  • Notifier - A function that gets called on each successfully applied state transition, before any state entry func is called. This is useful for providing external notifications about state updates. It is called with the name of the event applied and the current state of the data structure.
  • FinalityStates - a list of states from which the state machine cannot leave. When the statemachine enters these states, it shuts down and stops receiving messages.

Usage

Let's consider a hypothetical deal we want to track in Filecoin. Each deal will have a series of states it can be in, and various things that can happen to change its state. We will track multiple deals at the same time. In this example, we will model the actions of the receiving party (i.e. the person who accepted the deal and is responding)

Here' is the simplified deal structure:

type DealState struct {
  // the original proposal
  DealProposal
  // the current status identifier
  Status          DealStatus
  // the other party's network address
  Receiver        peer.ID
  // how much much we received
  TotalSent       uint64
  // how much money we have
	FundsReceived   abi.TokenAmount
  // an informational message to augment the status of the deal
  Message         string
}

Let's pretend our ideal deal flow looks like:

Receive new deal proposal -> Validate proposal -> For All Data Requested, Send a chunk, then request payment, then wait for payment before sending more -> Complete deal

You can imagine at each state in this happy path, things could go wrong. A deal proposal might need to be rejected for not meeting criteria. A network message could fail to send. A client could send only a partial payment, or one that fails to process. We might had an error reading our own data.

You can start to assemble different events that might happen in this process:

ReceivedNewDeal
AcceptedDeal
RejectedDeal
SentData
RequestedPayment
ReceivedPayment
...

And you can imagine different states the deal is in:

New
Accepted
Rejected
AwaitingPayment
Completed
Failed
...

We would track these states in the Status field of our deal.

So we have StateType - DealState - and a StateKeyField - Status. Now we need to define our events. Here's how we do that, using the modules custom DSL:

var DealEvents = fsm.Events{
  fsm.Event("ReceivedNewDeal").FromAny().To("New").Action(func (deal * DealState, proposal DealProposal) error {
    deal.DealProposal = proposal
    return nil
  }),
  fsm.Event("RejectedDeal").From("New").To("Rejected").Action(func (deal * DealState, reason string) error {
    deal.Message = fmt.Sprintf("Rejected deal because: %s", reason)
    return nil
  }),
  fsm.Event("AcceptedDeal").From("New").To("Accepted"),
  ...
}

As we enter each new state, there are things we need to do to advance the deal flow. When we have a new deal proposal, we need to validate it, to accept or reject. When we accept a deal, we need to start sending data. This is handled by StateEntryFuncs. We define this as a mapping between states and their handlers:

// assuming ValidateDeal, SendData, and SendRejection are defined elsewhere
var DealEntryFuncs = fsm.StateEntryFuncs{
  "New": ValidateDeal,
  "Rejected": SendRejection
  "Accepted": SendData,
}

As a baseline rule, where Actions on Events modify state, StateEntryFuncs leave state as it is but can have side effects. We therefore define an Environment type used to trigger these side effects with the outside world. We might define our environment here as:

type DealResponse struct {
  Data: []byte
}

type DealEnvironment interface {
  LookUpSomeData(proposal DealProposal) ([]byte, err)
  SendDealResponse(response DealResponse) error
  ...
}

And then our SendData StateEntryFunc function might look like this:

func SendData(ctx fsm.Context, environment DealEnvironment, deal DealState) error {
  data, err := environment.LookupSomeData(deal.DealProposal)
  if err != nil {
    return ctx.Trigger("DataError", err)
  }

  err := environment.SendDealResponse(DealResponse{Data: data})
  if err != nil {
    return ctx.Trigger("NetworkError", err)
  }

  return ctx.Trigger("SentData", len(data))
}

You can see our SendData interacts with the environment dispatches additional events using the Trigger function on the FSM Context which is also supplied to a StateEntryFunc. While the above function only dispatches at most one new event based on the conditional logic, it is possible to dismatch multiple events in a state entry func and they will be processed asynchronously in the order they are received.

Putting all this together, our state machine parameters are as follows:

var DealFSMParameters = fsm.Parameters{
  StateType: DealState{},
  StateKeyField: "Status",
  Events: DealEvents,
  StateEntryFuncs: DealEntryFuncs,
  Environment: DealEnvironmentImplementation{}
  FinalityStates: []StateKey{"Completed", "Failed"} 
}

Interaction with statestore

The FSM module is designed to be used with a list of data structures, persisted to a datastore through the go-statestore module.

You initialize a new set of FSM's as follows:

var ds datastore.Batching

var dealStateMachines = fsm.New(ds, DealFSMParameters)

You can now dispatch events from the outside to a particular deal FSM with:

var DealID // some identifier of a deal
var proposal DealProposal
dealStateMachines.Send(DealID, "ReceivedNewDeal", proposal)

The statemachine will initialize a new FSM if it is not already tracking data for the given identifier (the first parameter -- in this case a deal ID)

That's it! The FSM module:

  • persists state machines to disk with go-statestore
  • operated asynchronously and in nonblocking fashion (any event dispatches will return immediate)
  • operates multiple FSMs in parallel (each machine has its own go-routine)

License

This module is dual-licensed under Apache 2.0 and MIT terms.

Copyright 2019. Protocol Labs, Inc.

Documentation

Index

Constants

View Source 
const NotificationQueueSize = 128

Variables

This section is empty.

Functions

func GenerateUML 

func GenerateUML(w io.Writer, syntaxType SyntaxType, parameters Parameters, stateNameMap StateNameMap, eventNameMap EventNameMap, startStates []StateKey, includeFromAny bool, stateCmp func(a, b StateKey) bool) error

GenerateUML genderates a UML state diagram (in Mermaid/PlantUML syntax) for a given FSM

func NewFSMHandler 

func NewFSMHandler(parameters Parameters) (statemachine.StateHandler, error)

NewFSMHandler defines an StateHandler for go-statemachine that implements a traditional Finite State Machine model -- transitions, start states, end states, and callbacks

func VerifyEventParameters 

func VerifyEventParameters(state StateType, stateKeyField StateKeyField, events []EventBuilder) error

func VerifyStateParameters 

func VerifyStateParameters(parameters Parameters) error

VerifyStateParameters verifies if the Parameters for an FSM specification are sound

Types

type ActionFunc 

type ActionFunc interface{}

ActionFunc modifies the state further in addition to modifying the state key. It the signature func action<StateType, T extends any[]>(s stateType, args ...T) and then an event can be dispatched on context or group with the form .Event(Name, args ...T)

type Context 

type Context interface {
	// Context returns the golang context for this context
	Context() context.Context

	// Trigger initiates a state transition with the named event.
	//
	// The call takes a variable number of arguments that will be passed to the
	// callback, if defined.
	//
	// It will return nil if the event is one of these errors:
	//
	// - event X does not exist
	//
	// - arguments don't match expected transition
	Trigger(event EventName, args ...interface{}) error
}

Context provides access to the statemachine inside of a state handler

type Environment 

type Environment interface{}

Environment are externals dependencies will be needed by this particular state machine

type ErrSkipHandler 

type ErrSkipHandler struct{}

ErrSkipHandler is a sentinel type that indicates not an error but that we should skip any state handlers present

func (ErrSkipHandler) Error 

func (e ErrSkipHandler) Error() string

type EventBuilder 

type EventBuilder interface {
	// From begins describing a transition from a specific state
	From(s StateKey) TransitionToBuilder
	// FromAny begins describing a transition from any state
	FromAny() TransitionToBuilder
	// FromMany begins describing a transition from many states
	FromMany(sources ...StateKey) TransitionToBuilder
	// Action describes actions taken on the state for this event
	Action(action ActionFunc) EventBuilder
}

EventBuilder is an interface for describing events in an fsm and their associated transitions

func Event 

func Event(name EventName) EventBuilder

Event starts building a new event

type EventName 

type EventName interface{}

EventName is the name of an event

type EventNameMap 

type EventNameMap interface{}

EventNameMap maps an event name to a human readable string

type EventProcessor 

type EventProcessor interface {
	// Event generates an event that can be dispatched to go-statemachine from the given event name and context args
	Generate(ctx context.Context, event EventName, returnChannel chan error, args ...interface{}) (interface{}, error)
	// Apply applies the given event from go-statemachine to the given state, based on transition rules
	Apply(evt statemachine.Event, user interface{}) (EventName, error)
	// ClearEvents clears out events that are synchronous with the given error message
	ClearEvents(evts []statemachine.Event, err error)
}

EventProcessor creates and applies events for go-statemachine based on the given event list

func NewEventProcessor 

func NewEventProcessor(state StateType, stateKeyField StateKeyField, events []EventBuilder) (EventProcessor, error)

NewEventProcessor returns a new event machine for the given state and event list

type Events 

type Events []EventBuilder

Events is a list of the different events that can happen in a state machine, described by EventBuilders

type Group 

type Group interface {

	// Begin initiates tracking with a specific value for a given identifier
	Begin(id interface{}, userState interface{}) error

	// Send sends the given event name and parameters to the state specified by id
	// it will error if there are underlying state store errors or if the parameters
	// do not match what is expected for the event name
	Send(id interface{}, name EventName, args ...interface{}) (err error)

	// SendSync will block until the given event is actually processed, and
	// will return an error if the transition was not possible given the current
	// state
	SendSync(ctx context.Context, id interface{}, name EventName, args ...interface{}) (err error)

	// Get gets state for a single state machine
	Get(id interface{}) StoredState

	// GetSync will make sure all events present at the time of the call are processed before
	// returning a value, which is read into out
	GetSync(ctx context.Context, id interface{}, value cbg.CBORUnmarshaler) error

	// Has indicates whether there is data for the given state machine
	Has(id interface{}) (bool, error)

	// List outputs states of all state machines in this group
	// out: *[]StateT
	List(out interface{}) error

	// IsTerminated returns true if a StateType is in a FinalityState
	IsTerminated(out StateType) bool

	// Stop stops all state machines in this group
	Stop(ctx context.Context) error
}

Group is a manager of a group of states that follows finite state machine logic

func New 

func New(ds datastore.Datastore, parameters Parameters) (Group, error)

New generates a new state group that operates like a finite state machine, based on the given parameters ds: data store where state comes from parameters: finite state machine parameters

type Notifier 

type Notifier func(eventName EventName, state StateType)

Notifier should be a function that takes two parameters, a native event type and a statetype -- nil means no notification it is called after every successful state transition with the even that triggered it

type Parameters 

type Parameters struct {

	// Environment is the environment in which the state handlers operate --
	// used to connect to outside dependencies
	Environment Environment

	// StateType is the type of state being tracked. Should be a zero value of the state struct, in
	// non-pointer form
	StateType StateType

	// StateKeyField is the field in the state struct that will be used to uniquely identify the current state
	StateKeyField StateKeyField

	// Events is the list of events that that can be dispatched to the state machine to initiate transitions.
	// See EventDesc for event properties
	Events []EventBuilder

	// StateEntryFuncs - functions that will get called each time the machine enters a particular
	// state. this is a map of state key -> handler.
	StateEntryFuncs StateEntryFuncs

	// Notifier is a function that gets called on every successful event processing
	// with the event name and the new state
	Notifier Notifier

	// FinalityStates are states in which the statemachine will shut down,
	// stop calling handlers and stop processing events
	FinalityStates []StateKey
}

Parameters are the parameters that define a finite state machine

type StateEntryFunc 

type StateEntryFunc interface{}

StateEntryFunc is called upon entering a state after all events are processed. It should have the signature func stateEntryFunc<StateType, Environment>(ctx Context, environment Environment, state StateType) error

type StateEntryFuncs 

type StateEntryFuncs map[StateKey]StateEntryFunc

StateEntryFuncs is a map between states and their handlers

type StateKey 

type StateKey interface{}

StateKey is a value for the field in the state that represents its key that uniquely identifies the state in practice it must have the same type as the field in the state struct that is designated the state key and must be comparable

type StateKeyField 

type StateKeyField string

StateKeyField is the name of a field in a state struct that serves as the key by which the current state is identified

type StateNameMap 

type StateNameMap interface{}

StateNameMap maps a state type to a human readable string

type StateType 

type StateType interface{}

StateType is a type for a state, represented by an empty concrete value for a state

type StoredState 

type StoredState interface {
	End() error
	Get(out cbg.CBORUnmarshaler) error
	Mutate(mutator interface{}) error
}

StoredState is an abstraction for the stored state returned by the statestore

type SyntaxType 

type SyntaxType uint64

SyntaxType specifies what kind of UML syntax we're generating 

const (
	PlantUML SyntaxType = iota
	MermaidUML
)

type TransitionMap 

type TransitionMap map[StateKey]StateKey

TransitionMap is a map from src state to destination state

type TransitionToBuilder 

type TransitionToBuilder interface {
	// To means the transition ends in the given state
	To(StateKey) EventBuilder
	// ToNoChange means a transition ends in the same state it started in (just retriggers state cb)
	ToNoChange() EventBuilder
	// ToJustRecord means a transition ends in the same state it started in (and DOES NOT retrigger state cb)
	ToJustRecord() EventBuilder
}

TransitionToBuilder sets the destination of a transition

Source Files

View all Source files

Directories

Path Synopsis

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.