快速注册

Firebolt：如何在十八个月内组装一个商业数据库

木鸟杂记 2023-10-03 04:17:49 英国

假如你是一个初创公司的 CTO，想迅速推出一款面向 AP 市场可用的数据库产品，还得有差异化的功能（不然谁会用一个新产品），你会怎么做呢？

Firebolt 在 2022 年专门发了一篇论文：Assembling a Query Engine From Spare Parts[1] 来讲这个事情。核心思想就是，利用开源组件，像攒台式机一样攒出一个数据库。

让我们看下“装机清单”：

Firebolt 装机清单

了解数据库内核开发的同学都知道，一个数据库包含非常多的组件。就我所做的存储层来说，就可以列一个长长的清单，可以参考我之前写的这篇文章[2]。更遑论数据库的大头——查询引擎了。就算化简再化简，也需要解析器——Parser，计划生成——Planner，计划执行——Runtime。

当然，对于一个数据库来说，最重要的还有对外提供的接口—— SQL 。虽然有 ANSI SQL 这个标准在，但工业上真正使用的却是一个个的“方言”（dialect）。虽然说接口需要独立于实现，但不同的实现总会不可避免的冒出头来，影响到接口。而且，分布式数据库不可避免地会进行站队，选择某个方言。比如 TiDB 选择兼容 MySQL，而 Firebolt 选择兼容 Posgres。

组件选择

选定了兼容的 SQL 方言，下一步就是上面提到的几个重要组件的选择：Parser，Plannner，Runtime。让我们一块来看看 Firebolt 是怎么选的。

Parser & Planner

Parser 就是进行语法解析，将 SQL 语句进行分词，组织成语法树——AST。Planner 就是将 AST 基于规则和代价等进行优化成一个可以执行的算子树。

由于 Parser 和 Planner 的接口是 AST，而 AST 通常来说没有一个统一的标准——也即很难将从属于不同项目的 Parser 和 Planner 组合到一块。因此 Firebolt 倾向于寻找一个同时包括两个模块的项目。

Firebolt 对这两个模块的需求是：

Parser 需要支持大部分 Postgres SQL 方言，包括 DDL、DML、DCL 和 DQL
LogicPlanner 需要支持现代数仓的重要规则，如谓词下推、子查询去关联
LogicPlanner 需要支持对规则变换（rule-based transformation）的扩展
PhysicalPlanner 需要支持对基于代价的连接调序（cost-based join reordering）
PhysicalPlanner 需要支持自定义的统计信息收集和代价模型
Planner 需要支持复合数据类型，如数组、结构体

市面上当时针对这两个模块的开源项目还是挺多的，下面来逐一列举下其优劣：

最后 Firebolt 基于种种考虑，选择了 Hyrise ：

使用 C++ 开发
同时支持基于规则和基于代价的计划改写
代码库简单易于重构

Firebolt 参考 Calcite 的设计和概念体系对 Firebolt 做了深度改写，比如增加了复合类型支持、修改了逻辑执行计划的表示等等。

Runtime

Runtime 是对优化过后的查询计划进行执行的组件，对数据库的性能有至关重要的影响。当时作为一个小创，Firebolt 依然选择了使用开源项目。

Runtime 有两种实现流派——向量化（vectorization）和代码生成（code generation），后者效率可能会高一些，但实现复杂度较高，需要投入的研发资源太多。

总结下，Firebolt 对 Runtime 项目的要求有：

支持向量化执行
有一定的扩展性，可进行分布式的数据处理改造
由于 Runtime 和存储引擎耦合性较高，因此项目最好同时实现了高效的列存引擎

相对 Parser 和 Planner 的多样性选择，Runtime 可供选择的项目相对较少（当时 Facebook Velox[3] 也没有开源）。最终 Firebolt 选择了 ClickHouse：

是一个向量化的执行引擎
经过充分的测试
有自己的列存格式——MergeTree，支持高效的数据裁剪

缝合 Planner 和 Runtime

由于 ClickHouse 的执行引擎要求的格式和 Hyrise 的产出格式并不一致，即后者生成的执行计划树（LQP）并不能被前者直接执行。为此，Firebolt 做了一个骚操作——将 LQP 逆向翻译（backtranslate）回 ClickHouse SQL。

这种方式可以 work，但并不高效，且会丢失一些优化信息。后来，Firebolt 将其进行了替换，将 LQP 直接翻译成了多阶段的分布式执行计划（类似 Spark 执行时的多阶段划分），并借助 protobuf 进行序列化和反序列化，传到每个执行节点上进行执行。当然，也要求对 ClickHouse 进行一定的改造。