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

发布于:2020 年 5 月 26 日 14:54

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

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

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

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

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

  • 它可以提供高达 800,000QPS 的网络调用,
  • 它可以同时运行大约 35,000 个 A/B 实验,
  • 它每天可以处理多达 23 万亿次实验评估,
  • 实验评估的平均延迟为 700ns,第 99 个百分位数则为 3μs,
  • 它被用在大约 500 个生产服务中。

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

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

领英服务和 Lix 引擎

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

什么是 Lix 引擎,它的作用是什么?

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

  1. 对测试总体进行随机分割,
  2. 对总体进行细分,
  3. 为参与实验的给定实体分配实验变体。

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

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

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

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

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

总体细分

总体的细分和随机分割都封装在类似 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 中定义了以下数据类型,包括原语和集合:

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

上一代类型系统

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

  • 引擎核心中没有类型检查。每个步骤中都要执行所有验证,扩展能力很差。
  • 不支持多态,静态或动态都不行。这样就很难处理 (= “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”]))

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

评估树

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

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

评估树的存储

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

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

  • 较低的内存开销。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倍

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

性能优化结果

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

  • 顺序评估快至 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”分配一个随机值以触发分支。

  1. (= (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”。

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

自动生成的测试用例

为每个解析树分支构建测试套件并将这些测试递归组合后,我们就可以构建一套全面的测试,触发所有 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 测试来控制爬坡并衡量其影响。

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

上线过程

我们用了 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

阅读数:1 发布于:2020 年 5 月 26 日 14:54

评论

发布
暂无评论