存档

文章标签 ‘一般一致性’

存储一致性之一般一致性(General Consistency)和因果一致性(Causal Consistency)

2011年5月6日 sigma 4 条评论 70,253 views

相比于严格一致性顺序一致性虽然放松了限制条件,但是对性能的影响还是很大,因此出现了一般一致性和因果一致性。 一般一致性的定义是:

一个系统支持一般一致性,当每个处理机所执行的所有写已被完成时,如果一个内存位置的所有副本最终地包含同样的数据。

  因果一致模型(Hutto和Ahamad,1990)是顺序一致的淡化,它按有无可能的潜在因果联系来区分各事件。 假设进程P1写变量x,然后P2读出x,写入y。这里读出x和写入y之间可能有潜在的因果联系,因为y的计算很可能决定于P2读到的x值(即P1写入的值)。 另一方面,若两进程自然而同时地写两个变量,就没有因果联系。先有读操作之后执行写操作,两个事件就可能有因果联系。相似的,读和提供所读数据的写有因果关系。没有因果关系的操作称为并发的(concurrent)。 因果一致性定义:

A system provides causal consistency if memory operations that potentially are causally related are seen by every node of the system in the same order. Concurrent writes (i.e. ones that are not causally related) may be seen in different order by different nodes.

中译为:

因果一致的存储器应遵守以下条件:可能因果相关的写操作应对所有进程可见,且顺序一致。并发写操作在不同机器看来顺序可能是不同的。

在下图(a)中,W(x)b可能决定于W(x)a,因为 b可能是R(x)a所读的值计算的结果,两个写操作是因果联系的,所有进程必须视它们为同一顺序。因此(a)不正确。(b)中,读被取掉,W(x)a和W(x)b变为并发事件。因果一致性存储器不要求并发写有全局一致的次序,因此(b)是正确的。   实现因果一致性需要由记录来跟踪哪个进程看到哪个写操作。这要建立和维护一个依赖图:即一个操作依赖于其他什么操作。一种实现方法是使用向量时间戳。这样做需要一些额外的开销。

无觅相关文章插件,快速提升流量