️This article has been over 1 years since the last update.

本文先从Fibonacci递归计算开始，介绍了通过DP消除栈的算法，以及CPS的基本概念与Jenkins底层实现。

本文读者要求：掌握CPS/DP/Groovy的基本使用，编译理论的基本方法，部分需了解Jenkins。

本文目的：介绍DP、CPS的理论，以及CPS在Jenkins的实践。

What is DP?

DP(dynamic programming，动态规划)是缓存计算结果的方法，通过给参数注入全局缓存/消除栈等方法，降低重复计算成本。

以求fibonacci为例

1
2
3
4
5
6
7
8
9

//  in:0 1 2 3 4 5 6
// out:0 1 1 2 3 5 8
static int fibonacci(int i) {
  if (i <= 1) {
    return i;
  } else {
    return fibonacci(i - 2) + fibonacci(i - 1);
  }
}

上述例子如果你经过调试，就会发现有很多重复计算（因为它是tree recursion），也很容易产生栈溢出，我们尝试使用DP解决

方法一：我们可以加一个全局缓存int[] dp，这种方法与使用Redis当缓存没有区别，也很像“科学管理”中的计算尺

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// 方法一：top down DP，没有消除栈，空间复杂度为O(N)
public static int fibonacci(int i, int[] dp) {
  System.out.println("i = " + i);
  if (i <= 1) {
    dp[i] = i;
    return i;
  } else {
    if (dp[i] != 0){
      return dp[i];
    }
    dp[i] = fibonacci(i - 2, dp) + fibonacci(i - 1, dp);
    return dp[i];
  }
}

方法二，通过for循环求离散点的积分

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// 方法二：down-top，这种方法通过jump消除了栈，仍然消耗了O(N)的空间复杂度
public static int fibonacci(int i) {
  System.out.println("i = " + i);
  if (i <= 1) {
    return i;
  }
  int[] dp = new int[i+1];
  dp[0]=0;
  dp[1]=1;
  for (int j = 2; j <= i; j++) {
    dp[j] = dp[j-1] + dp[j-2];
  }
  return dp[i];
}

方法三，是更优写法，这种通过少数几个寄存器就实现了缓存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// 方法三：递归栈消除+低空间复杂度
public static int fibonacci(int i) {
  System.out.println("i = " + i);
  if (i <= 1) {
    return i;
  }
  int a = 0;
  int b = 1;
  int c = 0;
  for (int j = 2; j <= i; j++) {
    c = a + b;
    a = b;
    b = c;
  }
  return c;
}

在上面的场景中，方法一是保底，而for循环方法需要有积分的数学背景。

迭代与递归的选择/转换

无论是OJ题目，还是真实项目，它们都是现实的问题，现实的问题就有方法论去实施，去分解，所以不要惧怕这些问题。

• 递归的顶层方法论其实是形而上，通过分解为最小任务，并用多个参数实验获取结果。它可以实现最小的状态转移语意，代码量最少，但是可能出现分解思路困难/堆栈异常/忽视关闭条件。
• for循环等迭代底层都是JUMP命令，它没有栈，但是很多逻辑、全局变量混在一起，后面难以维护
• 以上问题均默认不开启编译器尾递归等优

在真实问题中，我个人先使用递归设计出原型，再通过CPS/DP技术去实现Desugar，优化掉递归调用。

拆解方法也是有方法论的，它可以通过DOE(Design of experiments)找出输入与输出的关系，比如

• 通过强制固定一些参数降低动态复杂度，DP一定是确定性的/无状态的，非NP问题
• 输出并不一定确切的值。比如计算EditDistance，只用求最终总和即可，而没要求具体的排列组合，这两个难度完全不一致。

除此之外，还有一些技巧性强的常数复杂度方案甚至经验公式/数学方法，但是这种方法是需要学习与记忆的

What is CPS?

将阻塞的请求改为异步的Callback形式（或者返回一个Promise/Next的结构体），仅此而已。注意网上有很多文章说通过CPS可以消除栈，但是只说对了一半，在没有编译器优化的情况下，并不能将栈优化为JMP调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// Consumer也可以用Groovy的Closure实现
public static void fibonacciCps(int i, Consumer<Integer> call) {
  if (i <= 1) {
    call.accept(i);
  } else {
    fibonacciCps(i - 1, new Consumer<Integer>() {
      @Override
      public void accept(Integer a) {
        fibonacciCps(i - 2, new Consumer<Integer>() {
          @Override
          public void accept(Integer b) {
            call.accept(a + b);
          }
        });
      }
    });
  }
}

使用方法

1
2
3
4
5
6

fibonacciCps(6, new Consumer<Integer>() {
  @Override
  public void accept(Integer sum) {
    System.out.println("sum = " + integer);
  }
});

平时编码这种写法可读性很差，很难显示区分同步还是异步执行，所以基本上没有利用的机会，一般会“人肉AST优化”到DP的第三种。

不过这样的好处是

• 作为AST的中间态，方便编译器进行栈消除
• 实现在JVM上自己的“栈”与“VM”，以及持久化
• 实现数据“状态”的持久化（Checkpoint/Restore），比如Jenkins/CRIU

Jenkinsfile的CPS实现

此部分介绍用户输入的Jenkinsfile脚本在Jenkins底层执行的流程

字符串编译为BlockAST

原始的脚本虽然写的像字符串，执行底层也是Groovy，但是它不是Groovy语言

• 所有Groovy语言的Token关键词(比如if/常数/变量)将不再是一个简单的JVM字节码，而有各个对应的Block，通过MetaMethodSite实现了"编译"为CPS的Block
• 静态工具类调用（比如forEach）/Closure表达式，通过CpsTransformer在编译时/运行时生成CPS转换，除非加入@NoCPS注解。有人可能看过王垠的40行代码，但是王垠的显然更高级。
• 定制的Step，通过FunctionCallBlock封装调用，它内部再使用CpsScript引擎去Eval

在执行侧，Jenkins通过Groovy的Script实现了自己封装了一个Runtime，具体可以看Groovy相关文章，避免自己从零写AST，最终输入的Groovy字符串将转为如下结构体

CPS层执行与栈消除

在CPS的内部AST，是一个Block单向链表，除了Parallel外，其它Block都是线性遍历的，因此设计上很简洁，这个与MyBatis的MixedSqlNode/S-Expression是相同的设计思路

内部通过循环一个单向链表进行消除，是不是很像DP优化的第三种。

1
2
3
4
5
6

// com.cloudbees.groovy.cps.Continuable#run0
Next n = cn.resumeFrom(e,k);
while(n.yield==null) {
  // 我删掉了处理异常的代码行
  n = n.step();
}

JenkinsCPS的缺点

由于它是对Jenkins深度定制的

• 执行CPS必须需要Jenkins服务端（注意Agent只是执行原生字节码的，不处理CPS编排），没有成熟的离线解释器，因此执行调度性能限制于Jenkins单点
• 基于文件进行状态的持久化比较鸡肋，大部分场景中，master重启都会导致任务失败。毕竟是单点工具，没法比得过flink这种级别的Persisted States
• 断点调试很困难，基本上只能靠echo来分析脚本；CPS编程范式导致参数固定
• 作为插件生态开发者，那么Groovy/CPS的学习门槛的确有点高，从整个插件只有Kawaguchi一人主刀也可以看出

更深的语义定制

假如你希望Jenkins能够实现更复杂的编排，或者自己的构建语法，可以尝试基于CPS再实现一层Interceptor，我基于此方案实现了

• YAML interceptor: 配合Macro解析，实现用Java/Groovy实现AzureDevOps的效果，这样就可以将很多cps测试转换为无状态的测试。
• Parallels BFS Tree嵌套并行执行构建
• Log live tail

这些是有门槛的定制场景，网上找不到开源的方案，全靠知识广度的积累。

附录

关于研发效能/DevOps工具的前景

DevOps平台一般由业务部门出预算，属于成本部门，比如“质量与效率工程部”，“研发效能部”，“基础研发平台”，“流程与IT”等名称，裁员很容易是第一批。当然也有可能发展起来后也兼任对外售卖。

• 国内除了大型公司的工具组有预算买现成的或者做这种改进，其它中小公司选择很有限，举例如下

  • 阿里：经常看到阿里的人抱怨打了一天包都打不出来
  • 百度：
    • 前百度研发效能团队自主创业“简单云”，招聘要求那么高，结果北京顶格才4.5万，同样能力还不如在大公司/外企接着苟。
    • 效率云：方案上还不支持config as code
  • 腾讯的蓝鲸对外宣称腾讯全链路构建，结果腾讯内部的Coding/Orange/TYPD等各立山头。
  • 华为云：CloudDev，ROMA Factory DevOps，云龙平台等各搞各的，价格吃水线很高。

• 假如工具要实现产品化可销售，由于技术上难度并不高，导致同质化严重，最好还是背靠大树来做，即和硬件/云一起去做，国内注定是强政府与强销售，要么出海和巨头（Gitlab/Github/Azure DevOps）竞争。

• 我个人认为这类工作很有挑战，因为它需要全局考虑，肯定比单独的业务项目有难度。

  • 机房、机柜、三层交换、云服务的配置
  • 分布式存储（块存储、对象存储）、VPC、分布式调度器（cgroup与容器）的测试与选型
  • 权限设计（IAM/ACL）、大数据度量与分析

参考链接

https://www.kimsereylam.com/racket/lisp/2019/02/14/recursion-with-fibonacci.html

http://arasio.hatenablog.com/entry/2016/10/08/220843

插件开发技巧（如何利用当前Step/Node信息）

由于我不希望定制场景的代码引入到Java层（重启Jenkins成本很高），但是又想获取到实时的Context信息，可以通过如下将业务代码移动到Groovy侧实现热部署

参考例本体的还原

1
2
3
4
5
6
7
8
9
10
11
12
13

// getting context of a *step*
@NoCPS // will not be compiled to CpsClosure, but MethodClosure
def callback(result, Step s, CpsContext c){
  // todo: use context, node and other metadata.
}

// in your cps steps
node{
  def result = sh("xxxxx")
  // implementation in java is required.
  // customStep内部直接调用 callback.call(this, context) 即可触发Groovy
  customStep(callback: this.&callback.curry(result))
}

Jenkins核心调试断点位置

从MQ取到Executor开始执行的位置(之前都是Jenkins的调度过程)

1

org.jenkinsci.plugins.workflow.job.WorkflowRun#run

整个Workflow总断点位置

1

org.jenkinsci.plugins.workflow.cps.CpsFlowExecution#start

如果只关注Step相关流程，可以在这里进行分析

1

org.jenkinsci.plugins.workflow.cps.DSL#invokeMethod