LMDB-B+树与MVCC

本文承接上一篇https://www.jianshu.com/p/6378082987ec。

LMDB中MVCC

当多个用户/进程/线程同时对数据库进行操作时，会出现3种冲突情形：

读-读，不存在任何问题
读-写，有隔离性问题，可能遇到脏读（会读到未提交的数据） ，幻影读等。
写-写，可能丢失更新

通常的读写操作中，我们常使用读写锁来进行对文件的并发操作。文件可支持多个读者，但一旦有写者参与进来，那么文件便需要加锁以便使文件的内容不会混乱。虽然这个解决了一致性的问题，但是却使得并发性很差。于是为了解决并发性问题，MVCC被提出。

MVCC（Multiversion concurrency control）有称为多版本并发控制技术，MVCC是数据库系统实现并发控制和一般系统中实现事务性内存控制的一种技术，主要用于并发控制，使用MVCC将读不会阻塞写，写不会阻塞读，只有两个线程写同一行数据可能导致冲突，因此可以提供最高的并发性。

对于数据库系统来说，若一个用户正在读数据的同时，另一个用户正在写同一个数据，则读用户可能读到写到一半的数据或者不一致的数据，因此数据库系统都会使用并发控制。最简单的方式就是写时阻塞所有读，这就是封锁技术。MVCC的方式是每个用户看到的数据是其连接上数据库时的快照，所有写操作对数据的改变其他数据库用户都不能看到，除非改变已经完成（即事务已提交）。

下面我们使用图来进行一下理解：

• 我们有数据V1，事务T1，此时事务T1改变数据V1，将其改为数据V2，如下图

image.png

• 此时T2还没有运行完成，而事务T3改变了V2，将其改为V3，在堆中，数据如下图：所以V1和V2属于recently dead状态，而不是真的dead状态。

事务T1提交后，事务T2启动，此时事务T3尚未启动，故T2可以看到T1提交后的数据V2。

image.png

• 事务T3提交后，事务T4启动，故T4只能看到数据V3。

image.png

当T0和T2都结束，已经没有事务在访问数据V1和V2了，此时V1和V2为dead状态，所以V1和V2都成为VACUUM的处理对象了。

即成为下图中灰色的部分。

image.png

MVCC在LMDB中的优缺点：

优点：

• 1 在并发读写数据库时，可以做到在读操作时不用阻塞写操作，写操作也不用阻塞读操作，提高了数据库并发读写的性能

PS：注意，MVCC的写写操作是需要在数据对象上加写锁的，因此对于同一数据对象的写写操作，MVCC也是串行执行的。下文中提到的大量写操作是指多个串行的写操作，由于写中夹杂着读，所以不得不创建非常多的副本给写。但每次只能进行一个写

• 由于实际业务中读操作事务数量要大于写操作事务，MVCC读写不冲突（不加锁），写写冲突（加做）的机制，能够提高读事务的执行性能，从而提高系统的整体性能。

适合读多、写少的情况。

缺点：

• MVCC的一个副作用就是对于存在大量写的应用，其数据版本很多，因此旧数据会占用大量空间（这个可以结合后面的append B+树来思考，增删改并不会在原来的位置进行，而是开辟新空间所以写与修改过多会带来很多额外开销）

解决方案： LMDB中通过freedb解决，即将不再使用的旧的数据页面空间插入到一颗b-Tree当中，这样旧空间在所有事务不再访问之后就可以被LMDB使用，从而避免了需要定期执行清理操作。

不适合写多的情况。

MVCC引发的一些问题与思考

乐观与悲观锁

数据库MVCC中，2个事务同时修改同一个数据，一个事务检查完没有别的事务对该数据的修改，准备commit。 在检查完和commit的这两个动作之间，第二个事务正好完成commit，此时，如何判断第一个事务能否提交？有办法无锁实现吗？

你可以想简单点，变量x，两个线程试图修改，一个想做x +=2；一个想做x+=1；

1. T1时刻，x=1
2. 线程A读到x=1，经过运算后试图将x改为3，此时A被系统调度走，排在cpu运行队列里面，所以此时A只是试图要把x改为3，实际还没做
3. 线程B起来后也读到了x=1，于是试图将x改为2，并且很幸运的直接改成功了，于是x现在的值是2
4. 线程A再被调度运行的时候，是否能将x直接改为3呢？不可以。因为按照串行之行的要求，无论是先A后B还是反过来，x的值都应该是4。
5. 问题变成A怎么办？这里就有两种基本思路

• 一个是悲观模式，即A在上面第二步开始加锁，避免任何人读写x，注意读也不行，除线程A外所有人不得操作x，一律等着，这样B起来后干瞪眼，拿不到x的锁就不会继续执行，于是x始终为1。等到轮到A执行的时候，x改为3；线程B如法炮制，先加锁再操作，最后x=4，结束。

• 一个是乐观模式，A不加锁，到了第5步修改x的时候要判断x的值是否是之前读到的值x，很快就会发现x已经被修改了，于是A放弃修改x并重新读x，加2，再做类似事情。

推广到事物是类似的，如果冲突严重也就是不同线程经常修改同一个变量，那么使用悲观模式，反之，乐观模式。

COW机制与LMDB中的B+树

cow为copy on write，MVCC的基础就是COW，对于不同的用户来说，若其在整个操作过程中不进行任何的数据改变，其就使用同一份数据即可，若需要进行改变，比如增加、删除、修改等，就需要在私有数据版本上进行，修改完成提交之后才给其他事务可见。

mdb_page_touch: 实现COW的技术，复制一个页面，并将更新过B-Tree指针关系的页面插入到B-Tree当中，这样意味着在修改时是在复制的页面上进行修改，别的事务在本事务没有提交之前看到还是以前的数据，提交之后的新事物看到的才是修改之后的数据。

LMDB在存储上使用的是B+树，而该B+树为append类型的。

传统的B+树如下图：

image.png

平面展开图为：

image.png

而append B+树：

以更新leaf 8为例，不能进行原地更新，需要新加入额外的节点（假如是leaf 12），并将数据copoy过去。这样的话，leaf8的所有父亲也需要进行同步的更新，与之同理，所有的父亲的指针无法原地修改，也需要新加入节点，并将数据copy一份。也就是说，会形成如下的B+树图：

image.png

更新操作最终都会转换为B+树的物理存储的append操作，文件不支持内部的修改，只支持append。

为什么要用append的这种形式呢？

因为需要让多个操作可以同时访问，在原来的基础上直接改不是很行。

优缺点如下：

优点：

• 1 旧的链路依然存在，依然可以正常的访问。

• 2 不在原来的位置做修改，方便了其余的进程对数据进行访问。

• 总体来说：在B树中，数据仅保留在叶节点中。B树仅将数据追加到将B树保留在磁盘上并且仅在末尾增长的数据库文件中。 新增文件？ 文件在末尾增长。 删除文件？ 该记录在文件末尾。 结果是一个健壮的数据库文件。 计算机由于多种原因而发生故障，例如断电或硬件故障。 由于不会覆盖任何现有数据，因此它无法破坏已写入并已提交到磁盘的任何内容。

缺点：

• 1 不可避免的增加了存储开销，因为旧的数据依然存在。

-2 旧数据可以复用，但是I/O成为了随机I/O。效率很低（虽然前面使用了dirty b+树，但是仍然使得这些块是随机的）。

• 写入次数很多

事务的基本特征

原子性（atomicity）。一个事务是一个不可分割的工作单位，事务中包括的诸操作要么都做，要么都不做。

一致性（consistency）。事务必须是使数据库从一个一致性状态变到另一个一致性状态。一致性与原子性是密切相关的。

隔离性（isolation）。一个事务的执行不能被其他事务干扰。即一个事务内部的操作及使用的数据对并发的其他事务是隔离的，并发执行的各个事务之间不能互相干扰。

持久性（durability）。持久性也称永久性（permanence），指一个事务一旦提交，它对数据库中数据的改变就应该是永久性的。接下来的其他操作或故障不应该对其有任何影响。

• 在 LMDB中通过游标进行操作，从而保障了统一刷新到磁盘中或者abort时都不提交。从而保障了原子性。

• LMDB中只能进行一个写操作，且原子性有保障的情况下肯定是一致的。

• 事务隔离通过锁控制（MUTEX），并且读与写操作使用的是私人版本，所以不会被其他事务干扰。

• LMDB中，没有使用WAL、undo/redo log等技术来保证系统崩溃时数据库的可用性，其保证数据持续可用的技术是COW技术和单线程写技术。假如LMDB或者系统崩溃时，只有读操作，那么数据本来就没有发生变化，因此数据将不可能遭到破坏。假如崩溃时，有一个线程在进行写操作，则只需要判断最后的页面号与成功提交到数据库中的页面号是否一致，若不一致则说明写操作没有完成，则最后一个事务写失败，数据在最后一个成功的页面前的是正确的，后续的属于崩溃事务的，不能用，这样就保证了数据只要序列化到磁盘则一定可用。

“重用旧页技术”可以帮助数据库恢复到上一个状态。