本文最初发布于领英技术博客，经领英官方授权由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），并能执行以下三种功能：

对测试总体进行随机分割，
对总体进行细分，
为参与实验的给定实体分配实验变体。

进行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拥有多个优点：

它很灵活：Lix DSL程序交付给服务时独立于代码和配置部署，这样实验的生命周期就可以独立于代码发布的生命周期。由于Lix DSL交付生产的速度快如闪电，因此当更改或回滚的速度要求非常高时，它们还可用作功能标志，或用于流量路由配置。
它是确定性的：给定相同的实验和实验DSL，评估完成后总会为会员分配相同的实验组，这意味着我们不必跟踪之前的会员分配，或进行远程调用来检索此类信息。
它的用途受到限制：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数据结构上虚拟调用的开销。

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

类型解析和代码生成

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

编译时节点不知道将从子节点返回什么类型的值。
节点应该能够在构建评估树时或在运行时解决操作的重载。

如前所述，我们决定不使用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”]))

可能的执行顺序如下：

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

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

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

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

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

(= (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版本的引擎上，是该项目最具挑战性的部分之一。

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

迁移过程对实验平台用户是透明的。
爬坡（ramping）过程可由团队控制。
影响是可衡量的。

为了以中心化的方式控制爬坡过程，我们发布了带有内部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

创作场景

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