摘 要

随着“互联网 ”时代的到来，网络环境下每十八个月新生成的数据量约为过去生成数据量的总和。数据量的爆炸性增长，对存储系统的I/O性能、数据容错性、存储安全性等指标提出了更高的要求。传统的集中式存储系统已经无法满足存储海量数据的需求，分布式存储系统应运而生。

为了增强分布式存储系统的访问性能，一种技术趋势将越来越多数据缓存在内存中，从而构成分布式内存系统。随着分布式内存规模的不断扩大，内存中驻留的数据也越来越多。但断电、火灾、硬件故障、病毒攻击等等事故可能导致存储节点失效从而使得整个系统数据丢失风险增大。出于内存数据容错性考虑，本文提出了“内存奇偶校验 外存单副本”的数据容错方案，以数据分块D₀和D₁的存储为例，内存校验数据分块P由源数据分块D₀和D₁异或得到，外存则存放一份源数据分块D₀和D₁的副本，利用这种放置方案，不仅能支持内存数据容错，而且能提高内存空间利用率。

本文通过与另外一种内存数据容错方案——“内存双副本 外存单副本”进行对比分析，从时间和空间开销的角度，验证本文“内存奇偶校验 外存单副本”方案在内存数据一致性方面的优越性，实验中两者内存数据更新时间基本相近，而内存空间利用率则从50%提高至66.7%，证明此内存数据容错方案能够有效的增强整体性能。

关键词：纠删码；分布式内存；数据容错；数据一致性

Abstract

With the coming of the “Internet ” age, in the network environment it is the fact that during every eighteen months the amount of newly generated data is approximately equivalent to the sum of the amount of generated data in the past. With the explosive growth of the amount of data, it puts forward higher requirements for the storage system in terms of the I/O performance, data fault tolerance, storage security and so on. The traditional centralized storage system has been unable to meet the needs of storing the massive data, the distributed storage system came into being.

In order to enhance the access performance of distributed storage system, it is a technology trend that more and more data is cached in memory, thereby forming a distributed memory system. With the continuous expansion of the scale of distributed memory, the data in memory becomes more and more. However, the accident of power failure, fire, hardware failure, virus attack and so on could cause the storage nodes failure so that the risk of data loss is increased in the entire system. For the considerations of fault tolerance of the data in memory, the paper proposes a data fault-tolerant solution called as “memory parity external memory single copy” , in data block D₀ and D₁ storage case, the memory parity data block P is got by the xor operation of the source data block D₀ and D₁, a copy of the source data block D₀ and D₁ is stored in external memory. Using the solution can not only support the fault tolerance of the data in memory, but also improve the space utilization of memory.

In the paper, the solution is compared and analyzed with another fault-tolerant solution of the data in memory called as “memory double copy external memory single copy”. From the view of time and space overhead, the advantages of the solution in terms of the consistency of the data in memory have been proved. In the experiments both update time of in-memory data is basically the same, but the space utilization of memory can be improved from 50% to 66.7%, which proves that the solution can effectively improve the overall performance.

Key words: Erasure code；Distributed memory；Data fault tolerance；Data consistency

目 录

第一章 绪论 1

1.1 研究背景和意义 1

1.1.1 研究背景 1

1.1.2 研究意义 3

1.1.3 国内外研究现状 3

1.2 本文内容 4

1.3 本文组织结构 5

第二章 技术背景概述与技术方案选择 6

2.1 存储集群下的内存管理机制概述 6

2.1.1 典型内存管理机制分析 6

2.1.2 常见内存管理器概述 9

2.2 纠删码概述 12

2.2.1 纠删码与完全副本比较 12

2.2.2 纠删码原理 12

2.2.3 典型纠删码 13

2.2.4 RS纠删码分类 13

2.3 内存数据更新方案 15

2.3.1小写更新 15

2.3.2 DUM更新方案 15

2.3.3 PUM更新方案 15

2.3.4两种方案分析比较 16

2.4 Unix网络编程概述 17

2.4.1 文件I/O 17

2.4.2 线程 17

2.4.3 Socket原理及分析 17

第三章 分布式内存数据容错模型设计与实现 20

3.1内存双副本 外存单副本容错模型 20

3.1.1 系统初始化过程 20

3.1.2 内存数据更新过程 22

3.2 内存奇偶校验 外存单副本容错模型 25

3.2.1 系统初始化过程 25

3.2.2 内存数据更新过程 27

3.3 方案对比分析 31

第四章 实验测试 33

4.1实验工具 33

4.2实验平台 39

4.3实验参数 40

4.4功能测试 41

4.5性能测试 50

4.6结果分析 55

第五章 总结与展望 57

5.1总结 57

5.2展望 58

参考文献 60

致谢 62

第一章 绪论

1.1 研究背景和意义

1.1.1 研究背景

随着WEB 2.0时代的到来，用户不再是单纯的信息阅读者，而成为了信息的创造者。据统计全球用户每分钟发送17.4千万封邮件，全球用户每天会上传2.88万部视频至Youtube，全球用户每天在Twitter上发布的信息超过5千万条，全球用户每天在亚马逊上会产生630万订单，全球用户每年产生的数据量已经达到ZB数量级等等，俨然大数据的发展势如破竹，近年来国内外已经相继出现了许多大数据应用的实例，比如2013年4月，美国著名的计算搜索引擎Wolfram Alpha,对脸书网中一百多万美国用户社会行为数据分析，希望得到美国用户的社会行为规律，通过大数据分析，发现大多数美国脸书网用户在二十岁左右谈恋爱，在二十七岁左右订婚，在三十岁左右结婚，而在三十岁至六十岁期间双方婚姻发展缓慢，此分析结果与美国官方人口普查结果相比基本相同^[1]；2012年4月美国著名的经销商OverDrive公司从其电子图书馆中采集大量网站访问数据，电子书和数字有声读物的流通数据以及读者的需求数据等等，并对其进行分析，既为图书馆提供了所不具备的书籍清单，也提高了出版商和经销商图书的销售额，达到了双赢的效果^[2]等等。数据即财富，著名出版公司O’Reilly的创始人Tim O’Reilly甚至断言：未来属于能把数据转换成产品的公司和群体；Gartner Group公司更加准确地预测至2015年采用大数据管理的公司将在各项财务指标上超过未作准备的公司达20%^[3]。世界各国为了提高自身综合国力，都相继将大数据的发展提升至战略高度，创造积极政策，法律环境，增加相关产业财政投入，加强人才培养和核心技术研发等等，比如2012年3月美国奥巴马总统把“大数据战略”提升为最高国策，将大数据比作“未来的新石油”并把对数据的占有和控制作为一种新的国家核心竞争力^[4]；2010年11月欧盟通信委员会以开放数据为核心制定了应对大数据发展的战略，为实现“欧盟2020战略”提供了新的动力^[5]等等，由此可见大数据的发展必将成为第四次工业革命的助力剂。

然而大数据的发展离不开海量数据的存储以及处理，面对海量数据，传统的解决方案是采用网络存储，且一般采用专用服务器和专用磁盘阵列集中式存储数据，由于大规模的访问请求可能成为系统性能的瓶颈，且在访问性能或者存储容量不足时集中式存储系统不易扩展，除此之外其存储可用性也很难符合需求。鉴于以上几点，集中式网络存储已经无法满足存储海量数据的需求，分布式存储系统应运而生。分布式存储系统是将海量数据分别存放在彼此相互独立的多个存储节点，能有效的分担存储节点的负载，并利用位置服务器定位存储信息，不同存储节点可同时提供数据访问服务，具有很高的数据吞吐率，解决了系统性能方面的瓶颈，且分布式存储系统通常使用普通的服务器作为存储节点，能方便廉价的实现动态的扩展和缩减功能，满足用户不同的存储需求，而对于海量数据的集中管理，不仅提高了存储数据的安全性，而且降低了安全管理成本，至于分布式存储系统的可靠性，大多数情况下采用冗余机制来维持，并且采用出色的节点恢复策略能在其失效时高效的进行修复。随着对等节点技术，网格计算，云计算等等新兴技术的快速发展，推动了分布式存储系统的快速发展，当前主流的分布式存储系统有Apache开源软件基金会的HDFS，它是GFS的开源实现，具有主从结构即主节点Namenode存放元数据，从节点Datanodes存放数据文件，由客户端询问Namenode数据文件索引信息，再与Datanodes进行读写交互，HDFS采用三副本冗余，主节点Namenode定期接受存储数据块的“心跳”信息，一旦发现数据失效，则立刻发送数据修复命令利用存储在不同节点的副本恢复失效数据^[6]；Amazon Dynamo则是一套典型的的基于Key-Value键值对存储的分布式系统，其存储模型是一张简单的Key-Value映射表，且采用著名的一致性哈希算法把副本数据分别存储在不同的节点，并通过鲁棒协议探测节点是否已经失效，利用hinted handoff技术解决节点临时性故障等等。