作者：实验室小陈 / 大数据凋谢实验室
在上一篇文章《内存数据库解析与主流产品比照（二）》中，咱们从数据组织和索引的角度介绍了内存数据库的特点和几款产品的技术实现。本文将持续解析内存数据库，从并发管制、长久化和查询处理的角度介绍几款技术，带来更多维度、更粗疏的内存数据库技术探讨。
— 数据库管理系统中的并发管制—
1. 内存数据库并发管制的两种策略
a. 多版本的并发管制
内存数据库中的并发管制次要采纳两类策略：1. 多版本的并发管制；2. 分 Partition 解决。并发管制机制能够分为乐观和乐观两种类型。乐观并发管制则认为过程竞争资源总是存在的，因而拜访时先加锁，拜访完再开释；乐观并发管制认为大多数状况不须要竞争资源，只在最初提交前查看是否存在抵触，有抵触就回滚，没有就提交。
乐观并发管制大多数不采纳基于锁的技术实现，并且通常是多版本的。多版本意味着每次更新都会产生新的版本，读操作依据可见范畴选取适合的老版本，读操作不阻塞写操作，所以并发水平比拟高。其毛病是会产生额定开销，例如更新要创立新版本，而且随着版本越来越多，还须要额定开销发出老版本。内存数据库多采纳乐观的多版本并发管制机制，相比于基于锁的乐观并发管制其劣势是开销较小，而且反对并发程度较高的场景；毛病是在有大量写竞争的场景下，事务间抵触概率比拟高时，大量事务会失败和回滚。
b. 分 Partition 解决
内存数据库并发管制的另外一类策略是把数据库分成多个 Partition，每个 Partition 采纳串行形式处理事务。劣势是单 Partition 业务的执行没有用于并发管制的额定开销，毛病是存在跨 Partition 事务时零碎的吞吐率会直线降落。因而，如果不能保障所有业务都是单 Partition 进行，将导致性能不可预测。
2. 多版本并发管制之 Hekaton
Hekaton 采纳乐观的多版本并发管制。Transaction 开始时，零碎为事务调配读工夫戳，并将 Transaction 标记为 active，而后开始执行事务，在操作过程中零碎记录被读取 / 扫描 / 写入的数据。随后，在 Pre-commit 阶段，先获取一个完结的工夫戳，而后验证读和扫描数据的版本是否依然无效。如果验证通过，就写一个新版本到日志，执行 Commit，而后把所有的新版本设置为可见。Commit 之后，Post-Processing 记录版本工夫戳，之后 Transaction 才真正完结。
a. Hekaton 的事务验证
i) Read Stability：Hekaton 零碎可能保证数据的读稳定性（Read Stability），比方交易开始时读到的每条记录版本，在 Commit 时依然可见，从而实现 Read Stability。
ii) Phantom Avoidances：Phantom 指一个事务在开始和完结时执行雷同的条件查问，两次后果不一样。呈现幻影的起因是该事务执行过程中，其余事务对雷同数据集进行了减少 / 删除 / 更新操作。应该如何防止幻影景象呢？可通过反复扫描，查看所读取的数据是否有新版本，保障记录在事务开始时的版本和在完结时统一。
Hekaton 并发管制的益处在于，不须要对 Read-Only 事务做验证，因为多版本可能保障事务开始时的记录版本在完结时仍然存在。对于执行更新的事务，是否做验证由事务的隔离级别决定。例如如果快照隔离级别，就不须要做任何验证；如果要做可反复读，就要做 Read Stability；如果是串行化隔离级别，既要保障 Read Stability，又要保障 Phantom Avoidance。
b. Hekaton 的 回收策略
Hekaton 中的回收工作并不禁独立的线程解决，而是每个事务本人回收。如下图所示，Transaction ID 为 250 的事务完结工夫戳为 150 且状态为 terminated，此时会有一个 Write Set 获取所有老版本，并判断以后所有 active 的 Transaction 的开始工夫戳是否大于 ID 为 250 的事务完结工夫，即 150。如果都大于 150，阐明不可能再基于工夫戳早于 150 的旧版本进行批改，因此由事务回收旧版本，这部分工作是每个线程在解决 Transaction 时的额定工作。
3. 多版本并发管制之 Hyper
Hyper 的并发管制和 Hekaton 的区别次要有以下三点：1. 间接在记录地位进行更新，通过 undo buffer 来保留对数据的批改，数据和所有批改被链接在一起；2. 验证是依据最近的更新与读的记录进行比拟来实现（后续会波及到）；3. 串行化解决 commit，对提交的事务进行排序，并顺次解决。
在事务验证方面，Hyper 的验证须要在日志中记录 Read Predictates，包含查问或 Range Scan，而且要记录插入、删除和更新的记录。在 Hyper 模式中，插入 / 删除 / 更新通过对应的 Undo Buffer 获悉被批改过的记录，所以记录改变对于 Hyper 而言是容易的。
对于每个 Transaction，只须要比拟该事务从开始到 Commit 之间，是否存在其余 Transaction 对满足搜寻条件的数据集进行过增 / 删 / 改，从而判断是否存在幻影景象，如果存在，就间接终止事务。
4. 多版本并发管制 之 HANA 和HStore/VoltDB
HANA 并行管制形式比较简单，采纳乐观的多版本控制，由行级锁爱护数据结构，每行由工夫戳决定每个版本的可见范畴。每个 Transaction 在更新或删除时都须要申请写锁，而且要做死锁检测。
HStore/VoltDB 是一个 Partition 零碎，锁的粒度很粗，每个 Partition 对应一把锁，因而 Transaction 在某节点上执行时，须要拿到该节点所有资源。一旦一个事务可能波及到两个 Partition，就须要把两个 Partition 的锁都拿到。所以 Partition 零碎的长处是单 Partition 处理速度十分快，毛病是多 Partition 效率很低。同时，零碎对于负载的偏斜十分敏感，如果有热点数据，那么热点数据就形成零碎瓶颈。
5. 多版本并发管制之负载预知
假如一个工作负载中，事务须要读和写的数据集能够提前取得，就能够在执行前确定所有事务的执行程序。Calvin 就是基于这样的假如设计的 VLL (Very Lightweight Locking）超轻量级锁数据库原型零碎。通用场景的工作负载是无奈提前晓得读写汇合的，但在存储过程业务的利用中，能够提前确定读写汇合，对于这些场景就能够思考相似 Calvin 的零碎。
— 数据库管理系统中的长久化技术—
对于内存数据库而言，和基于磁盘的数据库雷同也须要日志和 Checkpoint。Checkpoint 的目标是复原能够从最近的检查点开始，而不须要回放所有数据。因为 Checkpoint 波及写入磁盘的操作，所以影响性能，因而要尽量放慢相干的解决。
一个不同是内存数据库的日志和 Checkpoint 能够不蕴含索引，在复原时通过根底数据从新结构索引。内存数据库中的索引在复原时从新结构，结构实现后也放在内存中而不必落盘，内存索引数据失落了再重构即可。另外一个不同是内存数据库 Checkpoint 的数据量更大。面向磁盘的数据库在 Checkpoint 时，只须要把内存中所有 Dirty Page 写到磁盘上即可，然而内存数据库 Checkpoint 要把所有数据全副写到磁盘，数据量无论多大都要全量写一遍，所以内存数据库 Checkpoint 时写入磁盘的数据远大于基于磁盘的数据库。
Hekaton Checkpoint
对于长久化的性能优化，第一要保障写日志时的高吞吐量和低提早，第二要思考复原时如何疾速重构整个数据库。Hekaton 的记录和索引寄存在内存，所有操作写日志到磁盘。日志只记录数据的更新，而不记录索引的更新。进行 Checkpoint 时，Hekaton 会从日志中复原，并依据主键范畴并行处理。如下图，分三个主键范畴：100~199、200~299、300~399，绿色代表数据，红色代表删除的记录（独自保留被删除的文件）。在复原时，Hekaton 用并行算法在内存中重构索引和数据，过程中依据删除记录过滤数据文件，去除被删除的数据，而后从 Checkpoint 点开始，依据日志回放数据。
其余零碎的 Checkpoints
- 采纳 Logic Logging 的零碎如 H -Store/VoltDB，即不记录具体的数据改变，而是记录执行过的操作、指令。它的劣势是记录的日志信息比拟少。写日志时，HStore/VoltDB 采纳 COW(Copy-on-Write)模式，即失常状态是单版本，但在写日志时会另外“复制”一个版本，待写完再合并版本。
- 另一种是定期把 Snapshot 写入磁盘（不包含索引），比方 Hyper 就是基于操作系统 Folk 性能来提供 Snapshot。
— 数据库管理系统中的查询处理—
传统的查询处理采纳火山模型，查问树上的每个节点是一个通用的 Operator，劣势在于 Operator 能够任意组合。但 Operator 拿到的记录只是一个字节数组，还须要调用另一个办法来解析属性以及属性类型。如果这种设计放到内存数据库中，属性以及类型的解析都是在 Runtime 而非编译时进行的，会对性能产生影响。
另外对于 get-next，如果有百万个数据就要调用百万次，同时 get-next 通常实现是一个虚函数，通过指针调用，相比间接通过内存地址调用，这些都会影响性能。此外，这样的函数代码在内存中的散布是非间断的，要一直跳转。综上，传统 DBMS 的查询处理形式在内存数据库当中并不实用，尤其体现在在底层执行时。
内存数据库通常采纳编译执行的形式，首先对查问进行解析，而后优化解析后的语句，并生成执行打算，而后依据模板对执行打算进行编译产生可执行的机器代码，随后把机器代码加载到数据库引擎，执行时间接调用。
下图是对不同查问形式的耗时剖析，能够看出编译执行形式中 Resource Stall 的占比很少。
另外一张图解释了目前的 CPU 架构实现，L2 Cache 和主存之间存在 Hardware Pre-fetcher。L2 Cache 分为指令 Cache 和 Data Cache，指令 Cache 会由 Branch Prediction 实现分支预测，Data Cache 会由基于 Sequential Pattern 的 Pre-fetcher 实现预测。因而，数据库系统的设计须要思考该架构下如何充分发挥 Pre-fetcher 性能，让 Cache 能够一直为 CPU 计算单元提供指令和数据，避免出现 Cache Stall。
Hekaton 编译查询处理
Hekaton 的编译采纳 T -SQL 存储过程，编译的两头模式叫做 MAT Generator，生成最终的 C 代码在编译器中执行。它产生的库和通用 Operator 的区别在于：通用 Operator 须要在运行时解释数据类型；而 Hekaton 编译形式是把表的定义和查问编译在一起，每个库只能解决对应的表而不能通用，天然就能拿到数据类型，这样的实现能取得 3~4 倍的性能晋升。
HyPer 和 MemSQL 编译查询处理
HyPer 的编译形式是把查问树依照 Pipeline 的宰割点每段编译。而 MemSQL 采纳 LLVM 做编译，把 MPI 语言编译成代码。
下图是一个对 MemSQL 性能的测试。没有采纳编译执行时，MemSQL 两次执行雷同查问的工夫都是 0.05 秒；如果采纳编译执行，第一次耗时 0.08 秒，然而再执行时耗时仅 0.02 秒。
— 其余内存数据库系统—
除了之前提到的几种内存数据库外，还有其余一些驰名的内存 DBMS 呈现。
i) SolidDB：诞生于 1992 年的混合型数据库系统，同时具备基于磁盘和内存的优化引擎，应用 VTRIE（Variable-length Trie）树索引和乐观锁机制进行并发管制，通过 Snapshot Checkpoints 复原。
ii) Oracle Times Ten：晚期是惠普实验室名为 Smallbase 的钻研我的项目，在 2005 年被 Oracle 收买，当初多作为大型数据库系统的前端内存减速引擎。Oracle Times Ten 反对灵便部署，具备独立的 DBMS 引擎和基于 RDBMS 的事务缓存；在 BI 工作时反对 Memory Repository，通过 Locking 进行并发管制；应用行级 Latching 解决写抵触，采纳 Write-Ahead Logging 和 Checkpoint 机制进步持久性。
iii) Altibase：于 1999 年在韩国成立，在电信、金融和制造业利用宽泛。Altibase 在 Page 上存储记录，以 Page 为粒度进行 Checkpoint 且兼容传统 DBMS 引擎；反对多版本并发管制，应用预写日志记录和检查点实现持久性和恢复能力，通过 Latching-Free 对 Page 的数据进行 Checkpoint。
iv) PTime: 21 世纪起源于韩国，2005 年发售给 SAP，当初是 SAP HANA 的一部分。PTime 具备极佳的性能解决，对日志记录应用差分编码（XOR），采纳混合存储布局，反对大于内存（Larger-than-Memory）的数据库管理系统。
— 本文小结—
每一个数据库系统都是针对特定的硬件环境设计，基于磁盘的数据库系统面临 CPU 单核、内存小、磁盘慢的场景设计。而内存数据库以内存为主存，不须要再反复读写磁盘，磁盘 I / O 不再是性能瓶颈，而要解决其余瓶颈，比方：1. Locking/Latching 的开销；2. Cache-Line Miss，即如果数据结构定义的不够好或在内存中组织的不好，无奈匹配 CPU 的层级缓存，会导致计算性能变差；3. Pointer Chasing，即须要另一个指针解释，或者查另外的表能力查到记录地址，也是次要的性能开销。此外，还有 Predicate Evaluation 计算、数据迁徙 / 存储时的大量拷贝、分布式系统利用与数据库系统的网络通信等开销。
在本专栏中，咱们介绍了传统基于磁盘的 DBMS 和内存数据库的特点，并从数据组织、索引、并发管制、语句解决编译、长久化几个方面对内存数据库与基于磁盘数据库的雷同和差异性进行了介绍：
1. 数据组织：内存数据库中，把记录分成定长和变长治理，不须要数据间断存储，用指针代替了 Page ID + Offset 的间接拜访；
2. 索引优化：思考面向内存中的 Cach Line 优化、疾速的内存拜访等 Latch-Free 技术，以及索引的更新不记录日志等；
3. 并发管制：能够采纳乐观和乐观的并发管制形式，然而与传统基于磁盘数据库的区别是，内存数据库锁信息和数据绑定，而不必独自的 Lock Table 治理；
4. 查询处理：内存数据库场景下的程序拜访和随机拜访性能差异不大。能够通过编译执行进步查问性能；
5. 长久化：依然通过 WAL（Write-Ahead Logging）做 Logging，并采纳轻量级的日志，日志记录的内容尽量少，目标是升高日志写入磁盘提早。
内存数据库从 1970s 开始呈现经验了实践成熟、投入生产、市场验证等倒退环节。随着以后互联网秒杀、挪动领取、短视频平台等高并发、大流量、低时延的平台呈现，对于数据库性能提出了微小需要和挑战。同时，内存自身在容量、单位价格友好度上一直晋升，以及近期非容失性存储（NVM）的倒退，促成了内存数据库的倒退，这些因素使得内存数据库在将来有着广大的市场和落地机会。
注：本文相干内容参照以下材料：
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.
- 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.