大数据技术概览

             应导师要求研读一些论文。个人感觉这篇论文为我们面临的大数据一些关键技术做了比较全面权威的综述。我把其中一些关键地方做个笔记。

     1.当前大数据带来的变革 

       图灵奖获得者、著名数据库专家Jim  Gray博士观察并总结人类自古以来，在科学研究上，先后历经了实验、理论和计算３种范式．当数据量不断增长和累积到今天，传统的３种范式在科学研究，特别是一些新的研究领域已经无法很好地发挥作用，需要有一种全新的第４种范式来指导新形势下的科学研究．基于这种考虑，Jim  Gray提出了一种新的数据探索型研究方式，被他自己称之为科学研究的“第４种范式”（The  Fourth  Paradigm)。以下是科学发现的四种范式：

    

   2 .大数据处理框架

      分为流处理（直接处理）和批处理（先存储后处理）两种。

     2.1  流处理

特点： 数据持续到达，速度快，规模巨大，不会对数据永久存储，由于数据环境不断变化导致难以掌握整个数据的全貌。

  代表性的开源系统：

     Twitter的Strom :（开源源码）https://github.com/nathanmarz/storm  

  （相关中文概念技术解说）http://www.ibm.com/developerworks/cn/opensource/os-twitterstorm/

http://www.cnblogs.com/aga-j/archive/2012/02/03/2337440.html

         Yahoo的  S4：   （相关概念技术）http://www./lib/view/open1328255157234.html

          Linkedin的Kafka：（比较难找，这里有一篇稍微详细全面的资料）http:///search-engine/kafka/

   2.2  批处理

           代表处理技术：MapReduce

     

核心思想：  1)  将问题分而治之。

      2）把计算推到数据而不是把数据推到计算，有效避免数据传输过程中产生的大量通信开销。 

3. 大数据的处理流程

大数据的处理流程可以定义为在合适工具的辅助下，对广泛异构的数据源进行抽取和集成，结果按照一定的标准统一存储．利用合适的数据分析技术对存储的数据进行分析，从中提取有益的知识并利用恰当的方式将结果展现给终端用户．具体来说以分为数据抽取与集成、数据分析以及数据解释。

   下图展示了标准数据处理流程。

     

    4.关键技术分析

         大数据价值的完整体现需要多种技术的协同．文件系统提供最底层存储能力的支持．为了便于数据管理，需要在文件系统之上建立数据库系统．通过索引等的构建，对外提供高效的数据查询等常用功能．最终通过数据分析技术从数据库中的大数据提取出有益的知识．

      4.1 云计算： 大数据的基础平台与支撑技术

             4.1.1 文件系统

代表：Ｇｏｏｇｌｅ自行设计开发了Google文件系统GFS(Google File System）是构建在大量廉价服务器之上的一个可扩展的分布式文件系统，ＧＦＳ主要针对文件较大，且读远大于写的应用场景，采用主从（Master-Slave）结构．通过数据分块、追加更新（append-only）等方式实现了海量数据的高效存储．随着时间推移，ＧＦＳ的架构逐渐开始无法适应需求．Google对ＧＦＳ进行了重新的设计，该系统正式的名称为Colosuss具体实现尚未公开.

         FaceBook推出了专门针对海量小文件的文件系统HayStack 通过多个逻辑文件共享同一个物理文件、增加缓存层、部分元数据加载到内存等方式有效地解决了FaceBook海量图片存储问题.

           淘宝推出了类似的文件系统TFS(Tao File System)，通过将小文件合并成大文件、文件名隐含部分元数据等方式实现了海量小文件的高效存储．FastDFS针对小文件的优化类似于TFS.

         4.1.2 数据库系统

        直接采用关系模型分布式数据库并不能适应大数据时代的数据存储，原因：（1）传统数据库更倾向于纵向扩展，横向扩展能力有限。（2）面对大数据时代多样性数据，只能处理结构化数据的传统数据库相对无力。（3）面对不同问题需要不同的数据管理，而传统数据库的 one-fits-all的设计理念难以应对。（4）数据库中事物必须满足的 ACID（原子性，一致性，隔离性，持久性）这些过于严格的约束，使其无法应用于很多大数据场景，新型 BASE（基本可用，柔性状态，最终一致）更注重数据可用性。

     应对：NoSQL（not only SQl）.  特性：1）模式自由，2）支持简易备份。3)简单应用程序接口。4）最终一致性。5）支持海量数据。

典型的NoSQL数据库一些比较：

4.1.3 索引查询技术

关系数据库也是利用对数据构建索引的方式较好地解决了数据查询的问题．不同的索引方案使得关系数据库可以满足不同场景的要求．索引的建立以及更新都会耗费较多的时间，在面对传统数据库的小数据量时这些时间和其所带来的查询便利性相比是可以接受的，但是这些复杂的索引方案基本无法直接应用到大数据之上。

NoSQL数据库针对主键的查询效率一般较高，因此有关的研究集中在NoSQL数据库的多值查询优化上．针对NoSQL数据库上的查询优化研究主要有两种思路：（1）采用MapReduce并行技术优化多值查询：当利用MapReduce并行查询NoSQL数据库时，每个MapTask处理一部分的查询操作，通过实现多个部分之间的并行查询来提高多值查询的效率．此时每个部分的内部仍旧需要进行数据的全扫描．（2）采用索引技术优化多值查询：很多的研究工作尝试从添加多维索引的角度来加速NoSQL数据库的查询速度．

一些解决方案对比：

ＩＴＨｂａｓｅ，ＩＨｂａｓｅ，ＣＣＩｎｄｅｘ 和Ａｓｙｎｃｈｒｏｎｏｕｓ　ｖｉｅｗｓ是典型的采用多个一维二级索引来加速多值查询优化的实现方案．其中ＩＴＨｂａｓｅ 和ＩＨｂａｓｅ 是两个开源的实现方案，
ＩＴＨｂａｓｅ主要关注于数据一致性，事务性是其重要特性．ＩＨｂａｓｅ与ＩＴＨｂａｓｅ类似，从ＨＢａｓｅ源码级别进行了扩展，重新定义和实现了Ｓｅｒｖｅｒ，Ｃｌｉｅｎｔ端处理逻辑．ＣＣＩｎｄｅｘ（ｃｏｍｐｌｅｍｅｎｔａｌ　ｃｌｕｓｔｅｒｉｎｇ　ｉｎｄｅｘ）是中国科学院提出的另外一种索引结构，它在索引中既存储索引项，也存储记录的其他列的数据，以便在查询时直接在索引表中通过顺序扫描找到相应的数据，大幅度减少查询时间．该方法本质是以空间代价来换取查询效率．ＣＣＩｎｄｅｘ的索引更新代价比较高，会影响系统的吞吐量．索引创建以后不能够动态增加或修改．Ａｓｙｎｃｈｒｏｎｏｕｓ　ｖｉｅｗｓ以异步视图的方式来实现非主键的查询，提出了两种视图方案：远端视图表（ｒｅｍｏｔｅ　ｖｉｅｗ　ｔａｂｌｅｓ，ＲＶＴｓ）和局部视图表（ｌｏｃａｌ　ｖｉｅｗ　ｔａｂｌｅｓ，ＬＶＴｓ）．ＲＴ－ＣＡＮ［５４］采用多维索引加速多值查询．其局部索引采用Ｒ－ｔｒｅｅ，全局索引中采用了能够支持多维查询的ＣＡＮ覆盖网络．ＱＴ－Ｃｈｏｒｄ是另一种双层索引结构，它的局部索引采用的是改进的四叉树ＩＭＸ－ＣＩＦ　ｑｕａｄ－ｔｒｅｅ，全局索引采用的Ｃｈｏｒｄ覆盖网络．ＥＭＩＮＣ针对每个局部节点建立一个ＫＤｔｒｅｅ，然后选择ＫＤ－ｔｒｅｅ的部分节点作为全局索引．每一个局部索引节点被看成是一个多个维度组成的立方体，然后在全局索引中用Ｒ－ｔｒｅｅ对这些立方体进行索引．Ａ－Ｔｒｅｅ提出了另外一种方案．基本思路是：针对每一个存储节点构建Ｒ－ｔｒｅｅ，同时创建一个Ｂｌｏｏｍ　ｆｉｌｔｅｒ（布隆过滤器）．这样在进行点查询时，首先通过Ｂｌｏｏｍ　ｆｉｌｔｅｒ进行验证，如果查询点不在其中，则不再进行Ｒ－ｔｒｅｅ查询，否则继续进行Ｒｔｒｅｅ查询．ＭＤ－ＨＢａｓｅ提出一种基于空间目标排序的索引方案．基于空间目标排序的索引方法的基本思想是：按照一定规则将覆盖整个研究区的范围划分为大小相等的格子，并给每一格网分配一个编号，用这些编号为空间目标生成一组具有代表意义的数字．其实质是将ｋ维空间的实体映射到一维空间，因此可以利用现有数据库管理系统中比较成熟的一维索引技术．ＵＱＥ－Ｉｎｄｅｘ［５９］主要针对海量物联网应用场景的时空特性，在时间维度上把数据分成当前数据和历史数据，对当前数据和历史数据进行不同粒度的索引，对当前数据，在时间段和子空间上进行索引，从而减少索引更新的次数，降低索引维护的代价，提高系统的吞吐量；对历史数据，批量地建立记录级别的索引；在建立子空间索引时，为了确保数据分布均匀，采用ＫＤ　Ｔｒｅｅ进行动态划分．但是如果所有的数据都需要经过ＫＤ　Ｔｒｅｅ来索引也会带来较高的代价，会影响数据的插入速度，因此可以对数据进行采样，对采样得到的数据利用ＫＤ　Ｔｒｅｅ进行索引，从而得到空间上的划分方案。

    4.1.4 数据分析技术

      Pregel是Google继MapReduce之后提出的又一个计算模型，与MapReduce的离线批处理模式不同，它主要用于图的计算。该模型的核心思想源于著名的BSP计算模型。Dremel是Google提出的一个适合于Web数据级别的交互式数据分析系统，通过列存储和多层次的查询树，Dremel能够实现极短时间内的海量数据分析。PowerDrill是设计用来处理少量的核心数据集，因此对数据处理的速度要求极高，所以数据应当尽可能地驻留在内存，而Dremel的数据则存储在磁盘中。

  微软提出了一个类似ＭａｐＲｅｄｕｃｅ的数据处理模型，称之为Ｄｒｙａｄ，Ｄｒｙａｄ模型主要用来构建支持有向无环图（ｄｉｒｅｃｔｅｄ　ａｃｙｃｌｉｎｅ　ｇｒａｐｈ，ＤＡＧ）类型数据流的并行程序．Ｃａｓｃａｄｉｎｇ通过对ＨａｄｏｏｐＭａｐＲｅｄｕｃｅ　ＡＰＩ的封装，支持有向无环图类型的应用．Ｓｅｃｔｏｒ?ｓｐｈｅｒｅ 可以视为一种流式的ＭａｐＲｅｄｕｃｅ，它由分布式文件系统Ｓｅｃｔｏｒ和并行计算框架ｓｐｈｅｒｅ 组成。

    处理实时数据的思路有三种：

   １）采用流处理模式．虽然流处理模式天然适合实时处理系统，但其适用领域相对有限．流处理模型的应用主要集中在实时统计系统、在线状态监控等．
    ２）采用批处理模式．近几年来，利用批处理模型开发实时系统已经成为研究热点并取得了很多成果．从增量计算的角度出发，Ｇｏｏｇｌｅ提出了增量处理系统Ｐｅｒｃｏｌａｔｏｒ，微软则提出了Ｎｅｃｔａｒ和ＤｒｙａｄＩｎｃ．三者均实现了大规模数据的增量计算，但是这些系统和ＭａｐＲｅｄｕｃｅ并不兼容，因此Ｉｎｃｏｏｐ和ＩｎｃＭＲ实现了ＭａｐＲｅｄｕｃｅ框架下的增量计算．Ｙａｈｏｏ的Ｎｏｖａ则支持有状态的增量数据计算模式．ＨＯＰ［７４］在ＭａｐＲｅｄｕｃｅ处理的过程中引入管道（ｐｉｐｅｌｉｎｅ）的概念．在保证Ｈａｄｏｏｐ容错性的前提下，使数据在各个任务间以管道的方式交互，增加了任务的并发性，提高了数据处理的实时性

   ３）二者的融合．有不少研究人员尝试将流处理和批处理模式进行融合，主要思路是利用ＭａｐＲｅｄｕｃｅ模型实现流处理。