（计算机软件与理论专业论文）存储虚拟化原理分析及其实现.pdf

存储虚拟化原理分析及其实现刘镇涛摘要随着s a n 数据量的增长，要满足存储的管理，异步平台的数据的共享、存储系统的可用性和可扩展性方面的要求，就必须采用存储虚拟化技术1 1 3 l ，存储虚拟化己逐渐成为网格存储的发展方向。本文主要探讨虚拟存储化，首先从理论的角度上阐述了分布式集群技术在存储虚拟化中的重要理论，进而，探讨了分布式虚拟化的实现环节网络虚拟化存储空间映射技术，最后给出了存储虚拟化系统的一般模型。在分布式集群技术的理论前提中，探讨非对称技术( 带外技术) 的特点，基于以上的理论前提，研究并提出了一套存储虚拟化的实现。在实现中，主要阐述了存储虚拟的分类以及整个系统的存储架构，实现分布式快照系统，在s a n 系统中，自身数据块管理比较简单，本文提出具有备份瞬间恢复新型特性的分布式快照系统的理念和初步实现，在系统设计的结构上解决海量备份时的怕带宽的问题。探索了存储虚拟化的一条可行的道路。关键词：虚拟化；物理卷管理；逻辑卷管理；虚拟存储区域网( s a n ) ；快照；元数据p r i n c i p l ea n a l y s i sa n di m p l e m e n t a t i o no fs t o r a g ev i r t u a l i z a t i o nl i uz h e n t a oa b s t r a c tw i t hg r o w i n ge x p l o s i o no fd a t a i ns a n ，s t o r a g ev i r t u a l i z a t i o nt e c h n o l o g ym u s tb eu s e dt os a t i s f yt h ed e m a n do fs t o r a g er e s o u r c em a n a g e m e n t ，s h a r i n go fd a t ab e t w e e no fh e t e r o g e n e o u sp l a t f o r m s ，t h ea v a i l a b i l i t ya n ds c a l a b i l i t yo ft h es t o r a g es y s t e m t h ev i r t u a ls t o r a g ea r eb e 画n n i n gt ol e a dt h ed i r e c t i o no fg r i ds t o r a g e 。t h ep a p e rp r i m a r i l yp r o b e si n t ot h ev i r t u a ls t o r a g e f i r s t l y ，f r o mt h et h e o r y ，t h et e c h n o l o g yo fd i s t r i b u t ec l u s t e ri si m p o r t a n tf o rt h ev i r t u a ls t o r a g ed e v e l o p m e n t m o r e o v e r ，t h et e c h n o l o g yo ft h en e t w o r kv i r t u a l i z es t o r a g es p a c em a p p i n gi sv e r yi m p o r t a n tf o rr e s e a r c h i n gt h ev i r t u a l i z es t o r a g eo fd i s t r i b u t i n g l a s t l y ，t h i sp a p e rb r i n g sf o r w o r dt h em o d e lo ft h ev i r t u a l i z es t o r a g es y s t e m b a s e do nt h et h e o r yo ft h ed i s t r i b t u t ec l u s t e r ，t h i sp a p e rr e s e a r c h e st h eo u to fb a n dt e c h n o l o g y sc h a r a c t e ra n db r i n g so u ta ni m p l e m e n to fv i r t u a l i z es t o r a g e t h i sp a p e rm a i n l yd i s c u s s e st h es o r to fv i r t u a ls t o r a g ea n ds t o r a g es y s t e ms t r u c t u r ei ni m p l e m e n t i n gt h ed i s t r i b u t ev o l u m es y s t e m i ns a n ，t h em a n a g e m e n to ft h ed a t am o c ki ss i m p l e t h ep a p e rb r i n g sf o r w o r dt h ed i s t r i b u t es n a p s h o ts y s t e mw i t ht h en e wf e a t h e ro ft h ed a t ai n s t a n tr e c o v e r y a n di tr e s o l v e st h eq u e s t i o no ff ob a n da n db r i n g sf o r w o r da n di m p l e m e n t saw a yo fv i r t u a ls t o r a g e k e y w o r d s ：v i r t u a l i z a t i o n ；p h y s i c a lv o l u m e ( p v ) ；l o g i c a lv o l u m e ( i v ) ；s t o r a g ea r e an e t w o r k ( s a n ) ；s n a p s h o tm e t a d a t an学位论文独创性声明本人声明所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经注明引用的内容外，论文中不包含其他个人已经发表或撰写过的研究成果，也不包含为获得陕西师范大学或其它教育机构的学位或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意。作者签名：笋日期：幺生2 止学位论文使用授权声明本人同意研究生在校攻读学位期间论文工作的知识产权单位属陕西师范大学。本人保证毕业离校后，发表本论文或使用本论文成果时署名单位仍为陕西师范大学。学校有权保留学位论文并向国家主管部门或其它指定机构送交论文的电子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查阅；有权将学位论文的内容编入有关数据库进行检索；有权将学位论文的标题和摘要汇编出版。作者签名：陕西师范人学硕i 学位论文第1 章绪论随着电子技术、通信技术、计算机技术、网络技术等相关高科技技术的迅猛发展，人类社会进入了信息化时代。人们要接触和应用的信息越来越多，获取信息的手段也越来越先进，而信息数据的不断积累，使得存储的使用成指数级增长，各行各业都出现了专门的数据中心，信息存储的策略也成为企业核心战略的重要组成部分，信息的存储对人类社会的政治、经济、军事、科技等方面起着越来越大的影响，使得人们面临着如何处理海量数据的问题1 。海量数据的存储和管理、及其容灾、备份的问题成为存储技术发展中亟待解决的重要问题，麻省理工教授及其实验室创办入尼格洛庞蒂曾经指出：以后的社会发展将围绕着信息存储的发展，从以前单纯的存储设备去考虑解决存储问题，到使用存储网络去解决问题。这一问题的研究已有近2 0 年了，随着存储技术手段日益完善，新的技术层出不穷，海量数据的存储和管理也日趋完善。1 1 题目的研究背景和意义随着存储的高速发展，为解决当前的海量存储问题，提出网络虚拟化的架构设计，此项技术高速发展，逐渐成为今后存储的发展方向，简单的讲，虚拟存储( s t o r a g ev i r t u a l i z a t i o n ) ，就是把多个存储介质模块f 如硬盘、r a i d ) 通过一定的手段集中管理起来，所有的存储模块在一个存储池中得到统一管理。这种可以将多种、多级、多个存储设备统一管理起来、并能为使用者提供大容量、高速数据传输性能的存储系统，就称之为虚拟存储“。从计算机技术几十年的发展史上来看，内存系统从直接寻址发展到虚拟地址寻址，它的出现是因为，随着信息量的指数上升以及计算机系统硬件结构的同益完善，所以提出了内存虚拟化，使得对内存的访问变得不再透明。存储虚拟化技术的出现变成了解决海量信息存储的主要手段，也由此就逐步演变成了现代存储架构，即从内存的虚拟化扩展到外部存储的虚拟化，这一过程用了近2 0 年的时间。从真实的磁盘、磁带机到虚拟磁盘、虚拟磁带机、虚拟卷的大规模企业化应用，已最大程度上解决了现有应用所必须解决的存储管理的多种问题，但是数据的容灾、实时备份的问题，又成为一个突出的研究课题。实践表明，单纯从存储设备去入手解决这个问题已难已实现，必须从共享存储网络的新技术发展以及分存储虚拟化原理分析及其实现布式存储技术、并且结合现有存储设备硬件的升级去综合解决这个问题。总之，在现有的存储架构中，诸多的不足和缺陷是促使本文去不断研发新的存储技术的最终动力。1 2 相关研究的发展状况1 2 1 引言现代存储架构中三个主要结构为d a s ( d i r e c t a t t a c h e ds t o r a g e ) 、n a s ( n e t w o r ka t t a c h e ds t o r a g e ) 和s a n ( s t o r a g e a r e an e t w o r k ) 结构”。( 1 ) d a s ( d i r e c t a t t a c h e ds t o r a g e )传统的直接存储模式d a s 是直接将存储设备连接到服务器上。一方面，当存储容量增加时，这种方式很难扩展：另一方面，当服务器出现异常时，会使数据不可获得。( 2 ) n a s ( n e t w o r ka t t a c h e ds t o r a g e )n a s 将存储设备连接到现有的网络上，提供数据和文件服务。n a s 将存储设备通过标准的网络拓扑结构连接，可以无需服务器直接上网，不依赖通用的操作系统，而是采用一个面向用户设计的、专门用于数据存储的简化操作系统，内置了与网络连接所需的协议，因此使整个系统的管理和设置较为简单灵活。( 3 ) s a n ( s t o r a g ea r e an e t w o r k )s a n 通过特定的互连方式连接若干台存储服务器组成一个单独的数据网络。它是一种特殊的高速网络，连接网络服务器和诸如磁盘阵列或备份磁带库的存储设备，s a n 置于l a n 之下，而不涉及l a n ，常被称为企业的第二网。利用s a n ，不仅可以提供大容量的存储数据，而且地域上可以分散，并缓解了大量数据传输对于局域网的影响，它的主要特点是高效且容易扩充。存储从单盘发展到后来的磁盘阵列，一是由于存储的需求增加，二是要求增加系统的可伸缩性，并且保证系统的鲁棒性( r o b u s t ) 。由于异构计算机网络的发展，使多台异构计算机可以共同使用一个集中域( d o m a i n ) 去共同存储，也就是“存储集中化”。为实现“存储集中化”，d a s 、n a s 的技术相继推出，直到今天全新架构s a n 系统的出现，s a n 架构避免了d a s 、n a s 系统的单点故障的问题，而且易于扩充，效率更高。s a n 架构的存贮模型如图1 1 所示“。2陕两师范人学硕上学位论文图1 1s a n ( 共享存储网络淮架模型根据s a n 中存储虚拟化实现方式的不同，可以划分为三个层次：主机级、存储设备级和存储网络级o “。( 1 ) 主机级主机的虚拟化将虚拟化层放在s a n 中的应用服务器上，通过改造操作系统的文件系统层或者设备层来完成卷逻辑地址到物理地址的转换，这种方式实现起来比较简单，但是存在单点故障和安装调试复杂的缺点。( 2 ) 存储设备级即将存储虚拟化实现在实际的物理存储设备上面，例如磁盘阵列。这样的做法的特点是兼容性高，屏蔽各种操作系统的细节，但是在跨盘阵的分布式虚拟化的设计上有局限性。( 3 ) 存储网络级这个级别也正是本文所使用的方式，其特点为充分利用网络资源，在实现过程中，既能使用户感觉不到虚拟化的存在，而且操作上屏蔽各种细节，符合存储网格的发展趋势，同时具有很高的扩展性、灵活性，本文在后面的论述中将详细论述。1 2 2 海量存储的分布式集群技术现在的存储系统架构在分布式集群的环境中，作为一个系统支撑体系，分布式存储环境所面临的最为直接的问题就是：如何实现高效、高可用的系统支撑，这也是分布式集群技术所要解决的关键，分布式集群环境的一个集群系统是一系列独立的计算机系统的结合，用户应用与集群相互作用时，集群作用就如同一个高性能高可靠性的服务器，系统管理员完全可把集群当成一个服务器来处理。3存储虚拟化原理分析及j e 实现在现实集群存储系统时，管理员经常会遇到四大类问题，容量可扩展性；性能可扩展性；可用性；可管理性。虽然不是绝对的，但是，这4 类问题确实“催生”了许多存储集群产品，几乎所有的存储系统都是围绕着如何解决这些问题而设计的o “：容量可扩展性。在不干扰系统币常运作的情况之下，接入新的磁盘阵列，扩大系统的存储容量。性能可扩展性。随着系统容量的不断扩大，支持的主机服务器数量不断增加，系统整体的性能也应该有相应的提升，否则很难维持j 下常运作。高可用性。冗余的存储组件和透明化的容灾恢复操作，可确保备份数据的高可用性。可管理性。系统升级、数据容灾恢复、存储资源管理，都应该尽可能地实现自动化操作。从理论上讲，通过备用存储设备上的数据来修复最近一致的数据备份，重放一系列h 志，然后在备用服务器上重新启动应用程序就可恢复上次失效。此外，还要根据具体的应用程序，重建客户应用程序的连接并恢复客户状态。但是，事实上如今的大多数应用程序实现这个过程是不可行的。采用双结点集群、多结点集群和数据复制方式将使应用程序具有商有效性，但这三种解决方式的实现费用则依次增加。服务器集群可提高应用程序的有效性和可扩展性。1 ：集群技术的客户负载均衡，使用互相协作的网络路由器或应用程序服务器软件来分配客户请求；应用程序扩展，使用多台服务器来运行同一应用程序，并使用负载平衡为这些应用程序分配负载；保证应用程序有效，使用多台服务器，每台服务器可运行应用程序，当某一服务器失败时可在另一台服务器上重新启动；保证数据访问的有效与可扩展性，使用多台互连服务器提供对数据库或文件访问。多层次集群系统意在提高可扩展性和管理数据的完整性，发生失效后，可在残留服务器之间重新分配，即数据库同志的回放和检验文件系统元数据的完整性等。在所有存储设备互连到s a n 储存区域网络系统上，不但能够灵活分配存储资源，还能显著降低服务器的消耗，即把所有应用程序合并到一个集群系统中可节约费用和管理化简。还有，随着更多服务器加入到集群中来，可能出现冗余处理4陕两师范大学硕t 学位论文资源，这些冗余资源为应用程序的高有效性提供了保障，也使得系统为更多的应用程序提供失败保护。关于这一方面本文将从理论的角度，第2 章当中详细论述。1 2 3 存储虚拟化空间映射技术数据信息的爆炸性增长对存储系统提出了越来越高的要求，推动了存储区域网络技术的出现和发展，用高速数据网络代替主机和存储设备之间的传统数据总线，使物理存储设备成为可灵活分配和扩展的独立资源1 ，目前，如何高效管理并充分利用这些存储资源以提供更高的服务质量，仍是个亟须解决的问题。存储系统的服务质量必须从存储容量、数据可用性和性能这几个方面进行全面评测，存储虚拟化能够全面提升系统的服务质量。如何能够保证一个存储系统具有高性能的i 0 吞吐率、高可靠性和高可扩展能力，以及良好的容错性能，成为各个i t 厂商倾注极大热情去解决的重大问题。就目前看来，解决的方案不约而同地采用了能够提供高性能价格比的存储网络技术。存储区域s a n ( s t o r a g ea r e an e t w o r k s ) 技术的存储设备是用专用网络相连的，这个网络是一个基于光纤通道协议的网络。光纤通道的存储网和l a n 分开，且具有高可靠性、高传输率的特点，因此系统性能就得到有效的提高。由于具有这些优异的性能，所以s a n 成为企业存储的重要技术。随着存储虚拟化的概念的提出，在分布式集群技术的基础上，实现存储虚拟化，最核心问题就是如何实现从逻辑地址到物理地址的转化，本文从存储区域网s a n ( s t o r a g e a r e a n e t w o r k ) 结构的大规模应用，在s a n 架构上，存储空间地址映射成为实现存储虚拟化最先也是最核心要解决的问题。虽然虚拟网络存储受到了业界人士的广泛关注，但是目前大多还停留在探索阶段。现在给出了一种虚拟网络存储的存储空问映射方发，研究了客户端和服务器端的虚拟抽象技术，并对系统核心组件一虚拟存储服务器进行了重点研究。下面第3 章具体详细论述，虚拟化存储的一般性抽象性结构。1 2 4 带外( o u to fb a n d ) 数据的模型和存储存储虚拟化可分为“带内”和“带外”两种基本类型”1 。两者最显著的特点是管理路径和生产路径是否重叠，如果重叠，会发生争用带宽的问题，使得生产系统的效率降低。带内虚拟技术是在数据读写的过程中，在主机到存储设备的路径上实现存储虚拟化；而带外虚拟技术，是在数据读写之前，就已经做好了虚拟5存储虚拟化原理分析及其实现工作，而且实现虚拟的部分并不在主机到存储设备的访问路径上。所以带内虚拟技术可以基于主机、设备和网络实现，而带外虚拟技术则只能是基于存储网络实现。图1 2 带外架构拓扑图模型的建市是根据s c s i 协议的读写模型结合有限自动机理论来的描述和总结当今带外模型的和带内模型两大阵营在理沦上的不同点，并且论述本文在实现存储虚拟化的过程中，为什么会选择使用带外的存储技术。我将在第4 章中论述描述。随着数据存储量的爆炸性增长，s a n 等网络存储结构逐渐成为主要的存储体系结构。由于s a n 中数据量的增长速度惊人，对于存储和数据的管理、异构平台数据共享、系统可用性和可扩展性、访问控制和安全等的要求越来越高，必须采用存储虚拟化技术来满足这些要求。存储虚拟化是一种将服务器操作系统的存储描述与实际物理存储设备相分离的技术。它是存储的抽象，使用户能够在一个“更高的抽象层”显示存储资源的视图，将所有的存储资源置于一个统一的存储池中，为用户提供一个统一的逻辑视图。虚拟化技术可以减少存储系统的管理开销，满足用户对存储系统的要求，优化系统使用。目翦，网络级的存储虚拟化是其主流的实现方式。1 3 论文的工作重点和内容安排本文工作源于“基于s a n 的分布式卷管理架构及实现”而进行的。主要的目的是研究分析海量存储的分布式集群技术，借鉴和研究了网络虚拟化存储空间的映射技术，提出了一般性虚拟化存储系统的模型，由此理论基础上，分析和研究了带外架构的各种特点，提出了带外架构的基本模型，在以上研究工作中，着重解决了逻辑地址和物理地址问转换的重要问题，利用高效的s a n 环境的特性，提6陕两师范大学硕l ：学位论文出一整套存储虚拟化的实现方案。论文的第一章绪论，论述了课题开展的背景和研究意义，然后对海量存储的研究的现状做了简明扼要的介绍，同时对论文的工作重点和内容结构进行了安排。第2 章介绍了海量存储的分稚式集群技术，着重讲几个重要的分布式概念作了详尽的论述和分析。第3 章提出了网络虚拟化存储空间的映射技术是网络存储虚拟化中最为关键的技术，提出了一般性存储虚拟化存储系统的模型和存储服务器性能的模型，第4 章，做了对存储虚拟化实现的架构，作了深入地分析和研究，提出了带外虚拟化架构的特点，把它作为下一步实现框架基础。第5 章，着重论述了基于s a n 分布式卷管理架构，并且实现了其中重要的分稚式快照技术和异步i o的技术。第6 章，本文作了总结和展望。7存储虚拟化原理分析及其实现第2 章海量存储的分布式集群技术2 1 关于分布式全局状态的概念在分布式集群环境中设计海量存储管理及容灾备份系统，不可避免的问题就在于使用分布式集群技术去解决现有的负载均衡和高可用等方面的问题。如何协调分布式环境中各个主机上的进程，成为分布式集群设计中极其重要的问题，本文首先从理论上来论述所面临的问题和思路。如何从全局的角度上设计系统，成为本文必须从理论上认知的重要概念。下面将从理论的角度上来论述。所谓分饰式全局就足通过通道、状念、快照、全局状态、分布式快照等概念去描述一个集群环境中各主机所有的进程的集合的状态。2 2 全局状态和分布式快照紧耦合系统中所遇到的所有并发问题，例如互斥、死锁和饥饿，在分布式系统中也同样会遇到。在这些领域中的设计策略是很复杂的，因为没有系统的全局状态，也就是说，操作系统或任何进程都不可能知道分布式系统中的所有进程的当前状态。进程通过访问内存中的进程控制块，只能知道本地系统上的所有进程的当前状态。对于远程进程，进程只能通过消息接收到状念信息，它代表了过去某时刻远程进程的状态。由分布式系统的本质所造成的时间延迟，使与并发有关的所有问题都复杂了。为了说明这一点，给出一个的例子。下面将使用进程事件图( 如图2 3 和图2 4 所示) 来描述问题。在这些图中，每个进程的水平直线代表时间轴，直线上的点表示事件( 如内部进程事件、消息发送、消息接收) 。白色方框代表了一个在该点的本地进程的快照，箭头代表两个进程之问的消息。在这个例子中，某人具有分布在一家银行的两个部门的银行帐号。为了确定顾客帐号上的总余额，银行必须确定每个部门的金额，假设确定过程在下午三点整进行，图2 3 ( a ) 显示了组合的帐号共有1 0 0 美元余额的情况，但图2 3 ( b ) 显示的情况也是可能的，这晕，部门a 的余额在观察的时间罩正在转移到部门b ：结果被错误地认定为0 美元。这一特殊问题可以通过检测在观察时处于传递中的所有消息而得到解决。部门a 将保存一个所有转出帐号操作的记录，以及转移的目标。这样，将在部门a 帐号的状态中包括当前余额和一个转移记录。当检测两个帐号时，观察8陕西帅范犬学硕j 二学位论文者发现有一个离开部门a 、前往部门b 的该顾客帐号的转移操作。因为该金额还没有到达部门b ，它被加到了总余额中。任何传输或接收的金额只加一次，作为接收帐号的余额的一部分。这种策略并不十分安全，如图2 3 ( c ) 所示。在这个例子中，两个部门的时钟并不十分同步。在下午三点部门a 的顾客帐号的状态显示余额为1 0 0 美元。然而，根据a 的时钟，这一金额接着在3 ：0 1 时被转移到部f b ，但是根据b 的时钟，它是在2 ：5 9 到达b 的。因此，对于在三点整的观察，该金额被加了两次。部门a部门bs a = $ 1 0 0部门a部门bs a = $ o( a 余顿= $ 1 0 0s a = $ 0s a = $ of b l 余额= $ oi c 余额= $ 2 0 0图2 3 全局状态的例子93 ：1 0 01 筝储虚拟化腺理分析及雎实现为了帮助理解所面临的困难和更明确地表达解决方法，定义了下列术语：1 通道( c h a n n e l ) ：通道存在于交换消息的两个进程之间。可以认为通道就是消息传输的途径或方法。为方便起见，通道被看做是单向的。因此，如果要在两个进程间交换消息，则需要两条通道，每条通道用于一个方向的消息传输。2 状态( s t a t e ) ：进程的状态是已通过通道发送或接收的进程附带的消息序列。3 快照( s n a p s h o t ) ：快照记录了进程的状态。每个快照包括了自从前一个快照以来，在所有通道上所发送和接收的所有消息的1 记录。4 全局状态( g l o b a ls t a t e ) ：所有进程的组合状态。5 分布式快照( d i s t r i b u t e ds n a p s h o t ) ：一组快照的集合，其中每个进程一个。问题是真正的令局状态因为与消息传输有关的时间流逝而无法确定。这可以通过从所有进程处收集快照来尝试着定义一个全局状态。例如，图2 4 ( a ) 中在取得快照时的全局状态显示了有一条消息在 通道上移动，有一条消息于在 通道上移动，还有一条消息萨在 通道上移动。消息2 和4 都得到了适当的表现，消息3 却没有。分布式快照指示这条消息已经收到，但却还没有发送出去。进程a进程b进程c a ) 非一致的全局状态l o陕两师范大学硕上学位论文进程a进程b进程c( a ) 一致的全局状态图2 4 非一致与一致的全局状态这里希望分布式快照记录一个一致的全局状态。如果对于任何记录了消息接收情况的进程状态。该消息的发送被记录在发送消息的进程的进程状态中，则该全局状态是一致的。图2 4 ( b ) 给出了一个例子。非一致性的全局状态的发生情况是，如果一个进程已经记录了消息的接收情况，而相应的不发送进程还没有记录该消息己被发送，如图2 4 ( a ) 所示。2 - 3 分布式快照算法假设消息的传送按照它们发送的顺序，并且没有消息丢失。一个可靠传输协议( 例如t c p ) 满足了这些要求。算法使用了一个特殊的控制消息，称为标识( m a r k e r ) 。有些进程通过记录其状态并在任何消息发送之前在所有流出通道上发送一个标识来启动算法。然而每个进程p 按照下列步骤进行。当第一次接收到标识时( 从进程q ) ，接收进程p 执行下列步骤：1 、p 记录其本地状态s p 。2 、p 将从q 到p 的通道的状态记录为空。3 、p 通过所有流出通道向其所有邻居广播标识h 4 1 。这些步骤必须是原子执行，即直到所有3 个步骤都己执行完毕，才能在p 上发送和接收消息。在记录了状态之后的任何时候，当p 从另一个进入通道( 从进程r ) 接收到一个标识时，它将执行下列步骤：p 将从r 到p 的通道的状态记录为：从p 已经记录了它的本地状态s p n 它已经从r接收到了标识期间，p 从r 已接收到的消息序列。存储虚拟化原理分析及】t 实现当已在所有流入通道上接收到标识后，该无算法立即在进程上结束。关于算法给出了下列观察：1 、任何进程可以通过发送出一个标识而开始算法。事实上，若干个节点可以独立地决定记录状态，且算法依然可以成功进行。2 、算法将在有限的时间内结束，前提是每条消息( 包括标识消息) 的传送时间是有限的。3 、这是一个分布式算法：每个进程负责记录自身的状态以及所有流入通道的状态。4 、一旦所有的状态已记录完毕( 算法在所有进程结束) ，则算法所获得的一致的全局状态可以在每个进程中装配起来，方法是使每个进程发送它在所有流出通道上己经记录的状态数据，并且使每个进程转发它在所有流出通道上接收的状态数据。作为另一种方法，启动迸程也可以轮询所有进程，以获得全局状态。5 、算法既不影响任何其他的进程j i 在参与的分和式算法，也不受它们的影响。作为使用该算法的一个例子”，考虑图2 5 n 示的一组进程，每个进程由一个节点表示，每个单向的通道由位于两节点之问的直线表示，方向由箭头表示。假设正在运行快照算法，有9 条消息要在每个进程的所有流出通道上发送。进程l 决定在发送6 条消息后记录全局状态，进程4 独立地决定在发送3 条消息后记录全局状念。在结束后，从每个进程收集快照，结果如图2 6 所示。进程2 在记录状态之前在两条流出通道的每一条上向进程3 和4 发送了4 条消息，它在记录自身状态之前从进程1 接收到4 条消息，剩下了消息5 和6 成为与通道有关的。读者应该为一致性来检查快照：每条发送出去的消息或者在目的进程上被接收，或者被记录为j 下在通道中传送。分布式快照算法是一个强大而灵活的工具，它可用于适应任何分布式环境的集中式算法，因为任何集中式算法的基础是知道全局状态“”。具体的例子包括对死锁的检测和对进程结束的检测。它也用于提供分布式算法的检测点，如果检测到故障，则能够返回和恢复。陕两师范人学硕j 。学位论文2 4 分布式互斥2 4 1 分布式互斥概念雷25 进程和遗道图图2 5 进程和通道图当两个或多个进程对系统资源的使用产生竞争时，就需要一种执行互斥的机制。假设两个或多个进程要求访问一个非共享的资源，例如一台打印机，在执行期间，每个进程都将不断地向i o 设备发送命令、接收状态信息、发送数据以及接收数据。这里把这样的资源称为l 临界资源，把使用它的程序部分称为临界区，某一时刻只允许有一个程序在其临界区中是非常重要的。这里不能简单地靠操作系统来理解和强加这一限制，因为详细的要求可能并不明显。以打印机为例，任意一个独立进程在打印一个完整文件时，需要此进程具有对打印机的完全控制。否则，各竞争进程的打印行将是交叉打印的。进程间并发机制的成功使用，需要有定义i 晦界区和实行互斥的能力，这是任何并发处理方法的基础。任何对互斥提供支持的功能和应用应该满足下列要求：l 、必须实行互斥：在具有同一资源或共享对象的临界区的所有进程中，一次只允许一个进程进入其临界区。2 、位于非i 临界区中的进程也必须这样做，而且不能干涉其他进程。3 、必须做到使进程要求对临界区的访问不能无限期地延迟，即无死锁或饥饿。4 、当没有进程在临界区中时，任何请求进入其临界区的进程必须能够无延迟地进入。5 、不做有关进程速度或处理器数目的假设。6 、进程在其临界区中仅维持有限的时间。图2 6 展示了一个模型，可以用来在分布式环境中研究互斥方法。假设一定数1 3存储虚拟化原理分析及e 实现量的系统通过某种类型的网络设备相互连接，在每个系统内，假设操作系统中的某些函数或进程负责资源分配，每个这样的进程控制着很多资源，并服务与很多用户进程。任务就是设计一个算法，通过它，这些进程在实行互斥时可以合作。互斥算法可以是集中式的或分布式。在完全集中式算法中，一个节点被指定为控制节点，它控制对所有共享对象的访问。当任何进程请求对一个临界资源进行访问时，就向本地资源控制进程发送一个请求，这个进程接着向控制节点发送一条请求消息，当共享对象可用时，将返回一条许可消息，当进程结束使用资源后，向控制节点发送一条释放消息。这种的集中式算法具有两个关键特点：1 、只有控制节点能作资源分配的决定2 、所有需要的信息都集中在控制节点中，包括所有资源的实体和位置以及每个资源的分配状态。图2 6 分布式进程管理中的互斥问题模犁集中式方法很简单，也容易看出互斥是如何实行的：控制节点直到所请求的资源已经被释放，才会满足对该资的新请求。然而，这种方法具有许多缺点：如果控制节点崩溃，则互斥机制就会终止，至少是暂时终止。而且，所有的资源分配和回收都需要与控制节点进行一次消息交换，这样，控制节点可能会成为瓶颈。因为集中式算法存在问题，所以我门把更多的精力放在了对分布式算法的开发上，一个完整的分布式算法由下列特性所刻画：1 4陕西师范人学硕i j 学位论文1 、所有节点平均起来具有相同的信息量。2 、每个节点只掌握整个系统的部分情况，且必须基于这些信息做出决策。3 、所有节点对最终决策承担相同的责任。4 、所有节点在对最终决策的影响上平均起来付出了相同的努力。5 、一个节点的故障一般不会导致整个系统的崩溃。6 、不存在系统范围的公共时钟来调节事件的时问。第2 点和第6 点可能需要推敲。对于第2 点，有些分布式算法要求任何节点所知道的所有信息都要告知所有其他节点。即使在这种情况下，在任意给定的时间，某些信息也将处于传送状态，不会都到达所有的其他节点。这样，因为消息通信的时间延迟，一个节点的信息通常不是最新的，在这种意义上只是部分信息。对于第6 点，因为系统之间的通信延迟，不可能在系统范围内维护一个所有系统都随时可用的时钟。而且，维护一个中央时钟并让所有本地时钟与之保持精确同步，这在技术上也是不现实的，因为经过一段时间后，在各个本地时钟之间就会产生一些偏差，这将导致同步的丢失。正是通信中的延迟，再加上缺少一个公共时钟，使得在分布式系统中设计出一套互斥机制比在集中式系统中要更加困难。在讨论用于分布式互斥的某些算法之前，需要先研究一种通用的方法，来克服时钟不一致性的问题。2 4 2 分布式系统中的事件排序用于互斥和死锁的大多数分布式算法的操作基础是对事件的暂时排序。缺少公共时钟或同步的本地时钟就成了主要的限制。该问题可以描述成下面的形式。人们通常可以说系统i 的事件a 发生在系统j 的事件b 之前( 或之后) ，并且或许还可以在网络中的所有系统上一致地得到这个结论。遗憾的是，这种陈述不够精确，原因有二：第一，在事件的实际发生时间和在其他系统上观察该事件的时间两者之间可能会有延迟。第二，由于同步的缺乏，也导致了在不同系统上对时钟读取的不一致。为了克服这些困难，l a m p o r t 提出了一种称为时间戳的方法，它在分布式系统中，对事件排序时不需要使用物理时钟。j 下是因为这项技术非常有效且高效，所以目前在绝大多数互斥和死锁的算法中都使用了它。在开始时，本文需要确定术语事件的定义。在根本上，本文关注的是发生在本地系统上的行为，例如，进程进入或离开其临界区。然而，在分布式系统中，进程之间的交互方式是通过消息进行的，因此，将事件与消息联系起来是有意义1 5存储虚拟化原理分析及其实现的。本地事件可以很简单地与一条消息连接起来，例如，当进程希望进入其临界区时，或当它离开临界区时，可以发送一条消息。为避免含糊，只将事件与消息的发送关联起来，而不与消息的接收相联系。这样，在每次进程发送一条消息时，事件的定义与消息离开进程时的时问就一致了。时日j 戳方法j 下是用消息的传输顺序来对事件进行排序的。网络中的每个系统i都维护了一个本地计数器c i ，其功能相对于时钟。每次系统发送消息时，它首先将时钟加1 。消息发送时的形式为( m ，t i ，i )其中，m 表示消息的内容t i 表示该消息的时间戳，与c i 相等i 表示本站点的数字标识符当接收到消息时，接收系统j 将它的时钟设为其当前值和到达的时间戳这两者的最大值再加1 ：c j 一1 + m a x c j ，t i 在每个站点，事件的排序由下列规则确定：对于来自站点i 的消息x 和来自站点j 的消息y ，如果下述条件之一成立，则说x 在y 前面：l 、如果t i2 、如果t i ：t j 并且i 与每条消息有关的时间是伴随消息的时间戳，这些时1 1 日j 的顺序是通过上述两个规则确定的，具有相同时制戳的两条消息是通过它们的站点编号来排序的。因为这些规则的应用独立于站点，所以这种方法避免了各通信进程的不同时钟之间的偏差带来的问题。这个算法的操作示例见图2 7 。有三个站点，每个站点都通过一个控制时阃戳算法的进程来表示。进程p 1 开始时时钟的值为0 。为了传送消，g , a ，它将时钟加i 并发送( a 、1 、1 ) ，第一个数字值是时问戳，第二个是站点标识。这条消息被站点2和3 的进程接收到。在两种情况中，本地时钟的值是0 ，并被设置成值2 = l + m a x 0 ，1 。p 2 发出了下一条消息，首先将它的时钟增加为3 。在接收到这条消息后，p l 和p 3 必须将它们的时钟增3 n n 4 。然后在大致相同的时间，以相同的时间戳，p l 发出消息b ，p 3 发出消息j 。因为有前面所述的排序原则，这不会产生混淆，在所有这些事件发生后，消息的顺序在所有站点上是相同的，即 a ，x ，b ，j j 。陕两师范大学硕。k 学位论文p 101456图2 7 时间戳无算法的操作例子算法在工作时不考虑在两个系统之间的传输时间上的差别，如图2 8 所示。这里，p 1 和p 4 以相同的时间戳发出消息，p 1 的消息在站点2 上比p 4 的消息早到达，但在站点3 上要i ：e p 4 的消息晚到达。尽管这样，当所有消息在所有站点上都已接收完后，消息的顺序在所有站点上仍然是相同的，即 a ，q 。d 1012p 2p 3d 4图2 8 时间戳算法操作的另一个例子1 7存储虚拟化腺理分析及j t 实现注意，本方法所产生的排序不需要与实际的时间顺序相一致。对于这种基于时间戳的算法，哪个事件实际上首先发生并不重要，重要的是实现算法的所有进程都认同这种对事件的排序。在刚才讨论的两个例子中，每条消息都从一个进程发送到所有其他进程。如果某些消息不是以这种方式发送的，那么有些站点就收不到系统中的所有消息，因此所有站点具有相同消息顺序就是不可能的。在这种情况下，就存在一些部分排序情况。然而，前面主要考虑的是在具有互斥和死锁检测的分布式算法中，对时问戳的使用。在这个算法中，进程通常向每个其他进程发送一条消息( 具有时自j 戳) ，且时间戳常常决定如何处理该消息。2 4 3 分布式队列最早提供分布式互斥的方法中，有一个是以分布式队列为基础的。该算法基于下列假设：1 一个分布式系统由n 个节点组成，统一编号为l n n 。每个节点含有一个进程，该进程做出对代表其他进程的资源进行互斥访问的请求。当到达的请求在时问上有重叠时，这个进程也作为解决问题的仲裁器。2 从一个进程发送到其他进程的消息，按照它们发送时相同的顺序接收。3 每条消息都在有限的时间内正确地传送到目的地。4 网络是全互联的，这意味着每个进程可以直接将消息发送到任何其他进程，不需要请求一个中介进程转发该消息。第2 个和第3 个假设可以通过使用可靠传输协议例如t c p 来实现“。为了简化算法的描述，假设每个站点只控制一个单独的资源。对多资源进行一般化的意义不大。该算法试图生成一个以简单直接的形式工作在集中式系统中的算法。如果一个单独的中央进程管理着资源，则它可以将到达的多个请求排队，并以先进先出的方式接受请求。为了在分布式系统中获取同一算法，所有站点必须具有相同队列的一个副本。时间戳方法可以用于保证所有站点对资源请求的顺序，得到意见一致确认。这样就产生了一种复杂情况：因为消息在网络上的传送需要花费一定量的有限时间，所以两个不同站点对于哪个进程位于队列的头部存在意见不一致的危险。考虑图2 8 ，存在这样一种情况：消息a 已到达p 2 ，消息q 已到达p 3 ，但是两条消息仍然都正在向其他进程传送。这样就存在一个时间段，p 1 和p 2 认为消息a为是队列的头，而p 3 和p 4 认为消息q 是队列的头，这会导致违反互斥的要求。为了1 8陕两师范大学硕士学位论文避免这种情况，又提出了下列规则：为了让一个进程基于它自己的队列做出分配决定，它需要接收到一条来自所有其他站点的消息，保证没有比它自己的队列头更早的消息仍在传输中。在每个站点都维护着一个数据结构。它保存着一个从每个站点接收到的最近的消息( 包括在该站点上产生的最近的消息) 的记录。l a m p o r t 将这个结构称为队列“”，实际上它是一个数组，每一项用于一个站点。在任意时刻，本地数组中的项q j 包含一条来f l p j 的消息。该数组被初始化为q j = ( r e l e a s e ，0 ，j ) j = l ，n这个算法用到了三种类型的消息：( r e q u e s t ，t i ，i ) ：由p i 做出的访问资源的一个请求。( r e p l y ，t j ，j ) ：p j 同意在它的控制下访问资源。( r e l e a s e ，t k ，k ) ：p k 释放掉以前分配给它的一个资源。算法如下：1 当p i 请求访问一个资源时，它发出一个请求( r e q u e s t ，t i ，i ) ，取当前本地时钟的值打上时间戳。它将这条消息放入自己的数组中q i 的位置，并将消息发送给所有其他进程。2 当p j 接收到( r e q u e s t ，t i ，i ) 时，它将这条消息放入自己的队列中q i 的位置。如果q j 不包含一个请求消息，则p j 将( r e p l y ，t j ，j ) 传送给p i 。正是这个行动实现了前面所提到的规则，它保证没有更早的r e q u e s t 消息在决定之时仍在传送。3 当下列两个条件都成立时，p i 可以访问一个资源( 进入其临界区) ：( a ) p i 自己的r e q u e s t 消息，在数组q 中是最早的，因为消息在所有站点都进行一致排序，此规则允许在任意时刻只有一个进程的访问资源。( b ) 在本地数组中的所有其他消息都要比q i 的中消息晚，此规则确保p i 已经了解到了在它的当前请求之前的所有请求。4 p i 通过发出一个释放消息( r e l e a s e ，t i ，i ) 而释放掉资源，它将该消息放入自己的数组并传送到所有其他进程。5 当p i 接收到( r e l e a s e ，t j ，j ) 时，它就用这条消息替换q j 当前的内容。6 当p i 接收到( r e p l y ，t j ，j ) 时，它就用这条消息替换q j 当前的内容。很容易看出，这个算法实现了互斥，是公平的，避免了死锁和饥饿的情况：互斥：对进入临界区的请求，根据通过时间戳机制产生的消息的顺序来处理。一旦p i 决定进入其临界区时，系统中就不可能再有r e q u e s t 消息在它自己的消息之前传送。这种情况确实为真，因为p i 到那时已经接收到来自所有其他站点的一条1 9存储虚拟化原理分析发其实现消息，并且这些来自其他站点的消息从注明的r 期来看都晚于它自己的r e q u e s t 消息。通过r e p l y 消息机制，可以确保这一点。记住，两站点之白j 的消息不可能不按顺序到达。公平：严格按照时问戳的顺序接受请求，因此，所有进程具有相等的机会。无死锁：因为时间戳顺序在所有的站点上得到了一致性的维护，因而不可能发生死锁。无饥饿：一旦p i 已经完成了它的临界区，它就传送r e l e a s e 消息。这具有删除p i 的位于所有其他站点上的r e q u e s t 消息的效果，允许其他进程进入其l 临界区“。作为对这个算法效率的度量，为了确保互斥，需要3 ( n 1 ) 条消息：( n 一1 )条r e q u e s t 消息，( n - 1 ) 条r e p l y 消息，( n 一1 ) 条r e l e a s e 消息。提出了对l a m p o r t 算法的改进方法。它试图通过消除r e l e a s e 消息而使原算法达到最优。它仍然使用与以前相同的假设，只是“从一个进程发送到其他