简介：本文向读者具体揭秘了数据湖剖析引擎的关键技术，并通过 StarRocks 来帮忙用户进一步了解零碎的架构。
作者：
阿里云 EMR 开源大数据 OLAP 团队
StarRocks 社区数据湖剖析团队
前言
随着数字产业化和产业数字化成为经济驱动的重要能源，企业的数据分析场景越来越丰盛，对数据分析架构的要求也越来越高。新的数据分析场景催生了新的需要，次要包含三个方面：
用户心愿用更加低廉的老本，更加实时的形式导入并存储任何数量的关系数据数据（例如，来自业务线应用程序的经营数据库和数据）和非关系数据（例如，来自挪动应用程序、IoT 设施和社交媒体的经营数据库和数据）
用户心愿本人的数据资产受到紧密的爱护
用户心愿数据分析的速度变得更快、更灵便、更实时
数据湖的呈现很好的满足了用户的前两个需要，它容许用户导入任何数量的实时取得的数据。用户能够从多个起源收集数据，并以其原始模式存储到数据湖中。数据湖领有极高的程度扩大能力，使得用户可能存储任何规模的数据。同时其底层通常应用便宜的存储计划，使得用户存储数据的老本大大降低。数据湖通过敏感数据辨认、分级分类、隐衷爱护、资源权限管制、数据加密传输、加密存储、数据危险辨认以及合规审计等措施，帮忙用户建设平安预警机制，加强整体平安防护能力，让数据可用不可得和平安合规。
为了进一步满足用户对于数据湖剖析的要求，咱们须要一套实用于数据湖的剖析引擎，可能在更短的工夫内从更多起源利用更多数据，并使用户可能以不同形式协同解决和剖析数据，从而做出更好、更快的决策。本篇文章将向读者具体揭秘这样一套数据湖剖析引擎的关键技术，并通过 StarRocks 来帮忙用户进一步了解零碎的架构。
之后咱们会持续发表两篇文章，来更具体地介绍极速数据湖剖析引擎的内核和应用案例：
代码走读篇：通过走读 StarRocks 这个开源剖析型数据库内核的要害数据结构和算法，帮忙读者进一步了解极速数据湖剖析引擎的原理和具体实现。
Case Study 篇：介绍大型企业如何应用 StarRocks 在数据湖上实时且灵便的洞察数据的价值，从而帮忙业务进行更好的决策，帮忙读者进一步了解实践是如何在理论场景落地的。
什么是数据湖？
什么是数据湖，依据 Wikipedia 的定义，“A data lake is a system or repository of data stored in its natural/raw format, usually object blobs or files”。艰深来说能够将数据湖了解为在便宜的对象存储或分布式文件系统之上包了一层，使这些存储系统中离散的 object 或者 file 联合在一起对外展现出一个对立的语义，例如关系型数据库常见的“表”语义等。
理解完数据湖的定义之后，咱们自然而然地想晓得数据湖能为咱们提供什么独特的能力，咱们为什么要应用数据湖？
在数据湖这个概念进去之前，曾经有很多企业或组织大量应用 HDFS 或者 S3 来寄存业务日常运作中产生的各式各样的数据（例如一个制作 APP 的公司可能会心愿将用户所产生的点击事件事无巨细的记录）。因为这些数据的价值不肯定可能在短时间内被发现，所以找一个便宜的存储系统将它们暂存，期待在未来的一天这些数据能派上用场的时候再从中将有价值的信息提取进去。然而 HDFS 和 S3 对外提供的语义毕竟比拟繁多（HDFS 对外提供文件的语义，S3 对外提供对象的语义），随着工夫的推移工程师们可能都无法回答他们到底在这外面存储了些什么数据。为了避免后续应用数据的时候必须将数据一一解析能力了解数据的含意，聪慧的工程师想到将定义统一的数据组织在一起，而后再用额定的数据来形容这些数据，这些额定的数据被称之为“元”数据，因为他们是形容数据的数据。这样后续通过解析元数据就可能答复这些数据的具体含意。这就是数据湖最原始的作用。
随着用户对于数据品质的要求越来越高，数据湖开始丰盛其余能力。例如为用户提供相似数据库的 ACID 语义，帮忙用户在继续写入数据的过程中可能拿到 point-in-time 的视图，避免读取数据过程中呈现各种谬误。或者是提供用户更高性能的数据导入能力等，倒退到当初，数据湖曾经从单纯的元数据管理变成当初领有更加丰盛，更加相似数据库的语义了。
用一句不太精确的话形容数据湖，就是一个存储老本更便宜的“AP 数据库”。然而数据湖仅仅提供数据存储和组织的能力，一个残缺的数据库不仅要有数据存储的能力，还须要有数据分析能力。因而怎么为数据湖打造一款高效的剖析引擎，为用户提供洞察数据的能力，将是本文所要重点论述的局部。上面通过如下几个章节一起逐渐拆解一款古代的 OLAP 剖析引擎的外部结构和实现：
怎么在数据湖上进行极速剖析
古代数据湖剖析引擎的架构
怎么在数据湖上进行极速剖析？
从这一节开始，让咱们开始回到数据库课程，一个用于数据湖的剖析引擎和一个用于数据库的剖析引擎在架构上别无二致，通常咱们认为都会分为上面几个局部：
Parser：将用户输出的查问语句解析成一棵形象语法树
Analyzer：剖析查问语句的语法和语义是否正确，合乎定义
Optimizer：为查问生成性能更高、代价更低的物理查问打算
Execution Engine：执行物理查问打算，收集并返回查问后果
对于一个数据湖剖析引擎而言，Optimizer 和 Execution Engine 是影响其性能两个外围模块，上面咱们将从三个维度动手，逐个拆解这两个模块的核心技术原理，并通过不同技术计划的比照，帮忙读者了解一个古代的数据湖剖析引擎的始末。
RBO vs CBO
基本上来讲，优化器的工作就是对给定的一个查问，生成查问代价最低（或者绝对较低）的执行打算。不同的执行打算性能会有成千上万倍的差距，查问越简单，数据量越大，查问优化越重要。
Rule Based Optimization (RBO) 是传统剖析引擎罕用的优化策略。RBO 的实质是外围是基于关系代数的等价变换，通过一套事后制订好的规定来变换查问，从而取得代价更低的执行打算。常见的 RBO 规定谓词下推、Limit 下推、常量折叠等。在 RBO 中，有着一套严格的应用规定，只有你依照规定去写查问语句，无论数据表中的内容怎么，生成的执行打算都是固定的。然而在理论的业务环境中，数据的量级会重大影响查问的性能，而 RBO 是没法通过这些信息来获取更优的执行打算。
为了解决 RBO 的局限性，Cost Based Optimization (CBO) 的优化策略应运而生。CBO 通过收集数据的统计信息来估算执行打算的代价，这些统计信息包含数据集的大小，列的数量和列的基数等信息。举个例子，假如咱们当初有三张表 A，B 和 C，在进行 A join B join C 的查问时如果没有对应的统计信息咱们是无奈判断不同 join 的执行程序代价上的差别。如果咱们收集到这三张表的统计信息，发现 A 表和 B 表的数据量都是 1M 行，然而 C 表的 数据量仅为 10 行，那么通过先执行 B join C 能够大大减少两头后果的数据量，这在没有统计信息的状况下根本不可能判断。
随着查问复杂度的减少，执行打算的状态空间会变的十分微小。刷过算法题的小伙伴都晓得，一旦状态空间十分大，通过暴力搜寻的形式是不可能 AC 的，这时候一个好的搜索算法分外重要。通常 CBO 应用动静布局算法来失去最优解，并且缩小反复计算子空间的代价。当状态空间达到肯定水平之后，咱们只能抉择贪婪算法或者其余一些启发式算法来失去部分最优。实质上搜索算法是一种在搜寻工夫和后果品质做 trade-off 的办法。
（常见 CBO 实现架构）
Record Oriented vs Block Oriented
执行打算能够认为是一串 operator（关系代数的运算符）首尾相连串起来的执行流，前一个 operator 的 output 是下一个 operator 的 input。传统的剖析引擎是 Row Oriented 的，也就是说 operator 的 output 和 input 是一行一行的数据。
举一个简略的例子，假如咱们有上面一个表和查问：
CREATE TABLE t (n int, m int, o int, p int);
SELECT o FROM t WHERE m < n + 1;
例子起源：GitHub - jordanlewis/exectoy上述查问语句开展为执行打算的时候大抵如下图所示：
通常状况下，在 Row Oriented 的模型中，执行打算的执行过程能够用如下伪码示意：
next:
for:
row = source.next()
if filterExpr.Eval(row):
// return a new row containing just column o
returnedRow row
for col in selectedCols:
returnedRow.append(row[col])
return returnedRow 依据 DBMSs On A Modern Processor: Where Does Time Go? 的评估，这种执行形式存在大量的 L2 data stalls 和 L1 I-cache stalls、分支预测的效率低等问题。
随着磁盘等硬件技术的蓬勃发展，各种通过 CPU 换 IO 的压缩算法、Encoding 算法和存储技术的宽泛应用，CPU 的性能逐步成为成为剖析引擎的瓶颈。为了解决 Row Oriented 执行所存在的问题，学术界开始思考解决方案，Block oriented processing of Relational Database operations in modern Computer Architectures 这篇论文提出应用按 block 的形式在 operator 之间传递数据，可能平摊条件检查和分支预测的工作的耗时，MonetDB/X100: Hyper-Pipelining Query Execution 在此基础上更进一步，提出将通过将数据从原来的 Row Oriented，扭转成 Column Oriented，进一步晋升 CPU Cache 的效率，也更有利于编译器进行优化。在 Column Oriented 的模型中，执行打算的执行过程能够用如下伪码示意：
// first create an n + 1 result, for all values in the n column
projPlusIntIntConst.Next():
batch = source.Next()
for i < batch.n:
outCol[i] = intCol[i] + constArg
return batch
// then, compare the new column to the m column, putting the result into
// a selection vector: a list of the selected indexes in the column batch
selectLTIntInt.Next():
batch = source.Next()
for i < batch.n:
if int1Col < int2Col:
selectionVector.append(i)
return batch with selectionVector
// finally, we materialize the batch, returning actual rows to the user,
// containing just the columns requested:
materialize.Next():
batch = source.Next()
for s < batch.n:
i = selectionVector[i]
returnedRow row
for col in selectedCols:
returnedRow.append(cols[col][i])
yield returnedRow
能够看到，Column Oriented 领有更好的数据局部性和指令局部性，有利于进步 CPU Cache 的命中率，并且编译器更容易执行 SIMD 优化等。
Pull Based vs Push Based
数据库系统中，通常是将输出的 SQL 语句转化为一系列的算子，而后生成物理执行打算用于理论的计算并返回后果。在生成的物理执行打算中，通常会对算子进行 pipeline。常见的 pipeline 形式通常有两种：
基于数据驱动的 Push Based 模式，上游算子推送数据到上游算子
基于需要的 Pull Based 模式，上游算子被动从上游算子拉取数据。经典的火山模型就是 Pull Based 模式。
Push Based 的执行模式进步了缓存效率，可能更好地晋升查问性能。
参考：Push vs. Pull-Based Loop Fusion in Query Engines
古代数据湖剖析引擎的架构
通过上一节的介绍，置信读者曾经对数据湖剖析引擎的前沿实践有了相应理解。在本节中，咱们以 StarRocks 为例，进一步介绍数据湖剖析引擎是怎么有机的联合上述先进实践，并且通过优雅的零碎架构将其出现给用户。
如上图所示，StarRocks 的架构十分简洁，整个零碎的外围只有 Frontend (FE)、Backend (BE) 两类过程，不依赖任何内部组件，不便部署与保护。其中 FE 次要负责解析查问语句（SQL），优化查问以及查问的调度，而 BE 则次要负责从数据湖中读取数据，并实现一系列的 Filter 和 Aggregate 等操作。
Frontend
FE 的次要作用将 SQL 语句通过一系列转化和优化，最终转换成 BE 可能意识的一个个 Fragment。一个不那么精确但易于了解的比喻，如果把 BE 集群当成一个分布式的线程池的话，那么 Fragment 就是线程池中的 Task。从 SQL 文本到 Fragment，FE 的次要工作蕴含以下几个步骤:
SQL Parse：将 SQL 文本转换成一个 AST(形象语法树)
Analyze：基于 AST 进行语法和语义剖析
Logical Plan：将 AST 转换成逻辑打算
Optimize：基于关系代数，统计信息，Cost 模型对逻辑打算进行重写，转换，抉择出 Cost“最低”的物理执行打算
生成 Fragment：将 Optimizer 抉择的物理执行打算转换为 BE 能够间接执行的 Fragment
Coordinate：将 Fragment 调度到适合的 BE 上执行
Backend
BE 是 StarRocks 的后端节点，负责接管 FE 传下来的 Fragment 执行并返回后果给 FE。StarRocks 的 BE 节点都是齐全对等的，FE 依照肯定策略将数据调配到对应的 BE 节点。常见的 Fragment 工作流程是读取数据湖中的局部文件，并调用对应的 Reader（例如，适配 Parquet 文件的 Parquet Reader 和适配 ORC 文件的 ORC Reader 等）解析这些文件中的数据，应用向量化执行引擎进一步过滤和聚合解析后的数据后，返回给其余 BE 或 FE。
总结
本篇文章次要介绍了极速数据湖剖析引擎的核心技术原理，从多个维度比照了不同技术实现计划。为不便接下来的深入探讨，进一步介绍了开源数据湖剖析引擎 StarRocks 的零碎架构设计。心愿和各位同仁独特探讨、交换。
附录
基准测试
本次测试采纳的 TPCH 100G 的规范测试集，别离比照测试了 StarRocks 本地表，StarRocks On Hive 和 Trino（PrestoSQL）On Hive 三者之间的性能差距。
在 TPCH 100G 规模的数据集上进行比照测试，共 22 个查问，后果如下：
StarRocks 应用本地存储查问和 Hive 表面查问两种形式进行测试。其中，StarRocks On Hive 和 Trino On Hive 查问的是同一份数据，数据采纳 ORC 格局存储，采纳 zlib 格局压缩。测试环境应用 阿里云 EMR 进行构建。
最终，StarRocks 本地存储查问总耗时为 21s，StarRocks Hive 表面查问总耗时 92s。Trino 查问总耗时 307s。能够看到 StarRocks On Hive 在查问性能方面远远超过 Trino，然而比照本地存储查问还有不小的间隔，次要的起因是拜访远端存储减少了网络开销，以及远端存储的延时和 IOPS 通常都不如本地存储，前面的打算是通过 Cache 等机制补救问题，进一步缩短 StarRocks 本地表和 StarRocks On Hive 的差距。
参考资料
[1] GitHub – jordanlewis/exectoy
[2] DBMSs On A Modern Processor: Where Does Time Go?[3] Block oriented processing of Relational Database operations in modern Computer Architectures
[4] MonetDB/X100: Hyper-Pipelining Query Execution
[5] https://help.aliyun.com/docum…
原文链接
本文为阿里云原创内容，未经容许不得转载。