高级操作系统一致性和复制课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 一致性和复制,概述,以数据为中心的一致性模型,以客户为中心的一致性模型,复制管理,一致性协议,概述：复制的目的,可靠性,性能,服务器数量扩展,地理区域扩展,代价：一致性,网络通信开销,强一致性要求的原子操作很难快速完成,解决办法：,放宽一致性方面的限制，放宽程度取决于复制数据的访问和更新模式以及数据的用途,以数据为中心的一致性模型,逻辑数据存储的一般组织，物理上是分布的，并被复制到各个进程,讨论,共享数据,读操作和写操作时的一致性问题,一致性模型实质上是进程和数据存储间的约定：如果进程同意遵守某些规则，数据存储将正常进行。正常情况下，进程的读操作应该返回最后一次写操作的结果,没有全局时钟，精确定义哪次写操作是最后一次写操作是困难的,作为全局时钟的替代，产生了一系列一致性模型，每种模型都有效地限制了一个数据项上执行一次读操作所应返回的值,严格一致性（Strict Consistency）,a)严格的一致性存储,b)非严格的一致性存储,任何对数据项,X,的读操作将返回最近一次对,X,进行写操作的值,对所有进程来说，所有写操作都是瞬间可见的，系统维护着一个绝对的全局时间顺序,线性化和顺序一致性,Linearizability and Sequential Consistency(1),a)顺序一致的数据存储,b)非顺序一致的数据存储,顺序一致性对存储器的限制比严格一致性要弱一些，要满足以下的条件：,（1）每个进程的内部操作顺序是确定不变的；,（2）假如所有的进程都对某一个存储单元执行操作，那么，它们的操作顺序是确定的，即任一进程都可以感知到这些进程同样的操作顺序。,线性化和顺序一致性(2),顺序一致性可与事务串行化相比,串行化：如果一个并发执行的事务处理集合的结果可以按照某种顺序逐个执行事务获得，该事务处理集合是可串行化的,区别：粒度的不同,顺序一致性：读写操作,串行化：事务（一系列读写操作的集合）,尽管顺序一致性是一个对程序员友好的模型，但其存在严重的性能问题：,如果执行读操作的时间是r,执行写操作的时间是w，结点间最小的数据包传送时间是t,那么存在 r+w t。,线性化,：,弱于严格一致性而强于顺序一致性,根据一系列时钟同步确定序列顺序（利用时间戳）,顺序一致性和线性化提供了程序开发人员在并发程序设计中期望的语义：,所有写操作都以相同的顺序被每个进程看到,因果一致性Casual Consistency(1),所有进程必须以相同的顺序看到具有,潜在因果关系,的写操作,不同机器上的进程可以以不同的顺序看到并发的写操作,因果一致性(2),因果一致性存储允许的，但顺序和严格一致性存储不允许的顺序,因果一致性(3),违背因果一致性的时间存储顺序,符合因果一致性的时间存储顺序,FIFO 一致性FIFO Consistency(1),FIFO一致性模型是在因果一致性模型上的进一步弱化，它满足下面的条件：,由某一个进程完成的写操作可以被其他所有的进程按照顺序感知到，而从不同进程中来的写操作对不同的进程可以有不同的顺序。,FIFO 一致性(2),符合FIFO 一致性的时间存储顺序,FIFO 一致性(3),与顺序一致性的区别:,顺序一致性：尽管语句的执行顺序是非确定的，但所有的进程对顺序达成一致,FIFO,一致性：各个进程不需要达成一致，不同进程可以以不同的顺序看到,引入同步的一致性,引入显示的同步变量,当一个进程对数据进行操作时，不保证其他进程何时看到这一操作，只是在执行一次同步时，数据的改变才被传播,弱一致性,释放一致性,入口一致性,弱一致性Weak Consistency(1),同步变量S仅有一个关联操作synchronization(S),该操作同步数据存储的所有本地拷贝,弱一致性模型必须满足的条件有下面几点:,对同步变量的访问满足一致性的要求,说明所有进程都以相同的顺序看到同步变量进行的所有操作,对同步变量的访问，只有在以前的写操作在各处都完成之后才能进行。,强迫在所有备份上完成所有的写操作,对数据的操作（读或写），只有在以前的对同步变量的操作完成之后才能进行。,保证所得到的数值是最新值,弱一致性(2),对弱一致性有效的时间顺序,对弱一致性无效的时间顺序,释放一致性Release Consistency(1),对释放一致性有效的时间顺序,弱一致性存在的问题：当同步变量被访问时，数据存储不知道此次访问是因为进程结束对共享数据的写操作，还是因为进程将开始读数据而进行的,释放一致性使用两种类型的同步变量来代替原来的一种同步变量,获取,Acquire,操作用于表明进程进入临界区,释放,Release,操作用于表明进程退出临界区,释放一致性(2),通常，如果一个分布式共享存储系统满足释放一致性，则它必须遵守以下的规则：,某进程只有在成功完成Acquire操作之后，才能对共享数据进行读写操作。,某进程只有在完成对共享数据的读写操作之后，Release操作才能完成。,Acquire和Release操作必须满足FIFO一致性要求。,进程执行获取操作时要保证数据更新，与远程数据保持一致，但不保证本地数据改变被立即传播到其他拷贝,进程执行释放操作时已改变的数据被立即传播到其他拷贝，不保证一定从其他拷贝引入改变,入口一致性Entry Consistency(1),要求每个普通的共享数据都要与某种同步变量（如锁）关联,思想：使得多个包含不同共享数据的临界区可以同时执行，从而增加系统的并行度，付出的代价是每个共享数据与某种同步变量关联的额外开销和复杂性,满足入口一致性的条件是：,在一个进程可以获取一个同步变量前，所有由该同步变量保护的共享数据相对与该进程已经,更新,完毕,在一个进程被允许以,独占,模式访问某同步变量之前，任何别的进程不可以拥有该同步变量，即使以非独占模式拥有。,在一个进程以独占模式访问一个同步变量之后，在对该同步变量的所有者,检查,之前，任何其他进程都不能执行下一个非独占访问。,入口一致性(2),对入口一致性有效的时间顺序,一致性总结,不使用同步操作的一致性模型,使用同步操作的一致性模型,Consistency,Description,严格,所有共享访问按绝对时间排序,线性化,所有进程以相同顺序看到所有的共享访问。而且，访问是根据全局时间戳排序的,顺序,所有进程以相同顺序看到所有的共享访问。访问不是根据时间排序的,因果,所有进程以相同顺序看到因果相关的共享访问。,FIFO,所有进程以不同进程提出写操作的顺序相互看到写操作。来自不同进程的写操作可以不必总是以相同的顺序出现。,(a),Consistency,Description,弱,只有在执行一次同步后，共享数据才被认为是一致的,释放,退出临界区时，使共享数据成为一致的,入口,进入临界区时，使属于一个临界区的共享数据成为一致的,(b),以客户为中心的一致性模型,最终一致性（Eventual Consistency）,最终一致性,：很多情况下系统能容忍相对较高程度的不一致性，共同之处在于：只有一个或少数几个进程执行更新操作，如果较长时间内没有更新操作，那么副本将逐渐成为一致的,数据库系统,DNS,WWW,特点：,只有少数几个进程执行更新操作，只需要处理读写冲突,能容忍相对较高程度的不一致性,实现开销小,如果客户总是访问同一副本，最终一致性能工作得很好,以客户为中心的一致性模型,移动用户访问分布式数据库不同副本的原理,以客户为中心的一致性模型不考虑数据可能被多个用户共享的问题，而是集中考虑一个单独用户应被提供的一致性。,单调读（Monotonic Reads）,如果一个进程读取数据项x的值，那么该进程对x执行的任何后续读操作将总是得到第一次读取的那个值或更新的值,进程,P,对同一数据存储的两个不同本地备份执行的读操作,提供单调读一致性的数据存储,不提供单调读一致性的数据存储,.,WS(x,1,;x,2,)表示WS(x,1,)的操作已在L,2,更新完毕,单调写（Monotonic Writes）,一个进程对数据项x执行的写操作必须在该进程对x执行的任何后续写操作之前完成,进程,P,对同一数据存储的两个不同本地备份执行的写操作,提供单调写一致性的数据存储,不提供单调写一致性的数据存储,类似以数据为中心的FIFO一致性,写后读（Read Your Writes）,一个进程对数据项x执行的写操作结果总会被该进程对x执行的任何后续读操作看见,提供写后读一致性的数据存储,不提供写后读一致性的数据存储,读后写(Writes Follow Reads),同一个进程对数据项x执行的读操作之后的写操作，保证发生在与x读取之相同或更新的值上,提供读后写一致性的数据存储,不提供读后写一致性的数据存储,复制管理副本放置（Replica Placement）,数据存储的不同类型备份,分发协议,:,将数据更新发送给各个副本的方法,副本放置,：位置、时间和由谁来放置,永久副本：副本的初始集合，数量很少，用作允许被修改以保证一致性的,唯一副本,服务器启动的副本,:,用于在客户附近放置只读备份，从而提高性能,客户启动的副本：客户高速缓存，改善数据的访问时间；对只读数据高效；可以让多个客户共享缓存；效率取决于数据类型,服务器启动的副本Server-Initiated Replicas,来自不同客户的访问请求计数,服务器启动的副本是为提高性能而存在的数据存储的备份,创建或删除副本的确切位置和时间,:,每台服务器跟踪每个文件的访问计数以及提出这些访问的请求,删除阈值,复制阈值,请求的数量位于两者之间时，当来自,P,的对,F,的请求总量超过,Q,上对,F,的请求总量的一半时，,转移,数据到,P,更新传播,更新传播,：更新从一个拷贝传播到其他拷贝,相关设计问题：,状态与操作,拉协议与推协议,单播与多播,状态与操作,实际传播的信息,只传播,更新的通知,：无效化协议,可以指定数据存储的哪些部分被更新了,请求在无效的拷贝上操作时，先更新该拷贝,几乎不占带宽，适合更新操作比读写操作多的场合（两次更新间可能没有读操作）,把,数据,从一个拷贝传送到另一个拷贝,适合读对写的比率相对高的场合：被修改的数据可能在下一个更新前被读取，即更新是有效的可能性较高,可以只传送修改的日志,通过将多个修改压缩到一个消息里来减少通信开销,把,更新操作,传送到其他拷贝：主动复制,假设每个副本由一个进程代表，该进程通过执行操作主动地更新数据：假设操作关联的参数少，传播更新的带宽代价小,拉协议与推协议Pull versus Push Protocols,在多客户、单一服务器系统中，基于推式协议与基于拉式协议比较,问题,基于推式,基于拉式,服务器的状态,客户副本和高速缓存的列表,无,发送的消息,更新（以及以后可能获取的更新）,轮询和更新,客户响应时间,立即（或获取更新的时间）,获取更新的时间,基于推式协议：基于服务器的协议,永久副本和服务器启动的副本更新,用于副本需要完全相同的时候,适合读对写的比率相对高的场合（更新对读操作有效），高效,基于拉式协议：基于客户的协议,一台服务器或客户请求其他服务器向它发送持有的更新,用于客户高速缓存：Web高速缓存，客户轮询服务器,基于租用的更新传播,更新传播的混合形式,租用是服务器的承诺，它将在指定的时间内将更新推给客户。,租用到期后：,客户被迫轮询服务器以实现更新,客户请求一个新的租期,三种类型的租用,根据数据项的年龄：为预期保持不变的数据授予一个长期的租用，可以减少更新消息的数量,根据客户请求高速缓存副本的频率：频率高的客户授予长期的租用，只跟踪对数据感兴趣的客户,基于服务器的状态空间开销：将要过载时，缩短新租用的期限,单播与多播,多播：服务器向其他N台服务器发送更新时，底层的网络负责向多个接收者发送一个消息，高效,与推式更新结合更高效,单播：服务器向其他N台服务器发送更新时，要发送N个单独的消息,与拉式更新结合更高效：只有一个客户请求