Die State Machine – Aus Commands wird ein deterministischer Zustand
In dieser Serie entwickle ich ein System, das Commands verarbeitet und daraus einen konsistenten Zustand berechnet. Ich starte mit dem Herzstück: einer deterministischen Finite State Machine. Später in der Serie werde ich Snapshots zum Speichern des Zustandes einführen sowie mit einem Write-Ahead Log (WAL) Ansatz die Commands granularer speichern, um weniger Verlust bei einem Serverneustart zu haben.
- Die State Machine – Aus Commands wird ein deterministischer Zustand
- State Machine Snapshots laden und speichern
Eine Finite State Machine (FSM) kann sehr theoretisch mathematisch erklärt werden. Ich möchte mich hier aber auf die praktische Implementierung konzentrieren.
Kurz gesagt, eine FSM ist ein Modell, das einen eindeutigen Zustand zu einem bestimmten Zeitpunkt beschreibt. Sie kann auf Ereignisse (Events/Commands) reagieren und ihren Zustand ändern. In gewisser Weise ist z.B. Redux eine FSM. In der Datenbank Consul empfängt sie Commands und ändert damit in definierter Reihenfolge den Zustand der Datenbank.
Für eine einfache Implementierung einer FSM benötige ich ein Apply(cmd *Command) any, das einen Command verarbeitet und den neuen Zustand zurückgibt. Die Logik ob und wie ein Command angewendet wird, liegt in der Implementierung der FSM. Es kann sein, dass der Command ignoriert wird, weil er nicht zum aktuellen Zustand passt. Um Zustände wiederherzustellen, ist es wichtig, dass die FSM die Commands jedesmal gleich verarbeitet.
Da die FSM die Logik enthält, ist es der Bestandteil, der in jeder Anwendung unterschiedlich ist.
Command
Der Command ist die Anweisung, was getan werden soll. Er enthält alle Informationen, die benötigt werden um ihn immer gleich zu verarbeiten. Um ein bisschen Komplexeres Beispiel zu haben, werde ich Nodes in einem Baum verwalten können. Jeder Node kann Key-Value Attribute haben, die gesetzt oder gelöscht werden können. Der Command enthält den Node, auf den er sich bezieht, und die Operation, die durchgeführt werden soll.
type OperationType string
const (
CreateOperation OperationType = "create"
DeleteOperation OperationType = "delete"
SetAttributeOperation OperationType = "set_attribute"
DeleteAttributeOperation OperationType = "delete_attribute"
)
type Command struct {
Operation OperationType
// TargetNodeID is the ID of the parent node or the node itself for attribute operations
TargetNodeID string
// NewNodeID is the ID of the new node to create (for CreateOperation)
NewNodeID string
// Key for Attribute operations
Key string
// Value for Set operations
Value any
}
Es spricht nichts dagegen, den Command in mehrere aufzuteilen oder anders zu strukturieren. Er ist nur ein Container mit Informationen.
Der State
Für das Beispiel benötige ich eine Datenstruktur mit den Nodes.
package fsm
type Node struct {
ID string `json:"id"`
Attributes map[string]any `json:"attributes"`
Parent *Node `json:"-"`
Children map[string]*Node `json:"children"`
}
Die Finite State Machine selbst hält den aktuellen Zustand und die Logik, wie Commands verarbeitet werden. Sie kann entweder durch einen Mutex oder durch Channels thread-sicher gemacht werden. Um schnell auf einen Node zugreifen zu können, ohne den gesamten Baum zu durchsuchen, verwende ich eine Map, die die Nodes nach ihrer ID indiziert.
package fsm
// FSM represents a simple finite state machine
type FSM struct {
parentNode *Node
nodes map[string]*Node
lock sync.Mutex
}
// NewFSM creates a new finite state machine with an initial parent node
func NewFSM() *FSM {
rootNode := &Node{
ID: "root",
Attributes: make(map[string]any),
Children: make(map[string]*Node),
}
return &FSM{
parentNode: rootNode,
nodes: map[string]*Node{
"root": rootNode,
},
}
}
Apply Command
Die folgende Apply Methode ist eigentlich einfach aufgebaut. Sie erkennt den Command-Typ und führt die entsprechende Funktion aus. Wie das Ganze deutlich komplexer in der Praxis aussieht, kann im Source Code der Key-Value Datenbank Consul angeschaut werden. Der Rückgabewert ist any. So kann ich entweder einen Error zurückgeben, wenn z.B. ein interner Fehler auftritt oder ein Response Objekt das z.B. in der API verwendet wird.
package fsm
// Apply processes a command and transitions the state if valid
func (f *FSM) Apply(cmd *Command) any {
f.lock.Lock()
defer f.lock.Unlock()
switch cmd.Operation {
case CreateOperation:
return f.createNode(cmd)
case DeleteOperation:
return f.deleteNode(cmd)
case SetAttributeOperation:
return f.setAttribute(cmd)
case DeleteAttributeOperation:
return f.deleteAttribute(cmd)
default:
return fmt.Errorf("unknown operation: %s", cmd.Operation)
}
}
In diesem Artikel implementiere ich exemplarisch nur die createNode Methode. Wichtig ist, dass der Zustand nur verändert wird, wenn der Command gültig ist. Das bedeutet, dass der Target-Node existieren muss, um einen Child Node zu erstellen. Falls der Command ungültig ist, gibt die Methode einen Fehler zurück.
func (f *FSM) createNode(cmd *Command) any {
if _, exists := f.nodes[cmd.TargetNodeID]; !exists {
return fmt.Errorf("target node %s does not exist", cmd.TargetNodeID)
}
newNode := &Node{
ID: cmd.NewNodeID,
Attributes: make(map[string]any),
Children: make(map[string]*Node),
}
parentNode := f.nodes[cmd.TargetNodeID]
parentNode.Children[newNode.ID] = newNode
newNode.Parent = parentNode
f.nodes[newNode.ID] = newNode
return newNode
}
Anwendung
Die FSM kann nun Commands verarbeiten und den Zustand entsprechend ändern. Hier ein Beispiel, wie die FSM verwendet werden kann.
package main
func main() {
fsm := NewFSM()
// Create a new node under the root
cmd1 := &Command{
Operation: CreateOperation,
TargetNodeID: "root",
NewNodeID: "node1",
}
response := fsm.Apply(cmd1)
if err, ok := response.(error); ok {
log.Printf("Error applying command: %v", err)
} else {
fmt.Printf("Created node: %v\n", response)
}
// Set an attribute on the new node
cmd2 := &Command{
Operation: SetAttributeOperation,
TargetNodeID: "node1",
Key: "color",
Value: "blue",
}
response = fsm.Apply(cmd2)
if err, ok := response.(error); ok {
log.Printf("Error applying command: %v", err)
} else {
fmt.Printf("Set attribute on node: %v\n", response)
}
}
Die Response kann flexibel gewählt und weiterverarbeitet werden. In diesem Beispiel wird einfach der Node oder ein Fehler ausgegeben.
Im nächsten Teil werde ich der FSM Snapshots hinzufügen, um den Zustand speichern und wiederherstellen zu können.