分布式存储系统的可扩展性和灵活性

提高分布式存储系统纪尧姆·鲁蒂引用此版本：纪尧姆·鲁蒂为分布式存储系统提供更高的可扩展性和灵活性。分布式、并行和集群计算.巴黎-萨克雷大学，2019年。英语NNT：2019SACLT006。电话：02117812HAL Id：tel-02117812https://pastel.archives-ouvertes.fr/tel-021178122019年5月2日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire实现更高的可扩展性和灵活性，分布式存储系统大学里的医生们都去了萨pre'pare'ea`Te'le'comParisTechEcole doctoralen 580 Ecole Doctorale Sciences et Technologies dea通信（ED STIC）Spe'cialite'dedoctorat：Inforrmatique2019年6月15日，第15届亚太经合组织（亚太经合组织）部长级会议通过了《2019年亚太经合组织（亚太经合组织）部长级会议议程》，GUILLAUME RUTY评审团组成：Andre'-LucBeylotEnseur，ENSEEIHT（IRIT）特别报告员斯特凡诺·塞奇CNAM主席特别报告员拉乌夫·布塔巴滑铁卢大学讲师Nadia Boukhatem专业人士，TelecomParisTech（LTCI）Pre'sidentDamien SaucezCharge'deRecherche，INRIAExaminateur让-路易·鲁吉耶Professeur，TelecomParisTech（LTCI）Directeurdethe`seAndre`Surcouf杰出工程师，思科系统公司（PIRL）共同负责人MarkTownsley好吧，思科系统（PIRL）在生命中NNT：TELECOMP ARIS T ECHD八月T HESIS提高分布式存储系统的可扩展性和灵活性著者：纪尧姆·鲁蒂主管：Jean-Louis Rougier为满足哲学在思科系统巴黎创新与研究实验室（PIRL）培训与信息交流实验室2019年5月1日i作者声明我，Guillaume Ruty，声明这篇题为“分布式存储系统的可扩展性和灵活性”的论文以及其中的工作是我自己的。本人确认：这项工作全部或主要是在申请这所大学的研究学位时完成的。如果本论文的任何部分之前已提交学位或任何其他资格在这所大学或任何其他instructions，这已经清楚地说明。在我查阅他人已发表的著作时，这一点总是明确的。在我引用别人的作品时，总是给出出处。除了这些引文外，这篇论文完全是我自己的作品。• 我已经确认了所有主要的帮助来源。如果论文是基于我与他人共同完成的工作，我已经明确了别人做了什么，我有什么贡献自己。签署人：日期：年月日01/05/2019·····ii“人的成熟是在孩子出生时对孩子进行的一种教育。”Alain Damasio，La Horde du Contreventiii巴黎电信摘要信息培训与交流学院提高分布式存储系统的可扩展性和灵活性饰Guillaume Rutyiv对存储的指数增长的需求给传统的分布式存储系统带来了巨大的压力。虽然存储设备的性能随着时间的推移不断提高，但当前的分布式存储系统很难跟上数据增长的速度，特别是随着云和大数据应用的兴起。此外，存储、网络和计算设备之间的性能平衡已经发生了变化，作为大多数分布式存储系统基础的假设不再成立。本文解释了如何在几个方面的存储系统可以修改和重新思考，使其更有效地利用资源的处置。提出了一种新颖的存储体系结构6R100，它使用元数据的分布式层来提供灵活的、可扩展的对象级存储，并提出了一种改进通用存储系统处理并发请求的调度算法。最后，它描述了如何改进基于擦除代码的分布式存储系统的遗留文件系统级缓存，然后在简短的研究项目的背景下提出了一些其他的贡献。在指数增长的情况下，库存量的需求很难满足传统的库存分配系统。即使磁盘的性能持续改善，库存分配系统实际上也能满足库存所需数量的增长，尤其是大数据应用的此外，由于实际库存分配系统的存在，使得库存、库存网络和流程的性能发生了变化，对库存分配的假设也发生了变化Cette dissertation explique de quelle manière certains aspects de telssystems- tèmes de stockages peuvent être modifiés et repensés pour faireune utilisa- tion plus efficace des resources qui les composent.介绍了6年来，一种新的仓储结构，它以一个卧铺为基础，在车厢内分布着一种灵活的、可移动的物品仓储。她详细介绍了一个算法Enfin，elle décrit commentaméliqule cache générique du système de fictionary dans le contexte desystèmes de stockage distribué basés sur des codes correctly avant deprésenter des contributions effectuées dans le crawl de courts projets derecherche.v确认如果没有许多人的帮助和支持，这里介绍的工作是不可能完成的。我首先要感谢我的顾问Jean-Louis Rougier和André Surcouf，感谢他们的持续支持和洞察力以及他们的良好合作。他们让这3年感觉像1，当我开始在手头的科目的多样性感到迷失时，真的把我的注意力集中在相关的主题我还要感谢Aloys Augustin和Victor Nguyen，他们作为思科技术基金的开发人员加入了6G项目Aloys确实充实了我作为6x2的第一个原型编写的原始代码库我们还就6GPP的某些设计或实现细节进行了长时间的讨论，在此期间，他的见解帮助我详细阐述了全球架构。他还实现了RS3 -我们的存储调度器-在6x 10的存储服务器。Victor主要致力于6个区块设备的实现和基于擦除代码的存储系统副本缓存。这一部分不能不衷心提到思科和马克·汤斯利，他创立并经营着思科从项目的开始到我的博士学位结束，他一直是6xs背后的驱动力同样值得一提的还有Jérome Tollet，他在我们乘车或喝咖啡休息时多次激起我的好奇心，并与Aloys和我一起参与了RS3的详细设计，除了是一个快乐的办公桌邻居。最 后 ， 我 要 感 谢 我 的 博 士 生 和 朋 友 们 ， 即 Jacques Samain 、 YoannDesmouceaux、Marcel Enguehard、Mohammed Hawari和Hassen Siad。无论我们是围坐在餐桌旁，咖啡机旁还是婴儿足旁，他们总是让偶尔的沉闷远离我们，并为这三年的特别做出了巨大的贡献。vi内容作者声明我摘要IV确认v1关于分布式存储系统61.1不同类型的分布式存储系统架构61.1.1网络附加存储（NAS）和存储区域网工作（SAN） . . . . . . . . . . . . . . . . . . . . . . . . .71.1.2对等（P2P）网络。 . . . . . . . . . . . . . . .71.1.3分布式哈希表（DHT）。 . . . . . . . . . . . .91.1.4主-从架构 . . . . . . . . . . . . . . . .131.1.5总结。 . . . . . . . . . . . . . . . . . . . . . . . .161.2分布式存储系统。 . . . . . . . . . . .161.2.1奇迹。 . . . . . . . . . . . . . . . . . . . . . . . . .161.2.2复制。 . . . . . . . . . . . . . . . . . . . . . . . .171.2.3擦除代码。 . . . . . . . . . . . . . . . . . . . . . . .191.2.4擦除码和复制：什么是权衡 . .201.3一致性和共识。 . . . . . . . . . . . . . . . . . . .221.3.1理论框架 . . . . . . . . . . . . . . . . . .22一致性和可用性：CAP定理。 . . .22数据库特性：ACID和BASE。 . . . . . . .24以客户端和数据为中心的一致性模型。 . .251.3.2共识和一致性：如何达成。 . . . . . .27共识算法：Paxos和Raft。 . . . . . . . . .27延迟和一致性，（N，W，R）仲裁模型。281.4分布式存储系统的示例。 . . . . . . . . . . . .3126小时332.1为什么我们要从零开始？ . . . . . . . . . . . . . . . .342.1.1软件分层。 . . . . . . . . . . . . . . . . . . . . .342.1.2建筑原因 . . . . . . . . . . . . . . . . . . .342.1.3 Ceph . . . . . . . . . . . . . . . . . . . . . . . . . . . . .342.1.4 GFS。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .362.1.5扩展元数据层，- 是的 . . . . . . . . . . . . . . . . . . . . . . . . . . .372.2 6层架构 . . . . . . . . . . . . . . . . . . . . . . . . . .382.2.1体系结构描述。 . . . . . . . . . . . . . . . . .382.2.2将IPv6前缀归属于MN。 . . . . . . . . . . . .39vii2.2.36.2：以IPv6为中心的架构402.2.4基本操作说明422.2.5一致性452.3在不影响俱乐部的情况下扩大或缩小集群ter2.3.1存储节点472.3.2元数据节点482.3.3可用性和数据传输2.4应对故障：可靠性和修复模型502.4.1可靠性502.4.2对失败的反应50短路故障50失败51自愿关闭和维护51保持可靠性2.5关于架构的思考522.5.1客户端和群集配置522.5.2间接层522.5.3可扩展性532.5.4计量与分析542.5.5限制552.6实验评价552.6.1理由552.6.2设置和协议552.6.3结果572.6.4获取测试572.6.5测试后592.6.6CPU消耗分析602.6.7HTTP61的性能影响方案61结果622.7结论62360个延伸件653.1在6x65上构建块设备3.1.1不同的实施方式653.1.2关于缓存和一致性673.1.3业绩基准3.2将6LB适配为6LB713.2.1分布式存储系统3.2.2分段路由负载均衡733.2.3将6LB适配为6LB743.2.4一致性的后果753.3结论76viii4存储系统（RS3）784.1相关工作794.1.1分组调度804.1.2I/O调度804.1.3全系统调度4.2设计RS3814.2.1典型的存储服务器实施824.2.2RS34.2.3RS34.3第一次评估和分析4.3.1实验方案864.3.2公平结果874.3.3响应时间结果894.3.4搜索结果894.4利用Linux文件系统机制改进RS3914.4.1向内核924.4.2响应时间和吞吐量结果934.5与RS395更进一步4.5.1评估批量预算对RS3性能的影响。954.5.2调整RS3以实施策略：加权RS3974.5.3关于RS3及其目前实施情况的984.6结论1004.6.1更进一步1005缓存擦除编码对象1025.1相关工作1045.2分布式存储系统1065.2.1系统架构1065.2.2对象缓存1075.3理论评价1095.3.1型号1095.3.2系统型号1105.3.3业绩评价1115.3.4结果和评价1135.4实验评价1135.4.1实验装置1145.4.2评价与评价1165.5结论117一 预测容器图像预取123A.1 动机123A.2 储存和容器123A.3 关于流行容器图像的124A.4 优化预测集装箱图像存储系统（OPCISS）126ixB矢量化文件服务器129B.1动机129B.2技术水平130B.3VPP130中面向段的TCPB.4零拷贝文件服务器131参考书目133x2[2014 -05-23]图目录1SSD和HDD成本演变预测。 . . . . . . . . . . . .22网络、存储和内存硬件吞吐量发展。31.1 NAS和SAN。 . . . . . . . . . . . . . . . . . . . . . . . . . . .81.1a NAS。 . . . . . . . . . . . . . . . . . . . . . . . . . . . .81.1b SAN。 . . . . . . . . . . . . . . . . . . . . . . . . . . . .81.2具有ad hoc连接的非结构化P2P网络的示例节点之间的连接。 . . . . . . . . . . . . . . . . . . . . . . . .91.3使用DHT来识别节点的结构化P2P网络的示例。...............................101.4DHT说明示例111.5DHT再平衡141.5a分布式哈希表再平衡141.5b DHT稳定状态141.6GFS和HDFS SPOF151.6a GFS架构151.6b HDFS架构151.7Ceph18中的对象到服务器映射1.8对象间擦除码191.9对象内擦除码201.10 混合擦除码211.11 CAP定理：分区231.12 W>N保证了并发和不并发的不可能性，同时成功写入。.......................................................................................301.12a冲突实例301.12 b冲突已解决301.13 写死锁情况302.1可路由对象副本IPv6地址分解示例。 382.2元数据负载不平衡402.36架构示例412.4对象元数据示例422.54个基本的6进制操作的顺序图。...........................................................462.5a员额462.5b获取462.5c462.5d删除462.6当在集群4932 MG、7 MN2.6b 32机枪、8机枪2.7实验装置56xi2.8测试结果582.8a得到582.8b SSD上的帖子582.8c HDD58上的帖子2.9通过nginx和6.0获得的每秒请求数/对象大小623.1Linux存储堆栈663.2并行读取两个文件时的三个6字节块设备实现的图示。.....................673.36 GHz的块设备69的每秒I/O基准测试结果每秒3.3a I/O，3台服务器，读69每秒3.3 b I/O，3台服务器，写入693.3c每秒I/O，16台服务器，读693.3d每秒I/O，16台服务器，写入693.4600的块设备70的测试基准结果3.4 a发射机，3台服务器，读数703.4b吞吐量，3台服务器，写入703.4c投入，16台服务器，改为70台3.4d发送，16台服务器，写入703.56LB寻线示例743.66StorLB：MN753.76StorLB：SN764.1预算分配示例854.1a第一分配阶段814.1b第二分配阶段854.2每班平均吞吐量884.3每批预算的884.44KB请求的响应时间分布，RS3904.4a标准，读取大小= 4KB904.4b标准，读取大小= 32KB904.4c标准，读取大小= 64KB904.4d标准，读取大小= 128KB904.4e RS3，批量预算= 32KB904.4f RS3，批量预算= 64KB904.4g RS3，批次预算= 128KB904.4h RS3，批量预算= 256KB904.5使用和不使用RS3时的914.6使用和不使用posix_fadvise93时对象获取的阻塞时间4.6a不使用posix_fadvise934.6b使用posix_fadvise934.74KB请求的响应时间分布，RS3944.7a标准，读取大小= 4KB944.7b标准，读取大小= 32KB944.7c标准，读取大小= 64KB944.7d标准，读取大小= 128KB94xii4.7eRS3，批预算= 32KB。 . . . . . . . . . . . . . . . . .944.7fRS3，批预算= 64KB。 . . . . . . . . . . . . . . . . .944.7gRS3，批量预算= 128KB . . . . . . . . . . . . . . . . .944.7hRS3，批量预算= 256KB . . . . . . . . . . . . . . . . .944.8使用和不使用RS3的954.94KB请求响应时间的累积分布函数取决于批预算。........................... 964.10 40并发的总吞吐量和存储服务器CPU时间-每批预算租金类。...................................................................................975.1客户机从（2，r）擦除编码的分布式对象存储器请求对象B（未表示奇偶校验片段）。.................................................................................1065.2片段缓存与完整副本缓存。用虚线表示的缓存。.............................1085.2a遗留文件系统缓存：客户端2从缓存获取E1，但从磁盘获取E2迷人............................................................................................1085.2b完全副本缓存：客户端2从存储节点四是直接抓。. . . . . . . . . . . . . . . . . . . . . .1085.3缓存命中率。 . . . . . . . . . . . . . . . . . . . . . . . . . . .1125.3a缓存容量：0.01，类重分区：[1，1，4，4]。 . . .1125.3b缓存容量：0.01，类重分区：[1，1，1，1]。 . . .1125.3c缓存容量：0.05，类重分区：[1，1，4，4]。 . . .1125.3d缓存容量：0.05，类重分区：[1，1，1，1]。 . . .1125.3e缓存容量：0.1，类重分区：[1，1，4，4]。 . . . .1125.3f缓存容量：0.1，类重分区：[1，1，1，1]。 . . . .1125.4缓存浪费率 . . . . . . . . . . . . . . . . . . . . . . . . . .1145.4a类重新划分：[1，1，4，4]。 . . . . . . . . . . . . . . .1145.55.4b类重新划分：[1，1，1，1]。 . . . . . . . . . . . . . . .存储服务器实现：单个通用片段和对象，磁盘上有足够的通用片段，循环遍历它们而不会触及磁盘缓存。. . .1141155.6实际测试平台的缓存命中率。 . . . . . . . . . . . . . . . . .1175.7响应时间直方图。 . . . . . . . . . . . . . . . . . . . .1185.7a片段缓存，α=0.0。 . . . . . . . . . . . . . . . . .1185.7b高速缓存，α=0.0 . . . . . . . . . . . . . . . . . . .1185.7c片段缓存，α=0.4。 . . . . . . . . . . . . . . . . .1185.7d缓存，α=0.4 . . . . . . . . . . . . . . . . . . .1185.7e片段缓存，α=1.0。 . . . . . . . . . . . . . . . . .1185.7f高速缓存，α=1.0 . . . . . . . . . . . . . . . . . . .1185.7g碎片缓存，α=1.6。 . . . . . . . . . . . . . . . . .1185.7h缓存，α=1.6 . . . . . . . . . . . . . . . . . . .118A.1 81个最受欢迎的Docker镜像的大小和可执行比例分布。................125A.1a集装箱尺寸分布125A.1b容器中可执行文件的年龄125xiiiA.2 OPCISS架构。.......................................................................................126A.3 比较容器的启动策略。.........................................................................128A.3a完整下载128A.3b懒鬼lazy fetching128A.3c国际安全和安保组织的预测性预防措施B.1VPP架构130B.2在VPP131中应用B.3静态文件的预打包132xiv表的列表1大型科技公司每天存储和处理的数据估计。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31.1在DHT的度数和路由长度之间进行权衡。........................................... 111.2总结不同类型的体系结构及其特点161.3概述不同的分布式存储系统及其特点。...............................................322.1Get请求的CPU利用率平均值602.2员额请求的CPU利用率平均值604.1不带RS3、带RS3和带W-RS3的每个客户端的吞吐量，批量预算= 24KB。..................................................................................985.1模拟参数设置1115.2存储服务器在接收请求时执行的功能。.............................................1155.3基准参数设置116xv缩略语列表酸的原子性、一致性、隔离性和耐久性ACK确认ACL访问控制列表AFSAndrew文件系统AFPApple归档协议API应用程序可编程接口BASE基本可用，软状态，最终一致性位索引显式复制用户空间中的块CAP一致性、可用性、分区弹性CBQ基于类的CDN内容分发网络CFQ完全公平的CDNCOW写时复制中央处理器可扩展哈希下的CRUSH容器存储接口分布式哈希表DPDK数据平面开发包DRAM动态随机存取存储器EC擦除码/擦除编码ECMP 等成本多路径光纤通道协议FIOS闪存I/O接口GFSGoogle文件系统或全局文件系统HDD硬盘驱动器HDFSHadoop分布式文件系统HTTP超文本传输协议ICN信息中心网络I/O输入/输出每秒I/OpsiSCSI互联网小型计算机系统接口局域网LRU最近最少使用MDS最大距离可分MG元数据组MN元数据节点MRC单调读一致性MWC单调写一致性NAS网络连接存储xviNBD网络块设备NFS网络文件系统NoSQLNon SQL or Not only SQL（seeSQL）NVMeNon-Volatile MemoryexpressN2OS网络本机对象存储ON整流器节点OPCISS优化预测集装箱图像存储系统OSD对象存储守护程序PACELC分区：可用性或一致性，否则：延迟或一致性PCIe外围组件互连ExpressPG安置小组点对点QoS服务质量QUIC快速UDP互联网连接协议RADOS可靠自治分布式对象存储RAID独立RAM冗余阵列 随机存取存储器关系数据库管理系统研资局再生码RPM每分钟RS3请求存储服务器RTT往返时间RYWC读写一致性SaaS存储即服务SATA 串行AT附件SDS软件定义的存储SFQ启动时公平竞争SFQ（D）基于深度的起始时间公平搜索SLA服务级别协议SMB 服务器消息块SN存储节点存储平面开发工具包SQL结构化查询语言SR段路由SRLB网段路由负载均衡SSD固态硬盘TCP传输控制协议UDP用户数据报协议VFS虚拟文件系统VIP虚拟IPVM虚拟机矢量分组处理WFQ加权公平值WFRC写跟随读一致性YFQ又一个公平搜索算法1∼−∼−∼−介绍动机二十多年前，第一个分布式存储系统诞生，试图以比常规备份更方便的方式确保重要数据永远不会丢失，并且始终可用。绝大多数分布式存储系统都遵循相同的模式：它们被设计为运行在许多便宜，不可靠和通用的设备上，这些设备由多个存储磁盘，一个处理器，一个网络接口，有时还有一些额外的内存组成。这些系统的软件将这些设备组织在集群中，在服务器之间分发数据，并通常确保故障对集群性能的影响最小然而，在过去的几年里，存储的格局已经在许多方面发生了变化。首先，十多年来，在硬盘驱动器（HDD）达到每分钟15K转数（RPM）的机械限制后，存储硬件一直落后于CPU，内存和网络。然而，随着闪存变得越来越可用，性能 与速度慢且延迟高的HDD不同，515ms）以及低每秒输入/输出（I/Ops）（50 200个视情况而定在旋转速度和总线类型上[2]）由于旋转的机械部件，固态驱动器（SSD）提供了更好的吞吐量以及更低的访问延迟（0.050.2ms [3]）。更是如此对于非易失性存储器（NVMe）-此外，不断提高的闪存质量和可负担性意味着HDD和SSD价格曲线预计将在未来几年内继续接近甚至交叉，如图1所示。结合图2中DRAM吞吐量的演变与其存储和网络对应物的比较，自然的结果是传统的存储软件（旨在解决以前的值得注意的是，新一代NVMe使得传统中断驱动的I/O在CPU消耗方面非常低效[6]。此外，远程存储（由