算法介绍

分布式计算机系统的要求刺激了将相同信息的副本保存在计算机网络中的不同节点的兴趣。

数据复制允许信息位于其使用点附近,可以通过在高使用区域中静态定位副本,也可以根据需要动态创建临时副本。

通过允许许多节点并行处理对相同信息的请求,数据复制也增加了数据的可用性,并掩盖部分系统故障。

因此,在某些情况下,维护副本的成本会被复制数据所提供的性能,通信成本和可靠性优势所抵消。

新算法

我们提出了一种维护复制文件的新算法。

该算法可以通过以下描述简要表征:

  • 为复制文件的每个副本分配一定数量的投票。

  • 每个事务收集读取法定数量的r票数以读取文件,以及写入法定数量的w票数以写入文件,使得r + w大于分配给文件的总票数。

  • 这可确保每个读取仲裁与每个写入仲裁之间存在非空交集。 总是有一个文件代表的子集,其总票数为w当前。

  • 因此,所收集的任何读取法定数量都保证具有当前副本。

  • 版本号可以确定哪些副本是最新的。

该算法具有许多理想的属性:

  • 它继续正确运行,具有不可访问的副本。

  • 它由少量额外的机器组成,运行在事务文件系统之上。 虽然“投票”的发生将在本文后面发现,但是不需要基于复杂消息的协调机制。

  • 它提供了串行一致性。 换句话说,每个事务似乎都在运行它。始终向用户提供最新版本的数据。

  • 通过操纵r,w和复制文件的投票结构,系统管理员可以更改文件的性能和可靠性特征。

  • 创建的所有文件的额外副本(包括用户本地磁盘上的临时副本)都可以合并到我们的框架中。

本文的其余部分“分为五个部分。

第2部分描述了相关工作,以及该算法与以前的解决方案有何不同。

算法的环境,接口和基本结构在第3节中介绍。

第4节提供了改进,包括引入临时副本和新的锁定技术。

Violet 系统包含此提案的实现,以及一些性能考虑因素,将在第5节中讨论。

最后一节是一个简短的结论。附录说明我们的算法保持了串行一致性。

本文中的想法在Mesa中得到了说明,Mesa是在Xerox Palo Alto研究中心开发的一种编程语言。

Mesa非常适合这项任务,因为它包含对进程,监视器和条件变量的集成支持。

为了简化此演示,Mesa示例中省略了一些不必要的细节。

相关工作

以前用于维护复制数据的算法分为两类。

有些人坚持认为每个对象都有一个主要站点,负责更新仲裁。

分布式INGRES就是这样一个系统。 这种技术很简单,但相对不灵活。

其他人不使用对象的区分站点,并且比主站点算法更复杂。

SDD-1通过通过通信系统发送更新来保持对象的所有副本是最新的,该通信系统将通过机器崩溃来缓冲消息。

托马斯的提议只要求更新对象的大部分副本,并包括投票。

虽然我们分享投票的概念,但很难直接将我们的算法与Thomas’进行比较,因为这两者提供了不同的服务。

值得注意的是:

  • 我们保证查询的串行一致性(只读事务),而Thomas的算法则不然。

  • 我们不会坚持要更新对象的大部分副本。

  • Thomas的算法不使用加权选民,这限制了它的灵活性。

  • 托马斯的算法更复杂,因为它解决了一致性问题以及复制问题。 我们将两者分开,从而产生一种更容易推理和实现的算法。

  • 我们的结构允许包含临时副本。

3. 基本算法

3.1 环境

实现我们的算法所需的概念在下面被建模为稳定的文件系统。

在3.3节中,假设存在这样的系统,我们为复制数据构建算法。

我们的博览会使用两种对象,文件和容器。 文件是字节数组,通过读写操作寻址,如下所述。

容器是文件的存储库; 它们旨在表示存储设备,例如磁盘驱动器。 这些对象以及本文稍后介绍的其他对象具有唯一的名称。

即使它们位于不同的计算机上,也不会为两个对象分配相同的名称。

我们不会进一步关注程序如何获取名称,但会假设容器名称和感兴趣的文件即将到来。

逻辑上,文件是可以创建,删除,读取和写入的字节数组。

File.Create:PROCEDURE [container:Container.ID] RETURNS [file:File.ID],
File.Delete:PROCEDURE [file:File.ID];
File.Read: PROCEDURE [file:File.ID,startByte,count:INTEGER,Buffer:Pointer]
File.Write:PROCEDURE [file:File.ID,startByte,count:INTEGER,Buffer:Pointer]

为了简化讨论,我们假设文件系统原语在远程和本地文件上运行。

这可以通过将文件的位置或容器编码为其唯一标识符,或者通过维护远程文件的位置提示来实现。

这些细节将不再进一步考虑。

事务用于定义并发控制和故障恢复的范围。

事务是由开始事务调用和提交事务调用括起来的一组相关文件操作。

Transaction.Begin:PROCEDURE,
Transaction.Commit:PROCEDURE;

事务通过使其在文件操作中看起来不是系统中的其他活动(称为串行一致性的属性)来隐藏并发性。

事务隐藏了可以从中恢复的不良事件,例如检测到的磁盘读取错误或服务器崩溃。

事务还保证执行其所有写操作,或者不执行任何操作。

此外,一旦事务提交,其效果必须适应硬件故障,例如服务器崩溃。

每个进程都有一个当前事务。

因此,对于使用两个事务的应用程序,它必须创建至少两个进程。

分叉进程可以通过调用以下方式加入其父进程:

Transaction.JoinParentsTransaction:PROCEDURE;

如果文件所在的服务器已关闭,或者存在通信故障,则该文件可能不可用。

如果将读取操作定向到不可用的文件,则使用相应的文件。

读请求永远不会返回。我们的算法使用多个进程来允许它在这种情况下继续进行。

未完成的未完成读取,因为它们从未发生过,不会影响事务提交的能力。

事务系统仅保证在提交事务时实际完成的读取的串行一致性。

同样,如果写操作指向不可用的文件,相应的文件。

写请求永远不会返回。但是,尝试省略未完成写入的事务将保持未提交状态,直到其所有写入完成。

用户可能想要中止正在进行的事务。事务中止(可由用户启动,如下所示)将丢弃所有事务的写入,并终止事务。

Transaction.Abort:PROCEDURE,

由于服务器崩溃,通信故障或锁定冲突,文件系统也可能会自动中止事务。

这结束了我们的原始对象和操作的模型集。 该模型将合作计算机的联盟抽象为具有统一命名和分布式事务文件系统的结构。

正如我们将在后面的章节中看到的,这里介绍的抽象使复制算法直接解释。

当然,我们相信我们所描述的模型是可实现的和实用的; 事实上,实施所需的思想受到了极大的关注。

Gray提供了对两阶段提交协议,锁定和同步原语的精彩讨论。 Lampson和Sturgis描述了一个具有我们所有属性的已实现系统 模型要求。

TODO…

个人得失

  1. 英文能力非常重要。否则感觉找不到自己想要的东西。

  2. 查找过程

根据关键词 Gifford, 1979 搜索到 wiki

根据脚注,找到论文:Weighted Voting for Replicated Data

  1. 论文

论文作为一手的信息资料,虽然花费的时间会比看一个简短的文章时间多,但这是一种学习的方式。

下午需要将这个论文全部翻译一遍。

拓展阅读

WRN 算法

Paxos 算法

参考资料

论文

Weighted Voting for Replicated Data

Paxos 和 WRN 算法的区别

Quorum (distributed computing)