状态机引擎选型

状态机引擎选型

概念

有限状态机是一种用来进行对象行为建模的工具，其作用主要是描述对象在它的生命周期内所经历的状态序列，以及如何响应来自外界的各种事件。在电商场景（订单、物流、售后）、社交（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<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事件响应

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 使用队列存储事件

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 事件处理

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<E, C>(event, context));
    } else {
        //事件队列
        queuedEvents.addLast(new Pair<E, C>(event, context));
    }
    //事件消费，采用这种模型用来支持sync/async事件消费
    processEvents();
}

AbstractStateMachine#processEvents

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

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集成的一些细节；

更多文章请访问我的博客
转载请注明出处

时间： 2024-09-07 10:58:58

状态机引擎选型的相关文章

mysql不同版本和存储引擎选型的验证

Mysql的版本和存储引擎较多,为了选择最适合业务使用的系统,需要进行一定的验证,本文描述mysql的验证过程和思路. 主要涉及: Mysql的版本 v Mariadb v Tokudb v Oracle 具体的存储引擎 v Myisam v Innodb v TokuDB v Maria 如下是具体的思路 My.cnf配置 log-bin=mysql-bin 关闭,不要写日志 skip-networking 开启 安装和配置 v mariadb5.5 v Oracle v Tokudb 如上目

squirrel-foundation状态机的使用细节

squirrel-foundation状态机的使用细节 上一篇文章介绍了stateless4j.spring-statemachine以及squirrel-foundation三款状态机引擎的实现原理,以及我为何选择squirrel-foundation作为解决方案.本文主要介绍一下项目中如何使用squirrel-foundation的一些细节以及如何与spring进行集成.在阅读本文前,建议先阅读官方的使用手册. 生命周期 状态机创建过程 StateMachine: StateMachine实

开源大数据查询分析引擎现状

引言 大数据查询分析是云计算中核心问题之一,自从Google在2006年之前的几篇论文奠定云计算领域基础,尤其是GFS.Map-Reduce. Bigtable被称为云计算底层技术三大基石.GFS.Map-Reduce技术直接支持了Apache Hadoop项目的诞生.Bigtable和Amazon Dynamo直接催生了NoSQL这个崭新的数据库领域,撼动了RDBMS在商用数据库和数据仓库方面几十年的统治性地位.FaceBook的Hive项 目是建立在Hadoop上的数据仓库基础构架,提供了一

预告：大数据(hadoop\spark)解决方案构建详解,以阿里云E-MapReduce为例

在2016年09月22日 20:00 - 21:00笔者将在 CSDN学院,分享<大数据解决方案构建详解 :以阿里云E-MapReduce为例>欢迎大家报名,报名链接:http://edu.csdn.net/huiyiCourse/detail/186 ppt地址:https://yq.aliyun.com/attachment/download/?spm=0.0.0.0.PpnciK&filename=%E5%A4%A7%E6%95%B0%E6%8D%AE%E8%A7%A3%E5%8

土制状态机在工作流引擎中的应用

/**   * @author : ahuaxuan   * @date 2009-10-27   */ 很早之前(应该是一年以前),ahuaxuan在用dfa实现文字过滤一文中使用确定有限自动机实现了词典的高速查询.其实在当时那段时间里,由于对状态机有了一定的研究,ahuaxuan也触类旁通的理解了工作流引擎的核心体制.于是当时就用python写了一个小巧的工作流引擎的示例,在这之前ahuaxuan没有看过任何工作流引擎的实现,该实现纯属思维的自我延伸. 现在我来说说我的实现. 状态机的本质是

OA系统选型：选择好的工作流引擎

对OA系统而言,何为好的工作流引擎?我们知道错误的流程运行起来,带来的后果十分严重.因此,如果您的流程在正式使用之前就能得到测试,发现问题,并正确运行,这将会避免很多大麻烦. (10oa系统图形化工作流设计) 如今的OA产业鱼龙混杂,在大多数OA厂商正为是不是真正的"图形化工作流设计"而争执的时候,10oa已经脱身而出. 10oa的"图形化工作流设计和可视化表单设计",已经为千百家客户带来了极大业务扩展性和操作方便性,所见即所得的模式让流程配置更加便捷和顺畅,但10

数据库的选型原则

数据|数据库 一.数据库的选型原则1.稳定可靠(High-Availability) 数据库保存的是企业最重要的数据,是企业应用的核心,稳定可靠的数据库可以保证企业的应用常年运行,而不会因为数据库的宕机而遭受损失.企业的信息化可以促进生产力,但如果选择了不稳定产品,经常影响业务生产的正常运营,则实际效果很可能是拖了企业的后退.无论是计划中(数据库维护等正常工作)还是意外的宕机都将给企业带来巨大的损失,这意味着企业要减低收入.要降低生产力.要丢失客户.要在激烈的企业竞争中丢失信心.信息系统的稳定可

可配置语法分析器开发纪事（四） 构造一个真正能用的状态机（上）

本来说这一篇文章要把构造确定性状态机和look ahead讲完的,当我真正要写的时候发现东西太多,只好分成两篇了.上一篇文章说道一个基本的状态机是如何构造出来的,但是根据第一篇文章的说法,这一次设计的文法是为了直接构造出语法树服务的,所以必然在执行状态机的时候就要获得构造语法树的一切信息.如果自己开发过类似的东西就会知道,类似LALR这种东西,你可以很容易的把整个字符串分析完判断他是不是属于这个LALR状态机描述的这个集合,但是你却不能拿到语法分析所走的路径,也就是说你很难直接拿到那颗分析树.没

SharePoint状态机工作流解决方案（二）：SharePoint中的WF状态机

在前文中我们提到 SharePoint 是在 WF 工作流引擎之上,封装了事件驱动接口的一个工作流平台: SharePoint 在 WF 上扩充了很多 Activity,其中和 WF 密切相关的有三个常用 Activity是: OnWorkflowActivated,CreateTask,OnTaskChanged. 一个简单的 SharePoint 顺序流. OnWorkflowActivated:响应流程启动的事件. CreateTask:生成 SharePoint 的任务. OnTaskC