更多关于 RTP 系统的介绍请见 深度预测平台RTP介绍

背景简介

RTP 系统

RTP 系统(即 Rank Service)，是一个面向搜索和推荐的 ranking 需求，支持多种模型的在线 inference 服务。RTP 支持 LR、GBDT 以及 tensorflow 等多种模型及模型格式，并依托 suez 在线服务框架，将样本组装和模型预测一气呵成，提升了业务迭代效率，并在性能和稳定性方面予业务以充分保障。

inference 计算

RTP 上的业务大多数是打分类的场景，它的计算流程由一个 Compute Graph 描述（TF Graph）。从计算逻辑上来看，它可以分为这样三部分：

• 存储读取。根据商品 ID，利用 suez 存储能力，join 读取 Item 字段内容；获取 Query 和 User 信息。
• 特征生成。根据上一步的原始字段值，根据用户的特征配置，加工生成特征（如 match，combo 等），进行离散化以及 embedding 等。以经典的 MLP 为例，我们会最终生成一个大的 feature 矩阵。
• 模型计算。即大规模浮点运算部分，执行矩阵乘和激活等 Graph 节点，获得预测结果。

对于模型计算部分来说，我们利用图优化和 GPU/FPGA 异构计算等手段，在 latency 和 utility 等方面都拿到了不错的效果。本文将重点讨论存储读取和特征生成部分的问题和挑战。

PULL vs. PUSH，通用 vs. 优化

背景

RTP 引擎源于 HA3 搜索引擎，熟悉 HA3、写过插件的人都会多多少少听说过 matchdoc 和 expression。

搜索引擎在进行倒排 match 时，命中的文档一般 相距 都比较远。matchdoc 结构将命中的文档 ID 以及起字段值缓存到一块连续内存中，使后面的 ranking 阶段更加 cache 友好。这便是 matchdoc 的价值。

expression 则是常见的计算表达式 lib，提供了基本的一元二元表达式运算功能，也支持用户自定义 function。

pull，通用

在 2016 年，RTP 是这样计算 feature 的：

这样的实现具有很好的通用性和灵活性，然而在性能方面 expression 的封装却不尽人意。过度的虚函数开销，以及访存不连续带来的 cache miss，通用性带来的 overhead 难以令人接受。

push，优化

在 2017 年，RTP 是这样计算 feature 的：

我们去掉了 expression，而只用 matchdoc 结构存储每一步的中间结果，并且调整了 FOR 的结构，这些带来了 20-30% 的性能收益。

然而，这些改动也耗费了巨大的人力，并且丧失了表达式的一般通用性，feature 处理成为了一个定制的 lib。这样的计算方式，每一步都要缓存所有 feature 结果，这可能并不是必要的。同理而言，对于 matchdoc 中有些只需要使用一次的字段，也并不需要提前缓存。而列结构的计算和存储模型，是否就一定会比行结构好呢？

问题

push 或 pull 是众多优化中矛盾的一个缩影，而最具有问题的代表性。总结以上矛盾，有以下几点：

• 优化丧失了通用性，添加新功能会比之前困难。
• 对于 类型 和 数值 方面的枚举优化，破坏了整洁的代码结构。
• 运算逻辑不变，但改变执行方式需要大量的代码改动，令人望而却步。

解决

codegen

expression 不好，在于性能，但其他方面都很优秀，通用性够强，其本质是 按解释执行。PUSH model 不好，在于定制化没有通用性，而性能上占优势。更抽象的看，各自分别强在 描述 和 执行 上。

框架运算的代码通用化，在于一套系统、binary 可以在适用于所有场景，做到利用框架定义的内容描述自己的算法，而 运行时 我们的系统可以根据描述进行运算。对于 RTP 的某一个算法模型（版本）来说，输入描述、特征运算规则及网络结构，都是在配置里完全已知的，不会随着 Query 而变。对于这些已知的信息，我们实际上可以对各个场景各自进行 hard code，将运行时解释的东西提前到 编译时 解决。将运算描述转换成运算代码，这个过程便是 codegen。

codegen(代码生成) 并不是一项具体技术，它是一种方法和思想。C++、Java 等语言中的宏和模板，protobuf 根据 proto 生成具体语言的执行代码等等，这些都是 codegen 的例子。它们有些是语言内建的机制，有些是 library 的功能。简单的说，codegen 是语言到语言、代码到代码的转换，实现上则是一种编译器。

对于从存储到特征这个场景来说，我们需要将存储的 DSL 和特征 DSL 联合起来，编译成高效的运行代码。利用 codegen，我们可以在编译时保留通用的 expression 描述，不失拓展性和灵活性；而运行时运行的实际代码，也是高效的。

algo/sched 分离思想

解决了一个问题，但还没有解决所有问题。有了编译阶段，但具体怎样生成代码呢？是按照 pull 方式还是 push 方式呢？何时需要 cache？一般来说，编译期 expression（AST）描述了完整的运算过程，但一套规则并不能完美适配所有场景，取得最优性能。

运算描述（algorithm）和执行策略（schedule）分离的思想，在 Halide 一文中已经有了详尽的阐释。从这个角度看，matchdoc 只是一种具象的执行策略，而利用 codegen，我们可以任意地在编译器调度代码，寻找访存的最优解。而 expression 单纯负责描述计算，具体的策略下放给编译引擎，或是优化人员进行人工调优。

codegen 和 algo/sched 分离两者是相辅相成的。没有 codegen，便完全没有了 algo/sched 分离的能力；而 algo/sched 分离是 codegen 所获得最重要的能力，它的价值甚至比运行时提升到编译时更为重要。它可以让我们灵活应对任何一种存储和计算形式，以默认策略为开始，自动调节和人工调优双管齐下。

codegen 要求原本的计算原语需要被拆分开，拥有自由组合的能力。algo/sched 分离则有着更高的要求，它要求运算粒度要被拆分的足够细，拆分的越充分，可以调度的空间和可能性便越高。这也正契合全图化和算子化的方向，功能拆分越细，则灵活度越高，业务越自由，变更成本越小。而 codegen 和 algo/sched 分离的价值，不但会平衡抽象和拆分带来的性能损失，而且会在更广泛的空间上探索性能最优解。

相关工作

在深度学习方面，Tensorflow XLA 算是 codegen 鼻祖，后来的 tvm 与 TensorComprehension 则在方法上更进一步。tvm 注重于多框架和多语言，提供了一些 highlevel 的 schedule api；TensorComprehension 则更注重于利用 polyhedral 方法搜索和优化运算本身。两者都某种程度上同源于 Halide。这些框架重点关注于网络运算，在样本生成和特征生成方面并没有涉足。

在存储和运算方面，Impala 本身具有一定的 codegen 优化的能力，PostgreSQL 的 codegen 则刚刚起步。它们一定程度上解决了按解释执行的问题，也具有一定人工调度的能力。PlinyCompute 是更一般的计算系统，平衡了抽象和性能，但使用的基本方法依然是基本的表达式计算与行列混合式存储。类似的，在 dremio 这样的 OLAP 场景下，Gandiva 利用抽象表达式描述计算和访存 （ Apache Arrow ），通过 codegen 进一步描述转化成运行时高效代码。但 Gandiva 描述力有限，而我们的存储也比 Arrow 更复杂。

Julia，Ravi 等利用 LLVM-Jit 技术试图解决解释性语言的性能问题，但本身不具备 codegen 以及自由调度的能力。GraalVM 打破了语言互操作的界限，将问题统一到 Java bitcode 和 JVM 中，而 Truffle 框架在此基础上提供了良好的语言构建方案。但在我们场景下的代码都是非常 native 的，内存也是由开发者主动管理。已经优化的非常精细的代码再交给 JVM 来 handle，带来的任何 overhead 是无法接受的。

技术方案

IR 表示及 C++ 混合编程

将原本的读取存储和生成特征的过程拆碎和抽象并不难，重要的是将他们用可调度的 expression 表示出来。LLVM IR 是方法之一，还有很多 DSL 可以应用。对于 RTP 应用，我们时常需要操纵复杂的 C++ 结构，不能完全使用某种现有 IR，因此我们需要预先定义一些基本的 C++ 函数和数据结构，利用 IR 的函数机制来进行运算，IR 也需要具备这种能力。

相当多的 codegen 机制是通过自定义数据结构配合 LLVM IR 实现的。不过，LLVM IR 并不擅长于处理 C++ 的类型，也缺乏 C++ 语言的机制（模板，重载等）。对于 C++ 这样的机制复杂的语言，只有原生编译器前端自己做的最好。

HalideIR 源于 Halide 项目，被用于 tvm 做中间表示。使用 HalideIR 是期望能够借助统一的 IR 表示，日后使用 tvm 内置的 schedule 能力。HalideIR 提供了基本的类型能力，但还不够。我们依托 C++ 类型在 HalideIR 上了一套简单的函数注册和重载机制，照顾到了编译器的类型检查，也提供了基本的类型运算能力。

对于 IR，或者语言的选择上来说，求同大于存异，复用大于创造。可以充分利用现有生态和库是第一要务，而语言本身的特性则是越简单越好，越贴近底层越好，因为我们本身在做 codegen，只要机制够用即可，甚至不必特别关心目标编译器生成代码质量，毕竟做 codegen 就把一切握在了手中。

对于无法用 HalideIR 的逻辑，例如构造 C++ STL map，以及 map 查找等，我们定义了一些内置函数。而未来的 UDF 功能，也将依托于函数功能。进一步结合类型运算，我们定义了多种 Cast 方法，从简单的 int 到 string，到复杂的格式 string 到 map，富类型运算也是 codegen 的一个副产品，UDF 接口可以因此变得更自然舒适，而优化也会因此更优雅。

schedule

曾经的 matchdoc 是一个 1000 loc 的 lib，而现在，它只需要几行代码

    auto tmpidx = Variable::make(type_of<int32_t>(), "tmpidx");
    // item 的下标
    auto tmpdocid = Load::make(type_of<int32_t>(), docids, tmpidx, const_true());
    // 存储中的实际 id
    auto cacheValue = OverloadResolver::call("readField",
            {readerVar, tmpdocid});
    // 读取字段值
    auto attrCache = Variable::make(cacheValue.type(), "buffer");
    auto alloc = Allocate::make(attrCache, cacheValue.type(), {},
                                const_true(), Evaluate::make(0),
                                OverloadResolver::call("alloca",
                                        {Sub::make(endIdx, beginIdx) * cacheValue.type().bytes()}), "nop");
    // 分配 cache 部分内存空间 buffer
    auto storeCache = Store::make(attrCache, cacheValue, Sub::make(tmpidx, beginIdx), const_true());
    // 将字段值 cache 写入 buffer
    auto storeAll = For::make(tmpidx, beginIdx, endIdx,
                              ForType::Serial, DeviceAPI::None, storeCache);
    // 对 beginIdx -> endIdx 之间的 item 都执行 storeCache 操作，既缓存字段值

借助 IR 表示，我们可以自由的选择需要把哪些运算中间结果 cache，或者只是一遍过。

而对于以前 FOR 形式的 copy，因为有了 IR 层，运行时的数字变成编译时的常量，vectorize/SIMD 等手段便可任意使用。

在搜索和推荐、广告场景中，Query/User 部分是 1-batch 而 Item 维度计算是 n-batch 的，这个规律在 codegen 下也可以充分利用。

目前我们还没有利用 tvm 的内置的 schedule 逻辑，规整矩阵上的 bound-inference 和我们 C++ 的数据结构上单值到多值的扩展还有矛盾需要解决。schedule 还有很多可以探索的地方，它如编译器的 transform pass，一方面有一些预定义的规则，而更广阔的是根据场景去搜索自己的最佳解决方案。思想上类似 Clang LTO，但使用上更自由和灵活。

codegen & execute

有了 IR，进一步生成可执行代码已经不难了。当然我们不会直接生成汇编，还是要生成一种 中间语言，交给编译器，让它来最终生成可执行代码。方案上有两种选择，一是生成 C/C++ 代码，然后交出去完整编译，二是生成 LLVM IR。LLVM IR 对于类型较少或比较固定，或者有统一抽象类型的语言来说，无疑是首选。但我们的系统需要混合 C++ 编程，直接和 LLVM IR 交互，需要处理复杂的 mangling 规则以及 type inference，带来过多复杂性。而直接生成 C++ 代码，则可以完全利用 C++ 本身的类型机制，适配重载和模板，唯一缺点就是编译时间会相对慢一些，不过相对舒服的多。

而生成 executable 也有两种方案，一是提交给 LLVM-Jit，二是直接生成 so。提交给 LLVM-Jit 的弱势主要在调试上，正常调试可以通过实现 GDB listener，但对 coredump 则无能为力；而使用 perf 也需要实现对应 listener，比较麻烦。但统一到 LLVM-Jit 上的好处就是未来会有更多的可能的优化手段，甚至做到运行时自动 inline 的境界，此时更多的是需要 VM 层协助。两种方案我们都有实现，而选择了编译成 so 方案为默认方式。这样既有代码，也有 so，实现上类似于插件机制，方便调试和调查问题。但会多余在磁盘上生成文件，需要统一管理回收。

实例

来看看最终的结果吧

  for (int32_t doc_idx = idxBegin; doc_idx < idxEnd; ++doc_idx) {
    int32_t docid = (( int32_t*)docids)[doc_idx];
    int32_t item_int32_attr1_value = buffer[(doc_idx - idxBegin)];
    if (!isInvalidValue(item_int32_attr1_value)) {
      SimpleBuffer feature_buffer = SimpleBuffer();
      (void)fillFeatureToBuffer(item_int32_attr1_value, feature_buffer);
      LookupResult<float> lookup_result = getValue(reader, (Fingerprint64(toString(feature_buffer)) % (uint64_t)4\
));
      if ((int)1) {
        (( float*)output)[((doc_idx * (int32_t)1) + (int32_t)0)] = getValue(lookup_result);
      } else {
        (( float*)output)[((doc_idx * (int32_t)1) + (int32_t)0)] = 0.000000e+00f;
      }
    } else {
      for (int32_t zero_idx = (int32_t)0; zero_idx < 1; ++zero_idx) {
        (( float*)output)[(((doc_idx * (int32_t)1) + (int32_t)0) + zero_idx)] = 0.000000e+00f;
      }
    }
  }

if-else 分支条件被显示优化成了 1。for 循环 bound 也变成了常数，下标等都是常数。不需要 cache 的结果也绝不用 buffer 保存，需要 cache 的字段值则是从 buffer 中读取。

效果

codegen 已经成功在双十一淘宝、天猫搜索等深度模型上的字段读取和特征生成部分应用。在 CPU utility 方面，存储读取和特征生成方面有大幅节约。在 latency 方面，因为 latency 将整个特征部分包裹到一起，调度上有了按 item 维度 FOR 的能力，避免了原先纯 Graph 方案中并行的 latency 倾斜问题，有效降低了整体 latency，为用户体验提供保障。

一些讨论

存储和计算结构

RTP 字段目前是列存储格式，虽然最外层按照 item 维度并行，但每个并行块内还是在每个特征下 for item 的。而如果转换为行存格式，则对于每个 item 按照行存顺序生成所有特征更划算一些。如何排布计算，如何排布存储，codegen 能解决一半的问题，更多的需要整套系统的协调联动。

对于 embedding 操作，特征计算实际是在计算 embedding key，对于数组实现便是 offset。从这个角度看，特征计算类似于系统中的控制流，而 embedding vector 的拷贝则是实际的数据流。利用 codegen 方法，我们可以充分对利用各自的特点进行针对性优化，例如混合 item/feature 维度，在计算中做小块的 SIMD。而针对于 embedding vector，则可以绕过 cache，甚至在异构计算中绕过内存。codegen 作为适配层，可以为这种优化提供充分的自由度。

UDF 能力及扩展

传统的插件能力是在程序中定义一些固定的插入点，允许用户通过实现 SDK 抽象接口来实现一些自定义拓展功能。HA3 引擎中的插件便是此路，它要求用户分辨和定义哪些操作是 Query 维度的，哪些操作是 Item 维度的。

UDF（User Defined Function）则是更一般的插件方式，它允许用户在几乎任意位置插入自己的逻辑。Flink UDF 相对引擎的插件形式就优雅许多，每个函数只关心它真正计算需要的参数和计算逻辑，而不是和一些 context 打交道，算是个 pure function。

如果结合 codegen 和代码上的语义分析，其实我们能够分析出哪些运算是 Query 维度的，哪些运是 Item 维度的，可以对其进行合理的分拆和优化。用户只需要去定义运算本身，而计算的执行方式交给框架去分析和级联，这不仅需要 codegen 的胶水能力，还需要计算框架上强大的分析能力。

通过用户声明的 UDF 接口，框架可以自动将数据转换成需求的格式。而真正只关心计算逻辑的用户，也不用在乎这个运算是 elementwise 还是 broadcast。不仅如此，我们甚至可以跨越语言的障碍，用 codegen 减少 UDF 中语言间互操作的 overhead，而用户可以自由选择喜欢擅长的编程语言而不必担心性能问题。

混合的边界

打碎运算和操作是获得调度能力的基础，但拆分的粒度应该如何把握？对于老代码，我们可以利用先验知识，定出 IR 和 C++ 自定义函数的边界；对于新代码，我们如何设计和把握 IR 和 C++ 之间的边界，原则上是越细越好，而实际应用中并没有明确的指南。对于引擎的用户来说，找到 UDF 逻辑实现的边界在哪里，用图表示，还是通过 C++ 等语言编写，则是更困难的问题。

最自然的使用方式自然是用一种语言、一种表达方式解决问题。语法和语义分析是否能做到这一点，能否拥有灵活性的同时降低概念的复杂性，是我们需要继续思考的问题。

总结与展望

本文主要讨论了在 RTP 的存储读取和特征生成场景中 codegen 的应用。利用 IR 和 C++ 混合编程，解决系统的抽象和性能问题，并提供 schedule 的优化能力。从这个角度看，expression 和 matchdoc 还有 fg lib 都只是一个小的功能子集。

目前 codegen 只覆盖了 RTP 的部分特征，还需要继续改写。还有更多的优化可以探索，例如行存的存储格式、利用 prefetch、stream 等方法优化 cache 使用，这些曾经因为代码结构不好做的事情，因为 codegen 而变得容易。有了 codegen，可以做更多的通用的和针对场景的优化。不过也有问题，而对于 UDF 的支持，IR 和 C++ 混合编程的边界在哪里？如何进一步和模型运算部分结合等，这些需要我们继续去发展和解决。目前我们面对的主要是静态的模型，而未来面对动态的 Query 执行的情况，codegen 也需要根据访问情况生成最优代码，在 code(meta) 和 data 两者之间平衡和统一，怎样做样的 cache 和执行策略则是一个更大的话题了。

脱离 RTP，放眼通用的存储和计算框架，每个系统中都需要 codegen 能力。codegen 不但可以调度运算，还能够适配存储，甚至生成数据结构。分布式的计算引擎已经提供了很多 push/pull 的经验，优化单机内的运算以及还有分布式的 io/latency 。但在每个具体场景中，优化方向和方法又不尽相同，如何做到大统一始终是一个难题。而如何自动地调度运算，甚至调度存储以及微观的存储结构，更是很难。codegen 没有给出答案，但给了可能。