Anatomy of a Database System学习笔记 - 事务：并发控制与恢复

这一章看起来是讲存储引擎的。
作者抱怨数据库被黑为“monolithic”、不可拆分为可复用的组件；但是实际上除了事务存储引擎管理模块，其他模块入解析器、重写引擎、优化器、执行器、访问方式都是代码相对独立的，他们提供窄接口(宽接口功能强大如Socket，窄接口单一职责入TcpListener)给其他模块调用。
存储引擎一般有以下四个深深纠缠的组件：
1. A lock manager，并发控制
2. A log manager，恢复
3. A buffer pool，数据库I/O分段处理
4. Access methods. 组织磁盘上数据
这篇将不关注算法，概述上述不同组件的角色，重点关注教科书中经常忽略的系统基础设施，并强调组件之间的相互依赖关系。

概念

Atomicity：锁(可见性)+日志(正确性)

Consistency：查询执行器的检查（如果事务违反SQL完整性约束，则放弃并返回异常）

Isolation：锁

Durability：日志

可序列化：多个提交事务的交错操作序列必须对应于事务的某些串行执行。商业关系数据库都通过严格的两阶段锁（2pl）来实现可序列化：事务在读取或写入对象之前获取对象锁，并在事务提交或中止时释放所有锁。锁管理器是实现2pl的代码模块，作为助，还提供了轻量级的锁（闩/latch），以提供互斥。

锁：数据库锁(lock)只是系统中约定用来表示DBMS管理的物理项(例如磁盘页)或逻辑项(例如元组、文件、卷)的名称。任何名称都可以有一个与之关联的锁，即使该名称表示一个抽象概念。锁机制(lock mechanism)只是提供了一个注册和检查这些名称的位置。锁有不同的锁“模式”，这些模式与锁模式兼容表相关联。在大多数系统中，锁模式就是遵从Gray锁粒度论文里的锁模式。

锁管理器和闩

锁管理器支持以下API：

	必备	描述
lock(lockname, transaction_id, mode)	Y
remove_transaction(transaction_id)	Y	实现2PL,解锁transaction_id对应的所有资源
unlock(lockname, transaction_id)	N	实现低于serializable的一致性要求
lock_upgrade(lockname, transaction_id, newmode)	N	提升锁级别，不需要先释放锁再获得锁，如共享锁提升到排他锁
conditional_lock(lockname, transaction_id, mode)	N	不阻塞的返回锁是否获取成功，用于索引并发情况

为支持以上方法，锁管理器维护以下各种功能数据结构：
1. 全局锁表是Key=lockname的动态哈希表，value包含：current_mode锁模式、waitqueue等待锁的pair<transaction_id,mode>队列。
2. 事务表是key=transaction_id的表，value包含：一个事务线程状态指针用于获得锁后调度线程、一个事务所有锁请求的指针列表用于(commit/abort时)移除这个事务涉及的所有的锁。

论文外的东西：MySQL锁数据结构

/** Lock struct; protected by lock_sys->mutex */ struct lock_t { trx_t* trx; /*!< transaction owning the lock */ UT_LIST_NODE_T(lock_t) trx_locks; /*!< list of the locks of the transaction */ dict_index_t* index; /*!< index for a record lock */ 数据行和索引，都是索引 lock_t* hash; /*!< hash chain node for a record 　　　　　　　　lock. The link node in a singly linked 　　　　　　　　list, used during hashing. */ union {//详细信息 　　lock_table_t tab_lock;/*!< table lock */ 行锁这里为空 　　lock_rec_t rec_lock;/*!< record lock */ 哪个页、哪个行。表锁这里为空 } un_member; /*!< lock details */ ib_uint32_t type_mode; /*!< lock type, mode, LOCK_GAP or 　　　　　　　　　　　　LOCK_REC_NOT_GAP, 　　　　　　　　　　　　LOCK_INSERT_INTENTION, 　　　　　　　　　　　　wait flag, ORed */ ………………………………… }

锁管理器配备有死锁检测线程，定期检查锁表以便发现waits-for循环。当检测到死锁，如何决定终止哪个事务呢？读论文。shared-nothing系统和shared-disk系统中，分布式死锁检测机制如何实现呢？读Gray和Reuter合作的论文。

从上述数据结构可以看出锁比较笨重，相对于锁、闩很轻量级了。

latch闩不太像锁，而像是监视器：提供对内部数据结构的独占访问。例如，缓冲区页表有一个与每个帧关联的闩，以保证每时刻只有一个线程替换给定的帧。闩与锁的区别如下：
1. 锁存存放在锁表里、通过哈希表进行访问；闩存放在他们所闩住的资源附近、通过地址直接访问。
2. 锁服从2PL协议，闩由事务期间的特殊逻辑acquire/drop。
3. 锁的获得完全由数据访问驱动，因此顺序和生命周期取决于应用程序和查询优化器；闩是由DBMS内部的专门代码获得的，生命周期取决于代码策略。
4. 锁允许产生死锁、检测到死锁后通过重启事务来解决死锁；闩禁止产生死锁，如果有latch deadlock，说明数据库系统有bug。
5. 锁请求需要消耗上百个CPU循环；闩请求需要少数几个CPU循环。
闩的API主要有3个：latch(obj, mode),unlatch(obj),conditional_latch(obj, mode)。mode分为Shared共享和eXclusive排他。Latch对象包含current_mode和waitqueue线程队列。

ANSI SQL标准的4种隔离级别和3种附加隔离级别

隔离级别是事务发展中一个古老的概念，为支持更多并发、需要提供比串行化更弱的语义，其中影响力最大的是Gary在早年的《Degrees of Consistency》论文中提出的清晰的隔离级别定义和锁的实现。受gary作品的影响，ANSI SQL标准规定了以下4个隔离级别：

1. READ UNCOMMITTED：事务可以读到任何版本的数据，包括未提交的数据。这种隔离级别根据ARIES论文可由read请求不需要获取任何锁达到。
2. READ COMMITTED：事务可以读到任何版本的已提交数据，重复读一个对象可能获得不同的值(这个对象commit了多次的话)。这种隔离基本根据ARIES论文可由read请求需要获得读锁、但是读到数据后又立即释放读锁实现。
3. REPEATABLE READ：事务只能读到已提交的信息，而且以后读到的都和第一次读到的一样。这种隔离级别根据ARIES论文可由read请求访问数据前需要获得读锁、且这个锁一直到事务结束才释放而实现。
4. SERIALIZABLE：全序列化访问。

为什么说RR不是全序列化的呢？因为有幻读问题。幻读是事务按照某个谓词重新访问的时候，读到了第一次访问时候没有读到的新的元组。这是因为元组粒度上的2pl并不阻止将新元组插入到表中。表粒度的2PL可以防止出现幻读，但在事务仅通过索引访问几个元组的情况下，表级锁可能会受到限制。

论文外的思考：MySQL四种隔离级别像ARIES论文讲的那样通过读锁去实现吗？

- no. MySQL的查询通过MVCC快照去控制，是没有读锁的，具体实现方法如下：

读-不加锁

写-大部分是X，极端情况下有S

隔离级别实现-

void ha_innobase::unlock_row(void) /*=========================*/ { …………………………………………………… ……………………………………………………. switch (m_prebuilt->row_read_type) { case ROW_READ_WITH_LOCKS: if (!srv_locks_unsafe_for_binlog && m_prebuilt->trx->isolation_level > TRX_ISO_READ_COMMITTED) {//RR或serilizable，不释放 break; } /* fall through */ case ROW_READ_TRY_SEMI_CONSISTENT: row_unlock_for_mysql(m_prebuilt, FALSE); break; case ROW_READ_DID_SEMI_CONSISTENT: m_prebuilt->row_read_type = ROW_READ_TRY_SEMI_CONSISTENT; break; } DBUG_VOID_RETURN; }

论文外的思考：buffer_pool%read_ahead是什么？？为什么我的db是0？

-undone

以上四种级别中，写锁都是直到事务结束才释放的。商业数据库通过基于锁的并发控制来提供以上四种级别的隔离机制，但是有思潮认为Gray/ANSI的标准并不清晰：它们以微妙的方式依赖于一个假设，即并发控制基于锁来实现，而不是乐观的或多版本并发方案，因此这两种提议的语义定义不明确（可参见Berenson、Adya的文章）。很多供应商在四种隔离级别之上提供了附加级别，流行的附加级别有：

1. CURSOR STABILITY游标稳定性，DB2默认隔离级别。解决READ COMMITTED里丢失更新丢失问题，所以说它可以防止脏读，但是不能防止不可重复读和幻读。举例说明更新丢失问题：T1以RC级别运行，需要读X并将X=X+100写入原账户。T2也需要读X并写X=X-300到原账户。如果T2发生在T1的读和T1的写之间，那么T2的更新效果会丢失。CURSOR STABLITY对READ COMMITTED的补充是，锁定事务声明并打开的游标当前所引用的行，该锁持续到指针丢失(如另起一个查询)或事务终止，这样事务可以对单条记录进行read-think-write而不影响其他事务的更新。此外，CS像RC一样，如果事务修改了它检索到的任何行，那么在事务终止之前，其他事务不能更新或删除该行，即使游标不再位于被修改的行。
2. SNAPSHOT ISOLATION隔离快照，最初是Hal Berenson 1995年提出，MySQL、MongoDB、TiDB、OceanBase都实现SI。SI可以看作“乐观锁”，以SI模式运行的事务在事务开始时的数据库版本上运行;其他事务的后续更新对事务是不可见的。当事务开始时，它从一个单调递增的计数器获得一个惟一的启动时间戳；提交时从计数器获得一个惟一的结束时间戳。只有当没有其他具有重叠的start/end-transaction pair的事务写入了该事务也写入的数据时，该事务才提交。这种隔离模式依赖于多版本并发实现，而不是锁(尽管锁通常共存于支持SI的系统中)。
3. READ CONSISTENCY一致性读，Oracle最先提出，与SNAPSHTO ISOLATION略微不同。每个SQL语句(在一个事务中可能有很多SQL语句)在语句开始时都看到最近提交的值。对于从游标获取的语句，游标集基于打开时的值。这是通过维护单个元组的多个版本来实现的，一个事务可能引用单个元组的多个版本。修改是通过长期写锁来维护的，因此当两个事务想要写相同的对象时，第一个写者“赢”，而在SI中，第一个提交者“赢”。

弱一致性使系统可以有更高并发，因此很多系统使用弱一致性作为默认隔离级别。例如，Oracle默认是Read Committed。这就要求应用程序开发者需要考虑方案的细节，以便保证事务正确运行。

论文外的问题：为什么MySQL对一条记录的DIU操作时间上是update>delete>insert

-insert无row_search_mvcc查找，不加锁的插入（极端情况如排他锁、间隙锁需要加waiting锁）。

-update被拆成delete和insert：

　　1. 无索引或者索引字段被修改（需要维护二级索引一致性），需要通过全表扫描(锁表IS)找数据，

　　　　如果隔离级别是rr，则所有行上有x锁；

如果隔离级别是rc，则扫完后非命中记录上x锁被释放，故只有命中的记录上有x锁。

　　2. 含有索引（非主键）的非索引字段被修改，需要锁索引然后查找数据。

如果隔离级别是rr，命中的数据记录（b lock_rec_lock thread #； p index->name=primary）有x锁(mode=3)，被命中的记录的最后一行的nextkey（如index=6的下一行index=9）上有间隙锁（mode=3+512），被命中的索引上有锁(b lock_rec_lock, 可发现p index->name=idx_xxx)；record锁个数是2*命中row+1；查找顺序是先找索引，再找表。

如果隔离级别是rc，有x锁（mode=1027），record锁个数为2*row。

　　　　加锁顺序是idx->pri->idx->prx..->gap

　　3. 含有索引的索引字段被修改，需要按照索引查找数据（锁索引x），然后把所有（如果有筛选条件，筛选）记录（锁数据行x）按主键新建临时表（执行计划中的索引列要被修改，就会有之前谈到的圣诞日问题），之后从临时文件找数据，最后修改（b row_upd_clust_step ; b row_upd_sec_step）。

-delete：

　　1. 基于主键删除。首先按照主键查找（primary加锁），然后b row_upd_clust_step 行头设置为delete标签，然后idx加impl锁（隐含锁），然后打delete标签。整个sql只有一个record锁。

　　2. 基于索引删除。

　　rr：idx->pri->idx->pri...->idx_nextkey     2*n+1

rc：idx->pri->idx->pri...　　　　　　　　2*n

论文外的问题：为什么MySQL不同session间更新/插入/删除不同的行，却产生锁等待或者死锁？

-undone

日志管理

日志管理负责维持已提交事务的持久性、以及协助事务回滚以支持原子性。日志管理通过维护磁盘上的日志记录序列、内存里的数据结构来实现以上功能，很明显内存中数据结构需要能从持久化的日志和数据库中重新创建，才能在数据库crash后保证行为正常。
数据库日志复杂又面向细节，所以需要熟读期刊论文ARIES。这篇论文是数据库日志管理的规范参考文献，讨论了协议、其他设计可能性、其他设计可能导致的问题；如果论文难度太高，可看Ramakrishnan/Gehrke的教科书。下文只讨论recovery的基础概念。

数据库恢复的标准协议是Write-Ahead Logging(WAL预写式日志)，WAL3个基本原则是：

1. 数据库页的修改需要先写日志，日志刷盘后数据库页才能刷盘。
2. 数据库日志必须按照顺序来刷盘，也就是说日志记录r必须等到r以前的所有记录刷盘后，才能刷盘。
3. 对于事务提交请求，COMMIT日志记录刷盘后，commit请求才能返回成功。

大多数人只记得第1条原则，但是要3条原则一起生效才能保证数据库正确性。原则1保证未提交事务可以回滚--原子性；原则2+原则3保证crash后已提交但未刷盘的事务能redone -- 持久性。

WAL原则说起来很简单，实现起来却很复杂，因为数据库有性能要求：保证事务快速提交、保证快速回滚、保证快速crash recovery。对于特殊业务(如事务只能增加增加/减小某字段)的支持导致系统更不规整。下面简要说明：
1. 为保证快速提交，现代商业数据库以Härder 和 Reuter的“DIRECT, STEAL/NOT-FORCE”模式运行：

a) DIRECT：data objects are updated in place
b) STEAL：unpined缓冲池帧可以被“steal”偷走(然后修改后的缓冲页要被写回到磁盘)，即使缓冲页里包含未提交事务。
c) NOT-FORCE：事务commit结果返回给用户前，缓冲页不能被“force”强行刷盘到数据库。

这种模式使缓冲区管理和磁盘调度程序不需要考虑事务正确性，带来很大的性能优势，但是要求日志管理器高效的处理被偷页面的undo问题和不被forec页面的redo问题。

2. 为了保证日志记录尽可能小，以主动增加I/O吞吐，日志一般采用逻辑记录("insert (bob, $25000) into EMP")而不是物理记录(插入元组后的物理变化，如堆文件、索引块变更)。这样的好处是redo和undo逻辑操作变得很清晰，但是事务abort或数据库恢复性能变差。为此，提出了一种结合了“physiological logging”，在ARIES论文里雾里日志用于支持REDO，逻辑日志用于支持UNDO。逻辑记录也需要有对应的逆方法。

3. checkpoints机制可提高crash recovery性能，checkpoint使恢复程序只需要读有限的日志。严格的checkpoint生成性能消耗严重，于是使用模糊的checkpoing，这需要数据库考虑如何用最少日志保证正确的找到最近的一致状态检查点。ARIES论文里检查点记录非常小，仅包含供日志分析程序初始化、重建crash丢失的主存数据结构所需的最少信息。

4. 数据库不仅仅是磁盘页上用户数据元组的集合，也包含供数据库管理内部磁盘数据的各种物理信息，这使写日志和恢复更佳复杂。

针对索引的锁和日志

索引并发性和恢复需要保留的惟一不变条件是，索引总是从数据库返回事务一致的元组。

B+树闩用于支持并发
对于索引的修改往往是改了bufferpool页导致的，因此索引的并发控制策略中最直观的一种策略是两阶段锁。这种策略要求每次事务修改索引前都要锁住B+树的根、直到事务提交，这样策略的并发太差了。为了保证并发事务一直找到正确的叶子结点、又不给索引页加上事务锁，主要有3个基于闩的方案：
1. 保守方案。允许多个事务在能保证不冲突的情况下同时访问页面，这种冲突可能是“一个想要遍历索引页内树的事务，会与一个插入数据的事务”。保守方法牺牲了太多并发性。
2. latch-coupling闩锁耦合方案，是一种闩的下降方案，又称为latch crabbing(螃蟹闩？)，因为获得闩的步骤是，先从B+树根节点获得锁，然后找树枝、获得树枝的闩并释放父亲的闩，因为如果子节点是安全的，线程可以释放父节点上的闩。安全是指“插入时未满和删除时超过半满”。等待树枝/叶上的闩被释放的过程中，要一直持有当前树枝/根的闩。使用闩锁耦合方式查找索引的方案，可参照IBM的ARIES-IM。闩锁耦合方案只适用于B+树，对于基于负责数据的索引树入R树就不适用。而right-link方案适用范围更广。
3. right-link右连接方案，通过对B+树结点添加指向右邻居的连接，把两个节点当作一个大节点，以减少闩和再遍历需求。遍历时，右连接方案不需要有闩锁耦合(上闩、读、放开闩)，遍历事务访问到B+树结点期间可检测到节点的拆分，并通过右连接访问B+树里正确的位置。
论文没把右连接方案写清楚，也没有列全B+树并发控制方案，http://db.cs.berkeley.edu/jmh/cs262b/treeCCR.html讲得更详细。

物理结构的日志
为了更加高效，索引的日志逻辑代码更复杂，举例说明：insert事务abort后，新分裂的节点没有必要再合在一起，因此在记录索引日志的时候对一些动作会打上‘redo-only’标记。ARIES提出一种针对nested top actions场景的机制，使恢复程序直接跳过物理结构更改记录而不需要为每个场景都写代码。
同样的思路应用到数据库的其他类型日志上，如堆文件(文件链表)的插入操作就不需要undo。
为什么新分裂的节点就不需要合在一起了？假设B+树并发控制使用latch-coupling模式运行，这样做不会因为未达到半满而影响判断吗？ --- 不知道。

间隙锁用于在元组级别加锁、索引可用的同时保证串行化。
幻读问题与数据库元组可见性有关，如何锁住逻辑空隙呢？
1. 昂贵的谓词锁。谓词锁粒度不固定，*粒度大，则锁管理开销小，并行度低；*粒度小，则管理开销大，基于哈希的锁表不能实现谓词锁，因为谓词锁需要检测并发事务间的谓词之间是否相容。
2. Next-key lock，锁定记录本身+间隙，这是用物理对象(存在的元组)来替代逻辑概念(谓词)，这样简单的系统设施(例如基于哈希的锁表)就能支持复杂的目的。这个物理对象替代逻辑概念的思路是数据库独具的，因为没有其他并发系统需要像数据库这样“consider semantic information about logical concepts as part of the systems challenge”，作者鼓励复杂软件系统设计者可以考虑战略储备这种奇怪的技巧。

题外话，靠锁实现的并发控制大致有：谓词*、直接*(固定*粒度)、分层*(DB>Segmen>Relation>Tuple，IS、IX、SIX)/预约*

论文外的问题：怎么理解MySQL间隙锁？

并发控制、日志管理、bufferpool、访问方法四者的纠缠

并发控制与恢复管理之间

预写式日志WAL已经暗示了，锁协议遵循严格的两阶段锁，如果是不严格的2PL，WAL不会正确运行，举例说明：

事务T1回滚阶段，恢复代码从读T的日志开始，undo事务的修改。这个处理需要修改T1修改过的页数据和元组，也就是说T1此时还是需要持有这些页面或者元组的X锁的。如果是非严格的2PL方案，T1在abort前弃用锁，那么rollback程序就有问题了。
一方面，恢复逻辑依赖并发控制，恢复管理器需要了解可能引起何种不一致，然后用日志记录下来，以便恢复一棵树的物理一致性；另一方面，访问方法的并发控制依赖于恢复逻辑，例如需要知道哪些动作可以被undo跳过。

访问方法与其他功能模块的纠缠

因为书本上的线性哈希和R树太难有效实现了，数据库主流的原生、事务保护访问方法是堆文件+B+树。虽然这样说，B+树代码还是特别费解，因为像第4节讨论的那样，要想支持并发和恢复，就得实现各种闩、锁、日志协议。同时堆文件的代码也非常复杂，堆文件描述的数据结构不同，代码实现也不同。
并发控制与访问方法的纠缠。访问方法的并发控制只在*法领域发展完善，像乐观法、多版本快照法做访问方法的并发控制并不现实。
访问方法的恢复逻辑因系统不同而有差异：恢复协议严重依赖访问方法日志记录的时间、内容，数据结构修改内容(以便决定undo还是跳过)、物理日志和逻辑日志。

事务存储唯一独立的模块是缓冲区管理

只要管理好缓冲区页的pin和unpin，换页逻辑（STEAL）和刷新逻辑(NOT FORCE)就能正常秩序，这是因为并发控制和恢复做了大量的复杂工作来支持缓冲区的简便性。