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

《[分布式系统数据一致性解决方案.ppt》由会员分享，可在线阅读，更多相关《[分布式系统数据一致性解决方案.ppt（32页珍藏版）》请在三一办公上搜索。

1、第五章 分布式系统完整性解决方案,1.分布式系统中数据一致性存在的困难 1.高度并行带来的问题 本机内多任务并行带来的困难 多机并行带来的困难 网络延迟不可预测 2.多副本带来的问题 系统中存在多个副本，数据的修改通常会在不同的副 本上进行,第五章 分布式系统中的数据一致性问题,3.空间数据所存在的特殊困难 跨机图幅的接边问题 拓扑关系的全局动态改变与生成问题 4.分布式系统中数据一致性保证的不同模型 严格一致性：读出的数据始终为最近写入的数据,计算机A,计算机A,计算机A,读x,写x,时刻T1,时刻T2,T2 T1，如果两者非常接近，有可能因为网络原因读请求比写请求晚到！,太严格！实现难度极

2、大！几乎不可能！,第五章 分布式系统中的数据一致性问题,顺序一致性：只要所有的程序都以一定的顺序运行（即所有程序的访问操作在别的程序看来都是一样的），每个程序的操作都以程序规定的次序实现，结果都应该被接受。例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开头说

3、明，共有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：

4、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的结果才是正确的。因果一致性在实现时必须建立与维护依赖图，这里涉及到语义上的以来，是相当困难的。,第五章 分布式系统中的数据一致

5、性问题,PRAM一致性：一个程序的写操作被其他进程以指定的顺序见到，不同程序的写操作在不同程序看来次序可以不同。例1 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 符合PRAM一致性的要求。PRAM与顺序一致性的差别在于，后者虽然为确定语句的顺序，但要求所有程序遵从共同的顺序；而前者则允许不同程序见到的顺序可以不同。,第五章 分布式系统中的数据一致性问题,例2 在前面的例子中，结果001001是可以接受的。这时，各程序看到的顺序：,程序Aa=1Print（b,c）,程序Ba=1Print（a,c）C=1,程序Ca=1Print（a,

6、b）b=1,这里只列出本程序感兴趣（与自己的打印有关）的语句执行次序,第五章 分布式系统中的数据一致性问题,PRAM一致性要求虽然较弱，但它要求程序的写操作必须被其他程序看到（尽管他们的顺序可以不同）。实际上，这样的要求有点过高，每一个程序只要能够看到与自己有关的其他程序的写操作就可以了。弱排序：弱排序只要求对共享数据结构的访问保证顺序一致性。即：对同步变量（可与信号量类比）的访问是顺序一致的；在所有以前的写操作结束之前，不的访问同步变量；在先前所有的同步变量访问完成以前，不得访问共享数据。,第五章 分布式系统中的数据一致性问题,实现考虑：为保证第一点，对同步变量的访问必须立即广播。在广播完成

7、之前，其他程序不的访问别的同步变量；对第二点，强制要求所有的同步访问开始前，已经开始的所有的写操作必须完成，在更新共享数据后立即进行同步，将新值传遍所有副本；第三点，保证在读共享数据之前，完成同步操作，以便可以读到最新值。做法：任何程序编制时，在对共享数据写操作后都必须紧接着访问同步变量；任何读共享数据操作前，访问同步变量。例如：P1：W（x,1）S1 W（y,2）S2P2：S1 R（x）1P3:s2 R（y）2,弱一致性的缺陷在于没有区分对共享变量的修改与读取。所以同步变量的访问即要确保本地写全部完成（所有副本均已更新）还要收集其它计算机的写操作信息。,第五章 分布式系统中的数据一致性问题,

8、释放一致性：类似临界区，提供“获取”和“释放”两类原子同步操作。强制：程序在访问共享变量之前必须成功完成“获取”操作；完成“释放”操作前，程序的访问操作必须结束；“获取”、“释放”应保证顺序一致性。释放一致性与用信号量和P、V操作来保证临界区访问正确性何其相似乃尔！与此相对应，还可以有入口一致性。,第五章 分布式系统中的数据一致性问题,小结：,一致性模型可以分为两类：,不使用同步操作严格：所有访问时间绝对顺序顺序：所有程序以相同顺序检测所有 共享访问事件因果：所有程序以相同顺序检测所有 因果联系事件 PRAM：所有程序按预定次序到来自一 台机器的写操作，来自其他机 器的写操作顺序不必相同,最强

9、,使用同步操作弱：同步完成后共享数据才保持一致释放：离开临界区后共享数据才保持 一致入口：进入临界区时共享数据保持一致,第五章 分布式系统中的数据一致性问题,5.实现问题 维护副本一致性的两种策略：写有效：修改本地数据时，将修改值组播所有副本节点，副本节点据此修改本地数据。要求修改传送次序严格保证。每次修改必须传送修改值，网络开销大 写无效：修改本地数据前，通知所用副本停止使用（无效），组播完成后才进行修改。其他副本需使用前，向它申请发送修改值，进行修改后再使用。多次修改可能一次传送，但每次需发送无效通知。,第五章 分布式系统中的数据一致性问题,2.对分布式文件系统的要求 1.存取透明性 用户

10、无须知道文件的分布，传统的本地文件操作手段可以直接用于远程文件操作，对已有的用户程序不必刻意进行改动就可以适应分布式环境。用户无须注意环境中其他用户是否与自己竞争使用同一个文件，无须用户在自己的程序中对共享文件数据添加并发控制，并能保持文件数据的完整性。2.位置透明性 用户看到的是全局的文件名空间，文件或文件组在机器间迁移和重新定位时不必改变其路径，用户程序无须改动。无论用户处于哪个节点，看到的是相同的文件名空间。出于可靠性考虑，同一个文件可能在不同的节点上保留副本，副本的使用对用户无关，用户意识不到当前使用的是哪一个副本,第五章 分布式系统中的数据一致性问题,3.故障透明性 在文件服务执行过

11、程中发生故障并修复（例如文件服务器故障，启用备用服务器；网络传输故障，需要重发等）对用户屏蔽。4.性能透明性 用户不会感到由于远程存取文件而带来性能上的显著降低。此外，还应该满足硬件和本地操作系统的异构性，客户端和服务器端的软件可以在不同的硬件和本地操作系统上运行。因此接口定义必须良好。5.可扩展性 系统必须具备增量扩展的能力，以适应负载和网络扩充的需要。需要指出的是，目前这个问题还在研究和探讨中，还没有一个系统完全实现这种能力。特别是系统扩展到包含大量有源节点的网络时，这个问题就更加突出。,第五章 分布式系统中的数据一致性问题,6.支持细粒度数据存取 尽可能支持用户对细粒度数据的访问。这要求

12、制定和实现更加完备的数据请求协议。这个问题在空间数据分布式处理系统中更为突出。7.网络分割适应性尽可能适应网络动态分割的情形，避免由于网络的分割和重组引起系统的问题，影响用户的使用。,第五章 分布式系统中的数据一致性问题,3.分布式文件系统的组成,用户程序,用户程序,用户程序,文件系统组件,客 户 组 件,展 开 文 件 服 务,目录服务,目录服务RPC接口,用户程序接口,展开文件RPC接口,第五章 分布式系统中的数据一致性问题,其中：展开文件服务提供了一个远程调用接口供用户程序使用。它与目录服务结合起来，为文件的存取提供一系列复杂的操作。客户组件则将展开文件服务和目录服务所提供的功能组织和集

13、成在一起，辅以统一的接口，向用户提供单一的编程接口，是用户就向使用传统文件系统那样来使用分布式文件系统。,第五章 分布式系统中的数据一致性问题,1.展开文件服务 展开文件服务主要实现对文件内容的操作。在展开文件服务中，文件通过标识符来识别。通常，文件表示符用一个长整数来表示，以便保证分布式系统中所有文件表示的唯一性。文件标识符在创建文件和打开时产生并向用户返回，与传统方式一样。展开文件服务的模型根据文件系统设计的要求来组织，提供一个简单通用的操作集合。原则上，这些操作及和与传统的文件系统提供的服务并无两样。在分布式环境中，传统的文件控制块内容也发生了变化，文件的保护也是由文件展开服务来实现的。

14、其实现技术与传统方法一样，例如通过存取控制表、存取域等。,第五章 分布式系统中的数据一致性问题,文 件 名,文 件 长 度,创 建 时 间 邮 戳,读 时 间 邮 戳,写 时 间 邮 戳,属 性 时 间 邮 戳,用 户 计 数,文 件 所 有 者,文 件 类 型,存 取 权 限 表,文 件 控 制 快,展开文件服务负责维护其中文件长度、创建时间邮戳、读时间邮戳、写时间邮戳、属性时间邮戳等。而另外的一些属性则由目录服务来维护。文件展开服务提供某些访问和修改文件属性的原语，供目录服务使用。也允许用户自己定义部分属性。文件的保护也是由文件展开服务来实现的。其实现技术与传统方法一样，例如通过存取控制表

15、、存取域等。,第五章 分布式系统中的数据一致性问题,两类文件展开服务,客 户机,服务器,下载,上载,在客户机上修改,老文件,新文件,上载/下载模式,客 户机,服务器,远程访问模式,第五章 分布式系统中的数据一致性问题,在上载/下载模式，文件展开服务只提供读文件和写文件两种方式服务，即下载/上在整个文件。概念比较简单，接口非常简洁，服务器端实现也方便。但客户端必须具备较大的空间以便存放整个文件，客户端应该具有复杂的文件访问功能，如读、写、偏移植移动等等。而它们是本地文件系统的事。而且，当客户只需要文件的一小部分时，这种方式显然不够经济，加大了网络的压力和用户空间。在远程访问模式，展开文件服务提供

16、RPC接口包括打开文件、关闭文件、度、写、修改偏移植、检查/修改属性等等，这些都在服务器端实现。显然这种方式实现复杂，但运行开销（网络开销）较省，只需要传输要求的文件部分，在客户端也不必开辟较大的空间。,第五章 分布式系统中的数据一致性问题,2.文件目录服务 目录服务提供了文件的创建、删除、命名、改名以及从一个目录下移动到另一个目录下等操作。这些并不涉及文件体的操作，也不涉及文件是整体传输还是远程访问的问题。这里，关键的问题是实现文件名到唯一标识符的转换。为了完成这种转换，设立了目录文件。目录文件实际上是文件名到唯一标识符的对照表，组织成文件的形式，所以目录文件也有自己的文件标识符。目录允许有

17、子目录，这样用户可以将有关的文件组合到一个目录下。同样，目录服务提供的文件服务对象也包括目录文件。通常，分布式文件系统的目录文件组织成树型结构，从而使整个文件系统呈现出树型结构。不少系统允许目录之间建立指针连接（象UNIX的Link），这样，树型结构就变成了“格”。这在分布式系统中尤其重要。在这里，每个目录中又一个指针计数，表示指向该目录的连接数。,第五章 分布式系统中的数据一致性问题,A,B,C,2,0,1,计算机1,D,E,1,1,计算机2,图中，右上角的数字是指向该文件的目录数量,两台计算机中的目录,第五章 分布式系统中的数据一致性问题,问题：是否每一个文件都是整个目录树可见的？进而，如

18、果系统中有多个服务器（显然每个服务器上都有一颗独立的目录树），系统是否存在一个全局的根目录？再进一步，能否知道每个文件所在的计算机名？回答：应该让每一台系统中的计算机知道系统中所有的文件；如果应用需要，应该知道它所需要的文件所在的机器名。但是，不一定需要存在一个全局的根目录。办法:1.文件命名采用 机器名+文件路径名 2.将远程文件安装到本机的分层文件目录结构中 3.存在并维护一个在所有计算机上单名字空间,第五章 分布式系统中的数据一致性问题,4 分布式系统中地理空间数据一致性保障 1.全局目录的组织 反映系统全部空间数据的全局数据目录 反映系统全部节点的全局节点目录（含负载）2.全局数据目录

19、 采用基于空间位置的数据定位机制 设定主副本节点，只能由主副本所在节点可以执行相应“写操作”并发起相应数据的同步 数据库复制技术与全局数据目录同步 数据库复制技术与全局数据内容同步,第五章 分布式系统中的数据一致性问题,3.数据同步时刻规定 同步时刻：“写操作”执行之后、节点动态加入与退出之后 同步内容：数据同步、目录同步 4.操作分布策略 第一优先：就地计算 第二优先：主副本节点 第三优先：负载平衡 5.分布计算的组织 计算由并行语句组成 并行语句由执行线索组成,第五章 分布式系统中的数据一致性问题,例 计算任务BEGIN CONCURRENT BEGIN THREAD COPY f_cam

20、ain 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_

21、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 THREADEND CONCURRENT,第五章 分布式系统中的数据一致性问题,实现机制示意：,第五章 分布式系统中的数据一致性问题,补偿与二次分布机制,第五章 分布式系统中的数据一致性问题,结束语：分布式计算分为集中式与对等式两类，其中对等式协同计算容错能力强，实现技术更为复杂 网格计算的实质就是分布式计算 真正意义上的协同计算由于其技术上十分复杂，目前尚无软件产品出现，往往附加了若干限制以降低其复杂性 空间数据由于其数据的复杂性，实现分布式计算尤为困难 网格地理信息系统软件将在今后5-10年时间内出现，我国有希望在此领域取得进展,