Press "Enter" to skip to content

分析型数据库之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

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注