微流引擎的算法与实现

Question

我正在开发微流引擎(后端)，这是一个在运行时执行的流程流。

考虑下图，其中每个进程都是一个Java类。从一个进程到另一个进程都有一些变量。由于流本质上是动态的，因此可以使用许多网关(GW)和进程来实现非常复杂的流。

DFS/BFS是实现运行时引擎的好选择吗？有什么想法吗伙计们。

​

​

Answer 1

就给定的示例而言，它是通过深度优先搜索(DFS)解决的，使用输出节点作为树的“根”。

这是因为：

• 要获得值，需要Process4
• Process4的输出才能生成输出，需要Process2和Process3
• Process2 / Process3的输出才能生成输出，它们需要GW
  • 的输出才能生成输出它需要Process1

  的输出

因此，一般的想法是从每个输出做一次DFS，一直到输入。

从输出的角度来看，对于任何看起来像有向无环图(DAG，或者实际上是树)的东西，这几乎都是一样的。

如果工作流最终具有“循环边”或“反馈循环”，也就是说，如果它现在看起来像一个图，那么将需要额外考虑，以避免无限遍历和重新评估流程输出。

最后，如果工作流需要知道“时间”的概念(通常)，那么将需要额外考虑，以便确保尽管图是逐个节点地逐步评估的，但最终它已经为时间实例(n)生成了正确的输出。也就是说，您希望避免一些进程仅仅因为它们被更频繁地调用而在当前时间实例之前产生输出。

这个问题中已经有一个微不足道的例子。由于DFS，GW将被评估为Process2 (或Process3)，但它不必为Process3 (或Process2)重新评估(对于相同的时间实例)。在处理DAG时，您可以简单地在每个进程上添加一个"Evaluated“标志，该标志在遍历开始时被清除。然后，如果DFS发现它还没有被评估，它将决定向下下降到节点的分支。否则，它只是获取在前一次遍历期间评估过的某个流程的输出。(这就是我之前提到“几乎如前所述”的原因)。但是，这个微不足道的技巧在多个反馈循环中不起作用。在这种情况下，您真的需要让节点“意识到”时间的流逝。

要获得更多信息和对相关问题的全面阐述，我强烈建议您访问Bruno Preiss' Y logic simulator。尽管它是在C++中，并且是一个逻辑模拟器，但它所经历的考虑因素与任何类似的互连“抽象节点”系统所面临的问题完全相同，这些系统应该执行某种形式的“处理”。

希望这能有所帮助。