摘要：状态机引擎选型概念有限状态机是一种用来进行对象行为建模的工具，其作用主要是描述对象在它的生命周期内所经历的状态序列，以及如何响应来自外界的各种事件。状态机的要素状态机可归纳为个要素，即现态条件动作次态。
状态机引擎选型
date: 2017-06-19 15:50:18
概念
有限状态机是一种用来进行对象行为建模的工具，其作用主要是描述对象在它的生命周期内所经历的状态序列，以及如何响应来自外界的各种事件。在电商场景（订单、物流、售后）、社交（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实例来响应事件；
核心实现
protected void publicFire(T trigger, Object... args) {
...
//获取triggerBehaviour, destination/trigger/guard
AbstractTriggerBehaviour triggerBehaviour = getCurrentRepresentation().tryFindHandler(trigger);
if (triggerBehaviour == null) {
//异常流程，当前state无法处理trigger
unhandledTriggerAction.doIt(getCurrentRepresentation().getUnderlyingState(), trigger);
return;
}
S source = getState();
OutVar destination = new OutVar<>();
//状态迁移，设置目标状态
if (triggerBehaviour.resultsInTransitionFrom(source, args, destination)) {
Transition 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事件响应
private boolean sendEventInternal(Message 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 使用队列存储事件
protected synchronized boolean acceptEvent(Message message) {
State cs = currentState;
...
for (Transition transition : transitions) {
State source = transition.getSource();
Trigger trigger = transition.getTrigger();
if (cs != null && StateMachineUtils.containsAtleastOne(source.getIds(), cs.getIds())) {
//校验当前状态能否接受trigger
if (trigger != null && trigger.evaluate(new DefaultTriggerContext(message.getPayload()))) {
//存储迁移事件
stateMachineExecutor.queueEvent(message);
return true;
}
}
}
...
}
DefaultStateMachineExecutor#scheduleEventQueueProcessing 事件处理
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 目前迭代的版本不多，并没有得到充分的验证，还是存在一些bug的；
StateMachine实例的创建比较重，以单例方式线程不安全，使用工厂方式对于类似订单等场景StateMachineFactory缓存订单对应的状态机实例意义不大，并且transition的注解并不支持StateMachineFactory(stackoverflow上的一些讨论"using-statemachinefactory-from-persisthandlerconfig"、"withstatemachine-with-enablestatemachinefactor")；
我尝试在将StateMachine实例缓存在ThreadLocal变量中以到达复用目的，但在测试同一statemachine accept多个event过程中，如果任务执行时间过长，会导致状态机的deadlock发生(这个issue目前作者在snapshot版本上已修正)；
结论
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
private void internalFire(E event, C context, boolean insertAtFirst) {
...
if(insertAtFirst) {
queuedEvents.addFirst(new Pair(event, context));
} else {
//事件队列
queuedEvents.addLast(new Pair(event, context));
}
//事件消费，采用这种模型用来支持sync/async事件消费
processEvents();
}
AbstractStateMachine#processEvents
private void processEvents() {
//statemachine是否空闲
if (isIdle()) {
writeLock.lock();
//标记状态机正在忙碌，避免同一个状态机实例的事件消费产生挣用
setStatus(StateMachineStatus.BUSY);
try {
Pair 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 rawState = data.read().currentRawState();
if(isAutoTerminateEnabled && rawState.isRootState() && rawState.isFinalState()) {
terminate(context);
}
} finally {
//标记空闲
if(getStatus()==StateMachineStatus.BUSY)
setStatus(StateMachineStatus.IDLE);
writeLock.unlock();
}
}
}
AbstractStateMachine#processEvent
private boolean processEvent(E event, C context, StateMachineData originalData,
ActionExecutionService executionService, boolean isDataIsolateEnabled) {
...
try {
//执行StateMachine中定义的transitionBegin回调
beforeTransitionBegin(fromStateId, event, context);
//执行注册的listener中transitionBegin回调
fireEvent(new TransitionBeginEventImpl(fromStateId, event, context, getThis()));
//明确事件是否可被accept
TransitionResult result = FSM.newResult(false, fromState, null);
StateContext 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(fromStateId, toStateId,
event, context, getThis()));
//执行StateMachine中声明的transitionCompleted函数回调
afterTransitionCompleted(fromStateId, getCurrentState(), event, context);
return true;
} else {
//事件无法被处理
fireEvent(new TransitionDeclinedEventImpl(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(lastException, fromStateId,
localData.read().currentState(), event, context, getThis()));
afterTransitionCausedException(fromStateId, toStateId, event, context);
} finally {
executionService.reset();
fireEvent(new TransitionEndEventImpl(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集成的一些细节；
更多文章请访问我的博客
转载请注明出处
