作者：宫学庆 华东师范大学软件工程学院的博士生导师
速记整顿：实验室小陈 / 大数据凋谢实验室
8 月 26 日，星环邀请来自华东师范大学软件工程学院的博士生导师宫学庆传授带来《数据库前沿技术系列讲座》，分享数据库业内前沿倒退和钻研热点。现将宫学庆传授的培训第一讲内容：内存数据库的技术倒退分享给大家。
— 基于磁盘的数据库管理系统 —
传统的数据库管理系统（DBMS）通常是采纳基于磁盘的设计，起因在于晚期数据库管理系统设计时受到了硬件资源如单 CPU、单核、可用内存小等条件的限度，把整个数据库放到内存里是不事实的，只能放在磁盘上。因为磁盘是一个十分慢的存储设备（绝对于 CPU 的速度），因而学术界和工业界倒退出的数据库管理系统在架构上都必须适应过后的硬件条件，沿用至今的 Oracle 和 MySQL 等数据库管理系统依然采纳的是这种架构设计。
随同着技术的倒退，内存曾经越来越便宜，容量也越来越大。单台计算机的内存能够配置到几百 GB 甚至 TB 级别。对于一个数据库利用来说，这样的内存配置曾经足够将所有的业务数据加载到内存中进行应用。尽管大数据处理的数据量可能是 PB 级别的，但那些数据个别是非结构化的数据。通常来讲，结构化数据的规模并不会特地大，例如一个银行 10 年到 20 年的交易数据加在一起可能只有几十 TB。这样规模的结构化数据如果放在基于磁盘的 DBMS 中，在面对大规模 SQL 查问和交易解决时，受限于磁盘的 I / O 性能，很多时候数据库系统会成为整个利用零碎的性能瓶颈。
如果咱们为数据库服务器配置足够大的内存，是否能够依然采纳原来的架构，通过把所有的结构化数据加载到内存缓冲区中，就能够解决数据库系统的性能问题呢？这种形式尽管可能在肯定水平上进步数据库系统的性能，但在日志机制和更新数据落盘等方面依然受限于磁盘的读写速度，远没有施展出大内存零碎的劣势。内存数据库管理系统和传统基于磁盘的数据库管理系统在架构设计和内存应用形式上还是有着显著的区别。
— 缓冲区治理形式 —
在传统的数据库管理系统中，数据的主存储介质是磁盘。例如，逻辑上的一张表通常会被映射到磁盘上的一个文件，文件是以数据块（Data Block，也称作 Page）的模式存储在磁盘上。对于结构化数据来说，一条记录会被保留在磁盘上的某个数据块中，能够用数据块 ID 和 Offset/ 偏移量来示意该条记录的具体位置。这种模式的数据块也被称作 Slotted Page，顾名思义是把数据块划分成很多槽位，而后一个 Record 放在某一个槽位上。在对某条记录进行解决时，能够通过代表该记录地址的 Page ID + Offset 从磁盘上获取该记录；随后零碎会把存储有该条记录的数据块从磁盘读到缓冲区（Buffer Pool 分为多个 Frame，每个 Frame 能够保留一个磁盘块），再从缓冲区将该条记录读到线程或事务的工作区进行解决；解决完结后将更新的记录写回缓冲区中的数据块，再由数据库管理系统将批改过的数据块写回到磁盘上。
基于磁盘的数据库管理系统中的数据拜访示例
在基于磁盘的数据库管理系统中，解决查问时通常会把整个索引加载到内存，而 B + 树索引中一个索引节点的大小通常是一个数据块。每个被索引的 key 值在索引叶子节点中都有对应的索引项，索引项中蕴含该 key 值所对应记录的存储地位（Page ID + Offset）；当一个数据块被加载到内存中的缓冲区时，DBMS 通过 Page Table 构造来保护 Page ID + Offset 的地址与内存缓冲区地址的转换。在拜访数据时，先在 Page Table 中查找是否存在对应的 Page ID + Offset，如果没有则阐明这条记录依然在磁盘上，须要先把磁盘上数据块的读进缓冲区，而后再在 Page Table 中保护好地址映射关系。具体的实现过程是，DBMS 首先会在缓冲区中寻找可用的 Frame，如果没有就依据缓冲区替换算法选取脏页（Dirty Page）替换进来；如果选中了某个脏页进行替换，则须要对该地位加 Latch 锁来保障在替换过程中该地位不会被其余事务拜访（Latch 前面会介绍）。在脏页写回磁盘后，零碎就能够把指标数据块读入到缓冲区中的该地位，再将其在缓冲区中的地址写到 Page Table，保护好地址映射关系；在这些操作实现后再将 Frame 上的 Latch 锁开释。
传统 DBMS 中的内存地址映射
对于传统基于磁盘的 DBMS 而言，即便内存缓冲区足够大，能够将所有数据加载到内存中，但拜访数据过程中的地址映射和转换仍然存在，只是省掉了将数据块从磁盘加载到内存的开销。即便数据曾经全副被加载到内存，基于磁盘的 DBMS 性能上与内存数据库相比还是有很大差距，这是其中一个重要的起因。
总结来看，基于磁盘的 DBMS 和内存数据库在实现技术上一个重要区别是：在拜访数据时，基于磁盘的 DBMS 须要通过地址映射将数据在磁盘上的地址转换成在内存中地址，而内存数据库在设计上则是间接应用数据在内存中的地址。
— 事务 ACID 属性保障 —
在数据库管理系统中，须要保障并发拜访场景下事务的 ACID 属性，即事务的原子性、一致性、隔离性和持久性。事务的 ACID 属性次要靠数据库管理系统中的两个机制实现，一个是并发管制，另一个是 Logging/Recovery 机制。
- 并发管制
传统基于磁盘的 DBMS 大部分是采纳基于锁（Lock）的乐观并发管制，即事务在拜访数据时先加锁，用完后再进行解锁，其余事务在拜访数据时如果存在抵触则须要期待领有锁的事务开释锁。传统 DBMS 个别会在内存中保护一个独自数据结构——Lock Table 来寄存所有的锁，由 Lock Manager 模块进行对立治理，这样在内存中锁和缓冲区中的数据是离开寄存和治理的。事务在拜访数据时先向 Lock Manager 申请数据所对应的锁，而后再拜访数据；执行完结后通过 Lock Manager 把锁开释，Lock Manager 可能保障所有事务申请和开释锁都是遵循严格的两阶段封闭协定（strict 2 phase locking protocol）。同时，并发管制机制所带来的开销与用户的理论业务解决没有间接关系，是用于保障事务一致性和隔离性的额定开销。
内存数据库在拜访数据时也须要加锁，但和基于磁盘的 DBMS 不同，锁和数据在内存中是寄存在一起的，通常是将锁信息保留在数据记录 Header 中。为什么基于磁盘的 DBMS 要独自将锁信息放在 Lock Table 中，而内存数据库就能够把锁信息和数据寄存在一起呢？因为在基于磁盘的 DBMS 中，数据块是有可能被零碎从内存缓冲区中替换到磁盘上，如果锁信息和数据放在一起，一旦数据块被替换进来，Lock Manager 和所有事务都无奈取得对于数据的锁信息。所以说对于传统基于磁盘的 DBMS 来讲，锁要独自保护在内存中，且须要始终保持在内存中，不能被替换进来。而对于内存数据库来说，不存在这样的场景。
实际上，数据库管理系统中有两种锁机制，别离被称为 Lock 和 Latch，目标都是为了爱护数据的一致性不被并发拜访所毁坏。Lock 机制是对数据库逻辑内容的爱护，一般来说领有持续时间长，通常是事务执行的整个过程；并且 Lock 机制要反对事务的回滚以撤销事务对数据批改。而 Latch 机制是为了保障内存中特定的数据结构不会因为并发拜访而导致谬误，比方在多线程编程时有一个共享队列产生插入、删除等操作时，须要 Latch 保障操作过程中的队列不受其余线程的烦扰。Latch 的放弃时长与操作无关，本次操作做完就完结，同时也不须要反对对数据批改的回滚。
所以传统 DBMS 如果要对缓冲区中的一个 Page 做操作则须要加 Latch；如果是批改数据库的内容则须要加 Lock，独自放在 Lock Table 保护和治理。下图是对 Lock 和 Latch 的一个简略比照。
Lock 和 Latch 特色比照
- Logging 和 Recovery
数据库管理系统中，Logging 和 Recovery 机制是日志来保障事务的原子性和持久性的形式。原子性意味着一个事务中的所有操作必须同时胜利或者撤销，在执行一半做不上来时，能够依照日志进行回滚；持久性意味着数据如果失落，能够依据日志来进行复原。
在传统 DBMS 的 Logging 和 Recovery 中，最重要的概念是 WAL（Write-Ahead Log）——预写式日志。WAL 是指零碎中所有更新操作都有对应的日志，而在日志没有落盘前，对数据的批改不容许落盘。零碎中每条日志都有一个 LSN 号（Log Sequence Number），所有的 LSN 号枯燥递增，日志落盘的过程是向磁盘的间断写（程序写）。但如果零碎严格依照一条日志对应一条操作，日志落盘后马上将操作对数据的更新后果落盘，那么零碎性能会受到很大影响。所以，大多数的 DBMS 会采纳 Steal + No Force 的缓冲区管理策略。Steal 是指 DBMS 能够将未提交事务的更新刷到磁盘，不用等事务提交时再把更新刷到磁盘，进步了零碎刷盘的灵活性和性能；如果在事务未提交时产生 crash，因为更新可能曾经写到磁盘，这时就须要通过对日志的 undo 操作进行回滚。No Force 是指在事务曾经提交后，对数据的更新能够仍然寄存在内存缓冲区中不写入磁盘，在合并其余事务的更新后再一次性写入磁盘，为零碎提供优化空间。但 No Force 可能带来的危险是：如果事务曾经胜利提交但更新没有写到磁盘，此时呈现 crash，则依然在内存中的数据更新就会失落，须要依据曾经写到磁盘的日志（事务胜利提交的前提是其所有日志都必须曾经落盘）进行 redo 操作。
有了 WAL 和 Steal + No Force 机制后，就能够给基于磁盘的 DBMS 提供最大的灵活性，来优化磁盘 I /O。但对于内存数据库而言，所有的数据放在内存里，是否还须要这个机制呢？能够明确的一点是，内存数据库还是须要 Logging 的，但和基于磁盘的 DBMS 有所区别，在日志中只记录 redo 操作所需的信息，不记录 undo 所需的信息。大家能够想一下这是为什么？另一方面，内存数据库在 Logging 过程中不记录对于索引的更新，只记录对于根底表的更新，那 Logging 过程中所需写盘的内容就少了很多。而在内存数据库呈现故障须要复原时，首先从磁盘上保留的检查点（Check Point）数据和日志中复原根底表，而后在内存中从新结构索引。
— 面向磁盘的 DBMS 性能开销 —
2008 年，SIGMOD 的一篇论文对面向磁盘的数据库性能开销做了剖析，把整个数据库系统的开销做了划分。剖析发现：假如一次业务解决的总开销是 100%，实际上只有 7% 不到的资源是在真正解决业务逻辑；34% 用于缓冲区治理如缓冲区的加载替换、地址转化等；14% 解决 Latching；16% 解决 Locking；而后 12% 解决 Logging；最初 16% 用于对 B 树索引的解决。也就是说，机器资源跑满负荷当前，真正用于解决业务逻辑的只有 7%。
磁盘数据库系统性能开销
那么是否能够将开销大的局部去掉，来进步业务逻辑的资源占比呢？如果数据库是单用户的，没有并发竞争抵触，那么能够省去 Locking 和 Latching 等方面的开销。历史上也有一些单线程的解决方案，例如将数据库分成多个 Partition，每个 Partition 由一个线程解决等。但这样的计划具备显著毛病：每个 Partition 是串行解决，如果有一个长的事务在执行，串行解决将导致后续事务全副被阻塞，直到该事务完结。而且面向磁盘的零碎在进行大规模事务处理时瓶颈是磁盘 I /O，如果单线程执行，在从磁盘读取数据时 CPU 将处于闲暇状态。但对于内存数据库来说，所有数据存储在内存，磁盘 I / O 不是零碎次要瓶颈，因而应用的技术与之前有了很大的差异。当然技术在倒退过程中也经验了各种各样的尝试，某些技术的倒退不适宜于事实背景，缓缓就被人遗记了。
能够看到，基于磁盘的数据库管理系统做了很多额定的管理工作，这些工作尽管不解决业务逻辑，但在保障业务逻辑正确性上不可或缺。对于内存数据库而言，面临的问题是应该做哪些优化来失去最优的性能。和基于磁盘的零碎相比，内存数据库主存储是内存，但仍然须要磁盘来做 Check Point 和 Logging，故障时要靠磁盘上的检查点数据和日志来复原整个内存数据库。
— 内存数据库技术历史倒退 —
内存数据库的倒退大抵能够分成三个阶段：1984 年到 1994 年的 10 年；1994 年到 2005 年的 10 年；2005 年当前到当初。第一个阶段呈现了内存相干的解决技术；第二阶段呈现了一些内存数据库系统；第三个阶段就是咱们当初面临的场景。
- 1984 年 – 1994 年
在 1984 年到 1994 年间，学术界针对内存数据管理提出了很多假如，比方内存缓冲区能够放进全副数据，能够采纳组提交和疾速提交优化技术等。同时也提出了面向内存的数据拜访办法，不再像基于磁盘的 DBMS 一样采纳 Page ID + Offset 形式进行拜访，而是在所有数据结构中都间接采纳内存地址。还有面向内存的 T -tree 索引构造以及对系统按性能分成多个解决引擎，有的专门做事务处理，有的专门做复原，相当于有两个核，一个专门负责事务处理，另一个负责日志解决。此外还有和 Partition 相干的主存数据库，把数据库分成很多个 Partition，每个 Partition 对应一个核（或节点），过程间没有竞争。能够看到，这个期间的数据库技术倒退曾经在思考如果数据全副放在内存，能够采纳哪些技术。但受限于过后的硬件条件，这些技术并没有失去大规模利用。
- 1994 年 – 2005 年
1994 年到 2005 年间呈现了一些商业内存数据库系统，比方贝尔实验室研发的 Dali、Oracle Times Ten 的前身 Smallbase 等。同时，也呈现了一些面向多核的优化零碎如 P *-Time（当初是 SAP-HANA 事务处理引擎）。过后也有一些 Lock-free 的实现技术被利用于内存数据库系统，即无锁的编程技术和数据结构。
- 前两阶段小结
前两个阶段的技术大抵能够分成这样几类：
1、解决 Buffer Pool 的 In-Direction 拜访：把间接拜访替换掉，换成间接的内存地址拜访；索引的叶子节点不再放 Page ID 和 Offset，而间接是内存地址。
2、Data Partition：切分数据，不做并发访问控制的一类技术。
3、Lock-free 和 Cache-Conscious：相较于面向磁盘的数据库管理系统把一个索引节点存储在一个数据块中，内存数据库中一个索引节点是一个或几个 Cache Line 的长度。
4、粗粒度的锁：一次锁一张表或一个 Partition，而不是一条记录，但这种技术当初应用较少，因为多核场景拜访竞争强烈，粗粒度锁可能导致并发水平升高。（目前应用较少）
5、Functional Partition：把零碎依照性能进行切分，每一个线程负责特定的性能等。（目前应用较少）
DBMS 历史技术总结
— 数据库系统的现代化倒退 —
在当初的环境中，硬件条件根本有三个特点：1. 内存大而便宜；2. 多核 CPU（从主频晋升转变到内核数的晋升）；3. Multi-Socket 即多核多 CPU，意味着解决的并发水平能够越来越高。这些都是数据库系统研发在当下所面临的状况。
古代硬件环境
对于内存数据库而言，CPU 和磁盘 I / O 不再是次要瓶颈，因而优化技术目前次要从以下角度来思考：
- 去掉传统的缓冲区机制：传统的缓冲区机制在内存数据库中并不实用，锁和数据不须要再分两个中央存储，但依然须要并发管制，须要采纳与传统基于锁的乐观并发管制不同的并发控制策略。
- 尽量减少运行时开销：磁盘 I / O 不再是瓶颈，新的瓶颈在于计算性能和性能调用等方面，须要进步运行时性能。
- 采纳编译执行形式：传统数据库多采纳火山模型执行引擎，每一个 Operator 都被实现为一个迭代器，提供三个接口：Initial、Get-Next、Closed，从上往下顺次调用。这种执行引擎的调用开销在基于磁盘的数据库管理系统中不占次要比重（磁盘 I / O 是最次要瓶颈），但在内存数据库里可能会形成瓶颈。假如要读取 100 万条记录，就须要调用 100 万次，性能会变得难以忍受，这就是内存数据库中大量采纳编译执行形式的起因。间接调用编译后的机器代码，不再须要运行时的解释和指针调用，性能会无效晋升。
- 可扩大的高性能索引构建：尽管内存数据库不从磁盘读数据，但日志仍然要写进磁盘，须要思考日志写速度跟不上的问题。能够缩小写日志的内容，例如把 undo 信息去掉，只写 redo 信息；只写数据但不写索引更新。如果数据库系统解体，从磁盘上加载数据后，能够采纳并发的形式从新建设索引。只有根底表在，索引就能够重建，在内存中重建索引的速度也比拟快。
— 本文小结 —
本篇次要介绍了基于磁盘的数据库管理系统与内存数据库管理系统在几个实现方面存在的次要异同，以及内存数据库从 1984 年开始到当初的技术倒退。前面会持续分享对于内存数据库技术的倒退，从数据组织、索引、并发管制、编译查问和长久化角度登程，介绍并比照几款支流内存数据库产品的实现技术。
注：本文局部资料来自于：
- VLDB 2016 会议上的古代主存数据库系统教程（Modern Main-Memory Database Systems Tutorial）
- CMU（卡耐基梅隆大学）Andy Pavlo 传授的高级数据库系统（Advanced Database Systems）课程