英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
可扩展的分布式信息管理系统*
Praveen Yalagandula ypraveen@cs.utexas.edu
Mike Dahlin dahlin@cs.utexas.edu
德克萨斯州奥斯汀 德克萨斯大学奥斯汀分校计算机科学系,TX 78712
摘要
我们提出了一个可扩展的分布式信息管理系统( SDIMS )，该系统集结了关于大规模网络工作系统的信息，通过提供附近信息的详细视图和全局信息的摘要视图，可以作为广泛的大规模分布式应用的基本组成部分。作为一个基本的构建块，SDIMS应具备四个特性：对多个节点和属性的可扩展性（scalability）、适应广泛应用的弹性(flexibility)、为了安全性和可用性的管理隔离性（administrative isolation for security and availability）、对节点和网络故障的健壮性（robustness）。设计、实现和评估了一个SDIMS：(1)利用分布式哈希表(Distributed Hash Tables，DITT)创建可扩展的聚集树；(2)通过一个简单的API提供灵活性，使应用程序能够控制读写的传播；(3)通过DITT算法hms的简单扩展提供行政隔离；(4)通过懒惰的重新聚集、按需的重新聚集和可调整的空间复制实现对节点和网络重构的鲁棒性。通过广泛的仿真和微基准实验，我们观察到我们的系统比现有的方法具有更大的可扩展性，与平面DITT相比，以略微增加读取延迟的代价实现隔离属性，并很好的处理故障。
一般用语
管理，设计，实验
关键字
信息管理系统，分布式哈希表，网络系统监控
- 介绍
本研究的目标是设计和构建一个可扩展的分布式贡献信息管理系统( SDIMS )，该系统可以隐藏大规模网络系统的信息，并且可以作为广泛的大规模分布式应用的基本组成部分。监测、查询和响应分布式系统状态的变化是应用的核心部件，如系统管理[ 15，31，37，42 ]、服务放置[ 14，43 ]、数据共享和缓存[ 18，29，32，35，46 ]、传感器监测和控制[ 20，21 ]、组播树形成[ 8，9，33，36，38 ]、命名和请求路由[ 10，11 ]等。因此，我们推测在一个网络化的系统中，SDIMS将提供一个“分布式操作系统主干”，促进新的分布式服务的开发和部署。
对于一个大规模的信息系统，层次聚合是可扩展性的根本抽象。层次聚合并不是将所有信息暴露给所有节点，而是允许一个节点访问附近信息的详细视图和全局信息的摘要视图。因此，在基于分层聚合的SDIMS中，不同的节点可以对查询“查找一个至少有1GB空闲内存的[近旁]节点”或“查找文件foo的[近旁]副本”收到不同的答案。一个通过简化树聚合信息的分层系统[ 21，38 ]，允许节点在保持系统可扩展性的同时访问自己关心的信息。
一个SDIMS要作为一个基本的建筑块，应该具有四个属性。首先，系统应具有可扩展性：应容纳最大数量的参与节点，并应允许应 用程序安装和监视最大数量的数据。当今的企业和全球规模 的系统可能具有数万至数百万个节点，并且这些节点的数量会随着时间的推移而增加。同样，我们希望支持许多应用程序，并 且每个应用程序可以跟踪多个属性（例如，系统计算机的负 载和空闲内存）或数百万个属性（例如，哪些文件存储在哪 些计算机上）。
其次，系统应具有灵活性，以适应广泛的应用程序和属性。 例如，诸如riumCPUs的读取终止属性很少更改值，而诸如 numProcesses等以写入为主的属性更改次数却很频繁。针对 读为主的属性进行调整的方法在应用于写为主的属性时将消 耗高带宽。相反，为写为主的属性而优化的方法将遭受不必要的查询延迟或对读为主的不精确的查询。因此，SDIMS应该提供机制来处理不同类型的属性，并将调整复制的策略决定留给应用程序。
第三，SDIMS应该提供管理隔离。在大型系统中，很自然地 在组织或管理层次结构中排列节点。 SDIMS应该支持管理员主动隔离，可以在域内满足有关管理域信息的查询，以便系 统可以在与其他域的隔离期间运行，从而使外部观察者可以 监视或影响域内查询，并支持域范围内的查询有效地查询。
因此，该系统必须对节点故障和断开连接具有鲁棒性。 SDIMS应该及时适应重新配置，并且还应该提供机制，以便在 发生重新配置时，应用程序可以在汇总结果的一致性级别与 适应成本之间进行权衡。
我们从之前的两幅作品中汲取灵感：Astrolabe [38] 和 DistributedHash Tables (DHTs).
Astrolabe [38] 是一个强大的信息管理系统，因为trolabe提供了一个抽象的逻辑聚合树的抽象，该逻辑树反映了系统的管理层次结构。它提供了用于安装新聚合功能的通用接口，
并最终实现了其数据的一致性。由于Astrolabe使用非结构化的八卦协议来传播信息，并且其将子树的所有聚合属性值复制到子树中的所有节点的策略，因此它很强大。这这种组合允许任何通信模式产生最终的一致性，并允许任何节点使用本地信息来回答任何问题。但是，这种高度的复制可能会限制系统容纳大量属性的能力。同样，尽管该方法对于读取为主的属性非常有效，但一个节点上的更新最终会影响所有节点的状态，这可能会限制系统支持写入为主的属性的灵活性。.
最近对等结构网络的研究导致了分布式哈希表(DHTs) [ 18，28，29，32，35，46 ]-- 一种随节点数而伸缩，并在参与节点间分配不同查询的读写负载的数据结构。值得注意的是，尽管这些系统导出了全局哈希表，但是其中许多系统内部都使用了可看作是可伸缩的聚合树系统，例如将对给定密钥的请求路由到正确的DHT节点。实际上，原始应用程序没有输出通用的DHT接口，而是利用分层聚合来允许节点通过对象的副本来定位。开发SDIMS摘要以通用方式公开此内部功能似乎很吸引人，以便可伸缩的聚合对象可以与DHT一起作为基本的系统构建块。
一看，很明显，简单地将DHT与Astiolabe的聚合抽象融合将导致SDIMS。但是，满足SDIMS需求迫使一个设计要解决四个问题：(1)如何在DHT网格中可伸缩地将不同属性映射到不同的聚合树上？(2)如何在聚合中提供灵活性，以适应不同的应用需求？(3)如何适应一个全局的、平坦的DHT网格以达到管理隔离的特性？(4) 如何在不产生混乱的八卦和完全复制的情况下提供鲁棒性？
本文形成SDIMS设计基础的关键贡献如下：
-
- 我们定义了一个新的聚集函数，它既指定属性类型又指定属性名称，并将聚集函数与父属性类型相关联。此函数为DHT系统的内部树的聚合和利用节点和属性实现可伸缩性铺平了道路。
- 我们提供了一个灵活的API，使应用程序能够控制读写的传播，从而减少更新成本、读取延迟、复制和延迟。
- 我们扩充了现有的DHT算法，以确保路径收敛性和路径局部性属性，以实现管理隔离。
- 通过以下方式，我们为节点和网络重新配置提供了鲁棒性：（a）通过懒惰的重新协商提供时间复制，以确保最终的一致性；（b）确保我们的灵活API允许要求苛刻的应用程序通过使用数据聚合的可调空间复制或通过伪造获得额外的鲁棒性。快速按需重新聚集，以增强底层的惰性重新聚集，或者同时执行这两种操作。
我们已经建立了SDIMS的原型。通过在许多调度机器和PlanetLab [27]节点上进行的仿真和微型基准测试，我们发现该原型通过使用其灵活的API实现了节点和实体的可扩展性，从而导致了与无结构的闲聊方案相比，它的最大节点数量要低得多，以隔离DHT相比适度增加的读取等待时间为代价，实现了隔离性能，并且宽限度地处理了节点故障。
这项初始研究讨论了正在进行的系统构建效率的关键方面， 但是并未解决构建SDIMS的所有问题。例如，我们相信我们提供鲁棒性的策略将与诸如超级节点[22]和其他正在进行的改善 DHT的有效技术[30]紧密结合，以提高结实性。同样，尽管在许多树中拆分聚合可以提高简单查询的可扩展性，但是这种方 法可能会使复杂和多属性的查询比单个树更昂贵。需要更多的工作来理解这种限制对实际工作负载的重要性，并且，如 果有必要，还需要使查询计划技术从DHT抽象[16，19]适应可 伸缩的聚合树抽象。
在第2节中，我们解释了SDIMS提供给应用程序的层次聚合抽象。在第3节和第4节中，我们描述了olli系统的设计，以实现SDIMS的灵活性、可扩展性和管理隔离需求。第5节详细介绍了olli原型系统的实现。第6节讨论拓扑重配置的适应问题。在第七节中，我们通过大规模仿真和真实网络上的微基准来评估olli·系统。第8节详述相关工作，第9节总结olli贡献。
- 聚集摘要
对于大规模分布式信息系统来说，聚集是一种简单的限制，因为聚集提供了可伸缩性，允许节点查看关于状态的详细信息，并逐步粗粒度地合并系统中的数据子集[ 38 ]。
我们的聚合抽象定义在一个树上，该树覆盖了系统中所有节点。系统中每个物理节点是一个叶子，每个子树代表一个节点的逻辑组。请注意，逻辑组可以对应于管理域(e.g., depaitment or university)或域内节点组(e.g., 10 workshy; stations on a LAN in CS depaitment)。内部非叶子节点（我们称其为virtulll nude）由子节点叶子处的一个或多个物理节点（以viltual节点为根）进行模拟。 在后面的部分中，我们将介绍如何在以后的章节中形成这样的树。
每个物理节点将本地数据存储为一组( attributeType，attributeName，value )元组，如( configuration，numCPUs，16 )、( mcast membership，session foo，yes )或( file storage，foo，myIP Address )。系统将聚合函数ftype与每个属性类型相关联，对于系统中的每个level-i子树Ti，系统为每个(属性Type，属性Name )对定义聚合值Vi、type、name如下。对于0级的(物理)叶节点T0，V0，type，name是属性类型和name或NULL的本地存储值，如果不存在匹配元组。那么对于一个第i级子树Ti的聚合值就是该类型的聚合函数，ftype计算跨越Ti的每个第k个子树的聚合值：
虽然SDIMS允许任意聚集函数，但这些函数满足分层计算性质往往是可取的[ 21 ]：
相反，如果一个属性将值存储为元组( sum，count )，则该属性满足分层计算属性，同时仍然允许应用程序从聚合sum和count值中计算平均值。
最后，注意到对于大规模系统，很难或不可能坚持探针返回的聚集值对应于探针瞬间叶子处当前值计算的函数。因此我们的系统只提供弱一致性保证——具体如文献[ 38 ]定义的最终一致性。
- 灵活性
我们工作的一个重大创新是能够实现灵活的聚合计算和传播。聚合抽象的定义使得聚合值如何、何时、何地计算和传播具有相当的灵活性。虽然以前的系统[ 15，29，38，32，35，46 ]实现了单一的静态策略，但我们认为SDIMS应该提供灵活的计算和传播，以有效地支持各种需求不同的应用程序。为了提供这种灵活性，我们开发了一个简单的接口，将聚合抽象分解为三个功能：安装、更新和探测
聚合抽象的定义使我们的系统能够提供连续的策略范围， 从懒惰的聚合计算和读取传播到主动的即时计算和写入传播。 在图1中，我们同时说明了极端策略和中间策略。在懒惰的Updute-Lucul计算和传播策略下，更新（或写入）仅影响局部状态。然后，将读取（或写入）一个读取级别i聚合值的探针发送到该树，将其发送到发出节点的级别i祖先，然后将其向下发送到叶子。然后，系统在树的每一层上计算所需的合计值，直到持有所需值的第i级祖先为止。最后，级别祖先将结果沿着树发送到发出请求的节点。在激进的Update-All立即计算和写入时传播的另一种极端情况下[38]，当更新发生时，更改将聚集在树上，并且每个新的聚集值将泛洪到节点的所有后代。在这种情况下，每个level-i节点不仅维护 level-i子树的聚合值，而且还接收并本地存储其所有祖先的 level-j（jgt; i）聚合值的副本。同样，叶子使用纯本地数据即可满足有关i级聚集的探针的需求。在中间更新策略中，每个子树的根保持子树的当前聚合值，并且在发生更新时，叶节点更新其本地状态，并将更新传递给其父级，然后，每个连续的封闭子树都会更新其汇总值，并将新值传递给其父级。该策略通过将探针发送到叶子的层级存储，然后将总计值向下发送到叶级，来满足叶子对i级聚合值的探测。最后，请注意还存在其他策略。一般来说，Update- Upk- Downj策略聚合到第k个级别，并向下传播第j个级别l ( s，t，i lt;= k )节点的聚合值。
表1：安装操作的参数
SDIMS必须提供广泛的灵活计算和传播策略，以使其成为通用应用程序。应用程序应能够根据其读写比率选择特定的机制，以降低带宽消耗，同时获得所需的响应度和精度。请注意，应用程序广泛安装的属性的读写比率。例如，诸如num CPUs之类的以读为主的属性值很少改变，而诸如numProcesses 之类的以写为主的属性值则经常改变。像Update-All这样的聚合策略非常适用于以读为主属性，如果将其应用于以写为主的属性，则会消耗大量带宽。相反，像Update-Local这样的方法对于写为主
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[261061]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
