内存数据库解析与主流产品对比（二）（内存数据库性能）

内存数据库解析与主流产品对比（二）（内存数据库性能）

作者：实验室小陈/大数据开放实验室

在上一篇文章《内存数据库解析与主流产品对比（一）》中，我们介绍了基于磁盘的数据库管理系统相关知识，并简述了内存数据库的技术发展。本篇文章将从数据组织和索引的角度来介绍内存数据库的特点，并介绍几款产品实际的技术实现。

— 数据库管理系统中的数据组织—

定长Block VS 变长Block

内存数据库在内存中对数据进行管理时，虽然不再需要通过Slotted Page的形式对数据进行组织，但也不能在内存中任意为数据分配地址空间，依然需要把数据组织成块（Block/Page）的形式。传统基于磁盘的DBMS采用Slotted Page的形式组织数据是为了读写性能的考虑，因为磁盘接口是以Block/Page为读写单位。而内存数据库采用块的方式组织数据是为了便于寻址和管理，通常会将数据块分为定长数据块（Fixed-Length Data Block）和变长数据块(Variable-Length Data Block)两种。

假设一个数据集已经全部被加载进内存，为了使用方便，内存数据库在进行数据组织时会把记录的定长的属性全部分出来，放到定长数据块；所有变长的属性保存在另外的变长数据块中。例如，通常将数据表中所有小于8个字节的属性都放在定长数据块中，将变长属性和超过8个字节的属性单独放在变长数据块中，并在定长数据块中放一个指向其地址的指针。采用定长数据块管理数据的好处是寻址快，可以通过记录长度和编号确定记录在数据块中存储的位置；记录地址指针所需要的空间少，使得索引结构或其他结构中存放这条记录的内存地址最为精简，并且CPU做Pre-Fetch时预测较准。

在传统基于磁盘的DBMS中，索引叶子节点保存的记录地址是Page ID + Offset，Page Table负责将Page ID映射到Buffer的Frame；内存数据库中，索引的叶子节点保存的记录地址则是直接的内存地址。在传统基于磁盘的DBMS中，访问Buffer中的Page时需要对Page进行加锁/解锁/修改锁的操作，由于现实系统中锁（Latch）的类型可能会很多，一个线程如果要访问一个Page，往往要加好几种类型的Latch。现在内存数据库中没有了Buffer，因此就省去了Latch的开销，性能上有很大提升。

数据组织：数据分区、多版本、行/列存储在多核或多CPU共享内存的系统中，对数据的并发访问冲突是始终存在的。目前的内存数据库系统可以分为Partition System和Non-Partition System两种。Partition System是把所有的数据切分成互不相交的多个Partition，每一个Partition被分配给一个核（或分布式系统中的一个节点），所有操作都是串行执行，没有并发的数据访问，理想情况下可以获得最好的性能。但这类系统的缺点也很明显，例如如何划分Partition以及跨Partition的事务怎么处理等。对于Non-Partition System，所有的核以及所有的线程都可以访问所有的数据，因此一定会存在并发访问冲突，必须采用支持并发访问的数据结构。目前，通用数据库更多的是采用Non-Partition System设计，之所以不采用Partition设计的主要原因是：通用场景下很难对数据进行有效分区，Partition数据库无法使用。

在Non-Partition System中，如果两个线程访问同一个数据项会发生冲突，这时可以考虑Multi-Version的解决方案。Multi-Version的优势在于可以提高并发程度，其基本的思想是通过多版本的数据让所有的读操作不阻塞写操作，从而提高整个系统的性能。对于那些读多写少的系统，Multi-Version性能会很好，但对于一些Write Heavy的系统，性能并不理想。

数据组织还有一个需要考虑的是Row和Column的组织形式。传统数据库系统在磁盘上维护数据时，分为行式存储和列式存储。顾名思义，行式存储是按行存储数据，列式存储是按列存储数据。如果对少量记录的所有属性进行操作，行式存储更加合适，如果只读大量记录的部分列数据，则列式存储性能比较好。比如一条记录有100个属性，本次读操作需要读取所有记录的其中一个属性，如果按行存储，Block读进来后还需要再筛选列；如果按列存储，可以只读取这列数据所对应的Block，所以性能会比较好，适合去做统计分析。但内存数据库不会有这个问题，所有数据都放在内存，无论行存还是列存，访问的代价是差不多的。所以在内存数据库中，行存/列存是可以做交换或任意选择的。当然对于TP应用而言，更多的还是用行存，因为可以一次性把所有属性都读出来。但即使是列存，性能也并没有在基于磁盘的数据库系统中那么糟糕。比如SAP HANA就是一个行列混合的存储，前端的事务引擎是行存储，通过合并整合以后，后端转为了列存储。

— 内存数据库系统对比—

Hekaton是一个Non-Partition的系统，所有线程都可以访问任意数据。Hekaton的并发控制不采用基于锁的协议，而是利用多版本机制实现，每条记录的每个版本都有开始时间戳和结束时间戳，用于确定该版本的可见范围。

H-Store/VoltDB

H-Store/VoltDB是Partition System，每个Partition部署在一个节点，每个节点上的任务串行执行。H-Store/VoltDB没有并发控制，但有简单的锁控制。一个Partition对应一把锁，如果某事务要在一个Partition上执行，需要先拿到这个Partition的锁，才能开始执行。为了解决跨Partition执行问题，H-Store/VoltDB要求Transaction必须同时拿到所有相关Partition的锁才能开始执行，相当于同时锁住所有与事务相关的Partition。

H-Store/VoltDB采用两层架构：上层是Transaction Coordinator，确定Transaction是否需要跨Partition执行；下层是执行引擎负责数据的存储、索引和事务执行，采用的是单版本的行存结构。

— 数据库管理系统中的索引技术—

内存数据库领域在设计索引时，主要是从面向缓存的索引技术（Cache-Awareness）和多核多CPU的并行处理（Multi-Core and Multi-Socket Parallelism）两方面进行考虑。

由于内存数据库不再有磁盘的I/O限制，因此索引目的转变为加速CPU和内存之间的访问速度。虽然现在内存价格较低，但是内存速度的增速与CPU主频的增速相差依然较多，因此对于内存数据库，索引技术的目的是及时给CPU供数，以尽量快的速度将所需数据放入CPU的Cache中。

对于多核多CPU的并行处理，80年代就开始考虑如果数据结构和数据都放在内存中，应该如何合理的构造索引。其中，1986年威斯康星大学的MM-DBMS项目提出了自平衡的二叉搜索树T-Tree索引，每个二叉节点中存储取值范围内的数据记录，同时有两个指针指向它的两个子节点。T-Tree索引结构内存开销较小，因为在80年代内存昂贵，所以主要的度量不在于性能是否最优，而是是否占用最小内存空间。T-Tree的缺点是性能问题，需要定期地做负载平衡，并且扫描和指针也会对其性能产生影响。早期商业系统如Times Ten中，采用的便是T-Tree的数据结构。

另一个例子是PB+-Trees（Pre-fetching B+-Tree）。它并不是新的结构，只是在内存中实现了B+-Tree，每个节点的大小等于Cache Line的长度倍数。PB+-Trees比较特殊的是在整个系统实现过程中，引入了Pre-fetching，通过加入一些额外信息帮助系统预取数据。

PB+-Trees倾向于采用扁平的树来组织数据，论文中给出了它Search和Scan的性能，其中Search性能提高1.5倍，Scan上提高了6倍。处理Search时的性能相比CSB+-Tree，PB+-Trees的Data Cache Stalls占比更小。

Bw-Tree是Hekaton系统中使用的索引，基本思想是通过Compare-and-Swap指令级原子操作比较内存值，如果新旧值相等就更新，如果不等则不更新。比如原值为20（存储在磁盘），而内存地址对应30，那么要是把30更新成40就不会成功。这是一个原子操作，可用于在多线程编程中实现不被打断的数据交换操作。

Adaptive Radix Tree

Hyper的索引树的设计采用了Adaptive Radix Tree。传统Radix Tree是一个前缀树，其优势是树的深度不依赖于被索引的值的个数，而是靠Search Key的长度来决定。它的缺点是每一个节点都要维护可能取值的子节点的信息，导致每个节点的存储开销较大。

而在Adaptive Radix Tree中，为每个节点提供了不同类型长度的格式，分别可以保存4/16/48/256等不同个数的子节点。Node4为最小的节点类型，最多可存储4个子节点指针， Key用来表示节点所存储的值，指针可以指向叶子节点，也可以指向下一层内部节点。Node16 和Node4 结构上一致，但 Node16 可以存放16个 unsigned char 和16个指针，在存放第17个key时则需要将其扩大为 Node48。Node48结构上和 Node4/16 有所不同，有256个索引槽和48个指针，这256个索引槽对应 unsigned char 的0-255，每个索引槽的值对应指针的位置，分别为 1-48，如果某个字节不存在的话，那么它的索引槽的值就是0。当存放第49个key byte 时需要将其扩大为 Node256。Node256结果较为简单，直接存放256个指针，每个指针对应 unsigned char 的0-255 区间。

OLFIT on B+-Trees

OLFIT on B+-Trees（Optimistic Latch Free Index Access Protocol）是HANAP*Time采用的索引技术，能够在多核数据库上保证CPU的Cache Coherence。在多处理器计算机的体系结构中，多个CPU的Cache会缓存同一内存的数据。在内存数据库中，存储的数据会先读到对应Cache再处理；如果缓存数据处理过程中内存数据发生变化，那Cache的数据会因与内存数据不一致而失效，Cache Coherence就是解决这个不同步的问题。

Skiplists

本文首先介绍了内存数据库的数据组织，分别从数据划分，Partition/Non-Partition的系统差异和存储方式进行介绍，并对比了四款产品的实际实现。随后，介绍了六种内存数据库系统的索引技术，并通过例子简述了索引查询原理。下一篇文章将继续对内存数据库进行剖析，从并发控制、持久化存储和编译查询的角度，讨论内存数据库对于查询性能和可用性的优化设计。

注：本文相关内容参照以下资料：

Pavlo, Andrew & Curino, Carlo & Zdonik, Stan. (2012). Skew-aware automatic database partitioning in shared-nothing, parallel OLTP systems. Proceedings of the ACM SIGMOD International Conference on Management of Data. DOI: 10.1145/2213836.2213844. Kemper, Alfons & Neumann, Thomas. (2011). HyPer: A hybrid OLTP&OLAP main memory database system based on virtual memory snapshots. Proceedings - International Conference on Data Engineering. 195-206. DOI: 10.1109/ICDE.2011.5767867. Faerber, Frans & Kemper, Alfons & Larson, Per-Åke & Levandoski, Justin & Neumann, Tjomas & Pavlo, Andrew. (2017). Main Memory Database Systems. Foundations and Trends in Databases. 8. 1-130. DOI: 10.1561/1900000058. Sikka, Vishal & Färber, Franz & Lehner, Wolfgang & Cha, Sang & Peh, Thomas & Bornhövd, Christof. (2012). Efficient Transaction Processing in SAP HANA Database –The End of a Column Store Myth. DOI: 10.1145/2213836.2213946. Diaconu, Cristian & Freedman, Craig & Ismert, Erik & Larson, Per-Åke & Mittal, Pravin & Stonecipher, Ryan & Verma, Nitin & Zwilling, Mike. (2013). Hekaton: SQL server's memory-optimized OLTP engine. 1243-1254. DOI: 10.1145/2463676.2463710.

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。