状态机引擎选型

概念

有限状态机是一种用来进行对象行为建模的工具,其作用主要是描述对象在它的生命周期内所经历的状态序列,以及如何响应来自外界的各种事件。在电商场景(订单、物流、售后)、社交(IM消息投递)、分布式集群管理(分布式计算平台任务编排)等场景都有大规模的使用。

状态机的要素 状态机可归纳为4个要素,即现态、条件、动作、次态。“现态”和“条件”是因,“动作”和“次态”是果。详解如下: ①现态:是指当前所处的状态。 ②条件:又称为“事件”。当一个条件被满足,将会触发一个动作,或者执行一次状态的迁移。 ③动作:条件满足后执行的动作。动作执行完毕后,可以迁移到新的状态,也可以仍旧保持原状态。动作不是必需的,当条件满足后,也可以不执行任何动作,直接迁移到新状态。 ④次态:条件满足后要迁往的新状态。“次态”是相对于“现态”而言的,“次态”一旦被激活,就转变成新的“现态”了。 状态机动作类型 进入动作(entry action):在进入状态时进行 退出动作:在退出状态时进行 输入动作:依赖于当前状态和输入条件进行 转移动作:在进行特定转移时进行

为什么需要状态机

有限状态机是一种对象行为建模工具,适用对象有一个明确并且复杂的生命流(一般而言三个以上状态),并且在状态变迁存在不同的触发条件以及处理行为。从我个人的使用经验上,使用状态机来管理对象生命流的好处更多体现在代码的可维护性、可测试性上,明确的状态条件、原子的响应动作、事件驱动迁移目标状态,对于流程复杂易变的业务场景能大大减轻维护和测试的难度。

技术选型

有限状态机的使用场景很丰富,但在技术选型的时候我主要调研了squirrel-foundation(503stars)spring-statemachine(305stars)stateless4j(293stars),这三款finite state machine是github上stars top3的java状态机引擎框架,下面我的一些对比结果。

stateless4j

核心模型

stateless4j是这三款状态机框架中最轻量简单的实现,来源自stateless(C#版本的FSM)

  • StateRepresentation状态表示层,状态对应,注册了每状态的entry exit action,以及该状态所接受的triggerBehaviours;
  • StateConfiguration状态节点的配置实例,通过StateMachineConfig.configure创建,由stateRepresentation组成;
  • StateMachineConfig状态机配置,负责了全局状态机的创建以及保存,维护了了state到对应StateRepresentation的映射,通过当前状态找到对应的stateRepresentation,再根据triggerBehaviours执行相应的entry exit action;
  • StateMachine状态机实例,不可共享,记录了状态机实例的当前状态,并通过statemachine实例来响应事件;

核心实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
protected void publicFire(T trigger, Object... args) {
...
//获取triggerBehaviour, destination/trigger/guard
AbstractTriggerBehaviour<S, T> triggerBehaviour = getCurrentRepresentation().tryFindHandler(trigger);
if (triggerBehaviour == null) {
//异常流程,当前state无法处理trigger
unhandledTriggerAction.doIt(getCurrentRepresentation().getUnderlyingState(), trigger);
return;
}
S source = getState();
OutVar<S> destination = new OutVar<>();
//状态迁移,设置目标状态
if (triggerBehaviour.resultsInTransitionFrom(source, args, destination)) {
Transition<S, T> transition = new Transition<>(source, destination.get(), trigger);
//执行source的exit action
getCurrentRepresentation().exit(transition);
//执行stateMutator函数回调,设置当前状态为目标destination
setState(destination.get());
//执行destination的entry action
getCurrentRepresentation().enter(transition, args);
}
}

优缺点

优点

  • 足够轻量,创建StateMachine实例开销小;
  • 支持基本的事件迁移、exit/entry action、guard、dynamic permit(相同的事件不同的condition可到达不同的目标状态);
  • 核心代码千行左右,基于现有代码二次开发的难度也比较低;

缺点

  • 支持的动作只包含了entry exit action,不支持transition action;
  • 在状态迁移的模型中缺少全局的observer(缺少interceptor扩展点),例如要做state的持久化就很恶心(扩展stateMutator在设置目标状态的同时完成持久化的方案将先于entry进行persist实际上并不是一个好的解决方案);
  • 状态迁移的模型过于简单,这也导致了本身支持的action和提供的扩展点有限;

结论

  • stateless4j足够轻量,同步模型,在app中使用比较合适,但在服务端解决复杂业务场景上stateless4j确实略显单薄。

spring statemachine

核心模型

spring-statemachine是spring官方提供的状态机实现。

  • StateMachineStateConfigurer 状态定义,可以定义状态的entry exit action;
  • StateMachineTransitionConfigurer 转换定义,可以定义状态转换接受的事件,以及相应的transition action;
  • StateMachineConfigurationConfigurer 状态机系统配置,包括action执行器(spring statemachine实例可以accept多个event,存储在内部queue中,并通过sync/async executor执行)、listener(事件监听器)等;
  • StateMachineListener 事件监听器(通过Spring的event机制实现),监听stateEntered(进入状态)、stateExited(离开状态)、eventNotAccepted(事件无法响应)、transition(转换)、transitionStarted(转换开始)、transitionEnded(转换结束)、stateMachineStarted(状态机启动)、stateMachineStopped(状态机关闭)、stateMachineError(状态机异常)等事件,借助listener可以trace state transition;
  • StateMachineInterceptor 状态拦截器,不同于StateMachineListener被动监听,interceptor拥有可以改变状态变化链的能力,主要在preEvent(事件预处理)、preStateChange(状态变更的前置处理)、postStateChange(状态变更的后置处理)、preTransition(转化的前置处理)、postTransition(转化的后置处理)、stateMachineError(异常处理)等执行点生效,内部的PersistingStateChangeInterceptor(状态持久化)等都是基于这个扩展协议生效的;
  • StateMachine 状态机实例,spring statemachine支持单例、工厂模式两种方式创建,每个statemachine有一个独有的machineId用于标识machine实例;需要注意的是statemachine实例内部存储了当前状态机等上下文相关的属性,因此这个实例不能够被多线程共享

核心实现

AbstractStateMachine#sendEventInternal acceptEvent事件响应

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private boolean sendEventInternal(Message<E> event) {
...
try {
//stateMachineInterceptor事件预处理
event = getStateMachineInterceptors().preEvent(event, this);
} catch (Exception e) {
...
}
if (isComplete() || !isRunning()) {
notifyEventNotAccepted(buildStateContext(Stage.EVENT_NOT_ACCEPTED, event, null, getRelayStateMachine(), getState(), null));
return false;
}
boolean accepted = acceptEvent(event);
stateMachineExecutor.execute();
if (!accepted) {
notifyEventNotAccepted(buildStateContext(Stage.EVENT_NOT_ACCEPTED, event, null, getRelayStateMachine(), getState(), null));
}
return accepted;
}

AbstractStateMachine#acceptEvent 使用队列存储事件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
protected synchronized boolean acceptEvent(Message<E> message) {
State<S, E> cs = currentState;
...
for (Transition<S,E> transition : transitions) {
State<S,E> source = transition.getSource();
Trigger<S, E> trigger = transition.getTrigger();
if (cs != null && StateMachineUtils.containsAtleastOne(source.getIds(), cs.getIds())) {
//校验当前状态能否接受trigger
if (trigger != null && trigger.evaluate(new DefaultTriggerContext<S, E>(message.getPayload()))) {
//存储迁移事件
stateMachineExecutor.queueEvent(message);
return true;
}
}
}
...
}

DefaultStateMachineExecutor#scheduleEventQueueProcessing 事件处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
private void scheduleEventQueueProcessing() {
TaskExecutor executor = getTaskExecutor();
if (executor == null) {
return;
}
Runnable task = new Runnable() {
@Override
public void run() {
boolean eventProcessed = false;
while (processEventQueue()) {
//event queue -> tigger queue
eventProcessed = true;
//最终的transition得到处理,包括interceptor的preTransition、postTransition以及listener的事件通知都在这个过程中被执行
//具体实现可参看DefaultStateMachineExecutor.handleTriggerTrans以及AbstractStateMachine中executor的回调实现
processTriggerQueue();
while (processDeferList()) {
processTriggerQueue();
}
}
if (!eventProcessed) {
processTriggerQueue();
while (processDeferList()) {
processTriggerQueue();
}
}
taskRef.set(null);
if (requestTask.getAndSet(false)) {
scheduleEventQueueProcessing();
}
}
};
if (taskRef.compareAndSet(null, task)) {
//默认实现为sync executor,执行上面的task
executor.execute(task);
} else {
requestTask.set(true);
}
}

优缺点

优点

  • Easy to use flat one level state machine for simple use cases.
  • Hierarchical state machine structure to ease complex state configuration.
  • State machine regions to provide even more complex state configurations.
  • Usage of triggers, transitions, guards and actions.
  • Type safe configuration adapter.
  • Builder pattern for easy instantiation for use outside of Spring Application context
  • Recipes for usual use cases
  • Distributed state machine based on a Zookeeper
  • State machine event listeners.
  • UML Eclipse Papyrus modeling.
  • Store machine config in a persistent storage.
  • Spring IOC integration to associate beans with a state machine.
  • listener、interceptor机制方便状态机monitor以及持久化扩展;

缺点

结论

  • spring statemachine由spring组织孵化,长远来看应该会逐渐走上成熟,但目前而言确实太年轻,离业务的落地使用上确实还有太多坑要踩,鉴于这些原因我也没有选择这个方案。

squirrel-foundation

核心模型

squirrel-foundation是一款很优秀的开源产品,推荐大家阅读以下它的源码。相较于spring statemachine,squirrel的实现更为轻量,设计域也很清晰,对应的文档以及测试用例也很丰富。

  • StateMachineBuilderFactory:StateMachineBuilder工厂类,负责解析状态定义,根据状态定义创建对应的StateMachineBuilder;
  • StateMachineBuilder:StateMachine构造器,可复用构造器,所有状态机由生成器创建相同的状态机实例共享相同的状态定义;
  • StateMachine:状态机实例,通过StateMachineBuilder创建,轻量级内存实例,不可共享;支持对afterTransitionCausedException、beforeTransitionBegin、afterTransitionCompleted、afterTransitionEnd、afterTransitionDeclined beforeActionInvoked、afterActionInvoked事件的自定义全局处理流程,作用类似于spring statemachine中的inteceptor;
  • Condition:squirrel支持动态的transition,同一个state接受相同的trigger,statecontext不一样,到达的目标状态也可以不一样;
  • StateMachineListener:全局事件监听,包括了TransitionBeginListener、TransitionCompleteListener、TransitionExceptionListener等几类用于监听transition的不同阶段的监听器;

核心实现

squirrel的事件处理模型与spring-statemachine比较类似,squirrel的事件执行器的作用点粒度更细,通过预处理,将一个状态迁移分解成exit trasition entry 这三个action event,再递交给执行器分别执行(这个设计挺不错)。 部分核心代码 AbstractStateMachine#internalFire

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
private void internalFire(E event, C context, boolean insertAtFirst) {
...
if(insertAtFirst) {
queuedEvents.addFirst(new Pair<E, C>(event, context));
} else {
//事件队列
queuedEvents.addLast(new Pair<E, C>(event, context));
}
//事件消费,采用这种模型用来支持sync/async事件消费
processEvents();
}
```
AbstractStateMachine#processEvents
``` java
private void processEvents() {
//statemachine是否空闲
if (isIdle()) {
writeLock.lock();
//标记状态机正在忙碌,避免同一个状态机实例的事件消费产生挣用
setStatus(StateMachineStatus.BUSY);
try {
Pair<E, C> eventInfo;
E event;
C context = null;
while ((eventInfo=queuedEvents.poll())!=null) {
// response to cancel operation
if(Thread.interrupted()) {
queuedEvents.clear();
break;
}
event = eventInfo.first();
context = eventInfo.second();
processEvent(event, context, data, executor, isDataIsolateEnabled);
}
ImmutableState<T, S, E, C> rawState = data.read().currentRawState();
if(isAutoTerminateEnabled && rawState.isRootState() && rawState.isFinalState()) {
terminate(context);
}
} finally {
//标记空闲
if(getStatus()==StateMachineStatus.BUSY)
setStatus(StateMachineStatus.IDLE);
writeLock.unlock();
}
}
}

AbstractStateMachine#processEvent

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
private boolean processEvent(E event, C context, StateMachineData<T, S, E, C> originalData,
ActionExecutionService<T, S, E, C> executionService, boolean isDataIsolateEnabled) {
...
try {
//执行StateMachine中定义的transitionBegin回调
beforeTransitionBegin(fromStateId, event, context);
//执行注册的listener中transitionBegin回调
fireEvent(new TransitionBeginEventImpl<T, S, E, C>(fromStateId, event, context, getThis()));
//明确事件是否可被accept
TransitionResult<T, S, E, C> result = FSM.newResult(false, fromState, null);
StateContext<T, S, E, C> stateContext = FSM.newStateContext(this, localData,
fromState, event, context, result, executionService);
//执行Condition确认目标状态,生成exit state--transition-->entry state 三个内部事件,通过executor的actionBucket存储
fromState.internalFire(stateContext);
toStateId = result.getTargetState().getStateId();
if(result.isAccepted()) {
//真正执行actionBucket中存储的exit--transition-->entry action
executionService.execute();
localData.write().lastState(fromStateId);
localData.write().currentState(toStateId);
//执行listener的transitionComplete回调
fireEvent(new TransitionCompleteEventImpl<T, S, E, C>(fromStateId, toStateId,
event, context, getThis()));
//执行StateMachine中声明的transitionCompleted函数回调
afterTransitionCompleted(fromStateId, getCurrentState(), event, context);
return true;
} else {
//事件无法被处理
fireEvent(new TransitionDeclinedEventImpl<T, S, E, C>(fromStateId, event, context, getThis()));
afterTransitionDeclined(fromStateId, event, context);
}
} catch (Exception e) {
//标记statemachine状态为ERROR, 不再响应事件处理直至恢复
setStatus(StateMachineStatus.ERROR);
lastException = (e instanceof TransitionException) ? (TransitionException) e :
new TransitionException(e, ErrorCodes.FSM_TRANSITION_ERROR,
new Object[]{fromStateId, toStateId, event, context, "UNKNOWN", e.getMessage()});
fireEvent(new TransitionExceptionEventImpl<T, S, E, C>(lastException, fromStateId,
localData.read().currentState(), event, context, getThis()));
afterTransitionCausedException(fromStateId, toStateId, event, context);
} finally {
executionService.reset();
fireEvent(new TransitionEndEventImpl<T, S, E, C>(fromStateId, toStateId, event, context, getThis()));
//执行StateMachine中声明的transitionEnd函数回调
afterTransitionEnd(fromStateId, getCurrentState(), event, context);
}
return false;
}

优缺点

优点

  • 代码写的不错,设计域很清晰,测试case以及项目文档都比较详细;
  • 功能该有的都有,支持exit、transition、entry动作,状态转换过程被细化为tranistionBegin->exit->transition->entry->transitionComplete->transitionEnd,并且提供了自定义扩展机制,能够方便的实现状态持久化以及状态trace等功能;
  • StateMachine实例创建开销小,设计上就不支持单例复用,因此状态机的本身的生命流管理也更清晰,避免了类似spring statemachine复用statemachine导致的deadlock之类的问题;
  • 代码量适中,扩展和维护相对而言比较容易;

缺点

  • 注解方式定义状态转换,不支持自定义状态枚举、事件枚举;
  • interceptor的实现粒度比较粗,如果需要对特定状态的某些切入点进行逻辑处理需要在interceptor内部进行逻辑判断,例如在transitionEnd后某些状态下需要执行一些特定action,需要transitionEnd回调中分别处理;

结论:

  • 目前项目已经使用squirrel-foundation完成改造并上线,后面会详细介绍下项目中是如何落地实施squirrel-foundation状态机改造以及如何与spring集成的一些细节;