1. 事务并发管制原理概述
1.1 为什么要进行并发管制
数据库是共享资源，通常有许多个事务同时在运行。当多个事务并发地存取数据库时就会产生同时读取和/或批改同一数据的状况。若对并发操作不加管制就可能会存取和存储不正确的数据，毁坏数据库的一致性。所以数据库管理系统必须提供并发管制机制。
下图左事务 T2 在 t6 时刻的写操作 W(A)将事务 T1 在 t5 时刻的写操作笼罩了，造成事务 T1 的更新失落；下图右事务 T2 读到了事务 T1 回滚了的写操作，该数据不非法，称为脏读。除此之外，因为事务的并发执行，还会产生不可反复读、幻读、读写偏序等问题，在此不一一介绍。
图 1 左为更新失落，右为脏读
数据库为了进步资源利用率和事务执行效率、升高响应工夫，容许事务并发执行。然而多个事务同时操作同一对象，必然存在抵触，事务的中间状态可能裸露给其它事务，导致一些事务根据其它事务中间状态，把谬误的值写到数据库里。须要提供一种机制，保障事务执行不受并发事务的影响，让用户感觉，以后好像只有本人发动的事务在执行，这就是隔离性。因为隔离性对事务的执行程序要求较高，很多数据库提供了不同选项，用户能够就义一部分隔离性，晋升零碎性能。这些不同的选项就是事务隔离级别。事务的隔离级别个别划分为四个，由低到高别离为：读未提交、读已提交、可反复读、串行化。最终的目标是将并发执行的事务依照正当的程序做到逻辑上的串行操作，防止依照时序执行毁坏数据库的一致性。
图 2 并发操作的串行执行程序
1.2 罕用的并发管制方形式
罕用的并发管制有锁、工夫戳、有效性查看、快照、多版本机制，在此咱们介绍几个和云溪数据库相干的并发管制。
1.2.1 锁
为了最大化数据库事务的并发能力，数据库中的锁被设计为两种模式，别离是共享锁和互斥锁。当一个事务取得共享锁之后，它只能够进行读操作，所以共享锁也叫读锁；而当一个事务取得一行数据的互斥锁时，就能够对该行数据进行读和写操作，所以互斥锁也叫写锁。如果以后事务没有方法获取该行数据对应的锁时就会陷入期待的状态，直到其余事务将以后数据对应的锁开释才能够取得锁并执行相应的操作。
图 3 互斥锁和共享锁的相容性
两阶段锁协定（2PL）是一种可能保障事务可串行化的协定，它将事务的获取锁和开释锁划分成了增长（Growing）和缩减（Shrinking）两个不同的阶段。在增长阶段，一个事务能够取得锁然而不能开释锁；而在缩减阶段事务只能够开释锁，并不能取得新的锁。
死锁在多线程编程中是常常遇到的事件，一旦波及多个线程对资源进行抢夺就须要思考以后的几个线程或者事务是否会造成死锁. 通过有向期待图是否产生环能够判断是否有死锁产生。如何从死锁中复原其实非常简单，最常见的解决办法就是抉择整个环中一个事务进行回滚，以突破整个期待图中的环。
图 4 死锁的产生
1.2.2 工夫戳
为每个事务调配 timestamp，并以此决定事务执行程序。当事务 1 的 timestamp 小于事务 2 时，数据库系统要保障事务 1 先于事务 2 执行基于 T / O 的并发管制，读写不需加锁，每行记录都标记了最初批改和读取它的事务的 timestamp。当事务的 timestamp 小于记录的 timestamp 时（不能读到”将来的”数据），须要 abort 后从新执行。假如记录 X 上标记了读写两个 timestamp：WTS(X)和 RTS(X)，事务的 timestamp 为 TTS，可见性判断如下：
读：
TTS < WTS(X)：该对象对该事务不可见，abort 事务，取一个新 timestamp 从新开始。
TTS > WTS(X)：该对象对事务可见，更新 RTS(X) = max(TTS,RTS(X))。为了满足 repeatable read，事务复制 X 的值。
写：
TTS < WTS(X) || TTS < RTS(X)：abort 事务，从新开始。
TTS > WTS(X) && TTS > RTS(X)：事务更新 X，WTS(X) = TTS。
它缺点包含：长事务容易饿死，因为长事务的 timestamp 偏小，大概率会在执行一段时间后读到更新的数据，导致 abort；读操作也会产生写（写 RTS）。
1.2.3 多版本并发管制
数据库保护了一条记录的多个物理版本。事务写入时，创立写入数据的新版本，读申请根据事务 / 语句开始时的快照信息，获取过后曾经存在的最新版本数据。它带来的最间接的益处是：写不阻塞读，读也不阻塞写，读申请永远不会因而抵触失败（例如单版本 T /O）或者期待（例如单版本 2PL）。对数据库申请来说，读申请往往多于写申请。支流的数据库简直都采纳了这项优化技术。
图 5 多版本并发读写操作
2. 云溪数据库并发管制机制
云溪数据库采纳 Percolator 的并发管制模型，云溪数据库中的值不间接写入存储层; 相同，所有货色都是以长期状态写成的，称为“Write Intent”，并增加了一个附加值，用于标识值所属的事务记录（transaction record）。每当操作遇到 Write Intent 时，它会查找事务记录的状态以理解它应如何解决 Write Intent 值。
2.1 事务记录
为了跟踪事务执行的状态，咱们将一个事务记录的值写入 KV 存储，事务所有的 write intents 都指向该记录，该记录容许所有事务查看它们遇见的 write intents。这个在分布式环境中对并发性反对很重要。事务记录表白了以下事务的状态之一：
- PENDING: 所有值的初始状态，示意 Write Intent 的事务仍在进行中。
- COMMITTED: 事务实现后，此状态示意能够读取该值。
- STAGING：用于启用并行提交性能。依据此记录援用的写入用意的状态，事务可能处于提交状态，也可能不处于提交状态。
- ABORTED: 如果事务失败或被客户端停止，它将进入此状态。
- Record does not exist: 如果事务遇到不存在事务记录的写用意，它将应用写用意的工夫戳来确定如何持续。如果写用意的工夫戳在事务活跃度阈值内，则写用意的事务将被视为
PENDING，否则将被视为事务ABORTED。
2.2 写用意
它们实质上是多版本的并发管制值（也称为 MVCC，在存储层中有更深刻的解释），并增加了一个附加值，用于标识值所属的事务记录。能够把它们视为复制锁和复制长期 value 的组合。
每当操作遇到 Write Intent（而不是 MVCC 值）时，它会查找事务记录的状态以理解它应如何解决 Write Intent 值。如果事务记录失落，操作将查看 write intents 的工夫戳，并评估它是否过期。
每当操作遇到 key 的 Write Intent 时，它会尝试“解析”它，其后果取决于 Write Intent 的事务记录：
- COMMITTED: 该操作读取 Write Intent 并通过删除 Write Intent 指向事务记录的指针，来将其转换为 MVCC 值。
- ABORTED: Write Intent 被疏忽并删除。
- PENDING: 这示意存在事务抵触，必须解决。
- STAGING: 须要通过事务协调器去查看这个事务记录的心跳是否还在，如果存在则须要期待
2.3 解决抵触
2.3.1 写写抵触
1. 如果事务具备明确的优先级设置，则比拟优先级决定 push 操作，优先级高的事务会将优先级低的事务回滚
2. 如果没有优先级之分，工夫戳大的事务会进入工夫戳小的事务的队列中期待事务记录变为 committed 或者 aborted
2.3.2 写读抵触
1. 如果事务具备明确的优先级设置，则比拟优先级决定 push 操作，优先级高的事务会将优先级低的事务的是工夫戳推到高优先级事务之后
2. 如果没有优先级之分，工夫戳大的事务会进入工夫戳小的事务的队列中期待事务记录变为 committed 或者 aborted
2.3.3 读后写
读操作读取值的时候都会把读工夫戳存储到一个工夫戳缓存，该缓存显示读取值的高水位线写操作产生时，对照这个工夫戳缓存查看工夫戳，如果写事务工夫戳小于工夫戳缓存最新值，那么就是产生了读后写。写事务工夫戳会被后推，该操作可能影响事务产生重启（read refreshing）
3．云溪数据库并发控制器
3.1 为什么要做并发控制器
- 将申请同步解决和事务抵触解决集中在一个地位，容许独自记录、了解和测试主题。
- 简化了事务排队过程，升高了事务推送 RPC 的频率，并容许期待者在用意解析后立刻持续。
- 创立一个锁的框架，能够做 kv 级别 SELECT for update 和 SELECT for share 性能。
- 当事务发生冲突时，围绕公平性提供更无力的保障，以缩小竞争场景下的尾部提早
3.2 并发控制器根本构造
并发管理器是一种构造，它对传入的申请进行排序，并在收回那些要执行抵触操作的申请的事务之间提供隔离。在排序过程中，通过被动排队和被动推送相结合的形式发现抵触并解决任何发现的抵触。一旦申请被排序，它就能够自在地进行 evaluate，而不用放心与其余申请发生冲突。这种隔离在申请的生存期内失去保障，但在申请实现后终止。
事务中的每个申请都应该与其余申请隔离，无论是在申请的生存期内还是在申请实现后（假如它取得了锁），但申请都应该在事务的生存期内。
外围是两局部：latch manager 和 lock table。
- lm 是将 request 排序，保障他们的隔离性
- lt 给 request 提供锁和排序，它是一个在每个节点内存中的数据结构，保留取得锁的正在进行的事务汇合。lock 机制要和 write intent 兼容，所以当申请在 evaluate 过程中发现了内部锁，则会将这些信息引入。
3.3 并发控制器管制过程
- 从申请 SequenceReq 获取 Latch 保障没有 req 抵触并查看内存 locktable，如果有抵触则开释 latch 后期待对应锁
- 后开始失常执行申请，执行 apply 后会向 locktable 减少以后事务的锁信息
- 并在申请实现后 FinishReq 开释 Latch 持续其余申请
- 最初在事务提交或回滚后的 resolve intent 实现后开释 locktable 中事务占的锁，并唤醒其余期待事务的申请。
3.4 latch manager
latch manager 给传入申请进行排序，并在并发管理器的监督下提供这些申请之间的隔离。latch 就像一个低级别的继续时间段的 mutex
工作形式：
1. 某个 range 的写申请会被这个 range 的 LeaseHolder 序列化，置于某种程序中
2. 为了强化这个序列化，LeaseHolder 采纳对这些写的值采纳 latch 提供无竞争拜访
3. 其余申请进入 LeaseHolder 申请被 latch 锁的同一组 key，必须先获取 latch 能力持续
4. 读申请也能产生 latch，并且多个读申请对于雷同的 key 能够同时持有 latch（相容），但 是读 latch 和写 latch 不能相容。
另一种对待 latch 的形式相似于互斥锁，它只在单个低级申请的持续时间内须要。为了协调运行工夫更长、级别更高的申请（即客户端事务），咱们应用长久的写用意零碎。
3.5 lock table
它是一个在每个节点内存中的数据结构，保留取得锁的正在进行的事务汇合。每个锁都有一个与之相关联的队列，期待该锁开释的事务都在外面排队。本地存储的 lockWaitQueue 中的我的项目会被 RPC 流传到现有的 TxnWaitQueue 下来，该 TxnWaitQueue 队列存储在事务记录所在的的 Raft Group 的 leader 节点上。
并非所有锁都间接存储在管理器的管制下，因而在排序过程中并非所有锁都能够发现。具体来说，write intents（复制的、排他的锁）内联存储在 MVCC 密钥空间中，因而直到申请 evaluation 时才可检测到它们。为了适应这种锁存储模式，管理器将无关内部锁的信息集成到并发管理器构造中。
锁的生命周期要大于锁持有者（事务）的生命周期，锁将特定的 key 上提供的隔离的持续时间缩短到锁持有者事务自身的生命周期。它们（通常）仅在事务提交或停止时才被开释。
然而，并非所有锁都间接存储在管理器的管制下，因而在排序过程中并非所有锁都能够发现。具体来说，write intents（复制的、排他的锁）内联存储在 MVCC 中，因而直到申请 evaluation 时才可检测到它们。目前，并发管理器在非复制的锁表构造上运行
3.6 TxnWaitQueue
TxnWaitQueue 追踪所有他们遇到的无奈推动（push）写事务的事务，并且必须期待阻塞事务实现能力持续。他是一个存储阻塞事务 ID 的数据结构
重点：这些流动产生在单个节点上，该节点是蕴含事务记录的 range 的 Raft 组的 leader。
一旦事务的确解决了，一个信号被发送到 TxnWaitQueue，它容许被该事务阻塞的所有事务开始执行。
被阻塞的事务会查看本人事务的状态，以确保它们仍处于活动状态。如果被阻止的事务被停止，则只需将其删除。
如果事务之间存在死锁（即它们各自被彼此的 Write Intents 阻塞），则其中一个事务被随机停止。
3.7 lockTableWaiter
lockTableWaiter 负责 lock wait queue 中的持有锁的抵触事务，它保障在事务协调器出差或者死锁状况下，申请可能持续进行
waiter 实现了申请期待抵触的锁在 lock table 外面开释的逻辑，相似的，他实现了调用者申请之前的期待抵触申请的逻辑，该锁期待队列是调用者的一部分
此期待状态响应锁表中的一组状态转换：
1. 抵触的锁被开释
2. 抵触的所被更新使其不再抵触
3.lock wait queue 中抵触的申请取得锁
4.lock wait queue 中抵触的申请退出 lock wait queue
这些状态状态转换通常是反射性的，waiter 能够期待锁开释或者被其余参与者退出。
LockManager 反对对抵触锁的状态转换作出反应
RequestSequencer 接口反对对抵触 lock wait-queues 的状态转换作出反应
然而，在事务协调器失败或事务死锁的状况下，如果没有 waiter 的干涉，状态转换可能永远不会产生。为了确保向前推动，waiter 可能须要被动推送抵触锁的持有者或抵触锁期待队列的头。该行为 push 须要一个 RPC 到抵触事务记录的 leaseholder，通常会导致 RPC 在 leaseholder 的 txnWaitQueue 中排队。因为这样做的代价很高，所以推送不会立刻执行，它只在提早之后执行。