动态规划与JenkinsCPS技术
2020年02月15日に投稿

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

本文读者要求:掌握CPS/DP/Groovy的基本使用,编译理论的基本方法。

本文目的:介绍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);
}
}

上述例子如果你经过调试,就会发现有很多重复计算,也很容易产生栈溢出,我们尝试使用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;
}

在上面的场景中,我个人最推荐第二种方案,因为思路是很清晰的,熟悉后再尝试优化到第三种

迭代与递归的选择/转换

无论是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”,以及持久化
  • 实现数据“状态”的持久化,比如Jenkins

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都是线性遍历的,因此设计上很简洁,这个与MyBatisMixedSqlNode/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单点
  • 断点调试很困难,基本上只能靠echo来分析脚本;CPS编程范式导致参数固定
  • 作为插件开发者,那么这个Groovy/CPS的学习门槛的确有点高,从整个插件只有Kawaguchi一人主刀也可以看出

更深的语义定制

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

  • YAML interceptor
  • Parallels BFS Tree嵌套并行执行构建
  • Step AOP场景(实时GB级别日志ETL回传)

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

附录

关于Jenkins定制DevOps工具的前景

  • 国内除了大型公司的工具组(比如我就经常看到阿里的人抱怨打了一天包都打不出来)有预算做这种改进,其它中小公司基本只能用现成的。
  • 小公司的DevOps方案(比如深圳很多这种号称提高开发速度的公司)我也调研过,但是很多核心思路、方向都落后业界,而且工资有限,导致产品没有竞争力
  • 我个人认为这类工作很有挑战,因为它需要从裸机OS到容器、网关、Spring/CURD、ELK都要全局考虑,肯定比单独的Spring项目有难度。

参考链接

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层(重启成本很高),但是又想获取到事实的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