确保部分复制的数据存储Masoud Saeida Ardekani引用此版本：Masoud Saeida Ardekani确保部分复制的数据存储的一致性数据库[cs.DB]。皮埃尔和玛丽·居里大学-巴黎第六大学，2014年。英语NNT：2014PA066234。电话：01086358HAL Id：tel-01086358https://theses.hal.science/tel-010863582014年11月24日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire皮埃尔和玛丽·居里大学博士论文集斯佩恰利泰Informatique信息、电信和电子博士学校（巴黎）Présentée parMasoud SAEIDA ARDEKANI为了获得等级皮埃尔和玛丽·居里大学博士Sujet de la thèse：重复存储系统中一致性的维护2014年9月16日，陪审团组成如下：M. Marc SHAPIRODirecteur de thèseM. Pierre SUTRAEncadrant de thèseM. WillyZWAENEPOEL特别报告员M. Roberto BALDONI特别报告员M.道格拉斯湾审查员TerryMme.MariaPOTOP-BUTUCARU考官M. Nuno PREGUIXIA考官iiiABSTRACT基于云的应用程序（如社交网络或电子商务）需要跨多个站点复制数据，以提供响应能力、可用性和灾难容忍能力。确保具有缓慢且易于故障的WAN的大规模系统的一致性已变得至关重要。本文对这一问题进行了研究。在第一部分中，我们研究了事务系统中的一致性，并专注于协调可扩展性与强事务保证。我们确定了四个可伸缩性属性作为可伸缩性的关键：（i）只有由事务T更新的副本才能执行T;(ii)只读事务从不等待并发事务，并且总是提交;（iii）事务可以读取在其开始之后提交的版本;以及（iv）两个事务仅在它们的写入冲突时才彼此同步我们表明，没有一个强一致性标准确保所有四个。我们定义了一个新的可扩展的一致性标准称为非单调快照隔离（NMSI），而第一个是兼容所有四个属性。我们还提出了一个实际的实施NMSI，称为NMSI，我们比较实验对一些众所周知的标准。我们在第一部分中的最后一个贡献是一个框架，用于在不同的事务协议之间进行公平和苹果对苹果的比较我们的见解是，一个大家族的分布式事务协议有一个共同的结构，称为延迟更新复制（DUR）。DUR家族的协议仅在一些通用函数的行为上有所不同 我们提出了一个通用的DUR框架，称为G-DUR，以及所需行为的精细优化插件实现库。 我们的实证研究表明：（i）G-DUR允许开发人员在不到几百行的代码中实现各种事务协议;（ii）它提供了一个公平的，苹果对苹果的比较事务协议;（iii）通过替换插件，开发人员可以使用G-DUR来了解他们的协议中的瓶颈;（iv）这反过来又可以改进现有的协议;（v）给定一个协议，G-DUR允许评估确保不同程度的可靠性的成本。在本论文的第二部分，我们重点关注确保非事务数据存储的一致性我们介绍了Tuba，一个复制的键值存储，动态选择副本，以最大限度地提高实用程序提供给读操作根据所需的一致性定义的应用程序。此外，与当前系统不同的是，它会自动重新配置其副本集，同时遵守应用程序定义的约束，以便适应客户端位置或请求速率的变化我们在Windows Azure存储（WAS）上实现了Tuba在提供类似API的同时，Tuba还通过一组广泛的一致性选择、基于一致性的SLA和地理复制配置服务扩展了WAS与静态配置的系统相比，我们的评估表明，Tuba将返回强一致数据的读取增加了63%，并将平均效用提高了18%。v致我的爱妻尼卢法尔，感谢我善良鼓励我的父母，法特梅和赛义德，还有我的好兄弟姐妹，玛丽亚姆和穆罕默德vii一个小问题我衷心感谢我的顾问马克·夏皮罗给了我在他指导下工作的机会。这篇论文不会存在没有他的支持，耐心，和宝贵的指导，在过去的四年。我想向皮埃尔·苏特拉表达我最诚挚的谢意。他帮助我的每一位我的研究，并作出了重大贡献的许多算法和定理在第一部分的这篇论文。感谢皮埃尔的出色指导，支持和关怀。我非常感谢我的实习顾问道格我从他那里学到了分布式系统的许多实际感谢Doug对我的信任。2011年Nuno Preguiça访问我们的团队时，我有机会与他密切合作。我们与他的讨论导致了一些不可能的结果在这篇论文中提出谢谢Nuno我还要感谢我的所有论文评审团，特别是Willy Zwaenepoel和Roberto Baldoni，他们毫不犹豫地接受了我的评审团，以及他们宝贵的时间和对这项工作的评论。我还要感谢Regal团队中的所有研究生同学，特别是Marek Zawirski，Pierpaolo Mallilla，Corentin Mehat，Lisong Guo，Florian David，Maxime Lorrillere和Tyler Crain。感谢Marek在咖啡休息时间提供的所有有用和鼓舞人心的对话。感谢Pierpaolo，感谢你的友谊，以及你在开发早期版本的Pizza中的所有帮助，最重要的是，感谢你的所有翻译。我 非 常 感 谢 Marcos Aguilera 、 Mahesh Balakrishnan 、 Jiaqing Du 、 Sameh Elnikety 、Ramakrishna Kotla、Gilles Muller、Vivien Quéma和其他许多研究人员，他们花了一些时间来帮助我进行这项研究。我要感谢我的父母，我的姐姐和哥哥，这些年来一直鼓励我。最后，我非常感谢我的妻子Niloofar，感谢她的耐心和理解。ix没能 附件表15图表一览表1介绍11.1捐款11.1.1第一部分1.1.2第二部分1.2论文大纲4第一部分：确保事务数据存储52背景72.1模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .92.1.1对象事务. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .92.1.2历史。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .92.1.3分布式系统。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .102.1.3.1故障模型。. . . . . . . . . . . . . . . . . . . . . . . . . . . . .112.1.3.2同步假设。. . . . . . . . . . . . . . . . . . . . . . . .112.1.3.3故障检测器. . . . . . . . . . . . . . . . . . . . . . . . . . . .112.1.4复制的. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .112.1.5transmittance承诺。. . . . . . . . . . . . . . . . . . . . . . . . . . .122.1.5.1原子承诺方法。. . . . . . . . . . . . . . . . . . . .132.1.5.2总订购方法。. . . . . . . . . . . . . . . . . . . . . . .132.1.5.3部分订购方法。. . . . . . . . . . . . . . . . . . . . . . .142.2强一致性标准。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2.1严格可串行性（SSER）。. . . . . . . . . . . . . . . . . . . . . . . . . . .15162.2.2完全可串行性（SER）。. . . . . . . . . . . . . . . . . . . . . . . . . . . . .172.2.3更新可串行性（美国）。. . . . . . . . . . . . . . . . . . . . . . . . . . . .182.2.4快照隔离（SI）。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .182.2.4.1广义快照隔离（GSI）。. . . . . . . . . . . . . . . .20x目录2.2.5并行快照隔离（PSI）202.2.6因果可串行性（CSER）202.2.7软件事务存储器212.2.8异常比较212.3活力与进步213支持部分复制253.1可扩展性属性263.1.1免费等待服务（WFQ）263.1.2真正的部分复制（GPR）263.1.3最小提交同步273.1.4新鲜感283.2支持部分复制283.2.1SSER313.2.2SER313.2.3美国333.2.4 SI333.2.5 PSI344强一致性标准354.1分解SI364.1.1不存在级联流产（ACA）374.1.2一致和严格一致快照（SCONS）374.1.3快照单调性（MON）384.1.4写冲突自由394.1.5分解394.2用GPR40实现SI的不可能性4.3讨论444.3.1SSER和不透明度444.3.2SER444.3.3PSI444.3.4第45章不可能的结果4.4结论455非单调快照隔离475.1NMSI的定义485.2NMSI49的一个协议5.2.1拍摄一致的快照50xi目录5.2.2交易生命周期（单位：USD）53目录xi5.2.3执行协议。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .545.2.4终止协议。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .555.2.5证明。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .565.2.5.1安全属性。. . . . . . . . . . . . . . . . . . . . . . . . . . . .565.2.5.2 ScalabilityProperties.. . . . . . . . . . . . . . . . . . . . . . . . .575.3确保无障碍。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .575.4实证研究。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .585.4.1实施。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .585.4.2设置和基准。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .585.4.3实验结果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .605.5结论. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .626G-DUR：通用延迟更新复制656.1概览686.2处决706.2.1版本跟踪716.2.2选择版本726.3终止726.3.1小组沟通736.3.2两阶段提交756.3.3容错766.4实现协议776.4.1P-Store776.4.2S-DUR776.4.3GMU786.4.4塞拉诺07786.4.5Walter沃尔特796.4.679号机2台6.5实现方式806.6案例研究806.6.1设置和基准816.6.2比较Transmission协议826.6.3理解瓶颈846.6.4可插拔能力846.6.5可靠性856.6.5.1灾难倾向856.6.5.2灾难容忍866.7相关工作87目录xii6.8结论89目录xiii第二部分：确保非事务性数据存储917Tuba：一个可自配置的云存储系统937.1导言。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .957.2系统概述。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .967.2.1来自Pileus。. . . . . . . . . . . . . . . . . . . . . . . . . . . .967.2.2 Tuba. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .977.3配置服务（CS）。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .987.3.1限制。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .997.3.2成本模型。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .997.3.3选择。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1007.3.4操作。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1017.3.4.1调整同步周期。. . . . . . . . . . . . . . . . .1017.3.4.2添加/删除辅助服务器。. . . . . . . . . . . . . . . . . . .1027.3.4.3 ChangePrimary. . . . . . . . . . . . . . . . . . . . . . .1027.3.4.4添加主目录。. . . . . . . . . . . . . . . . . . . . . . . . . .1037.3.4.5摘要。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1047.4客户端执行模式。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1047.5执行。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1067.5.1沟通。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1067.5.2客户端操作。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1077.5.2.1读取操作。. . . . . . . . . . . . . . . . . . . . . . . . . . . . .1077.5.2.2单主写操作。. . . . . . . . . . . . . . . . . . .1077.5.2.3多主写操作。. . . . . . . . . . . . . . . . . . .1087.5.3 CS重新配置操作。. . . . . . . . . . . . . . . . . . . . . . . . .1097.5.4容错。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1107.6评价。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1127.6.1设置和基准。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1127.6.2宏观视图。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1137.6.3显微镜观察。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1157.6.4快速模式与慢速模式。. . . . . . . . . . . . . . . . . . . . . . . . . . . . .1167.6.5 CS的可扩展性. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1177.7相关工作. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1187.8结论。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1198结论1218.1今后的工作. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .123第三部分：附录125目录xivASI分解的证明127B133.第133章正确B.1安全133B.2生活与进步134CRésumé dela thèse137C.1简历139C.2导言. 140C.2.1捐款141C.2.1.1第一党141C.2.1.2第二部分144C.3Passage àC.3.1Décomposition SI145C.3.1.1级联环化（无级联流产）145C.3.1.2Instantanés cohérents etstrictement cohérents146C.3.1.3Instantané monotone单调147C.3.2写冲突自由147C.3.3La décomposition147C.3.4L’impossibilité de SI avec GPRC.4非单调快照隔离149C.5通用延迟更新复制152C.6Un Système de StockageCloud Auto-Configurable155参考书目157目录xvxvLIST关于TABLES2.1有用的符号。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .102.2强相合性准则的异常比较。. . . . . . . . . . . . . . . . . . .222.3一致性标准冲突表。. . . . . . . . . . . . . . . . . . . . . . . . . . . .222.4进度属性。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .243.1部分复制协议的假设比较。. . . . . . . . . . . . . .293.2部分复制协议的特性比较。. . . . . . . . . . . . . . . .305.1比较一致性标准。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .496.1符号。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .686.2源代码。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .816.3实验设置。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81C.1Comparaisondes critères de consistance.. . . . . . . . . . . . . . . . . . . . . . . . . .150
我的内容管理
收起
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助 
