领英重写了实验引擎：速度提升 20 倍

本文最初发布于领英技术博客，经领英官方授权由 InfoQ 中文站翻译并分享。

在领英，我们常说公司的血液中流淌着实验的基因，因为公司要发布任何产品之前都必须经过实验的检验。所谓“实验”一般指的是“A/B 测试”。领英依靠员工通过数据分析来做出决策。实验是决策流程的数据驱动基础，它可以帮助精确衡量每次变更和发布所产生的影响，并评估产品的期望是否与现实情况相符。

领英的实验平台有着庞大的运作规模：

• 它可以提供高达 800,000QPS 的网络调用，

• 它可以同时运行大约 35,000 个 A/B 实验，

• 它每天可以处理多达 23 万亿次实验评估，

• 实验评估的平均延迟为 700ns，第 99 个百分位数则为 3μs，

• 它被用在大约 500 个生产服务中。

这一平台的核心是领英实验引擎，简称“Lix 引擎”。这一引擎需要处理数量巨大的评估和 QPS，并在整个公司范围内广泛应用，因此它的库必须具备很高的性能和资源使用效率，并遵循严格的测试、验证和发布流程。我们知道，对该引擎做出的每一点优化和改进，都会对整个公司的生产服务性能产生重大影响。最近我们就完成了一项重大改进工作，以满足不断增长的需求。

领英服务和 Lix 引擎

图 1 显示了领英服务与 Lix 引擎交互的机制。首先，Lix 引擎会评估 A/B 测试请求并返回实验（treatment）或对照（control）组。根据 Lix 引擎的结果，服务将对应的功能页面返回给会员。

什么是 Lix 引擎，它的作用是什么？

从概念上讲，Lix 引擎是一种软件，它可以理解用于实验的领域特定语言（也就是 Lix DSL），并能执行以下三种功能：

1. 对测试总体进行随机分割，

2. 对总体进行细分，

3. 为参与实验的给定实体分配实验变体。

进行 A/B 测试的一个前提条件是将测试总体分为随机、独立的样本桶。为 Lix 引擎提供了样本桶的相对权重后，引擎就可以无缝执行分桶操作。

按 1:4.5 加权的总体随机分割

实验过程的另一个重要需求是向特定的总体子集（例如，所有应届生）发布功能。Lix 引擎可以将总体分为多个群组（称为细分，segmentation），并针对每个细分独立执行随机分割：

总体细分

总体的细分和随机分割都封装在类似 Lisp 的实验 DSL 包中。例如，上图在 DSL 中表示为：

（ab (all) [treatment 18.2 control 81.8]）；

而图 2 中的示例表示为：

（ab (is-student) [treatment 50 control 50] (is-job-seeker) [treatment 25 control 75]）。

Lix DSL 拥有多个优点：

1. 它很灵活：Lix DSL 程序交付给服务时独立于代码和配置部署，这样实验的生命周期就可以独立于代码发布的生命周期。由于 Lix DSL 交付生产的速度快如闪电，因此当更改或回滚的速度要求非常高时，它们还可用作功能标志，或用于流量路由配置。

2. 它是确定性的：给定相同的实验和实验 DSL，评估完成后总会为会员分配相同的实验组，这意味着我们不必跟踪之前的会员分配，或进行远程调用来检索此类信息。

3. 它的用途受到限制：DSL 只能执行一组基本操作，不能执行诸如循环或递归调用之类的动作。这样可以防止语言滥用，并能简化静态分析工作。

两年前的状态

Lix 引擎创建于 2012 年左右，最初是用 Clojure 编写的。从那时起它一直运行在领英内部负责评估实验。随着时间的流逝，它开始受到一系列不同问题的困扰，这些问题是引擎的设计缺陷和所选实现语言的特性导致的。我们最近对系统进行改造时，这些都是我们要解决的挑战。

弱类型，边缘场景和宽松的语法

为了支持实验评估，Clojure Lix 引擎在 DSL 中定义了以下数据类型，包括原语和集合：

上一代类型系统

看起来这是一个结构良好，定义明确的类型系统，但是它的实际表现不是很好，原因有二：

• 引擎核心中没有类型检查。每个步骤中都要执行所有验证，扩展能力很差。

• 不支持多态，静态或动态都不行。这样就很难处理(= “string” “string”)或(= 1 2.0)之类的对比了——它们都必须经过代码中的同一个入口点，并且需要开发人员来负责正确识别所有可能的输入值组合，还得按正确顺序处理它们。

内存、垃圾回收和执行速度方面的问题

多年来，我们在 Clojure Lix 引擎中发现了多个性能问题。

内存

影响效率的一个主要因素来自于内存管理。由于 Clojure 延迟评估的特性，引擎会在 JVM 的堆中创建大量临时对象（例如延迟序列）。使用 Clojure 引擎时，这些临时对象至少占据了服务中 30%的 Java 堆。

垃圾收集

与常规 Java 集合相比，Clojure 的不可变数据结构占用了太多的内存空间。大量对象和巨大的内存占用导致了生产中过长的 GC 暂停（约 0.5 秒），因为临时对象可以在多个 GC 周期中幸存下来并移动到 JVM 的老对象（old generation）上。

速度

另一大性能问题是速度。性能下降并不是单一原因导致的。相反，它是以下几个因素的共同结果：

• 经常使用反射（reflection）API，

• 动态对象和方法发现，

• 弱类型，Clojure 端的延迟评估和低效率的类型转换，

• Lix DSL 端的异常处理和锁定。

没有 Clojure 开发人员=没法开发

另一个问题是公司缺少熟练的 Clojure 开发人员。公司中只有很少的工程师能理解和编写 Clojure 代码（后者更为关键），因此这拖累了我们的生产力。

重写

目标

实验平台是领英公司最常用的库之一，在维护它的过程中，我们意识到第一版引擎缺少了很多内容，并存在诸多缺陷；因此我们开始开发 v2 版本，希望达成以下目标。

新版引擎必须足够快，同时具备：

• 较低的内存占用和垃圾足迹。

• 较快的执行速度。

新版引擎必须易于开发和维护：

• 引擎代码必须容易理解。

• 在语言中添加新的操作不能花费太长时间。

新版引擎必须足够安全：

• 类型安全是标配。

• 引擎应该让开发人员很难出错。

• 它必须具备广泛的测试覆盖。

选项

在开始重写前，我们需要做出一些决策：

• 语言选择。我们用 Java 制作了一个用于概念验证的语言解析器和评估器。结果令人惊讶：我们的代码并没有做大量优化工作，但性能却达到了之前版本的 2-3 倍！鉴于 Java 是公司中使用最广泛的语言，并且有着最丰富的技术栈，因此我们很容易就决定改用 Java 了。

• 解释 vs 字节码生成。我们运行了许多基准测试，结果发现，虽然字节码生成的性能表现最出色，但 Lix DSL 解释的性能已经够用了，并且能大大减少我们花费在实现上的时间。于是我们决定将 DSL 解析为评估树，然后执行它们，以此来解释 DSL。

• 编译时代码生成 vs Java 反射 API。我们决定要支持操作重载，以自动将执行（execution）路由到与参数兼容且签名是“最佳”的方法上。根据我们的基准测试，合适的类型解析代码速度大约是 Java 反射的 3 倍，前者是 15ns，后者为 45ns。

实现

在 v2 版引擎的开发过程中，我们提出了许多有趣的想法并发现很多新事物。下面我们会分享其中一些最重要的内容。

规范

为了让新的实现具备类型安全的特性，我们必须指定语言中每个元素的行为，其中包括它们的契约（例如输入参数类型和操作的返回类型）。规范中还加入了元数据，这样我们就可以在实验 UI 中读取并编辑这些元数据了。具体请参见此处的示例。

我们用规范文件来为操作自动生成 Java 实现，其中包括用于所有已定义操作重载的抽象方法，还包括了参数解析代码，后者会在后文讨论。

评估树

与 DSL 语法树类似，我们引入了 DSL 评估树，其中每个节点都可以基于一个输入实体（例如会员/来宾）、上下文和从子树返回的值来计算一个值。

这个树以两种类的形式来定义：这两种类分别是AbstractEvalTree和AbstractEvalNode。EvalTree是一种高级实现，因为我们没有在每个节点的对象中存储子节点，而是将所有信息都移动到了评估树类中，并以三个数组的形式存储了下来（示例见图 5）：

• AbstractEvalNode[]节点，其中包含树的所有节点，并且根节点始终位于索引 0 处，

• byte[]childCounts，其中第 i 个元素是上述数组中节点 node[i]的子节点数，

• short[]childListStartPositions，其中第 i 个元素定义数组节点中，节点 node[i]的子节点列表的起始索引。每个节点的子节点都在数组节点中占据连续的空间，因此要遍历节点[i]的所有子节点，必须从节点[childListStartPositions[i]]遍历到节点[childListStartPositions[i]+childCounts[i]-1]。

考虑以下 DSL 表达式的评估树：

(and (= (string-property “osVersion”) “1.2.3”) (in (country-code) [“us” “gb”]))

评估树

评估树存储在以下数据结构中。

评估树的存储

在这里我们考虑了一种简单方法，以上述结构的节点形式来实现树。

与简单方法相比，我们现行的方法有许多优势：

• 较低的内存开销。Java 在对象的内存表示方面效率是很低的。现行方法下，在启用了压缩 OOP 的 32 位 JVM 或 64 位 JVM 中实现上述树的开销是 60 字节：

• 每个对象 12 字节

• 3 个数组 48 字节（每个数组 16 字节）

而简单方法下是 208 字节：

• 每个对象 12 字节

• 4 数组列表需要 196 字节（每个数组列表 48 字节）。

• 执行速度更快。令人惊讶的是，我们从简单方法切换到现行方法后，性能提升到了 2.5 倍之多，原因在于：

CPU 更喜欢顺序内存访问和较小的数据结构，因为CPU高速缓存较小，而主内存访问速度很慢。

切换到三个普通数组后，我们还消除了 Java ArrayList 数据结构上虚拟调用的开销。

我们的节点通常执行的是轻量级操作，因此树的遍历速度很关键。

类型解析和代码生成

每个评估节点都有其特定的处理逻辑，但它们还需要能应对任何场景，这意味着：

1. 编译时节点不知道将从子节点返回什么类型的值。

2. 节点应该能够在构建评估树时或在运行时解决操作的重载。

如前所述，我们决定不使用 Java 反射 API，而是让代码根据子节点返回的值类型来解析适当的重载方法。为了避免重复编写样板代码，我们决定以抽象方法的形式自动生成用于操作重载的存根，并根据 DSL 语言规范自动生成参数解析代码。

使用自动生成的代码可以显著降低实现的复杂度，因为开发人员只需要实现特定参数类型的处理逻辑即可。我们还能调整所有 DSL 操作实现的行为，从而节省了很多时间。

远程调用，短路

因为我们这种语言完全在我们的掌控之下，所以我们还可以执行一些高级优化工作。下面就讨论其中一个例子。

为了执行细分，操作通常需要会员属性数据，这会导致网络调用并增加评估延迟。完整的本地评估最快的执行速度是 50ns，而远程调用的 p99（第 99 个百分点）延迟为 4ms。例如，我们在图 1 中讨论的 is-student 操作需要获取会员的教育经历数据以做处理，但是某些操作不需要远程调用，因此我们可以利用这一点并避免昂贵的查询操作。在以下示例中，如果字符串属性“osVersion”未返回“7.1.1”，我们将不执行远程调用：

(ab (and (ge (connection-count) 30) (= (string-property “osVersion”) “7.1.1”)) [treatment 50])

从技术上讲，这里的优化是在本地执行期间禁用“and”和“or”操作的短路，并尝试在其中找到至少一个可以完全在本地执行并返回“false”的子分支。

图 7 显示了使用和不使用远程调用优化的评估过程。

启用和没有启用远程调用优化的评估

性能优化结果

做了这么多工作和优化之后，我们实现了以下改进：

• 顺序评估快至 20 倍，并发评估快至 14.7 倍，

• 内存占用效率提升至 10.2 倍，

• 临时对象生成速率减小到 1/6，并且没有超过 50ms 的 GC hiccup。

验证

可以说，编程语言是很难验证的，因为你要测试的是具有无限可能状态的高动态系统。因此，我们在新 DSL 的验证和发布过程中小心谨慎，步步为营。

单元测试

首先我们编写了大量的单元测试，让引擎运行时代码的行覆盖率至少达到 80-90％。

测试用例生成器

为了声明新代码的功能与旧代码完全相同，我们必须证明 v1 和 v2 版本的引擎生成的结果完全相等。我们发现，一种完美的方法是获取所有生产 DSL，并在其上分别运行 v1 和 v2 版的引擎，同时触发评估树的所有可能执行分支。于是我们想到了自动生成测试数据的简单方法。了解程序的结构以及每个运算符的工作机制后，我们就可以解析树并递归生成输入数据，以触发不同的程序分支。

例如，我们可以从图 4 中获取以下 DSL 表达式：

(and (= (string-property “osVersion”) “1.2.3”) (in (country-code) [“us” “gb”]))

可能的执行顺序如下：

1. (= (string-property “osVersion”) “1.2.3”)返回 false，并且(in (country-code) [“us” “gb”])的返回值无关紧要。

应为属性“osVersion”分配一个随机值以触发分支。

2. (= (string-property “osVersion”) “1.2.3”)返回 true，但(in (country-code) [“us” “gb”]) returns 返回 false。

应为属性“osVersion”分配“1.2.3”。

“Country-code”会员属性应设置为“us”或“gb”以外的任何值。

1. (= (string-property “osVersion”) “1.2.3”)和(in (country-code) [“us” “gb”]) 都返回 true。

应为属性“osVersion”分配“1.2.3”。

“Country-code”会员属性应设置为“us”或“gb”。

自动生成的测试用例

为每个解析树分支构建测试套件并将这些测试递归组合后，我们就可以构建一套全面的测试，触发所有 DSL 执行分支的 99.9％，其中 99％的分支返回多个不同的值。

Hadoop 中的分布式脱机验证

获得 99.9％的置信度对我们来说还不够，因此我们在生产 Hadoop 群集中计算了 4,000 种运行时参数组合与 2,000,000 种会员属性集的乘积，从而生成了 8,000,000,000 个测试用例。我们使用它们在数千个内核上进行了分布式验证来对比 v1 和 v2 版本的引擎，并达到了所有生产 DSL 分支的 99.9998％覆盖率。

爬坡

但是，完成实现并不是故事的终点。实际上，上线这个库并将数百个领英服务迁移到 v2 版本的引擎上，是该项目最具挑战性的部分之一。

我们为这个库制定了一项上线计划，其目标如下：

1. 迁移过程对实验平台用户是透明的。

2. 爬坡（ramping）过程可由团队控制。

3. 影响是可衡量的。

为了以中心化的方式控制爬坡过程，我们发布了带有内部 A/B 测试的实验客户端库版本，可以在 v1 和 v2 版的引擎之间切换。使用该库的所有服务都升级到了这个版本，并且我们能够通过 A/B 测试来控制爬坡并衡量其影响。

上线过程

我们用了 37 次迭代和 8 个月的时间来爬坡、测量、更新和迭代。在上线期间，我们发现将引擎代码集成到目标服务中时存在一些问题，即便经过如此严格的测试，我们也无法在本地捕获这些问题。我们还在爬坡过程中理解了远程调用缓存的重要性，并且在生产中同时 A/B 测试了多达三种缓存逻辑“风味”（flavor）。

影响

鉴于我们的库是领英基础架构中使用最多的库之一，因此我们对其进行的任何更改都会产生巨大的影响。这次重写后：

• 我们将公司所有 API 端点的性能平均提高了 0.5％；

• 一些关键服务的速度快至两倍。

• 我们在所有服务中释放了总计超过 4TB 的已用内存。

• 我们在成千上万的机器上获得了更好的垃圾收集持续性能。

致谢

我们要感谢 T-REX 团队的所有成员，如果没有他们在实验平台上的辛勤工作，这个项目将是不可能完成的。非常感谢管理团队的Igor Perisic、Kapil Surlaker、Ya Xu、Suja Viswesan、Vish Balasubramanian和Shaochen Huang，以及 T-REX 校友Shao Xie的持续投入和指导。领英的许多团队都参与了我们引擎的上线过程。我们感谢他们的合作。特别感谢实验数据科学团队和 EPCSRE 团队的支持。

原文链接：

Making the LinkedIn experimentation engine 20x faster