字节跳动 Service Mesh 数据面编译优化实践

2022-04-06 字节跳动技术团队

前言

字节跳动在内部大规模落地了 Service Mesh，提供 RPC、HTTP 等多种流量代理能力，以及丰富的服务治理功能。Service Mesh 架构包含数据面和控制面，其中，字节跳动 Service Mesh 数据面基于开源的 Envoy 项目进行二次开发及改造，并针对主要的流量代理及服务治理功能进行了重写，项目采用 C++ 语言编写。

我们在优化数据面的历程中，基于 LLVM 编译工具链，围绕 C++ Devirtualization 以及编译优化进行了较多探索，落地了 LTO (Link Time Optimization)、PGO (Profile Guided Optimization) 、C++ Devirtualization 等编译优化技术，获得了 25% 的可观性能收益。本文将分享我们在字节跳动 Service Mesh 数据面的编译优化方向相关工作。

背景

字节跳动 Service Mesh 数据面以及依赖的 Envoy（下称 mesh proxy）为了提供较好的抽象与可扩展性，较多使用了 C++ 的 virtual 函数，虽然这能为编写程序带来极大的便捷性，但是编译后生成的机器指令中会包含大量 indirect call，每个 indirect call 都不可避免地需要进行一次动态跳转，过多的 indirect call 会带来如下问题：

间接指令跳转开销：由于运行期的实际函数（或接口）代码地址是动态赋值的，机器指令无法做更多优化，只能直接执行 call 指令，这对于 cache 局部性、指令预执行以及分支预测都十分不友好。
无法内联优化：由于 virtual 函数的实现本身是多态的，编译中无法得出实际运行期会执行的实现，因此也无法进行内联优化。同时在很多场景下，调用一个函数只是为了得到部分返回值或副作用，但函数实现通常还执行了某些额外计算，这些计算本可以通过内联优化消除，由于无法内联，indirect call 会执行更多无效的计算。
阻碍进一步的编译优化：indirect call 相当于是指令中的一个屏障，由于其本身是一个运行期才能确定的调用，它在编译期会使各种控制流判断以及代码展开失效，从而限制进一步编译及链接的优化空间。

虽然 virtual 函数会较大损失性能，但它又是必需的：第一，很多模块本身就需要动态的子类实现；第二，将功能模块声明为 virtual 接口对于测试编写更友好，便于提供 mock 实现；第三，C++ 对于 virtual 函数及接口的支持较为成熟，代码结构简单清晰，即便对于静态多态的接口，如果不使用 virtual 函数而是换做 template 模式来支持（例如 CRTP），代码结构也会异常复杂，且上手成本较高，较难维护。

考虑到 virtual 函数本身的优势，以及对代码结构的改造成本，我们决定在代码层继续保持 virtual 函数的结构，转而从编译优化的角度对其性能开销进行优化。

调研

针对 virtual 函数的优化（即 devirtualization，或 Indirect Call Promotion）大致可分为三类：Link Time Optimization (LTO)、 Whole Program Devirtualization (WPD) 以及 Speculative Devirtualization，它们大致的原理如下：

Link Time Optimization （LTO）：链接时优化，在编译阶段生成中间编译对象代替传统的二进制对象，并保留了元信息，接着在最终的链接阶段以全局的视角链接所有中间编译对象，执行跨模块的优化手段，并生成二进制代码。LTO 分为 full LTO 和 thin LTO，full LTO 主要串行执行，链接非常耗时，thin LTO 以少量的优化损失作为代价换取并发的执行模型，极大加快链接速度。由于 LTO 在链接阶段具有全局的视角，因此可以进行跨模块的类型推导，进行一定的 devirtualization 优化。
Whole Program Devirtualization （WPD）：通过分析程序中类的继承结构，得到某个 virtual 函数的所有子类实现，并依据这个结果进行 devirtualization。这个优化需要结合 LTO 才能够实施，且经过实践，该优化效果并不理想（后文阐述）。
Speculative Devirtualization：该优化针对某个 virtual callsite，“投机”地假设其运行期的实现是某个或某几个特定的子类，如果命中了，则可以直接显式地调用对应的实现逻辑，否则，再走常规的 indirect call 逻辑。这个优化结合 PGO 才有较好效果。

本文主要关注 Speculative Devirtualization 以及 PGO 优化技术的原理及实践，对 LTO 以及 WPD 的原理不作过多展开。

Speculative Devirtualization 原理介绍

下面以一个例子解释 Speculative Devirtualization 的原理，假设我们编写了一个 Foo 的接口以及一个 FooImpl 的具体实现，如下所示：

struct Foo {
    virtual ~Foo() = default;
    virtual void do_something() = 0;
};

struct FooImpl : public Foo {
    void do_something() override { ... }
};

接着，在其他模块使用了 Foo 接口，如下：

void bar(Foo &foo) {
    foo.do_something();
}

经过编译后，bar 函数的机器指令伪代码大致如下：

addr = vtable.do_something.addr@foo
call *addr

上述伪代码将传入参数 foo 的 do_something 函数的实际地址进行加载，接着对该地址执行一个 call 指令，即动态多态分发的基本原理。

对于上述例子，在 Speculative Devirtualization 优化中，编译器假设在实际运行中，foo 大概率是 FooImpl 的对象，因而生成的指令中，先判断该假设是否成立，如果成立，则直接调用 FooImpl::do_something()，否则，再走常规的 indirect call，伪代码如下：

addr = vtable.do_something.addr@foo
if (addr == FooImpl::do_something)
    FooImpl::do_something()
else
    call *addr

可以看到，上面的伪代码中，获取实际的函数地址后，并没有直接执行一个 indirect call，而是先判断它是不是 FooImpl，如果命中，则可以直接调用 FooImpl::do_something()。这个例子只有一个子类实现，如果有多个，也是类似会有 if 判断，等所有 if 判断都失败后，最后 fallback 到 indirect call。

初步看来，这个做法反而增加了指令量，有悖于优化的直觉。然而，假设大部分调用中， foo 参数的类型都是 FooImpl 的话，实际上只是增加一个地址的比较指令。并且，由于 CPU 指令的顺序执行特征，这里不会有分支跳转的开销（尽管有个 if）。进一步地，直接调用 FooImpl::do_something() 与 else 分支中的 call *addr 在高级语言中看起来似乎并没有区别，然而在编译器的视角中是完全不一样的。这是因为FooImpl::do_something()是明确的静态函数，可以直接应用内联优化，不仅能够省去函数跳转的开销，还可以消除函数实现中不必要的计算。考虑一个极端场景，假设FooImpl::do_something()的实现是个空函数，经过内联后，整个过程由最开始的一个 indirect call，优化成了只需比较一次函数地址即可结束的过程，这带来的性能差异是巨大的。

当然，正如这个优化给人的直觉一样。如果上面 foo 的类型不是 FooImpl，那么这就是个负优化，也正因如此，这个优化在默认情况下基本不会生效，而是要在 PGO 优化中才会被触发。由于在 PGO 优化中，编译器具备程序在运行期的 profile 信息，其中就包括 indirect call 调用各个实现函数的概率分布，因此编译器可以根据这个信息，针对高概率的函数实现开启该优化。

PGO 优化实践

PGO（Profile Guided Optimization），也称 FDO（Feedback Directed Optimization），是指利用程序运行过程中采集到的 profile 数据，来重新编译程序以达到优化效果的 post-link 优化技术。其原理认为，对于特征相似的 input，程序运行的特征也相似，因此，我们可以把运行期的 profile 特征数据先采集一遍，再用来指导编译过程进行优化。

PGO 优化依赖程序运行期所采集的 profile 数据，profile 数据的采集有两种方式，一是编译期插桩（例如 clang 的 -fprofile-instr-generate 编译参数）；二是运行期使用 linux-perf 工具采集，并将 perf 的数据转换成 LLVM 可识别的 profile 格式。对于第二种方式，AutoFDO 是更通用的叫法。AutoFDO 的整体流程如下图所示：

我们的实践采用的是第二种方式：运行期采集 perf 。这是因为，如果采用插桩的方式，就只能采集特定 benchmark 的 profile，而不能采集线上真实流量的 profile，毕竟不可能在线上环境运行一个插桩的版本。PGO 的成功实践极大地促进了 devirtualization 的效果，同时，由于本身也带来了其他的优化机制，获得了 15% 的性能收益，下面介绍我们在 PGO 优化上的重点工作。

基于 Profile 数据的 PGO 优化基本原理介绍

程序运行期采集到的 profile 数据中，记录了该程序的热点函数及指令，这里不做过多展开，以两个简单例子说明它是如何指导编译器做 PGO 优化的。

virtual 函数 PGO 优化示例

第一个例子接着上文中的 Foo 接口。假设程序中除了有 FooImpl 子类外，还存在 BarImpl 以及其他子类，在 Speculative Devirtualization 优化前，程序是直接获取到实际函数地址后执行 call 指令，而 profile 数据则会记录在所有采集到的这个调用样本中，实际调用了 FooImpl、BarImpl 以及其他子类实现的次数。例如，该调用点一共被采样 10000 次，其中有 9000 次都是调用 FooImpl 实现，那么编译器认为这里大概率都是调用 FooImpl，就可以针对 FooImpl 开启 Speculative Devirtualization，从而优化 90% 的 case。可以看出，这个优化对于只有单个实现的 virtual 函数是极佳的，它在保留了未来的 virtual 函数可扩展性的基础上，将其性能优化到与普通直接函数调用无异。

分支判断 PGO 优化示例

第二个例子是一个针对分支判断的优化示例。假设有如下代码片段，该代码片段判断参数 a 是否为 true，若是，则执行 a_staff 的逻辑；否则，执行 b_staff 逻辑。

if (a)
    // do a_staff...
else
    // do b_staff...
return

在编译时，由于编译器并不能假设 a 为 true 或者 false 的概率，通常按照同样的 block 顺序输出机器指令，伪汇编代码如下。其中，先对参数 a 进行 bool 判断，若为 true ，则紧接着执行 a_staff 的逻辑，再 return；否则，便跳转到 .else 处，再执行 b_staff 的逻辑。

test a, a
je   .else  ; jump if a is false
.if:
; do a staff...
ret
.else:
; do b staff...
ret

在 CPU 的实际执行中，由于指令顺序执行以及 pipeline 预执行等机制，因此，会优先执行当前指令紧接着的下一条指令。上面的指令对 a_staff 是有利的，如果 a 为 true，那么整个流水线便一气呵成，没有跳转的开销；相反的，指令对 b_staff 不利，如果 a 为 false，那么 pipeline 中先前预执行的 a_staff 计算则会被作废，转而需要从 .else 处的重新加载指令，并重新执行 b_staff，这些消耗会显著降低指令的执行性能。

从上面的分析可以得出，如果恰好在实际运行中，a 为 true 的概率比较大，那么该代码片段会比较高效，反之则低效。借助对程序运行期的 profile 数据进行采集，则可以得到上面的分支判断中，实际走 if 分支和走 else 分支的次数。借助该统计数据，在 PGO 编译中，若走 else 分支的概率较大，编译器便可以对输出的机器指令进行调整，类似如下的伪汇编指令，从而对 b_staff 更有利。

test a, a
jne  .if  ; jump if a is true
.else:
; do b staff...
ret
.if:
; do a staff...
ret

Profile 数据的采集及转换

为了采集 mesh proxy 运行期的 profile 数据，首先需要进行正常的最优编译并生成二进制。为了避免二进制中同名 static 函数符号的歧义，以及区分同一行 C++ 代码中多个函数的调用，提高 PGO 的优化效果，我们需要新增
-funique-internal-linkage-names 和
-fdebug-info-for-profiling 这两个 clang 编译参数，此外，还需要增加 -Wl,--no-rosegment 链接参数，否则 linux-perf 收集到的 perf 数据无法通过 AutoFDO 转换工具转换成 LLVM 所需的格式。

完成编译后，选择合适的 benchmark 或者真实流量运行程序，并采用 linux-perf 工具采集 perf 数据。经过实践验证，使用 linux-perf 采集时，启用 LBR（Last Branch Record）功能可以获得更佳的优化效果。我们采用如下命令对 mesh proxy 进程进行 perf 数据采集。

perf record -p <pid> -e cycles:up -j any,u -a -- sleep 60

完成 perf 数据采集后，使用 AutoFDO 工具（
https://github.com/google/autofdo）将 perf 数据转换成 LLVM profile 格式。

create_llvm_prof --profile perf.data --binary <binary> --out=llvm.prof

带 PGO 的优化编译

得到 profile 数据后，即可进行最后一步带 PGO 优化的重编译步骤，需要注意的是，该次编译的源码必须和之前 profile 采集用的源码完全一致，否则会干扰优化效果。为了开启 PGO 优化，只需要再添加 -fprofile-sample-use=llvm.prof clang 编译参数，使用该 llvm.prof 文件中的 profile 数据进行 PGO 编译优化。

经过 PGO 编译优化后，mesh proxy 二进制整体的 indirect call 数量降低了 80%，基本完成了 C++ Devirtualization 的目标。此外，PGO 会根据 profile 中的热点函数及指令进行更进一步的内联，对热点指令及内存进行重排，并进一步增强常规的优化手段，这些都能给性能带来显著的收益。

其他编译优化工作

全静态链接及 LTO 实践

在字节 mesh proxy 达到一定的线上规模后，我们遇到了动态链接上的一些问题，包括运行机器的 glibc 版本可能较低，以及动态链接的函数调用本身有多余开销。

考虑到 mesh proxy 本身其实是作为一个独立的 sidecar 运行，并不需要作为一个程序库供其他程序使用，因此，我们提出将 binary 进行全静态链接的想法。这样做的好处有：一是可以避免 glibc 版本问题，二是消除动态链接函数跳转开销，三是全静态链接下可以进一步应用更多编译优化。

支持全静态链接后，由于 binary 没有任何外部库依赖，我们又增加了进一步的编译优化，包括将 thread local storage 的模型改为 local-exec，以及 ThinLTO（Link Time Optimization）优化。其中，ThinLTO 带来了将近 8% 的性能提升。

WPD 的尝试

为了达到 devirtualization 的效果，我们也尝试了 Whole Program Devirtualization，但实际效果并不理想，只有较少一部分的 indirect call 被优化。通过对 LLVM 相应模块实现的研究，我们了解到目前的 WPD 优化只对仅有单个实现的 virtual 函数生效，因此在现阶段还无法带来显著的性能收益。

BOLT post-link 优化

在 LTO、PGO 编译优化的基础上，我们还更进一步探索了 BOLT 这类 post-link 优化技术，并得到了约 8% 的性能收益。考虑到稳定因素，该优化仍在探索与测试中，暂未上线。

后记

希望以上的分享能够对社区有所帮助，我们也在规划将上述编译优化方法回馈到 Envoy 开源社区版本，共同参与 Service Mesh 领域的建设。

参考资料

https://people.cs.pitt.edu/~zhangyt/research/pgco.pdf
https://research.google/pubs/pub45290/
https://clang.llvm.org/docs/UsersManual.html#profile-guided-optimization
https://github.com/llvm/llvm-project/tree/main/bolt
https://llvm.org/devmtg/2015-10/slides/Baev-IndirectCallPromotion.pdf
https://quuxplusone.github.io/blog/2021/02/15/devirtualization/