分布式系统数据一致性解决方案

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 分布式系统完整性解决方案,1.分布式系统中数据一致性存在的困难,1.高度并行带来的问题,本机内多任务并行带来的困难,多机并行带来的困难,网络延迟不可预测,2.多副本带来的问题,系统中存在多个副本，数据的修改通常会在不同的副,本上进行,第五章 分布式系统中的数据一致性问题,3. 空间数据所存在的特殊困难,跨机图幅的接边问题,拓扑关系的全局动态改变与生成问题,4. 分布式系统中数据一致性保证的不同模型,严格一致性：读出的数据始终为最近写入的数据,计算机A,计算机A,计算机A,读x,写x,时刻T,1,时刻T,2,T,2,T,1,，如果两者非常接近，有可能因为网络原因读请求比写请求晚到！,太严格！实现难度极大！几乎不可能！,第五章 分布式系统中的数据一致性问题,顺序一致性：只要所有的程序都以一定的顺序运行（即所有程序的访问操作在别的程序看来都是一样的），每个程序的操作都以程序规定的次序实现，结果都应该被接受。,例1 程序P,1,：W（x，1）,程序P,2,：,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 程序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,见到访问顺序不同。,第五章 分布式系统中的数据一致性问题,例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,的结果才是正确的。,因果一致性在实现时必须建立与维护依赖图，这里涉及到语义上的以来，是相当困难的。,第五章 分布式系统中的数据一致性问题,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,与顺序一致性的差别在于，后者虽然为确定语句的顺序，但要求所有程序遵从共同的顺序；而前者则允许不同程序见到的顺序可以不同。,第五章 分布式系统中的数据一致性问题,例2 在前面的例子中，结果001001是可以接受的。这时，各程序看到的顺序：,程序A,a=1,Print（b,c）,程序B,a=1,Print（a,c）,C=1,程序C,a=1,Print（a,b）,b=1,这里只列出本程序感兴趣（与自己的打印有关）的语句执行次序,第五章 分布式系统中的数据一致性问题,PRAM一致性要求虽然较弱，但它要求程序的写操作必须被其他程序看到（尽管他们的顺序可以不同）。实际上，这样的要求有点过高，每一个程序只要能够看到与自己有关的其他程序的写操作就可以了。,弱排序：弱排序只要求对共享数据结构的访问保证顺序一致性。即：,对同步变量（可与信号量类比）的访问是顺序一致的；,在所有以前的写操作结束之前，不的访问同步变量；,在先前所有的同步变量访问完成以前，不得访问共享数据。,第五章 分布式系统中的数据一致性问题,实现考虑：,为保证第一点，对同步变量的访问必须立即广播。在广播完成之前，其他程序不的访问别的同步变量；,对第二点，强制要求所有的同步访问开始前，已经开始的所有的写操作必须完成，在更新共享数据后立即进行同步，将新值传遍所有副本；,第三点，保证在读共享数据之前，完成同步操作，以便可以读到最新值。,做法：,任何程序编制时，在对共享数据写操作后都必须紧接着访问同步变量；,任何读共享数据操作前，访问同步变量。,例如：,P,1,：W（x,1） S,1,W（y,2）S,2,P,2,： S,1,R（x）1,P,3,: s,2,R（y）2,弱一致性的缺陷在于没有区分对共享变量的修改与读取。所以同步变量的访问即要确保本地写全部完成（所有副本均已更新）还要收集其它计算机的写操作信息。,第五章 分布式系统中的数据一致性问题,释放一致性：类似临界区，提供“获取”和“释放”两类原子同步操作。强制：,程序在访问共享变量之前必须成功完成“获取”操作；,完成“释放”操作前，程序的访问操作必须结束；,“获取”、“释放”应保证顺序一致性。,释放一致性与用信号量和P、V操作来保证临界区访问正确性何其相似乃尔！,与此相对应，还可以有入口一致性。,第五章 分布式系统中的数据一致性问题,小结：,一致性模型可以分为两类：,不使用同步操作,严格：所有访问时间绝对顺序,顺序：所有程序以相同顺序检测所有,共享访问事件,因果：所有程序以相同顺序检测所有,因果联系事件,PRAM：所有程序按预定次序到来自一,台机器的写操作，来自其他机,器的写操作顺序不必相同,最强,使用同步操作,弱：同步完成后共享数据才保持一致,释放：离开临界区后共享数据才保持,一致,入口：进入临界区时共享数据保持一致,第五章 分布式系统中的数据一致性问题,5.实现问题,维护副本一致性的两种策略：,写有效：修改本地数据时，将修改值组播所有副本节点，副本节点据此修改本地数据。,要求修改传送次序严格保证。,每次修改必须传送修改值，网络开销大,写无效：修改本地数据前，通知所用副本停止使用（无效），组播完成后才进行修改。其他副本需使用前，向它申请发送修改值，进行修改后再使用。,多次修改可能一次传送，但每次需发送无效通知。,第五章 分布式系统中的数据一致性问题,2.对分布式文件系统的要求,1. 存取透明性,用户无须知道文件的分布，传统的本地文件操作手段可以直接用于远程文件操作，对已有的用户程序不必刻意进行改动就可以适应分布式环境。,用户无须注意环境中其他用户是否与自己竞争使用同一个文件，无须用户在自己的程序中对共享文件数据添加并发控制，并能保持文件数据的完整性。,2.位置透明性,用户看到的是全局的文件名空间，文件或文件组在机器间迁移和重新定位时不必改变其路径，用户程序无须改动。无论用户处于哪个节点，看到的是相同的文件名空间。出于可靠性考虑，同一个文件可能在不同的节点上保留副本，副本的使用对用户无关，用户意识不到当前使用的是哪一个副本,第五章 分布式系统中的数据一致性问题,3.,故障透明性,在文件服务执行过程中发生故障并修复（例如文件服务器故障，启用备用服务器；网络传输故障，需要重发等）对用户屏蔽。,4. 性能透明性,用户不会感到由于远程存取文件而带来性能上的显著降低。此外，还应该满足硬件和本地操作系统的异构性，客户端和服务器端的软件可以在不同的硬件和本地操作系统上运行。因此接口定义必须良好。,5. 可扩展性,系统必须具备增量扩展的能力，以适应负载和网络扩充的需要。,需要指出的是，目前这个问题还在研究和探讨中，还没有一个系统完全实现这种能力。特别是系统扩展到包含大量有源节点的网络时，这个问题就更加突出。,第五章 分布式系统中的数据一致性问题,6.,支持细粒度数据存取,尽可能支持用户对细粒度数据的访问。这要求制定和实现更加完备的数据请求协议。,这个问题在空间数据分布式处理系统中更为突出。,7. 网络分割适应性,尽可能适应网络动态分割的情形，避免由于网络的分割和重组引起系统的问题，影响用户的使用。,第五章 分布式系统中的数据一致性问题,3.分布式文件系统的组成,用户程序,用户程序,用户程序,文件系统组件,客 户 组 件,展 开 文 件 服 务,目录服务,目录服务RPC接口,用户程序接口,展开文件RPC接口,第五章 分布式系统中的数据一致性问题,其中：,展开文件服务提供了一个远程调用接口供用户程序使用。它与目录服务结合起来，为文件的存取提供一系列复杂的操作。,客户组件则将展开文件服务和目录服务所提供的功能组织和集成在一起，辅以统一的接口，向用户提供单一的编程接口，是用户就向使用传统文件系统那样来使用分布式文件系统。,第五章 分布式系统中的数据一致性问题,1. 展开文件服务,展开文件服务主要实现对文件内容的操作。在展开文件服务中，文件通过标识符来识别。通常，文件表示符用一个长整数来表示，以便保证分布式系统中所有文件表示的唯一性。文件标识符在创建文件和打开时产生并向用户返回，与传统方式一样。,展开文件服务的模型根据文件系统设计的要求来组织，提供一个简单通用的操作集合。原则上，这些操作及和与传统的文件系统提供的服务并无两样。,在分布式环境中，传统的文件控制块内容也发生了变化，,文件的保护也是由文件展开服务来实现的。其实现技术与传统方法一样，例如通过存取控制表、存取域等。,第五章 分布式系统中的数据一致性问题,文 件 名,文 件 长 度,创 建 时 间 邮 戳,读 时 间 邮 戳,写 时 间 邮 戳,属 性 时 间 邮 戳,用 户 计 数,文 件 所 有 者,文 件 类 型,存 取 权 限 表,文 件 控 制 快,展开文件服务负责维护其中文件长度、创建时间邮戳、读时间邮戳、写时间邮戳、属性时间邮戳等。而另外的一些属性则由目录服务来维护。文件展开服务提供某些访问和修改文件属性的原语，供目录服务使用。也允许用户自己定义部分属性。,文件的保护也是由文件展开服务来实现的。其实现技术与传统方法一样，例如通过存取控制表、存取域等。,第五章 分布式系统中的数据一致性问题,两类文件展开服务,客 户机,服务器,下载,上载,在客户机上修改,老文件,新文件,上载/下载模式,客 户机,服务器,远程访问模式,第五章 分布式系统中的数据一致性问题,在上载/下载模式，文件展开服务只提供读文件和写文件两种方式服务，即下载/上在整个文件。概念比较简单，接口非常简洁，服务器端实现也方便。但客户端必须具备较大的空间以便存放整个文件，客户端应该具有复杂的文件访问功能，如读、写、偏移植移动等等。而它们是本地文件系统的事。而且，当客户只需要文件的一小部分时，这种方式显然不够经济，加大了网络的压力和用户空间。,在远程访问模式，展开文件服务提供RPC接口包括打开文件、关闭文件、度、写、修改偏移植、检查/修改属性等等，这些都在服务器端实现。显然这种方式实现复杂，但运行开销（网络开销）较省，只需要传输要求的文件部分，在客户端也不必开辟较大的空间。,第五章 分布式系统中的数据一致性问题,2. 文件目录服务,目录服务提供了文件的创建、删除、命名、改名以及从一个目录下移动到另一个目录下等操作。这些并不涉及文件体的操作，也不涉及文件是整体传输还是远程访问的问题。这里，关键的问题是实现文件名到唯一标识符的转换。,为了完成这种转换，设立了目录文件。目录文件实际上是文件名到唯一标识符的对照表，组织成文件的形式，所以目录文件也有自己的文件标识符。目录允许有子目录，这样用户可以将有关的文件组合到一个目录下。同样，目录服务提供的文件服务对象也包括目录文件。通常，分布式文件系统的目录文件组织成树型结构，从而使整个文件系统呈现出树型结构。不少系统允许目录之间建立指针连接（象UNIX的Link），这样，树型结构就变成了“格”。这在分布式系统中尤其重要。在这里，每个目录中又一个指针计数，表示指向该目录的连接数。,第五章 分布式系统中的数据一致性问题,A,B,C,2,0,1,计算机1,D,E,1,1,计算机2,图中，右上角的数字是指向该文件的目录数量,两台计算机中的目录,第五章 分布式系统中的数据一致性问题,问题：,是否每一个文件都是整个目录树可见的？进而，如果系统中有多个服务器（显然每个服务器上都有一颗独立的目录树），系统是否存在一个全局的根目录？再进一步，能否知道每个文件所在的计算机名？,回答：应该让每一台系统中的计算机知道系统中所有的文件；如果应用需要，应该知道它所需要的文件所在的机器名。但是，不一定需要存在一个全局的根目录。,办法: 1.,文件命名采用 机器名+ 文件路径名,2.,将远程文件安装到本机的分层文件目录结构中,3.,存在并维护一个在所有计算机上单名字空间,第五章 分布式系统中的数据一致性问题,4 分布式系统中地理空间数据一致性保障,1. 全局目录的组织,反映系统全部空间数据的全局数据目录,反映系统全部节点的全局节点目录（含负载）,2. 全局数据目录,采用基于空间位置的数据定位机制,设定主副本节点，,只能由主副本所在节点可以执行相应“写操作”并发起相应数据的同步,数据库复制技术与全局数据目录同步,数据库复制技术与全局数据内容同步,第五章 分布式系统中的数据一致性问题,3. 数据同步时刻规定,同步时刻：“写操作”执行之后、节点动态加入与退出之后,同步内容：数据同步、目录同步,4. 操作分布策略,第一优先：就地计算,第二优先：主副本节点,第三优先：负载平衡,5. 分布计算的组织,计算由并行语句组成,并行语句由执行线索组成,第五章 分布式系统中的数据一致性问题,例 计算任务,BEGIN CONCURRENT,BEGIN THREAD,COPY f_camain TO f_casite1,STCQLsite1(SELECT flight_no, field_name, TSLICE(field, 2004-10-10) AS field,INTO result_ca FROM f_ca, atmosphere,WHERE OVERLAP(TSWEEP(flight_position, 2004-10-10),TSLICE(field, 2004-10-10),COPY result_casite1 TO result_site1main,END THREAD,第五章 分布式系统中的数据一致性问题,BEGIN THREAD,COPY f_camain TO f_casite2,STCQLsite1(SELECT flight_no, field_name, TSLICE(field, 2004-10-10) AS field,INTO result_ca FROM f_ca, atmosphere,WHERE OVERLAP(TSWEEP(flight_position, 2004-10-10),TSLICE(field, 2004-10-10),COPY result_casite2 TO result_site2main,END THREAD,END CONCURRENT,第五章 分布式系统中的数据一致性问题,实现机制示意：,第五章 分布式系统中的数据一致性问题,补偿与二次分布机制,第五章 分布式系统中的数据一致性问题,结束语：,分布式计算分为集中式与对等式两类，其中对等式协同计算容错能力强，实现技术更为复杂,网格计算的实质就是分布式计算,真正意义上的协同计算由于其技术上十分复杂，目前尚无软件产品出现，往往附加了若干限制以降低其复杂性,空间数据由于其数据的复杂性，实现分布式计算尤为困难,网格地理信息系统软件将在今后5-10年时间内出现，我国有希望在此领域取得进展,