LOGO

基于有向无环图的策略引擎设计


设计背景

业务初期阶段流程简单,只需要通过单层if else就可以处理不同场景下的需求。

当业务成熟后场景繁多,需要兼容的,需要依赖的条件更多,代码上补丁摞补丁,任何改动都可能带来未知的结果。此时无论是单层逻辑判断还是多层嵌套判断都不能优雅的扩展,更加不易维护和更新迭代。因而有此设计。

基础概念

图由顶点和连接这些顶点的边所构成。
每条边都带有从一个顶点指向另一个顶点的方向的图为有向图。
有向图中的道路为一系列的边,系列中每条边的终点都是下一条边的起点。
如果一条路径的起点是这条路径的终点,那么这条路径就是一个环。
有向无环图即为没有环出现的有向图。维基百科

设计思想

首先我们用抽象思维去看复杂业务,任何业务都具备以下特质:

  1. 无论多复杂都是流程(对应图的某条可达路径)
  2. 都可能存在参数依赖(对应图边数据输入)
  3. 都有执行逻辑(对应图的节点)
  4. 都有结果输出(对应图边数据输出)
  5. 都有条件分支(对应图内部各个多路径出节点)

以此,我们可以将业务的复杂流程分支转化为DAG图结构,if else的判断变成策略状态变化。
图的每个节点都有一系列状态,并由状态机维护,将策略可执行部分转化为图节点的执行动作,变为无状态。
策略引擎只表示流程的分支(业务流程必将结束且只作出1个最终决策),因此与for while 循环无关,所以策略引擎是有向无环图,而不是有环图。

图存储结构

邻接矩阵

邻接矩阵

参见:维基百科

邻接矩阵 邻接矩阵

策略引擎

伪代码示例

定义一个有起始根节点和结束根节点的DAG,DAG的每一条边都是在某些情况下程序可能执行的路径,如:上左图,a节点作为起始根节点,e节点作为结束根节点, 那么路径“a -> c -> e” 的伪代码逻辑表示:

传统逻辑版

// 伪代码
// 假设我们有业务逻辑如下:
// 先经过 b c d e 四个判断,
// 然后进入 c, 再进行 d,e判断,
// 选择 e并执行 doSthE()
// 最终输出结果 resultE

int argA; //表示有一个输入参数
if(cond(b, argA)) { // 判断 b,c,d,e(因为a的出边为b,c,d,e)
  //输出 resultB
} else if(cond(c, argA)) { // 符合c的条件
    // 输出 resultC
    // 符合, 进行下一步
    int resultC = doSthC(); //输出了个结果 resultC, 并在下游继续使用
    if(cond(d, resultC)) {  //再判断 d, e
         // 输出 resultD
    } else if(cond(e, resultC)) { 
         // 输出 resultE
         // 符合
         int resultE = doSthE(); //执行逻辑
         //最终返回 resultE
    }
   
} else if(cond(d, argA)) {
     ...
} else if(cond(e, argA)) {
     ...
}

这只是简单的两层逻辑判断,实际业务中的逻辑分支可能既广又深。

策略引擎版

// 定义若干个执行策略,与前面保持一致,这里有abcde5个执行策略
// Strategy 表示一个策略类, 
// 在程序启动后就初始化好策略所需要的基本数据(如 db相关的,配置相关的)
// 对于动态数据,则以参数的形式动态传入
// 我们定义了如下几个策略
// 每个策略都是将上游结果作为输入(取决于DAG的边构建),策略内部会判断是否用它,
// 每个都会返回一个结果
StrategyA a;  // 根策略,直接输出 argA
StrategyB b;  // 输出 resultB
StrategyC c;  // 输出 resultC 相当于上面代码的 "int resultC = doSth1(); "
StrategyD d;  // 输出 resultD
StrategyE e;  // 输出 resultE

//构建DAG图(程序启动后就构建好了)
DAG graph = new DAG();
//添加图节点(这时还没有可达路径关系)
graph.addNode(a);
graph.addNode(b);
graph.addNode(c);
graph.addNode(d);
graph.addNode(e);
//构建边,即上面普通代码中的if条件分支
graph.addEdge(a, b);  // a->b的边
graph.addEdge(a, c);  // a->c的边
graph.addEdge(a, d);  // a->d的边, 以下雷同
graph.addEdge(a, e);
graph.addEdge(b, d);
graph.addEdge(c, d);
graph.addEdge(c, e);
graph.addEdge(d, e);
//初始化DAG调度器
DagScheduler dagScheduler = new DagScheduler();
// 以上部分全部是在程序启动后进行,与业务请求无关。

//在每次业务请求中执行图调度
Response xxxxHandler(Request request) {
  dagScheduler.schedule(graph, input= request.argA);
   // 图路径 “a -> c -> e” 的最终结果 resultE
   int resultE = graph.getFinalDagNode().getResult();
   return XXX;
}

策略可以再进行分类为:

  • 分支策略:只负责逻辑判断,相当于IF ELSE组合
  • 逻辑策略:只负责执行具体动作,只要被调度起来就开始干活,不考虑逻辑。

每个分支策略都存在一个结果集合{resultA, resultB, resultC, …. },每次会输出其中之一。

对等的在其下游挂上分别接收{resultA, resultB, resultC, …. }参数的逻辑策略, 每个逻辑策略只要碰到了自己的参数,就可以执行。

这是处理最常见的多分支流程(无聚合),从图的角度来说,这是一棵有向树。

引擎调度

在策略引擎中,所有节点都有如下状态:

  • CREATED //节点已经创建
  • PREPARED //准备开始调度
  • START //开始调度
  • WAITING //等待执行
  • RUNNING //正在执行
  • SUCCESS //执行成功
  • FAILED //执行失败
  • INEFFECTIVE //无效节点(父节点失败后下游单依赖子节点全部无效)
  • TIMEOUT //执行超时

所有节点都会被引擎调度到“PREPARED”状态,根节点首先被调度到“RUNNING”状态,其下游路径节点获得“WAITING”状态,根节点执行完毕后只有符合条件的下游节点会被调度到“RUNNING”状态进行逻辑执行;
同层级不符合条件的会被转化为“FAILED”状态,对应下游所有单依赖节点都会被迫变成“INEFFECTIVE”状态(说明该路径永不可达)。
获得执行的节点输出的结果会被引擎路由给该路径下游所有节点,下游节点顺势获得“RUNNING”状态,在其逻辑内部对上游传递过来的结果进行判断是否使用,然后继续输出结果给下游,直到DAG终节点结束得到最后结果。

在策略引擎中,策略流程是可以配置的,动作逻辑是原子化的,做到充分解耦。
策略引擎可以为每次执行都记录执行路径(如“a -> c -> e”),也可以对执行历史进行存储、分析和可视化。将传统代码模式的N层补丁式逻辑嵌套,变成透明的可阅读可分析的流程。

JavaRed介绍

JavaRed库是一种以有效直观的界面定义和管理异步、并行执行流。JavaRed 需要 JDK 1.8 或更高版本。

RedSynchronizer执行器

Red Synchronizer DAG
ListenableFuture<String> executeA();
ListenableFuture<String> executeB(String aResult);
ListenableFuture<String> executeC(String aResult);
ListenableFuture<String> executeD(String bResult, String cResult);
ListenableFuture<String> executeE(String aResult);
ListenableFuture<String> executeF(String eResult);
ListenableFuture<String> executeG(String fResult);
ListenableFuture<String> executeH(String dResult, String gResult);

Result<String> aResult = produceFutureOf(String.class).byExecuting(this::executeA);
Result<String> bResult = ifResult(aResult).succeed().produceFutureOf(String.class).byExecuting(this::executeB);
Result<String> cResult = ifResult(aResult).succeed().produceFutureOf(String.class).byExecuting(this::executeC);
Result<String> eResult = ifResult(aResult).succeed().produceFutureOf(String.class).byExecuting(this::executeE);
Result<String> dResult = ifResults(bResult, cResult).succeed().produceFutureOf(String.class).byExecuting(this::executeD);
Result<String> fResult = ifResult(eResult).succeed().produceFutureOf(String.class).byExecuting(this::executeF);
Result<String> gResult = ifResult(fResult).succeed().produceFutureOf(String.class).byExecuting(this::executeG);
return ifResults(dResult, gResult).succeed().produceFutureOf(String.class).byExecuting(this::executeH);

继承实现

public class Example1 extends RedSynchronizer<String, Boolean> {
    @Override
    protected Result<Boolean> handle(String s) throws Throwable {
        // implementation of the flow
    }
}

public class Example2 extends RedVoidSynchronizer<String> {
    @Override
    protected Marker handle(String s) throws Throwable {
        // implementation of the flow
    }
}

代码参考


文章作者: 鲁君树人
版权声明: 本篇文章采用 CC BY 4.0 版权协议『必须署名,可共享,可演绎』,转载请注明来源 幺蛾日记 !
评论
 上一篇
KAD(Kademlia)算法介绍 KAD(Kademlia)算法介绍
Kademlia协议(简称Kad)是美国纽约大学的PetarP. Maymounkov和David Mazieres. 在2002年发布的一项研究结果。 Kad 通过独特的以异或算法(XOR)为距离度量基础,建立了一种 全新的 DHT 拓扑网络结构。
2022-01-06
下一篇 
三维定位技术概要 三维定位技术概要
无法获取文章摘要。本文为加密文章,联系文章作者获取阅读密码。
2021-11-01
  目录