分析型数据库之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 条评论
登录 后参与评论

相关文章

来自专栏孙小白

mysql的十二条基本语句

库名后面加charset 字符集(如utf8); 现在可以不加,在配置文件里已经设置了默认编码格式。

13610
来自专栏JiekeXu之路

Oracle 12C 最新补丁下载与安装操作指北

上一篇安装文档中说过 Oracle 也有一份安装手册,虽是英文版但很是详细,很有参考意义,如下是官方地址可查看详细内容:https://docs.oracle....

63210
来自专栏Python工程师

Python-sqlite3-05-删除记录

9020
来自专栏孙小白

数据库系统的特点

7140
来自专栏孙小白

数据库系统概述

数据是数据库中存储的基本对象。描述事物的符号记录称为数据。数据是有结构的,记录是计算机中表示和存储数据的一种格式或一种方法。

8520
来自专栏FunTester

python plotly制作接口响应耗时的时间序列表(Time Series )

本人在做工作中,要对某一个接口的响应耗时进行一个长期的统计,由于之前的数据全都写在了数据库中,统计了半年多的数据。在学习了plotly的Time Series ...

9720
来自专栏AVAJ

基于数据库的分布式锁实现

续上次用nginx搭建好反向代理负载均衡的俩个实例后,我在项目中关联了如下这张表:

13830
来自专栏A周立SpringCloud

面试官:谈谈你对 MySQL 索引的认识?

大家好,我渣渣烟。我曾经写过一篇《面试官:讲讲mysql表设计要注意啥》,当时写完后,似乎效果还行!

7720
来自专栏Java架构沉思录

聊聊db和缓存一致性常见的实现方式

数据存储在数据库中,为了加快业务访问的速度,我们将数据库中的一些数据放在缓存中,那么问题来了,如何确保db和缓存中数据的一致性呢?我们列出了5种方法,大家都了解...

9510
来自专栏AustinDatabases

数据库及周边的未来有可能是什么?

今天突发奇想,题目很大,其实估计没有人能准确说出数据库的未来是什么,未来的事情的留到未来去验证,姑且现在说的都是瞎想,虽然是瞎想,但也要有底线不能天马行空。

10920

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励