高弹性存储系统的副本数据自适应一致性协议

高弹性存储系统中副本数据的自适应一致性协议Sathiya Prabhu Kumar引用此版本：Sathiya Prabhu Kumar.高弹性存储系统中复制数据的自适应一致性协议。文档和文本处理。国立艺术与工艺学院英语NNT：2016CNAM1035。电话：01359621HAL Id：tel-01359621https://theses.hal.science/tel-013596212016年9月2日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire高弹性存储系统自然保护区艺术与技术国立工艺学院博士学校CEDRIC - CNAM LABORATOIRELISITE -ISEP博士论文集提交人：Sathiya Prabhu KUMARsoutenue le： 2016年3月15日获得国家艺术和技术学院博士学位专业：信息Thisse dirigée parM. GRESSIER-SOUDAN Eric教授，CEDRIC-CNAMEncadrée par夫人CHIKY RajaEnseignant-Chercheur，ISITE-ISEPM. LEFEBVRE SylvainEnseignant-Chercheur，LISITE-ISEP报告员M. DEFUDE Bruno教授，巴黎电信M. 丹尼尔教授，IRIT/ENSEEIHT艺术家夫人CHABRIDON Sophie助理教授，巴黎电信夫人RONCANCIO Claudia教授，GRENOBLE INP感谢我的导师Raja Chiky博士，是他给了我这个机会。3致谢我欠欠我的导师屁股教授拉贾Chiky感激，谁给了我这个机会，相信我，并把这么多的努力，在寻找论文的资金我很幸运，有教授。Eric Gressier Soudan作为我的论文指导。他很善良，很有爱心。他总是设法找到一些时间，让他有空的任何问题或讨论有关的论文。在每一次会议上，他就像知识之雨，给了吨和吨有用的参考和宝贵的想法，以推进。言语不足以感谢Sylvain Lefebvre教授，他给了我大量的技术支持，并不断推动我在工作质量方面取得进步他精力充沛，为论文的顺利完成付出了全部的心血。如果没有他的支持和评论，这篇论文就不可能完成得很好。我非常感谢奥利维耶·赫尔墨斯，他花了时间和精力帮助我完成了第3章的形式主义部分我还要衷心感谢RDI-LISITE的所有团队成员：Yousara Chabchoub，Zakia Kazi-Aoul，Matthieu Manceny，Mohamed Sellami，他们对我非常友好，并帮助我解决有关论文的任何问题或建议。我非常感谢Gilles Carpentier在这三年中对我参与的所有教学活动的照顾，并确保我的教学活动的时间和日程不影响论文工作。我还要感谢我所有的ISEP同事，特别是Ahmad，Manuel，Chen，Navneet，Nuraishah，Amadou和Rayane，他们参与了我博士旅程的所有起伏我非常感谢金敏英和马克·奥利弗·施特尔给我机会，让我作为加州斯坦福研究院的国际研究员与他们一起工作这次团契非常有成效，充满了学习和经验。Minyoung和Mark非常善良，激励，并负责论文的第七章我真诚地感谢所有的中期和辩护陪审团成员：教授。Philippe Rigaux、BrunoDefude教授、Daniel Hagimont教授、Claudia Roncancio教授和Ass Prof. SophieChabridon教授接受成为陪审团的一员，并为及时实现辩护提供了宝贵的时间和合作我感谢Datastax的Duyhai Doan对论文第7章的支持和有益的我也感谢Datastax和其他企业、社区、协会和个人通过大量的网站、博客、教程、聚会、研讨会和会议用大量的知识和信息来启发世界最后，我想感谢我的父亲，他给了我很多力量，教训和祝福，让我在一生中面对所有的好与坏，让我成为现在的我。我妈妈和我姐姐的爱和感情也是无价的。特别感谢我所有的朋友、祝福者和站在我面前的全能者。继续希望我能做到最好我还感谢Amazon AWS Research资助我的实验，以及NSF资助0932397的部分支持，以支持我的国际奖学金。本材料中表达的任何意见、发现、结论或建议均为作者的观点，并不反映NSF的观点5简历现代化的基础系统包括成对的clé和valeur（s）的对象，其中valeur（价值）被识别为唯一的clé。Cette approche facilite la distribution des données sur le réseau（grâceaux tables de hachage distribuées）et permet un accès rapide et simple à chaque objet.这些制度的主要选择是提供最佳的可支配性和最佳的反应时间，以应对对捐助者一致性的管理。由于这些系统是一对一对的系统，因此我们可以通过写作或演讲来帮助我们制定优化的策略。这是可能的，因为存在着一些暂时性的不协调。这种不协调的现象在过时的演讲形式或冲突中表现出来。在这些系统中获得一致性的可能性取决于所需的联系人名称。Certains systèmes autorisentChoisir un haut niveau de cohérence ajoute uncocoon t supplémentaire en terme这三个项目的主要贡献是三个名字。这方面的第一部分涉及一项名为LibRe的新的复制协议的执行情况，该协议将限制在一个库存分配系统中废弃的讲座名称LibRe是一个有意义的首字母缩写词“Library for Replication”。LibRe的主要目标是确保在讲座和写作过程中与最低限度的读者保持在该议定书中，在一项写作工作中，登记册（“图书馆”）上有一个登记册6具有修改后的版本的标识符Lors des opérations de lecture，la requête est establérée auréplica le plus approprié en fonesty de这一机制允许限制过时的讲座名称。L'évaluationdela cohérence d'un système reste un problem difficile à résoudre，que ce soit par simulation or parévaluation en conditions réelles. 因此，我们可以使用一个叫做Simizer的模拟器，它可以评估和比较不同一致性协议的性能。Le systèmeLe code du simulateur et les modificationsapportées à虽然现代化的教育基础体系能够适应使用者的需求，但预期难以实现应用程序所需的一致性要求这一问题的第二个贡献是通过外部信息部分的其他规则来解决这些信息可以提供给行政部门或外部服务部门在这一点上，我们验证了Cassandra分发数据库系统的模式这三个方面的贡献涉及解决过去几天的冲突。La résolution de ce type de conflitsnéciliitederetenirtouteslesvaleurspossiblesCeciimpliquedescoffeetssupplémentaires en termes de débit et de latence.在这方面，我们讨论了一种新的对象分配类型的基础和概念，即优先登记，它利用一种战略来检测和解决领域内的特殊冲突，并提供服务。我们要利用特别安置令的概念。Nous montrons qu'un type de donnéeparamètrée par un tel ordre peut fournir une solution efficace pour les applications demandant dessolutionsspécifiquesà larésolutiondesconflits. 我们也要在卡桑德拉身上植入一个概念。Mots clés：NoSql、Théorème CAP、Cohérence éventuelle、Systèmes de Quorums。9摘要在现代分布式数据库系统中，数据对象被存储为键值对，其中每个数据对象由唯一的键标识。用唯一密钥存储数据使得容易在存储网络上分发数据（例如，使用散列技术），并简单地通过传递密钥来访问数据对象这些数据存储中的大多数选择通过让任何副本节点按照乐观的复制策略处理读写请求这些系统允许副本为相同的键保存不同的值，接受副本之间的临时不一致问题的两个主要变体是陈旧读取和更新冲突。在这些系统中确保强一致性取决于在读和写请求期间接触的副本节点系统允许用户根据所需的一致性级别选择要联系的副本节点的数量，并在每个查询或每个表的基础上适应系统的一致性级别除了在联系足够数量的副本节点时在请求延迟上花费的额外成本之外，如果不能联系足够数量的节点，则系统使请求失败，从而影响系统的可用性。本文的主要贡献有三个方面。论文的第一个贡献集中在一个有效的方法来控制陈旧的读取在现代数据库系统的帮助下，一个新的一致性协议称为LibRe。LibRe是Library forReplication的缩写。LibRe协议的主要目标是通过在库信息的帮助根据该协议，在写操作期间，每个副本节点用更新数据的最近版本标识符异步地更新注册表（库）将读请求转发到引用10注册表信息有助于在读取操作期间控制陈旧读取数据一致性的评估仍然具有挑战性，无论是通过模拟，以及在现实世界的设置。因此，我们实现了一个新的模拟工具包，称为Simizer，有助于以快速有效的方式评估不同一致性策略的性能我们还扩展了一个现有的基准测试工具YCSB，它有助于评估现代数据库系统提供的一致性-延迟权衡。模拟器的代码库和扩展的YCSB是开源的，供公众访问。LibRe协议的性能通过仿真以及在实际设置的帮助下，扩展的YCSB进行了验证。尽管现代数据库系统在每个查询的基础上适应系统的一致性保证，但是在应用开发时提前预测应用查询的一致性水平对于应用开发者来说仍然是具有挑战性为了克服这一限制，论文的第二个贡献的重点是使数据库系统在运行时覆盖应用程序定义的一致性选项与外部输入的帮助。外部输入可以由数据管理员或外部服务给出。本文通过Cassandra分布式存储系统的一个原型实现验证了所提出的模型本文的第三个贡献是解决更新冲突。解决更新冲突通常涉及维护所有可能的值，并在客户端通过特定于域的知识执行这涉及网络带宽和延迟方面的额外成本以及相当大的复杂性。在这篇论文中，我们讨论了一种新的数据类型优先级寄存器的动机和设计，它直接在数据库端实现了一个特定于域的冲突检测和解决方案，同时在应用程序级保留了额外的协调选项。我们的方法使用的概念，应用程序定义的替换排序，我们表明，这样的顺序参数化的数据类型可以提供一个有效的解决方案，为应用程序的需求特定于域的冲突解决方案。我们还描述了Cassandra内部优先级寄存器的概念实现证明保留字：NoSql系统，CAP定理，最终一致性，Quorum系统。11目录1导言. 451.1捐款471.1.1基于法定人数的复制系统的更好的一致性-延迟权衡................................. 471.1.2通过模拟评估一致性协议1.1.3使用YCSB 49动态评估数据一致性1.1.4期间覆盖查询的应用程序定义的一致性选项运行时间501.1.5为特别数据重新调解而作出的应用程序界定的替换命令...........................511.2Mandarinpt组织1.3出版物531.3.1国际出版物1.3.2国家出版物2艺术552.1事件排序562.2分布式系统中的时间2.2.1物理时钟572.2.2逻辑时钟582.2.3Lamport时钟58122.2.4矢量时钟592.2.5版本矢量592.2.6更新-冲突602.2.7数据核对612.3一致性模型2.3.1严格的一致性612.3.2顺序一致性或可串行性622.3.3快照隔离632.3.4因果一致性652.3.5最终一致性662.3.6一致性模型的比较2.4现代数据库系统2.4.1CAP影响力682.4.2BASEParadigm 702.5现代数据库系统2.5.1一致性-延迟权衡712.5.2耐久性-延迟权衡732.6控制协议732.6.1主拷贝算法742.6.2基于投票的副本控制协议742.7基于法定人数的表决系统2.7.1法定人数：76人2.7.2投票数：762.7.3西非办事处：77个目录132.7.4 ROWA-A：. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .772.7.5丢失写入协议：. . . . . . . . . . . . . . . . . . . . . . . .782.7.6Epoch协议：. . . . . . . . . . . . . . . . . . . . . . . . . . . .782.7.7可能的法定人数。. . . . . . . . . . . . . . . . . . . . . . . . .792.7.8部分法定人数：. . . . . . . . . . . . . . . . . . . . . . . . . . . .792.8客户端与服务器端保证。. . . . . . . . . . . . . . . . . . .822.8.1服务器端保证：. . . . . . . . . . . . . . . . . . . . . . . . .822.8.2客户端保证。. . . . . . . . . . . . . . . . . . . . . . . . .832.9自适应一致性。. . . . . . . . . . . . . . . . . . . . . . . . . . . . .852.9.1一致性模型的类别。. . . . . . . . . . . . . . . . . . .852.9.2适应性一致性的类别。. . . . . . . . . . . . . . . . . .872.10 现代数据库系统-示例。. . . . . . . . . . . . . . . . . . . . .902.11 讨论. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .913 LibRe：ASystems一种新的分布式数据库953.1 LibRe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .963.1.1LibRe Registry.. . . . . . . . . . . . . . . . . . . . . . . . . . . . .963.1.2算法描述。. . . . . . . . . . . . . . . . . . . . . . . . .973.2LibRe在现代分布式数据库系统中3.2.1目标系统993.2.2LibReRegistry 1003.2.3LibRe消息1013.2.4LibRe写操作1023.2.5LibRe读取操作1033.2.6LibRe可靠性104目录143.2.7 LibRe成本。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 1043.3LibRe正式化。. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 1053.3.1符号。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 1053.3.2系统状态。. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 1083.3.3稳定状态属性。. . . . . . . . . . . . . . . . . . . . . . .. 1113.3.4不稳定状态属性。. . . . . . . . . . . . . . . . . . . . .. 1143.4相关作品。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 1163.5摘要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 1184一致性协议的仿真评估1214.1 Simizer描述和架构。. . . . . . . . . . . . . . . . . . . .. 1234.1.1实体。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 1234.1.2处理器仿真。. . . . . . . . . . . . . . . . . . . . . . . . .. 1254.1.3请求执行。. . . . . . . . . . . . . . . . . . . . . . . . . .. 1264.2模拟器的使用。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 1264.2.1安装说明文件。. . . . . . . . . . . . . . . . . . . . . .. 1274.2.2请求描述文件。. . . . . . . . . . . . . . . . . . . . . . .. 1284.2.3服务器描述文件。. . . . . . . . . . . . . . . . . . . . . . . .. 1284.3使用Simizer模拟一致性选项。. . . . . . . . . . . . . .. 1294.4使用Simizer进行一致性评价。. . . . . . . . . . . . . . . . . . .. 1334.5结论。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 1355LibRe对Cassandra的原生一致性选项的性能5.1在Cassandra 138中实现LibRe5.1.1Cassandra数据模型1385.1.2Cassandra 141中的LibRe实现5.2YCSB用于评估数据一致性142目录155.2.1YCSB 1435.2.2延伸至YCSB 1445.3使用YCSB 146的CaLibRe性能评估5.3.1测试设置1465.3.2测试评估1465.4结论1486在运行时覆盖应用程序定义的一致性选项6.1示例用例1526.1.1库存控制系统1536.1.2拍卖系统1536.1.3自行车共享系统1546.1.4紧急情况1546.2学习一致性需求1556.3型号1566.4自行车共享系统的自适应一致性1596.5实验评价1606.5.1原型实现1606.5.2测试设置1616.5.3测试评估1626.6结论1647应用程序定义的临时对账替换订单1677.1语法和语义的协调1687.1.1语法和解1687.1.2语义和解1707.2动机173目录167.3优先级寄存器1757.3.1与CRDT的比较7.3.2示例用例1787.4在Cassandra 179中实现优先级寄存器7.4.1Cassandra读写模式1807.4.2优先级寄存器实现1807.4.3原型示例会话1837.5结论1888结论和未来工作191Bibliographie书目196Glossaire 21717表的列表2.1PACELC模型中的分布式存储系统2.2Dynamo：现代数据库系统的例子4.1Simizer中的分布定律19图目录2.1具有严格一致性的合规和不合规订单622.2符合和不符合顺序一致性的订单632.3符合和不符合快照隔离642.4符合和不符合因果一致性的订单652.5一致性模型比较672.6CAP定理693.1LibRe总体架构图983.2LibRe通用序列图983.3基于DHT的LibRe 100架构图3.4基于DHT的LibRe 101序列图4.1Architecture deSimizer 1234.2建筑模拟课程1254.3服务器描述文件示例1294.4实验结果1355.1列-族数据存储1395.2YCSB1455.3部分更新传播下的CaLibRe性能评估147