Apache Trafodion 设计构架

概览

Trafodion提供了一个基于Hadoop平台的交易型SQL引擎。它是一个擅长处理交易型负载的Hadoop大数据解决方案。其主要特性包括：

• 完整的ANSI SQL语言支持
• 完整的ACID事务支持。对于读、写查询，Trafodion支持跨行，跨表和跨语句的事务保护
• 支持多种异构存储引擎的直接访问
• 为应用程序提供极佳的高可用性保证
• 采用了查询间(intra-query)并发执行模式。轻松支持大数据应用
• 同时应用编译时和运行时优化技术，优化了OLTP工作负载的性能

事务管理特性包括

• 事务串行化基于开源项目HBase-Trx的实现原理，采用多版本并发控制(MVCC)
• 增强的故障恢复机制保证了数据库中用户数据的一致性
• 事务管理器支持多线程的SQL客户端应用
• 支持非事务型数据访问，即直接访问底层HBase表

进程构架

上图描述了Trafodion的进程构架。主要进程包括：

• 客户端应用通过JDBC或者ODBC访问Trafodion。Trafodion的ODBC驱动采用了优化的wire protocol，高效地同Master Executor进程进行网络交互。上图演示了一个Type 4的JDBC配置。.
• Master Executor是负责执行用户SQL语句的主进程。它内部包含了一份SQL compiler代码的拷贝，因此多数SQL语句可以在Master Executor进程内部进行编译而无需和单独的编译进程进行通信。此外，所有执行计划中的root节点都在Master Executor进程中执行。
• 少部分SQL语句（比如,DDL和一些应用工具）需要启动第二个独立的编译器进程对SQL语句进行处理；即上图中的CMP进程
• Trafodion 支持多种不同形式的并发执行方式。当系统生成了并发查询计划时，系统会动态地启动多个ESP进程，即Executor Server Processes。每一个ESP负责执行查询计划中的一个分段(fragment)
• DTM进程负责分布式事务。DTM的职责包括日志管理和事务协调。
• Trafodion支持访问原生HBase表，为此，SQL引擎将读取HBase的元数据。为了提供更好的OLTP访问性能，Trafodion还提供了定制的Trafodion表结构，用HBase Table进行存储。Trafodion表拥有自己的元数据，同样存储在HBase中。

连接子系统

数据库连接服务(DCS)允许标准的ODBC/JDBC应用程序访问Trafodion。DCS是一个分布式服务。它利用底层的HBase服务 ZooKeeper 来管理DCS集群。ZooKeeper（一个Apache开源项目）服务能提供配置管理，命名空间管理等功能。利用ZooKeeper，还可以实现分布式环境下的同步，以及集群成员管理。所有的集群节点以及客户端应用都可以访问ZooKeeper。

DCS由多个子系统组成：

• ODBC/JDBC驱动程序：ODBC提供了标准的API来访问数据库管理系统。
• DCS主进程：DCS主进程负责监控所有的Server实例。它为ODBC/JDBC客户端连接请求分配MXOSRVR进程（在上图中显示为"Master Executor"）。DCS主进程拥有一个standby备份，当DCS主进程发生故障时，standby备份可以立即接管，成为新的DCS主进程。
• DCS Server进程：Server进程负责启动和管理MXOSRVR进程的运行。集群的每个节点上都运行一个DCS Server进程。
• MXOSRVR Server 进程(在上图中显示为"Master Executor"): 这个进程负责处理ODBC/JDBC客户的数据库访问请求。一个客户端程序对应一个单独的MXOSRVR server进程。MXOSRVR server进程代表客户端执行SQL查询，并将结果返回给客户端应用程序。

事务子系统

Trafodion采用多版本并发控制(MVCC)的方法支持分布式ACID事务。具体实现基于开源项目HBase-trx。Trafodion在HBase-trx的基础上做了一些改进：

1. 支持HBase 0.98.1版本(CDH 5.1)，和0.98.9版本(HDP 2.1)
2. 采用线程池技术并发地处理事务原语
3. 支持全局事务
4. 添加了事务的故障恢复能力

Trafodion在每个集群节点上启动一个事务管理进程（在上图中显示为"DTM"）。该进程记录了该节点上启动的所有事务，并负责管理它们（在原始的HBase-trx中，事务由客户端应用程序负责管理，当客户端进程异常退出后，系统无法再重新启动in-doubt事务，即被中断的未知结果的事务）

当Trafodion客户端开始执行一条SQL语句时，会和事务管理进程(TM)进行通信，由TM启动该事务。TM返回一个集群唯一的事务ID。这个事务ID会传给执行该查询的所有执行器进程。这个传播过程建立在Trafodion消息层上，Trafodion消息层负责跟踪参与消息通信的节点健康情况，如果某个节点在这个过程中崩溃，Trafodion的TM进程会得到相应的通知，并进行错误处理。

当Trafodion执行器调用HBase访问层，修改过的HBase-trx库相应地会被调用。通过解析事务ID，HBase-trx层能够获知启动该事务的TM，并向该TM进程进行注册。这样，TM就可以在任意时刻获知参与某事务的所有进程信息。

原始的HBase-trx项目扩展了HBase源代码中和Region Server相关的类实现，有很强的代码侵入性。Trafodion利用了HBase的协处理器，减少了代码间的耦合。这使得Trafodion的HBase-trx实现拥有更好的扩展性。Java语言不支持多重继承，因此采用扩展类的方法，一次只能实现一个特性。采用协处理，则可以实现多种扩展。Trafodion利用Endpoint和Observer协处理器协同工作，作为两阶段事务处理中的资源管理器(Resource Manager)。

请参考Trafodion 分布式事务管理 (pdf, 220 KB) 获得关于事务处理更加详细的信息。

编译器构架

Trafodion的编译器将SQL语句翻译为执行计划，并交给执行器(executor)负责具体执行。

Trafodion采用了多阶段编译器。每个阶段对输入的SQL表达式进行特定变换，并输出作为下一个阶段的输入。接下来将分别介绍每个阶段的详细信息。具体的代码可以参考文件$MY_SQROOT/sql/sqlcomp/CmpMain.cpp，主函数为CmpMain::compile。

Master进程空间中有一份编译器代码的拷贝。因此Master进程无需和单独的编译器进程进行通信，而是可以直接进行函数调用。目前，编译器代码依然不是多线程可重入的，但可以运行顺序的多次调用。某些处理需要嵌套。比如，DDL语句的处理需要调用编译器代码。因此，当需要执行DDL时，执行器会启动一个单独的编译器进程执行所需要的功能。再例举一个例子。'UPDATE STATISTICS'语句会动态地产生SELECT语句以便从系统表中获取统计信息，因为代码不可重入，因此Trafodion会在这类情况下启动单独的编译器进程进行嵌套处理。

编译器是由C++语言编写实现的。

Parser 语法编译器

Paser执行词法和语法分析，将SQL文本转化为语法树。为了处理多语言字符集UCS2编码，Trafodion采用手工编码的词法分析器（没有使用lexer）。(为了处理UTF-8编码，Trafodion首先将文本转化为UCS2，再输入parser进行处理)。语法规则使用Bison规则描述。Parser的输出为语法树，树节点为RelExpr类型。标量表达式用ItemExpr表示，并嵌入在RelExpr中。在接下来的所有编译阶段中，语法树都采用这个同样的形式表示。

Binder绑定器

Binder阶段在语法树中加入元数据信息。SQL对象（表，视图，列等）都会被绑定到相应的元数据。Binder也负责数据类型综合（即将SQL类型解析为C++类型和相应的存储空间）。在这个阶段，检查数据类型是否合法，比如是否符合函数调用的规约，或者是否符合列类型的定义。

Binder还负责处理查询计划缓存的管理。Binder会分辨出类似的，已经被缓存的SQL语句，并直接从计划缓存中取出相应的计划返回，从而略过后续的编译器阶段，极大地节约了编译时间。

Normalizer规范器

SQL语言有一定的冗余性，很多概念可以用多种不同的方式表达。比如，子查询可以用Join来表示。DISTINCT可以用GROUP BY表示。Normalizer消除这类冗余，将不同的表达方法规范为统一的表示方式，以便后续阶段的处理更加容易。

查询条件上推： 查询条件会被尽可能地上推到语法树的顶端。这样编译器就可以为查询条件中的值和表列建立等价表达式组Value Equivalence Group（VEG）。所有对这些表列和值的引用都会被替换为VEG。查询条件上推是Trafodion实现闭包的方法。
规范化：执行查询条件下推，并执行某些规则优化。比如，给定查询,select * from t1 join t2 on t1.a = t2.b where t1.a = 5。编译器可以推断出t2.b =5这个查询条件可以下推到t2的scan操作符。
基于规则的优化： Trafodion执行无条件的基于规则的优化，这些优化仅仅依赖于结果的唯一性和cardinality约束。

Optimizer优化器

Trafodion优化器是一个基于变换规则的成本驱动的优化器。采用了先进的优化器框架：Cascades Framework。这里的术语‘基于变换规则’(rule-based)，和通常意义上的Rule Based Optimization有所不同。这里的规则指的是对SQL进行等价变换的规则，而非基于经验的优化规则。（还需要和嵌入SQL语句中的hint区别开了，这里的规则并不是指hint优化规则）。‘成本驱动’的含义是指Trafodion优化器比较不同执行计划的成本来驱动优化过程。

这是一个自顶向下的优化器：首先它生成一个初始的比较合理的执行计划，然后，利用规则，将执行计划变换为等价形式。优化器计算每个计划的成本，利用'branch-and-bound'算法，应用成本进行计划的搜索过程。和传统的dynamic-programming算法不同，Dynamic programming使用自底向上的搜索顺序。

优化器本身包含多个阶段，根据用户选择的不同优化等级，某些阶段将被略过。第一个阶段会生成一个初始的合理计划。接下来的阶段会应用更多的优化规则。比如，开始阶段只考虑hash join，在后续的阶段才会应用Nest Join和Merge Join。

优化器将区分逻辑表达式和物理表达式。一个逻辑表达式表示某个操作符的语义，比如，一个join。一个执行计划的某些方面仅和逻辑表达式相关，比如预估的输出行数。一个物理表达式则明确指出了操作符的具体物理实现方法，比如，一个nested join。一个执行计划的某些方面和物理表达式相关，比如，预估的消息通信开销。Trafodion利用转换规则将逻辑表达式转换为其他的逻辑表达式或者物理表达式。比如，join的不同顺序可以仅使用不同的逻辑表达式，最后当我们需要将操作符实现为具体物理表达式的时候才考虑具体的join方式。

搜索空间是指数级增长的。因此优化器使用了很多的经验规则来限制搜索的范围。优化器也会考虑一些现实的：对于单个关系操作符的成本估计总是不完美的；当成本估计极不准确的情况下，优化器仍然能够选择一个相对准确的执行计划。

采用自顶向下搜索顺序意味着优化器会重新访问之前已经访问过的计划。优化器利用"memo"数据结构，可以记忆曾经访问过的计划。每个计划都拥有一个哈希ID，以便快速查找。

Pre-Code生成器

Pre-code生成器执行一些无条件的优化规则。利用VEG，优化器对于每个表达式都可以找到最优的表达方式。比如，存在一个VEG包含{T1.A, T2.B, 5}，那么在T2扫描操作符的上下文中，优化器可以利用搜索条件 T2.B=5对整体执行计划进行优化。

Generator 计划生成器

计划生成器将优化器生成的最佳执行计划转换为执行器可以执行的执行方案。在这个阶段，还需要对标量表达式执行底层优化。Trafodion采用开源的LLVM infrastructure将多数执行方案中的标量表达式转为可以直接执行的机器代码。对于少数无法转换的表达式，Trafodion会生成解释性的运行时中间代码。

内存Heap管理

为了高效地管理堆内存，编译器使用了NAHeap类对内存进行直接管理。执行器也使用同一个NAHeap类进行内存管理。Statement堆用来存放编译阶段需要的内存对象，比如，语法树的节点。在编译的最后一个阶段，Trafodion直接释放整个Statement堆，而无需对上千个对象一一调用'delete'。另外一个堆，被称为Context堆，用来保存跨语句的内存对象。比如用于缓存元数据的内存对象，就放置在Context堆中。当创建对象时，Trafodion会仔细考虑将对象放入哪个堆中，以避免空指针和内存泄漏等问题。比如，访问指定文件的操作必须封装在一个全局堆内存对象中，因为在Statement堆中，我们不能依赖析构函数来自动关闭文件句柄。

错误管理

编译器将执行错误保存在ComDiagsArea对象中。编译器代码采用C语言风格的错误处理，调用者必须检查调用函数的返回值来进行相应的错误处理。

执行器构架

Trafodion的执行器采用数据驱动构架。关系运算符由一系列的任务组成，由调度器统一调度执行。运算符直接通过内存队列通信。

关系操作符

一个执行计划由多个段组成，每一个段由一个单独的执行器进程负责。每一个段自身也是一个关系操作符组成的树。每一个关系操作符还可能会包含标量表达式。 关系操作符由两个类处理：ex_tdb和ex_tcb。ex_tdb（tdb代表task description block）仅包含了编译器生成的操作符。ex_tcb(tcb代表task control block)则包含了运行时的状态。比如，操作符之间通信所需要的queue就是保存在ex_tcb中。

标量表达式

标量表达式由表达式evaluator负责处理。如果表达式能够被编译为可执行的机器指令，则evaluator仅仅需要简单地跳转到该代码块的开始位置即可。否则，evaluator需要作为解释器执行表达式逻辑。由于历史的原因，Trafodion内部有两个解释器。第一个解释器（老的解释器）是一个clause-based表达式解释器，每一个clause对应于表达式中的一个操作符。第二个解释器（新的解释器）叫做PCODE-based evaluator。PCODE是一种中间代码。如果不能被直接编译为可执行的机器指令，那么表达式可以被编译为PCODE；对于无法编译为PCODE的部分依旧使用clause表达。有时，为了调试的需要，可以强制编译器生成PCODE，或者clause-based表达式。

进程间通信

各个组件之间的通信通过IPC层进行，IPC抽象了跨越进程边界的对象间通信。通信数据包括执行计划，执行结果数据，或者错误对象(ComDiagsArea)。

CLI接口层

执行器的最顶层软件被称为Call Level Interface(CLI)。CLI采用了类似ODBC的函数接口设计。Connectivity代码通过CLI层和执行器进行交互。在CLI层中，执行器维护SQL语句的抽象和游标。CLI也提供了获取SQL诊断信息的接口。

内存heap管理

执行器使用NAHeap类进行内存堆管理。将内存分为两个部分。第一部分由单个SQL语句使用，存放SQL语句本地所需的内存对象；第二部分存放全局内存对象。

错误管理

执行器也适用ComDiagsArea类进行错误处理。同编译器一样，执行器不使用C++风格的异常处理，而使用传统的检查函数返回值的方法进行错误处理。

统计报告

执行器负责收集特定查询的运行时统计信息。上层软件可以通过CLI接口获取这些统计信息。

源代码结构

在这个小节中，我们将浏览一下Trafodion的源代码结构，并针对每一个源代码模块指出其在Trafodion体系结构中的相应部分。

在Trafodion的core代码库中：

• conn: connectivity子系统
• • conn/jdbc: JDBC Type 4 客户端驱动
• • conn/jdbc_type2: JDBC Type 2 客户端驱动
• • conn/nci: trafci, Trafodion的命令行工具
• • conn/odbc: ODBC
• • conn/odbc/src/odbc/*: ODBC 服务端组件
• • conn/odbc/src/odbc/odbcclient: ODBC Windows客户端驱动
• • conn/unixodbc: ODBC Linux客户端驱动
• sqf: 事务处理子系统以及相关的软件
• • sqf/src/seabed: 消息通信层
• • sqf/src/seatrans: 事务处理子系统
• • sqf/src/seatrans/hbase-trx: Trafodion修改过的HBase-trx代码，包含所有事务处理实现
• • sqf/src/seatrans/tm: 在HBase-trx之上的Trafodion事务管理代码, 包含TM
• sql: SQL引擎, 包括编译器和执行器
• • sql/arkcmp: Compiler主进程
• • sql/bin: 各种SQL进程的主函数
• • sql/cli: CLI层
• • sql/comexe: 编译器和执行公用的代码
• • sql/common: 编译器和执行公用的代码 ；包括定义SQL数据类型的类和诊断信息类
• • sql/executor：执行器
• • sql/exp: 标量表达式evaluator
• • sql/export: 编译器和执行公用的代码 (比如, ComDiagsArea)
• • sql/generator: Pre-code代码生成器和生成器代码
• • sql/optimizer: Binder, Normalizer and Optimizer代码
• • sql/parser: Parser 代码
• • sql/regress: 回归测试
• • sql/sort: 排序实现代码
• • sql/sqlci: 用于调试的命令行SQL交互工具
• • sql/sqlcomp: 编译器驱动代码
• • sql/SqlCompilerDebugger: 编译器的图形化调试器
• • sql/ustat: UPDATE STATISTICS 代码