专栏
《数据库系统内 幕》存储引擎
《数据库系统内 幕》事务恢复与处理
《数据库系统内 幕》日志结构存储
《数据库系统内 幕》B树的变体
《数据库系统内 幕》分布式系统
本文引用了博主对于两阶段、三阶段提交的总结传送门，膜大佬~
第二部分里面讲了分布式系统的术语简介（章8）；故障，包括故障检测（章9）、反熵和传播（章12）；领导者选举（章10）依赖于共识算法（章14）；分布式中保持一致性，单个操作的一致性模型（章11）、多个操作一致性，分布式事务（章13）
重点是9、10、11、14章
分布式数据库系统是相对于集中式数据库系统而言的，是将数据库技术与网络技术相结合的产物。分布式数据库（Distributed DataBase，DDB）比较确切的定义是：分布式数据库是由一组数据组成的，这组数据分布在计算机网络的不同计算机上，网络中的每个结点具有独立处理的能力，成为场地自治，它可以执行局部应用，同时，每个结点也能通过网络通信子系统执行全局应用。负责分布式数据库的建立、查询、更新、复制、管理和维护的软件，称为分布式数据库管理系统（Distributed DataBase Management System， DDBMS）。
与集中式数据库相比，分布式数据库具有下列优点：
（1）坚固性好。由于分布式数据库系统是由多个位置上的多台计算机构成的，在个别结点或个别通信链路发生故障的情况下，它仍然可以降低级别继续工作，如果采用冗余技术，还可以获得一定的容错能力。因此，系统的坚固性好，即系统的可靠性和可用性好。
（2）可扩充性好。可根据发展的需要增减结点，或对系统重新配置，这比用一个更大的系统代替一个已有的集中式数据库要容易得多。
（3）可改善性能。在分布式数据库中可按就近分布，合理地冗余的原则来分布各结点上的数据，构造分布式数据库，使大部分数据可以就近访问，避免了集中式数据库中的瓶颈问题，减少了系统的响应时间，提高了系统的效率，而且也降低了通信费用。
（4）自治性好。数据可以分散管理，统一协调，即系统中各结点的数据操纵和相互作用是高度自治的，不存在主从控制，因此，分布式数据库较好地满足了一个单位中各部门希望拥有自己的数据，管理自己的数据，同时又想共享其他部门有关数据的要求。
理解不同进程并发执行时可能的交错情形。
了解分布式计算中的误区：
进程本地队列的目标：
网络分区：两个或多个服务器无法相互通信
级联故障：从系统一部分传播到另一部分，扩大问题。
退避策略：通过合理安排重试，增加后续请求之间的时间来避免问题扩大。
链路：
公平损失链路：发送方不能确定消息是否送达；消息最终会送达；发送的消息不会被送达无限次；链路不会自己生成消息。
顽固链路：传输过程中不会发生不可恢复的消息丢失；
完美链路：每个发送的消息都会被传递、消息不会传送多次、仅传递由发送者发送过的消息。
重传
我们在得知消息状态之前会进行重传，但是会造成消息重复的问题。那么这部分提到了一个幂等。当要执行操作是幂等时，处理重复消息才是安全的。
幂等：理解下就是一个接口可以重复调用，在调用多次情况下，最终结果是一致的。（执行了多次一个相同的操作但是结果保持执行一次的结果，不会产生其他副作用。）
比如查询功能、关机操作此类。
为了保持幂等性，我们会引入一些操作。
分布式系统中的两种问题：①保证消息顺序；②严格一次传递；
通过上面去重表中的一个有序数组，可以保证消息顺序。
由于链路故障可能导致传递消息的第一次尝试无法成功，因此大多数实际的系统都采用至少一次传递（at-least-once delivery），它确保了发送方将重试直到收到确认为止，否则就认为对方没有收到该消息。还有一种传递语义是最多一次（at-most-once）：发送方仅仅发送消息而不期待得到任何确认。
要想建立可靠的链路，不可能不重复传送某些消息。但是，我们可以通过仅处理每个消息一次并忽略重复消息，使得从发送方的角度来看是严格一次发送。
一个正确的共识协议必须具备以下三个属性：
一致性
协议达成的决定必须是一致的：每个进程都做出了决定且所有进程决定的值是相同的。否则我们就尚未达成共识。
有效性
达成共识的值必须由某一个参与者提出，这意味着系统本身不能“提出”值。这也意味着这个值不是无关紧要（trivial）的：进程不能总是决定某个预定义的默认值。
终止性
只有当所有进程都达到决定状态时，协议才算完成。
故障模型
故障模型准确地描述了分布式系统中的进程可能以怎样的方式崩溃，并基于这些假设来开发算法。包括崩溃故障、遗漏故障、任意故障。
故障检测器在任何分布式系统中都是一个重要的组成部分。有助于扩展模型，允许我们通过准确性和完备性之间进行权衡来解决一致性问题。
第九章介绍了几种故障检测算法：心跳、ping、截止时间、联系范围等。
心跳：进程通过向其对等方发送消息来主动通知其仍在运行。
ping:进程将消息发给远程进程，在指定时间段是否能得到响应来检查是否处于活动状态。
可在异步系统假设下运行，仅对心跳计数并允许应用程序基于心跳计数器向量中的数据来检测进程故障。每个进程要维护一个邻居列表和与其相关联的计数器。
过程：
进程向邻居发送心跳消息，每个消息都包含心跳到目前为止经过的路径。（dp）初始消息包含路径中的第一个发件人和唯一标识符，该标识符可用于避免同一消息被广播多次。这个过程中由于消息是通过不同进程传播的，并且心跳路径包含从相邻进程接收的聚合信息，因此我们可以将无法到达的进程标记为活动进程（即使两个进程之间的直接链路出现故障）。
包括三个子系统的组合：
监控、解释、行动。
该算法原理是：收集和采样到达时间，创建出一个可用于对节点状况做出判断的试图，然后根据采样结果计算值，如达到阈值，则节点记为宕机。由于阈值可以被人工调整，所以这种故障检测器可以动态适应变化的网络条件。
了解Raft算法：在本质上，Raft算法通过一切 以领导者为准的方式，实现一系列共识和各节点日志的一致。
成员身份：领导者、跟随者、候选人。
跟随者等到领导者心跳超时时候推荐自己成为候选者；
候选者向其他节点发送投票消息，如果选票多成为领导者；
领导者负责写请求、管理日志复制和不断发送心跳信息。
服务器节点间沟通联络采用远程过程调用（RPC）：请求投票和日志复制。
日志复制只能由领导者发起。
Raft算法中的任期号：
跟随者在等待领导者心跳信息超时后，推荐自己时会增加自己的任期号；或者一个服务器节点，发现自己任期编号比其他节点小，那么会更新自己的编号到较大的编号值。
Raft算法约定，如果一个服务器节点发现自己任期号小于其他节点，那么会恢复成跟随者状态。（在分区错误恢复后，曾经的领导者任期号3，收到了新领导者的心跳消息，任期号为4，此时该节点会立即变为跟随者状态。
一个节点如果接收到任期号小的请求，那么会直接拒绝该请求。
霸道选举算法–>依次故障转移算法–>候选节点优化–>邀请算法–>环算法
一致性模型解释了多数据副本系统的可见性语义和行为。
数据复制通过维护多个数据副本来引入冗余，在多数据中心部署中，复制尤为重要。
定义两个可调度量：
收成：收成，就是能完成的量。查询过程中，目标100行，由于节点不可用问题得到尽可能多的查询，比“颗粒无收”的好（没有任何查询结果返回）。
产量：成功完成的请求数/尝试请求总数。
按照从保证最多的到保证最少的介绍：
可线性化：
要求：
在顺序一致性的基础上，加上序列化后的操作必须与它们的时间戳一致。也就是不单要变成一个序列，而且如果序列中op1->op2，那么要有ts(op1)<ts(op2)
做到可线性化需要与时间戳同步，所以开销大。
顺序一致性：
要求：
对于一些读写写操作的集合，所有进程看到的都是同样的顺序。也就是将并行的操作序列化，而且每个进程得到的序列都相同。
那么，很自然对于同一个进程执行的操作，必然要按照它们执行的顺序出现。
比严格一致性去掉了全局时钟。
因果一致性
要求：
有因果关系的写操作必须按照它们的因果关系的顺序被看到，没有因果关系的写操作可以以任意顺序被别的进程看到。
例如：
进程1 W(x)a
进程2 R(x)a W(x)b
进程3 R(x)a R(x)b
进程4 R(x)b R(x)a
进程3和1、2是满足因果一致性的，加上4就不满足了。因为进程2是由于读到x=a才把x写成b的，所以W(x)a和W(x)b之间有因果关系，必须按照因果的顺序出现。
相比顺序一致性，去掉了那些没有联系的操作达成一致顺序观点的要求，只是保留那些必要的顺序（有因果关系的）。
FIFO一致性
要求：
同一个进程的写操作必须以同样的顺序被别的进程看到，不同进程的写操作可以以任意顺序被看到。
比起因果一致性，不同进程的操作顺序都不管了，只要同一个进程的操作顺序保证就行了。
读自己写（read-own-write）
一个进程对于数据x的写操作，那么进程无论到任何副本上都应该看到这个写操作的影响，也就是看到和自己写操作的影响或者更新的值。
单调读（Monotonic Reads）
当进程从一个地方读出数据x，那么这个以后再读到的x应该是和当前x相同或比当前更新的版本。也就是如果进程迁移到了别的位置，那么对x的更新应该比进程先到达。这里的客户就是指这个进程。
单调写（Monotonic Writes）
跟单调读相应，如果一个进程写一个数据x，那么它在本地或者迁移到别的地方再进行写操作的时候，原来的写操作必须要先传播到这个位置。也就是进程要在任何地方至少和上一次写一样新的数据。
读后写（Writes follow reads）
顾名思义了，也就是在读操作后面的写操作要是基于至少跟上一次读出来一样新的值。也就是如果进程在地点1读了x，那么在地点2要写x的副本的话，至少写的时候应该是基于至少和地点1读出的一样新的值。
远程写协议
在数据项x上做写操作，
也即客户->主备份->其他备份->主备份->客户
本地写协议
定位x主副本，移到自己位置，在本地做写操作，主备份更新完成，再将更新传播给其他副本（即离线操作）
N个副本服务器，得到NR个读团体成员同意，NW个写团体成员同意，满足
NR + NW > N
NW > N/2
在大型集群中，由于节点数量庞大同时过度依赖于一个进程。广播变得又昂贵又不可靠。
熵：是一种衡量系统无序程度的属性。
假设在传播过程中会传播失败，协调者会尽量传递给可用的参与者，当出现故障时，反熵可以让节点重新同步。传递消息的责任所有节点共同承担，分为两步：主要传递和定期同步。
通过读取检测出副本差异，由协调者将缺失的变更发送给响应的副本。
读修复可以实现为阻塞或者异步操作。
阻塞修复，原始的客户端请求要等到协调者“修复”副本才能返回，确保读取单调性。
异步操作仅仅调度一个恢复任务，读请求会立刻返回结果给用户。
协调者可以不向每个节点都发出完全读取请求，优化为发送一个完全读取请求和多个请求数据的摘要。对于摘要请求我们读取本地数据，计算出数据哈希值。之后协调者在算出完整读取的哈希值来和别的摘要进行比较。若摘要都匹配，则确信副本是同步的。若不匹配，就像摘要不同的副本发送完全读取请求，比较响应找出差异并将变更发送给滞后副本。
目标节点未能确认写入时，则协调者或某一副本会存储一条特殊的记录，称为一个提示。当目标节点恢复后，该记录会立即重放过去。
用来寻找和修复未被查询到的数据的不一致性。
自底向上的一个递归计算树，确定两个副本时候，要比较Merkle树的根节点哈希值。
该方法的优势：捕获了值写入之间的因果关系，并允许节点精确表示其他节点缺少的数据点。
缺点：节点长时间宕机，对等节点一直无法截断日志。要等待滞后节点恢复后，将数据复制给它。
基于gossip的广播由对等节点操作——这些对等点接收来自通道上其他对等点的消息，然后将这些消息转发到通道上随机选择的多个对等节点，其中这个数字是一个可配置的常量，也称为扇出。
gossip可以构成一个生成树，每个点彼此相连用了尽量少的路径，但是一条链路的断开可能导致整个子树断开连接。
优化：推送/懒惰推送多播树：构建出节点的生成树覆盖网络，将完整的消息发送给很小的对等节点子集（对等节点采用服务），对于其他节点，只转发消息ID。节点对于未见过的消息标识符，查询对等节点获得这条消息（可以主动采用拉取机制获得消息）。
与串行化相比 是允许并发的实现
在保证一致性情况下，允许并发操作执行。
冲突可串行化（conflict serializability）
一个调度，如果通过交换相邻两个无冲突的操作能够转换到某一个串行的调度，称为冲突可串行化的调度。
当下面三种条件都满足时，我们将两个操作视为冲突
两个操作属于不同的事务
两个操作访问和处理的数据集有重叠
至少有一个操作的是写操作
对于S1是conflict serializability，可以交换非冲突操作，但S2都不可交换，不是conflict serializability。
// S1
T1 T2
R(A)
W(A)
R(A) <---
W(A)
R(B)
W(B) <------
R(B)
W(B)
// S2
T1 T2
R(A)
W(A)
R(A)
W(A)
R(B)
W(B)
R(B)
W(B)
同一个事务操作不可改顺序，同时t1的操作与相邻的t2操作不可交换。
关系
冲突可串行性 比 可串行性 要严格；
满足冲突可串行性 必 满足 可串行性，反之不然。
可串行化一定是正确的并发调度，反正不一定。
所以引出了优先图检测冲突可串行化。
如Ti的Ri(A)与Tj的Wj(A)冲突，而Ri(A)<Wj(A)，所以Ti就要先于Tj执行，所以就可以使用优先图来检测冲突可串行化。而如果优先图(precedence graph)没有环，则说明调度是冲突可串行化的。因为如果Ti需要在Tj前执行，又有Tj需要在Ti前执行，显然这是矛盾的，所以存在环则不是冲突可串行化的。
我们必须先执行事务，再让结果可见。
两阶段提交也被称为是一种协议。在分布式系统中，每个节点虽然可以知晓自己的操作时成功或者失败，却无法知道其他节点的操作的成功或失败。当一个事务跨越多个节点时，为了保持事务的ACID特性，需要引入一个作为协调者的组件来统一掌控所有节点(称作参与者)的操作结果并最终指示这些节点是否要把操作结果进行真正的提交(比如将更新后的数据写入磁盘等等)。
因此算法思路可以概括为：参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。
所谓的两个阶段是指：准备阶段(投票阶段)和提交阶段（执行阶段）。
准备阶段
事务协调者(事务管理器)给每个参与者(资源管理器)发送Prepare消息，每个参与者要么直接返回失败(如权限验证失败)，要么在本地执行事务，写本地的redo和undo日志，但不提交，到达一种“万事俱备，只欠东风”的状态。
1）协调者节点向所有参与者节点询问是否可以执行提交操作(vote)，并开始等待各参与者节点的响应。
2）参与者节点执行询问发起为止的所有事务操作，并将Undo信息和Redo信息写入日志。（注意：若成功这里其实每个参与者已经执行了事务操作）
3）各参与者节点响应协调者节点发起的询问。如果参与者节点的事务操作实际执行成功，则它返回一个”同意”消息；如果参与者节点的事务操作实际执行失败，则它返回一个”中止”消息。
提交阶段
如果协调者收到了参与者的失败消息或者超时，直接给每个参与者发送回滚(Rollback)消息；否则，发送提交(Commit)消息；参与者根据协调者的指令执行提交或者回滚操作，释放所有事务处理过程中使用的锁资源。(注意:必须在最后阶段释放锁资源)
接下来分两种情况分别讨论提交阶段的过程。
当协调者节点从所有参与者节点获得的相应消息都为”同意”时:
1）协调者节点向所有参与者节点发出”正式提交(commit)”的请求。
2）参与者节点正式完成操作，并释放在整个事务期间内占用的资源。
3）参与者节点向协调者节点发送”完成”消息。
4）协调者节点受到所有参与者节点反馈的”完成”消息后，完成事务。
如果任一参与者节点在第一阶段返回的响应消息为”中止”，或者 协调者节点在第一阶段的询问超时之前无法获取所有参与者节点的响应消息时：
1）协调者节点向所有参与者节点发出”回滚操作(rollback)”的请求。
2）参与者节点利用之前写入的Undo信息执行回滚，并释放在整个事务期间内占用的资源。
3）参与者节点向协调者节点发送”回滚完成”消息。
4）协调者节点受到所有参与者节点反馈的”回滚完成”消息后，取消事务。
二阶段提交看起来确实能够提供原子性的操作，但是存在如下缺点：
1、同步阻塞问题。执行过程中，所有参与节点都是事务阻塞型的。当参与者占有公共资源时，其他第三方节点访问公共资源不得不处于阻塞状态。
2、单点故障。由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。（如果是协调者挂掉，可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题）
3、数据不一致。在二阶段提交的阶段二中，当协调者向参与者发送commit请求之后，发生了局部网络异常或者在发送commit请求过程中协调者发生了故障，这回导致只有一部分参与者接受到了commit请求。而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据部一致性的现象。
4、二阶段无法解决的问题：协调者再发出commit消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。
由于二阶段提交存在着诸如同步阻塞、单点问题、脑裂等缺陷，所以，研究者们在二阶段提交的基础上做了改进，提出了三阶段提交。
三阶段提交有两个改动点。
1、引入超时机制。
2、在第一阶段和第二阶段中插入一个准备阶段。
CanCommit阶段
3PC的CanCommit阶段其实和2PC的准备阶段很像。协调者向参与者发送commit请求，参与者如果可以提交就返回Yes响应，否则返回No响应。
PreCommit阶段
协调者根据参与者的反应情况来决定是否可以记性事务的PreCommit操作。根据响应情况，有以下两种可能。
假如协调者从所有的参与者获得的反馈都是Yes响应，那么就会执行事务的预执行。
1.发送预提交请求 协调者向参与者发送PreCommit请求，并进入Prepared阶段。
2.事务预提交 参与者接收到PreCommit请求后，会执行事务操作，并将undo和redo信息记录到事务日志中。
3.响应反馈 如果参与者成功的执行了事务操作，则返回ACK响应，同时开始等待最终指令。
假如有任何一个参与者向协调者发送了No响应，或者等待超时之后，协调者都没有接到参与者的响应，那么就执行事务的中断。
1.发送中断请求 协调者向所有参与者发送abort请求。
2.中断事务 参与者收到来自协调者的abort请求之后（或超时之后，仍未收到协调者的请求），执行事务的中断。
doCommit阶段
分为以下两种情况。
执行提交
1.发送提交请求
2.事务提交 参与者接收到doCommit请求之后，执行正式的事务提交。并在完成事务提交之后释放所有事务资源。
3.响应反馈 事务提交完之后，向协调者发送Ack响应。
4.完成事务 协调者接收到所有参与者的ack响应之后，完成事务。
中断事务 协调者没有接收到参与者发送的ACK响应（可能是接受者发送的不是ACK响应，也可能响应超时），那么就会执行中断事务。
1.发送中断请求
2.事务回滚 参与者接收到abort请求之后，利用其在阶段二记录的undo信息来执行事务的回滚操作，并在完成回滚之后释放所有的事务资源。
3.反馈结果 参与者完成事务回滚之后，向协调者发送ACK消息。
4.中断事务 协调者接收到参与者反馈的ACK消息之后，执行事务的中断。
在doCommit阶段，如果参与者无法及时接收到来自协调者的doCommit或者rebort请求时，会在等待超时之后，会继续进行事务的提交。（其实这个应该是基于概率来决定的，当进入第三阶段时，说明参与者在第二阶段已经收到了PreCommit请求，那么协调者产生PreCommit请求的前提条件是他在第二阶段开始之前，收到所有参与者的CanCommit响应都是Yes。（一旦参与者收到了PreCommit，意味他知道大家其实都同意修改了）所以，一句话概括就是，当进入第三阶段时，由于网络超时等原因，虽然参与者没有收到commit或者abort响应，但是他有理由相信：成功提交的几率很大。 ）
2PC与3PC的区别
相对于2PC，3PC主要解决的单点故障问题，并减少阻塞，因为一旦参与者无法及时收到来自协调者的信息之后，他会默认执行commit。而不会一直持有事务资源并处于阻塞状态。但是这种机制也会导致数据一致性问题，因为，由于网络原因，协调者发送的abort响应没有及时被参与者接收到，那么参与者在等待超时之后执行了commit操作。这样就和其他接到abort命令并执行回滚的参与者之间存在数据不一致的情况。
理论上来说，共识算法具有3个性质：
一致性——所有正确进程决定的值相同；
有效性——决定的由其中某一个进程提出；
终止性——所有正确进程最终都会做出决定。
两个基本性质：
原子性：各个进程就接收消息达成一致。要么全收到，要么全没收到。
有序性：所有无故障进程相同顺序收到消息。
它包括三种角色： 提议者、接受者、学习者。
提议者（Proposer）：提议一个值，用于投票表决。
接受者（Acceptor）：对每个提议的值进行投票，并存储接受的值，比如 A、B、C 三 个节点。 一般来说，集群中的所有节点都在扮演接受者的角色，参与共识协商，并接受 和存储数据。
学习者（Learner）：被告知投票的结果，接受达成共识的值，存储保存，不参与投票的 过程。一般来说，学习者是数据备份节点，比如“Master-Slave”模型中的 Slave，被 动地接受数据，容灾备份。
这三种角色，在本质上代表的是三种功能：
提议者代表的是接入和协调功能，收到客户端请求后，发起二阶段提交，进行共识协 商；
接受者代表投票协商和存储数据，对提议的值进行投票，并接受达成共识的值，存储保 存；
学习者代表存储数据，不参与共识协商，只接受达成共识的值，存储保存。
在上面第十章的时候进行学习了。