英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
可扩展分布式信息管理系统
Praveen Yalagandula Mike Dahlin
ypraveen@cs.utexas.edu dahlin@cs.utexas.edu
计算机科学系
德克萨斯大学奥斯汀分校
Austin, TX 78712
摘要
我们提出了一个可扩展的分布式信息管理系统（SDIMS），其汇集关于大型网络系统的信息，并且可以作为广泛的大规模分布式应用程序的基本构建块，提供脱钩视图附近的信息和全球信息的摘要视图。作为基本构建块，SDIMS应具有四个属性：对许多节点和属性的可扩展性，适应广泛应用程序的灵活性，安全性和可用性的管理间隔，以及节点和网络工作故障的鲁棒性。我们设计，实施和评估SDIMS，（1）利用分布式哈希表（DHT）来创建可扩展的聚合树，（2）通过简单的API提供灵活性，使应用程序可以控制读写的传播，（3）提供通过对当前DHT算法的简单扩展进行管理隔离，以及（4）通过延迟重新聚合，点播重聚和可调空间复制实现对节点和网络重构的鲁棒性。通过广泛的模拟和微基准测试，我们观察到我们的系统比现有方法具有更大的可扩展性，与平坦的DHT相比，以牺牲适度增加的读取延迟为代价，实现隔离性能，并且优雅地处理故障。
分类和主题描述
C.2.4 [计算机通信网络]：分布式系统 - 网络操作系统，分布式数据库
概述
管理，设计，实验
关键词
信息管理系统，分布式哈希表，网络系统监控
这项工作得到国家科学技术部（CNS-0326001）和德州先进技术计划部分的支持。 达林林还获得了IBM学院合作伙伴奖。
授予个人或教室使用的全部或部分本作品的数字或复印件的许可，无需付费，只要副本不是为了利润或商业利益而制作或分发的，并且副本在第一页上承担本通知和完整引用。 要复制，要重新发布，在服务器上发布或重新分发到列表，需要事先具体的许可和/或费用。
SIGCOMM#39;04，8月30日至9月 2004年3月3日，波特兰，俄勒冈州，美国。
版权所有2004 ACM 1-58113-862-8 / 04/0008 ... $ 5.00。
1.简介
这项研究的目的是设计和构建一个可扩展分布式信息管理系统（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应具有四个属性。首先，系统应该是可扩展的：它应该容纳大量的参与节点，并且应该允许应用程序安装和监视大量的数据。今天的企业和全球规模系统可能会有数万到数百万个节点，这些数字将随着时间的推移而增加。类似地，我们希望支持许多应用程序，并且每个应用程序可以跟踪几个属性（例如，系统的机器的加载和空闲内存）或数百万个属性（例如，哪些文件存储在哪些机器上）。
第二，系统应具有适应广泛应用和属性的灵活性。例如，像NumCPU这样的读取主导的属性很少有变化，而像numProcesses这样的写主导的属性却经常变化。调整为读主导属性的方法在应用于以写入为主的属性时将消耗高带宽。相反，针对写入主导的属性调整的方法将遭受不必要的查询延迟或读取主导的属性的不精确。因此，SDIMS应提供处理不同类型属性的机制，并将调优复制的策略决定留给应用程序。
第三，SDIMS应提供行政隔离。在一个大型系统中，将组织或管理层次结构中的节点排列很自然。 SDIMS应该支持行政管理，
在域内可以满足关于管理域的信息的查询的潜在隔离，以便系统在与其他域的断开连接期间可以运行，以便外部观察者不能监视或影响域内查询，并支持域有效查询。
第四，系统必须对于节点故障和中断是稳健的。 SDIMS应适时适应重新配置，并应提供机制，使应用程序可以在重新配置发生时，将聚合结果中的一致性级别与适应成本进行权衡。
我们从以前的两件作品中得到灵感：Astrolabe [38]和分布式哈希表（DHT）。
Astrolabe [38]是一个强大的信息管理系统。 As-trolabe提供了镜像系统管理层次结构的单个逻辑聚合树的抽象。它提供了一个通用的界面，用于安装新的聚合功能，并为其数据提供最终的一致性。 Astrolabe是稳健的，因为它使用非结构化的八卦协议传播信息及其将子树的所有聚合属性值复制到子树中的所有节点的策略。该组合允许任何通信模式产生最终的一致性，并允许任何节点使用本地信息应答任何查询。然而，这种高度的复制可能会限制系统适应大量属性的能力。此外，尽管ap-proach对于读主导属性有效，但是在一个节点上的更新可能会最终影响所有节点的状态，这可能会限制系统的灵活性，以支持以写为主的属性。
最近对对等结构化网络的研究产生了分布式哈希表（DHT）[18,28,29,32,35,46] - 一种数据结构，其数量结构与节点数量和扩展读写负载对于参与节点之间的不同查询。值得注意的是，虽然这些系统导出了一个全局散列表抽象，但是它们中的许多内部使用可以被看作是一个可扩展的聚合树系统，例如将给定密钥的请求路由到正确的DHT节点。实际上，Plaxton等人的[28]原始应用程序不是导出一般的DHT接口，而是使用层次聚合来允许节点定位附近的对象副本。似乎有吸引力的是开发一种以一般方式公开内部功能的SDIMS抽象，以便聚合的可扩展树可以作为DHT旁边的基本系统构建块。
乍看起来，看起来显而易见的是，简单地使用Astrolabe的聚合抽象的DHT将导致SDIMS。然而，满足SDIMS要求强制解除解决四个问题：（1）如何将不同的属性可扩展地映射到DHT网格中的不同聚合树？ （2）如何提供聚合的灵活性以适应不同的应用要求？ （3）如何适应全球平坦的DHT网格以获得行政隔离财产？和（4）如何提供无结构化八卦和全面复制的鲁棒性？
构成我们SDIMS设计基础的本文的主要贡献如下。
1.我们定义一个新的聚合抽象，它指定属性类型和属性名称，并将聚合函数与特定属性类型相关联。这种排除为利用DHT系统的内部树进行聚合和实现节点和属性的可扩展性铺平了道路。
2.我们提供一个灵活的API，使应用程序可以控制读写的传播，从而降低更新成本，阅读延迟，复制和陈旧。
3.我们增加一个现有的DHT算法，以确保路径收敛和路径位置属性，以实现广告隔离。
4.通过以下方式，为节点和网络重新配置提供鲁棒性：（a）通过延迟重组提供时间复制，保证最终的一致性;（b）确保我们的灵活API允许苛刻应用通过使用可调谐的数据空间复制获得更多的鲁棒性聚合或通过执行快速点播重组来增加潜在的懒惰聚合或两者兼而有之。
我们已经建立了SDIMS的原型。通过对许多部门机器和PlanetLab [27]节点进行模拟和微基准测试，我们观察到，该原型通过使用其灵活的API实现了对节点和属性的可扩展性，造成了一个数量级的最大节点应力与非结构化的闲聊方案相比，实现隔离属性，与平坦的DHT相比，以适度增加的读取延迟为代价，并且优雅地处理节点故障。
这项初步研究讨论了正在进行的系统构建工作的关键方面，但它并未解决构建SDIMS的所有问题。例如，我们认为，我们提供健壮性的策略将与诸如超节点等技术相结合，以及其他正在努力改进DHT [30]以进一步提高粗糙度。另外，尽管在许多树之间分割聚合提高了简单查询的可扩展性，但是与单个树相比，该方法可能使复杂和多属性查询更昂贵。需要额外的工作来了解这种限制对实际工作负载的重要性，如有必要，可以将查询规划技术从DHT抽象[16,19]转换为可伸缩聚合树抽象。
在第2节中，我们将介绍SDIMS为应用程序提供的层次化聚合消除。在第3和第4节中，我们描述了我们的系统的设计，以实现SDIMS的灵活性，可扩展能力和管理隔离要求。在第5节中，我们详细介绍了我们的原型系统的实现。第6节讨论了适应拓扑重构的问题。在第7节中，我们通过实际网络上的大规模模拟和微型基准来评估我们的系统。第8节详细介绍相关工作，第9节总结了我们的贡献。
2.综合摘要
聚合是大规模分布式信息系统的自然抽象，因为聚合通过降低节点来查看关于其附近的状态的详细信息并逐渐更粗糙地摘录系统数据的逐渐增加的子集来提供可扩展性[38]。
我们的聚合抽象是跨越系统中所有节点的树定义的。系统中的每个物理节点都是叶子，每个子树代表一个逻辑节点组。注意，逻辑组可以对应于域中的管理域（例如，部门或大学）或节点组（例如，CS部门中的LAN上的10个工作站）。我们称之为虚拟节点的内部非叶节点由虚拟节点为根的子树的叶子上的一个或多个物理节点进行模拟。我们将在后面的部分描述如何形成这样的树。
每个物理节点将本地数据作为一组（attributeTy pe，attributeName，value）元组存储，如（configuration，numCPUs，16），（mcast membership，session foo，yes）或（file stored，foo，myI-Paddress ）。系统将聚合函数fty pe与每个属性类型相关联，对于系统中的每个级别i子树Ti，系统定义每个（at-tributeType，attributeName）对的聚合值Vi，ty pe，name如下。对于等级0的（物理）叶节点T0，V0，ty pe，name是属性类型和名称的本地存储值，如果不存在匹配的元组，则为NULL。然后级别i子树Ti的聚合值是类型的聚合函数，在每个Ti的k个孩子的聚合值之间计算的fty pe：
|
, . . . ,V kminus;1 |
||||
|
Vi,ty pe,name = fty pe(V 0 |
,V 1 |
). |
||
|
iminus;1,ty pe,name |
iminus;1,ty pe,name |
iminus;1,ty pe,name |
||
虽然SIMS允许任意的聚合函数，但是这些函数通常希望满足分层计算[21]：
f (v1, ...,vn)= f ( f (v1, ...,vs1 ), f (vs1 1, ...,vs2 ),..., f (vsk 1, ...,vn)),其中vi是节点i处属的值。 例如，平均操作，定义为avg(v1, ...,vn) = 1/n.aring;ni=0 vi,不符合期望。 相反，如果属性将值存储为元组（sum，count），则属性满足较低级的计算属性，同时仍允许应用程序从总和和计数值计算平均值。
最后，请注意，对于大型系统来说，难以或不可能坚持探测器返回的聚合值对应于在探针时刻叶片上的当前值计算的函数。 因此，我们的系统只提供弱一致性保证——特别是[38]中定义的最终的一致性。
3.灵活性
我们工作的一个主要创新是灵活的聚合计算和传播。聚合抽象的定义允许在如何计算和
全文共27437字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[143386]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
