一致性模型

2020-06-19 04:04:30

Jepsen分析分布式系统的安全属性-最值得注意的是,识别一致性模型的违规行为。但是什么是一致性模型呢?他们允许什么现象?给定的程序真正需要什么样的一致性?

在本参考指南中,我们为工程师和学者提供了各种一致性模型的基本定义、直观解释和理论基础。

分布式系统是并发系统的一种,很多关于并发控制的文献都直接应用于分布式系统,实际上,我们将要讨论的大多数概念最初都是针对单节点并发系统而提出的。然而,在可用性和性能方面有一些重要的区别。

系统具有随时间变化的逻辑状态。例如,一个简单的系统可以是一个整数变量,其状态类似于0、3和42。一个互斥体只有两种状态:锁定或解锁。键值存储的状态可以是键到值的映射,例如:{cat:1,dog:1}或{cat:4}。

进程1是执行计算和运行操作的逻辑单线程程序。流程从来不是异步的-我们通过独立的流程对异步计算进行建模。我们说“逻辑单线程”是为了强调,虽然一个进程在某个时刻只能做一件事,但它的实现可以跨多个线程、操作系统进程,甚至是物理节点-只要这些组件提供了连贯的单线程程序的错觉。

操作是从状态到状态的转换。例如,单变量系统可能有读和写这样的操作,分别获取和设置该变量的值。计数器可能有递增、递减和读取等操作。SQL存储可能会有选择和更新等操作。

从理论上讲,我们可以给每个州的过渡起一个唯一的名字。锁正好有两个过渡:锁定和解锁。整数寄存器的读取和写入次数是无限的:读取值-1、读取值-2、…。和WRITE-1、WRITE-2、…。。

为了使其更易于处理,我们将这些转换分解为读、写、cas、增量等函数,以及将这些函数参数化的值。在单个寄存器系统中,可以写入1:

在给定键值存储的情况下,我们可能会将键“a”的值递增3,如下所示:

在事务性存储中,值可以是复杂的事务。在这里,我们在单个状态转换中读取a的当前值,查找2,并将b设置为3:

一般来说,手术需要时间。在多线程程序中,操作可能是函数调用。在分布式系统中,操作可能意味着向服务器发送请求并接收响应。

为了对此进行建模,我们假设每个操作都有一个调用时间,并且,如果它完成了,则完成时间要严格更长,这两个时间都是由Animaginary 2给出的,完全同步,全局可访问的时钟。3我们将这些时钟称为提供实时顺序的时钟,而不是仅跟踪因果顺序的时钟。4.。

由于操作需要时间,因此两个操作可能在时间上重叠。例如,给定两个操作A和B,A可以开始,B可以开始,A可以完成,然后B可以完成。我们说两个操作A和B是并发的,如果在这段时间内A和B都在执行。

进程是单线程的,这意味着同一进程执行的两个操作永远不会是并发的。

如果操作由于某种原因没有完成(可能是因为它在关键组件崩溃时超时),则该操作没有完成时间,一般情况下,必须将其与调用后的每个操作视为并发。它可能会执行,也可能不会执行。

具有操作的进程处于此状态实际上是停滞的,并且永远不能再次调用另一个操作。如果它调用另一个操作,它将违反我们的单线程约束:进程一次只做一件事。

一些论文将其描述为一组操作,其中每个操作包括两个数字,表示它们的调用和完成时间;并发结构是通过比较进程之间的时间窗口来推断的。

Jepsen将历史表示为调用和完成操作的有序列表,有效地将每个操作一分为二。对于迭代历史的算法来说,这种表示法更方便,保持了对并发操作和可能状态的表示。

一致性模型是一组历史记录。我们使用一致性模型来定义系统中哪些历史记录是“好的”或“合法的”。当我们说历史“违反可序列化”或“不可序列化”时,我们的意思是历史不在可序列化历史集中。

如果A是B的子集,我们说一致性模型A蕴含模型B。例如,可线性化意味着序列一致性,因为每个可线性化的历史也是序列一致的。这允许我们在层次结构中关联一致性模型。

非正式地说,我们将较小、限制性较强的一致性模型称为“较强”,将较大、较宽松的一致性模型称为“较弱”。

并不是所有的一致性模型都是直接可比较的。通常,两个模型允许不同的行为,但都不包含另一个。