分布式系统之9、一致性与复制

第六章 全都性与复制一、概述复制目标牢靠性性能难题数据的全都性两种全都性模型以数据为中心的全都性模型以客户为中心的全都性模型实现全都性的两个问题数据更新的实际分发问题保持副本全都性的问题全都性模型实质上是进程和数据存储之间的一个商定，进程只有遵守商定，数据存储才能正常运行根本原则：正常状况下，一个进程执行对某项数据的读操作时，应当返回该数据项最近一次写操作的结果在没有全局时钟的状况下，准确定义哪次写操作是最终一次写操作相当困难根本目标：有效限制在一个数据项执行读操作所应当返回的值二、以数据为中心的全都性模型〔a〕不使用同步操作的全都性模型〔b〕使用同步操作的全都性模型一致性描述严格一致性所有共享访问事件必须按绝对时间严格排序线性一致性所有进程看到的共享访问必须是同一顺序。访问则是按照全局时间戳排序。顺序一致性所有进程看到的共享访问必须是同一顺序。访问不是按时间戳排序。因果一致性所有进程以相同顺序看到的有因果关系的共享访问FIFO各进程按自己的队列方式对写操作排序，这个顺序对所有进程可见，但来自不同进程的对共享写操作的排序有可能不一样。(a)一致性描述弱一致性至少执行一次同步后，共享数据才被认为是一致的。释放一致性退出临界区后，执行共享数据一致性操作入口一致性进入临界区时，执行属于该临界区的共享数据的一致性操作。(b)三、以客户为中心的全都性模型1、最终全都性在很多分布式系统的数据存储中不会消失同时发生的更新操作或者发生同时更新时，可以简洁化解它们大局部操作是读操作供给一种很弱的全都性模型，称为最终全都性模型例：DNS系统中，各域由各自机构治理，不会消失写－写冲突，只需处理读－写冲突。在Web中，通常扫瞄器或者web代理在本地高速缓存保存一份已下载的页面，但有可能过时，然而这种不全都性对客户来说是可以承受的。最终全都性特点：假设在一段很长的时间内没有更新操作，那么全部副本将渐渐成为全都的这种形式的全都性就称为最终全都性最终全都性实际上只要求更新操作被保证传播到全部副本上。最终全都性在客户总是访问同一个副本时，没有任何问题假设客户访问不同的副本时，就会消失问题移动用户访问分布式数据库的不同副本2、以客户为中心的全都性以客户为中心的全都性有效解决最终全都性模型中客户对不同副本访问的问题根本思想：为单一的客户供给全都性保证，保证该客户对数据存储的访问全都不保证不同客户并发访问的全都性四种模型单调读单调写写后读读后写单调读定义：假设一个进程读取数据项x的值，那么它对x执行的任何后续读操作总是得到第一次读取的值或者更新的值。保证进程不会读到比以前读的值更老的版本。单调写定义：一个进程对数据项x执行的写操作必需在它对x执行任何后续写操作之前完成。单调写操作规定，对x的拷贝上执行写操作只有该拷贝已经完全通过了从前的全部写操作之后才能被进展，而这些从前执行的写操作可能发生在x的其他拷贝上。例子：软件的更新，比方windows更新，杀毒软件的更新写后读定义：一个进程对数据项x的写操作的结果总是被它对x的后续读操作观察。写后读要求当进程在某个副本上执行了写操作后，假设在其他副本上对该数据执行后续的读操作的话，必需先执行这个写操作更新，保证写的结果对后续读操作可见。例子：分布式web站点的页面更新问题读后写定义：进程对x的读操作得到的值，不能比它后续写操作所基于的x的值更新。也就是说，读后写全都性要求假设后续的写操作需要x的值的话，它们〔指这些后续写〕得到的x的值必需与前面读操作的值一样或者更新。例如：分布式bbs系统的回帖问题四、分发协议1、副本类型全都性模型只从理论上解决全都性问题从实现的角度争论数据更新发送给各个副本的方法，即分发协议全都性协议副本的设计问题位置时间谁来放置这些拷贝三种类型的副本永久副本效劳器启动的副本客户启动的副本三种副本2、永久副本永久副本是分布式数据存储的初始集合数量一般比较少静态配置例1：分布式web站点，两种分布方式：在局域网内多台效劳器上复制web页面文件，恳求被转发到其中一台上镜像形式。站点被复制到散布于因特网上多个效劳器，客户访问时选择镜像例2：分布式数据库，数据库被复制在多台效劳器上，形成工作站集群，不共享磁盘和内存。3、效劳器启动的副本目标提高系统性能而由效劳器动态创立的副本原理由效劳器依据系统运行状况动态创立、销毁副本例如对于突发的大流量web访问，就有可能需要创立这种副本。一个重要问题：何时、何地创立或删除副本动态复制算法原则：复制可能是为了减轻一台效劳器的负载一台效劳器的某些文件可能被转移或复制到对这些文件访问频繁的客户四周的效劳器效劳器启动的副本动态复制算法：每台效劳器跟踪每个文件的访问计数以及这些访问客户的位置。对效劳器S上的文件F的访问数下降到低于删除阈值del(S,F)时，S可以删除F。但必需保证系统中至少有一个F拷贝。反之，假设对F的恳求高于复制阈值rep(S,F)时，则发生复制。假设访问数在二者之间，则允许F的转移。4、客户启动的副本定义：实际上就是客户高速缓存客户使用它临时存储刚恳求过的数据的拷贝。高速缓存完全由客户治理，所以原则上效劳器不负责缓存内容是否过时高速缓存形式位于客户机本机位于局域网中一台特殊的主机，如代理效劳器。部署在广域网中的几个特定的特地高速缓存效劳器上。5、更新传播为保证数据的全都性，数据的更新最终要被传播到其他拷贝上更新传播的三种类型只传播更新通知数据从一个副本传送到另一个副本更新操作被传播到其他副本更新传播无效化协议是一种典型的更新通知通知其他拷贝已经发生了更新，这些拷贝包含的指定数据项不再有效更新操作远远多于读操作时特别适宜。当读的频率远高于写频率时，就需要在多个副本之间传送被修改的数据更新操作传播不传送任何数据修改信息，而是告知其他副本它应当执行什么操作也称为主动复制更新传播更新传播的另一个问题是实行什么方式传播更新两种方式“推”式的方法〔基于效劳器的协议或推协议〕：更新由发生的原始点主动传播到其他副本上。应用于需要维持较高程度全都性的系统，永久副本和效劳器启动的副本就一般承受这种方式。“拉”式的方法〔基于客户的协议或拉协议〕：客户或者非更新原始点副本恳求其他效劳器发送更新集合。适用于客户高速缓存。五、全都性协议全都性协议：全都性模型的实际实现的工作原理。两种全都性协议类型基于主备份的协议复制的写协议区分在于是否具有主拷贝。1、基于主备份的协议数据存储的任一数据项x都有一个主备份对x的全部写操作都必需经过主备份来协调远程写协议最简洁的基于主备份的协议原理读和写操作都在远程主备份效劳器上执行数据实际上根本没有被复制，而且也不允许移动。缺点？基于主备份的远程写协议主机备份协议远程写协议的一种改进方式原理允许进程在本地可用副本上执行读操作但必需向主拷贝上转发写操作潜在性能问题：更新是堵塞的。因而启动更新的进程要等待很长时间。也可以在主机备份协议中使用非堵塞的工作方式，只要主备份效劳器更新了x的主拷贝，就返回确认消息。这种方式的主要问题是容错力量问题。主机备份协议本地写协议本地写协议也有两种第一种每个数据项只有一个拷贝进程要对其执行操作时，先将数据的唯一主拷贝传送到进程本地，再执行操作这种完全迁移的方法的主要问题是它需要跟踪每个数据项的当前位置其次种在主机备份协议中，主拷贝允许在多个执行写操作的进程〔效劳器〕之间迁移。 这种方法的主要优点是系列写操作可以在本地执行。基于主备份的本地写协议主机备份协议中移