背景介绍
身处大数据时代,在数据库领域,我们要分析处理的数据越来越多,我们分析处理数据的速度也要越来越快,但是传统数据库基于磁盘的计算模型,已经难以满足我们的需求。幸运的是随着硬件的发展,内存设备的性能在不断提高,而价格却在不断下降。内存计算技术将带着我们“飞”起来!
内存计算(In-Memory Computing),实质上是 CPU 直接从内存而非硬盘上读取数据,并对数据进行计算、分析。在数据库上引入内存计算技术,意味着去除磁盘 IO 的消耗,利用内存随机访问的特性可以制定更高效的算法等等。这都极大的提高数据的处理速度。
目前很多商业数据库已经拥有了内存计算功能,如 SAP HANA、DB2 BLU、Oracle 12C、SQL Server 2014。但是商业数据库的价格毕竟不菲,在开源产品飞速发展的今天,利用开源的内存计算产品是一个好主意。
(点击放大图像)
图 1 数据库产品使用排名
从图 1 我们可以看到,目前开源的数据库使用比较多的是 MySQL、Redis、PostgreSQL 等等。Redis、MemCached 是 KV 类型的内存数据库,不支持关系模型,仅作为关系型数据库的缓存。MySQL 支持 In-Memory 引擎,但是不支持数据的持久化,不支持列存储。基于这种情况,我们打算开发一套基于开源关系型数据库之上的内存计算引擎,实现支持内存计算,数据持久化,并行计算等特性。
为什么选择 PostgreSQL?
虽然决定自开发,但是站在巨人的肩膀上是一个好主意!我们决定基于 PostgreSQL 开发一个内存计算的引擎,具体理由如下:
- PostgreSQL 的许可证非常开放(BSD 协议),简单来说,你可以忘记许可证的问题。
- PostgreSQL 提供完善的外部表(FDW:Foreign Data Wrapper)扩展开发机制,可以很容易的开发满足自身需求的插件。
- PostgreSQL 的自身稳定性很高,基于 PostgreSQL 开发产品,不用担心稳定性的问题。
- 在开源社区上有很多 PostgreSQL 的扩展插件,可以借鉴。
- 可以随着 PostgreSQL 的社区版本进行迭代。
- 由于 PostgreSQL 的学院派风格。PostgreSQL 的代码质量很高,便于阅读学习。
内存计算引擎的设计思路
数据需要存储在内存上,由于 PostgreSQL 提供了外部表(FDW)概念,可以通过 API 来对数据进行管理,普通思维是外部表对应的是远程数据库或者其他数据来源,但是我们提出一个概念是将这个 FDW 对应成内存,这样通过开发扩展插件来实现,不影响 PostgreSQL 升级带来的迭代问题,也不需要修改内核源码。数据常驻内存,只是简单的解决了数据库 IO 的问题,只能节省 IO 的时间,并不能带来计算上质的飞跃,我们测试过,只是将数据 Cache 到内存中,性能只有 1-2 倍的提升。如果说设计好存储,利用列式存储将数据分条带分块,通过多线程对数据进行计算,每个线程互不干扰的扫描并计算所分配的条带,这样对内存计算来说能够达到质的飞跃,这也是所有常见数据库所追求的。
外部表 (FDW)
(点击放大图像)
图 2 外部表透明访问
外部表:在 PostgreSQL 内部提供一种表类型,能够提供用户访问外部源数据的一种方式,这是 PostgreSQL 作为学院派设计比较优美的地方,努力打造成世界的中心,提供给开发人员遐想的空间。
列式存储
如图 3 所示,将一张表进行横向切割产生了 stripe,stripe 是由多个块数组构成,blockArray 是多列的 block 数据,block 是由单列的多个行数据组成,在对数据进行索引时,只需要通过 stripeNum、blockArrayNum、blockRowNum 能索引到行,这样组成了 RowID。
(点击放大图像)
图 3 内存列式存储
注:blockArrayNum:DEFAULT is 15blockRowNum:DEFAULT is 10000RowID = stripeNum + blockNum + blockRowNum(“+”号是拼接)
对字符串存储使用了 Hash 字典表,字符串存储过程中会在 Hash 表中对应一个 8 字节的 MapCode,在进行字符串比较过滤或者对字符串进行 Join 计算时,只需要对 MapCode 值进行比较或者对 MapCode 值进行排序而不是对字符串进行比较或者排序,这样不仅带来了效率上的提升,而且还节省了空间。在存储中采用分条带分块的概念,这样的存储模型为多线程计算做好了完美铺垫。
内存计算
在对内存计算分析之前需要提出一个概念,对数据列单个的取出或者两个列的取出都称之为序列 (Time Series),序列是自定义的一种类型,我们打造是所有类型皆序列,如下面的例子:
- SQL:select sum(c1 + 1) from table where c2>10;
- -> select cs_sum(cs_filter(c2>10,c1) + 1) from table_get();
(点击放大图像)
图 4 内存计算流程
对图 4 的分析如下:
我们是将整个 SQL 语句翻译成 UDF 函数来进行执行,通过这样的翻译会生成如图 4 所示的一个树形结构,当中的每个节点都是对应的一个 Iterator,当键入带有 UDF 的 SQL 语句后,准备工作先生成 Iterator 的结构树,在对 SUM 值输出时才开始进行计算。
C2>10 是一个公式,在迭代器中进行的是 C2 与常数 10 的比较,满足条件的会返回序列 (Time Series), 在过滤过程中返回的序列其实是一个 Bitmap,通过这个 Bitmap 可以知道 C1 这个序列哪些记录被选中,再对选中返回的序列进行 Add 操作,最终返回 SUM 结果。
并行计算
首先多线程是通过参数配置启动多少个线程来完成这次计算,配置选项在 postgres.conf 文件,默认情况是单线程计算,如果配置了会根据配置数量来进行启动 nthreads 个线程。
之前也提到过由于使用了分条带分块,因此并行计算不是问题了,以下是拆分条带的间隔
Interval = (stripe_last – stripe_first + nthreads)/nthreads
并行中按照这个间隔来对条带进行扫描并计算,还是以 SUM 为例。
(点击放大图像)
图 5 并行计算分析
如图 5 所示,每个线程都只扫描所分配的条带号并进行计算,最终将各个线程的计算结果 merge,最终得到计算结果。
内存计算引擎的优化 Join
由于使用的是列式存储,因此与原生 PostgreSQL 行式计算引擎有很大的不同,但是实现的原理以及算法都是模仿 PostgreSQL 内部实现,支持三种 Join 方式:Nestloop Join、Sort Merge Join、Hash Join。
Nestloop
实现方式:
(点击放大图像)
参见伪代码,Nestloop 实现的方式比较简单,通过 for 循环进行嵌套实现,所以复杂度是 O(N*M)。
分析: 比较通用的连接方式,分为内外表,每扫描外表的一行数据都要在内表中查找与之相匹配的行,对于被连接的数据子集较小的情况,Nestloop 连接是个较好的选择。
Sort Merge Join
实现方式:
(点击放大图像)
参考 PostgreSQL 中提供的伪代码分析,首先对两个表做 Join 的两列进行排序,由于我们是列存储,这个操作非常容易。接下来遍历两个表,如果合适放入结果集,依次处理直到将两表的数据取完。
分析: merge join 需要在排序上花一部分开销,排序后运算成本接近全表扫描两个表的成本之和。在已经排序的条件下,这种 join 方式具有巨大优势。
hash join
(点击放大图像)
图 6 hash join 实现分析
实现方式:对于要做 join 的两张表,首先将小表转换成 hash map,然后扫描大表的每一行数据,计算行数据的 hash 值,映射 hash map,可以得到匹配的行。
分析:当表比较大的时候,采用 hash join 是比较有优势的。运算成本接近全表扫描两个表的成本之和。当然这会浪费一定的内存空间,不过既然我们是内存计算引擎,内存空间显然不是问题。由于采用 hash 字典技术,字符串数据在表中实际上存储的是字符串对应的 hash 值,这样在做 hash join 的时候,我们选择字符串的列去做 join 的话,我们将更快的得到结果。
持久化
既然是内存引擎会出现断电数据丢失的问题,因此我们在设计之初考虑到了这个问题,添加一个可配置的功能持久化,只要配置该选项是把持久化 switch 打开,在创建内存外部表时,会同时创建 PostgreSQL 原生表,该表的插入操作是会进行 Wal 日志记录以及落盘,在对内存进行增删改操作时,会先将 sql 拷贝一份,并将在 PostgreSQL 原生表中先执行一遍,然后再对内存外部表操作,这样保证了数据的持久化了,数据都可以从原生表以及 Wal 日志中获取。
(点击放大图像)
图 7 数据持久化过程
测试对比
测试环境:
- Server Specs: Physical Server, 24 Cores, 128G RAM
- Test Products: LeMCS; PostgreSQL ; DB2
- Data Volume: 2 tables , 30GB,800w 条记录和 1300w 条记录
测试结果:
(点击放大图像)
图 8 测试对比
如图 8 所示,LeMCS 在对比 PostgreSQL 原生表测试中,计算速度都能够快到 5x-30x。
附测试 sql:
(点击放大图像)
注:LeMCS 均使用的是 UDF 函数替换进行测试
后续开发
通过运用以上的技术手段实现的内存计算引擎,以插件的形式嵌入 PostgreSQL 数据库中,目前通过测试使用正常,达到我们之前制定的目标。当然很多问题需要后续开发进行解决。目前所有对内存中表的访问都是通过自定义函数(UDF)来实现的,为了便于使用,我们正在开发对于标准 SQL 的支持。后续我们会将这款工具发布出来,与有需要的同学分享,大家一起使用并持续开发,把这款工具打造的更加强大,帮助更多的人。
作者介绍
联想数据库团队,集开发和运维于一体的团队,大部分成员具有 6 年以上数据库领域相关经验,部分成员拥有原厂工作经验。团队协同合作,专业分工,负责运维 800 多个数据库实例,数据库可用率达到 99.8% 以上,涉及 DB2、Oracle、SQL-Server、 MySQL、PostgreSQL、Redis、MongoDB、Hadoop 等 10 多款产品。团队自开发了管理和部署工具,大大提升了运维效率,利用大数据技术解决传统数据库的性能瓶颈,拓展 PostgreSQL 内存计算功能。团队不断壮大,正式进军对外服务领域,现已在帅康、鞍钢等数据库优化、迁移等项目中取得显著成效,致力于打造更专业、快捷的原厂级服务。(liuhc10@lenovo.com)
感谢木环对本文的审校。
给InfoQ 中文站投稿或者参与内容翻译工作,请邮件至 editors@cn.infoq.com 。也欢迎大家通过新浪微博( @InfoQ , @丁晓昀),微信(微信号: InfoQChina )关注我们。
评论