云计算之分布式计算

内容 背景 分布式计算 批量计算(非实时计算) 实时计算 技术趋势

内容 背景 分布式计算 批量计算(非实时计算) 实时计算 技术趋势

大数据时代 移动互联网时代 物联网 互联网 移动互联网 信息时代 早期：Google 现在：Facebook 未来：？？

2009年加州大学研究报告《多少信息？》 大数据时代 34GB：2008年每个美国人每天平均信息消费 12TB： 2008年每个美国人平均年信息消费总量 3.6ZB：2008年美国人年信息消费总量

2011年IDC研究报告《 Extracting Value from Chaos 》 大数据时代 2011年IDC研究报告《 Extracting Value from Chaos 》 1.8ZB：2011年全球被创建和被复制的数据总量 50%：数据年增长率 2年：数据量翻番

大数据时代 2012年《纽约时报》称“大数据时代”已经降临，决策行为将日益基于数据和分析而作出，而并非基于经验和直觉。这不是简单的数据增多的问题，而是全新的问题。

分布式环境

内容 背景 分布式计算 批量计算(非实时计算) 实时计算 技术趋势

Google 批量处理 增量处理（准实时计算） MapReduce：海量数据离线计算框架 Pregel：迭代计算框架 Percolator：数据增量更新系统 Dremel：数据分析系统 Tenzing：SQL查询引擎

Google & Apache Google Apache 文件系统 GFS HDFS 分布式数据库 BigTable HBase 批量计算框架 MapReduce 迭代计算框架 Pregel Hama SQL查询引擎 Tenzing Hive

查询引擎：Tenzing/Hive 计算框架：MapReduce/ Pregel/Hama 数据管理：BigTable/HBase Google & Apache 查询引擎：Tenzing/Hive 计算框架：MapReduce/ Pregel/Hama 数据管理：BigTable/HBase 数据存储：GFS/HDFS

离线计算——Google 数据： PB量级 应用：数以百计 爬虫文档 Web日志 倒排索引 问题 计算并行 数据分发 错误处理

离线计算——Google 2003年Google提出MapReduce批量计算框架 抽象模型 Map Reduce 用户只需要考虑如何对数据进行逻辑处理，而不需要考虑以下细节： 并行化 容错 数据分布 负载均衡

MapReduce工作流程 统计天气预报中每个字出现的次数 Master Slave Slave Slave 昨天 小雨转多云 今天 多云转阵雨 明天 小雨转中雨

MapReduce工作流程 Master Map计算 处理昨天的 处理今天的 处理明天的 Slave Slave Slave 小 1 雨 1 小 1 雨 1 转 1 多 1 云 1 多 1 云 1 转 1 阵 1 雨 1 小 1 雨 2 转 1 中 1 昨天 小雨转多云 今天 多云转阵雨 明天 小雨转中雨

MapReduce工作流程 Master Reduce计算划分 统计“小” “中”“多” 统计“雨” “云” 统计“转” “阵” Slave 小 1 雨 1 转 1 多 1 云 1 多 1 云 1 转 1 阵 1 雨 1 小 1 雨 2 转 1 中 1

MapReduce工作流程 Master Reduce数据传输 多 1 小 1 中 1 雨 2 转 1 阵 1 小 1 多 1 雨 1 多 1 小 1 中 1 雨 2 转 1 阵 1 小 1 多 1 雨 1 云 1 转 1 云 1 雨 1 Slave 转 1 Slave Slave 雨 1 云 1 多 1 雨 2 转 1 阵 1 小 1 中 1 转 1

MapReduce工作流程 Master 任务完成 Reduce计算 统计任务 完成 统计任务 完成 统计任务 完成 Slave Slave 小 1，1 多 1，1 中 1 小 2 多 2 中 1 云 1，1 雨 1，1，2 云 2 雨 4 转 1，1，1 阵 1 转 3 阵 1

并行定理 Amdahl’s Law: 对于工作量为1的问题，若子问题的最大工作量为f，那么并行加速比不超过1/f。 洗开水壶 (1分钟) 洗茶壶 (3分钟) 拿茶叶 (2分钟) 泡茶 (2分钟) 烧开水 (15分钟) 洗茶杯 (2分钟)

并行定理 Amdahl’s Law: 对于工作量为1的问题，若子问题的最大工作量为f，那么并行加速比不超过1/f。 1+15+2=18分钟 洗开水壶 (1分钟) 烧开水 (15分钟) 洗茶壶 (3分钟) 泡茶 (2分钟) 洗茶杯 (2分钟) 1+15+2=18分钟 拿茶叶 (2分钟)

并行定理 Gustafson’s Law: 解决问题的时间是存在界限的，但是在这个时间内可以通过增加处理单元处理多个同类问题，加速比与处理器数目近似线性关系.

技术分析 Perfect：搜索类80%的计算 缺点：处理有向图模型的算法效率很低 有向无环图 迭代模型 执行2 执行1 执行4 执行3

迭代计算——Google 迭代计算 PageRank计算 图遍历 最短路径

2010年Google推出Pregel迭代计算框架 BSP模型 显示同步模型 SuperStep 计算与通讯分离

Pregel工作流程 Node1 Node4 Node3 6 1 9 Node5 Node2 5 3 Node7 Node6 4 6

Pregel工作流程 选取图中权值最大的节点作leader Master Slave Slave Slave

Pregel工作流程 N4 N3 N1 9 Step0：计算 1 6 3 N2 4 5 N6 N7 6 N5 Master 处理Node1，2，3 N6 N7 6 N5 处理Node4，5 处理Node6，7 Slave Slave Slave Node1：[6] （4，5，7） Node2：[3] （3，6） Node3：[9] （2，4） Node4：[1] （1，3，5） Node5：[5] （1，4，6，7） Node6：[6] （2，5） Node7：[4] （1，5）

Pregel工作流程 N4 N3 N1 9 Step0：通信 1 6 3 N2 4 5 N6 N7 6 N5 Master Node2：9 （4，5，7） Node2：[3] （3，6） Node3：[9] （2，4）

Pregel工作流程 N4 N3 N1 9 Step0：通信 1 6 3 N2 4 5 N6 N7 6 N5 Master Node4：5 （1，3，5） Node5：[5] （1，4，6，7）

Pregel工作流程 N4 N3 N1 9 Step0：通信 1 6 3 N2 4 5 N6 N7 6 N5 Master Node1：4 （2，5） Node7：[4] （1，5）

Pregel工作流程 N4 N3 N1 9 Step1：计算 1 6 3 N2 4 5 N6 N7 6 N5 Master Node1：1，4，5 Node2：6，9 Node3：1，3 Node4：5，6，9 Node5：1，4，6，6 Node6：3，5 Node7：5，6 Node1：[6] （4，5，7） Node2：[3] （3，6） Node3：[9] （2，4） Node4：[1] （1，3，5） Node5：[5] （1，4，6，7） Node6：[6] （2，5） Node7：[4] （1，5）

Pregel工作流程 N4 N3 N1 9 Step1：计算 1 6 3 N2 4 5 N6 N7 6 N5 Master Node1：1，4，5 Node2：6，9 Node3：1，3 Node4：5，6，9 Node5：1，4，6，6 Node6：3，5 Node7：5，6 Node1：[6] （4，5，7） Node2：[9] （3，6） Node3：[9] （2，4） Node4：[9] （1，3，5） Node5：[6] （1，4，6，7） Node6：[6] （2，5） Node7：[6] （1，5）

Pregel工作流程 N4 N3 N1 9 Step1：通信 1 6 3 N2 4 5 N6 N7 6 N5 Master Node3：9 （4，5，7） Node2：[9] （3，6） Node3：[9] （2，4） Node4：[9] （1，3，5） Node5：[6] （1，4，6，7） Node6：[6] （2，5） Node7：[6] （1，5）

Pregel工作流程 N4 N3 N1 9 Step1：通信 1 6 3 N2 4 5 N6 N7 6 N5 Master Node4：6 （4，5，7） Node2：[9] （3，6） Node3：[9] （2，4） Node4：[9] （1，3，5） Node5：[6] （1，4，6，7） Node6：[6] （2，5） Node7：[6] （1，5）

Pregel工作流程 N4 N3 N1 9 Step1：通信 1 6 3 N2 4 5 N6 N7 6 N5 Master Node1：6 （4，5，7） Node2：[9] （3，6） Node3：[9] （2，4） Node4：[9] （1，3，5） Node5：[6] （1，4，6，7） Node6：[6] （2，5） Node7：[6] （1，5）

Pregel工作流程 N4 N3 N1 9 Step2：计算 1 6 3 N2 4 5 N6 N7 6 N5 Master Node1：6，6，9 Node3：9，9 Node4：6 Node5：6，9 Node6：6，9 Node7：6 Node1：[6] （4，5，7） Node2：[9] （3，6） Node3：[9] （2，4） Node4：[9] （1，3，5） Node5：[6] （1，4，6，7） Node6：[6] （2，5） Node7：[6] （1，5）

Pregel工作流程 N4 N3 N1 9 Step2：计算 1 6 3 N2 4 5 N6 N7 6 N5 Master Node1：6，6，9 Node3：9，9 Node4：6 Node5：6，9 Node6：6，9 Node7：6 Node1：[9] （4，5，7） Node2：[9] （3，6） Node3：[9] （2，4） Node4：[9] （1，3，5） Node5：[9] （1，4，6，7） Node6：[9] （2，5） Node7：[6] （1，5）

Pregel工作流程 N4 N3 N1 9 Step2：通信 1 6 3 N2 4 5 N6 N7 6 N5 Master Node7：9 （4，5，7） Node2：[9] （3，6） Node3：[9] （2，4） Node4：[9] （1，3，5） Node5：[9] （1，4，6，7） Node6：[9] （2，5） Node7：[6] （1，5）

Pregel工作流程 N4 N3 N1 9 Step2：通信 1 6 3 N2 4 5 N6 N7 6 N5 Master Node4：9 （4，5，7） Node2：[9] （3，6） Node3：[9] （2，4） Node4：[9] （1，3，5） Node5：[9] （1，4，6，7） Node6：[9] （2，5） Node7：[6] （1，5）

Pregel工作流程 N4 N3 N1 9 Step2：通信 1 6 3 N2 4 5 N6 N7 6 N5 Master Node2：9 （4，5，7） Node2：[9] （3，6） Node3：[9] （2，4） Node4：[9] （1，3，5） Node5：[9] （1，4，6，7） Node6：[9] （2，5） Node7：[6] （1，5）

Pregel工作流程 N4 N3 N1 9 Step3：计算 1 6 3 N2 4 5 N6 N7 6 N5 Master Node1：9 （4，5，7） Node2：[9] （3，6） Node3：[9] （2，4） Node4：[9] （1，3，5） Node5：[9] （1，4，6，7） Node6：[9] （2，5） Node7：[6] （1，5）

Pregel工作流程 N4 N3 N1 9 Step3：计算 1 6 3 N2 4 5 N6 N7 6 N5 Master Node1：9 （4，5，7） Node2：[9] （3，6） Node3：[9] （2，4） Node4：[9] （1，3，5） Node5：[9] （1，4，6，7） Node6：[9] （2，5） Node7：[9] （1，5）

Pregel工作流程 N4 N3 N1 9 Step3：通信 1 6 3 N2 4 5 N6 N7 6 N5 Master Node1：9 （4，5，7） Node2：[9] （3，6） Node3：[9] （2，4） Node4：[9] （1，3，5） Node5：[9] （1，4，6，7） Node6：[9] （2，5） Node7：[9] （1，5）

Pregel工作流程 N4 N3 N1 9 Step4：计算 1 6 3 N2 4 5 N6 N7 6 N5 Master Node1：9 （4，5，7） Node2：[9] （3，6） Node3：[9] （2，4） Node4：[9] （1，3，5） Node5：[9] （1，4，6，7） Node6：[9] （2，5） Node7：[9] （1，5）

Pregel工作流程 N4 N3 N1 9 Step4：通信 1 6 3 N2 4 5 N6 N7 6 N5 Master Node1：[9] （4，5，7） Node2：[9] （3，6） Node3：[9] （2，4） Node4：[9] （1，3，5） Node5：[9] （1，4，6，7） Node6：[9] （2，5） Node7：[9] （1，5）

Pregel工作流程 计算结束 Master 任务完成 Node1：[9] （4，5，7） Node2：[9] （3，6） （2，4） Node4：[9] （1，3，5） Node5：[9] （1，4，6，7） Node6：[9] （2，5） Node7：[9] （1，5）

算法的有向无环图（DAG）模型 技术分析 T1 T5 T2 T7 T3 T6 T4 T1.a1 = T2.b1 T5.e1 = T6.f1 T3.c1 = T4.d1 T6 T4

微软Dryad Dryad：DAG模型计算平台 2009年公布学术版 2010年公测 2011年放弃，转投Hadoop

Dryad工作流程 （T1 join T2） join （T3 join T4） Master Slave Slave Slave

Dryad工作流程 Master 处理T1 join T2 处理T1 join T2 处理T3 join T4 Slave Slave 数据传输 数据传输

Dryad工作流程 Master 处理T5 join T6 处理T5 join T6 处理T5 join T6 Slave Slave 数据传输 数据传输

Dryad工作流程 Master 任务完成 Slave Slave Slave

总结 3类模型 简单模型：MapReduce 迭代模型：Pregel DAG模型：Dryad

内容 背景 分布式计算 批量计算(非实时计算) 实时计算 技术趋势

SQL查询引擎：借鉴于Hive Google——Tenzing 反应时间：~秒 编译：MR执行计划 优化：MR框架 工作过程：同MR 查询引擎：Tenzing/Hive 计算框架：MapReduce/ Pregel/Hama 数据管理：BigTable/HBase 数据存储：GFS/HDFS

编程模型：DAG模型（topology） FaceBook——Storm 实时计算系统 分布式的 容错 编程模型：DAG模型（topology） 点：bolt 边：stream

Storm工作流程 Master 书籍推荐 topology Slave Slave Slave

Storm工作流程 Master 解析用户行为bolt1 处理用户行为bolt2 处理用户行为bolt3

Storm工作流程 Master 发生异常行为 输出 输入 发生书籍购买 Bolt1 Bolt2 用户行为解析 Bolt3 书籍购买处理 异常行为处理

Storm工作流程 Master A买了一本《C++编程入门》 Bolt1 用户行为解析 Bolt2 书籍购买处理 Bolt3 异常行为处理

Storm工作流程 Master 《C++编程入门》 Bolt1 用户行为解析 Bolt2 书籍购买处理 Bolt3 异常行为处理

Storm工作流程 Master Bolt1 用户行为解析 Bolt2 找到跟《C++编程入门》相关的书籍《C++编程实例》 Bolt3 异常行为处理

Storm工作流程 Master 《C++编程实例》 Bolt1 用户行为解析 Bolt2 书籍购买处理 Bolt3 异常行为处理

Storm工作流程 Master A又买了一本《C++编程入门》 Bolt1 Bolt2 用户行为解析 Bolt3 书籍购买处理 异常行为处理

Storm工作流程 Master 是不是买错了? Bolt1 用户行为解析 Bolt2 书籍购买处理 Bolt3 异常行为处理

Yahoo——S4 P2P实时计算系统 分布式的 编程模型：DAG模型 点：PE 边：XML配置文件

S4工作流程 解析用户行为bolt1 处理用户行为bolt2 处理用户行为bolt3

S4工作流程 发生异常行为 输出 输入 发生书籍购买 Bolt1 用户行为解析 Bolt2 书籍购买处理 Bolt3 异常行为处理

总结 分布式流计算刚刚起步 模型相似：DAG 细节存在差异：配置、通信

内容 背景 分布式计算 批量计算(非实时计算) 实时计算 技术趋势

大数据时代才刚刚开始 数据=价值 Google已经先行一步 群雄逐鹿 互联网、移动互联网、物联网 企业云、私有云、公有云 数据的价值随着时间的流逝而降低 Google已经先行一步

胜者为王 趋势 模型： DAG 应用：简洁 效率：高 功能：强大