海量数据处理

海量数据处理是基于海量数据上的存储、处理、操作。

所谓海量，就是数据量很大，可能是TB级别甚至是PB级别，导致无法一次性载入内存或者无法在较短时间内处理完成。面对海量数据，我们想到的最简单方法即是分治法，即分开处理，大而化小，小而治之。我们也可以想到集群分布式处理。

1 海量数据的存储：为大数据分析做准备

传统关系型数据库

传统关系型数据库在数据存储上主要面向结构化数据，聚焦于便捷的数据查询分析能力、按照严格规则快速处理事务（transaction）的能力、多用户并发访问能力以及数据安全性的保证。其结构化的数据组织形式，严格的一致性模型，简单便捷的查询语言，强大的数据分析能力以及较高的程序与数据独立性等优点获得广泛应用。 但是 面向结构化数据存储的关系型数据库已经不能满足当今互联网数据快速访问、大规模数据分析挖掘的需求。

它主要缺点：

1) 对于半结构化、非结构化的海量数据存储效果不理想。像电子邮件、 超文本、标签（Tag）以及图片、音视频等各种非结构化的海量数据。

2）关系模型束缚对海量数据的快速访问能力：关系模型是一种按内容访问的模型。即在传统的关系型数据库中，根据列的值来定位相应的行。这种访问模型，会在数据访问过程中引入耗时的输入输出，从而影响快速访问的能力。虽然，传统的数据库系统可以通过分区的技术（水平分区和垂直分区） ，来减少查询过程中数据输入输出的次数以缩减响应时间， 提高数据处理能力， 但是在海量数据的规模下，这种分区所带来的性能改善并不显著。

3）在海量规模下， 传统数据库一个致命弱点， 就是其可扩展性差。

非集中式数据存储管理系统

1）亚马逊（Amazon）的 Dynamo ：

Dynamo是亚马逊的key-value模式的存储平台，可用性和扩展性都很好，性能也不错：读写访问中99.9%的响应时间都在300ms内。

在 Dynamo 中，数据按照键/值对（key-value）进行组织，主要面向原始数据的存储。这种架构下，系统中每个节点都能相互感知，自我管理性能较强，没有单点失效。

2）Google的Bigtable

Bigtable 是谷歌开发的一套结构化存储系统。数据以多维顺序表的方式进行存储。整个系统采用传统的服务器群形式，由一个主控服务器和多个子表服务器构成，并使用分布式锁服务 Chubby进行容错等管理。这种架构下，将存储（依靠 GFS）和服务的管理分离开来，简化了管理难度，易于维护且人为可控。但是由于底层存储依赖分布式文件系统，使得Bigtable 只能在集群中部署。

hadoop中Hbase就是Google BigTable的开源实现。

2）Facebook 的 Cassandra

CassandraCassandra最初由Facebook开发,后转变成了开源项目.是一套采用对等网络计算（peer to peer，P2P）技术实现的结构化数据存储系统。以Amazon专有的完全分布式的Dynamo为基础，结合了Google BigTable基于列族（Column Family）的数据模型.P2P去中心化的存储。很多方面都可以称之为Dynamo 2.0。

与 Dynamo 有所不同的是，Cassandra 采用类似 Bigtable 的多维表数据模型组织数据。其主要功能比Dynamo更丰富，但支持度却不如文档存储MongoDB（介于关系数据库和非关系数据库之间的开源产品，是非关系数据库当中功能最丰富，最像关系数据库的。支持的数据结构非常松散，是类似json的bjson格式，因此可以存储比较复杂的数据类型。）

主要特性：
　　● 分布式
　　● 基于column的结构化
　　● 高伸展性

2 海量数据处理

海量数据处理就是如何快速地从这些海量数据中抽取出关键的信息，然后提供给用户。

并行计算解决方案：

解决大规模数据处理的方法之一就是并行计算。将大量数据分散到多个节点上，将计算并行化，利用多机的计算资源，从而加快数据处理的速度。目前，这种并行计算的模型主要分为三大类：

一类是广泛应用于高性能计算的 MPI技术，

一类是以谷歌/雅虎为代表的互联网互联网海量数据存储和处理技术综述企业兴起的 Map/Reduce计算，

一类是微软提出的 Dryad[并行计算模型。

1）MPI

MPI 即消息传递接口（MessagePassing Interface），是一种编程接口标准，而不是一种具体的编程语言。

MPI 是一种工业标准的 API规范，专为在多处理器计算机、计算机集群和超级计算机上进行高性能计算而设计。该标准是由大量计算机供应商和软件开发商于 1994 年共同设计完成。
MPI 作为目前国际上最流行的并行编程环境之一，因其良好的可移植性和易用性、完备的异步通信功能等优点，而在机群高性能计算中得到广泛应用。在基于 MPI 编程模型中，计算任务是由一个或多个彼此间通过调用库函数进行消息收、发通信的进程所组成。绝大部分 MPI 实现在程序初始化时生成一组固定的通信进程。这些进程在不同的节点上运行（通常一个处理器一个进程） ，执行着相同或不同的程序，以点对点通信或者集合通信的方式进行进程间交互，共同协作完成同一个计算任务。
以任务之间的消息传递驱动的 MPI，其进行大规模数据处理的基本思路就是，将任务划分成为可以独立完成的不同计算部分， 将每个计算部分需要处理的数据分发到相应的计算节点分别进行计算，计算完成后各个节点将各自的结果集中到主计算节点进行结果的最终汇总。

2） MapReduce

MapReduce是谷歌在 2004 年提出的应用于大规模集群进行大规模数据处理的并行计算模型。Map（映射）和 Reduce（化简）的概念，以及他们的主要思想，都来自于函数式语言。
在一个计算任务中，计算被抽象并简化成为两个阶段：Map 和 Reduce。Map 阶段，系统调用用户提供的 Map 函数，完成从一组键值到新一组键值的映射计算；而 Reduce 阶段，用户指定的 Reduce 函数则被用来将所有 Map 计算完成的结果进行一次化简归约。与 MPI 有所不同的是，Map/Reduce 是通过将计算（Map 或者Reduce）分发到相应的数据存储节点或靠近的节点，让计算（Map 或者 Reduce）在数据存储节点就地或者就近完成，尽可能减轻大量数据在网络上传输所产生的压力。

详细文档：

谷歌三大核心技术（二）Google MapReduce中文版

3）Dryad

Dryad 是微软在 2007 年提出的数据并行计算模型。目前已经在 Microsoft Ad’Center 投入使用。 与 MapReduce的思路类似， Dryad 也是通过将计算任务移动到相应的数据存储节点或靠近的节点，让计算就地或者就近完成，从而减轻网络上传输的压力。 在 Dryad 中，每个计算任务被表示成一个有向无环图（Directed Acyclic Graph, DAG） ，计算任务按照有向无环图的方向按照依赖关系执行。DAG 相对于两阶段式的 MapReduce，可以表达更加丰富的计算类型；同时，它支持在子任务之间通过 TCP管道、Shared-memory FIFOs（共享内存先进先出）进行结果传递，尽量避免一些不必要的磁盘输入输出，加速计算的执行。

如果从数据结构和算法来考虑处理海量数据：

1. Bloom Filter
2. Hash统计和映射
3. Bit-Map
4. 堆(Heap)/快速/归并排序
5. 双层桶划分
6. 数据库索引
7. 倒排索引（Inverted Index）
8. 外排序
9. Trie树

这些都是针对特定场景,如在大量数据中（1千万以上）中,选出最大的k个数或者是频率最高的前k条文本数据等。