文档介绍：第五章 分布式系统完整性解决方案
§
本机内多任务并行带来的困难
多机并行带来的困难
网络延迟不可预测
系统中存在多个副本，数据的修改通常会在不同的副
本上进行
分布式系统数据一致性解决方案
第五章 分布式系统中的数据一致性问题
3. 空间数据所存在的特殊困难
跨机图幅的接边问题
拓扑关系的全局动态改变与生成问题
4. 分布式系统中数据一致性保证的不同模型
● 严格一致性：读出的数据始终为最近写入的数据
计算机A
计算机A
计算机A
读x
写x
时刻T1
时刻T2
T2 〉T1，如果两者非常接近，有可能因为网络原因读请求比写请求晚到！
太严格！实现难度极大！几乎不可能！
分布式系统数据一致性解决方案
第五章 分布式系统中的数据一致性问题
● 顺序一致性：只要所有的程序都以一定的顺序运行（即所有程序的访问操作在别的程序看来都是一样的），每个程序的操作都以程序规定的次序实现，结果都应该被接受。
[例1] 程序P1：W（x，1）…
程序P2 ： … R（x）0 R（x）1 …
或者两次都为1，都应该接受。
顺序一致性看似很“弱”，实际很强，对多副本一致性有很强的要求，实际实现也是难以做到的。只能在单一服务器上使用。
分布式系统数据一致性解决方案
第五章 分布式系统中的数据一致性问题
[例2] 程序A 程序B 程序C
a=1; b=1； c=1；
print（b,c） print（a,c） print（a,b）
理论上有90个执行的次序。以a=1开头说明，共有5！=120个顺序，但b=1不能在print（a,c）之后，因此一半是无效的；同理程序C也如此，只剩下30个有效，共90个有效顺序。
但是，打印结果只有6个数字、64种可能。其中，000000和001001显然不可能。
应该承认所有合理的结果。例如，001011，表示执行的次序为：
A=1 print（b,c） b=1 print（a,c） c=1 print（a,b）
A=1 print（b,c） b=1 print（a,c） c=1
分布式系统数据一致性解决方案
第五章 分布式系统中的数据一致性问题
● 因果一致性：可能因果相关的写操作应对所有程序可见并保持顺序一致。并发的写操作在不同计算机上看来可以顺序不同。
[例1] 程序P1：W（x,1） … W（x,3）
P2： R（x）1 W（x,2）
P3： R（x）1 … R（x）2 R（x）3
P4： R（x）1 … R（x）3 R（x）2
符合因果一致性要求，但违反了顺序一致性。因为P3和P4见到访问顺序不同。
分布式系统数据一致性解决方案
第五章 分布式系统中的数据一致性问题
[例2] P1： W（x,1） …
P2： … R（x）1 W（x,2）
P3： … R（x）1 R（x）2
P4： … R（x）2 R（x）1
违反了因果一致性。因为P2读出了x=1，所以P1和P2的两个写操作顺序必定为W（x,1）在W（x,2）前。 P3的结果才是正确的。
因果一致性在实现时必须建立与维护依赖图，这里涉及到语义上的以来，是相当困难的。
分布式系统数据一致性解决方案
第五章 分布式系统中的数据一致性问题
● PRAM一致性：一个程序的写操作被其他进程以指定的顺序见到，不同程序的写操作在不同程序看来次序可以不同。
[例1] P1： W（x,1） …