事务实现算法
2023-12-18 21:57:14 # 技术

私有工作空间

在概念上,当一个进程开始一个事务时,它被分配一个私有工作空间,该工作空间包含所有它有权访问的文件。在事务提交或中止前,它的所有读写操作都在私有空间内进行,而不是直接对文件系统进行操作。这就直接导致了第一种实现方法的产生;在进程开始一个事务的时刻,实际上为该进程分配了一个私有工作空间。

此技术带来的问题是把所有的东西都复制到私有工作空间的开销是十分大的,但是各种各样的优化方法使这种方法可行。

第一种优化方法是基于这样的认识,即当一个进程只读取一个文件而不对它做修改时,就不需要私有拷贝。该进程可以直接使用真正的文件(除非自事务开始以来文件已被改动)。因此,当进程开始一个事务时,就为它创建一个私有的工作空间,该空间是空的,除非当一个指针回指到它的父辈工作空间。当进程为了读取而打开文件时,指针将回指,直到可以在父辈(或者更老的祖先)工作空间中找到文件为止。

第二种优化方法可以大大减少复制工作量。因为它不是复制整个文件,而是只将索引复制到私有工作空间。索引是与判断文件所在磁盘块位置有关的数据块。在UNIX系统中,索引是$i$节点(index node,即索引节点)。通过私有索引,文件可以按通常方式读取,这是因为索引中所包含的地址指向的是文件所在的原始磁盘块。然而,当一个文件块第一次被修改时,将生成该块的副本,其地址也被插入索引中(如下图所示)。然后就可以在不影响原始块的情况下更新这个块。添加块也是用这种方法解决。新块有时会被称为影像块。(这是一种写时复制技术,即copy-on- write)

写时复制.drawio

在上图中,运行事务的进程看到了修改的文件,但是其他所有进程看到的仍是原始的文件。在更复杂的事务中,私有工作空间可能包含大量的文件而不仅仅是一个。如果事务中止,私有工作空间就被简单的删除,它所指向的私有块也将被释放回自由列表(free list)中。如果事务被提交了,那么私有索引被移到父辈工作空间中。

写前日志

另一个实现事务的常用方法是写前日志(write ahead log,WAL)。使用这种方法时,文件将真正被修改,但是在任何一个数据块被修改前,一条记录被写到了日志中以说明哪个事务正在对文件进行修改,哪个文件和哪个数据块被改动了,旧值和新值是什么。只有当日志被写入成功后,此改动才可以被写入文件。

如果事务执行成功并被提交,那么一条提交记录被写进日志,但是数据结构不需要变动,这是因为它们已经被更新了。如果事务中止,那么可以使用日志来回退到原来的状态。从日志的末尾开始向前读取每条记录,同时将在每条记录中描述的改动撤销(这也被称为「回退」或「回滚」,也即rollback)。

注:本文内容摘自「分布式系统原理与范型」,供本人学习回顾使用。