文档介绍：第五章分布式系统完整性解决方案§ ,数据的修改通常会在不同的副本上进行 1 1 第五章分布式系统中的数据一致性问题 3. 空间数据所存在的特殊困难跨机图幅的接边问题拓扑关系的全局动态改变与生成问题 4. 分布式系统中数据一致性保证的不同模型●严格一致性:读出的数据始终为最近写入的数据计算机 A 计算机 A 计算机 A 读x 写x 时刻 T 1时刻 T 2T 2〉 T 1,如果两者非常接近,有可能因为网络原因读请求比写请求晚到! 太严格!实现难度极大!几乎不可能! 2 2 第五章分布式系统中的数据一致性问题●顺序一致性:只要所有的程序都以一定的顺序运行(即所有程序的访问操作在别的程序看来都是一样的), 每个程序的操作都以程序规定的次序实现,结果都应该被接受。[例 1] 程序 P 1:W(x,1)…程序 P 2:… R (x) 0 R (x) 1 …或者两次都为 1,都应该接受。顺序一致性看似很“弱”,实际很强,对多副本一致性有很强的要求,实际实现也是难以做到的。只能在单一服务器上使用。 3 3 第五章分布式系统中的数据一致性问题[例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 4 4 第五章分布式系统中的数据一致性问题●因果一致性:可能因果相关的写操作应对所有程序可见并保持顺序一致。并发的写操作在不同计算机上看来可以顺序不同。[例 1] 程序 P 1:W( x,1 )… W ( x,3 ) P 2:R(x) 1 W ( x,2 ) P 3:R(x) 1 … R (x) 2 R (x)3 P 4:R(x) 1 … R (x) 3 R (x)2 符合因果一致性要求,但违反了顺序一致性。因为 P 3和P 4见到访问顺序不同。 5 5 第五章分布式系统中的数据一致性问题[例 2] P 1:W( x,1 )… P 2:… R (x) 1 W ( x,2 ) P 3:… R (x) 1 R (x)2 P 4:… R (x) 2 R (x)1 违反了因果一致性。因为 P 2读出了 x=1 ,所以 P 1和P 2的两个写操作顺序必定为 W( x,1 )在 W( x,2 )前。 P 3的结果才是正确的。因果一致性在实现时必须建立与维护依赖图,这里涉及到语义上的以来,是相当困难的。 6 6 第五章分布式系统中的数据一致性问题● PRAM 一致性:一个程序的写操作被其他进程以指定的顺序见到,不同程序的写操作在不同程序看来次序可以不同。[例 1] P 1:W( x,1 )… P 2:… R (x) 1 W ( x,2 ) P 3:… R (x) 1 R (x)2 P 4:… R (x) 2 R (x)1 符合 PRAM 一致性的要求。 PRAM 与顺序一致性的差别在于,后者虽然为确定语句的顺序,但要求所有程序遵从共同的顺序;而前者则允许不同程序见到的顺序可以不同。 7 7 第五章分布式系统中的数据一致性问题[例 2] 在前面的例子中,结果 001001 是可以接受的。这时, 各程序看到的顺序: 程序 A a=1 Print ( b,