分析型数据库之MonetDB

提示：公众号展示代码会自动折行，建议横屏阅读

1 历史

• MonetDB是荷兰阿姆斯特丹大学数学和计算机科学的一个研究所CWI开发的。CWI最有名的是发明了Python(Python之父Guido van Rossum毕业于阿姆斯特丹大学，当时在这里工作)，并且还发明了MonetDB、VectorWise（2008年）等产品。

• MonetDB起源于二十世纪90年代，一个数据挖掘项目需要一个分析型数据库，CWI开发了一叫Data Distilleries，该产品成为了MonetDB的早期产品。

• MonetDB这个名字诞生于2002，并且在2004年9月30号，MonetDB 4发布并且开源，该产品支持SQL:2003标准。

• 2008年，MonetDB/X100启动，该项目对向量计算，CPU cache进行了多项优化，最后并入VectorWise产品。

• 2011年，MonetDB 5诞生，对底层API进行了重构，从MonetDB Instruction Language (MIL)变到MonetDB Assembly Language (MAL)。

• 2015年，开源协议变到Mozilla Public License, version 2.0。

2 存储模型

MonetDB采用列式存储，每一列称作一个BAT（Binary Association Table），每一个BAT存储是一个（OID，value）形式的数组，OID实际上就是行号，不需要真正存储。对于定长的数据类型（integer、decimal、float等），实际上存储就是实际数据的数组。对于变长类型（string等），采用字典存储（BLOB），value是实际字典BLOB文件的position。如下是一个变长类型name和定长类型age转换成的BAT示例如下：

MonetDB采用内存映射方式存储，也就是说内存数据结构和文件内容一致。查询采用晚期物化策略（late tuple reconstruction），只有在发送结果时才进行物化所需的数据。查询引擎在火山模型基础上，在整个执行过程中采用了向量执行方式，优化了CPU cache。

3 执行模型

MonetDB的内核可以看做一个由MonetDB汇编语言(MonetDB Assembly Language，MAL)实现的抽象机（abstract machine）。最主要的MAL为定义在两列BAT上的各种关系代数。每一个算子对应一个MAL指令，该指令参数不能将复杂表达式作为参数。复杂指令会被分解成一系列简单指令的序列（被称为bulk processing）。下图是一个select算子和其对应的实现：

这种用简单循环的实现容易产生高的本地指令，减少cache miss，并且容易被编译器和运算器所优化。

4 系统架构

MonetDB的查询处理包括三个软件层：前端层（Front-end）、后端层（Back-end）和内核层（Kernel）组成。举例如下：

• Front-end。前端主要负责将查询数据映射成BAT和将查询语言映射成MAL。该过程会进行一些strategic optimizations，主要目的是为了减少中间结果的生成。包括一些条件下推，应用join索引等方法。

• Back-end。中间层包括MAL优化和将MAL命令转成kernel接口的任务。MAL优化包括一系列优化模型，也包括一些资源管理的功能。这些优化也称为tactical optimization，包括各种代价优化器（cost-based optimizers）。

• Kernel。内核层包括操作各种BAT和执行各种BAT的算子。

5 关键技术

MonetDB充分认识了硬件的发展，将硬件利用最大化来提高性能。

5.1 内存模型

近20年来，计算机的CPU时钟速度增长迅速，但是内存的读取速度并没有跟上。比如：80年代读取内存大约需要1~2个时钟周期，但是现在大约需要300个，这就导致被称为“memory wall”的现象，就是内存获取的缓慢，导致CPU执行变慢。传统的top命令并不能查看到这种问题，虽然CPU显示是100%，可能有95%的时间在进行内存与cache的交换。为了降低这种内存延时（DRAM latency）问题，硬件厂商通常会在内存和CPU之间，放置多级缓存（CPU cache）。以下是现代内存层级结构。

其中L1、L2的cache速度依次变慢，但仍然比内存速度快很多。计算机存储硬件容量和速度成反比，参考如下：

上图只是给出了一个定性描述，下面给出一个定量的结果。

L1 cache access : 1 nanosecond

L2 cache access : 4 nanoseconds

RAM access : 100 nanoseconds

这就意味着，从cache计算相比从内存计算，能够带了接近25-100倍的提升。遗憾的是大部分程序员并未注意到这一点。还有一个比较通俗的例子是矩阵乘法计算，不同的循环方法，也会导致性能的差别极大。具体参考如下：

MonetDB充分考虑的硬件的这种特性，将各cache的各性能参数量化，统一计算权重，来达到合理评估选择计算模型的目的。

5.2 向量运算

MonetDB的算子是向量运算的，为了充分利用CPU cache，降低CPU cache与内存的频繁交换，MonetDB并不是把整列数据一起执行计算，而是一段一段的计算，每一段称之为一个向量（Vector），尽量使该计算数据能够保存在CPU cache中，这样会极大降低内存交换。通过测试，可以看到如下结果：

通过如上图，横坐标是计算向量的大小（最坐标的横坐标为1，是通常的执行模型，一条一条计算），纵坐标是执行时间。可以看到向量size在1000到4000左右，达到最优。之后随着size增大，交换变得频繁，导致性能下降。

理想的运算应该是运算都在CPU cache内运行。示例如下：

5.3 cache-CONSCIOUS JOINS

对于两表等值连接，通常采用的方法是HashJoin。MonetDB对HashJoin进行了较大的改造（称之为radix-partitioned hash-join），充分考虑了CPU cache，通过降低cache与内存的交换，达到提升性能的目的。举例如下：

传统的Grace Hash-Join当分成H个clusters时，当H超过L1或L2的cache lines时，会发生明显的Cache抖动问题，如果将H=2的B次方，并且H<cache lines进行初次分组，则会有效避免抖动问题。上图显示了L和R通过数值的低3个bit位进行两次分组，各自生成8个clusters。然后L和R的对应cluster再执行HashJoin。这样有效避免了内存抖动（cache thrashing）。

6 缺点

• MonetDB完全基于内存映射文件的，一旦需要swap到磁盘，性能就惨不忍睹。比如当查询的数据扫描量超过内存时，性能会下降明显。

• Decimal限制18，精度不够。

7 参考资料

1 https://en.wikipedia.org/wiki/MonetDB

2 https://stratos.seas.harvard.edu/files/MonetDebull2012.pdf

3 https://www.monetdb.org/AboutUs

4 https://ir.cwi.nl/pub/16497/16497B.pdf

5 http://www.gdmc.nl/projects/rgi-otb/geoinfoned/documents/RGI232-2008-01-p77-boncz.pdf

6 https://jacksondunstan.com/articles/3860

7 http://web.cecs.pdx.edu/~jrb/cs201/lectures/cache.friendly.code.pdf

腾讯数据库技术团队对内支持QQ空间、微信红包、腾讯广告、腾讯音乐、腾讯新闻等公司自研业务，对外在腾讯云上支持TencentDB相关产品，如CynosDB、CDB、CTSDB、CMongo等。腾讯数据库技术团队专注于持续优化数据库内核和架构能力，提升数据库性能和稳定性，为腾讯自研业务和腾讯云客户提供“省心、放心”的数据库服务。此公众号和广大数据库技术爱好者一起，推广和分享数据库领域专业知识，希望对大家有所帮助。