分布式数据库一致性协议与XML文档模式提取方法解析

# 分布式数据库一致性协议与XML文档模式提取方法解析 ## 1. 分布式数据库一致性协议 ### 1.1 版本号机制 在分布式数据库中，为每个对象维护一个版本号。该版本号不进行复制，但协议会确保其在各个副本之间保持一致。当对象创建时，版本号设为0；每次事务更新对象并提交后，对象的版本号加1。由于原子广播保证了事务的总顺序，所有副本会按相同顺序处理事务，从而使版本号在副本间保持同步。 版本号用于检测冲突事务。若事务t′读取了版本号为vo的对象o，而在t′即将提交时，本地数据库中对象o的版本号v′o高于vo，则说明t′读取的数据已被其他事务（如事务t）修改，t′应被中止。此定义仅涵盖读写冲突，因为在该系统中，所有对象在写入前都会先被读取，所以不存在写写冲突。 ### 1.2 非投票算法 非投票算法的大致流程如下： 1. 事务的所有操作在发起事务的节点（委托节点）上本地执行。 2. 当应用程序请求提交时，使用原子广播原语将读取对象集及其版本号，以及写入对象集发送到所有节点。 3. 当原子广播协议传递事务时，所有服务器会验证接收到的事务是否与本地正在运行的其他事务冲突。若到达事务读取的对象版本号大于或等于本地数据库中这些对象的版本号，则无冲突，事务提交；否则，事务中止。由于该过程是确定性的，且所有节点（包括委托节点）按相同顺序接收事务，因此所有节点对事务结果达成相同决策。委托节点随后可将事务的最终结果通知客户端应用程序。 ### 1.3 投票协议 投票协议是对相关协议的改进，适用于Copla事务模型，包括写集广播阶段和投票（决策）阶段。其大致流程如下： 1. 事务的所有操作在委托节点上本地执行，对读取对象获取（本地）读锁（写入对象前必须先读取）。 2. 当应用程序请求提交时，使用原子广播将包含写入对象集的消息 < t, WSt > 发送到所有节点。 3. 当原子广播传递事务t的写集时，所有节点尝试对集合中的所有对象获取本地写锁。若有事务持有写集内任何对象的写锁，事务t将被挂起，直到该写锁被释放；持有写集内任何对象读锁的事务将被中止（通过原子广播发送中止消息）。当委托节点获取所有写锁后，通过原子广播向所有服务器发送提交消息。 4. 节点收到提交消息后，将事务的写入操作应用到本地数据库，并释放为该事务持有的所有锁；收到中止消息后，委托节点中止事务并释放所有锁，其他节点忽略该消息。该算法利用原子广播的顺序对冲突事务进行序列化，最终事务顺序由 < t, WSt > 消息的顺序决定，冲突检测通过锁实现。 ### 1.4 节点恢复 为支持节点恢复，每个节点将每个已提交事务的信息存储在非复制的持久日志中（由UDS模块的PER - API维护）。日志写入在相应事务的上下文中进行，UDS确保若事务提交，日志更新也会提交。日志由一个包含三列的表格组成：事务序列号、事务唯一标识符和事务执行的更改集，每行对应一个事务日志记录。 由于日志大小有限，恢复有两种方式：一是传输整个数据库的内容；二是使用日志中的信息重放恢复节点错过的事务。 投票和非投票算法在本地节点处于多数分区时按上述方式运行。若节点因故障或网络分区处于少数分区，则停止处理写事务，系统可配置为允许只读事务在少数分区读取（可能过时）的数据。 为支持恢复过程，一致性协议维护服务器成员的三种互补视图： - 最新进程组视图P(t)：包含在时间t能够处理事务的所有节点。 - 恢复组视图R(t)：包含在时间t与P(t)中的节点相连的所有节点，包括进程组视图和正在更新状态但尚未能处理事务的节点。 - 静态组视图S：包含系统中的所有节点，在初始节点配置中指定，该视图是静态的，不随时间变化。 节点恢复的具体步骤如下： 1. 恢复节点r加入副本组，进入R(t)。 2. 恢复期间，最新进程组视图中的进程可继续接受和处理新事务。恢复节点需立即开始收集收到的所有事务，但由于其状态未更新，这些更新将处于挂起状态。将第一个加入挂起状态的事务的唯一标识符（非序列号）存储在变量pendingr中。 3. 从P(t)中选择一个节点p作为恢复节点的对等节点，负责帮助恢复节点同步数据库。 4. 恢复节点r向p发送其成功处