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

/**
  * @author : ahuaxuan
  * @date 2009-10-27
  */

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

现在我来说说我的实现。
状态机的本质是状态的迁移,即从A状态+某个动作===》B状态。到这里我们还要来看看这张图。

从这张图中我们可以看到,状态(大写字母)+动作(小写字母)可以到达新的状态。那么对于程序员来说,我们要做的就是将这种机制用程序表达出来。比如说我们最常想到的是什么?矩阵!

这很好理解,但是对于工作流引擎来说,由于状态的迁移涉及到:当前状态+动作+条件===》新状态。
所以用二维的矩阵无法表示出这种逻辑。那么我们可以将矩阵中的元素替换为条件数组。
这样,我们可以通过当前状态+动作得到一个条件数组,然后再遍历这个条件数组,条件数组中的元素即是条件和满足条件的下一个状态(虽然本质上是一个三维数组,但是在这里还是看成矩阵+数组元素比较符合逻辑)。

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

这里需要画一个图,一个矩阵,矩阵中的元素是一个条件数组

没错,这是一种方案,但是这里有一个问题,那就是每次做状态迁移的时候,我们必须知道某个状态在矩阵一维上的index,已经某个动作在矩阵二维上的index.有了这两个index我们才能得到条件数组。所以这里还有一个繁琐的转换操作操作。来看一段伪代码:


1.conditions = matrix[getStatusIndex[‘A’], getActionIndex[‘a’]]  
2.For condiction in conditions:  
3.       If condition match input:  
4.              Return Condition.nextStatus  

核心流程大概就是这样,当

那么除了矩阵这种数据结构,我们还有其他的数据结构可以用来表示: “当前状态+动作+条件===》新状态”吗。

当然有,那就是使用树结构。在了解了三维数组的实现之后,再来看树实现,应该和容易了,那就直接上图, 将上图的矩阵转换成树结构之后,我们可以得到如下的树结构。

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

那现在我们来审视一下现在的问题,打个比方,我们现在手里有两张牌,一张是状态A,一张是动作a,我们如何通过这两种牌来得到条件集合呢,最简单的方法是首先遍历第二层节点,找到A,然后再遍历A的子节点,找到a。通过两次for循环找到了条件集合,而条件集合中包含着下一个状态。

那么有没有更简单更快速的方式可以直接找到条件集合,而直接跳过两次遍历呢。有,ahuaxuan的想法是tree+hash.也就是通过A的hash值,我们可以直接找到tree上的A节点。然后再通过a的hash值,我们可以直接找到A的子中的a节点。得到a节点之后我们就可以条件集合。那么我们可以用什么样的数据结构来实现一个这样的模型呢。这里面有hash运算,那么我们首先选择HashMap来创建这么一颗树。

我们来看一下这个定义: 


Map<String, Map<String, Map<String, List<Transition>>>> dfa。  


那么我们如何根据A,和a来得到一个条件集合呢? 


Dfa.get[“processName”].get[“A”].get[“a”]  


通过这样的方式,我们就可以根据当前状态和当前的动作得到一个条件集合。然后遍历这个条件集合就是找到满足“输入“的条件,该条件会指向下一个状态。

我们来看一下代码实现:
首先我们来构造这么一个状态机: 


1.private void constructDfa(List<WfProcess> processList) {  
2.        for (WfProcess pro : processList) {  
3.            Map<String, Map<String, List<Transition>>> pmap = new HashMap<String, Map<String,List<Transition>>>();  
4.            dfa.put(pro.getName(), pmap);  
5.              
6.            for (State sta : pro.getStates()) {  
7.                Map<String, List<Transition>> smap = new HashMap<String, List<Transition>>();  
8.                pmap.put(String.valueOf(sta.getName()), smap);  
9.                  
10.                for (Action action : sta.getActions()) {  
11.                    List<Transition> transitions = new ArrayList<Transition>();  
12.                    for (String transName : action.getTransNames()) {  
13.                        transitions.add(pro.getTransitions().get(transName));  
14.                    }  
15.                      
16.                    smap.put(String.valueOf(action.getName()), transitions);  
17.                }  
18.                  
19.            }  
20.        }  
21.    }  


接着我们来看看如何根据这个状态机来做状态迁移: 


1.public String getNextState(String processName, String stateId, String actionId, Map<String, String> conditions) {  
2.          
3.        List<Transition> transitions = dfa.get(processName).get(String.valueOf(stateId)).get(String.valueOf(actionId));  
4.          
5.        for (Transition trans : transitions) {  
6.            if (match(trans.getConditions(), conditions)) {  
7.                return trans.getToState();  
8.            }  
9.        }  
10.          
11.        StringBuilder sb = new StringBuilder();  
12.        sb.append("There is no state for process : ").append(processName);  
13.        sb.append(", stateId : ").append(stateId);  
14.        sb.append(", actionId : ").append(actionId);  
15.        sb.append(", conditions : ").append(conditions);  
16.          
17.        throw new WorkFlowStateException(sb.toString());  
18.    }  


通过这种tree + hash的方式,我们可以很容易的进行状态的迁移,不需要那么多for循环。但是for循环确实有这样的实现。

今天早上下载了osworkflow的代码,稍微看了一下AbstractWorkflow的doAction方法。
发现osworkflow就是通过循环来实现状态的迁移的,比如说上图中树结构的状态可以用以下伪代码: 


1.For state in states:  
2.    If state.name == inputStateName:  
3.        For action in state.actions:  
4.            If action.name == inputActionName:  
5.                    for transition in action.transitions:  
6.    …………………………………………………………………  

通过这种方式,用户传入inputStateName和inputActionName, osworkflow得到了一组transition,并根据条件选择某个transition, 这样也实现了状态的转移。

从这里面可以看出,osworkflow是利用广度优先的原则,先找到符合条件的state,然后再找到符合条件的action,以此类推。

说到这里,通过这种状态机实现工作流引擎的方式基本的完全的,较为清晰的呈现在我们眼前了。

未完待续 
上一篇:js前端模块化的前世今生


下一篇:python 基础语法知识