第八章分布式数据管理.doc

第八章分布式数据管理.doc第八章分布式数据管理
分布式系统中一个重要的问题是数据的复制问题，为了提高可靠性和提高数据的访问性能，数 据往往有多个副本，分别存放在系统中的不同物理节点上。例如一个文件如果在不同的节点上有多 个副本，当一个失效时，对该文件的访问可以切换到另一个副本上继续进行。另外，使用多副本文 件可以更好地保护文件不受损害。在一个大规模的分布计算系统中，如果数据以单副本的形式集中 存放在一个机器上，这个机器就成为整个系统的瓶颈。其他机器上的进程对该文件的访问必须通过 网络来完成，势必影响远程进程访问文件的性能。如果在不同的机器上有多个副本的话，进程可以 就近访问本地的文件副本。
与分布式数据管理相关的一个主要问题是如何保持多副本数据的一致性。分布式系统的许多方 面和多副本数据的一致性有关，如分布式文件系统、分布式数据库系统和分布式共享存储器等。
一致性模型
当数据有多个副本的时候，一个重要的问题是如何保持多个副本的一致性。也就是说，当一个 副本更新后，我们需要保证其他的副本也同样得到更新。否则的话，两个副本的内容就会不同。
一致性模型是进程和数据存储之间的一个基本约定。也就是说，如果进程对数据的访问遵守特 定的规则，那么数据存储就能够正确地进行。一般地来说，一个进程如果对一个数据项施加一个读 操作，那么期望读操作的返回值就是最后一次对该数据项进行写所得的结果。由于在分布计算系统 中没有一个全局的时钟，很难精确地定义哪个写操作是最后一个。为此，需要提供其他一些定义， 不同的定义对应着不同的一致性模型。每个一致性模型对施加在一个数据项上的读操作所能返回的 值进行了限制，下面按这种限制由强到弱的顺序逐步介绍各种不同的一致性模型。关于一致性模型 的更进一步的讨论可以参考[MOSBERGER. 1993] W [ ADVE, 1996] <>

严格一致性(strict consistency)模型是限制最严格的一 ''一致性模型。对于严格一致性模型来 说，对一个数据项所进行的任何读操作所返回的值总是对该数据项最近一次进行写操作的结果。严 格一致性模型隐含地假定有一个全局的绝对时钟，所以“最近”的定义是明确的。单机系统上采用 严格一致性模型是理所当然的。但是在分布计算系统中，数据可能存在多个副本并且分布在多个机 器上，并可以被多个进程访问，所以实现严格一致性协议是非常困难的。
即使是存在一个全局时钟，并且数据只有一个副本存放在一个机器上，要实现严格一致性模型 也是很困难的。例如一个数据X存放在机器B上，机器A上的一个进程P读这个数据，虽然读的 时候，数据是最新的，但是当这个最新值由机器B向机器A传送时，机器B上的另一个进程Q对 该数据X进行写，当进程P得到数据X的值的时候，该值已经过时了。
为了方便地描述一致性模型，，从左到右的方向是时 间前进的方向。进程R对数据项x写入值a的操作用Wi(x)a来表示，R(x)b表示进程R对数据项x 读，返回值为b。假定任何数据的初始值为NIL。
例如，(a)中，数据X有两个副本分别在进程Pi和进程P2所在节点，Pi对数据项x 写入值a,它首先对x在Pi处的副本进行修改，随后将此修改传播到其他副本。P2随后读x,读得 的值为
a。所以符合严格一致性的规定。
节 点的副本上，所以P2的第一次读操作得到的返回值为NIL。而P2进行第二次读时，Pi写的结果已 经传播到P2所在节点的副本上，所以P2的第二次读操作得到的返回值为a。所以不符合严格一致 性的规定。
P,: W|(x)a Pi： W|(x)a
P2: R2(x)a P2: R2(x)NIL R2(x)a
⑷ (b)
图& (a)符合严格一致性(b)不符合严格一致性

比严格一致性模型的限制稍弱的一致性模型是顺序一致性(sequential consistency)模型。它最 初是由Lamport定义的，作为多处理机系统共享内存的语义。顺序一致性模型需要满足下列条件： 所有进程对数据项的所有操作可以认为是按照某个顺序进行的，任何进程对这个顺序的观点是 一样的。当然这个顺序不一定是物理意义上顺序。这说明当进程在不同的机器上并发执行的时候， 对数据项的读写操作的任何合法的交叠顺序都是可以接受的，所有进程所见到的交叠是完全相同 的。这里并不涉及到时间的问题，也不涉及到"最近”写操作的问题。
图&。(a)中，进程比对数据项x写入a, “随后”(物理时间意义上的)进程P2对数据项x写入b。然而进程P3和进程旳都是先读到值b, 后读到值a。即从所有进程的观点来看