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

第六章一致性与复制,一、概述,复制目标可靠性性能难题数据的一致性两种一致性模型以数据为中心的一致性模型以客户为中心的一致性模型实现一致性的两个问题数据更新的实际分发问题保持副本一致性的问题,一致性模型,实质上是进程和数据存储之间的一个约定，进程只有遵守约定，数据存储才能正常运行基本原则：正常情况下，一个进程执行对某项数据的读操作时，应该返回该数据项最近一次写操作的结果在没有全局时钟的情况下，精确定义哪次写操作是最后一次写操作相当困难基本目标：有效限制在一个数据项执行读操作所应该返回的值,二、以数据为中心的一致性模型,（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的主拷贝，就返回确认消息。这种方式的主要问题是容错能力问题。,主机备份协议,本地写协议,本地写协议也有两种第一种每个数据项只有一个拷贝进程要对其执行操作时，先将数据的唯一主拷贝传送到进程本地，再执行操作这种完全迁移的方法的主要问题是它需要跟踪每个数据项的当前位置第二种在主机备份协议中，主拷贝允许在多个执行写操作的进程（服务器）之间迁移。这种方法的主要优点是系列写操作可以在本地执行。,基于主备份的本地写协议,主机备份协议中移动主备份,2、复制的写协议,不同于基于