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

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