相亲模型与有限状态机

2022/07/09 21:15 下午 posted in  设计模式

如果有人问你需要几步可以把大象关进冰箱里,你脑海中肯定浮现起宋大妈的笑容并脱口而出: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 这种任务管理系统来说,状态肯定是围绕任务展开的:

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,存储所有的边。这种存储方式可以快速通过一个事件,找到能执行的所有操作。

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 的状态枚举可以看出当前的引擎相对简单,因此它的状态流转图也并不复杂:

构建状态流转图的逻辑:

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. 状态转换完成后,执行对应的动作
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。劝君上当,上当一回。