本文作者：吕政、长别、知数等
目的
随着数字经济时代的到来，越来越多的运用依赖数据分析来发掘数据的价值。作为大数据存储、在线分析的重要基础系统，分析型数据库（OLAP）为数据价值的在线化提供重要的技术平台。
阿里巴巴OLAP团队经过调研发现，现有的OLAP数据库执行引擎往往是在已有的OLTP执行引擎的基础之上，停止二次开发而来，存在功能损耗大、历史包袱重、未充分应用最新优化技术、未充分发挥新硬件优势等成绩。
随着数据量的疾速增长和数据分析需求的日趋微弱，OLAP系统所需求承担的计算量也呈指数级增长，现有系统的功能难以满足将来的在线数据分析的需求。经过分析，阿里巴巴OLAP团队以为，真正面向片面上云时代、面向数字经济时代的OLAP执行引擎，该当具有如下技术特点：
• 支持多种硬件平台。满足企业上云需求，支持多种硬件平台。除了支持传统X86平台，也该当兼容ARM平台，同时支持应用GPU、FPGA等新兴硬件停止加速。
• 极致性价比。充分应用硬件功能，精选最佳算法和算子完成，提升硬件执行效率。对于密集、复杂的计算，运用特殊算法特殊硬件来提升效率。
• SQL 兼容性高。高度兼容现有的SQL标准、优化器标准、存储标准，减少用户的迁移难度和学习难度。用户无需改写SQL，无需重新学习优化技术，无需迁移数据，仅需求停止小版本软件晋级，即可享遭到最新的功能优化技术。
为了处理如上需求，阿里巴巴OLAP AnalyticDB Postgres(简称ADB PG版)研发团队历时1年多，研发了新型的计算引擎Odyssey。Odyssey计算引擎具有如下次要技术特点:
• 支持多种软硬件平台。除传统X86平台外，也支持ARM芯片服务器；支持采用GPU、FPGA加速部分核心算法。
• 功能微弱。丢弃传统数据库执行引擎的完成方式，充分应用硬件执行效率。经过算法设计，消弭了火山模型、碎片化内存分配、冗余逻辑等带来的功能成绩，将宝贵的CPU资源用于核心计算；采用LLVM进举动态代码生成（CodeGen），提升表达式计算功能、精简计算逻辑，完成逻辑计算完美“瘦身”；采用“超算”优化技术、对算子功能停止建模，片面分析代码热点，严厉调查每一行代码的完成功能；充分应用新硬件特性，应用CPU的SIMD技术、GPU的超高带宽技术、FPGA的深度流水线，进一步提升功能。
• 兼容性强。Odyssey计算引擎内生于ADB PG版，与PostgreSQL的SQL标准、优化器、存储层多个层面完成完美兼容，用户无需任何操作，即可从原生引擎迁移到Odyssey计算引擎。
本文的如下部分，我们将从架构设计、核心技术点、功能评测三个维度，引见新型计算引擎Odyssey的特点。
Odyssey计算引擎引见
基本框架
下图是ADB PG版的系统框架，以及Odyssey计算引擎与ADB PG版的关系。
ADB PG是一个MPP架构、高可用、可伸缩的分布式分析型数据库系统。一个ADB PG集群由Master节点和Segment节点组成，经过网络停止互联。Master节点担任接收用户央求、对SQL停止解析/优化、下发计算义务。Segment节点担任存储数据、执行计算义务，Segment节点之间能够会有多次数据交换(shuffle)操作。网络互联速度、存储功能、Segment节点的执行功能，均对ADB PG的功能有重要影响。本次发布的Odyssey计算引擎，次要提升了Segment的执行功能。
Odyssey计算引擎的研发目的，是为ADB PG新增一个更高效的计算引擎，而保持原有各模块不变。ADB PG的Master节点在接收到用户的SQL央求之后，对SQL停止解析、优化，生成执行计划然后下发到Segment，Odyssey计算引擎对这一环节没有影响，因此用户无需修正SQL、无需重新优化SQL。
Segment接遭到Master节点下发的执行计划后，若Odyssey打开，将不再调用原生执行引擎，而是调用Odyssey计算引擎。在存储层面，Odyssey计算引擎与ADB PG原生的Heap表、AOCS表、AORO表均完全兼容，复用原生活储结构和存储访问接口，Odyssey专注于执行层。实际上说，Odyssey原生引擎与ADB PG的优化器优化、存储优化等不同层次的优化是正交的，可以无缝衔接。
Odyssey计算引擎执行流程如上图所示。Odyssey经过hook接入ADB PG，成为对用户透明的新引擎。ADB PG在SQL执行末尾时，经过选择不同的Hook函数，来选择不同的执行引擎。对于用户来说，既可以选择原生执行引擎，也可以经过设置GUC参数选择Odyssey执行引擎。下一个版本将经过代价模型和规则来自动的选择计算引擎，更能发挥各自的优势。
为了保证系统的波动性和功能的残缺性，Odyssey计算引擎支持执行引擎的回退，当功能不支持或者执行失败，可以自动回退到原生的执行引擎。由于执行引擎本身是有形状的，用户可以根据需求，以恣意粒度（库级别、session级别、SQL级别）停止执行引擎切换。
设计思想
基于上述架构，Odyssey计算引擎充分应用ADB PG本身的优势，复用其存储、优化器和事务控制，Odyssey专注于计算功能的提升，与原生ADB PG弱小、丰富的功能构成互补。为了提升计算功能，经过对原生执行引擎停止分析、横向对比多种执行引擎，我们设计了新的计算引擎。Odyssey计算引擎重新设计了plan node、codegen和executor，三者之间逐一对应，如下图所示，每个plan的node对应一个codegen单元和一个Executor，codegen单元根据plan node生成code(IR)，Executor根据硬件平台选择不同的后端，将IR生成对应的执行文件，并央求资源执行，最终的结果经过master前往给客户端。
执行模型优化。Odyssey计算引擎放弃了传统的火山模型，改用批量化(batch)的火山模型，批量化执行减少函数调用的开支，也方便运用向量化计算提升数据处理效率，同时也使得开发更为灵敏、优化空间更大。
即时编译技术。Odyssey计算引擎采用了Just-in-Time(JIT)技术，采用LLVM动态生成代码。在一些核心操作上采用JIT技术，处理了高级言语笼统程度过高带来的功能开支，可以对表达式计算、复杂逻辑操作停止汇编级优化，最大化紧缩指令的规模。
内存管理优化。ADB GP原生执行引擎存在碎片化内存分配、碎片化内存拷贝等功能成绩。Odyssey计算引擎在算法层停止了重新设计，采用模块化内存分配、最大化反复应用已分配内存，大大减少了内存分配的次数。
超算软件优化。Odyssey计算引擎的开发，大量采用了“超级计算机”软件开发中的优化技术。在超算软件优化中，建立实际功能模型、停止详细功能分析（Profiling）、严厉审核代码功能，可以有效协助软件功能的提升。Odyssey计算引擎片面采用了相关技术，做到每个算子、每段代码，都停止了深度优化。
多平台兼容。除传统X86平台，Odyssey计算引擎兼容其他X86平台和ARM平台，同时支持不同版本的Linux操作系统，为用户提供了更多的选择和优化空间。
硬件加速优化。Odyssey计算引擎可以应用GPU的超大吞吐才能和FPGA的高密度计算才能。对于部分计算量大、吞吐要求高的算子，采用GPU停止加速；对于部分计算逻辑相对固定、逻辑复杂的算子，采用FPGA停止加速。
核心技术点
执行模型优化
上图展现了TPCH-Q3的执行计划。在ADB PG中，一条SQL会被转化成一个树形执行计划。数据库传统的传统火山模型，是父节点驱动子节点执行，子节点按行前往数据给父节点，然后父节点再继续执行。火山模型有三个核心功能成绩：
(1) 函数调用过多，每行数据的传递需求至少一次函数调用，CPU开支大；
(2) 优化困难，一些逻辑运算横跨多个函数，无法停止优化；
(3) CPU应用率低，CPU完成某个算子的一个操作后，马上前往到下层节点去做另一个操作，逻辑跳转多，不利于提升CPU执行效率。
Odyssey计算引擎对火山模型停止了完全重写，在复用原有的树形架构基础上，采用批量化(batch)执行提升执行功能。
火山模型中，节点之间传递数据的单位为一行，每个节点生成一行数据之后会被下层节点层层拉取，然后停止下一阶段的计算。 而Odyssey计算引擎以batch为单位停止数据传递。一个Batch包含多行数据（通常是数千行数据），采用列优先格式停止数据存储。一个节点在生成多行数据、填满一个batch之后，才会将数据前往给下层节点，消弭了火山模型的功能成绩。一方面，该方案将火山模型的函数调用的次数降低了三个数量级，消弭了过多函数调用带来的功能影响；另一方面，减少了跨函数的操作，有利于在算法层停止优化、为各个算子选取最佳算法；最后，减少了逻辑跳转操作，可以有效应用古代CPU的执行资源。
内存管理
Odyssey计算引擎继续沿用了ADB PG的内存管理模块。ADBPG原生的内存管理模块除了功能上有所提升，而且可以自动追踪内存的分配，从而完成自动的内存释放，提升功能的同时避免了内存泄露的成绩。该模块曾经经过大规模云上实际的检验，因此在工程上。Odyssey计算引擎沿用了这一模块，但是在内存的运用上停止了优化，减少了不必要的内存分配和碎片化的内存分配。
一方面，Odyssey会尽力复用已分配的内存，避免不必要的多次内存分配。在火山模型中，部分节点生成一行数据后会为这行数据分配新的内存空间，因此每行数据都能够需求一次内存分配。Odyssey丢弃了火山模型、运用batch停止数据中转。每个batch的数据被下层节点消费完一行，Odyssey会复用此batch的内存空间，无须重新停止分配。
// 原生引擎：碎片化分配，按行分配内存
for (...) {
void* hash_entry = palloc(32);
... // copy data
}
// Odyssey引擎：整块内存分配。
void* hash_table = palloc(32*1000,000);
for () {
... // copy data
}
另一方面，在一些大快内存分配时，Odyssey选取了效率更高的分配方式(如上述伪代码所示)。例如在Hash Join建哈希表时，一次插入一行数据，ADB PG的原生执行引擎，会在每行数据的插入之前为这一行分配内存。因此，每一行数据都需求重新停止一次内存分配，这种方案会带来大量的碎片化内存分配。例如Hash表有1M行，每行32字节，会导致1M个32字节的碎片化内存分配。对于古代化的系统来说，碎片化的内存分配对于功能的影响是非常大的，不只分配过程非常耗时，后续的管理、追踪、释放过程也会非常耗时。
Odyssey对ADB PG原生执行引擎的碎片化内存分配成绩停止了诊断和缘由分析，排查出几个导致碎片化内存分配的关键算法成绩。经过算法设计，Odyssey避免了碎片化内存分配成绩，从而在不降低内存运用效率的同时，提高了内存管理的功能。
Codegen
Odyssey计算引擎采用基于LLVM的Codegen(代码生成)技术，减少了虚函数的调用，提升了复杂逻辑表达式和逻辑判别的功能。有别于PostgreSQL 11中表达式的codegen，Odyssey计算引擎是对整个算子停止codegen。目前Codegen次要用于三个层面的优化，算子优化、逻辑表达式优化和Code Specialization(代码专业化)。
算子优化。采用codegen，可以将整个算子生成一个函数，减少虚函数调用和冗余代码，也可以将多个算子生成一个函数，不光有上述优势，还能减少内存的运用和内存的拷贝。例如join + group by的场景，可以交融成一个函数，将join和AGG在一个函数里完成。特别是假如hash key和group key相反时，只需求建一个hash表。
逻辑表达式优化。如下代码实例解释了是如何完成这一优化的。对于a > 10 and b < 5这样一个过滤条件, ADBPG是经过三个函数调用来完成的，第一个函数调用Int32GT(a, 10)完成 a > 10, 第二个函数调用Int32LT(b, 5)完成b < 5, 第三个函数完成And操作。该方案需求三次函数调用，对功能有分明的影响。而Odyssey计算引擎采用的方案，运用LLVM生成LLVM IR，在编译成底层的机器码，只需求三条指令即可完成这一操作。经过该方案，Odyssey计算引擎避免了大量的冗余操作，可以针对不同的表达式、不同的逻辑判别，生成最小化的底层代码。
// 实例SQL
select count(*) from table where a > 10 and b < 5;
// ADBPG表达式方案：多次函数调用
result = Int8AndOp(Int32GT(a, 10), Int32LT(b, 5));
// Odyssey方案：生成最小化底层代码
%res1 = icmp ugt i32 %a, 10;
%res2 = icmp ult i32 %b, 5;
%res = and i8 %res1, %res2;
Code Specialization。 对于一些在执行全已知的逻辑判别，可以经过LLVM停止code specialization, 从而消弭逻辑判别。例如，某些数据结构的类型SQL解析完成后、在执行引擎末尾执行前是确定的，比如每个节点的输入数据类型、数据长度。假如是运用高级言语（比如C言语）停止执行，由于写代码是开发者并不知道数据的类型，需求对每个元素的类型、长度停止判别。但是LLVM是在代码生成时就确定了数据的类型，因此生成的最终代码无需停止判别、直接停止操作即可。由于执行引擎常常需求停止数据类型、长度判别，虽然每次节省的工夫非常少，但是累计上去功能的提升非常分明。
向量化执行
将按行拉取数据的火山模型改为按batch拉取数据的火山模型后，结合按列存放的优势，可以更进一步发掘处理器的功能。例如，批量化处理的模型可以应用CPU的向量指令，或者GPU的众核优势，进一步提升功能。
// 伪代码样例：应用SIMD指令加速聚合
for (int i = 0; i < round_row; i += 8) {
__m256 m_tmp = _mm256_load_ps(&(aligned_input_data));
__m256 ymm2 = _mm256_permute2f128_ps(m_tmp , m_tmp , 1);
m_tmp = _mm256_add_ps(m_tmp, ymm2);
m_tmp = _mm256_hadd_ps(m_tmp, m_tmp);
m_tmp = _mm256_hadd_ps(m_tmp, m_tmp);
result += m_tmp[0];
}
例如OLAP 中常用的Aggregation操作，采用SIMD指令，计算功能能提升4倍左右，伪代码如上所示。一些更为复杂的算法可以应用GPU众核计算才能，例如并行过滤、聚合、规约等算法，计算功能最高可以提升一个数量级。
跨平台支持
云计算时代，云平台支持多种不同的硬件资源，除传统x86平台外，国产x86平台、国产ARM平台、GPU、FPGA资源均可支持，用户只需求购买相应的资源规格即可，满足了用户不同的场景需求。Odyssey计算引擎在ADB PG的基础之上，进一步扩展了支持的范围，目前Odyssey计算引擎曾经完美运转在x86平台和ARM平台上。
除此之外，Odyssey计算引擎支持运用GPU和FPGA对关键算子停止加速。GPU作为一种众核架构，计算资源和带宽资源充足，合适数据密集型、高吞吐的场景。FPGA作为一种可定制化处理器，非常合适一些逻辑复杂的操作，有效提升硬件的资源应用率。目前Odyssey计算引擎支持运用GPU加速部分高密度算子，可完成超过5倍的功能提升。支持运用FPGA加速存储层的紧缩和解紧缩，最高功能提升超过10倍。
功能结果
测试采用的是标准的TPCH测试集，运用TPCH官方的工具生成数据和22条SQL，数据量为1TB，scale factor = 1000，集群规模都为32个segment。22条SQL从Q1到Q22单并发顺序、延续执行，每一条SQL发送出去记为末尾工夫，前往结果为结束工夫，执行工夫为两者的差值。
X86平台测试结果
x86平台测试在阿里云上停止，实例的详细规格如下：
单节点核数：4
单节点内存：32G
单节点磁盘：320G SSD
实例节点数：32
测试结果如下：
从图中可以看出，Odyssey计算引擎比原生引擎有比较分明的优势，Q1、Q4、Q9、Q11、Q17、Q20、Q21、Q22这些SQL有1倍以上的提升，其中Q17有2倍以上的功能提升。提升的比例与SQL类型有关，对于计算密集型的SQL优势愈加分明。对于IO密集型的SQL，我们在IO接口上做了适配和优化，计算功能提升的同事，IO功能也有提升。
ARM平台测试结果
ARM平台的测试采用三台服务器，一台作为master，另外两台作为计算节点。计算节点上各部署16个segment，共32个segment。每台服务器的配置如下：
CPU：128 cores
内存：378G
磁盘：3.84Tx4 AliFlash
从图中可以看出，在ARM平台，Odyssey计算引擎也有比较大的优势，而且相对x86平台，Odyssey在ARM平台上优势更分明。
总结
以上是ADB PG新的计算引擎Odyssey的一些技术细节，总的来说，Odyssey运用了新的技术：JIT，新的模型：批量（batch）化的火山模型，新的硬件特性：CPU的AVX指令、GPU的众核计算、FPGA的公用计算。在公有云上1TB的TPCH实测，22条语句的总工夫是原引擎的50%，单条SQL功能最高提升2倍多；ARM服务器上搭载Odyssey计算引擎的ADB PG也有一倍的功能提升，并且相对X86平台，Odyssey引擎提升更分明。
接上去的Odyssey计算引擎还会在存储层适配优化，更极致的功能优化上下功夫，敬请各位关注! |
