分布式系统之一致性与复制正规版资料

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,分布式系统之一致性与复制(fzh),第一页，共33页。,一、概述(i sh),复制目标(mbio),可靠性,性能,难题,数据的一致性,两种一致性模型,以数据为中心的一致性模型,以客户为中心的一致性模型,实现一致性的两个问题,数据更新的实际分发问题,保持副本一致性的问题,第二页，共33页。,一致性模型(mxng),实质上是进程和数据存储之间的一个约定，进程只有遵守约定，数据存储才能正常运行,基本原则：正常情况下，一个进程执行对某项数据的读操作时，应该返回该数据项最近一次写操作的结果,在没有全局时钟的情况下，精确定义哪次写操作是最后(zuhu)一次写操作相当困难,基本目标：有效限制在一个数据项执行读操作所应该返回的值,第三页，共33页。,二、以数据为中心(zhngxn)的一致性模型,（a）不使用(shyng)同步操作的一致性模型 （b）使用(shyng)同步操作的一致性模型,一致性,描述,严格一致性,所有共享访问事件必须按绝对时间严格排序,线性一致性,所有进程看到的共享访问必须是同一顺序,。,访问则是按照全局时间戳排序。,顺序一致性,所有进程看到的共享访问必须是同一顺序,。,访问不是按时间戳排序。,因果一致性,所有进程以相同顺序看到的有因果关系的共享访问,FIFO,各进程按自己的队列方式对写操作排序，这个顺序对所有进程可见，但来自不同进程的对共享写操作的排序有可能不一样。,(,a),一致性,描述,弱一致性,至少执行一次同步后，共享数据才被认为是一致的。,释放一致性,退出临界区后，执行共享数据一致性操作,入口一致性,进入临界区时，执行属于该临界区的共享数据的一致性操作。,(,b),第四页，共33页。,三、以客户(k h)为中心的一致性模型,第五页，共33页。,1、最终(zu zhn)一致性,在许多分布式系统的数据存储中,不会出现同时发生的更新操作,或者发生同时更新时，可以容易化解它们,大部分操作是读操作,提供一种很弱的一致性模型，称为最终一致性模型,例：,DNS系统中，各域由各自机构管理，不会出现写写冲突(chngt)，只需处理读写冲突(chngt)。,在Web中，通常浏览器或者web代理在本地高速缓存保存一份已下载的页面，但有可能过时，然而这种不一致性对客户来说是可以接受的。,第六页，共33页。,最终(zu zhn)一致性,特点：,如果在一段很长的时间内没有更新操作，那么所有副本将逐渐成为一致的,这种形式的一致性就称为最终一致性,最终一致性实际上只要求(yoqi)更新操作被保证传播到所有副本上。,最终一致性在,客户总是访问同一个副本时，没有任何问题,如果客户访问不同的副本时，就会出现问题,第七页，共33页。,移动用户访问分布式数据库的不同(b tn)副本,第八页，共33页。,2、以客户(k h)为中心的一致性,以客户为中心的一致性,有效解决最终一致性模型中客户对不同副本访问的问题,基本(jbn)思想：,为单一的客户提供一致性保证，保证该客户对数据存储的访问一致,不保证不同客户并发访问的一致性,四种模型,单调读,单调写,写后读,读后写,第九页，共33页。,单调(dndio)读,定义：如果一个进程读取数据项x的值，那么它对x执行的任何后续读操作(cozu)总是得到第一次读取的值或者更新的值。,保证进程不会读到比以前读的值更老的版本。,第十页，共33页。,单调(dndio)写,定义：一个进程对数据项x执行的写操作必须在它对x执行任何后续写操作之前(zhqin)完成。,单调写操作规定，对x的拷贝上执行写操作只有该拷贝已经完全通过了先前的所有写操作之后才能被进行，而这些先前执行的写操作可能发生在x的其他拷贝上。,例子：软件的更新，比如windows更新，杀毒软件的更新,第十一页，共33页。,在局域网内多台服务器上复制web页面文件，请求被转发到其中一台上,更新(gngxn)传播,如果访问数在二者之间，则允许F的转移。,由服务器根据系统运行情况动态创建、销毁副本,如果访问数在二者之间，则允许F的转移。,位于局域网中一台特殊的主机，如代理服务器。,应用于需要维持较高程度一致性的系统，永久副本和服务器启动的副本就一般(ybn)采用这种方式。,4、客户启动(qdng)的副本,单调(dndio)读,第二十四页，共33页。,3、服务器启动(qdng)的副本,或者发生同时更新时，可以容易化解它们,定义：如果一个进程读取数据项x的值，那么它对x执行的任何后续读操作(cozu)总是得到第一次读取的值或者更新的值。,本地(bnd)写协议,数据(shj)实际上根本没有被复制，而且也不允许移动。,研究数据更新发送给各个副本的方法，即分发协议,写后读,定义：一个进程对数据项x的写操作的结果总是被它对x的后续读操作看见。,写后读要求当进程在某个副本上执行了写操作后，如果在其他副本上对该数据执行后续的读操作的话，必须先执行这个写操作更新，保证写的结果对后续读操作可见(kjin)。,例子：分布式web站点的页面更新问题,第十二页，共33页。,读后写,定义：进程对x的读操作得到的值，不能比它后续写操作所基于的x的值更新。,也就是说，读后写一致性要求如果后续的写操作需要x的值的话，它们（指这些后续写）得到的x的值必须与前面读操作的值相同或者(huzh)更新。,例如：分布式bbs系统的回帖问题,第十三页，共33页。,四、分发(fnf)协议,第十四页，共33页。,1、副本(fbn)类型,一致性模型只从理论上解决一致性问题,从实现的角度,研究数据更新发送给各个副本的方法，即分发协议,一致性协议,副本的设计问题,位置,时间,谁来放置这些拷贝,三种(sn zhn)类型的副本,永久副本,服务器启动的副本,客户启动的副本,第十五页，共33页。,三种(sn zhn)副本,第十六页，共33页。,2、永久(yngji)副本,永久(yngji)副本是分布式数据存储的初始集合,数量一般比较少,静态配置,例1：分布式web站点，两种分布方式：,在局域网内多台服务器上复制web页面文件，请求被转发到其中一台上,镜像形式。站点被复制到散布于因特网上多个服务器，客户访问时选择镜像,例2：分布式数据库，数据库被复制在多台服务器上，形成工作站集群，不共享磁盘和内存。,第十七页，共33页。,3、服务器启动(qdng)的副本,目标,提高系统性能而由服务器动态创建的副本,原理,由服务器根据系统运行情况动态创建、销毁副本,例如对于突发的大流量(liling)web访问，就有可能需要创建这种副本。,一个重要问题：何时、何地创建或删除副本,动态复制算法原则：,复制可能是为了减轻一台服务器的负载,一台服务器的某些文件可能被转移或复制到对这些文件访问频繁的客户附近的服务器,第十八页，共33页。,服务器启动(qdng)的副本,动态复制算法：,每台服务器跟踪每个文件的访问计数以及这些访问客户的位置。,对服务器S上的文件F的访问数下降到低于删除阈值del(S,F)时，S可以删除F。但必须(bx)保证系统中至少有一个F拷贝。,反之，如果对F的请求高于复制阈值rep(S,F)时，则发生复制。,如果访问数在二者之间，则允许F的转移。,第十九页，共33页。,4、客户启动(qdng)的副本,定义：,实际上就是客户高速缓存,客户使用它暂时存储刚请求(qngqi)过的数据的拷贝。,高速缓存完全由客户管理，所以原则上服务器不负责缓存内容是否过时,高速缓存形式,位于客户机本机,位于局域网中一台特殊的主机，如代理服务器。,部署在广域网中的几个特定的专门高速缓存服务器上。,第二十页，共33页。,5、更新(gngxn)传播,为保证数据的一致性，数据的更新最终要被传播到其他拷贝上,更新传播的三种类型,只传播更新通知,数据从一个(y)副本传送到另一个(y)副本,更新操作被传播到其他副本,第二十一页，共33页。,更新(gngxn)传播,无效化协议,是一种典型的更新通知,通知其他(qt)拷贝已经发生了更新，这些拷贝包含的指定数据项不再有效,更新操作远远多于读操作时非常合适。,当读的频率远高于写频率时，就需要在多个副本之间传送被修改的数据,更新操作传播,不传送任何数据修改信息，而是告诉其他(qt)副本它应该执行什么操作,也称为主动复制,第二十二页，共33页。,更新(gngxn)传播,更新传播的另一个问题是采取什么方式传播更新,两种方式,“推”式的方法（基于服务器的协议或推协议）：更新由发生的原始点主动传播到其他副本上。应用于需要维持较高程度一致性的系统，永久副本和服务器启动的副本就一般(ybn)采用这种方式。,“拉”式的方法（基于客户的协议或拉协议）：客户或者非更新原始点副本请求其他服务器发送更新集合。适用于客户高速缓存。,第二十三页，共33页。,五、一致性协议(xiy),第二十四页，共33页。,一致性协议：一致性模型的实际实现(shxin)的工作原理。,两种一致性协议类型,基于主备份的协议,复制的写协议,区别在于是否具有主拷贝。,第二十五页，共33页。,1、基于(jy)主备份的协议,数据存储(cn ch)的任一数据项x都有一个主备份,对x的所有写操作都必须经过主备份来协调,第二十六页，共33页。,远程(yunchng)写协议,最简单的基于主备份的协议,原理,读和写操作都在远程主备份服务器上执行,数据(shj)实际上根本没有被复制，而且也不允许移动。,缺点？,第二十七页，共33页。,基于主备份(bi fn)的远程写协议,第二十八页，共33页。,一个重要问题：何时、何地创建或删除副本,数据(shj)实际上根本没有被复制，而且也不允许移动。,所有进程以相同顺序看到的有因果关系的共享访问,为单一的客户提供一致性保证，保证该客户对数据存储的访问一致,如果访问数在二者之间，则允许F的转移。,对服务器S上的文件F的访问数下降到低于删除阈值del(S,F)时，S可以删除F。,实际上就是客户高速缓存,“推”式的方法（基于服务器的协议或推协议）：更新由发生的原始点主动传播到其他副本上。,为单一的客户提供一致性保证，保证该客户对数据存储的访问一致,4、客户启动(qdng)的副本,所有进程看到的共享访问必须是同一顺序。,定义：一个进程对数据项x的写操作的结果总是被它对x的后续读操作看见。,基本原则：正常情况下，一个进程执行对某项数据的读操作时，应该返回该数据项最近一次写操作的结果,复制可能是为了减轻一台服务器的负载,3、服务器启动(qdng)的副本,第二十五页，共33页。,主机(zhj)备份协议,远程写协议的一种改进方式,原理,允许进程在本地可用副本上执行读操作,但必须向主拷贝上转发写操作,潜在性能问题：更新是阻塞的。因而启动更新的进程要等待很长时间。,也可以在主机备份协议中使用非阻塞的工作方式，只要主备份服务器更新了x的主拷贝，就返回(fnhu)确认消息。这种方式的主要问题是容错能力问题。,第二十九页，共33页。,主机备份(bi fn)协议,第三十页，共33页。,本地(bnd)写协议,本地写协议也有两种,第一种,每个数据项只有一个拷贝,进程要对其执行操作时，先将数据的唯一主拷贝传送到进程本地，再执行操作,这种完全迁移的方法的主要问题是它需要跟踪每个数据项的当前位置,第二种,在主机备份协议中，主拷贝允许在多个执行写操作的进程（服务器）之间迁移。,这种方法的主要优点(yudin)是系列写操作可以在本地执行。,第三十一页，共33页。,基于主备份的本地(bnd)写协议,第三十二页，共33页。,主机备份(bi fn)协议中移动主备份(bi fn),第三十三页，共33页。,