论文阅读笔记：Photon: A Fast Query Engine for Lakehouse Systems
SIGMOD 2022 Best Industry Paper Award。近期有大团队论文阅读分享，提前做个筹备。Photon: A Fast Query Engine for Lakehouse Systems
概述
本论文介绍了 Databricks 的针对 Lakehouse 湖仓一体的环境下的向量化查询引擎 Photon，用于解决传统引擎在数据湖中存储的列式非布局化数据的劣势，Photon 在兼容 Apache Spark API 的基础上，提供了大量的性能提升。论文从查询执行引擎的相关设计理念长进行了大标的目的的讨论，并针对分歧的技术标的目的选择进行了优错误谬误讨论，以及 Photon 选择技术道路的一些性能数据的展示，对于新开发执行引擎，在技术方案选型有很多不错的指导性定见（出格适合像我这样的不熟悉 Spark 的人，在不接触过多 Spark 细节上掌握整体的一些设计思路）。
布景及挑战
布景
[*]存储太贵，大量数据可以以开放列存格式（Parquet、ORC、DeltaLake）存储在廉价的对象存储（S3、OSS）上
[*]对数据湖中非管护（uncurated）数据长进行复杂查询的需求越来越多，不仅存储需要进行改造撑持，查询引擎也需要针对性优化
挑战
[*]能够措置数据湖中的原始非管护（raw & uncurated）数据（字符串暗示的数值类型、大量且分布不均的null、大字段，可能没有统计信息）
[*]需要一个兼容已有系统（Apache Spark DataFrame API）的执行引擎以适应这种需求，同时将上层的改削减到最小（对用户友好）
[*]跑的快。。。
然后文章介绍了目前 Databricks 的架构及 SQL 执行流程。
Databricks 的SQL执行流程
Databricks 的 Lakehouse 平台有4部门组成：
[*]最底层的数据湖存储层（在S3、OSS上）
[*]撑持数仓事务的数据打点层（DeltaLake）
[*]弹性分析执行层（论文的重点，Apache Spark-based Databricks Runtime简称DBR）
[*]用户界面
DBR 是措置查询的主要组件，Photon 位于 DBR 的最底层，用于实际的打算执行。同时 Photon 是单线程的措置模型，整体在 DBR 的多线程多任务调剂下的最底层执行单元，代替之前的 Apache Spark SQL 执行引擎，这样的 Photon 的设计就会非常简单且不用考虑容错、恢复、数据跨任务调剂等问题，着重于计算密集任务的性能优化。
SQL 请求的优化和调剂都不是本论文的重点，这些都在 DBR 中被完成，直到生成最终 Photon 执行所需的执行打算片段（最小的执行单元），由 Photon 完成计算。
执行引擎技术路线选择
对应论文 EXECUTION ENGINE DESIGN DECISIONS 章节，主要介绍了 Databricks 再各种实现技术之间的选择及各种在实际工程实现和实际业务测试中发现的优错误谬误。
总体上 Photon 是个 C++ 实现的列式计算引擎，通过 JNI 方式接入 DBR 系统，有着完全独立的内存数据存储和措置模型，通过 HasNext()/GetNext() API 和上下文任务交互。其主要的技术路线选择有：
JVM vs. Native Execution
虽然 DBR 基于 JVM，但 Photon 毅然选择 C++ 去实现，也是个很重大的决定，主要基于如下原因：
[*]论文作者发现他们系统的性能瓶颈在 CPU，因为：
[*]底层存在 NVMe SSD cache、shuffle 显著减少了 IO 的瓶颈；
[*]DeltaLake的文件裁剪和请求 IO 优化能力进一步减少 IO 量；
[*]措置非尺度化的数据，可能需要进行大量的类型转换和规范化的操作，这本身是 CPU 密集的。
[*]JVM 不适合写高性能向量化操作：
[*]需要开发者对 JVM 有深入了解；
[*]Java 代码无法精细化掌控内存流水线和 SIMD 指令（没法写自定义的kernel function）；
[*]JVM 在实际生成环境中不雅察看到性能扩展断崖（大于 64GB 堆的GC性能急剧下降，本身打点堆外复杂度高）；
[*]在宽表场景下，受限于代码生成和代码缓存大小，会回退到 Volcano-style 的实现上。
Interpreted Vectorization vs. Code-Gen
现代的高性能执行引擎往往是2个标的目的：解释型向量化和动态代码生成。这两种思路都是为了解决 Volcano 执行模型的虚函数调用代价的，思路各有分歧，一种是将数据批量措置，平摊虚函数调用代价，另一种是通过动态编译相应查询的代码来消除虚函数调用。除此之外，这两种技术路线还有相应的深入优化空间和相应的优错误谬误：
向量化：
[*]充实操作批量数据的相似特征，操作 SIMD、编码等方式加速不异计算的措置，充实操作 CPU 流水线和缓存；
[*]开发和调试较为容易，现有开发东西齐全，便于注入埋点，具备可不雅观测性；
[*]算子边界明确，便于输出性能分析陈述，有利于调优；
[*]DBR 中有动态调剂能力，可以在运行中改换执行路径，对于算子边界明确的执行模式更合适；
[*]无编译代价；
[*]只能通过特定模板方式适配一些融合运算符，例如 between 表达式，但可以满足大部门场景。
代码生成：
[*]可以针对查询，将中间成果保留在寄存器中，快速减少中间成果集数据量；
[*]开发和调试较为困难，对开发人员要求高，调试器难以分析，仓库非尺度无符号，大量开发时间用于调试东西和可不雅观测性开发；
[*]算子混合在整体流程中，没有明确边界，插手埋点后会粉碎整体指令流水线；
[*]无法撑持动态变换执行路径，如果需要撑持则会消耗大量编译时间和内存；
[*]有可不雅观的编译代价和启动开销；
[*]在某些常见复杂表达式中具备极佳的性能优势，且具备通用性。
基于以上原因，Databricks 选择了解释型向量化路线。
Row vs. Column-Oriented Execution
经典技术选型标的目的，列式还是行式数据措置，通用的优错误谬误就不再赘述，这里主要还是看业务场景和客户需求。DBR 中是 Apache Spark，措置的数据是行式存储的，但 Photon 选择了列式措置。原因如下：
[*]Photon 选择了向量化引擎；
[*]DeltaLake 中数据格式是 Parquet；
[*]Photon 想用字典压缩字符串等变长数据；
[*]并不是全部列式内存布局，hash表等场景还是行式存储。
Partial Rollout
针对上线了的项目迭代的一种工程化策略，由于 Photon 处于逐步迭代成长过程中，对于 DBR 中已经撑持但 Photon 没有撑持的能力，退化到已有实现上，想必这也是 Photon 采用这么折腾的 JNI 方式接入，而不是新搞个完整执行引擎的一个重要原因，毕竟先上线、先有效才是促进一个项目正常推进的合适路线。
向量化执行器细节
内存数据布局
Photon 内存列存数据布局
内存布局还是斗劲尺度的列式存储，除了数据列，还有null向量，对于有效的列，并没有采用bitmap的方式标识表记标帜有效行，而是采用了position list的方式，这种暗示在稀疏的情况下会更优（论文暗示bitmap的方式大部门情况下更差）。Photon 的算子消费一个 batch 的数据并吐出一个或多个 batch。
执行函数
Photon 的执行核心是一系列针对特定任务循环高度优化的 kernel function（虽然都是对向量进行映射，叫核函数容易和 SVM 的核函数搞歧义，这里就不翻了），可以说是对一系列向量的措置映射函数，其本身是 CPU 密集的（由于列存，cache miss 不会很严重，最适合预读的内存访谒模式）。这里的 kernel function 凡是采用手写的方式，通过 RESTRICT 关键字让编译器去优化（手写汇编对开发者要求高，但真正极端优化还是要动态生成kernel function，相当向量化+codegen，按照cache大小设计循环展开的，之前看mkldnn里面是这么搞的）。用模板的方式实现措置分歧数据类型，输入是向量和position list，输出为向量。论文给了个sqrt的例子。
向量化sqrt例子
Filter
Filter 算子采用 position list 做过滤，这样可以复用 vector。例如在措置 case when 的时候，通过 position list 去让对应的 kernel function 只措置标识表记标帜的行，而保留其他不符合条件的行（我理解是将 case when 展开成多步措置，每步只措置一种 case 条件）。
向量化 hash 表
将 hash 表查找拆成多步，每步都向量化，即对于一批数据的查找，采用先向量化计算 hash，再向量化加载对应的 bucket 指针，最后去查找对应 key 是否存在。hash 表采用开放地址平方探测策略。每一步操作都是相似的简单功能，便于硬件的自动并行化。
内存打点
为了减少内存分配开销，Photon 采用内部本身的内存缓存和分配机制，尽可能复用热内存（cache 友好），变长向量单独打点，同时会按照变长数据的大小，调整 batch 大小。对于 Agg 或 Join 用到的大块长时间内存，单独跟踪打点。
自适应执行
针对非管户数据存在大量 null 和缺乏统计信息的问题，Photon 会对 batch 进行自适应调整：
[*]对 null 进行精细化统计，无 null 的 batch 可以采用不措置 position list 的 kernel function，提升性能；
[*]针对分歧字符集编码采用特化的 kernel function；
[*]动态检测并压缩稀疏 vector（提升有效数据内存密度），提升 join probe 时的性能；
[*]按照数据模式选择 shuffle 算法；
[*]UUID、数字字符串，解码后二进制化。
与 DBR 的整合
处于工程设计和迭代，Photon 需要整合到 DBR 中。这里仅挑一些通用的设计思路记录，和 DBR 强相关的内容就简单带过。
执行打算转换
首先 DBR 中生成的是 Spark SQL 的打算，需要执行打算转换，这里 Photon 实现了一个适配器和 FileScan 连接，直接拿列存的原始数据，具体是通过传递数据向量指针和 null 向量指针，数据都存储在堆外 OffHeapColumnVector 中，避免列转行再转列，同时避免 JNI 进出拷贝。执行打算采用 protobuf 编码后用 JNI 传递到 C++ 环境中。当 Photon 完成计算后，如果需要数据交换，则生成符合 Spark shuffle 格式的文件，将成果和对应元数据返回给 DBR，DBR 将这个成果交给下一个 Photon 任务。如果最后的 Photon 算子是将数据吐回给 Spark，则是一个 Transition 算子，将列式转行式吐给 Spark（这可能是个性能瓶颈点）。
对于内存打点，由于 Photon 通过 JNI 跑在 DBR 中，需要统一的内存感知避免 OOM，Photon 通过在内存打点器中预留内存和注册相应回调感知需要 spill 到磁盘上的情况，保证 DBR 的内存打点机制有效。同时，为了解决 JVM 对堆外内存打点的问题，Photon 通过注册回调将请求的堆外内存和请求的生命周期关联起来，主动释放。
Photon 的可不雅观测性也通过在 DBR 中注册回调来实现，可以透明地将 Photon 内部的执行情况通过 DBR 已有的不雅观测方式展现出来。
测试也是一个工程项目的重要部门，由于 Photon 是对 DBR 执行引擎的替换，测试主要采用一下方式：
[*]单元测试，包罗 Photon 本身的测试，和 Spark 的开源表达式单元测试；
[*]端到端，由于是引擎的替换，通过配置选择合适路径进行端到端测试对比，并通过故障注入不雅察看行为；
[*]随机测试，通过随机查询概率性验证兼容性。
尝试评估
micro-benchmarks
Photon 主要优化的是 CPU 密集型的算子，micro-benchmarks 跑在 i3.2xlarge（8 cores），11G JVM heap，35G off-heap 上，单线程内存表测试下。
Photon micro-benchmarks
论文主要对比了 Join、Agg、表达式（upper 如果是 ASCII 可以向量化，utf8 还是得走 ICU）、和写 Parquet（integers, longs, dates, timestamps, strings, and booleans 6列，200M 行，主要是向量化解码的优势），表白相对于原引擎有性能优势。
TPC-H & TPC-DS
8 x i3.2xlarge(8 cores 64GB) SF=3000 TPC-H
主要加速优势来自于，Decimal 计算优化及向量化，Scan、Agg、Join的向量化。TPC-DS 100T记录保持者。
TPC-DS 100T
JNI 开销
论文跑了个简单的内存表单列整形读，没有发现明显的 JNI 瓶颈，JNI 内部开销在0.06%，适配器读取0.2%，95%以上CPU在列转行上，然而这部门 DBR 单独跑也是不成省略的。
自适应执行
自适应 vector 压缩
自适应压缩提升了内存有效数据密度，没有压缩的时候 Photon 跑不外 DBR 的 code-gen（解释执行虚函数代价）。UUID解码二进制化，5000w UUID二进制化后，端到端时间减少15%，数据量减少一半以上。
UUID解码二进制化
总结
这个论文从通用列存执行引擎上，介绍了选择各种技术路线的原因，没有过多深入细节，斗劲适合初期整体设计的大标的目的把握。非常适合初学者学习些整体思想。
参考
[*]^Photon: A Fast Query Engine for Lakehouse Systems https://www-cs.stanford.edu/~matei/papers/2022/sigmod_photon.pdf
[*]^Lakehouse: A NewGeneration of Open Platforms that Unify DataWarehousing and Advanced Analytics https://www.cidrdb.org/cidr2021/papers/cidr2021_paper17.pdf
[*]^abcDelta Lake: High-Performance ACID Table Storage over Cloud Object Stores https://www.databricks.com/wp-content/uploads/2020/08/p975-armbrust.pdf
[*]^OffHeapColumnVector. https://github.com/apache/spark/blob/
页:
[1]