皮埃尔和玛丽·居里大学博士论文REGAL团队，LIP 6/INRIA学科：计算机科学选项：分布式系统导演：Rudyar Cortés结构化对等网络成对结构体系的于2017年4月6日在以下陪审团面前呈现：安妮-玛丽·凯尔马雷克INRIA研究局法国雷恩审稿帕斯卡尔·莫利Université de Nantes法国南特审稿彼得·德鲁舍尔科学总监，MPI-SWS德国萨尔布吕肯考官弗兰克·珀蒂皮埃尔和玛丽·居里法国巴黎考官泽维尔·博内尔Santa María瓦尔帕莱索考官奥利维耶·马林上海纽约大学助理教授中国上海顾问皮埃尔·桑斯皮埃尔和玛丽·居里法国巴黎Thesis Directori致谢我想表达我的感激之情，许多人谁作出了贡献，使这篇博士论文是一个美好的经历。首 先 ， 我 要 感 谢 由 Anne-Marie Ker- marrec 博 士 、 Pascal Molli 博 士 、 PeterDruschel博士和Franck Petit博士组成的论文评审团对我的工作进行了评估。你的研究质量令人印象深刻，我很荣幸能向你介绍我的工作。我要特别感谢Anne-MarieKermarrec博士和Pascal Molli博士对论文手稿的深刻评论，使我能够不断提高工作质量。我想对每天与我一起工作的人表示衷心的感谢：Xavier Bonnaire博士，OlivierMarin博士，Luciana Arantes博士和Pierre Sens博士。感谢你们激励我从事分布式系统的研究，感谢你们在过去几年中的建议和友谊。你一直非常善良，我感到很幸运有机会与你一起工作。Xavier Bonnaire博士，感谢您在UTFSM工程项目结束时对我的能力的信任，以及您不断的专业和个人建议;从我做研究的第一步开始，直到今天。我开始做研究是因为你令人印象深刻的知识激励我走上这条道路。感谢你这些年来一起做研究的真正乐趣，以及你在过去几年中不断的帮助（特别是在我在巴黎的第一周博士Olivier Marin，感谢您从我到达Lip6的第一天起就坚定不移地支持我即使你对我知之甚少，当我在法国租第一套公寓时，你同意做我的担保人你教我，一步一步，如何写和目前的研究文章，最重要的是，如何发现新的研究轴线，以及如何提出原创性的研究贡献。博士Luciana Arantes，谢谢你在我读博士期间给我的宝贵建议和帮助你总是可以讨论和喝一杯咖啡。你帮助我提高了我的工作质量，很高兴与你合作Pierre Sens博士，感谢您所有有见地的评论和您对细节的关注，这令人印象深刻。我想特别感谢你在博士最困难的部分提供的所有帮助。每次我离开你的办公室我都得到了我想要的答案！除了我的顾问，我有一个令人难以置信的经验与富豪团队合作我想感谢团队中的每一个人为创造一个良好的工作环境做出的贡献，我很幸运能成为其中的一员。我遇到了热情的人，他们正在从事令人兴奋的项目，每个人都有很好的幽默感，我一直很欣赏。II我想特别感谢现在和过去的博士生：Peter Senna，Denis Jean- neau，MarjorieBournat，Florian David，Maxime Bittan，Gauthier Voron，Hakan Metin，DamienCarver，IlyasTomlilt，LyesHa midouche，BenjaminBaron，JoadovicdeAraujo，Lu-dovic Le Frioux，Redha Gouicem，Jonathan Lejeune，Antoine Blin，AlejandroTomsic，Mahsa Najafzadeh，Francis Laniel，Marek Zawirski，Florent Coriat，Lisong Guo，Maxime Lorrillere，Laure Millet和我在这里遇到的所有其他人，我们在Lip 6工作的那段美好时光我还要感谢CONICYT对我的工作的财政支持和信任在巴黎逗留期间，我遇到了许多令人难以置信的人，他们帮助我把这座美丽的城市变成了一个新家。 我想感谢你们所有人，我们一起分享了所有的美好时光，我们将在未来继续努力。T ha n k y ou T h ′ e o d o r e B l u c h e，L et i c i a G o t o，Sophie Kranzlin，MarionBlondel，Osman Ahmady，Vincent Girard-Reydet，Julien Senet，A l ex and n d re P lan c h o n，L a mi s S h a m a s，L aéet i t i a L au r e n c i a，A n n e A l ice F i e v e t，E v a B r a ba n t，Sofia Gaete，Jerome Thedrel，Zoe Stillpass，Jake Wotherspoon，Corinne Lee，Clarisse L e m a i r e，E m m a D' Bazz，G a b r i e l D' Bazz，Ma r i n eR ess，S t e pha n i e P e r e a u，Julien C r o m b' e，Nicolas Lewandowski，Aranud-Pierre del Perugia Lewandowski，Jess Wigram，Daan Van德·威肯和我有幸见到的许多其他人我要感谢我的家人无条件的支持和爱。谢谢你让我相信你可以实现你的每一个梦想我 想 让 我 的 朋 友 们 知 道 我 的 朋 友 们 是 JavierOliv ares ， TannyaP'erez ，FranciscoGamboa，CristianFuentes，Sebast ian Munoz，GustavoMunoz，MarielVillegas和SergioHenriquez。尽管距离很远，但你在这次冒险中一直支持我！我很高兴您能与我一起迈出这重要的一步。我非常感谢您在过去几年里对我的信任、个人建议和支持。你是我的第二个家，我很高兴有你在我的生活中。我想用我最重要、最美丽、最聪明的另一半ShanAndreaPinna-Griffith来结束这些话。 无论是文字还是文字，都说明了我对你的感情是无限的。我很爱你，我很享受在一起的每一刻。谢谢你的爱，耐心，支持，让我成为世界上最幸福，最幸运的人。我想让你知道我会尽一切努力和你在一起。我把这篇博士论文献给你。好的。iii内容1介绍11.1动机11.2捐款31.3大纲41.4出版物52 最新技术：P2P网络72.1点对点（P2P）网络82.1.1非结构化P2P覆盖网络92.1.1.1非结构化覆盖的局限性102.1.2结构化P2P覆盖网络102.1.2.1杆122.1.2.2糕点122.1.2.3罐142.1.2.4DHT体系结构的比较152.2在DHT上的位置-时间范围查询162.2.1分布式哈希表162.3Over-DHT解决方案172.3.1分布式前缀树172.3.1.1前缀哈希树182.3.1.2地点实验室192.3.1.3光202.3.1.4DRING222.3.1.5ECHO232.3.1.6分布式前缀树242.3.2二叉树242.3.2.1分布式段树252.3.2.2范围搜索树2.4依赖DHT的解决方案272.4.1MAAN27II2.4.2水星282.4.3鱿鱼282.4.4土星29号2.5非DHT解决方案302.5.1基于跳过列表的解决方案312.5.2基于树的解决方案352.5.3基于Voroni的解决方案402.6讨论412.6.1Over-DHT解决方案422.6.2依赖DHT的解决方案432.6.3非DHT解决方案442.7摘要443 Big-LHT：n个最近地理定位查询493.1导言.493.2设计503.2.1查询定义513.2.2索引结构513.2.3制图533.2.4LHT维护553.2.5管理人员的维修3.2.6查询处理593.3评价613.3.1理论评价613.3.2实验评价3.4讨论673.4.1优势673.4.2局限性683.5结论684GeoTrie：一个用于位置-时间范围查询694.1导言。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .694.2设计 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .714.2.1查询定义。 . . . . . . . . . . . . . . . . . . . . . . . . . . . .714.2.2索引结构。. . . . . . . . . . . . . . . . . . . . . . . . . .714.2.3映射。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .724.2.4指标维护 . . . . . . . . . . . . . . . . . . . . . . . . . . .734.2.5查询处理。 . . . . . . . . . . . . . . . . . . . . . . . . . . .75v4.2.6缓存优化。 . . . . . . . . . . . . . . . . . . . . . . . . .774.3评价。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .804.3.1理论评价 . . . . . . . . . . . . . . . . . . . . . . . . .814.3.2实验评价 . . . . . . . . . . . . . . . . . . . . . . . .824.4讨论。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .964.4.1优势 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .964.4.2限制. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .984.5结论。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .98v5结论和今后的工作5.1结论.995.2未来工作100Bibliography参考书目10311vi第1章绪论按位置和时间索引和检索数据允许人们共享和探索在社交网络（如Facebook1、Flickr2和Twitter3）上观察到的大量地理标记数据集。这种场景被称为基于位置的社交网络（LBSN）[RH 13]，由数百万用户组成，共享和执行位置-时间范围查询，以检索在给定地理区域和时间间隔内生成的地理标记数据。一个关键的挑战是提供一个可扩展的架构，允许执行插入和位置的时间范围查询，从大量的用户。为了实现这一点，分布式哈希表（DHT）和对等（P2P）计算范式提供了一个强大的构建块实现大规模的应用程序。然而，DHT不适合支持范围查询，因为使用诸如安全散列函数1（SHA-1）[EJ 01]的散列函数会为了负载平衡而破坏数据局部性。Ex是一种使用DHT的方法，它是一种将块[RRHS04，CRR+05，TZX 10，HRA+11，HASB16]全部分成几个部分的方法。 尽管如此，它们并不针对位置-时间范围查询，并且在查询响应时间和消息流量方面表现出较差的性能。本文提出了两种基于位置和时间的地理标记数据索引和检索的可扩展解决方案1.1动机越来越多的支持GPS的设备，如智能手机和相机，导致产生大量的地理标记数据。每天都有数百万人在社交网络上分享多媒体文件（图片和视频）和评论。在这种情况下，LBSN [RH13]允许用户共享和探索基于位置和时间的地理标记信息。LBSN的一个关键要求是支持大规模的位置-时态查询这些查询检索与给定位置匹配的所有对象1https：//www.facebook.com2https：//wwww.flickr.com3https：//wwww.twitter.com2时间谓词它是在地理区域和时间范围内进行数据提取、探索和分析的一项重大挑战允许数亿用户共享和探索地理标记数据对于拯救生命至关重要，可以帮助找到失踪儿童，或者出于安全目的，允许用户通知自己即将发生的威胁。例如，用户可能想要查看关于感兴趣的地点或地理区域的最新信息 在这种情况下，相应的查询检索由位置间隔覆盖的每个地理区域的最新n个上传的元素。 我们将这种类型的查询称为n-最近位置-时间区域查询。它还可以帮助人们更多地了解公共活动。例如，在晚上20：30之间参加音乐会的人凌晨1：30 可能想要查看来自参加同一场音乐会的人的公开图片和评论。音乐会经理可能希望通过分析图片、评论和标签来获取关于整体音乐会体验的更多反馈。我们将这种类型的查询称为位置-时间范围查询。构建一个允许人们按位置和时间共享和搜索数据的架构对于帮助他们更多地了解给定地理区域和时间间隔内发生的事情至关重要基于位置和时间创建索引允许以较低的查询响应时间执行此类任务位置和时间由地理标记数据中观察到的三个核心参数表示：纬度，经度和时间戳。提出的主要挑战是提供一个可扩展的架构，组织基于位置和时间的数据，这不是一个微不足道的任务，由于多维和不同的位置和时间的表示。集中式关系数据库为存储和索引数据提供了强大的解决方案。然而，大量的用户执行并发插入和位置-时间查询，这对中心服务施加了可伸缩性约束，因为它们存在以下两个主要问题：1. 内存瓶颈。针对大量对象的并发查询可能会使主内存过载。这个问题对查询响应时间有直接影响2. 带宽瓶颈。 带宽目前是一种昂贵且有限的资源，当系统遇到大量并发查询时，带宽可能成为瓶颈。基于集群的解决方案可以扩展服务器的数量，从而缓解存储瓶颈。然而，输出带宽仍然是一个问题，因为它限制了可扩展性和应用场景。另一方面，对等（P2P）计算范例提出了一种替代模型，其允许使用由分布在世界各地的节点提供的资源（存储器、带宽和处理能力）来构建高度可扩展的应用分布式哈希表（DHT）由Pastry[RD01]和Chord[SMK+01]组成，为互联网规模的应用提供了一个简单但功能强大的构建块他们提供了一个get/put路由接口，以O（log（N））消息的形式路由消息，其中N是网络中的节点数。此接口允许执行精确匹配查询3有效地然而，DHT不适合范围查询，因为它们所依赖的哈希函数破坏了数据的局部性。[RRHS04，CRR+05，TZX 10，HRA+11，HASB16，CFCS04，BAS04，SP08、PNT 12]提供了对DHT的范围查询支持。这些解决方案可以支持使用空间填充曲线（SFC）的多维范围查询[Sam06]。但是，它们为范围查询提供了高延迟和消息流量。此外，他们提供的n-最近的位置-时间区查询的支持差。1.2贡献本文提出了两种支持海量地理标记数据集的位置时态查询的体系结构。与基于集群的架构相反，这些解决方案依赖于用户之间共享的资源，而不是额外的专用服务器。所提出的解决方案涉及到DHT的问题，例如Pas ry[RD01]或Chord[SMK+01]。这可以利用DHT的所有理想属性的优势，例如存储负载平衡和通过复制的容错。第一个贡献，称为大位置哈希树（Big-LHT），支持n-最近的位置-时区查询。Big-LHT随DHT节点的数量而扩展，并提供对地理区域内生成的最后数据项的直接数据访问它根据位置生成一个主索引，根据上传时间生成一个辅助索引主索引将输入数据集划分为地理区域，其中区域的大小二级索引按上传时间对输入数据集进行排序，类似于时态日志。Big-LHT提供以下主要属性：低插入和索引维护成本。 使用O（log（N））消息执行插入，其中N是DHT节点的数量。索引维护操作在消息数量方面成本较低。例如，拆分索引维护操作只需要O（log（N））消息。存储数据分发。Big-LHT提供了良好的存储数据分布，这略微取决于地理区域的大小例如，使用由N= 100个DHT节点组成的网络，没有节点存储超过数据项总数的4%这个结果接近理想的数据分布，其中每个节点（N= 100）存储的数据项总量的1%插入负载平衡。Big-LHT为需要定义小地理区域（如兴趣点（POI））的应用程序提供了良好的插入负载平衡。但是，对于需要定义大地理区域的应用程序，负载平衡会恶化.这是因为每个地理区域的大小都是预先定义的（静态数据分区）。第二个贡献，名为GeoTrie，支持可扩展的位置时间范围查询。GeoTrie的主要组成部分是一个三维分布式索引，···4索引数据的基础上（纬度，经度，时间戳）元组作为关键字到分布式前缀八叉树。与Big-LHT相比，GeoTrie引入了一种动态分区策略，可以适应实际的数据分布，从而提供可扩展性和负载平衡。它包括一个客户端缓存和一个乐观的协议，大大减少了消息的传输和延迟的时间成本，以简化哈希树（PHT）[RRHS04]4。GeoTrie提供以下主要属性：低延迟和消息流量。使用由数百万个上传到Flickr的带有地理标记的多媒体文件组成的数据集进行实际评估的结果，该数据集测量消息流量、负载平衡以及插入和范围查询的延迟。结果证实，与最接近的解决方案（PHT）相比，GeoTrie提供了低延迟和低消息流量。例如，GeoTrie执行插入的速度比PHT快2.47倍，消息减少了80.4%范围查询的执行速度提高了2.64倍，消息减少了31.75%负载平衡。该架构确保插入和位置-时间范围查询的自然负载平衡。这是因为GeoTrie维护前缀树的直接访问属性，这允许客户端节点直接联系任何GeoTrie节点。本文的主要贡献如下：1. 很大一种新的可扩展的分布式数据结构，建立在一个分布式哈希表的顶部，支持n-最近的位置-时区查询，低插入成本和低索引维护成本。Big-LHT将输入数据集划分为地理区域，并提供对每个区域生成的最新数据项的直接访问2. GeoTrie一个完全分布式的全局索引，建立在一个分布式哈希表之上，支持位置-时间范围查询。GeoTrie基于纬度、经度、时间戳元组动态地将数据索引到分布式前缀八叉树中。它提供了可伸缩性、负载平衡和容错等属性。它引入了一个客户端缓存协议，减少了插入和范围查询的延迟和消息流量与当前的解决方案相比，它提供了更低的消息流量和更低的延迟。1.3纲要本论文的写作思路如下：第2章介绍了P2P网络，并提出了一个关键的评估的主要研究工作，索引的DHTs。现有的解决方案分为三组：（i）Over-DHT解决方案，（ii）覆盖依赖解决方案，和（iii）非DHT解决方案。图4建立在分布式哈希表之上的著名前缀树索引结构··5第3章和第4章分别介绍了Big-LHT和GeoTrie。它们被组织成三个主要部分：（一）设计，（二）理论和实践评价，（三）讨论的主要优点和局限性。最后，第五章对本研究工作进行了总结，并提出了未来研究。1.4出版物由于本论文的研究阶段不同，以下研究工作已在国际会议上发表。1. R. 好吧，X。Bonnairee，O. 马林湖 是的，P。 SE NS。2. R. 好的，奥。 M arin，X. 博纳雷湖;Arantes，P. SENS。3. R. 好吧，X。Bonnaire，O.Marin，P. SENS。4. X. 博纳伊雷河（R.好的，弗。 Ko rdon，O. MARIN。67第2P2P网络内容2.1点对点（P2P）网络82.1.1非结构化P2P覆盖网络。. . . . . . . . . . . . . .92.1.2结构化P2P覆盖网络102.2在DHT上的位置-时间范围查询162.2.1分布式哈希表162.3Over-DHT解决方案172.3.1分布式前缀树172.3.2二叉树242.4依赖DHT的解决方案272.4.1MAAN272.4.2水星282.4.3鱿鱼282.4.4土星29号2.5非DHT解决方案302.5.1基于跳过列表的解决方案312.5.2基于树的解决方案352.5.3基于Voroni的解决方案402.6讨论412.6.1Over-DHT解决方案422.6.2依赖DHT的解决方案432.6.3非DHT解决方案442.7摘要448本章介绍了主要的研究工作，旨在创建数据局部性的结构化P2P网络，以支持范围查询。我们简要介绍了P2P网络，分为非结构化和结构化网络。然后，我们提出了一个位置-时间范围查询的定义和结构化P2P网络上实现这样的查询的主要问题从这一点上，我们专注于提出主要的研究线索，以克服这些问题。最后，我们提出了一个关键的评估这些解决方案的延迟，消息的复杂性和负载平衡。(a)（b）对等模式图2.1：客户端-服务器模型与P2P模型2.1对等（P2P）网络基于互联网的应用程序在用户数量和计算资源方面的持续和广泛增长，对客户端-服务器范式的集中化性质提出了挑战。这些应用程序最相关的需求之一是可扩展性，[Neu94]中定义如下。定义1（可扩展性）如果一个系统可以处理用户和资源的增加而不会遭受明显的性能损失或管理复杂性的增加，那么它就是可伸缩图2.1a展示了客户机-服务器模式的一般模型。服务在由一个或多个服务器组成的中央实体上维护。人们普遍认为，如果没有大量的资源，这种范式就无法完成可伸缩性的定义此外，其集中的组织结构容易出现资源瓶颈。对等（P2P）网络和计算范例旨在分散服务。它提出了一种不同的模型，由称为对等体或节点的自治实体组成，这些实体共享计算资源（CPU，存储和带宽），以实现共同的任务。图2.1b给出了它的一般模型。节点通过称为对等覆盖网络或简单对等网络的逻辑网络中的互联网链路连接到一组邻居。9[01 -04][02 - 04 - 05][02 - 04]定义2（点对点）一种平等的、自治的实体（对等体）的自组织系统，其目标是在网络环境中共享使用分布式资源，避免中央服务。这个基本定义赋予对等网络以下理想的属性。1. 自我组织。节点能够在没有任何中央控制的情况下彼此交互这是对等系统的主要属性，它将范式从客户端-服务器范式转移2. 分散的资源使用。节点的可用资源（CPU、存储和带宽）是分布式的，并尽最大努力共享其负载分布。3. 可扩展性。它实现了上述可伸缩性的定义（参见定义1）。4. 容错能力。单个节点的故障不得影响系统的正确运行通常，资源r由属于资源标识符空间I（r）的资源标识符id（r大多数对等网络支持的基本功能如下。• Put（n，r）：将资源r添加到节点n上。Get（n，id（r））：从节点获取标识符id（r）表示的资源n.Query（q，nq）：获取nq的所有节点标识符，这些节点标识符保存完成查询谓词q的资源。在文献中已经提出了实现这些特征的许多解决方案它们可以分为两大类：非结构化覆盖网络和结构化覆盖网络2.1.1非结构化P2P覆盖网络在非结构化覆盖网络中，节点可以独立于其状态自由地加入网络。这些网络通常呈现图形结构或分层结构。这两种结构之间的主要区别在于，在前者中，所有节点都被视为平等的实体，而第二种结构添加了一个由称为超级对等点的节点组成的层。超级对等点代表一组对等点，它们通过中心节点与更大的系统交互。图2.2给出了这两个模型的示意图使用这种覆盖的系统的一个流行示例是第一代点对点文件共享应用程序，如Gnutella[Rip01]。可以通过以下属性来描述这种P2P网络··10(a) P2P图形结构（b）P2P层次结构图2.2：图结构与层次结构网络知识。节点知道一组邻居（本地知识）。也就是说，没有节点维护系统的整个状态资源知识。没有关于资源位置的隐含知识也就是说，节点只知道自己的资源。搜索算法。 由于没有资源监督，搜索必须使用泛洪技术（如广度优先搜索算法（BFS）[Cor09]）通过相邻节点传播。搜索消息被转发到所有邻居，邻居依次转发它，直到完成了生存时间（TTL）数量的步骤为了避免循环转发，每个节点都可以记住最近的消息并丢弃重复的消息。2.1.1.1非结构化覆盖非结构化覆盖网络的主要优点是维护成本低然而，缺乏资源监督导致执行搜索的高消息流量。在最坏的情况下，可以访问所有节点，以便知道系统中 已经提出了几种改进，以减少在BFS算法中访问的节点数。它们包括选择转发[SBR04]、迭代扩展[YGM02]和随机游走[LCC+02]。这些算法虽然减少了搜索的成本，但是它们仍然可能需要访问所有节点以便找到数据项。2.1.2结构化P2P覆盖网络结构化P2P覆盖层网络[SMK+01，RD01，RFH+01]是一种基于结构化P2P网络的网络结构，它通过减少在非结构化覆盖层上观察到的资源知识的查找来降低查找消息的流量开销。它们通过强大的网络拓扑实现这一目标，···
我的内容管理
展开
