用于现代高弹性存储系统中复制数据的自适应一致性协议萨提亚·帕布·库马尔引用此版本：萨提亚·帕布·库马尔。现代高弹性存储系统中复制数据的自适应一致性协议文档和文本处理。国家艺术与工艺学院英语。NNT：2016CNAM1035。电话：01359621HAL ID：电话：01359621https://theses.hal.science/tel-01359621提交日期：2016年HAL是一个多学科的开放存取档案馆，用于存放和传播科学研究论文，无论它们是否被公开。论文可以来自法国或国外的教学和研究机构，也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire现代高弹性存储系统中复制数据的自适应一致性国家保护区艺术与职业国立艺术与手工艺学院博士学院Cedric实验室- CNAM实验室列表-ISEP博士论文提交人：Sathiya Prabhu Kumar支持： 2016年3月15日获得以下学位：国家艺术与工业学院博士专业：计算机科学论文指导人M. GRESSIER-SOUDAN Eric教授，CEDRIC-CNAM框架由夫人。CHIKY Raja教授-研究员，LISITE-ISEPM. LEFEBVRE SylvainLISITE-ISEP讲师兼研究员报告员M. DEFUDE Bruno教授，巴黎电信公司M. Hagimont Daniel教授，IRIT/ENSEEIHT考试员夫人。CHABRIDON SophieSUDPARIS电信助理教授夫人。RONCANCIO Claudia教授，GRENOBLE INP感谢我的导师Raja Chiky博士，他给了我这个机会。3确认文件我非常感谢我的导师拉贾·奇基教授，他给了我这个机会，相信我，并付出了如此多的努力来获得论文的资金。我很幸运有老师。Eric Gressier Sudan是我的论文主任。他很善良，很有爱心。他总是设法找到一些时间，使他可以回答任何问题或讨论有关的论文。在每一次会议上，他都像知识雨一样，提供了大量有用的参考资料和有价值的想法来推动前进。言语不足以感谢Sylvain Lefebvre教授，他给了我大量的技术支持，并不断推动我前进，因为我看到了工作的质量他是非常有活力的，并给他的全部奉献精神的好论文工作。没有他的支持和评论，这篇论文就不会很好地完成。我非常感谢Olivier Hermant花时间和精力帮助我完成第三章的形式主义部分我还要衷心感谢RDI-LISITE团队的所有成员：Yousara Chabchoub、Zakia Kazi-Aoul、Matthieu Manceny、Mohamed Sellami，感谢他们对我非常好，并帮助我提出了关于论文的任何问题或建议。我非常感谢Gilles Carpentier照顾我在这三年中参与的所有教学活动，并确保我的教学活动的时间和时间表不影响论文工作。我还要感谢我所有的ISEP同事，特别是Ahmad、Manuel、Chen、Navneet、Nuraishah、Amadou和Rayane，他们在我的博士之旅中经历了所有的起伏。我非常感谢Minyoung Kim和Mark Oliver Stehr给我机会，让我作为加州斯坦福研究所的国际研究员奖学金是非常富有成效的，充满了大量的学习和经验。Minyoung和Mark非常善良，激励人心，并对论文的第7章负责我衷心感谢所有中期和辩护陪审团成员。Philippe Rigaux、Bruno Defude教授、Daniel Hagimont教授、Claudia Roncancio教授和Ass Sophie Chabridon教授同意成为陪审团成员，并在及时进行辩护方面提供了宝贵的时间和合作我感谢Datastax的Duyhai Doan对论文第7章的我也感谢Datastax和其他公司、社区、协会和个人通过各种网站、博客文章、教程、聚会、研讨会和会议，用大量的知识和信息照亮世界最后但并非最不重要的是，我要感谢我的父亲给了我很多力量，教训和祝福，让我面对生活中所有的好的和坏的，让我成为我自己。我妈妈和姐姐的爱和感情也很棒。特别感谢我所有的朋友，祝福者和全能的人和我在一起，继续希望我最好的。我还获得了亚马逊AWS研究基金来支持我的实验，以及NSF基金0932397的部分支持来支持我的国际奖学金。本材料中表达的任何意见、发现、结论或建议均为作者的意见、发现、结论或建议，并不反映NSF的观点5摘要现代数据库系统将对象存储为键和值对，其中每个值由唯一的键标识这种方法促进了数据在网络上的分布（由于分布式哈希表），并允许快速、简单地访问每个对象。这些系统中的大多数选择更好的可用性级别和响应时间，而不是数据一致性管理。由于这些系统是对等系统，因此每个节点都使用乐观复制策略来处理写或读请求。因此，可能的复制品之间可能存在暂时的不一致。这些不一致可能表现为过时的读数或相互冲突的更新在这些系统中实现的一致性级别取决于在每个请求中联系的节点的数量某些系统允许选择高级别的一致性会增加消息交换的额外成本，从而增加延迟，并且如果无法联系到足够数量的副本，则可能本文的主要贡献有三个。本文的第一部分涉及一个名为LibRe的新复制协议的开发LibRe是"用于复制的库"的首字母缩写LibRe的主要目标是在该协议中，在写入操作期间6以及在读取操作期间，根据寄存器中的信息将请求转发到最合适的副本此机制有助于限制过时读数的数量无论是通过模拟还是通过实际条件下的评估，系统一致性的评估仍然是一个难以解决的问题。 因此，我们开发了一个名为Simizer的模拟器，它允许评估和比较不同一致性协议的性能。YCSB数据库评估系统也得到了扩展，以评估现代存储系统中一致性模拟器代码和对YCSB工具的更改虽然现代数据库系统根据用户的需求调整一致性保证，但对于应用程序开发人员来说，预测每个操作所需的一致性级别仍然是一个挑战本文的第二个贡献试图通过允许数据库用从外部信息定义的其他规则替换默认定义的一致性级别来解决这个问题此信息可以由管理员或外部服务提供在本文中，我们使用Cassandra分布式数据库系统中的一个实现来验证这个模型本论文的第三个贡献是解决更新冲突。解决这种类型的冲突需要保留对象的所有可能值，这意味着在吞吐量和延迟方面的额外成本在本文中，我们讨论了一种新型分布式对象的需求和设计，即优先级注册表，它使用特定于域的冲突检测和解决策略，以及服务器端实现。我们的方法使用特定替换顺序的概念。我们证明了由这种顺序参数化的数据类型可以为需要特定冲突解决方案的应用程序提供有效的解决方案。 我们还描述了Cassandra中概念验证的实现。关键词：Nosql，CAP定理，可能的一致性，法定人数系统。9摘要在现代分布式数据库系统中，数据对象被存储为键值对，其中每个数据对象由唯一的键标识。使用单个密钥存储数据使得在存储网络上分发数据变得容易（例如，使用散列技术），并通过传递密钥来访问数据对象这些数据存储中的大多数选择通过允许任何副本节点处理程序遵循优化复制策略来交换一致性，以有利于请求延迟和可用性。这些系统允许副本为相同的密钥保留不同的值，接受副本之间的暂时不一致不一致问题的两个主要变体是静态读取和更新冲突。确保这些系统的强一致性取决于在读取和写入请求期间联系的副本节点的系统允许用户根据所需的一致性级别选择要联系的副本节点的数量，并根据每个查询或每个表调整系统的一致性级别。除了在联系足够数量的副本节点时在请求延迟上花费的额外成本之外，如果无法联系足够数量的节点，则系统将使请求失败，从而影响系统的可用性。本文的主要贡献是三折。本文的第一个贡献是在一个名为LibRe的新一致性协议的帮助下，研究了一种在现代数据库系统中控制静态读取的有效LibRe是用于复制的库的首字母缩写。LibRe协议的主要目标是在信息库的帮助下，通过在读取和写入操作期间联系最少数量的副本节点来确保数据一致性。根据协议，在写入操作期间，每个副本节点与更新数据的最新版本标识符异步更新注册表（库）将读取请求转发到引用的右副本节点10注册表信息有助于在读取操作期间控制静态读取通过模拟以及在真实世界设置中评估数据一致性仍然具有挑战性。Hence实现了一个名为Simizer的新模拟工具包，它有助于以快速有效的方式评估不同一致性策略的性能。我们还扩展了现有的YCSB基准工具，以帮助评估现代数据库系统提供的一致性-延迟权衡。模拟器的代码库和扩展的YCSB是开源的，可供公众访问。在扩展YCSB的帮助下，通过模拟验证了LibRe协议的性能，就像在真实环境中一样。尽管现代数据库系统在每次查询的基础上调整系统的一致性保证，但在应用程序开发时间之前预测应用程序查询的一致性级别对应用程序开发人员来说仍然是一个挑战。为了克服这一限制，本文的第二篇论文侧重于在外部输入的帮助下，使数据库系统能够在运行时间内覆盖应用程序定义的一致性选项。外部输入可以由数据管理员或外部服务提供。本文通过在Cassandra分布式存储系统中实现原型来验证模型论文的第三个贡献集中在解决最新的冲突。解决经常涉及的冲突，保持所有可能的值，并通过客户端的域特定知识执行解决。这在网络带宽和延迟以及相当大的复杂性方面带来了额外的成本。在本文中，我们讨论了一种称为优先级寄存器的新型数据类型的动机和设计，该数据类型直接在数据库端实现了特定于域的冲突检测和解决方案，同时在应用层保留了额外协调的选项。我们的方法使用了应用程序定义的替换排序的概念，并且我们表明，由这样的排序参数化的数据类型可以为需要域特定冲突解决的应用程序提供有效的解决方案。我们还描述了Cassandra内部优先级寄存器的概念验证实现关键词：Nosql系统、CAP定理、偶然一致性、法定系统。11内容表1导言451.1捐款471.1.1基于quorus的复制系统的一致性-延迟权衡更好.........................................1.1.2通过模拟评估方案的一致性1.1.3使用YCSB 49评估飞行数据一致性1.1.4在查询期间覆盖应用程序定义的一致性选项运行时501.1.5临时数据重新核对的应用程序定义的替换订单...........................................511.2手稿52的组织1.3出版物531.3.1国际出版物531.3.2国家出版物542最新技术水平2.1事件排序562.2分布式系统中的时间2.2.1物理钟572.2.2逻辑时钟582.2.3拉波特时钟58122.2.4矢量时钟592.2.5矢量版本2.2.6更新-冲突602.2.7数据核对612.3一致性模型612.3.1严格一致性612.3.2顺序一致性或序列化性622.3.3快照隔离632.3.4因果一致性652.3.5最终一致性662.3.6一致性模型的比较2.4现代数据库系统的演变672.4.1CAP影响682.4.2基本范式702.5现代数据库系统的权衡712.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.6纪元协议：... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...782.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：一个系统现代分布式数据库953.1自由. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ... ... ... ... ... ... ... ... ...963.1.1Libre注册表。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ...96内容表143.1.2算法描述。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...973.2LibRe对现代分布式数据库系统3.2.1目标系统993.2.2Libre注册表1003.2.3自由消息1013.2.4LibRe写入操作1023.2.5Libre Read操作1033.2.6Libre可靠性104内容表153.2.7自由成本。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 1043.3自由形式化。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 1053.3.1符号。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 1053.2系统状态。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ....... 1083.3.3稳定状态属性。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 1113.3不稳定状态属性。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 1143.4相关作品。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 116.3.5摘要。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ... ... ... ... .... 1184通过模拟评估协议的一致性1214.1 Simizer描述和体系结构。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 1234.1.1实体。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .... 1234.1.2处理器模拟。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 1254.1.3请求执行。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 1264.2模拟器使用。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 1264.2.1工作负载描述文件。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 1274.2.2请求描述文. 128内容表16件。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...4.2.3服务器描述文件。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 128使用Simizer模拟一致性选项。... ... ... ... ... ... ... ... ... ... ... ... ... .... 1294.4使用Simizer进行一致性评估。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 1334.5结论。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 1355LibRe与Cassandra的原生一致性选项的性能5.1LibRe在Cassandra 138中5.1.1Cassandra数据模型1385.1.2Cassandra 141中的LibRe实现5.2YCSB用于评估数据一致性142内容表175.2.1YCSB 1435.2.2扩展至YCSB 1445.3使用YCSB 146进行CaLibRe性能评估5.3.1测试设置1465.3.2测试评估1465.4结论1486在运行时期间覆盖应用程序定义的一致性选项1516.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内容表187.3优先级寄存器1757.3.1与CRDT的比较7.3.2示例使用案例1787.4在Cassandra 179中实施优先级登记册7.4.1Cassandra读写模式1807.4.2优先级注册表实施1807.4.3原型示例会话1837.5结论1888结论和未来的工作191参考书目196词汇表21717表列表2.1PACELCModel 70中的分布式存储系统2.2Dynamo：现代数据库系统的示例4.1Simizer 127中提供的分销法律
我的内容管理
展开
