自己动手造一个状态机

大忽悠爱学习

发布于 2024-01-13 10:25:41

2590

发布于 2024-01-13 10:25:41

文章被收录于专栏：c++与qt学习c++与qt学习

自己动手造一个状态机

引言
有限自动状态机 (FSM)
- 五要素
- 应用场景
- 优势
开源产品
造个轮子
- 改造点
- Looplab fsm
- - 示例演示
  - 实现解析
- 改造过程

引言

有限自动状态机 (Finite-state machine , FSM) 通常用来描述某个具有有限个状态的对象，并且在对象的生命周期中组成了一个状态序列，通过响应外界各种事件完成状态流转。

FSM 被广泛应用于建模应用行为，硬件电路系统设计，软件工程，编译器，网络协议和计算机语言的研究。

有限自动状态机 (FSM)

五要素

现态 (src state) : 事物当前所处的状态
事件 (event) : 事件就是执行某个操作后触发的条件或者口令，当一个事件被满足，将会触发一个动作，或者执行一次状态的迁移。
行为 (action) : 事件满足后执行的动作，动作执行完毕后，可以迁移到新的状态，也可以仍旧保持原状态。动作不是必需的，当事件满足后，也可以不执行任何动作，直接迁移到新状态。
次态 (dst state) : 事件满足后要迁往的新状态，‘次态’是相对于‘现态’而言的，‘次态’一旦被激活，就转变成新的‘现态’了。
状态流转 (transition) : 事物从现态变为次态的整个过程。

应用场景

FSM 应用场景满足的规则:

可以用状态来描述事物，并且任一时刻，事物总是处于一种状态
事物拥有的状态总数是有限的
通过触发事物的某些行为，可以导致事物从一种状态迁移到另一种状态
事物状态变化是有规则的。A状态 -> B状态，B状态 -> C状态，C状态 -> A状态。
同一种行为，可以将事物从多种状态变为同种状态，但是不同从同种状态变成多种状态。

落地的应用场景:

网络通信协议
订单，服务单，退款场景

优势

代码抽象: 将业务流程进行抽象和结构化，将复杂的状态转移图，分割成相邻状态的最小单元，这样相当于搭建了乐高积木，在这套机制上可以组合成复杂的状态转移图，同时隐藏了系统的复杂度。
简化流程: 业务rd只需要关注当前操作的业务逻辑(状态流转过程中的业务回调函数)，极大的解耦了状态和业务。
易扩展: 在新增状态或事件时，无需修改原有的状态流转逻辑，直接建立新的状态转移链路即可。
业务建模: 通过最小粒度的相邻状态拼接，最终组成了业务整体的graph。

开源产品

cola-component-statemachine (java)
- 优点
  - 支持condition (dsl需要再扩展)
  - 事件类型: 内部事件，外部事件
  - interceptor: 进入，退出状态机；进入，退出状态；
- 缺点
  - 无分布式状态控制
  - 无时间触发
squirrel-foundation (java)
- 优点
  - 支持动作的exit，transition，entry
  - 状态转换过程细分，可以做功能扩展和状态跟踪
  - 没有并发死锁问题
  - 轻量级
- 缺点
  - 注解方式定义状态和事件，不支持状态和事件枚举
  - interceptor粒度粗
Spring statemachine (java)
- 优点
  - Interceptor ，listener 方便监控，持久化，功能扩展
  - 对象化的状态机配置
  - 分层状态机，解决复杂场景的多状态问题
  - 使用triggers，transitions，guards，actions概念
  - 基于zk的分布式事件监听
  - 状态机配置持久化
  - 时间触发和事件触发
  - 事件类型: 内部事件，外部事件 (内部，外部是相对于状态来说的)
  - 支持spel表达式
- 缺点
  - 重量级
  - 配合spring使用更方便
  - 单实例的StateMachine存在线程安全问题
Looplab fsm (go)
- 优点
  - 支持Callback，BeforeEvent，LeaveEvent，EnterSatte，AfterEvent
  - 异常感知
  - 对状态的Mutex锁
- 缺点
  - 无异步类型的event
  - 无分布式状态控制
  - 无condition

造个轮子

改造点

我们本节将基于Looplab fsm (go) 进行改造，改造点主要有以下几个:

同一个event下，一个现态 , 可流转到不同的次态

传统概念的状态机中，一个src和一个event的组合，只能确定一个且仅有一个的dst，但是经过改造后，一个src和一个event的组合，可能会关联多个dst，这样做并不是改变了状态机的模型，而是通过将相似的event合并，配合条件表达式，也就是组成src，event ，和条件表达式的三元组，唯一的确定可流转的dst。这样做的好处有两点:

简化状态流转的配置
可以将event设计的更贴合业务语义

以下单场景为例:

订单处于 “下单” 状态，当接收到 “创建订单” 事件时。根据订单类型的不同可以分为0元单和非0元单，传统的FSM会将两种类型的订单创建定义为两个不同的event : “创建0元订单” 和 “创建非0元订单” ，但是在bfsm中，可以只定义一个 “创建订单” 的 event ，配合条件表达式判断订单类型，将状态流转到不同的dst 。这样可以简化配置，同时也不需要将 “创建订单” 这个event做更细粒度的拆解。

匹配表达式

根据src 和 event ，能够匹配到一组 dst ，通过匹配表达式执行复杂匹配逻辑，每个匹配条件被满足后对应一个dst，在状态流转的过程中，会按照表达式的注册顺序依次进行匹配，最终会匹配执行结果为true的表达式所对应的dst ；如果所有匹配表达式执行结果都为false，那么状态不会发生流转。

可合并多场景的状态转移配置

可以将多个场景的状态转移配置合并，不合并也可以正常使用。

加锁状态流转

为应对高并发场景，支持基于redis分布式锁的状态转移，对状态转移，通过锁定状态转移的实体对象(通常为订单id，服务单id等)，锁定事件fire过程，保证高并发场景下，同一实体对象的状态流程串行执行。另外，支持用户自定义锁的实现。

多对多状态配置

简化配置，提供多状态到多状态的流转配置。

状态配置的图化

基于状态流转配置，在线展示状态转移图。

Looplab fsm

示例演示

Looplab fsm 一个简单的使用示例如下所示:

func main() {
	var afterFinishCalled bool
	fsm := fsm.NewFSM(
		// 初态 
		"start",
		// 状态流转图
		fsm.Events{
		     // 事件名 / 现态 / 次态
		     // 现态 + 事件 = 次态
			{Name: "run", Src: []string{"start"}, Dst: "end"},
			{Name: "finish", Src: []string{"end"}, Dst: "finished"},
			{Name: "reset", Src: []string{"end", "finished"}, Dst: "start"},
		},
		// 回调接口集合
		fsm.Callbacks{
		    // 在进入end状态前,会回调该接口
			"enter_end": func(ctx context.Context, e *fsm.Event) {
				if err := e.FSM.Event(ctx, "finish"); err != nil {
					fmt.Println(err)
				}
			},
			// 再离开finish状态时,会回调该接口
			"after_finish": func(ctx context.Context, e *fsm.Event) {
				afterFinishCalled = true
				if e.Src != "end" {
					panic(fmt.Sprintf("source should have been 'end' but was '%s'", e.Src))
				}
				if err := e.FSM.Event(ctx, "reset"); err != nil {
					fmt.Println(err)
				}
			},
		},
	)
    // 触发run事件
	if err := fsm.Event(context.Background(), "run"); err != nil {
		panic(fmt.Sprintf("Error encountered when triggering the run event: %v", err))
	}
   
	if !afterFinishCalled {
		panic(fmt.Sprintf("After finish callback should have run, current state: '%s'", fsm.Current()))
	}
    // 查看当前状态  
	currentState := fsm.Current()
	if currentState != "start" {
		panic(fmt.Sprintf("expected state to be 'start', was '%s'", currentState))
	}

	fmt.Println("Successfully ran state machine.")
}

实现解析

Looplab fsm 只支持 event ，state 二元组状态流转方式，所以整理实现流程比较简单，如下图所示:

Looplab fsm 核心代码都位于 fsm.go 文件中，具体实现大家可以去阅读该源文件进行学习。

改造过程

改造的具体代码实现此处就不贴出来了，只给出流程图级别的改造说明：

加锁:

上图省去了加锁保护细节，此处的加锁需要替换为redis分布式锁了，当然加锁这块还是可以好好优化一下的，不然高并发场景下，锁的争抢会成为瓶颈。

异常处理:

状态机内部的错误会通过error的形式抛给业务方
业务方的calllback函数执行异常时，需要业务方通过cancel方法主动通知状态机结束此次状态流转，但是不能再状态变更后的AfterTransCallback中调用cancel回调，因为此时状态已经发生了变更。

表达式:

基于govaluate实现

多场景状态转移配置合并:

可以通过场景隔离，同时抽取状态转移配置全局化，实现多场景状态转移配置合并

每种场景下的配置伪代码如下:

FSMConf := map[string]FsmDesc{
    "场景名1" : {
         // 当前场景下的全局回调接口
         BeforeTransCallback
         AfterTransCallback
         // 支持多状态到多状态流转
         TransDesc: []TransDesc{
            {
             // 事件名
             EventName
             // 现态集合
             Src []string{}
             // 属于本次状态流转过程中的局部回调接口
             BeforeTransCallback
             AfterTransCallback
             // 表达式集合
             Matchers []Matcher{
                 // 表达式,次态,回调接口
                {Condition,Dst,BeforeMatchCallback,AfterMatchCallback}
             }
            }
         } 
     },
     "场景2" : {}
}

FSM 初始化过程也分为了两步: