摘 要

随着社会信息化程度不断提高，数据对于个人、企业和国家而言都尤为重要。而数据存储面临着各种人为和自然灾害的威胁，如何防止数据丢失、保证数据安全性成为重中之重。数据冗余技术是保障数据安全的有效方法，它主要包括副本和纠删码技术，纠删码技术可以在保证数据安全性的同时，节省更多的存储空间，从而广泛地运用于存储系统中。同时，随着数据产生的价值越来越多，挖掘数据价值的企业级应用对于实时查询、实时动态计算等新的实时业务诉求在不断增长，而受限于磁盘I/O，出现了明显的滞后性。采用内存文件系统构建高吞吐量和低访问延迟的数据存储系统，是一种比较好的解决方案。

本文将数据冗余技术和文件系统进行结合，在分布式内存文件系统Alluxio基础上分别为其增加了纠删码特性、副本特性，基于这两类系统完成了数据创建写、数据更新写、数据失效读、正常读四种访问操作；同时基于本地磁盘文件系统为其增加副本特性，完成四种访问操作；之后测试了三类文件系统的四种访问操作的性能并分析其结果。

本文还完成了纠删码技术和副本技术的空间使用效率、纠删码内存文件系统对不同大小数据块读写性能的测试与结果分析。测试结果表明，纠删码内存文件系统在存储空间使用效率上相对于副本文件系统有明显的提高，对大文件的处理性能明显要好于对小文件的处理性能，同时正常读写速率明显优于副本磁盘文件系统。但由于纠删码需要进行编码和解码计算，纠删码文件系统在数据失效读和更新写操作方面相比于副本内存文件系统稍有劣势。

关键词：纠删码；副本；Alluxio内存文件系统

Abstract

With the continuous improvement of social information, data is particularly important to individuals, businesses and countries. Data storage is faced with a variety of man-made and natural disaster threats. How to prevent data loss and ensure data security becomes a top priority. Data redundancy technology is an effective method to ensure data security,it mainly includes replication and erasure code technologies， erasure code technology can save more storage space while ensuring data security, thus it is widely used in storage systems. At the same time, with the increasing value of data generation, enterprise-level applications that mine data values ​​are increasingly demanding new real-time services such as real-time queries and real-time dynamic computing, but there is a significant lag in these applications because of disk I/O. Using a memory file system to build a high-throughput and low-access delay data storage system is a better solution.

This paper combines the data redundancy technology and the file system, and adds the erasure code feature and the replication feature respectively to the distributed memory file system Alluxio. Based on these two types of systems, four data access operations ,the data normal reading, normal writing, degraded reading and data update writing, has been completed. At the same time, based on the local disk file system, it has been added a replication feature and also implemented four access operations. After that, the performance of the four access operations of these three types of file systems was tested, and the reasons for the different access performances of the above different file systems were analyzed.

This paper also completes the test and analysis of the space usage efficiency of erasure code technology and replication technology and of the erasure code memory file system read and write performance for different data block size. From the experimental results, the erasure code memory file system has a significant improvement in the efficiency of the storage space relative to the replication file system. The processing performance of the large file is obviously better than the processing performance of the small file, and the read/write speed is obviously better than the replication disk file system. However, due to the need for encoding and decoding calculations, there is a slight disadvantage compared to the replication memory file system in terms of data degraded reading and update writing operations.

Keywords: Erasure code, Replication, Alluxio memory file system

目录

摘 要 I

Abstract II

第1章 绪论 1

1.1研究背景与意义 1

1.2数据冗余技术研究现状 2

1.2.1 副本技术 2

1.2.2 纠删码技术 2

1.3内存文件系统的研究现状 3

1.4主要研究内容 4

1.5本文组织结构 5

第2章 相关技术 6

2.1数据冗余技术 6

2.1.1 副本技术 6

2.1.2 纠删码技术 6

2.1.3 纠删码技术与副本技术的比较 11

2.2 Jerasure开源库 12

2.2.1 运算模块 12

2.2.2 相关函数说明 12

2.3 Alluxio内存文件系统 13

2.3.1 Alluxio系统架构 13

2.3.2 Alluxio数据读写过程 14

2.4 本章小结 15

第3章 系统设计与实现 16

3.1 系统体系结构设计 16

3.1.1 纠删码内存文件系统体系架构 16

3.1.2 副本内存文件系统体系架构 17

3.1.3 副本磁盘文件系统体系架构 17

3.2 内存文件系统四种访问操作实现 18

3.2.1 正常读 18

3.2.2 数据创建写 18

3.2.3数据失效读 20

3.2.4 数据更新写 21

3.3副本磁盘文件系统四种访问操作实现流程 22

3.3.1 正常读 22

3.3.2 数据创建写 22

3.3.3 数据失效读 23

3.3.4 数据更新写 24

3.4 本章小结 24

第4章 系统测试与结果分析 25

4.1测试环境简述 25

4.2 系统读写数据和纠删码编解码正确性测试 26

4.3 三类文件系统的四种数据访问操作性能测试 28

4.3.1 正常读性能测试 28

4.3.2 正常写性能测试 29

4.3.3 更新写性能测试 30

4.3.4 数据失效读性能测试 30

4.4空间效率测试与分析 31

4.5 文件块大小对纠删码内存文件系统性能影响测试 33

4.6 本章小结 34

第5章 结束语 35

5.1 工作总结 35

5.2 未来展望 35

参考文献 37

致谢 39

第1章 绪论

1.1研究背景与意义

随着信息时代的来临，人类正处于一个数据爆炸的时代，数以亿计的用户无时无刻不在产生新的数据，同时记录人们生活的历史信息也呈爆炸式增长。国际数据公司IDC(www.idc.com)在2012年12月份发布了一份关于数字宇宙(Digital Universe)的研究报告，预计到2020年，数字宇宙即全球的数据量总和将达到40ZB，相比2005年的130EB，增幅达到300倍^[1]。为了满足日益增长的存储需要，数据存储系统结构正在不断改变，从传统的集中式存储到分布式存储再到近几年出现的云存储等新型海量存储模式。然而，这些存储系统所支持的存储介质单一，导致了数据分析处理时工作流中间数据I/O开销过大，效率低下。此外，随着新型硬件技术的不断发展，内存容量越来越大，价格却在不断降低。更多的硬件将配备越来越高的内存，作为可以用作存储资源的内存空间正在不断变大。所以，如何合理使用内存构建大规模存储系统使得以突破磁盘I/O时延瓶颈已成为研究热点。

同时，随着人们在日常生活和工作中对于信息技术的依赖程度的提高，越来越多的重要数据被存储在计算机系统中，一旦信息系统中的关键数据丢失或破坏，可能会带来不可估量的损失。根据IDC咨询公司的调查结果，美国在20世纪后10年发生过数据灾难的公司中，55%当即倒闭，剩下45%中由于信息数据丢失，29%在两年内倒闭，能生存下来的仅占 16%。而著名 IT咨询服务提供商Gartner的报告数据也表明，40%的企业不能在灾难发生后恢复运营，剩下60% 中有33%在两年内倒闭。美国9.11事件一年后，重返世贸大厦的企业由原先的350家减少到150家，200家企业由于重要信息系统破坏及关键数据丢失而永远倒闭消失^[2]。

数据如此重要，因此需要提高存储系统可靠性以增强数据可用性。为了保障存储可靠性与数据可用性，必须采用数据冗余机制。冗余机制主要包括副本（Replication）和纠删码（Erasure Code）技术，前者将每个原始数据分块都镜像复制到另一个存储设备上，以保证原始数据不可用时有副本可恢复；后者将原始数据进行划分、编码和分发，后将编码分块独立存储到存储设备上。相对于副本技术，纠删码具有更高的存储效率（即，存储空间利用率），在相同存储空间情况下能获得更高的容错能力。如今，纠删码已成为副本之外的另一种可靠存储方式，广泛应用于存储系统中，如面向大数据挖掘的集群存储、面向数据托管的云存储、和面向数据长期保存的归档存储等。

基于上述研究背景，本文将在现有的内存文件系统上增加纠删码特性，将其与基于副本的内存文件系统和基于副本的磁盘文件系统进行性能比较，验证纠删码内存文件系统的优越性。

1.2数据冗余技术研究现状

1.2.1 副本技术

副本技术(Replication)其基本思想是将数据文件按照固定大小切成分块，每个数据分块在多个位置都保存有副本。当源数据分块失效后，可以读取其他副本恢复数据。目前副本放置策略是副本技术的研究热点。

存储系统中一般采用多副本策略来提高系统的可靠性，但副本的增多会导致网络带宽压力过大，传输数据时间增长。所以，在保证系统高可靠性的同时保证副本传输效率是副本放置策略好坏的关键。目前，主要有顺序副本放置策略和随机副本放置策略两种。

顺序副本放置策略是在将副本写进系统之前就确定好了放置位置，之后就不在改变。该策略能够很好的预防系统中随机的多个节点失效错误，如分布式虚拟磁盘文件系统Petal^[3]所应用的放置策略就是比较典型的顺序放置策略，其采用菊花链式结构，在多节点存储系统中，当逻辑顺序连续的两个节点失效才会导致数据丢失，除此之外，任意一个节点上的数据都能够在其相邻的节点上找到相应的副本。

随机副本放置策略是将副本随机的放到各个节点上。这样有利于系统的负载均衡，避免系统中某个节点数据热度高而被频繁访问出现的单点故障。目前，开源分布式文件系统HDFS、谷歌公司的GFS系统与及Facebook公司的Cassandra系统都采用了多副本随机放置策略。此外，学术研究主要集中在提高数据访问效率和系统能效方面，文献[4]以目前主流的Hadoop为研究对象，提出一种面向大规模异构Hadoop集群存储系统的随机副本放置策略，能够充分利用集群中的高性能节点提升大数据应用的执行能力同时提高系统能效；文献[5]针对副本放置问题,提出一种基于多访问策略的副本动态更新算法MPFSF(min_placement far servers first)。该算法在引入通信距离限制的同时,尽可能多地重用网络中已存在的副本,并根据需要实施必要的副本更新,最大使用每个副本的处理能力,以便降低数据访问的时延,提高数据访问效率。

1.2.2 纠删码技术

(1)国内研究现状

国内学者在纠删码方面开展了富有成效的研究工作。通过梳理国内在纠删码存储方面的文献，发现国内的纠删码存储研究主要集中于磁盘阵列与阵列编码两个分支上，如中科院研究生院提出一类纠双错MDS阵列纠删码（V码）^[6],其具有最佳编译码特性、平衡特性、码长可为偶数和奇数特性与及较其它纠双错码具有更好的整体性能；西北工业大学设计了一种容三错RAID布局（TP-RAID）^[7]，其是基于水平和对角奇偶校验，并可分别容许两个和三个磁盘故障的数据布局，满足了单容错数据布局所实现的数据可用性不能满足应用对高可用性的需求；国防科技大学为大规模存储系统设计了一种高容错低修复成本的编码EXPyramid^[8]，文中针对该码提出了一种最小修复成本算法和基于广度优先搜索的最小读取成本算法，并对这两种算法进行了测试与分析，分析结果表明, EXPyramid码能够有效地降低系统的修复成本和读取成本,有较强的容错能力,且构造灵活,结构规则易实现,具有很强的实际应用价值；中国科技大学为RAID-6存储系统提出一种最优行对角校验恢复方法（RDOR）^[9]，它是针对RAID-6存储系统中广泛使用的行对角奇偶校验码（RDP）和EVENODD码利用一个奇偶校验磁盘恢复单磁盘故障而没有充分利用RAID-6系统中的两个奇偶校验磁盘提出的一种混合恢复方法。

(2)国外研究现状

纠删码存储相关研究主要集中于国外大公司，具体地，这些公司为各自大规模存储系统产品提供设计方案和优化方案，例如：Google在其GFS文件系统中增加了RS码支持^[10],文中通过调整RS码的不同参数和数据放置策略设计了多种测试模型对系统数据可用性进行比较，选出了最佳RS码；微软研制的Azure云存储系统也支持RS码，使存储系统具有高可用性、持久性和可扩展性，其研究团队还在此RS码基础上设计了具有重构优化特性的局部重构编码（Local Reconstruction Code，LRC）^[11]；Facebook采用Hadoop HDFS来搭建其Blob 存储集群，其采用了Mirrored RAID-5编码和RS编码，也支持一种缩短重构链的局部修复编码（Locally Repairable Codes，LRCs）^[12]，其针对随着时间的推移数据的访问频度会逐渐下降这一特性，采用不同的编码方式来存储数据从而提高存储空间利用率；此外，IBM所收购的Cleversafe致力于归档存储，其采用柯西RS码来获得高性价比存储^[13]。

1.3内存文件系统的研究现状

内存文件系统是指直接在内存中建立文件系统，将内存作为元数据和数据存储的基本介质。随着存储器技术的不断更新与发展，内存文件系统主要分为两类：基于DRAM的内存文件系统和基于NVRAM内存文件系统。

DRAM是一种易失性的存储器，并且DARM存在着密度和容量的瓶颈，在数据爆炸式增长的今天，为了保证基于DRAM内存文件系统的高可扩展性、高数据吞吐量和低访问延迟性，传统的内存文件系统如tmpfs已难堪重负，目前分布式内存文件系统已成为研究热点。分布式内存文件系统部署和运行于分布式环境之中，具有高速的读写访问服务。分布式内存文件系统的研究主要在解决数据可靠性、数据分布和系统可扩展性、并发控制与一致性问题上进行。John Outerhout提出了基于DRAM的云存储—RAMClouds^[14]。RAMClouds利用并发写数据备份策略来提高可靠性、使用高效数据分配额算法和负载平衡技术来提高可扩展性。李浩源提出了基于DRAM的开源分布式存储系统—Tachyon^[15]。Tachyon利用zookeeper、Journal、世代关系进行容错，具有一个通用、方便于接入不同底层文件系统的接口来实现扩展性。东南大学提出了一种基于内存的HDFS数据存储技术^[16]，通过合理部署内存存储资源、优化内存存储的副本放置、设计文件热度估算模型来置换内存存储数据实现高速、可靠、高吞吐性。

此外，NVRAM虽然还处于起步和发展阶段，但基于NVRAM的内存文件系统的研究也在紧锣密鼓地进行着。新型的NVRAM存储介质一方面可以像DRAM一样按字节访问，因此可以直接连接总线被存储器直接访问；另一方面可以像磁盘那样持久化数据。BPFS^[17]是利用BPRAM建立在用户空间上的文件系统，保证了文件操作是原子性的并且是按程序顺序执行的，同时数据是持久存储在内存中的。PRAMFS^[18]是针对NVRAM设计的具有持久化存储和数据保护功能的文件系统，用来存储经常访问且未写到外存的易失数据。PMFS^[19]文件系统支持POSIX文件系统接口，跳过了块设备驱动层和页缓存层，从而使程序易于移植并避免了面向块的I/O慢速读写，提供了到持久化介质的同步读写。

1.4主要工作

本文针对存储系统中磁盘I/O效率低无法满足企业级应用对实时业务的诉求与及副本技术备份数据占用空间大的问题进行了研究，通过将内存文件系统和纠删码技术结合来提高存储系统的I/O读写速率和空间使用率，主要在以下三个方面展开了工作。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：