分布式 DBMS - 复制控制

本章探讨复制控制，这是在所有站点中维护一致数据所必需的。我们将研究复制控制技术以及复制控制所需的算法。

如前所述，复制是分布式数据库中使用的一种技术，用于在不同站点存储数据表的多个副本。在多个站点中拥有多个副本的问题是维护数据一致性的开销，特别是在更新操作期间。

为了保持所有站点的数据相互一致，需要采用复制控制技术。复制控制有两种方法，即 -

  • 同步复制控制
  • 异步复制控制

同步复制控制

在同步复制方法中，数据库是同步的，因此所有复制始终具有相同的值。请求数据项的事务将有权访问所有站点中的相同值。为了确保这种一致性，更新数据项的事务被扩展，以便它在数据项的所有副本中进行更新。通常，使用两阶段提交协议来达到此目的。

例如，让我们考虑一个数据表 PROJECT(PId, PName, PLocation)。如果 PLocation 是“孟买”，我们需要运行事务 T1 将 PLocation 更新为“孟买”。如果没有复制，事务 T1 中的操作将是 -

Begin T1: 
   Update PROJECT Set PLocation = 'Mumbai' 
   Where PLocation = 'Bombay'; 
End T1;

如果数据表在站点 A 和站点 B 中有两个副本，则 T1 需要生成与这两个站点对应的两个子项 T1A 和 T1B。扩展后的交易 T1 将是 -

Begin T1: 
   Begin T1A : 
      Update PROJECT Set PLocation = 'Mumbai' 
      Where PLocation = 'Bombay'; 
   End T1A;  
	
   Begin T2A : 
      Update PROJECT Set PLocation = 'Mumbai'
      Where PLocation = 'Bombay'; 
   End T2A; 
	
End T1;

异步复制控制

在异步复制方法中，副本并不总是保持相同的值。一个或多个副本可能存储过时的值，并且事务可以看到不同的值。使所有副本达到当前值的过程称为同步。

一种流行的同步方法是存储转发方法。在这种方法中，一个站点被指定为主站点，其他站点被指定为辅助站点。主站点始终包含更新的值。所有的交易首先进入主站点。然后，这些事务将在辅助站点中排队等待应用。仅当计划在辅助站点上执行事务时，才使用转出方法更新辅助站点。

复制控制算法

一些复制控制算法是 -

  • 主从复制控制算法。
  • 分布式投票算法。
  • 多数共识算法。
  • 流通代币算法。

主从复制控制算法

有 1 个主站点和“N”个从站点。主算法在主站点运行以检测冲突。从属算法的副本在每个从属站点运行。整体算法分以下两个阶段执行 -

  • 事务接受/拒绝阶段- 当事务进入从站点的事务监视器时，从站点向主站点发送请求。主站点检查冲突。如果没有任何冲突，主站将向从站发送“ACK+”消息，然后从站开始事务申请阶段。否则，主设备将向从设备发送“ACK-”消息，然后从设备拒绝该事务。

  • 事务应用阶段- 进入此阶段后，事务已进入的从站站点向所有从站广播执行事务的请求。收到请求后，对等从属设备执行事务并在完成后向发出请求的从属设备发送“ACK”。请求从站收到来自所有对等方的“ACK”消息后，它会向主站发送“DONE”消息。主设备知道事务已完成并将其从待处理队列中删除。

分布式投票算法

这由“N”个对等站点组成，所有这些站点都必须在事务开始执行之前“确定”该事务。以下是该算法的两个阶段 -

  • 分布式事务接受阶段- 当事务进入站点的事务管理器时，它会向所有其他站点发送事务请求。收到请求后，对等站点使用基于优先级的投票规则解决冲突。如果所有对等站点都对事务“OK”，则请求站点开始申请阶段。如果任何对等站点未“确定”事务，则请求站点将拒绝该事务。

  • 分布式事务应用阶段- 进入此阶段后，事务进入的站点向所有从站广播执行事务的请求。收到请求后，对等从属设备执行事务并在完成后向发出请求的从属设备发送“ACK”消息。在发出请求的从属设备收到来自所有对等方的“ACK”消息后，它会让事务管理器知道事务已完成。

多数共识算法

这是分布式投票算法的一种变体，在分布式投票算法中，当大多数节点“OK”交易时，交易就被允许执行。这分为三个阶段 -

  • 投票阶段- 当交易进入站点的交易管理器时，它会向所有其他站点发送交易请求。收到请求后，对等站点使用投票规则测试冲突，并将冲突的事务（如果有）保留在待处理队列中。然后，它发送“OK”或“NOT OK”消息。

  • 交易接受/拒绝阶段- 如果请求站点收到交易的多数“OK”，则它接受交易并向所有站点广播“ACCEPT”。否则，它向所有站点广播“REJECT”并拒绝交易。

  • 交易应用阶段- 当对等站点收到“拒绝”消息时，它会从其待处理列表中删除该交易，并重新考虑所有推迟的交易。当对等站点收到“接受”消息时，它会应用该事务并拒绝待处理队列中与该事务冲突的所有延迟事务。完成后，它会向发出请求的从机发送“ACK”。

流通代币算法

在这种方法中，系统中的事务使用循环令牌进行序列化，并针对数据库的每个副本相应地执行。因此，所有交易都被接受，即没有交易被拒绝。这有两个阶段 -

  • 事务序列化阶段- 在此阶段，所有事务都计划按序列化顺序运行。每个站点中的每笔交易都会被分配一个来自连续序列的唯一票证，指示交易的顺序。一旦交易被分配了票证，它就会被广播到所有站点。

  • 交易应用阶段- 当站点收到交易及其票据时，它会根据其票据放置交易以执行。交易完成执行后，该站点会广播适当的消息。当事务在所有站点中完成执行时结束。