180 lines
5.2 KiB
Markdown
180 lines
5.2 KiB
Markdown
---
|
|
tags: [pattern/fsm, finite-state-machine, state-transition, dfa-nfa, fsm-implementation]
|
|
create time: 2026-08-08 14:30
|
|
update time: 2026-08-08 14:30
|
|
---
|
|
|
|
# 有限状态机核心概念
|
|
|
|
## 概述
|
|
|
|
有限状态机（Finite State Machine，简称 FSM）是一种数学计算模型，也是软件工程中最实用的抽象之一。它将任何有明确"状态"和"动作"的系统建模为一组离散状态的集合，配合事件驱动的转换规则，让复杂业务流程变得可预测、可测试、可追溯。
|
|
|
|
## 核心原理
|
|
|
|
### 四大核心概念
|
|
|
|
| 概念 | 定义 | 示例 |
|
|
|------|------|------|
|
|
| 状态 (State) | 系统在某一时刻所处的条件或模式 | `PENDING`、`APPROVED`、`REJECTED` |
|
|
| 事件 (Event) | 触发状态转换的外部或内部信号 | `submit`、`approve`、`reject` |
|
|
| 转换 (Transition) | 从一个状态到另一个状态的映射关系 | `PENDING + approve -> APPROVED` |
|
|
| 动作 (Action) | 状态转换时或进入状态时执行的副作用 | 发送邮件通知、写审计日志 |
|
|
|
|
一个完整的 FSM 可以用五元组表示：`(States, Events, Transitions, Actions, StartState)`
|
|
|
|
### DFA vs NFA
|
|
|
|
确定性有限自动机（DFA）和非确定性有限自动机（NFA）是两种理论模型，区别在于同一个状态下对同一事件的响应是否唯一。
|
|
|
|
```mermaid
|
|
graph TD
|
|
subgraph DFA["DFA - 确定性有限自动机"]
|
|
A["状态A"] -->|"事件X"| B["状态B"]
|
|
A -->|"事件Y"| C["状态C"]
|
|
B -->|"事件X"| D["状态D"]
|
|
B -->|"事件Y"| C
|
|
end
|
|
|
|
subgraph NFA["NFA - 非确定性有限自动机"]
|
|
E["状态E"] -->|"事件X"| F["状态F"]
|
|
E -->|"事件X"| G["状态G"]
|
|
E -->|"事件Y"| H["状态H"]
|
|
end
|
|
```
|
|
|
|
关键区别：
|
|
|
|
- **DFA**：每个状态对每个事件最多只有一个后继状态。行为可预测，适合工程实现。
|
|
- **NFA**：同一个状态对同一事件可能转移到多个后继状态，甚至可以无转移地"猜"一条路径。等价于 DFA 但更紧凑，适合正则表达式引擎底层。
|
|
|
|
> [!NOTE]
|
|
> 工程实践中的 FSM 几乎总是 DFA。Go 里的 switch-case、map-of-function-map、接口模式本质上都是 DFA 的编程表达。
|
|
|
|
### 状态转移方程
|
|
|
|
FSM 的核心是转移函数 δ（delta）：
|
|
|
|
```
|
|
δ(current_state, event) → next_state
|
|
```
|
|
|
|
当转移存在 Action 时扩展为：
|
|
|
|
```
|
|
δ(current_state, event) → (next_state, action)
|
|
```
|
|
|
|
约束条件：
|
|
- 转移函数必须是**部分函数** — 并非所有事件在所有状态都有效。例如订单已经"已退款"后不能再"支付"。
|
|
- 非法转移应返回错误或被拒绝，而非静默忽略。
|
|
|
|
## 代码示例
|
|
|
|
### 方式一：switch-case 枚举
|
|
|
|
最直观的方式，适合状态数少于 10 的场景。
|
|
|
|
```go
|
|
type OrderStatus int
|
|
|
|
const (
|
|
Pending OrderStatus = iota
|
|
Paid
|
|
Shipped
|
|
Completed
|
|
Refunding
|
|
Refunded
|
|
)
|
|
|
|
func (o *Order) Handle(event string) error {
|
|
switch o.Status {
|
|
case Pending:
|
|
if event == "pay" {
|
|
o.Status = Paid
|
|
return nil
|
|
}
|
|
return fmt.Errorf("cannot %s from %s", event, o.Status)
|
|
case Paid:
|
|
if event == "ship" {
|
|
o.Status = Shipped
|
|
return nil
|
|
}
|
|
// ...
|
|
}
|
|
return fmt.Errorf("invalid transition")
|
|
}
|
|
```
|
|
|
|
### 方式二：map-of-function-map
|
|
|
|
将状态转成数据驱动，新增状态只需注册新规则，无需改 switch。
|
|
|
|
```go
|
|
type FSM struct {
|
|
transitions map[State]map[string]func() error
|
|
State State
|
|
}
|
|
|
|
func (f *FSM) Register(state State, event string, fn func() error) {
|
|
if f.transitions[state] == nil {
|
|
f.transitions[state] = make(map[string]func() error)
|
|
}
|
|
f.transitions[state][event] = fn
|
|
}
|
|
|
|
func (f *FSM) Fire(event string) error {
|
|
handlers, ok := f.transitions[f.State][event]
|
|
if !ok {
|
|
return fmt.Errorf("no handler for %q in state %v", event, f.State)
|
|
}
|
|
return handlers()
|
|
}
|
|
```
|
|
|
|
### 方式三：State 接口 + Context 模式
|
|
|
|
面向对象的 FSM 设计，每个状态独立封装行为。
|
|
|
|
```go
|
|
type State interface {
|
|
Enter(ctx *Context) error
|
|
Handle(event string) (State, error)
|
|
}
|
|
|
|
type Context struct {
|
|
state State
|
|
data map[string]any
|
|
}
|
|
|
|
func (c *Context) Fire(event string) error {
|
|
next, err := c.state.Handle(event)
|
|
if err != nil {
|
|
return err
|
|
}
|
|
if err := next.Enter(c); err != nil {
|
|
return err
|
|
}
|
|
c.state = next
|
|
return nil
|
|
}
|
|
```
|
|
|
|
## 实践场景
|
|
|
|
| 选型策略 | 适用场景 | 优点 | 缺点 |
|
|
|---------|---------|------|------|
|
|
| switch-case | 状态少（≤10）、逻辑简单 | 直观、调试容易 | 违反开闭原则 |
|
|
| map-of-function | 状态中等（10~50）、需要灵活扩展 | 注册式扩展、易测试 | 闭包上下文传递稍繁琐 |
|
|
| State 接口 | 状态多（>50）、每个状态行为复杂 | 单一职责、面向对象 | 有一定架构开销 |
|
|
|
|
> [!TIP]
|
|
> 面试常考点：为什么不建议用数字枚举 + 硬编码数组来做状态校验？因为数字枚举不具备语义表达能力，编译期无法捕获非法转移。
|
|
|
|
> [!WARNING]
|
|
> 常见误区：把 FSM 当成普通的 if-else。FSM 的核心价值是**把所有合法转换集中在一处定义**，而不是散落在业务逻辑各处。
|
|
|
|
## 关联笔记
|
|
|
|
- [[有限状态机在业务中的应用]]
|