超轻量级有限状态机Mini-FSM

背景介绍

Mini-FSM：超轻量级有限状态机框架，已在Github开源

有限状态机(Finite State Machine，简称FSM)，表示有限个状态以及在这些状态之间的转移和动作等行为的处理模型。在任何给定的时间点，有限状态机都处于某一特定状态，并且可以根据当前状态和输入条件，从当前状态转移到另一个状态。有限状态机相关的核心概念主要包括：

• 实体(Entity)：状态机的主体和作用对象，它的状态可以改变
• 状态(State)：实体在某一特定时间点的情况，可分为现态(当前状态)、次态(跳转新状态)
• 事件(Event)：导致状态转换的触发器和条件
• 动作(Action)：状态转换时执行的操作，可以发生在状态转换前、转换中、转换后阶段

状态转移图

跳转

有限状态机除了使用状态转移图表示，也可以使用状态转移表呈现，展示基于当前状态和其他输入，要移动到什么状态的表格。例如：当前状态（B）和条件（Y）的组合指示出下一个状态（C）。

很多调度系统和工作流系统都会内置状态机管理，用于维护状态转移的事件处理。例如，YARN(资源调度系统)将各种处理逻辑抽象为事件和对应的事件调度器。每类事件的处理过程可分割成多个步骤，用有限状态机表示。

处理请求作为事件进入系统，由中央异步调度器(Async-Dispatcher)负责传递给相应事件调度器(Event Handler)。事件调度器可能将事件转发给另外一个事件调度器，也可能转发给一个带有有限状态机的事件处理器，其处理结果也以事件的形式输出给中央异步调度器。而新的事件会再次被中央异步调度器转发给下一个事件调度器，直至达到终止条件才处理完成。

YARN事件处理模型

跳转

实现方式

有限状态机有不同的实现方式，具体取决于具体的应用场景，常见的实现方式有：

• Switch Case/枚举实现：基于枚举类型表示状态，定义一个方法来处理状态转换，转移过程可基于Switch 匹配语句实现
• 查找表：基于二维数组或者哈希表维护状态转移表，其中一维表示当前状态，另一维表示输入条件(时间)，表格中的元素则表示下一个状态。该方法处理简单便捷，适合非复杂场景
• 状态模式：State Pattern，是一种行为设计模式。将对象的状态分离并封装到专用的状态类，使得对象状态可灵活变化，当状态改变时会相应改变对象的行为
• 状态机框架：基于现成的状态机库或框架处理，功能较丰富且完整

状态模式

每个状态都是一个对象，这些对象共享一个公共状态接口。状态机持有一个状态对象的引用，所有的事件处理和动作执行都委托给这个状态对象。当状态转移时，状态机将引用切换到另一个状态对象。

• Context：上下文(状态机)，保存具体状态的引用，通过状态接口与状态对象交互，提供设置器用于接收新的状态对象
• State：状态，以接口类的形式定义状态的公共方法，用于事件处理和动作执行
• Concrete States：具体状态，继承State，实现特定状态对应的事件处理方法。可保存Context的反向引用，从Context获取所需信息并触发状态转移

其中，Context和具体状态都可以设置Context的下个状态， 并通过触发变更Context的状态引用实现状态转移。

状态模式结构

跳转

状态机框架

Spring Statemachine

Spring Statemachine (SSM) 是一个框架，允许在Spring 应用程序中使用传统的状态机概念。SSM 提供以下功能：

• 易于使用的一级状态机，适用于简单的用例
• 分层状态机结构，以简化复杂的状态配置
• 状态机区域提供更复杂的状态配置
• 触发器(triggers)、转换(transitions)、检测器(guards)和动作(actions)的使用，其中，transitions指示状态变更，guards检测是否满足从一个状态切换到另外一个状态的条件
• 类型安全的配置适配器
• 状态机事件监听器
• Spring IoC 集成将 bean 与状态机相关联

更多详情可查看：官方文档

Cola StateMachine

Cola：Clean Object-Oriented and Layered Architecture的缩写，代表“整洁面向对象分层架构”。COLA分为两个部分，COLA架构和COLA组件，其中StateMachine组件实现了有限状态机功能。

跳转

Cola 参考Spring Statemachine设计思想进行简化，有限状态机的核心概念主要包括：

• StateMachine：状态机，维护状态机的上下文
• State：状态
• Event：事件，状态由事件触发，引起变化
• Transition：流转，表示从一个状态到另一个状态
  • External Transition：外部流转，两个不同状态之间的流转
  • Internal Transition：内部流转，同一个状态之间的流转
• Condition：条件，表示是否允许到达某个状态
• Action：动作，到达某个状态之后，可以做什么

核心语义模型

跳转

更多详情可查看：官方说明文档

其他框架

常见的其他状态机开源框架有：

• Squirrel-foundation：一个基于Java的轻量级状态机库
• Stateless：NET中基于C#实现的轻量级状态库，支持各种类型作为状态和触发事件、支持状态继承、支持状态进入/离开事件、支持条件状态转移、支持状态/转移查询，对应的Java版本实现：Stateless4j。

轻量级实现

设计说明

在业务功能实现时，遇到状态流转的管理。针对状态机进行选择，遇到几个问题：

• 复杂性：开源系统丰富的功能，有很多高级转换功能，但对于我们系统来说太多复杂且不必须，引入会增加系统复杂性
• 性能问题：开源的状态机都是有状态的（Stateful）的，对应实例线程不安全，在使用过程中存在性能问题

Cola StateMachine的状态机本身是无状态（Stateless）的，且实现较简洁，因此选择基于Cola StateMachine 和 Spring StateMachine 的设计思想进行简化。在系统内部内嵌了简单的有限状态机管理，并根据业务需求扩展了Action执行后的返回结果ActionResult。其中Action的执行使用响应式编程，基于Flux 和 Mono 实现。

简化的Mini-FSM 有限状态机的主要接口定义包括：

• StateMachine：状态机，维护状态机的上下文
• StateMachineEventResult：状态机事件转换的返回结果，包括获取当前状态、Action结果等
• State：状态，传递事件信息并用于状态转换，FSM核心处理，StateContext 反向引用状态机的上下文
• Event：事件，可基于枚举类定义
• Action：动作，对应具体事件的执行处理
• ActionResult：事件执行的返回结果，封装结果详情
• Guard：条件，表示是否允许到达某个状态
• Transition：流转，表示从一个状态到另一个状态，包括TransitionKind类型，TransitionData 数据

实现架构

Mini-FSM框架实现如下所示：用户基于Event事件触发当前状态转移并返回转移结果。

• sendEvent：Action接受sendEvent请求处理，封装封装transition信息进行transit操作
• transit：基于TransitionData处理，1. 基于Guard校验执行条件；2. 基于Action触发执行Apply并返回执行结果

Transition流转类型分为两类：

• EXTERNAL：外部流转，Event执行变更状态
• INTERNAL：内部流转，Event执行不变更状态，现态与次态保持一致，是EXTERNAL流转的特例

使用示例

更多可参考Mini-FSM中的单元测试类StateMachineTest。

1. 定义状态与事件

可自定义使用枚举类定义State状态 和 Event事件

enum State {
    S1, S2, S3
}
enum Event {
    E1, E23, E22, E13
}

2. 构建状态机

本示例中状态机配置定义包括：

1. S1基于E1的内部流转
2. S2 → S3 基于 E23 的外部流转
3. 模拟S1基于E13的异常流转
4. 模拟S3流转Guard条件校验不通过

Builder<State, Event> builder = StateMachineBuilder.builder();
// FSM状态变换定义
builder.configureTransitions()
    .withInternal() //1.构建内部流转 S1
    .source(State.S1)
    .event(Event.E1)
    .action(context -> {
        sleep(2000);
        assert context.getEvent() == Event.E1;
        return ActionResult.of();
    })
    .and()
    .withExternal() //2.构建外部流转 S2 → S3
    .source(State.S2)
    .target(State.S3)
    .event(Event.E23)
    .action(context -> {
        assert context.getEvent() == Event.E23;
        MessageHeaders headers = context.getMessage().getHeaders();
        String result = ((String) headers.get("info")) + context.getEvent();
        return ActionResult.of(ImmutableMap.of("result", result));
    })
    .and()
    .withInternal()
    .source(State.S1)
    .event(Event.E13) //3.构建内部流转 S1, 模拟异常回滚
    .action(
        context -> {
            System.out.println("mock failed case");
            throw new RuntimeException("event e13 error");
        },
        context -> {
            System.out.println("Drop table Rollback");
            return ActionResult.of(ImmutableMap.of("result", "drop table back"));
        })
    .and()
    .withInternal()
    .source(State.S3)
    .event(Event.E22)
    .guard(context -> context.getEvent() == Event.E13) //4.构建内部流转S3,模拟guard失败
    .action(context -> ActionResult.of());
//构建FSM状态机
StateMachine<State, Event> stateMachine = builder.build();

3. 执行Event事件

(1). 单个Event事件执行，没有返回结果场景

MessageHeaders headers = new MessageHeaders(ImmutableMap.of("info", "123456"));
final StateMachineEventResult<State, Event> inner =
    stateMachine.sendEvent(Message.of(State.S1, Event.E1, headers));
assert inner.getResultType() == ResultType.ACCEPTED;
assert inner.getState() == State.S1;

(2). 单个Event事件执行，具有返回执行结果

final StateMachineEventResult<State, Event> external =
    stateMachine.sendEvent(Message.of(State.S2, Event.E23, headers));
assert external.getState() == State.S3;
ActionResult actionResult = external.getActionResults().iterator().next();//获取结果
assertEquals("123456E23", actionResult.infos().get("result"));

(3). 多个Event事件 同步执行，默认执行方式

List<StateMachineEventResult<State, Event>> results = stateMachine.sendEvents(
    ImmutableList.of(
        Message.of(State.S1, Event.E1, headers),
        Message.of(State.S2, Event.E23, headers)));
assert results.stream().noneMatch(result -> result.getResultType() == ResultType.DENIED);

(4). 多个Event事件 异步执行

List<StateMachineEventResult<State, Event>> async = stateMachine.sendEvents(
    ImmutableList.of(
        Message.of(State.S1, Event.E1, headers),
        Message.of(State.S2, Event.E23, headers)), 
    true); //指定多个事件异步执行
assert async.stream().noneMatch(result -> result.getResultType() == ResultType.DENIED);

(5). 失败事件执行，结果类型为DENIED

final StateMachineEventResult<State, Event> failed =
    stateMachine.sendEvent(Message.of(State.S1, Event.E13, headers));
assert failed.getResultType() == ResultType.DENIED;

(6). 多个事件执行，事件之间相互隔离，失败事件不影响其他事件执行

results = stateMachine.sendEvents(
    ImmutableList.of(
        Message.of(State.S1, Event.E13, headers),
        Message.of(State.S1, Event.E1, headers),
        Message.of(State.S2, Event.E23, headers)));
assert results.size() ==3;
//事件失败的数量=1
assert results.stream().filter(result -> result.getResultType() == ResultType.DENIED).count() == 1;
//事件成功的数量=2
assert results.stream().filter(result -> result.getResultType() == ResultType.ACCEPTED).count() == 2;

(7). Guad校验不通过

StateMachineEventResult<State, Event> guard =
    stateMachine.sendEvent(Message.of(State.S3, Event.E22, headers));
assert guard.getResultType() == ResultType.DENIED;

总结

有限状态机对于复杂的多状态流转管理是有效的，但状态机的执行流程引入会增加系统的复杂性和提升维护难度，因此不能滥用。对于简单的状态流转，例如只有3个状态变换，且执行操作单一，更建议直接使用Switch Case/枚举实现。最后，希望通过本文可了解到FSM框架的一些设计思路。