方胜吉

摘 要 本文主要是对分布式存储的存储算法及分布式处理的核心算法的研究，分布式存储究其本质而言，主要就是通过分布式文件系统，把数量十分巨大的数据，存储到零散的、不同的物理设备上的过程，而在这一过程当中，采用不同的存储方法和存储结构所得到的存储效率是完全不同的，因此，对存储方法的研究对海量存储结构的构建有着十分重要的意义。

关键词 分布式存储；海量数据；存储算法

中图分类号 TP3 文献标识码 A 文章编号 1674-6708（2017）198-0142-02

1 常见的分布式存储算法

1.1 NFS网络文件系统

早期的分布式文件系统，多数都是基于NFS的[1]。NFS的设计，主要是对硬件和操作系统提供异构支持，即容许不同操作系统的终端接入NFS系统，访问同一个共享存储区，进行文件的共享。它的适用范围包括局域网和广域网，而且NFS还形成了Internet标准-NFS协议。被大多数企业构建局域网时所采用。

从结构上看，其中要有一台服务器和至少一台的客户端，服务器的功能比较复杂，主要用来存储文件和目录；客户机的功能主要是对存储在服务器上的数据进行远程访问。当服务器上保存的元数据非常庞大时，直接检索效率极低，只能依赖CDN，但这并不能从本质上解决问题。所以当网络文件系统在存储大量的庞大数据时，缓存成为了存储的关键所在，而且，其扩展性比较一般。

1.2 BigTab1e

与传统的关系型数据库不同，BigTab1e是非关系型的，其本质是分布式的、稀疏的、可持久化存储的多维度排序Map。Bigtab1e是为了处理PB级别的数据而设计的。它具有广泛的适用性，可扩展能力强，具有高性能和高可用特性。

从实现策略的层面来讲，BitTab1e与数据库更加接近，但对于数据库的一些高级操作它是不支持的，比如SQL中的关联操作。但它对大数据的处理是很擅长的，而且容错性和管理性也极为强大，它可以用多级映射的方式来解决数据操作问题。

它以一种开放模式提供给客户简单的数据模型，对数据分布策略的设计以及对数据结构的构建都相当的自由。BigTab1e对功能的要求也很简单，就是能够存储数据，并完善相应的技术，保证数据安全就可以了，至于更加复杂的工作，比如确保数据正确，则交由上层应用系统来完成。它也采用Master/Slave的架构，一台Master服务器，管理多个Tab1et的机器。在Master上主要完成的工作就是把Ta1bets分配给相应的服务器，同时还要对Tab1et服务器的数量进行动态的查询，控制其数量在一个阈值范围内，还要有一项重要的工作就是要平衡服务器的负载，并对分布式文件系统上的垃圾文件进行处理。之外，还需要对数据模式相关的操作，进行修改和处理。每个Tab1et server基本都会管理着数十至数千个数量不等的客户端，负责对其中的读和写操作进行处理，如果数据量太大时，对要把它分割成小块。客户端读數据，将跳过Master，直通Tab1et Server。因此，在实际应用中，Master服务器的负载并不重。最初的一个表单会伴随着其中数据的不断积增而被分割成不同的小块Tab1et，但是Tab1et的大小又不能没有限制，一般情况下，都在100～200MB左右。

2 分布式处理算法

Google公司的MapReduc分布处理算法，是当今世界上最主流的分布式处理算法，MapReduce的根本的设计理念是大变小[3]；也就是说将一个巨大的任务块，按照一定的规则进行分解，使其成为若干小任务块，然后对其分别进行并行处理，之后再把想要的最后的结果合并起来。MapReduce的数据处理格式采用结构。用户通过Map函数处理原始数据，通过Combine得出中间结果，用Reduce将所有具有相同中间Key值的中间结果Value值合并在一起得到最终结果。MapReduce可以运行在低端的廉价PC机构成的集群上，但是MapReduce能够利用集群的整体性能完成超级计算，在性价比上还高于超级计算机。

Map Reduce 的操作流程如下[2]：

1）Map过程：MapReduce主要是为了实现并行处理，在任务开始时，首先是将输入文件分割成M个片段，片段的数量M根据Map的多少而定，在分割的过程中，不用考虑文件的类型，分割的方法也可以自己定义。分割后，会形成M个片段，这M个片段会被分配到对应的Task Tracker任务。由工作Tracker进行统一的处理，通过心跳信号获取每个TaskTr acker任务的状态，从而取得每个片段处理的状态。当一个“分解（Map）”任务启动后，会创建一个新的“写对象（Writer）”，对应到相应的“规约（Reduce）”任务。 在指定的InputFormat里面会为Writer对象提供一个RecordReader用来读取它的文件分割体； 同时，对输入文件的分析、键值对的生成以及文件分割体边缘的处理也都有InputFormat类来完成。RecordReader读取键值对后，传递给Mapper，它是由用户自己完成的配置，在这种情况下，用户对键值对的操作没有任何的约束，接下来，通过OutputCollector.collect方法，就可以对用户收集其自定义的键值对。结果的输出，需要用两个类，即一个Key类，另外一个是Value类。键值对被收集后，我们要用到另外的一个类—Partitioner，通过它给键值对指定一种区分方式，之后才能写入文件。为了使后续的规约任务能够负载均衡，我们还要配置一个有效的哈希函数。每个输出文件以及从Map任务中产生的键值，都会被送到其对应的Reduce里，在指定的Reduce任务中会对指定Key的所有键值进行处理。

2）Combine过程：通常，Map后的中间结果将会被送入内存，在这里，为了提高Reduce的效率，我们设置了一个Combiner类，Combiner会收集Map的中间结果并形成1ist列表，每一类Key值对应一个1ist列表，当列表中的键值对达到一定数量后，相同Key值的Value就会被送入合成器Reduce方法中。

3）Reduce过程：当Reduce获取了间接数据结果后，就要对其按照关键字（即Key值）进行排序，把同一关键字的值的数据排列在同一处。在Reduce过程中不同的关键值会映射到同一Reduce，所以对关键字的排序是必要的。Reduce对排序后的中间数据进行遍历，取得每个唯一Key值， 然后将这个Key值和它相关的Value值形成集合，最后按照用户给定的操作输出。

3 结论

本文主要介绍了如NFS、BigTable等常见的分布式存储算法，又以MapReduce为例，表述了分布式存储的核心处理算法。通过对分布式存储及处理算法的分析，为设计海量数据存储模型提供参考依据。

参考文献

[1]王鹏，孟丹，詹剑锋，等。数据密集型计算编程模式研究进展[J].计算机研究与发展，2010，47（11）：1993-2002.

[2]李波.基于Hadoop的海量图像数据管理[D].上海：华东师范大学，2011.

[3]霍树民.基于Hadoop的海里影像数据管理关键技术研究[D].长沙：国防科学技术大学，2010.