作者：实验室小陈 / 大数据凋谢实验室
在上一篇文章《内存数据库解析与主流产品比照（二）》中，咱们从数据组织和索引的角度介绍了内存数据库的特点和几款产品的技术实现。本文将持续解析内存数据库，从并发管制、长久化和查询处理的角度介绍几款技术，带来更多维度、更粗疏的内存数据库技术探讨。
— 数据库管理系统中的并发管制—
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.