工作流和状态机

原创

王磊-字节跳动

修改于 2020-08-08 22:29:26

6K3

修改于 2020-08-08 22:29:26

文章被收录于专栏：01ZOO01ZOO

起源

因为工作相关的一些原因，最近开始看一些工作流的框架或者产品，有兴趣的可以看我这篇文章。任务流是一种很常见的任务组织形式：

graph LR
Start-->Step1
Step1-->Step2
Step2-->End

这种例子充斥我们的生活，比如订单系统，Hr系统，审批系统，CI/CD 系统，都是任务流的常见引用。

Dag

我们常见两种任务流的实现形式，一种是 DAG，dag 的表达的核心在于描述单个任务, 比如描述一个 Task 他完成什么样的动作，以及他依赖什么样的动作，DAG 的描述和他的名字一样，缺陷在于不支持有环的任务流转（这一点只是为了简化，实际上也有办法实现）

TaskA:
    Actions:
    - 动作 A
    Dependencies:
TaskB:
    Actions:
    - 动作 B
    Dependencies:
    - TaskA
TaskC:
    Actions:
    - 动作 C
    Dependencies:
    - TaskA
    - TaskB

对这个 dag 进行简单的拓扑排序，就能得到他大概的执行流程, 下图为依赖图，首先会执行 TaskA，然后 TaskB，最后 TaskC

graph LR
TaskA-->TaskB
TaskA-->TaskC
TaskB-->TaskC

这个计算过程可以用下面的伪代码来简单描述，可以看出实现非常简单

For task in Tasks:
    if all_done(task's Dependencies):
        do(task)

状态机

状态机是实现任务流的另一种形式，表达的核心在于描述任务流转行为，即 Transition.

下面是一个状态机的例子

Start: TaskA
TaskA:
    Actions:
    - 动作A
    Next:
        TaskB
TaskB:
    Actions:
    - 动作B
    Next:
        TaskC
TaskC:
    Actions:
    - 动作C
    Next:
        End

用一个简化的图表示：

graph LR
Start-->TaskA
TaskA-->TaskB
TaskB-->TaskC
TaskC-->End

对比

Dag	状态机
关注单个任务	关注状态流转
无环（也能实现，不过没这么直观）	可以简单的实现有环
实现简单	比较麻烦，需要记录任务当前状态
可以多个 Start	单个 Start

灵活性

Dag 串行表达，看上去不是很灵活, 而状态机表达更灵活，可以有环，可以任意流转。实际上并非如此：想象这样一种场景，如下图中的任务流程，我们需要新增一个任务 D，在任务 A 后执行，在任务 C 之前执行。对于这种变化，对 Dag 的修改是简单的，我们只需要新增一个节点就可以了, 同时修改节点 D 增加一个依赖:

TaskA:
    Actions:
    - 动作 A
    Dependencies:
TaskB:
    Actions:
    - 动作 B
    Dependencies:
    - TaskA
TaskC:
    Actions:
    - 动作 C
    Dependencies:
    - TaskA
    - TaskB
    - TaskD
TaskD:
    Actions:
    - 动作 D
    Dependencies:
    - TaskA

而对于状态机，同样的修改则更为麻烦，D 应该放在什么位置呢，首先考虑到 D 在 A之后执行，又在 D 之前，那么我们可以推理出：B和D可以并发执行, 然而这个结论并不那么显而易见，对于更负责的任务流转更是如此，涉及的修改也更多。新增一个流程对原先的状态机破坏，可能是颠覆性的。

Start: TaskA
TaskA:
    Actions:
    - 动作A
    Next:
        TaskB
Parallel:
    Tasks: 
        TaskB
            Actions:
            - 动作B
        TaskD
            Actions:
            - 动作D
    Next:
        TaskC
TaskC:
    Actions:
    - 动作C
    Next:
        End

可读性

状态机模型似乎可读性更高，因为 Dag 关注描述任务，一眼很难看出任务流转的模式，状态机直接描述任务流转，内部就可以很明显的看出每个 Stage。事实并非总是如此。想象一个任务流程有几百个任务, 这种情况下，即使是任务流所在的领域，比如 CRM 领域的专家也很难读懂整个任务流，这时候阅读当个任务的动作或者依赖，变成了一种更为简单直观的方式，通过好的前端实现，Dag 的可读性至少不会比状态机差。

效率

不管是从实现相关系统的效率（Dag 的实现更为简单），还是从描述一个任务流程的效率（Dag 的描述更简单，状态机往往有更多概念，比如并行，Map等），还是具体的运行效率（考虑上面的例子，确定两个任务可以并发执行，并不是一件容易的事情）Dag 都有相当的优势。

总结

最近的实现 Aws 的 statemachine spec，以及类似的云厂商都推出了类似的状态机描述 spec，以及对应的实现。cncf 甚至推出了一个更复杂的实现。然而事实却没那么理想，各个云产商应该是跟随 AWS 做了一个错误的决策。

和这些产品相比，AWS 的一个老产品 Simple Workflow 的理念（DAG）则更优秀，不过由于 AWS 当年的实现过于抽象，这个产品也不是很成功，现在已经处于不再更新的状态（开源产品 Argo 有两种表达形态，既可以用 StateMachine，也可以用 Dag 表示）。但是未来的某一天，产品经理们可能会把它从垃圾堆里重新翻出来，因为他们最终发现，这才是正确的产品。