相亲模型与有限状态机

2022-08-01 20:16:51 浏览数 (1)

如果有人问你需要几步可以把大象关进冰箱里，你脑海中肯定浮现起宋大妈的笑容并脱口而出：3步。

如果有人问你从单身到定终身需要几步，估计你还真需要掰着手指算一算。

相亲模型

一入编程深似海，代码尽头是相亲。有前辈说过，没有相过亲的程序猿是不完整的，连写出来的代码都少一分深沉。虽说没有亲身体验，但如果掰着手指算算定终身的事情，倒也可以从相亲说起。

从相亲说起

你清清嗓子，咽了口水，双指快速摩挲着菜单的边角，抬头望着桌对面的陌生漂亮小姐姐：“你有啥想吃的么”。

“随便吃点就好”。

你继续埋头到菜单之中，胡乱的点了几个菜，匆忙的连饮料都忘了点。

“那个，我先自我介绍一下”，你把菜单一推，心想大不了当 HR 面试了，开始介绍起自己的来，还顺便提了一句自己不写 Java。

饭后回家，回想起吃饭的点滴，尴尬阵阵涌起，不过好在相谈甚欢，仿佛有戏。意犹未尽之后，你打开某绿色聊天 app，点开熟悉又陌生的头像，开始了下半场。

次月，又是这家饭馆。你决定捅破那层窗户纸，咖啡馆、剧本杀均留下来了共同的美好回忆，说不好时机已经成熟。

你清清嗓子，咽了口水，双指快速摩挲着菜单的边角，抬头望着桌对面的小姐姐：“你有啥想吃的么”。

相亲状态流转图

恐怕只有像我这样蹩脚的人才会写出如此没有起伏的故事，为何？因为情感是世间最复杂的事情之一，而以聊天为打法，以推动情感发展为底层逻辑的相亲也是变量最多的战役。虽不能穷举相亲的过程，但是尝试把相亲的场景过程抽象量化，想必可以得到一张复杂的状态流转图。

上面这张图，月老看了都直呼内行。相亲过程中的中间状态只多不少，那么从单身到定终身需要几步呢？

有限状态机

有限状态机（FSM）本是控制论的一个数学模型。用来表示可枚举种类的状态之间的转移和动作等行为。说人话就是用来控制机器状态的变更。

基本概念

从相亲的模型中可以看到，一个有限状态机包含『状态』和『行为』两大基本概念。

『状态』包括两个核心元素：

  • 第一个是 State 即状态，一个状态机至少要包含两个状态。比如最简单的状态机就是电灯，包含了 “亮” 和 “灭” 两个状态。
  • 第二个是 Transition 即状态流转，也就是从一个状态变化为另一个状态。比如 “开灯的过程” 就是一个状态流转。

『行为』也包含两个核心元素

  • 第一个是 Event 即事件，事件就是执行某个操作，也可以看做外部系统的输入。比如 “按下灯开关” 就是一个事件。
  • 第二个是 Action 即动作，事件发生后引发的变更，也可以看做状态机对外部的输出。比如 “按下灯开关” 事件后，会触发 “灯泡亮起” 这个动作。

适用场景

有限状态机的适用场景很多，尤其是状态复杂的场景，比如订单、任务管理等。有限状态机的本质是维护状态流转图，使得在复杂的用户输入中，依然保持状态的合法和安全。

(图来自《京东京麦交易平台设计与实现》)

除了复杂状态流转的场景，当状态无法明确的情况下，有限状态机也可以被考虑。仿佛和『有限』这个字眼相悖，这里的无法明确是指需求无法明确，也许今天 3 个状态就满足需求了，但下个版本可能需要 5 个状态。对于有限状态机来说，多加两种状态只不过是在状态流转图了多几条边而已。

有限状态机实现

本节的实现以 GoFlow 为例，GoFlow 是一个用 Golang 实现的任务引擎 代码可见：https://github.com/basenana/go-flow/tree/main/fsm

MIT 数位系统概论中总结了一套实现 FSM 的方法论：

  • 明确状态类型（identify distinct states）
  • 创建状态流转图（create state transition diagram）
  • 编写状态流转逻辑（write for next-state logic）
  • 编写输出信号逻辑（write for output signals）

我们就从这个四个角度讲下 GoFlow 的 FSM 实现。

枚举状态类型

首先是明确『有限』的状态，对于 GoFlow 这种任务管理系统来说，状态肯定是围绕任务展开的：

代码语言：javascript复制
const (
 CreatingStatus     fsm.Status = "creating"
 InitializingStatus            = "initializing"
 RunningStatus                 = "running"
 SucceedStatus                 = "succeed"
 FailedStatus                  = "failed"
 ErrorStatus                   = "error"
 PausedStatus                  = "paused"
 CanceledStatus                = "canceled"
)

状态流转图

状态流转图是一个有向图，每个状态都是一个点，两点之间的边即是事件，边的方向是流转方向。最简单存储方式有两种：

  1. 十字链表法：以当前状态为维度维护指向其前驱节点的边。也就是以当前状态为 Key，保存的 Value 即是事件类型和可以流转的下一级状态
  2. 边存储法：以事件为维度维护所有的边。也就是事件类型为 Key，Value 是上级状态和下级状态

两种存储方式各有好处，因为 GoFlow 状态流转图的边的数量比较少，也就选择了第二种方式：基于 Map 以事件类型为 Key，存储所有的边。这种存储方式可以快速通过一个事件，找到能执行的所有操作。

代码语言：javascript复制
type edge struct {
 from Status
 to   Status
 when EventType
 do   Handler
 next *edge
}

type FSM struct {
 obj   Stateful
 graph map[EventType]*edge

 crtBuilder *edgeBuilder
 mux        sync.Mutex
 logger     log.Logger
}

从 GoFlow 的状态枚举可以看出当前的引擎相对简单，因此它的状态流转图也并不复杂：

构建状态流转图的逻辑：

代码语言：javascript复制
func buildFlowTaskFSM(r *runner, t flow.Task) *fsm.FSM {
 m := fsm.New(fsm.Option{
  Obj:    t,
  Logger: r.logger.With(fmt.Sprintf("task.%s.fsm", t.Name())),
 })

 m.From([]fsm.Status{flow.InitializingStatus}).
  To(flow.RunningStatus).
  When(flow.TaskTriggerEvent).
  Do(r.handleTaskRun)

 m.From([]fsm.Status{flow.RunningStatus}).
  To(flow.SucceedStatus).
  When(flow.TaskExecuteFinishEvent).
  Do(r.handleTaskSucceed)

 m.From([]fsm.Status{flow.RunningStatus}).
  To(flow.PausedStatus).
  When(flow.TaskExecutePauseEvent).
  Do(r.handleTaskPaused)

 m.From([]fsm.Status{flow.PausedStatus}).
  To(flow.RunningStatus).
  When(flow.TaskExecuteResumeEvent).
  Do(r.handleTaskResume)

 m.From([]fsm.Status{flow.InitializingStatus, flow.RunningStatus, flow.PausedStatus}).
  To(flow.CanceledStatus).
  When(flow.TaskExecuteCancelEvent).
  Do(r.handleTaskCanceled)

 m.From([]fsm.Status{flow.InitializingStatus, flow.RunningStatus}).
  To(flow.FailedStatus).
  When(flow.TaskExecuteErrorEvent).
  Do(r.handleTaskFailed)

 return m
}

状态流转逻辑与触发动作

状态的流转是 FSM 的核心，GoFlow 的状态流转，基本流程：

  1. 根据当前事件获取该事件影响的边
  2. 基于边的初始状态与当前状态匹配
  3. 如果存在匹配的边，则把当前状态机状态置为下级状态
  4. 状态转换完成后，执行对应的动作
代码语言：javascript复制
func (m *FSM) Event(event Event) error {
 m.mux.Lock()
 defer m.mux.Unlock()

 m.logger.Debugf("handler fsm event: %s", event.Type)
 head := m.graph[event.Type]
 if head == nil {
  return nil
 }

 defer func() {
  if panicErr := recover(); panicErr != nil {
   m.logger.Errorf("event %s handle panic: %v", event, panicErr)
  }
 }()

 for head != nil {
  if m.obj.GetStatus() == head.from {
   m.logger.Infof("change obj status from %s to %s with event: %s", head.from, head.to, event.Type)
   m.obj.SetStatus(head.to)
   if event.Message != "" {
    m.obj.SetMessage(event.Message)
   }

   if head.do != nil {
    if handleErr := head.do(event); handleErr != nil {
     m.logger.Errorf("event %s handle failed: %s", event.Type, handleErr.Error())
     return handleErr
    }
   }
   return nil
  }
  head = head.next
 }
 return fmt.Errorf("get event %s and current status is %s, no change path matched", event.Type, m.obj.GetStatus())
}

有状态的状态机

GoFlow 的状态机是一种非常简单或者说偷懒的实现，主要问题在于这是一个有状态的状态机。听起来很奇怪，状态机本来不就是用来维护状态的吗。这里的状态其实指的是状态机本身的状态。简单来说，当 FSM 被实例化之后，这个用来维护任务的状态的 FSM 只能在当前进程（或者说副本）中使用，因为其他副本并没有这个 FSM 实例对象。

对于一个长时间运行的任务引擎来说，这件事情本身也无可厚非，但是换个场景，比如一个电商订单被创建之后，状态机实例也随之创建。如果这个订单只能被创建该订单的副本进程执行，其他副本均无法处理该订单，这是不可接受的。

状态机的无状态化有两种实现，一种是“集中处理”的方式，一种是“用时构造”的方式。

“集中处理”适合长尾任务，比如任务引擎，一个状态机是长时间存在的。该方式让多个副本通过类选主，选择出一个特定的副本来实例化 FSM，当其他的副本需要执行状态流转时，通过 RPC 或者事件的方式让持有 FSM 的副本处理。基于事件的实现方式是最优的，毕竟状态机本身也算是一个事件驱动的模式。这种设计的好处是简单、容易理解，当然坏处也比较明显，依赖了分布式的消息组件。

“用时构造”适合短时任务，比如电商订单的 API 请求，状态机只有在用的时候才需要存在。该方式是状态机不再维持当前状态，而是只存储状态流转图，在需要状态流转时，根据当前的实时状态重建状态机，在状态流转结束后，对状态机进行销毁。

最后

状态机本身并不是一个复杂的模型，甚至说得上简单。但是基于状态机延伸出的附加条件比较繁琐，比如状态嵌套、状态并行等，很多开源项目覆盖了的场景更全面，但也导致其实现十分复杂和效率低下。繁重的实现反而阻碍了在小场景的使用状态机的勇气。毕竟用 NASA 的方法论去制造一个木板凳是个很怪异的事情。所以不如尝试放手一搏，写一个贴近自己场景的 FSM。劝君上当，上当一回。

key state 状态机

0 人点赞