没有合适的资源?快使用搜索试试~ 我知道了~
分布式存储系统中的一致性:基于云存储应用的理论基础引用此版本:保罗· 维奥蒂Cohérence dans les systèmes de stockage distribués:fondements théoriques avecapplica- tions au cloud storage.数据库[cs.DB]。Télécom ParisTech,2017.英语NNT:2017ENST0016。电话:02113900HAL Id:tel-02113900https://pastel.archives-ouvertes.fr/tel-021139002019年4月29日提交HAL是一个多学科的开放获取档案馆,用于存放和传播科学研究文件,无论它们是否已这些文件可能来自法国或国外的教学和研究机构,或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire2017-ENST-0016EDITE-ED 130巴黎理工大学博士pour obtenir le grade de docteur délivré par巴黎科技电信« INFORMATIQUE et RESEAUX »专业目前和今后的出版保罗·维奥蒂le 6 avril 2017分布式存储系统中的一致性:云存储Directorde thèse:M. 马尔科·武科利奇陪审团M. Pietro MICHIARDI,EURECOM主席,数据科学部专家M. Nuno NEVES,里斯本大学计算机科学系讲师,特别报告员M. Marc SHAPIRO,Directeur de Recherche,UPMC-LIP 6 and Inria特别报告员Sonia BEN MOKHTAR女士,Chercheuse,CNRS和INSA LyonExaminatriceM. Petr KUZNETSOV,Professor,INFRES,Télécom ParisTech巴黎科技电信巴黎理工学院电信学院与摘要工程分布式系统是一项繁重的任务:性能,正确性和可靠性的设计目标交织在复杂的权衡中,这已经被多个理论结果所概述。随着计算和存储转向分布式架构,这些权衡变得越来越重要。此外,在现代编程工具中普遍缺乏系统的方法来解决分布问题,这使得这些问题变得更加严重-特别是现在大多数程序员必须接受分布的挑战。因此,在编程抽象、应用需求和存储语义之间存在明显的鸿沟,这阻碍了设计人员和开发人员的工作本论文提出了一套贡献的总体目标设计可靠的分布式存储系统,通过检查这些问题,通过棱镜的一致性。 我们首先提供一个统一的,声明性的框架,正式定义一致性语义。我们使用这个框架来描述和比较在以前的文献中提出的50多个非事务一致性语义。这个框架的声明性和可组合的性质,使我们能够建立一个部分的一致性模型,根据其语义强度。我们通过设计和实现Hybris,一个存储系统,利用不同的模型和语义,以改善公共云存储平台通常提供的弱一致性,展示了可组合性的实际好处我们证明了Hybris最后,我们提出了一种新的技术来验证真实世界的存储系统提供的一致性保证这种技术利用我们的声明性方法的一致性:我们认为一致性语义不变的存储系统执行的图形表示初步的实现证明了该方法的实用性和有效性,以改善国家的最先进的一致性验证。我简历La concept des systèmes distribués est une tâche onéreuse : les objectifs deperformance, Ces compromis sont devenus de plus en plus importants à mesure que lecalcul et le stockage se sont déplacés vers des architectures distribuées. 此外,在现代程序设计的过程中,缺乏解决这些问题的系统方法,这使得程序的大部分时间都在为应用程序的分发提供保护。 因此,它存在一个由程序设计的抽象、应用的必要性和储存的系统组成的系统,它包含了概念设计和开发的工作。这是一个关于分布式存储系统概念的总体贡献,并对这些问题进行了研究。Nousprofessions par fournir un crawl uniforme et déclarative pour definir formellement lesmodèles de cohérence.Nous utilisons ce crawl pour décrire et comparer plus de cohérencenon transactionnelles proposés in la littérature.这种干部的解释性和综合性使我们能够在安全部队基础上对协调模式进行分类。我们在实践中取得了一些先进的成果,在实施混合动力系统时,利用不同的模式建立了一个储存系统,通过在语言中提供储存服务来提高总体的一致性。我们必须确保d'Hybris的效率,并确保其能够容忍运费价格上的服务仲裁错误最后,我们提出了一种新的技术,以验证世界储备系统提供的一致性保证。 这一技术支持我们对一致性的理解:我们认为一致性模型对于存储系统执行的图形表示是不变的。 Une enÜuvre préliminaireprove cette approche pratique et utile pour amélibrary l'état de l'art sur la vérification de lacohérence.确认有人说,不是没有理由,追求博士学位是一个孤独的努力。虽然我不能否认这一信念,但我不能不感谢同事、经验丰富的研究人员、家人和朋友的宝贵支持首先,我要感谢我的博士生导师马尔科·武科利奇(Marko Vukolić),感谢他对我的信任,让我有机会踏上这段旅程;感谢他让我走上了一条有益的探索之路--尽管我倾向于探索、徘徊和迷失;感谢他教会扎实而严谨的研究工作的内在价值。我感谢论文委员会的所有成员花时间阅读这篇论文,并提供了建设性和有益的反馈。还要特别感谢Pietro Ziardi教授和Pietro Ziardi教授。 Maurizio Filippe在Eurecom年轻而有前途的数据科学部门中担任热情和忙碌的研究人员的鼓舞人心的例子。我还要感谢欧洲通信公司的同事们,他们是我来到这里的共同经历:Alberto Benegiamo、Shengyun Liu 、 Yongchao Tian 、 Xiaohu Wu 、 Jingjing Zhang 、 Romain Favraud 、Laurent Gallo、Mariano Graziano、Andrea Enrici、Martina Cardone、Xien Jiang、IrfanKhan、Robin Thomas、Luigi Vigneri、Fabio Pulvirenti、Daniele Venzano、KurtCutajar、Francesco Pace、Marco Milanesio、Paul Pidou、Hung Phan和Trung Nguyen。 谢谢你们所有人的快乐和同情的陪伴!衷心感谢那些让我在蔚蓝海岸度过愉快和有趣的朋友最后但并非最不重要的一点是,我承认我在世界上一个富裕的地方出生和长大,并享受教育的最高特权是一种盲目的运气 对于这一切,以及他们持续不断的爱和支持,我感谢我的父母。v我不想离开你:我只想赚钱,我的公司不想离开我,我的公司也不想离开我。我先要到一个地方去,从那里来的人,是预定要来的。黑人,印第安人,穷人,放纵和宽恕。我明白了,不是吗?他把它拿出来,把它拿出来。埃斯科必须独自一人为我编织,为我所需要的衣服编织,他没有能力;他没有,他接受了所有人的命运。他的车是永恒的,我的车也是永恒的P. 莱维镇一颗同样的英雄之心,时间和命运使他变得软弱,但他有坚强的意志去奋斗,去寻找,去发现,而不是屈服。A. 丁尼生vi内容1介绍11.1一个表达一致性的语义框架。. . . . . . . . . . . . . . . . .31.2强大的混合云存储。. . . . . . . . . . . . . . . . . . . . . . . . . . .41.3自动声明一致性验证。. . . . . . . . . . . . . . . . .51.4概述和以前发表的工作。. . . . . . . . . . . . . . . . . . . . .62非事务性分布式存储系统72.1导言。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.2系统型号102.2.1第10章2.2.2操作、历史和抽象执行112.2.3复制数据类型和返回值一致性132.2.4一致性语义学132.3非事务一致性语义152.3.1线性化和相关的2.3.2弱一致性和最终一致性182.3.3PRAM和顺序一致性202.3.4会话保证212.3.5因果模型232.3.6基于耐久性的模型252.3.7叉车模型282.3.8复合和可调语义302.3.9Per-objectsemantics每对象语义322.3.10同步模型34VII2.4相关工作362.5摘要383强大且高度一致的混合云存储393.1导言。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .393.2 Hybris概述。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .433.2.1系统模型。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .433.2.2 Hybris数据模型和语义。. . . . . . . . . . . . . . . . . . . .443.3 Hybris协议。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .463.3.1概述。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .463.3.2输出协议。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .473.3.3在普通情况。. . . . . . . . . . . . . . . . . . . . . . . . .483.3.4垃圾收集。. . . . . . . . . . . . . . . . . . . . . . . . . . . .483.5最坏的情况. . . . . . . . . . . . . . . . . . . . . . . . . . .483.3.6运输工具. . . . . . . . . . . . . . . . . . . . . . . . . . . . .503.3.7删除和删除. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .513.3.8保密。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .513.3.9擦除编码。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .513.3.10较弱的一致性语义。. . . . . . . . . . . . . . . . . . . . . .523.4执行。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .543.4.1基于ZooKeeper的RMDS。. . . . . . . . . . . . . . . . . . . . . . . . .543.4.2基于咨询的RMDS。. . . . . . . . . . . . . . . . . . . . . . . . . . .563.4.3交叉容错RMDS。. . . . . . . . . . . . . . . . . . . . . . . .563.4.4优化。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .573.5评价。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .593.5.1实验1:普通情况下的潜伏期。. . . . . . . . . . . . . . . . . .593.5.2实验2:故障下的延迟。. . . . . . . . . . . . . . . . . . .613.5.3实验3:RMDS性能。. . . . . . . . . . . . . . . . . . .623.5.4实验4:RMDS地理复制。. . . . . . . . . . . . . . . . . .643.5.5实验5:缓存。. . . . . . . . . . . . . . . . . . . . . . . . . .663.5.6实验6:Hybris作为个人存储后端。. . . . . . . . . .663.5.7成本比较。. . . . . . . . . . . . . . . . . . . . . . . . . . . . .683.6相关工作. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .703.7总结734自动声明一致性验证754.1一、导言. 754.2A declarative semantic model声明性语义模型774.3基于属性的一致性验证784.4讨论814.5今后的工作824.6摘要835结论855.1Towardsa cross-stack principal approach to consistency. 855.2行星尺度的一致性和组成的挑战865.3分布式系统正确性86A 一致性同品种器械总结111B一致性语义之间强度关系的证明115C一致性语义和实现117D Hybris:证明和算法121D.1Hybris协议122D.2正确性证明124D.3Hybris线性化的替代证明127E法语摘要131E.1Lacohérence dans les systèmes de storkage répartis non transactionnels131E.2Stockagerobuste et fortement cohérent dans le Cloud hybrid134E.2.1PrincipalescaractéristiquesE.2.2Implementationet résultats执行和结果137E.3Vérificationdéclarative et automatiée de la cohérence138E.3.1Principalescaractéristiques特点139第1介绍在过去的十年中,云计算的兴起以及存储和计算成本的稳步下降[12,152],使得互联网规模和移动应用程序得到广泛采用。 随着这些普及服务的用户产生越来越多的数据(所谓的“大数据”),企业和政府努力收集和分析它们以提取有利可图的信息。反过来,数据密集型应用程序的日益普及以及摩尔定律的消亡[ 224 ]促使设计人员采用横向 数据存储层在此类系统的架构中具有突出的作用,因为它通常负责解决并发和分布挑战的关键任务[97,197]。分布式系统确实是出了名的难以设计和编程,因为有两个内在的不确定性来源困扰着它们的执行。首先,由于通信的复杂性,消息传递的顺序和时间是不确定的。其次,系统组件和通信尝试的失败可能导致不完整的结果,甚至损坏应用程序状态。为了应对这些挑战,研究人员构思了一系列理论结果[111,120],通过暴露正确性,可靠性和性能的多方面权衡来塑造设计空间。 根据这些研究,从业人员开发了不同的数据库系统并将其商业化。 第一代数据库系统的设计反映了一个时代,在这个时代,计算主要是集中的,垂直扩展仍然是一个可行的选择。在这种情况下,数据库通常提供强大的事务语义,例如可串行化[50]。简而言之,可串行化保证了操作包(即事务)的并发执行将等效于某些串行执行。然而,在过去的十年中,新一代数据库系统-通常称为“NoSQL”系统- 出现了 这个新的、定义松散的系统家族的共同特点是它们对数据库状态和查询结果的语义保证较弱。实际上,NoSQL存储放弃了事务性的强语义,以提供更大的可伸缩性和性能1第1章介绍2通过分配[96,237]。在实践中,检查和强制执行正确性约束的负担通常是模糊的,留给程序员-经常导致容易出错的分布式应用程序[33]。因此,新一代的研究工作和产品已经努力弥合正确性和可扩展性之间的鸿沟,通过提供强语义抽象的优化实现[192,257]或通过暴露匹配特定应用程序语义的权衡[34,125]。在这篇论文中,我们通过一致性的棱镜来构建可扩展和正确的分布式存储系统,从而解决设计和工程难题。一致性是一个正确性语义概念,它位于可靠分布式系统设计中所涉及的复杂约束和需求集的核心。其结果直接影响用户体验和系统的工程方面,跨越不同的堆栈层和域。 出于这个原因,一致性构成了表示和分析分布式系统的理想工具。然而,我们目前缺乏一个全面的理论基础来定义和比较一致性语义。反过来,缺乏严格的一致性术语和语法会阻止设计人员发现和试验进一步可能的正确性和性能权衡。此外,一个实用的基本语义框架将使我们能够推理其组合的潜在好处,并将使更准确的技术来测试现有系统的正确性。本文试图填补这一空白的研究文献。具体而言,本文的贡献可以概括如下:— 我们设计了一个语义模型来描述一致性概念。使用这样的模型,我们提供了正式的定义,迄今为止最流行的语义定义的研究人员和从业人员的非事务性商店。— 我们设计并评估了一个键值存储系统,该系统提高了公共云存储的健壮性和一致性,但保留了可扩展性和运营优势。我们的设计利用了两种不同的一致性语义的良好的可组合性,并有效地利用公共和私有存储资源。— 我们描述和评估一种新的一致性验证方法 我们的方法侧重于自动验证的一致性语义的有效性,作为存储系统执行的声明性不变量。在本章的其余部分,我们将阐述我们的每一个关键贡献,并列出论文大纲。1.1. 表达一致性的语义框架31.1表达一致性的语义框架尽管它在并发和分布式系统的设计中具有相关性,但一致性的概念在历史上缺乏一个共同的参考框架来描述其在研究人员和实践者社区中的各个方面 在过去,研究和行业之间的一些联合努力有助于形式化,比较甚至标准化事务语义[21,126,8]。然而,这些工作不包括过去十年的数据库研究的进展,他们不考虑非事务语义。最近,由于NoSQL存储的日益普及,非事务一致性又重新流行起来。因此,新的模型已经被设计来考虑容错问题和应用程序不变量的各种组合。研究人员一直在努力制定正确性方面的最低要求,因此,协调,以允许设计快速但功能强大的分布式系统[34,30]。此外,一个正在进行的令人兴奋的研究趋势一直在利用不同的工具和堆栈层来解决这个问题,从编程语言[16]到数据结构[213]和应用程序级静态检查器[219,125]。然而,尽管最近对存储正确性的不同方面进行了积极的研究,但我们目前缺乏一个合理而全面的模型来推理一致性。作为本论文的第一个贡献,我们提出了一个框架来定义和比较非事务一致性语义。这个框架的目的是在一个最小的声明性,可组合的属性集内捕获一致性的所有突出方面。我们使用这个框架提供了一个正式的分类法,在过去三十年的研究中引入了五十多个一致性语义。由于这些新的形式定义,我们能够比较和定位它们在一个部分有序的层次结构,根据它们的语义“强度”。此外,我们将这些语义映射到研究文献中描述的原型和成熟系统的相应实现。我们相信这一贡献将作为第一个规范化的步骤,并在未来的分布式系统设计的辩论中带来进一步的清晰度此外,我们希望这项工作将有助于研究人员从事进一步探索的成分的一致性语义。本论文的第二个贡献,我们将在下一节中总结,代表了在这个研究方向上的第一步第1章介绍41.2强大的混合云存储最近在“云存储”商业标签下出现的高可用性和可扩展的存储系统从根本上改变了公司和最终用户处理数据存储的方式。云存储提供了前所未有的按需可扩展性,利用全球范围的数据复制增强了持久性,并方便地卸载了操作任务。然而,云存储也提出了有关数据隐私,完整性和可用性的新挑战[128]。此外,不同云提供商之间缺乏互操作性标准大大增加了转换成本[4]。最后,云存储因提供弱一致性保证而臭名昭著[237]。为了克服这些问题,研究人员设想了复合系统,使用多个云存储来分发信任并提高可靠性-这种方法通常被称为多云。与此同时,云提供商已经开始提供混合云服务,利用内部资源来存储机密数据。不幸的是,混合云和多云方法都存在很大的缺点。多云方法受到其跨云通信协议固有的严重性能限制。此外,容忍任意云故障的性能和货币成本非常高,并且一致性保证仅与底层云的一致性保证成比例[53]。 另一方面,商业混合云存储仍然存在与使用单一云相关的安全性和可靠性问题。作为本论文的第二个贡献,我们提出了一个混合多云键值存储的设计和评估,我们称之为Hybris。Hybris通过公共云和私有资源的组合,结合了混合云和多云存储的优势 它容忍任意的(例如,恶意)云故障,以承受得起的价格容忍中断。有趣的是,Hybris的设计是一致性语义组合的一个实际例子。其结果的一致性是由各个子系统提供的最强的。也就是说,即使公共云的一致性较弱,Hybris也能提供强一致性。Hybris高效且可扩展,因为它将轻量级元数据存储在私有场所,同时在少数云存储上复制或擦除编码批量数据。我们实现了Hybris协议,并在不同的环境中对其进行了基准测试,包括地理复制部署和存储同步应用程序的后端。 我们的评估表明,Hybris的性能优于同类最先进的强大云存储系统,并接近基本商品云存储的性能。1.3. 自动声明性一致性验证51.3自动声明一致性验证虽然我们在Hybris上试验了存储系统的设计,但大多数现实世界的工程都需要处理现成的商业系统。因此,软件工程的关键部分在于理解给定架构的每个组件带来的假设和保证是什么,以及它们是如何组成的。不幸的是,这些假设和保证通常被原始开发人员表达得很差(如果有的话)。此外,他们的规范中采用的术语通常不使用一组标准的明确概念,进一步阻碍了集成任务。在存储系统及其一致性保证方面尤其如此通常情况下,一致性规范实际上是以一种非正式的,因此不精确的方式表达的;它们涉及特定的设置,其有效性取决于特定的假设。因此,它们是不兼容和不可比的,从而导致复杂和容易出错的测试技术。研究人员对这个问题提出了不同的方法。文献中的一些作品提出并完善了算法,以确定执行是否尊重强一致性语义[191,122]。另一种流行的方法是通过客户端陈旧性测量来量化最终的一致性[47,169]。最后,事务存储语义传统上通过采用基于图的方法进行验证[8,254]。尽管所有这些技术都是有效的,但它们未能涵盖一致性谱的整体和元素一致性语义的组成。作为本论文的第三个贡献,我们提出了一个自动化的声明性一致性验证方法。 为了实现这一点,我们提倡采用我们在第2章中介绍的声明式语义模型来表达一致性。 这样的公理模型允许将一致性仅仅视为存储系统执行的不变量。反过来,将一致性视为不变式允许应用高级验证技术,例如基于属性的测试[83]。因此,我们开发了封面,一个原型的验证框架,实现基于属性的一致性验证。Conver允许用户选择一组在执行过程中必须遵守的一致性谓词。然后,它自动生成由并发读写操作组成的随机执行,可能是为了更好地验证特定的一致性语义而定制的。在每次执行过程中,Conver都会验证所选一致性谓词的有效性,并且在不一致的情况下,它会输出一个可视化,突出显示导致异常的操作序列。此外,Conver可以通过终止进程和创建网络分区来在存储系统中注入故障总之,Conver将程序员从生成和运行准确测试以验证存储系统正确性的负担中解脱出来。第1章介绍61.4大纲和以前发表的工作本论文的其余部分如下进行第二章介绍了一个定义一致性语义的声明式语义框架,并对各种一致性模型进行了综述。附录C和附录A中给出了两个表,总结了表达一致性语义的谓词及其实现。 在附录B中,我们证明了一致性语义之间的强度关系,遵循我们在第2章中提供的形式化定义。第3章讨论了云存储面临的挑战,并介绍了Hybris。 Hybris的正确性证明和算法列表推迟到附录D。第4章考虑了验证数据库正确性条件的障碍,并介绍了一种基于属性的方法。第五章是本文的结论,并对今后的工作进行了讨论。本论文包括以前发表的研究工作与几个合作者共同特别是,第2章包括来自以下方面的材料P. Viotti和M.Vukolić,ACM Computing Surveys,vol.49岁,不。2016年1月1日第3章介绍了工作发表在:P. Viotti,D.Dobre和M.Vukolić,ACM Transactions on Storage,vol.第13话第3话不2017年9月这反过来又修订和扩大了:D. 多布雷山口Viotti和M.Vukolić,ACM云计算研讨会,2014年。第4章修改和扩展:P. 维奥蒂角Meiklejohn和M.Vukolić,2016年ACM分布式数据一致性原则与实践研讨会在本论文的主要范围之外,在我的博士学位期间,我还致力于保证交叉容错的状态机复制协议的实现和测试,这导致了以下出版物:S. Liu,P.维奥蒂角卡钦河谷Quéma和M.Vukolić,“XFT:超越崩溃的实用容错”,2016年USENIX操作系统设计与实现研讨会第2非事务性分布式存储系统在本章中,我们开发了一个形式化的框架来表达非事务一致性语义。我们使用这个框架来定义在过去几十年的研究中描述的一致性语义这些新的,正式的定义,使结构化和全面的一致性频谱,我们说明了对比的2.1介绍面对固有的挑战,故障,通信冗余和并发访问共享资源,分布式系统的设计者不断寻求隐藏这些基本问题,从用户提供的抽象和语义模型的各种强度。分布式系统的最终目标看起来很简单,因为在理想情况下,它应该只是集中式系统的容错和更具可扩展性的版本理想的分布式系统应该利用分布和复制来通过屏蔽故障来提高可用性,提供可伸缩性和/或减少延迟,同时保持使用集中式系统的简单性-特别是其一致性-提供顺序访问的假象 这种强一致性标准可以在为现代存储系统铺平道路的早期工作中找到[163],以及随后在定义一般,实际正确性条件(如线性化)方面的进展[138]。不幸的是,高可用性和强一致性的目标负面的理论结果和下限,如FLP不可能性证明[111]和CAP定理[120],塑造了分布式系统的设计空间因此,分布式系统设计者要么放弃可伸缩性和可用性的理想化目标,要么放松一致性。7
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功