导读
本文作者是阿里巴巴 OLTP 数据库团队资深技术专家 -- 曲山. 作为自研高性能, 低成本存储引擎 X-Engine 的负责人, 曲山眼中的优秀关系型数据库存储引擎应该具备哪些能力呢?
正文
数据库内核按层次来分, 就是两层: SQL & Storage.SQL Layer 负责将你输入的 SQL statement 通过一系列步骤 (parse/resolve/rewrite/optimize...) 转换成物理执行计划, 同时负责计划的执行, 执行计划通常是一颗树的形式, 其中树的叶子节点 (执行器算子) 部分往往负责单表的数据操作, 这些操作算子就要在 storage layer 来执行了.
因此, 一个数据库存储引擎的主要工作, 简单来讲就是存取数据, 但是前提是保证数据库的 ACID(atomicity/consistency/isolation/durability)语义. 存储引擎对外提供的接口其实比较简单, 主要就是数据写入 / 修改 / 查询, 事务处理(start transaction/commit/rollback...), 修改 schema 对象 / 数据字典(可选), 数据统计, 还有一些周边的运维或数据导入导出功能.
仅仅从功能上来说, 要实现一个存储引擎似乎并不困难, 如今也有很多 Key-Value Store 摇身一变就成为了数据库存储引擎, 无非是加上一套事务处理机制罢了. 但是作为数据库的底盘, 一个成熟的存储引擎必须要考虑效率, 如何高效 (性能 / 成本最大化) 的实现数据存取则成了在设计上做出种种权衡的主要考量. 可以从存储引擎的几个主要组件来讨论:
数据组织
数据在内存和磁盘中的组织方式很大程度上决定了存取的效率, 不同的应用场景选择也不同, 典型的如:
数据按行存储(NSM), 对事务处理比较友好, 因为事务数据总是完整行写进来, 多用于 OLTP 场景.
按列存储(DSM), 把 tuples 中相同的列值物理上存储在一起, 这样只需要读取需要的列, 在大规模数据扫描时减少大量 I/O. 另外列存做压缩的效果更好, 适合 OLAP 场景, 但是事务处理就不那么方便, 需要做行转列. 所以大部分 AP 数据库事务处理效率都不怎么高, 某些甚至只支持批量导入.
混合存储 (FSM), 行列混合布局, 有把数据先按行分组(Segment, SubPage), 组内使用 DSM 组织, 如 PAX, RCFile, 也有先按列分组(Column Group), 组内指定的列按 NSM 组织, 如 Peloton 的 Tile. 此种格式试图结合 NSM 和 DSM 两者的优点, 达到处理混合负载(HTAP) 的目的, 但是同时也继承了两者的缺点.
所以做存储引擎, 一开始就要面临选择何种存储格式的问题. 即便选定了大类, 每种格式中也有无数的细节需要考虑, 每种数据类型的字段如何编码(Encoding), 行存中 null/not null 如何存储, 是否需要列索引加快 project operation, 是否需要对列值进行重排, 列存如何进行数据压缩, 等等, 都要存储空间和存取速度中做平衡.
现代数据库为了应对复杂的应用场景, 往往使用不只一种存储格式, 比如 Oracle 有 In-memory Column Store 在内存中将行存的页面转换为列存方式的 page, 用来加速复杂查询.
当数据选定存储格式以后, 还要选择数据在磁盘和内存中的聚集方式. 以按行存储为例, 大部分存储引擎使用固定大小的页面 (page) 来存储连续的若干行. 当然, 数据行如何连续排列, 有堆表 (随机) 和索引组织表 (按索引序) 两种, 现在较为流行的 LSM-Like 的存储引擎使用不定大小的页面(称为 DataBlock), 只支持按主键索引序聚集; 这两种方式主要区别在于前者被设计为可更新的, 每个 page 中会留有空间, 后者是只读的, 数据紧密存储不带 padding, 便于压缩. 两者的区别实际上是因为事务处理机制有较大的区别导致的, 后面再论.
对于 In-Memory Database 来说, 数据组织的方式会有较大区别, 因为不需要在内存和持久化存储中交换数据, 内存中一般不会使用 page 形式, 而是直接使用索引存储结构 (比如 B+Tree) 直接索引到记录(tuples), 无需 page 这一层间接引用, 减少 CPU cache miss.
缓存管理
缓存的粒度一般是 page, 关键在于缓存替换算法. 目前用的比较广泛的 LRU,LFU,ARC.. 以及各种变种的算法都有在数据库中使用. 另外还有一个是如何更有效的管理内存的问题, 这点上, 定长的 page 会比不定长的更有优势.
当然还要考虑各种 query pattern 对 cache 的影响, 如果单行查询较多, 选用更细粒度 (比如 row) 的 cache 会更有效率, 但是淘汰的策略会更复杂, 很多新的研究开始尝试引入机器学习的方法来优化 cache 淘汰算法, 以及有效的管理 cache.
事务处理
存储引擎之核心, 保证数据库的 ACID. 要保证 D, 大家的做法差不多, 都是写 WAL(Write Ahead Log)来做 recovery, 关键是如何高效的实现 ACI, 也就是所谓的多版本并发控制 (MVCC) 机制.
MVCC 的完整实现比较复杂, 暂不详细阐述, 这里面的关键在于如何处理并发执行过程中的数据冲突(data race), 包括写写冲突, 读写冲突; 因为数据库的负载一般是读多写少的, 要做到高效, 只读事务不能被读写事务阻塞, 这就要求我们的写不能直接去更新当前的数据, 而是要有一套维护多版本数据的能力, 当前的存储引擎管理多版本数据的办法无非两种:
写入数据原地更新, 被更新的旧版本写到 undo 链中, 写入代价大, 事务处理复杂, 但是回收旧版本数据高效.
写入数据不直接更新原来的数据, 而是追加为新版本, 写入代价小, 但是读, 尤其是扫描需要读取层次较多, 更为严重的问题是回收旧版本的数据需要做 compact, 代价很大.
前一种称为 ARIES 算法比大多数主流数据库存储引擎使用, 后一种称为 LSM-Tree 的结构也被很多新存储引擎使用, 受到越来越多的关注.
Catalog
与 KV store 有区别的是, 数据库是有严格的 schema 的, 所以多数存储引擎中的记录都是有结构的, 很多 KV store 在作为数据库存储引擎时, 都是在中间做一层转换, 将上层处理的 tuples 以特定的编码方式转换为 binary key-value, 写入 KVStore, 并在读取到上层后, 依靠 schema 解释为 tuples 格式供上层处理.
这种方法当然可以工作, 但是诸多优化无法实施: a. 数据迭代必须是整行, 即便只需要其中一列, 序列化 / 反序列化开销是免不了的. b. project 和 filter 的工作无法下放到存储层内部进行处理; c. 没有列信息, 做按列编码, 压缩也不可能. d. schema change 只能暴力重整数据... 因此要做到真正的高效, 越来越多的存储引擎选择完全感知 schema, 存储细微结构.
总结
以上所探讨的, 还只是单机数据库的存储引擎几个大的问题, 而现代数据库对存储引擎提出了更高的要求, 可扩展, 高可用已经成为标配, 现在要考虑的是如何给你的存储引擎加上分布式的能力, 而这又涉及到高可用一致性保证, 自动扩展, 分布式事务等一系列更为复杂的问题, 这已远超出本文的范畴, 需要另开篇章.
最后介绍下我们正在开发的阿里自研分布式数据库 X-DB, 其中的存储引擎就使用了我们自研的 X-Engine.X-Engine 使用了一种对数据进行分层的存储架构, 因为目标是面向大规模的海量数据存储, 提供高并发事务处理能力和尽可能降低成本.
我们根据数据访问频度 (冷热) 的不同将数据划分为多个层次, 针对每个层次数据的访问特点, 设计对应的存储结构, 写入合适的存储设备. X-Engine 使用了 LSM-Tree 作为分层存储的架构基础, 并在这之上进行了重新设计.
简单来讲, 热数据层和数据更新使用内存存储, 利用了大量内存数据库的技术 (Lock-Free index structure/append only) 提高事务处理的性能, 我们设计了一套事务处理流水线处理机制, 把事务处理的几个阶段并行起来, 极大提升了吞吐. 而访问频度低的冷 (温) 数据逐渐淘汰或是合并到持久化的存储层次中, 结合当前丰富的存储设备层次体系 (NVM/SSD/HDD) 进行存储.
我们对性能影响比较大的 compaction 过程做了大量优化, 主要是拆分数据存储粒度, 利用数据更新热点较为集中的特征, 尽可能的在合并过程中复用数据, 精细化控制 LSM 的形状, 减少 I/O 和计算代价, 并同时极大的减少了合并过程中的空间放大. 同时使用更细粒度的访问控制和缓存机制, 优化读的性能. 当然优化是无止境的, 得益于丰富的应用场景, 我们在其中获得了大量的工程经验.
X-Engine 现在已经不只一个单机数据库存储引擎, 结合我们的 X-Paxos(分布式强一致高可用框架), GMS(分布式管理服务), 和 X-Trx(分布式事务处理框架), 已经演变为一个分布式数据库存储系统.
来源: https://yq.aliyun.com/articles/688880