自己动手写数据库:并发管理的基本原理

一个好的数据库，其特点必然是吞吐量高，也就是它能在高并发请求压力下保证数据的准确性和安全性，由此并发管理是不可或缺的一环。事实上并发管理是一个相当复杂的计算机科学领域的课题，它几乎可以自成一格领域，是能够与操作系统，编译原理比肩，完全可以成为计算机科学中的支柱性存在，因此它自身也有着丰富且复杂的理论基础，在这里我们就接触一下它的皮毛。

在前面章节中，我们提到一个叫”交易“或者是”事务“的概念，事实上它本质是一组提交给数据库系统的命令，这些命令依次执行以便完成一个具体的目标。我们需要在对”交易“进行逻辑上的描述，这样我们才有思考的材料。第一种描述方法是详细描述其读写过程，例如记录它一次读取了哪个数据，写入哪个数据，例子如下：

tx1:  setInt(blk, 80, 1, false)
        setString(blk, 40, "one", false)

tx2:  getInt(blk, 80);
        getString(blk, 40);
        setInt(blk, 80, newival, true);
        setString(blk, 40, newsval, true);

第二种描述方法是对对第一种方法的简化，它仅仅描述对特定区块的读写操作，例如：

tx1:  W(blk1);  W(blk2);
tx2: R(blk1);  R(blk2); W(blk3); W(blk4);

第二种方法仅仅记录在特定区块上的操作，同时忽略具体的操作内容。所谓”交易“实际上就是两种方式所描述的操作的集合。在思考并发管理时，我们需要想象程序给数据库系统提交了一系列的命令，如果程序提交的命令能依次运行, 例如下面：

这种情况不难处理，数据库系统依次执行给定命令即可，但是下面的情况就麻烦了：

上面的情况是，两个交易同时将同一个区块的写命令提交给数据库，那么后者该执行哪个命令先，不同的执行次序就会导致不同的数据结果。所谓并发管理就是一种如何处理情况2的方法，它要求对同时抵达的处理命令进行调度或安排，使得执行命令在执行后得到某种特定的结果。

当我们面临情况2时会产生一种模糊，那就是如何定义”正确“，我们到底是先值程序1的请求还是现执行程序2的请求，不同的选择会导致不同的结果，那么哪种结果可以是认为“正确”呢，我们这里需要建立一种客观条件来判断结果的正确性。由此我们回到情况1，也就是假想所有交易的步骤都是单独无干扰的进行，也就是假设当一个交易启动时，它向数据库发送命令期间没有其他交易在进行，也就是我们设想当一个交易启动后，它会独占整个数据库。也就是数据库每次只执行一个交易的命令，当它把当前交易的命令全部执行完毕后才去执行另一个交易的命令，于是当程序1和程序2 同时向数据库发送交易命令时，假设数据库把程序2的命令请求全部缓存起来，一直到程序1的交易完成后再依次执行程序2的交易命令，我们把这种调度叫做序列调度。

在序列调度的前提下我们可以定义”正确性“，假设我们有两个交易：

T1: W(b1)，W(b2)
T2:W(b1)，W(b2)

假设T1在执行W(b1)时，它写入的数据是X, T2在执行W(b1)时写入Y,那么哪个交易先调度所得结果就会不同，如果先调度T1，那么两个交易执行完毕，区块b1包含的数据就是Y,如果先调度T2,那么b1包含的结果就是X，那么哪一种才“正确”呢，这里我们认为哪一种结果都正确，只要调度遵守了序列原则，那么所得结果就都是正确的，因此无论是先单独执行T1的命令还是先单独执行T2的命令，所得结果可以认为是正确。

因此当同时有多个不同交易的命令提交给数据库时，数据库执行这些命令的次序后只要能实现”序列化”的结果，那么我们认为调到就是正确的。我们看个具体例子，假设数据库在同一时刻接收来自两个交易的多个命令，然后它将命令的执行次序安排如下：

W1(b1); W2(b1); W1(b2); W2(b2);

其中W1(b1)表示交易1要求写入区块b1。这个调度所得结果跟先单独执行交易1的所有命令，然后再单独执行交易2的所有命令，其结果一致，也就是说上面的命令执行次序所得效果就好像交易1独占了数据库，然后交易2独占了数据库一样。当数据库将同时抵达的交易命令进行排列执行，所得的结果就好像每个交易独占数据库运行后的结果，那么这样的调到方法就定义为“正确”.

我们看看所谓“错误”的情形，假设数据库在同一时刻接收到两个交易如上所述的读写命令，然后它把这些命令的执行次序安排如下：

W1(b1); W2(b1); W2(b2); W1(b2)

我们看到这种执行结果导致最终区块b1包含交易2写入的数据，区块b2包含交易1写入的次序。如果按照“序列化”执行，也就是先全部执行完交易1然后再执行交易2，那么所得结果就是b1,b2都包含交易2写入的数据，或者是先全部执行完交易2，再执行交易1，那么所得结果就是b1,b2包含交易1写入数据，无论那种情况都不可能出现b1,b2包含来自不同交易写入数据的情形，因此我们定义上面的调度是“非序列化”的，因此是错误的。

要实现可序列化的调度，我们就需要通过“加锁”来完成，我们引入两种锁，一种是共享锁，一种是互斥锁，如果某个交易在给定区块上实施了互斥锁，那么其他交易就不能在对上锁的区块进行任何操作；如果讴歌交易在给定区块删实施了共享锁，那么其交易就可以对给定区块进行读操作，但不能执行写操作，我们先定义锁的接口如下：

type LockTableInterface interface {
	SLock(blk *fm.BlockId)  //增加共享锁
	XLock(blk *fm.BlockId)  //增加互斥锁
	UnLock(blk *fm.BlockId) //解除锁
}

当代码执行XLock时，如果给定区块已经被加锁，无论加的是共享锁还是互斥或，那么调用都会阻塞，并等到给定锁被释放后才能继续执行。我们看看为何加锁能实现调度的序列化，假设我们有如下两个交易的操作:

T1: R1(b1), W1(b2)
T2:W2(b1), W2(b2)

由于两个交易都要写入区块b2，那么哪个交易最后写入就会影响系统数据的最终结果。这种因为调度次序而导致不同结果的情形，我们称之为冲突操作。这里我们看到产生冲突的是两个写操作，因此他们也叫写-写冲突，还有一种冲突叫读-写冲突，例如{R1(b1), W2(b1)}，因为先执行W2(b1)和先执行R1(b1)，都会导致T1读到不同的数据，由此冲突只会发生在读-写，和写-写操作上，而且需要这些操作作用在同一个区块。

冲突操作的处理决定了序列化调度，对于冲突操作{R1(b1), W2(b1)}，如果是W2(b1)先执行，那在逻辑上相当于数据库先单独执行了交易T2，然后再执行交易T1，如果T1,T2的操作命令同时抵达数据库，那么数据库要确保在面对冲突操作时，要确保总是先执行T1的操作，或者是先执行T2的操作。数据库决不能在第一次冲突操作中选择T1，然后在第二次冲突操作中选择T2。

数据库要确保面对冲突操作时，它每次总能优先选择同一个交易的操作，那么它可以使用如下加锁协议：

1，在读取区块前，先获取针对区块的共享锁。
2，在修改一个区块时，先获取针对它的互斥锁
3，在执行commit,或者rollback操作后释放对应的锁

从上面协议步骤我们可以得到一点要点。首先当交易1在给定区块上获得共享锁时，交易2就不能修改给定区块的内容，如果交易2能写入区块，那意味着根据加锁协议交易2已经获得了互斥锁，于是交易1就不能获得共享锁，于是它就不能读取数据，于是{读-写}冲突就解决了。第二，如果某个交易获得了给定区块上的互斥锁，那么所有其他交易都不能读取或写入该区块。这两点就能保证一个交易的第n个步骤不会跟其他交易前n-1个步骤相冲突。

但这样又带来一个问题，那就是交易必须在完成所有操作后才能释放所有获得的锁，例如交易1在第一步时针对区块1获得互斥锁，假设它总共有100步操作，那么它必须在完成全部100步操作后才能释放第一步获得的锁，要不然问题还是会出现，因为假设交易2只有1步，那就是写入区块1，于是如果交易1释放区块1的锁后，交易2里面得到锁，然后执行写入区块1，如果交易1只有在第一步写入区块1，那么当它完成后，区块1包含的是交易2写入的数据，这样就破坏了序列化原则。但是将锁持有到交易所有步骤完成又会严重影响效率，因此我们又得想办法解决这个问题。

加锁是一个比较复杂的问题，操作不当会引发很多错误，特别是在并发或多线程的情况下。我们用UL(x)表示对区块x解锁，SL(y)表示对区块y加锁共享锁，我们看下面一个例子：
T1:

T1: ...  R(x), UL(x), SL(y) ,R(y),....

假设交易T1执行的线程在解锁区块x和加锁区块y之间被中断，这时T1的序列化就很容易被破坏，如果此时执行交易T2的线程在R(x),SL(y)中间插进来，同时对x和y加锁，然后将数据写入这两个区块，然后执行commit操作，使得写入x,y区块的数据被写入磁盘，这样T1的数据完整性就被破坏，这样T1的执行就不再满足序列化的要求，因为它访问过的区块所包含的数据并非由他所创建，因此在多线程，高并发的情况下，一个交易必须要在它所有操作完成后才能释放它所获得的所有锁，这种情况也叫“两阶段锁”，第一阶段就是专门获取锁，第二阶段就是专门释放锁，很显然这种情形对效率是一种致命影响。

一旦获得锁就需要在所有操作完成后才能释放，要不然我们还会面临读取“未提交数据”问题。假设两个交易同时给数据库提交了一系列操作请求：

W1(b), UL1(b), SL2(b), R2(b)...

在这个过程中交易1先对区块b加锁，然后写入区块b，接着解锁区块b, 很快交易2又对区块b进行加锁，然后读取区块b的数据，这里有个问题在于交易2读取区块b时，交易1没有执行commit操作，当交易2读取区块b的数据后，如果交易1执行rollback操作，那意味着区块2包含的是过时或是无效数据，于是交易2就只能同样要执行rollback操作，这意味着一切由交易2写入的数据都会变得过时，于是其他那些读取了交易2写入区块的其他交易同样也得执行rollback操作，这个过程会链式进行下去，由此产生所谓"cascading rollback"问题。

除了数据一致性问题，在并发下加锁还容易产生死锁问题。假设两交易的命令执行次序如下：

T1:  W(b1),  W(b2)
T2:  W(b2),  W(b1)

假设T1先对区块b1加锁，如果此时T1执行的线程被挂起，T2的线程执行，然后它对b2加锁，这样就形成了死锁。要判断出这种情形的死锁，我们需要借助”等待图“数据结构，节点表示交易，如果T1要获取一个被T2加锁的区块b，那么节点T1就会有一个路径指向节点T2，因此上面死锁可以用下面的有向图表示：

不难看出当加锁图出现环时意味着死锁出现。但是加锁图也有不足之处，那就是要交易数量变多，或者要加锁的对象变多，加锁图就不好使，例如：

T1: xlock(b1);  pin(b4);
T2: pin(b2);  pin(b3);  xlock(b1);

假设缓冲区池只能容纳两个区块，交易1在执行xlock(b1)后它所在线程被中断，同时T1在缓冲池中引用了b2, b3,这时候它必须等待T1释放掉b1的锁才能继续执行，同时由于T2引用了两个区块后，缓冲池的容量全部被占据，当T1恢复后他想引用b4，但是此时缓冲池已经满了，没有内存片可以将b4对应的数据读入内存，于是T1也陷入等待，这就形成了死锁，这种情况是加锁图无法描述的。

通过以上描述，我们可以替换到并发管理的复杂性。为了处理复杂的并发问题，业界采用了两种应对策略，一种叫wait-die, 它的基本逻辑如下：

假设T1请求的资源已经被T2加锁占据，那么根据以下条件处理：
if 如果T1比T2老，那么T1继续等待(wait)
else T1 执行rollback操作(die)

这种策略使得在加锁图中，只有老的交易会生成指向年轻交易的箭头，因此不会产生环，于是死锁不会产生。

第二种策略是，如果交易管理器发现某个交易等待时间过长，那么它默认死锁发生，于是对等待的交易执行rollback操作，其逻辑如下：

1，T1 等待获取锁
2，如果T1等待超过给定时间，那么T1执行rollback操作

无论那种策略并发管理器都必须让某个交易执行回滚操作。除了区块的读取有并发问题，文件处理也会有，在前面章节中，文件管理器有size和append接口，这两个操作就会有并发冲突，如果T1调用文件管理器的append接口，T2调用size接口，那么调度必须要让T1在T2之前执行。关于文件的并发冲突有一种情况叫phantom problem，假设T2在循环中读取整个文件的内容，在读取文件前先调用size获取文件的区块数，假设在第一次循环T2读取了文件所有内容，此时T1所在的线程执行，然后T1往文件中加入若干区块，那么T2在第二次读取文件时会意外的发现文件凭空多了一些内容，这些内容对应T2来说是一种“幻影”(phantom)，这就会破坏“交易执行时就好像只有它一个在执行”这个原则。

我们前面描述的加锁协议在这种情况就不适用，因为加锁只能针对已经存在的区块，而T1创建的是新区块，于是T2根本不能对它在运行时还没有存在的区块加锁。解决办法是对文件末尾加锁，在实现上我们针对文件专门创建一把互斥锁，当执行append或size时都需要先获得这把锁。

好在对于数据库应用，最常见的操作是读而不是写，因为读操作获取的是共享锁，因此多个读操作可以并发执行。但假设我们有100个交易，其中99个交易只执行读操作，但第100个交易要执行写操作，如果包含写操作的交易先执行，那么那99个只读交易就必须全部暂停，等待第100个交易完成后才能执行，这么看来成本就很高。这种情况在数据库系统中很常见，于是就有了一种策略交易多版本加锁。

多版本加锁就是对每个区块赋予不同版本的锁，其基本思路如下：
1，每个区块会对应多个不同版本的锁，每个锁都有一个时间戳，这个时间戳在交易执行commit操作时会创建。
2，当一个只读交易要从一个区块读取数据时，交易管理器会将该交易启动前就执行了commit命令的交易写入的内容返回。

我们看一个具体例子，假设我们有如下交易：

T1: W(b1); W(b2);
T2: W(b1); W(b2);
T3: R(b1); R(b2);
T4: W(b2)

假设它们同时将操作提交给数据库，后者调度执行命令的次序如下：

W1(b1), W1(b2), COMMIT1,  W2(b1), R3(b1); W4(b2), COMMIT4, R3(b2), COMMIT3, W2(b1), COMMIT2

我们把区块写入的情况根据时间点做如下假设

b1 : time= 3, T1将数据写入；  time = 11 T2将数据写入
b2:  time = 3, T1将数据写入； time = 7 T4将数据写入；time=11 T2将数据写入

由于交易1执行commit命令时，区块b1,b2都被写入数据，因此在对b1,b2加锁时，锁对应的时间戳就是COMMIT1执行的时间，假设每个操作耗时1个时间单位，那么COMMIT1是第三个操作，于是它时间点是3，因此b1,b2两个区块对应的时间戳就是3，以此类推。对于T3而言它是只读交易，同时它对应的R(b1)在序列中排第5，此时虽然交易2在它之前写入了数据，但是区块b1对应时间戳为3，因此R3(b1)读取的数据以时间戳为准，因此数据库在执行R3(b1)时返回的是W1(b1)写入的数据而不是W2(b1)写入的数据。

当执行R3(b2)时，距离它最近的写入是W4(b2)，并且T4也执行了commit命令，但commit命令并不是在T3启动前就执行，在T3启动前执行COMMIT命令的是T1，因此数据库返回给R3(b2)的数据是由T1执行W1(b2)时写入的数据，而不是W4(b2)写入的数据，因此COMMIT4的执行并不在R3启动前。

这种做法的好处在于，读操作不需要再获取锁，于是能大大加快读的效率。于是数据的写入和读取就不再发生冲突。因为读取的数据取决于对应交易的起始时间，与数据的写入次序再无关系。在后面我们实现并发管理器时将采用多版本加锁的策略。

我们可以基于日志机制来实现多版本加锁。当一个交易执行commit操作时，我们给这个交易所有写操作都对应一个时间戳，也就是当commit操作执行时，并发管理器对每个被写入的区块进行pin操作，将时间戳写在这个区块的开头，然后再执行unpin操作。交易管理器使用日志来实现区块的读命令，它通过undo所有在时间t之前对区块的写入操作来获得对应版本的数据。

我们需要回忆一下前面的日志内容以便更好掌握多版本加锁的实现。在实现恢复管理器时我们曾经有一个checkpoint日志，这条日志意味着在这条日志之前所有的写入操作所对应的交易要么已经执行了commit操作，要么写入的内容已经从内存写入到了磁盘。并发管理器在执行读请求时需要依赖日志，特别是日志中的checkpoint 和 commit这两种记录。

假设一个交易的起始时间是t, 它要读取区块b，那么并发管理器需要做如下操作：
1， 他将当前区块b的数据拷贝到一个新的内存页
2，它逆向读取日志三次，第一次它构建一个列表用来记录在时间t之后才执行commit的交易，这个过程在它遇到第一个commit时间早于t的交易时停止。第二次用于构建一个队列用于记录那些没有执行commit或rollback的交易，直到遇到checkpoint记录时就停止，第三次再次逆向读取日志，当遇到写操作，并且执行写操作的交易在第一次或第二次构建的队列中时，执行undo操作，第三步一直执行，直到遇到两个列表中，最早那个交易产生的start 记录为止。

这些步骤的执行，目的在于undo掉那些在时间t时还没有执行commit的交易写入区块b的数据。另外在实现时，交易必须要向并发管理器表明自己是否是只读交易，我们通过一个接口或者标志位来设定。

加锁是一个很影响效率的操作，而多版本锁可以让只读交易的执行效率大大加快，因为它不用因为锁而等待或挂起，但是多版本锁的缺点在于实现复杂，而且需要多次读写磁盘，因为要读取日志，另外对于有写操作的交易而言，还是要面临加锁导致的各种问题。

下一节我们看看怎么实现我们这节所描述的算法。视频讲解请在b站搜索Coding迪斯尼。