乐趣区

阿里资深技术专家:优秀的数据库存储引擎应具备哪些能力?

摘要:作为数据库的底盘,一个成熟的存储引擎如何实现高效数据存取?
导读
本文作者是阿里巴巴 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(分布式事务处理框架),已经演变为一个分布式数据库存储系统。

本文作者:七幕阅读原文
本文为云栖社区原创内容,未经允许不得转载。

退出移动版