Ｊ２９卷第１９期ＶｏＬ２９脑Ｊ９・基金项且论文・计算机工程ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ２００３年１１月Ｎｏｖｅｍｂｅｒ２００３文章■母，ｌ∞ｍｑ４２８（２哪）１９—删２—ｍ３丈嘲景识码ｔＡＯｌｍ蚰．ｍ４，ＴＰ３９３分布式文件系统中的负载平衡技术田一，许鲁（中国科学院计算技术研究所国家高性能计算机工程技术研究中心，北京１０００８０）擅要：Ｊｎ特别是存赭系统成为了计算机系统结构的核心，因而用于组织存储内容并提供使用接口的文件系统中的负载平衡研究也成为提高整个系统性能和可扩展性的重要组成部分。在分析现有文件系统负载平衡技术的优缺点的基础上。提出了一种动态的负载平衡技术，并给出此技术的实现方案和可行性分析。关ｔ爿：分布式文件系统；负载平衡；负载分配ＴｅｃｈｎｏｌｏｇｙｏｆＬｏａｄＢａｌａｎｃｉｎｇｉｎＤｉｓｔｒｉｂｕｔｅｄＦｉｌｅＳｙｓｔｅｍＴＩＡＮＹｉｎｇ，ＸＵＬｕＰｅｒｆｏｒｍａｎｃｅＣｏｍｐｕｔｅｒｓ．ＩｎｓｔｉｔｕｔｅｏｆＣｏｍｐｕｔｉｎｇＴｅｃｈｎｏｌｏｇｙ，ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，ＢｅＵｉｎ９１０００８０）ＩＡｂｓｔｒａｃｔｌＩｎｔｈｅｔｉｍｅｔｈａｔ１／４０ｅｓｐｅｃｉａｌｌｙｔｈｅｓｔｏｒａｇｅｓｙｓｔｅｍｈａｓｂｆｃｏｍｅｔｈｅｃｅｎｔｅｒｏｆｃｏｍｐｕｔｅｒｓｙｓｔｅｍａｒｃｈｉｔｅｃｔｕｒｅ．ｒｅｓｅａｒｃｈ∞Ｉｏ酣ｂａｌａｎｃｉｎｇｉｎＣｅｎｔｅｒｆｏｒＨｉｇｈｄｉｓＵ＇ｉｂｕｔｃｄｆｉｌｅｓｙｓｔｅｍｗｈｉｃｈｏｒｇａｎｉｚｅｓｄａｔａｃｏｎｔｅｎｔ州ｍｉｏｎ出Ｒｅｓｅａｒｃｈａｎｄｐｒｏｖｉｄｅｓａｏ：ｅｓｓｉｎｔｅｒｆａｃｅｈａｓｂｅｃｏｍｅｔｈｅｍｏｓｔｉｍｐｏｒｔａｎｔｐａｒｔｏｆｓｔｕｄｙｔｏｉｍｐｒｏｖｅｔｈｅｐｅｒｆｏｒｍａｎｃｅａｎｄｓｃａｌａｂｉｌｉｔｙｏｆｔｈｅｗｈｏｌｅｓｙｓｔｅｍＡｎａｌｙｓｉｓ（３０ｔｈｅａｄｖａｎｔａｇｅｓａｎｄｄｉａａｄｖａｎｔａｇｅｓｏｆｔｈｅｃｕｎｅｎｔｌｏａｄｂａｌａｎｃｉｎｇｔｅｃｈｎＭｏ科ｉｓｆｉｒｓｔｇｉｖｅｎ，ｔｈｅｎａｄｙｎａｍｌｃ［ｏａｄｂａｌａｎｃｉｎｇｔｅｃｈｎｏｌｏｇｙｉｓｐｒｏｐｏｓｅｄｉｓｇｉｖｅｎｉｎｔｈｅｅｎｄ．ＡＲｃｒｔｈｅｉｍｐｌｅｍｅｎｔａｔｉｏｎｓｃｈｌｄａｎｄｆｅａｓｉｂｉｌｉｔｙ８ｎａ岍ｉｓ，ａｒｅｄｈｃｕｓｓａｄ．ｔｈｅｐｅｒｆｏｒｍａｎｃｅｅｖａｌｕａｔｉｏｎＩＫｅｙｗｏｒｄｓｉＤｉｓｔｒｉｂｕｔｅｄｆｉｌｅｓｙｓｔｅｍ；Ｌｏａｄｂａｌａｎｃｉｎｇ；Ｌａｄａｌｌｏｃａｔｉｏｎｌ问置的提出计算机系统发展到今天，其应用的主流已从科学计算变为泛计算应用，特别是信息服务。这种变化使得计算机在经历以ＣＰＵ为中心和以内存为中心的阶段后，进入了以Ｉ／Ｏ，特别是存储系统为中心的阶段。为了适应信息量和访问量日益增长的需要，人们在积极探索网络服务器体系结构和存储系统访问模式的同时，研究分布式文件系统中的负载平衡技术也成为了热点。目前，服务器系统仍以ＤＡＳ（Ｄｉｒｅｃｔ．ＡｔｔａｃｈｅｄＳｔｏｒａｇｅ）方式的存储设备为主。随着数据量的大量增长，这种方式势必会造成数据传输、数据共享和管理共享等各方面问题。为解决由此带来的性能瓶颈和可扩展性问题，基于网络的存储系统应运而生。基于网络的存储系统是建立在网络存储设备之上的一种高性能、高可扩展的服务器系统，体系结构如图ｌ所示。系统主要包括４部分：应用服务器，系统服务器，管理台和网络存储设备。其中，应用服务器是运行各种用户服务程序的通用服务器，包括Ｅ－ｍａｉｌ、ｗｅｂ和流媒体服务等；系统服务器则为应用服务器提供与存储相关的服务；网络存储设备是一种可以处理网络协议和提供数据访问的智能化存储设备。由于数据被放在飚络上统一管理，因此可以实现数据共享和管理共享。此外，各种网络互联技术和磁盘访问协议提供了高效的数据传输。单个系统服务器无法胜任大型系统中频繁的文件访问操作，在存储系统中需由多个系统服务器提供存储服务。网络应用环境中，文件的访问情况千变万化，即文件的访问频率随时间等各种因素而不断变化。因此，存储系统就必须具有良好的负载平衡能力，将请求处理负载尽可能均匀地分布在多个系统服务器上，以保证系统资源的利用率，提高系统效率和可扩展性。Ｓｏｕｒｃｅ：ＨＰＬ—１９９９・３５Ｒ】９９１００６圈２越界＃■站曲ａｍｆｌ－圈基盒曩目±国家高科技发展计划“８６３＂资助项目（２００２ＡＡＩ式文件系统和存储系统；许鲁，博士、研究员收■Ｈ捆：２００２・ｌｌ－２８Ｅ・ｍａｉｌ：ｔｉａｎｙｉｎｇ＠ｉｃｔａｃ｜ｃｎ１２０１０）作者蕾介：田颖（１９７６一）。女，硕士生．主要研究方向为分布万方数据图２是１９９８年世界杯期间，其网站的日流量统计数据。从世界杯开始到结束，流量呈现出一个延长的“ｆｌａｓｈ－ｃｒｏｗｄ”。为应付这种突发性的访问，存储系统必须提供一个良好的动态平衡处理能力，而现存的系统往往采用了静态的负载分配方式，导致处理能力受限。针对此问题，本文提出了一种动态的负载分配策略和负载的动态再平衡技术。２相关的研究２．１Ｔｉｇｅｒ轴ａｒｋ丈件系统ＴｉｇｅｒＳｈａｒｋ是用于ＡＩｘ操作系统中的一个面向流媒体应用的并行文件系统。从结构上看，它实现了一个支持缓存一致性的分布式ＮＦｓ服务器系统。存储系统的负载平衡主要是通过宽范围的条带化和对象级的复制完成的。由于ＴｉｇｅｒＳｈａｒｋ主要是面向延续性应用，因此当其检测到某个ＮＦＳＣｌｉｅｎｔ正在以缺省播放速率顺序读时。就为其预留带宽，磁盘调度使用截止期限调度算｛去【”。２．２ｓ晒文件系统ＤｕｋｅＵｎｉｖｅｒｓｉｔｙ的ＳＦＳ（ＳｌｉｃｅＦｉｌｅＳｙｓｔｅｍ）是一个分布式Ｉ构ＩＮＦＳ。系统包括应用服务器、系统服务器和存储设备。所有文件的处理被静态地映射到相应的系统服务器。客户服务器通过系统服务器访问文件。为给用户提供一个完全透明的使用环境，系统中加入一个文件系统代理“ｐｒｏｘｙ。该代理采用哈希方式将收到的文件操作请求进行映射并转发给某个系统服务器。由于这种静态的映射机制，因此系统缺乏动态的应变能力ｕ・。２．３Ｌｕｓｔｒｅ文件熏统Ｌｕｓｔｒｅ（ＬｉｎｕｘＣｌｕｓｔ神是ＣｌｕｓｔｅｒＦｉｌｅＳｙｓｔｅｍ公司设计的一个基于存储区域网的文件系统。它采用了类似于ＳＦＳ的系统结构——专用服务器（ＤｅｄｉｃａｔｅｄＳｅｒｖｅｒ）模式。由“ＭｅｔａｄａｔａＣｏｍｒｏｌＳｙｓｔｅｍｓ”负责元数据和目录的处理，且文件的处理到这些服务器的映射是通过哈希方式完成的，数据的传输则是存储设备与客户端直接传递。由于文件到服务器的映射是静态的，Ｌｕｓｔｒｅ的动态处理能力相对较弱。类似于ＳＦＳ，系统服务器的负载并不是根据动态负载情况而加以平衡，这对于系统的可扩展性也是极大的限制”１。综上所速，现有的存储系统或者由于体系结构的限制，或者由于文件处理的限制，均导致系统灵括性较差，动态负载平衡难以进行，因此限制了系统的可扩展能力。３动态负载平衡方法３．１负载分析文件系统操作包括元数据操作和文件数据操作两部分。在分布式文件系统中（以图１所示系统结构为研究背景），元数据的处理分布于多个系统服务器。不同的元数据在不同时刻的访问量是不同的，且元数据的访问存在着局域性（考虑文件访问的局域性），因此，研究元数据的负载平衡即是研究如何将元数据处理负载均匀地分布到各服务器以达到系统最高的性能。元数据处理的负载平衡可以采用多种方式实现，一种常见的做法是将文件映射到系统服务器上，与此文件相关的所有元数据操作都由这个服务器实现。也即服务器上的负载由映射在它上面的元数据的访问量决定。本文也拟采用此种方式，即研究如何将元数据映射到服务器，特别是如何动态地调整这些映射关系实现集群间的负载平衡。我们将负责元数据处理的系统服务器称为元数据服务器，Ｉ］［ＩＭＳ（Ｍｅｔａｄａｌａ万方数据Ｓｅｒｖｅｒ）。具体地说，元数据负载平衡包括两方面：元数据到ＭＳ的映射策略和ＭＳ集群之间的负载动态平衡。此外，文件系统负载平衡还包括热点文件的处理（ＭＳ上的元数据和存储设备上的文件数据），本文暂不考虑。３．２映射策略对于可扩展存储系统，应采用动态的映射策略，即能够根据系统中各ＭＳ上的负载状况灵ｉ舌地进行负载分配，设计考虑包括以下５方面：（１）简单性。负载平衡算法不能过于复杂。文件到系统的映射很频繁，复杂的算法对系统会造成过重的负载ｏ（２１灵活性。体现在以下两方面：一方面它决定了负载动态平衡能力，限制性较强的映射方式会很大程度上限制负载平衡能力；另一方面它决定了能否支持各种用户需求，如厂商Ａ和厂商Ｂ不愿共享同样的系统服务器。（３）公平性。要求抉策算法根据各个服务器的软硬件配置合理地进行负载分配。在存储系统中，服务器可能是异构的，因此需要在不同服务器之间进行负载和处理能力的比较，从而提高系统工作的效率。（４）逻辑性。文件的访问是有局域性的，如当创建一个新文件时。其所在的目录文件和被创建的文件应由同一服务器处理；否则，所带来的分布式操作使得处理更为复杂，效率低下，并且难于恢复。（５）对数据一致性的影响。映射可分为单一映射和多维映射。采用多雉映射时，需要使用分布式锁管理来堆护数据的一致性，增加系统的复杂度，极大地限黼系统的可扩展性和可恢复性。基于上面５种考虑，我们作出如下５个决定：（１）采用极为简单的映射算法。没有任何复杂的计算。（２）不对映射方式作任何限制，保证系统动态平衡和满足用户需求。（３）根据机器的配置情况和物理负载量计算出逻辑负载量对不同服务器进行量度。（４）映射策略充分考虑逻辑性因素，如对创建的文件将其映射到父目录所在的系统服务器。（５１采用单一映射。使文件在系统服务器问的分布完全不相交。简化数据的一致性处理ｔ综上所述。我们的动态映射策略是一种根据元数据服务器当前负载，同时兼顾用户需求、元数据之间逻辑性的单一映射机制。在系统服务器中引入一绑定服务器ＢＳ（ＢｉｎｄｉｎｇＳｅｒｖｅｒ），由其执行映射策略完成元数据到ＭＳ的映射。３．３负羹平衡策略虽然映射策略采用动态机制，但考虑到文件的访问频率不断变化，各服务器的处理能力不同，这些因素都会造成ＭＳ子系统中的负载分配不均，导致整个系统的性能下降，因此进行负载转移就变得必不可少。此外，对于当前的这种２４Ｘ７Ｘ３６５的持续性服务。服务器失效或要下线进行维护、升级时都要进行负载的重分配。ＭＳ集群之间的动态平衡即是通过将元数据进行重映射完成，主要包括平衡决策算法和负载转移实现两部分内容。动态平衡策略的设计考虑包括以下两方面：ｆ１）有效性。保证采用此平衡算法能提高系统性船。进行负载的再分配时，同样要充分考虑到元数据访问的逻辑性。（２）稳定性。运行此算｛岳不能产生抖动现象。基于以上两点，我们采用一种集中式和分布式相结合的负载平衡方法。首先。由Ｂｓ决定进行负载转移的源ＭＳ和目的ＭＳ，然后由源ＭＳ发起负载的转移。４实现方案４．１映射策略实现方案映射策略的实现方案包括３部分：（１）负载信息的收集使用监控系统实现对系统中各个服务器的运行状态信息的收集。运行在ＢＳ上的ＭＳ集群成员管理模块负责收集各个ＭＳ的状态信息，包括配置信息、负载信息。（２）映射决策和算法对于某一ＭＳ发来的元数据绑定请求，ＢＳ上运行映射决策算法动态地选出映射目标ＭＳ。算法考虑如下因素：Ｉ）用户提出的要求（灵括性）；２）ＭＳ，是否想处理这个元数据（逻辑性）；３）ＭＳ．的当前负载状况（公平性）。（３）评价方案使用ＳｐｅｃＷｅｂ９９测试动态映射策略对于Ｗｅｂ应用的效率。使用ＳｐｅｃＳＦＳ测试动态映射策略对于文件服务器应用的效率。４．２次序。考虑实现的简单性，采用以树为单位进行转移。（４）评价方案（与第一部分基本相同）。４．３可行性分析元数据到ＭＳ的映射是一种集中式方法，Ｍｓ集群间负载平衡是一种集中式与分布式相结合的方法。由于集中式方法掌握全局信息，可以做出比较精确的判断，但往往产生瓶颈问尉５“。因此。我们通过一系列技术方法确保将Ｂｓ从系统运行的“前端”放到系统的“后端”，如在应用服务器和元数据服务器中增加元数据映射关系的缓存，将近期访问的元数据的映射关系记录在表中。这样根据元数据访问的局域性，在大部分情况下都可以不需要查询ＢＳ目［Ｉ可以得到活跃元数据所在的ＭＳ地址，从而解决了集中式方法中的瓶颈问题，大大提高了系统的可扩展性。另一方面，为提高可用性，我们也采取了相关措施实现Ｂｓ的ＨＡ。Ｍ蝴橱负藏年衡实现方案５总结本文在分析现有文件系统负载平衡能力不足的基础上，提出了一种动态的映射策略和负载平衡方法。并给出了实现方案和可行性分析。目前，我们已经在国家高性能计算机工负载平衡的实现方案包括４部分：（１）负载信息的收集（与前一部分相同）。（２）决策算法Ｍｓ集群间负载均衡决策包括：决定负载转移的时机，选择负载转移的结点对和选定转移负载对象３部分。针对存储系统结构特点，采用Ｂｓ选取负载转移结点对，重载ＭＳ选取转移负载的集中式与分布式方法相结合的平衡策略。着眼点在于为了减小Ｍｓ的开销，每个ＭＳ不去收集其他ＭＳ的负载信息，系统中只有Ｂｓ收集全局ＭＳ的负载信息，同时ＭＳ根据自身的元数据缓存可以较容易地选取移走哪些负载最有效且负载转移过程中的代价最小。设定两个翊值：分别为发送结点阈值和接收结点阈值。Ｂｓ考察各个ＭＳ的负载，与这两个阈值作比较，选出负载平衡结点对（源ＭＳ，目标ＭＳ）及每对结点之间可以转移的负载量。然后通知源ＭＳ。源ＭＳ考察自身的负载，根据目标ＭＳ可以接收的负载量选出元数据子树进行转移，而目标ＭＳ只要做好接收的准备即可。（３）负载的转移负载转移是指在确定好转移的结点对和负载量后的具体转移过程。实现时要求代价小、效率高，同时预防抖动现象。由于转移的负载是元数据子树，存在转移单位和次序问题。单位可以是一个元数据，也可以是一颗树，如果以元数据为单位，则可以采用深度优先次序，也可以采用广度优先程技术研究中心研制的蓝鲸一１００嘶型网络存储系统中予以了实现，且从当前的一些简单测试结果看。该技术显著提高了系统的效率和可扩展性。下一步我们将进入第２阶段一一对系统进行完整的性能分析和映射策略的优化改进。参考文献ＩＨａｓｋｉｎＲ．ＳｃｈｍｕｃｋＦＴｈｅＴｉｇｅｒＳｈａｒｋＦｉｌｅＳｙｓｔｅｍＰｒｏｃｅｅｄｉｎｇｓｏｆＩＥＥＥｌ９９６ＳｐｒｉｎｇＣＯＭＰＣＯＮ，ＳａｎｔａＣｌａｒａ，ＣＡ，１９９６－０２２ＡｎｄｅｒｓｏｎＤ，ＣｈａｓｅＪ．ＶａｈｄａｔＡＩｎｔｅｒｐｏｓｅｄＲｅｑｕｅｓｔＲｏｕｔｉｎｇｆｏｒＳｃａｌ・ｏｎａｂｌｅＮｅｔｗｏｒｋＳｔｏｒａｇｅＩｎＡＣＭＪｏｕｒｎａｌＴｒａｎｓａｃｔｉｏｎｓｏｎＣｏｍｐｕｔｅｒＳｙｓｔｅｍｓ（ＴＯＣＳ），２００２，２０（Ｉ）３ＢｒａａｍＰＪ，ＺａｈｉｒＲＬｕｓｔｒｅＴｅｃｈｎｉｃａｌ２００卜０７－２９４ＡｒｌｉｔｔＭ，ＪｉｎＰｒｏｊｅｃｔＳｕｍｍａｒｙＶｅｒｓｉｏｎ２，Ｔ．ＷｏｒｋｌｏａｄＣｈａｒａｃｔｅｒｉｚａｔｉｏｎｏｆｔｈｅｌ９９８ＷｏｒｌｄＣｕｐＷｅｂＬａｂｏｒａｔｏｒｙＨＰＬａｂｏｒａｔｏｒｉｅｓＳｉｔｅ．ＩｎｔｅｍｅｔＳｙｓｔｅｍｓａｎｄＡｐｐｌｉｃａｔｉｏｎｓＰａｔｈＡＩｔｏＨＰＬ－１９９９．３５（Ｒ１１．１９９９．０９Ｓｙｓｔｅｍｓ［ＰｈＤｔｈｅｓｉｓ］．ＢｅｒｋｅｌｅｙＵｎｉｖｅｒｓｉｔｙｏｆＣａｌｉｆｏｒ—ｎｉａ，５ＫｕｏｌｉｎＨ．ＡｌｌｏｃａｔｉｏｎｏｆＰＩ＇ｏｃｅｓｓｏｒｓａｎｄＦｉｌｅｓｆｏｒＬｏａｄＢａｌａｎｃｉｎｇｉｎＤｉｓｔｒｉｂｕｔｅｄ１９８５６ＭａｒｃＨＷ．ＲｅｅｖｅｓＡＰＳｔｒａｔｅｇｉｅｓｆｏｒＤｙｎａｍｉｃＬｏａｄＢａｌａｎｃｉｎｇｏｎＨｉ曲ｌｙＰａｍｌｌｅＩＣｏｍｐｕｔｅｒｓＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＰａｒａｌｌｅＩｔｏｌｄＤｉｓｔｒｉｂｕ－ｔｅｄＳｙｓｔｅｍｓ．１９９３，４（９）☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆２００３年。上海国际工业博览会・科技论坛”举办。国际化大都市・上海・数字城市”研讨会在当前信息化大潮中，信息技术的应用与创新必将引发一场新的城市化革命，即数字城市，它是城市信息化目标的具体展现：数字技术、信息技术、网络技术对城市生活各个领域的广泛渗透和融合，实现了对物质城市及其相关现象（经济社会特征）统一的数字化重现和认识，体现了城市规划、建设、管理与服务数字化工程的终极目标。在技术上，数字城市的实现无疑将为调控城市、预测城市、监管城市提供革命性的手段，从而有力地推动城市的可持续发展。上海城市信息化的实现和“数字城市”的建设将大大提高上海在亚太地区和世界范围内的国际竞争力，为上海城市经济的可持续发展发挥巨大的作用。上海在城市信息化和“数字城市”建设上已经取得了引人注目的成就，但是上海与世界发达国家中心城市之间在信息化程度上还存在着不小的差距。为进一步提升信息技术的应用能级，激发上海经济腾飞的活力，促进“上海数字城市”的发展，上海市科学技术协会与上海市计算机学会联合主办的“国际大都市－上海・数字城市”研讨会，于１１月７日在上海科学会堂举行。—．４４－一万方数据
