分布计算系统笔记——第七章 分布式数据管理

数据一致性模型 ​

严格一致性 ​

对一个数据项所进行的任何读操作所返回的值总是对该数据项最近一次进行写操作的结果

顺序一致性（可线性化一致性） ​

读的顺序要都一样？

相关一致性 ​

没看明白想表达什么意思

FIFO一致性 ​

一个进程中的所有写操作能够以它在该进程中出现的顺序被所有其他进程看见。但是不同进程中的写操作在不同的进程看来具有不同的顺序

处理机一致性模型：FIFO基础上不同进程对同一数据的写的顺序也被其他进程看到

弱一致性 ​

1. 访问与数据存储有关的同步变量时，必须遵守顺序一致性模型；
2. 以前的所有写操作在每个副本上没有完成之前，对同步变量进行的操作不允许执行；
3. 以前的所有对同步变量的操作完成之前，对数据项进行任何读或写操作不允许执行。

释放一致性 ​

2个操作：

1. acquire操作，它用于告诉系统调用进程要进入一个临界区，在这种情况下，其他进程对远程副本的修改应该传播到本地，并且要对本地的副本进行更新；
2. release操作，用于告诉系统调用进程要离开一个临界区，在这种情况下，本地进程对本地数据副本的修改应该传播到所有的远程副本上。

3个规则

1. 前面的所有acquire操作完全成功完成以前，对共享数据的读写操作不能执行；
2. 在一个释放操作被允许执行之前，所有以前的读写操作必须完成；
3. 对同步变量的访问必须遵守FIFO一致性模型。

进入一致性 ​

1. 被保护数据的所有更新完成之前，一个进程对相应同步变量的acquire操作不能执行。
2. 如果有其他进程持有某个同步变量，即使是以非互斥的方式持有这个同步变量，一个进程以互斥的方式对这个同步变量的访问不能执行。
3. 当一个对同步变量的互斥方式访问完成以后，其他进程对这个同步变量的非互斥方式的访问也不能立即执行，除非在这个同步变量的所有者的访问完成之后。

总结 ​

并发控制 ​

并发控制的目的是在有多个用户的情况下允许每个用户像单个用户那样访问共享资源，多个用户同时访问时互相不干扰。并发控制要解决多个用户的活动之间的切换，保护一个用户的活动不受另一个用户的活动的影响，以及对相互依赖的若干活动进行同步等问题。

数据库中的事务处理(transaction)是施加在共享数据上的一组操作，这些操作是结合在一起的，被当作单个活动看待。

无并发控制的情况下，两个并发的事务处理可能会相互干扰：

1. 丢失更新。多个事务处理同时对一个共同的数据对象进行写操作时，就会有丢失更新的现象发生，并且使数据库处于不一致状态。
2. 检索的不一致。检索的不一致发生在一个事务处理读取数据库中的某些数据对象，但是另一个事务处理对其中一些数据对象的修改还没有完成。

并发控制的正确性标准：

1. 用户交给系统的每个事务处理最终将被执行，并最终得到完成；
2. 多个事务处理并发执行的结果和这多个事务处理串行执行的结果相同。

并发事务处理时会有暂时不一致性和冲突。暂时不一致性是固有的，冲突是要避免的。

可串行化调度 ​

并发控制就是控制相互冲突操作的相对执行顺序，完成这种控制的算法也叫同步技术。我们希望使用这样的同步技术，它能使各个非冲突的操作交叠执行，以便进行各事务处理时具有最大的并发性。一组事务处理中各个操作的交叉次序叫做调度。如果一个调度给每个事务处理一个一致的状态观点，则这种调度叫做一致调度。一致调度的充分条件是这种调度执行的结果和所有事务处理串行执行的结果是一样的。满足这个条件的调度叫做可串行化调度或线性化调度。

两个调度等价：在事务处理系统上两个调度等价当且仅当

1. 两个调度中每个对应的读操作读自同一个写操作；
2. 两个调度中有同样的最终写。

串行化图 ​

读后写、写后读、写后写，都画一条边。读->写，写->读，写->写

基于锁的并发控制 ​

静态封锁和动态封锁 ​

在静态封锁方式中，事务处理在执行操作前，对所有需要的数据对象封锁。这个方法相对简单，然而它限制了并发性，因为有冲突的事务处理必须串行执行。在动态封锁方式中，事务处理在执行的不同阶段对不同对象封锁。

两阶段封锁 ​

1. 访问一个对象前先封锁它，为此必须先获得锁
2. 对所有要访问的对象封锁前不对任何对象进行解锁
3. 不要封锁已经被封锁的对象，为此不同的事务处理不可同时获得冲突的锁
4. 事务处理执行结束前，为每个被它封锁的对象解锁
5. 一旦一个事务处理释放一个锁，该事务处理就不能再获得另外的锁。

锁的增长阶段和收缩阶段 ​

增长阶段中事务处理获得所有的锁而不释放任何锁；收缩阶段释放所有的锁而不取得另外的锁。

问题：

1. 在锁的增长阶段会出现死锁的问题。发生死锁是因为在加锁机制中，锁是一种竞争的资源。死锁问题可以用第六章讨论的办法来解决。
2. 在锁的收缩阶段容易出现层叠回退(cascaded aborts)的问题。层叠回退的问题发生在一个事务处理操作失败后回退，在回退前由于该进程已经释放了某些数据对象上的锁，所以其他事务处理可能已经读取了被这个事务处理修改过的数据对象，这些事务处理也必须回退。

层叠回退可以通过操作完成后使用一个原子操作释放所有锁来解决，但是降低了并发程度

加锁方法 ​

1. 集中式加锁方法。在这种加锁方式中，锁管理是集中进行的。有一个集中的锁管理员，它负责锁的分配和释放。
2. 主站点加锁方法。每个数据对象有一个主站点，所有对数据对象的更新首先定向到主站点。对某个数据对象的加锁和释放锁的管理活动是由该数据对象的主站点上的锁管理员负责的。
3. 分散式加锁方法。锁的管理有所有站点共同完成。事务处理的执行包括许多站点的参与和协作。

原子事务处理 ​

性质 ​

1. 原子性(Atomicity)。一个原子事务处理的执行必须确保是完全执行完毕或相当于完全没有执行。
2. 一致性(Consistency)。一个事务处理必须以一致性的状态开始，以一致性的状态结束。不能违背系统的恒定性。
3. 孤立性(Isolation)。原子事务处理所有的中间操作必须以孤立的形式执行。只允许在该事务处理操作的某个数据对象达到一致的状态时才能够被其他事务处理访问。也就是说，并发的事务处理之间不会发生相互干扰。孤立性也称为可串行性。
4. 持久性(Durability)。一旦事务处理已经被提交，即使在发生系统失效的情况下，结果将永不丢失。

事务处理分类 ​

1. 平面事务处理：事务处理都是由一系列基本的操作所组成；
2. 一个嵌套事务处理是由多个子事务处理组成的，顶层的事务处理产生多个子事务处理，这些子事务处理相互在不同的机器上并行执行。每个子事务处理也可以产生自己的子事务处理；
3. 分布式事务处理也是由一些子事务处理组成的，分布式事务处理在逻辑上是平面的，是施加在分布式数据对象上的一系列在逻辑上不可分的操作组成的；

原子事务处理实现 ​

1. 事务处理管理员：负责使该事务处理的各个参加者就该事务处理是否提交或夭折达成一致意见；
2. 恢复管理员：负责在事务处理失效后恢复状态；
3. 缓冲器管理员：负责在主存和磁盘间传送数据；
4. 运行记录(log)管理员：负责各种操作及状态的记录；
5. 锁管理员；负责并发控制；
6. 通信管理员：负责透明的跨网络的通信，在分布式事务处理中通知事务处理的管理部分。

局部恢复技术 ​

意图表法 ​

执行：

1. 把事务处理要向各数据对象施加的所有修改操作都存放在一个表中，该表称为意图表；
2. 该表被写入坚固存储器中；
3. 事务处理管理员决定该事务处理是否提交；
4. 若该事务处理提交，则在表中设置完整标志，开始按照意图表修改在磁盘中的那些对象；
5. 删除意图表。

失效：

1. 意图表不存在，夭折事务处理
2. 意图表不完整，夭折事务处理，删除该表
3. 按意图表更新时节点崩溃，重新更新，更新完删除该表

先写运行记录 ​

执行：

修改数据对象前在运行记录里写记录项，存储数据对象和修改前后的值，写完运行记录再修改。记录存在坚固存储器中。

恢复：

从运行记录末尾读取每一个记录项，按内容执行恢复操作（叫做卷回roolback）

分布式提交协议 ​

保证一个进程组要么都执行某操作，要么都不执行

两阶段提交协议(2PC) ​

选一个协调者，所有进程每做完一件事，向协调者发报文，协调者全收到就OK，出问题就发夭折报文，全部进程白干

1. 协调者向所有进程发送PREPARE报文，等待回答
2. 参加者收到PREPARE报文，完成工作后将COMPLETE写入运行记录，发送PREPARED报文，否则发送ABORT报文
3. 协调者如果收到ABORT，或者超时了，就将ABORT写入运行记录，发送ABORT报文；成功收到了所有PREPARED，就将COMMIT写入运行记录，发送COMMIT报文，等待回答
4. 参加者如果收到ABORT，就ABORT，然后发送ACK-ABORT；如果收到COMMIT，就将COMMIT写入运行记录，释放锁，发送ACK-COMMIT
5. 协调者收到所有ACK-COMMIT，将COMPLETE写入运行记录，结束本次协议

协调者在第3步之前崩溃，重启后发送ABORT；第5步之前崩溃，发送COMMIT

多副本更新和一致性管理 ​

系统数据库的分布 ​

• 完全分割方式：数据库的各部分分散到各地点，相互都是不重复的；
• 完全冗余方式：整个数据库的各个副本分散各处；
• 部分冗余方式：数据库分成若干部分，其中有些部分有副本存放在其他地点。

一致性 ​

冗余副本的相互一致性和每个副本的内部一致性

相互一致性：整个数据库或其一部分的各副本是相同的

内部一致性：数据要符合现实，事务处理要原子性

兼容可串行化 ​

并发事务处理在不同处理机上保持相同的串行顺序叫做兼容可串行化，一般由复制控制算法保证

表决法

在控制者之间交换报文，对分布式数据库要进行的各事务处理的整个次序达成一致意见

• 在同步表决方案中，各控制者对一个给定事务处理进行表决，一旦取得一致意见就共同执行此事务处理的各步骤。
• 在异步表决方案中，允许各控制者和存储处理机并发地对不同事务处理的请求和执行进行表决。

非表决法

使用控制优先权，一种方法是在各控制者之间建立主从关系

主站点法 ​

指定一个站点为主站点，其他为备份站点，所有请求发到主站点

读请求：主站点直接返回

写请求：向至少k个站点发送更新请求，所有站点收到后，主站点完成操作再送回结果

循环令牌法 ​

全部控制者排成单向环，给一个控制者分配一个暂时的唯一的控制权

1. 控制者收到令牌后执行事务处理
2. 令牌携带顺序号，给所有请求发票，建立全排序，请求排到第一位时执行事务处理

同步表决法 ​

控制者接到请求时对该事务表决，并广播投票，其他控制者表决并广播，收到所有控制者的投票后，并且自己也投了票，开始事务处理，完毕后发送END报文，收到所有控制者的END后返回初始状态

如果有更高优先级的请求，就放弃当前事务处理

活动复制控制方法 ​

要求顺序一致性：每个控制者经历同样顺序的修改操作，同时，如果没有新操作时它们的值应该相等

每个本地更新加上时间戳后广播到所有其他控制者。每个控制者i有一个队列Qi[j]，包含有从控制者j发送来的报文。因为每个队列中的报文是按照它们的发送顺序排列的，所以按顺序查看报文时只需要检查队列头

法定数方法 ​

N个服务员，想要读需要得到R个服务员同意，想要写需要得到W个同意。要求 $R+W\le N$。读越简单，则写越难。因此法定数的选择取决于读写操作的频率。

分层表决方法 ​

对于表决方法，使用分层的树型结构，还可以减少表决所需的报文数目。例如前面的Holler同步表决方案，完成一次同步表决至少需要2N(N-1)个报文，其中每个控制者需要向所有其他N-1个控制者发送投票报文，每个控制者完成本地副本更新后需要向所有其他N-1个控制者发送END报文。如果16个副本被线性组织，那么完成一次表决至少需要2×16×15=480个报文。如果采用树型结构，那么完成一次表决只需要5×2×4×3=120个报文。