Big-Data-A-Survey 论文阅读分享

Posted on | In

《Big Data: A Survey》论文阅读分享
2018-08-18
liyakun.hit

论文信息：Mobile Networks and Applications，April 2014, Volume 19, Issue 2, pp 171–209

概述

  • 大数据技术所处位置：与云计算、IOT、数据中心和Hadoop的关系
  • 大数据生命周期：产生、获得、存储、分析
  • 典型应用场景：企业管理、IOT、社交网络、医疗、集体智慧、智能电网

相关技术

大数据与云计算

  • 云计算改革了IT基础架构，大数据则影响了商业决策，云计算是大数据能平滑扩展的保证
  • 云计算的目标用户是CIO(首席信息官)，大数据的目标用户是CEO

大数据与IOT

IOT(物联网)丰富的终端产生了大量的半结构、非结构化数据，这些数据只有被拿来分析才有价值

  • IOT为大数据带来了很好的应用场景
  • 大数据技术在IOT中的应用也加速了IOT的研究进展和商业模式。

大数据与数据中心

  • 大数据需要数据中心提供强有力的支持：容量、带宽、散热等
  • 大数据加速了数据中心的革命和创新，一些独特的大数据架构，促进了数据中心的存储，网络技术开发。
  • 大数据希望数据中心提供更多的软实力支持，如数据获取、加工、分析与应用

大数据与Hadoop

Hadoop是工业界应用最广泛的大数据应用

大数据生命周期

数据产生

  • 企业数据
  • IOT数据
  • 生物医学数据
  • 其它学科中产生的数据：天文学等等

数据获取

数据采集

  • 日志文件
  • 传感器数据
  • 获取网络数据：
    • 基于Libpcap的数据包捕获技术：被广泛使用的函数库
    • Zero-copy数据包捕获技术：全程绕过内核与CPU
      • 发送时：数据从用户进程，直接通过网卡进入网络
      • 接收时：网卡直接把数据送给用户进程
  • 移动设备收集：IOS，Android

数据传输

  • 跨数据中心传输：主要是数据进入数据中心的过程。
    • (注：对通信这块不太了解，这里只列出概念，大家可以自行搜索相关资料)
    • WDM：在光纤上进行信道复用的技术，光的频分复用
    • OFDM ：多载波传输方案的实现方式之一，采用N个重叠的子频带，子频带间正交，在接收端无需分离频谱就可将信号接收。
  • 数据中心内传输：
    • 网络拓扑结构
    • 目标：高吞吐、低延迟，低能耗
    • 挑战：网络可视化

数据预处理

  • 数据集成：数据整合，并为用户提供统一视图
  • 清洗：发现不正确、不完整、不合理的数据，通过修改或删除，提升数据质量
  • 冗余消除

数据存储

传统外挂存储系统

  • DAS: Direct Attached Storage，将存储设备通过SCSI接口或光纤通道直接连接到一台计算机上
  • NAS: Network Attached Storage，存储设备通过标准的网络拓扑结构，连接到一群计算机上
  • SAN: Storage Area Network，通过光纤通道连接到一群计算机上，建立专用于数据存储的区域网络

分布式存储理论基础

  • CAP理论：一个分布式系统最多只能同时满足CAP三个特性中的两项。(Eric Brewer, 2000)
    • Consistency：一致性，即数据写入后，所有节点在同一时间的数据完全一致
    • Availability：可用性，服务一直可用，而且是正常响应时间
    • Partition Tolerance：区容错性，某节点或网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务
  • CA系统：不是分布式服务，比如传统的关系型数据库。或者完全不能容忍一台主机down掉的服务
  • CP系统：保证一致性，但不保证任意时间可用，如BigTable，Hbase
  • AP系统：保证可用性，同时保证最终一致性，如Dynamo，Cassandra
  • (注：绝对的A是不存在的，P是分布式的基础，所以这个理论其实是有问题的)

大数据存储机制

  • 文件系统：
    • 技术已经比较成熟，不做为重点介绍，目前工业界的系统有：GFS，HDFS，Kosmosfs，Cosmos(by微软)，Haystack(by FB)，TFS(by Taobao)，FastDFS(by ali)
  • 数据库
    • 行式kv数据库：
      • Dynamo：by亚马逊，只有论文，未开源。分区依赖一致性哈希，高可用性，保证最终一致性
      • Voldemort：by LinkedIn，开源，号称是Dynamo的开源实现。
    • 列式kv数据库：
      • BigTable：by Google，分布式结构化数据存储系统，原理，排序大表 + Column Family列式存储 + lsm(Log-Structured Merge)树，尤其适合写多读少的场景
      • Cassandra：by FB，开源，分区模仿Dynamo依赖一致性哈希，数据模型模仿BigTable使用列式存储
      • HBase：Hadoop生态圈中的一员，BigTable的Java开源实现。
      • Hypertable：by Zvents，开源，BigTable的C++开源实现。
    • 文档型kv数据库：
      • MongoDB：by MongoDB，开源，c++，存储Value是Binary JSON对象。可以配置为CP(默认)，或AP
      • SimpleDB：by亚马逊，不开源，不支持自动的partition，最终一致
      • Couchbase：by Apache，Erlang，存储value是JSON对象，最终一致
    • 关系型数据库(支持跨行事务)：
      • Spanner/f1：by Google，不开源，share nothing，兼容SQL语法，跨行事务，CP系统
      • Aurora：by亚马逊，不开源，共享存储，兼容mysql语法，跨行事务，CP系统
      • TiDB：by PingCAP，号称是Spanner的开源实现，但是事务模型不同，share nothing，兼容mysql语法，跨行事务，CP系统。
      • CockroachDB：号称是Spanner的开源实现
      • (注：论文中把数据库分成了三类：行式、列式、文档型，结合最新的成果，我在这里又添加了关系型数据库。个人认为Google，亚马逊是这个领域的先驱，在kv时代两者分别提出不同的解决方案，在关系型时代，又分别提出了不同的解决方案。)
  • 编程模型
    • MapReduce:
      • 这个模型只提供两个函数给用户编程，分别是map和reduce，由框架来负责将原始数据切分并分别进行map运算，然后再将map的结果重新组织(shuffle)到各个reduce函数，最终由reduce产生输出结果。
      • 由于map和reduce是两个非常基础的方法，复杂的程序设计中，需要花费大量的时间来设计如何调用这两个方法，因此，在mr的基础上，出现了一些高级一点的封装：
        • Sawzall by Google, Pig Latin by Yahoo，Hive by Facebook，Scope by 微软
    • Dryad：
      • by微软，通过DAG把多个MR串联起来，学院派产物。可以重点关注一下Spark。
    • Spark:
      • by MIT，工业级的Dryad，目前最活跃的大数据的计算模型。
      • 基于DAG把MR串起来，在需要shuffle的地方划分为两个不同的stage，在stage内是并行计算的，在stage间是串行的。
      • 在自己的内核外层同时封装了SQL、Streaming(流式计算)、MLlib(机器学习)、GraphX(图数据)等类库，生态完整。
    • All-Pairs：
      • 主要应用在生物特征、生物信息学和数据挖掘应用。给定SetA SetB FuncA，All-Pairs能给出两个集群中的任意点求FuncA的结果矩阵。
      • 共分为两步，第一步使用一个近似模型来对数据分区，第二步把数据流动到指定节点后，分批次的在各个节点上进行运算。
    • Pregel：
      • by Google，图计算模型，不开源。
      • 先把图构建好了，然后把计算划分为超步(类似stage)，单个超步内是并发计算的，超步之间是串行的。每个节点在一个超步结束时，可能会改变自己的状态、或自己的边的状态。
    • Dremel:
      • by Google，不开源。
      • 解决大规模交互数据分析的实时性问题，适合数据读取数据量大，但是返回数据量小的场景，宣称可以在3秒钟的时间处理1PB数据。
      • 列式存储+自定义的SQL语法
    • (注：论文中并没有提到Spark,Dremel，因为Spark算是当红炸子鸡，所以必须要讲一下。Dremel是Google的分布进化中很重要的一步，在这里介绍一下Google的分布式计算进化历程：
      • 从MapReduce(对应开源MapReduce)开始，提供了一种从分布式文件系统中读取并处理的解决方案。
      • 接着提出了BigTable(对应开源Hbase)，在分布式文件系统上面简单的包装了一个KV数据库。
      • 接着又提出了Dremel(对应开源的Impala/drill)，依靠自定义的存储结构和定制的SQL，在返回数据量小的场景在比MR快几个数量级)，但是其实可以把它看做一个高度定制优化的MR。
      • 然后又提出了Spanner/f1(对应开源的TiDB)，主要背景是分布式理论实践(尤其是paxos\raft)储备就绪，向难度更高的跨行事务发起了挑战。
      • 可以说，整个分布式计算的进程基本是由Google来提出问题，并指引方向（当然，亚马逊在后面也提出一些独特解决问题的方法)。

数据分析

传统分析

  • 聚类
  • 因子分析：指研究从变量群中提取共性因子的统计技术
  • 相关性分析
  • 回归分析：是一种揭示一个变量和几个其他变量之间相关性的数学工具。
  • A/B测试
  • 统计分析：提供大数据的描述和推断，广泛应用于经济领域
  • 各种各样的数据挖掘算法

大数据分析

  • 大数据时代的工具知识点
    • Bloom Filter
    • 哈希
    • 索引
    • 字典树(Triel)
    • 并行计算(比如，MPI, MR, Spark, Flink)
  • 常见数据挖掘分析工具
    • R语言
    • Excel
    • Rapid-I Rapidminer
    • KNMINE
    • Weka/Pentaho
    • tableau
    • qlikview
  • 实时和离线分析
    • 实时计算：主要应用在电子商务和财经系统中，常见的解决方案有：
      • 使用并行的传统关系型数据库组成，Greenplum by EMC，已经开源
      • 使用纯内存的计算平台，HANA by SAP，商业软件，很贵
      • (注：论文里面介绍到此处，是想描述一些类似于传统事务型的数据的大数据支持场景，如果是这种场景，其实还应该包含，Spanner/f1，Aurora，TiDB)
      • (注：其实大数据圈子里面，还有另一个实时计算(流式计算)的概念，跟上面的概念不同，主要是解决大量数据的流动，以及流动过程中的计算问题，典型的流式计算组件有：storm，flink，都是开源的，其中Flink被认为是取代storm的产品，目前阿里在这个产品上投入了非常多的人力)
    • 离线计算：主要应用在机器学习、统计、推荐系统中，常见的解决方案有：
      • Hadoop，这个已经很成熟了不多介绍。
      • Scribe，by FaceBook，开源的日志收集系统
      • Kafka，by LinkedIn，开源消息中间件
      • Timetunnel，by Taobao，开源，基于thrift通讯框架搭建的实时数据传输平台
      • Chukwa，by Apache，开源日志收集处理平台，hadoop生态

大数据典型应用

  • 方向
    • 驱动应用程序的进化：商业应用、网络应用、科研应用
    • 结构化数据分析
    • 文本数据分析
    • 互联网数据分析
    • 多媒体分析
    • 图数据分析
    • 移动数据分析
  • 典型场景
    • 企业级数据分析
    • IOT应用
    • 社交网络
    • 医疗健康应用
    • 集体智慧：众包, 如Amazon Turk
    • 智能电网