专栏首页腾讯数据库技术分析型数据库之MonetDB

分析型数据库之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等。腾讯数据库技术团队专注于持续优化数据库内核和架构能力,提升数据库性能和稳定性,为腾讯自研业务和腾讯云客户提供“省心、放心”的数据库服务。此公众号和广大数据库技术爱好者一起,推广和分享数据库领域专业知识,希望对大家有所帮助。

本文分享自微信公众号 - 腾讯数据库技术(gh_83eebc796d5d),作者:腾讯数据库技术

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Buffer pool 详解

    提示:公众号展示代码会自动折行,建议横屏阅读 ---- 1 综述 buffer pool 是 innodb的数据缓存,保存了 data page、index...

    腾讯数据库技术
  • 如何快速删除InnoDB中的大表?

    腾讯数据库技术
  • 浅析InnoDB文件结构

    innodb的物理文件包括系统表空间文件ibdata,用户表空间文件ibd,日志文件ib_logfile,临时表空间文件ibtmp,undo独立表空间等。

    腾讯数据库技术
  • Linux TOP 命令详解

    当前时间(date)、系统已运行时间(last reboot)、当前登录用户的数量(who )、最近5、10、15分钟内的平均负载

    付威
  • Android 8.0以后CPU使用率的方案研究

    由于Android 8.0以后Google的权限限制,SDK再也拿不到进程CPU的实时占用率,只能拿到自己本身进程的Jiffies,而由于拿不到系统整体Jif...

    腾讯移动品质中心TMQ
  • Nginx 负载均衡配置+使用方法

    双面人
  • 重学计算机组成原理(二)- 制定学习路线,攀登“性能”之巅

    需要搞明白,我们每天撰写的一行行C、Java、PHP程序,是怎么在计算机里面跑起来的。

    JavaEdge
  • linux top命令详解

    Java学习123
  • linux下top命令参数解释

    top命令是Linux下常用的性能分析工具,能够实时显示系统中各个进程的资源占用状况,类似于Windows的任务管理器。下面详细介绍它的使用方法。

    一见
  • 火绒小课堂:为什么火绒全盘扫描要占用CPU?

    火绒在进行全盘扫描时,对CPU资源占用较高。很多用户表示不理解,认为CPU占用高是“异常现象”。其实,大家大可不必担心,CPU是一台计算机的运算核心,所有程序的...

    用户6477171

扫码关注云+社区

领取腾讯云代金券