关于数据库:内存数据库解析与主流产品对比二

作者：实验室小陈 / 大数凋谢实验室

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

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

定长 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 就是一个行列混合的存储，前端的事务引擎是行存储，通过合并整合当前，后端转为了列存储。

— 内存数据库系统比照—

接下来从数据组织的角度，简要介绍一下 4 个具备代表性的零碎：SQL Server 的内存数据库引擎 Hekaton、慕尼黑工业大学的内存数据库系统 HyPer、SAP 的 HANA、图灵奖获得者 Michael Stonebraker 的 H -Store/VoltDB。

Hekaton

Hekaton 是一个 Non-Partition 的零碎，所有线程都能够拜访任意数据。Hekaton 的并发管制不采纳基于锁的协定，而是利用多版本机制实现，每条记录的每个版本都有开始工夫戳和完结工夫戳，用于确定该版本的可见范畴。

Hekaton 中每一张表最多有 8 个索引，能够是 Hash 或者 Range 索引。同时，所有记录版本在内存中不要求间断存储，能够是非间断存储（No-Clustering），通过指针（Pointer Link）将同一记录的不同版本关联起来。

上图所示，图中有一个蕴含姓名、城市和金额字段的表，姓名字段上有一个 Hash 索引，城市字段上有一个 B -Tree 索引。彩色箭头代表姓名索引对应的指针，名字 John 对应的第一条记录，指向下一个具备雷同结尾字母名字的记录。每条记录蕴含有开始和完结工夫戳，红色示意存在一个事务正在更新记录，事务提交后会替换完结的工夫戳。B-Tree 索引也是同理，蓝色箭头指针依照城市值串联。

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 执行；上层是 执行引擎 负责数据的存储、索引和事务执行，采纳的是单版本的行存构造。

H-Store/VoltDB 中的数据块分为定长和变长两类：定长数据块的每条记录长度都雷同，索引中采纳 8 字节地址指向每条记录在定长数据块中的地位；变长属性被保留在变长数据块中，在定长数据块的记录中对应一个指针（Non-Inline Data），指向其在变长数据块中具体的地位。在这种数据组织形式下，能够用一个压缩过的 Block Look-Up Table 来对数据记录进行寻址。

HyPer

HyPer 是多版本的 Non-Partition System，每个 Transaction 能够拜访任何数据。同时 HyPer 是针对于 HTAP 业务建设的 TP 和 AP 混合解决零碎。HyPer 通过 Copy on Write 机制实现 TP 和 AP 混合解决。假如以后零碎正在对数据集做事务处理，此时如果呈现 AP 申请，HyPer 会通过操作系统的 Fork 性能对数据集做 Snapshot，随后在快照下面做剖析。Copy on Write 机制并不会对内存中的所有数据进行复制，只有因 OLTP 业务导致数据发生变化时，快照才会真正拷贝出原数据，而没有变动的数据则通过虚拟地址援用到雷同的物理内存地址。

此外，Hyper 采纳多版本控制，所有更新都是基于原记录的，每条记录都会保护一个 Undo Buffer 存储增量更新数据，并通过 Version Vector 指出以后最新版本。因而，能够通过 Transaction 找到被批改过的记录，同时能够通过反向利用增量数据来找回批改前的版本，当然也能够对数据版本进行定期交融或复原等操作。

SAP HANA

SAP HANA 是一个 Non-Partition 的混合存储系统，物理记录在存储介质中会通过三个阶段：1. 事务处理的记录存储在 L1-Delta（行存形式）；2. 随后记录转化为列式并存储在 L2-Delta（列式存储、未排序字典编码）；3. SAP HANA 的主存是列存（高度压缩并采纳排序字典编码）。每条记录经验着从行存到列存的映射合并，相当于一个多版本设计。

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

内存数据库畛域在设计索引时，次要是从面向缓存的索引技术（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 的数据结构。

那么索引的设计为什么须要思考 Cache-Awareness 呢？1999 年有钻研发现内存拜访中的 Cache Stall 或者 Cache Miss 是内存零碎最次要的性能瓶颈。该钻研进行了一项性能测试，通过对 A /B/C/D 4 个零碎评测，测试以下过程的工夫占比：Computation、Memory Stalls、Branch Mispredicitons 和 Resource Stalls。Computation 示意真正用于计算的工夫；Memory Stall 是期待内存拜访的工夫；Branch Mispredicitons 是指 CPU 指令分支预测失败的开销；Resource Stalls 是指期待其余资源的工夫开源，如网络、磁盘等。

能够看到 Memory Stall 在不同的测试场景都会占据较大比例开销。因而对于内存索引构造来说，倒退面向缓存的索引的次要目标就是为了缩小 Memory Stall 的开销。

CSB+-Tree

这里介绍几个典型的内存索引构造例子。第一个是 CSB+-Tree，它在逻辑上依然是 B +-Tree，然而做了一些变动。首先每个 Node 的大小是一个 Cache Line 长度的倍数；同时 CSB+-Tree 将一个节点的所有的子节点组织成 Children Group，一个父节点通过一个指针指向它的 Children Group，目标是缩小数据结构中的指针数量。因为 CSB+-Tree 的节点与 Cache Line 长度相匹配，只有依序读取，就能够达到较好的 pre-fetche 性能。当树决裂时，CSB+-Tree 会对内存中的 Group 重新分配地位，因为 CSB+-Tree 节点在内存中不须要间断，排好后再创立新的指针链接就能够。

PB+-Trees

另一个例子是 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 占比更小。

另外一个性能比照是，当没有采纳预取时，读取一个 Node 大小等于两个 Cache Line 的三级索引须要 900 个时钟周期，而加了预取后仅须要 480 个周期。PB+-Trees 还有一个实现是，它会在每个节点加上 Jump Pointer Array，用来判断做扫描时要跳过多少 Cache Line 以预取下一个值。

Bw-Tree

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

Bw-Tree 中存在 Mapping Table，每一个节点都在 Mapping Table 中有一个存储地位，Mapping Table 会存储节点在内存中的地址。对于 Bw-Tree 来讲，从父节点到子节点的指针并不是物理指针，而是逻辑指针，也就是记录在 Mapping Table 中的地位并不是真正的内存地位。

Bw-Tree 采纳的设计是节点的更新并不是间接批改节点，而是通过减少 Delta Record（增量记录）来保留批改的内容，而后在 Mapping Table 中指向 Delta Record，如果有新的更新就持续指向新的 Delta Record。在读取一个节点的内容时，实际上是合并所有的 Delta Record。因为对 Bw-Tree 的更新是通过一个原子操作来实现的，产生竞争时只有一个改变能胜利，因而是一种 Latch-Free 构造，只须要靠 Compare-and-Swap 就可能解决竞争问题，不再须要依赖锁机制。

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 区间。

比如说在这个例子里，咱们要索引一个整数（+218237439），整数的二进制示意模式为 32 位，随后将 32 位 bit 转换为 4 个 Byte，这 4 个 byte 十进制示意为 13、2、9、255，这就是它的 Search Key。在索引树中，第一层为 Node 4，13 合乎这一层的存储要求，于是就保留在第一层节点上，前面的位数则进入下一层存储，下一层为 Node 48，用来存储 2；接下来的每一位都存储到上面的每一层。因为本例子中整数为 4 个字节示意，故共有 4 层。能够看到，每个节点的构造是不一样的，依据字节位数和程序逐个存储，数值在这一层目前有多少个不同的值，就抉择什么类型的节点。如果以后类型的不够用，能够再减少个数，每个节点能够包容的 key 是动态变化的，这样既能够节俭空间，又能够进步缓存局部性。

另外 Adaptive Radix 还采纳了门路压缩机制，如果一条门路的父节点只有一个子节点就会将之压缩合并。Adaptive Radix 之所以采纳这样的索引构造，是因为每个节点的大小都等于一个 Cache Line，所有操作能够在一个 Cache Line 的根底上实现。

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 就是解决这个不同步的问题。

思考这样一个场景：如下图所示，内存中有一个树形数据结构，由 4 个 CPU 解决，每个 CPU 有本人的 Cache。假如 CPU-P1 先读了 n1、n2、n4，Cache 中便有了 n1、n2、n4。随后 CPU-P2 读 n1、n2 和 n5 时，假如这个数据结构不是 Latch-Free，如果在读的同时且容许批改，就须要一个 Latch 来在读的时候上锁，读完再开释。因为内存数据库中 Latch 和数据放在一起，数据尽管没有变动，然而 Latch 的状态产生了扭转，计算机的硬件构造会认为内存产生了变动。所以，当多个 CPU 读同样的数据时，只有最初一次读取状态是无效的，前序的读取会被认为生效。这就会呈现即便都是进行读操作，然而因为 Latch 状态扭转导致 CPU 的 Cache 生效。因而 OLFIT 设计了一套机制，要求写操作申请 Latch，读操作不须要。OLFIT 通过版号保护读写事务，每个 CPU 读前先把版本号拷贝到本地寄存器，而后等读完数据后，再判断此时版本号跟读前的是否一样。如果一样就持续失常执行，不一样就阐明 Cache 生效。因而，读申请不会引起其余 CPU 的 Cache 生效。

通过这个例子能够看到，内存数据库思考的问题和基于磁盘的数据库是不一样的，没有了磁盘 I / O 的因素，就须要思考其余方面对性能的限度。

Skiplists

Skiplists 是 MemSQL 的数据处理引擎所用到的技术，它的最底层是一个有序的列表，下层依照肯定的概率（P-value）抽取数据，再做一层列表。进行大列表搜寻时，从最上层开始一层层递进，相似于二分查找，粒度能够依据理论状况自定义。之所以这样设计是因为所有对列表的插入操作，都是能够通过 Compare-and-Swap 原子操作实现，从而省去了锁的开销。

— 本文小结—

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

注：本文相干内容参照以下材料：

1. 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. 

2. 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. 

3. 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. 

1. 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. 

5. 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.