分布式编程模型的设计和演化

阿里大数据平台核心技术_笔记3

分布式编程模型的设计和演化

• 数据格式和抽象

  • 概要
    
    • 编程模型指编程的方式，不特指某种编程语言
    • 命令式编程 vs. 声明式编程
    • 编程模型 vs. 系统实现
  • 例子
    
    • 命令式Python,声明式SQL
  • 数据
    
    • 结构
      
      • 关系型数据
      • 树形数据(JSON…)
      • 矩阵数据
      • 图数据
    • 非结构
      
      • 图片、音频、视频等

• 分布式编程模型

  • 关系型数据
    
    • Table
    • Relation –apache pig
    • PCollection,PTable –Google Dataflow
    • RDD –Spark
  • 需求
    
    • 处理大数据量 TB-PB
    • 处理多种数据格式
    • 高效率
    • 尽可能多的利用分布式集群中的CPU、内存和磁盘
    • 对用户隐藏底层存储(盘古)和调度(伏羲)的细节
  • 数据为中心的编程模型 –高级语言，原来的c++、java则相当于汇编
  • 在线数据应用(OLTP) vs. 离线数据计算(OLAP)

• MapReduce编程模型
  MapReduce对输入数据的格式要求比较灵猴，可以是关系形数据，也可以其他。

  • 编程思想来自于函数式编程
  • 用户实现两个函数接口
    
    • Map
      
      • 一对一 (key,value)
      • 一对多 list(key,value)
      • 一对零 进行过滤操作
    • Reduce
      
      • (key,)->list(key,value),是将同一个key以及对应的一组value，映射到一组新的key和value
  • 实现
    
    • Google MapReduce(起源，2004)
    • Hadoop MapReduce (开源实现)
    • ODPS MapRedcue

  • 例子

    • Map

      public void map(LongWritable key, Text value, OutputCollector<Text, IntWritable> output, Reporter reporter) throws IOException {
               String line = (caseSensitive) ? value.toString() : value.toString().toLowerCase();
    
               for (String pattern : patternsToSkip) {
                 line = line.replaceAll(pattern, "");
               }
    
               StringTokenizer tokenizer = new StringTokenizer(line);
               while (tokenizer.hasMoreTokens()) {
                 word.set(tokenizer.nextToken());
                 output.collect(word, one);
                 reporter.incrCounter(Counters.INPUT_WORDS, 1);
               }
    
               if ((++numRecords % 100) == 0) {
                 reporter.setStatus("Finished processing " + numRecords + " records " + "from the input file: " + inputFile);
               }
             }
           }
    

    • Reduce

     public static class Reduce extends MapReduceBase implements Reducer<Text, IntWritable, Text, IntWritable> {
         public void reduce(Text key, Iterator<IntWritable> values, OutputCollector<Text, IntWritable> output, Reporter reporter) throws IOException {
           int sum = 0;
           while (values.hasNext()) {
             sum += values.next().get();
           }
           output.collect(key, new IntWritable(sum));
         }
       }

  • 特点

    • 并发性

      • 数据自动切分，多任务(task)运行，负载均衡
      • Map任务依赖于输入数据(data split对应与盘古文件系统的chunk)
      • 任一Map/Reduce任务都可以独立运行

    • 容错

      • 分布式文件系统的数据有副本(replication)
      • Map/Reduce任务都可以重新启动，不影响结果
      • Master节点监控到任务失败，可在另外的机器重启

    • 数据本地化

      • 把Map任务启动到输入数据所在机器上(利用伏羲调度的功能)

    • MapReduce应用场景

    • 日志分析和流量统计
      
      • Apache日志，广告点击日志，搜索日志
      • 访问来源分析，广告点击消耗统计
    • 商业数据分析
    • 机器学习和数据挖掘
      
      • 相关推荐
      • 协同过滤算法

    • 分布式索引

      • 网页索引(Google的最早应用场景)

    • 扩展MapReduce

    • 传统MapReduce模型
      Map->Reduce |Map->Reduce | Map->Reduce
    • Hadoop ChainedMapper&ChainedReducer
      (Map->Map)->(Reduce->Map) | ->(Map)->(Reduce)
    • ODPS MapRedcue Pipeline
      Map->Reduce->Reduce

• 关系型数据编程模型

  • 关系型数据计算模型

    • 数据源是关系型数据：Table,Relations,PCollection,RDD,…
    • 相关编程语言：FlumeJava(Crunch),Cascading,Pig,Spark等
    • Google FlumeJava primitive operations
      parallelDo,groupByKey,flatten
    • Cascading Pipes
      Each,GroupBy,Every,CoGroup
    • Pig Latin Operators –DSL邻域专用语言
      FOREACH,GROUPBY,JOIN,FILTER,ORDER…BY

  • 实现
    编程接口层(Pig,MapRedcue API,SQL)->执行计划->执行引擎(Spark,MapReduce,Tez)

  • 特点
    
    • 包含基本的编程算子(Operator/Primitives)
    • 各类编程框架可以相互转化
    • 甚至一套编程框架可以用另外一套来实现
    • DSL语言(SQL.Pig) vs. 通用语言(Spark.Cascading)
    • 编程模型简单，只需要关注数据格式及数据间的关系
    • 容错、并发、数据本地化

• 分布式图计算模型

  • BSP计算模型

    • 特点
      
      • 并发计算，计算任务分成多个计算单元(进程)
      • 计算单元之间可以相互通讯
      • 定期同步点(Barrier synchronisation)
    • BSP程序由超步(Superstep)组成,超步间垂直关系，超步内进程并发水平
      
    • 超步分为三个阶段
      
      • 本地计算阶段：计算单元只对本地内存中的数据做计算
      • 全局通讯阶段：数据交换
      • 珊栏同步阶段
    • BSP计算模型场景
      
      • 多轮迭代的运算，数据都可以保存在内存里
      • 数据本地化要求高：可以提升性能
      • 简单的编程模型:更加灵活的数据处理方式
      • 同步模型:不会产生死锁，简化编程
    • 优点：通用的BSP框架解决了容错、负载均衡等问题
    • 缺点
      
      • 栅栏同步开销较大,需要大量的通讯
      • 计算单元间可能存在数据不均衡

  • ODPS Graph

    • 计算框架
      
      • 参考Google 论文Pregel实现
      • 以顶点(Vertex)为中心的API设计

    • Graph Job的生命周期
      ODPS表-加载->图—数据分片，n轮迭代计算->结果图-输出->ODPS表

    • 特点

      • 性能
        
        • 有状态（在内存中）
        • 只有输入、输出和Checkpoint会写磁盘
      • 并发性
        
        • 运算过程不需要锁和信号量
        • 每个迭代阶段内计算隔离，计算并发
      • 容错性
        
        • 通过Checkpoint,每个迭代阶段前可持久化数据
        • Master和worker之间心跳联系
  • 其他图计算
    
    • Mahout:Graph on MapReduce
    • Neo4j:图数据库，单机版
    • GraphLab:基于MPI实现，API较为复杂
    • GraphChi:单机版，性能强大
    • GraphX:Spark上的图计算框架，扩展RDD的算子

• 未来展望

  • 离线计算到实时计算
    
    • 更加实时的引擎：Spark,Tez,Impala等
    • 批量计算到流式计算：Pig on Storm
    • 编程模型的融合：关系型，图计算，迭代算法等.Spark:Spark SQL,GraphX,Spark Streaming