第9讲 流式计算与图数据计算.pptx

第9讲流式计算与图数据计算莫同motong@ss.pku.edu.cn

上一讲回顾引言并行化思想MapReduce批量计算特点架构代码实例算法调优MapReduce批量计算引言MapReduce算法调优

内容提要1流式计算2图数据计算

内容提要1流式计算2图数据计算

流式计算数据流一系列动态数据的集合体例如计算机网络传输的若干数据包数据流特点微观上有独立的组成单元（例如一个数据包）宏观上呈现流的特点实时性随时间不断到来具有一定的次序

流式计算典型应用领域交通证券银行购物网站系统运维日志物联网…

流式计算流式处理的典型结构流的处理，核心是一个管道/线路的拓扑结构设计类比：流水线

流式计算批量计算batchcomputing与流式计算streamcomputing的对比批量计算离线计算、存在延时先将数据保存起来，然后处理用户驱动计算请求拉式获取计算结果流式计算实时计算、延时较少来一个处理一个数据驱动计算请求推式获取计算结果

流式计算两种数据处理方式的特点

流式计算流式计算与批量计算的核心区别实时性，来一个处理一个主要挑战处理速度与数据到来速度的匹配保障数据的顺利流动处理逻辑的表示...

流式计算流式计算：各处理节点的拓扑结构每个节点的作用连接关系（数据流向）

流式计算示例——wordcount统计聊天记录中各个词出现的次数HelloworldHelloworldHello 12world 13HelloworldGoodHelloGoodBolt2Bolt1Spout

流式计算示例——wordcount统计聊天记录中各个词出现的次数有什么问题？来的速度太快如何提高分词节点效率HelloworldHelloworldHello 12world 13HelloworldGoodHelloGoodBolt2Bolt1Spout

流式计算增加分词节点个数核心在于分发策略我受不了了！发牌式分发HelloworldHello 12world 13HelloworldGoodHelloGoodHelloworldGoodHelloGoodBolt2Bolt1bSpoutBolt1aBolt1c

流式计算增加统计节点个数注意分发策略的区别HelloworldHelloworldGoodHelloGood…HelloworldGoodGoodHelloHelloworldGoodHelloGoodBolt1bSpoutBolt1aBolt1cBolt2bBolt2aBolt2c

流式计算分发策略随机分发/发牌式分发按特定值分发广播分发（每个包会分发给所有的节点）…

流式计算分发策略设置原则核心目的是为了解决节点处理压力问题将单一节点的处理压力分散到多个节点上关键是如何保证流经多个节点与流经一个节点的处理逻辑不变

流式计算流式计算技巧增加前序节点，在处理前对数据进行某种转换前序节点可以起到限流、过滤、变换等作用前序节点

流式计算流式计算技巧增加功能相同的节点，使用随机分发各节点处理逻辑相同，仅需保证数据量的均衡分配，采用发牌式分发

流式计算流式计算技巧将处理功能分散，使用特定值分发各节点负责处理的内容不同，把满足不同条件的内容分发到相应的节点上A开头的B开头的C开头的

流式计算流式计算技巧如果多个后续节点都需要同一个数据，可以设置一个专门的数据转发节点，使用广播分发发给这些后续节点广播节点实际上起到了数据复制的作用，使得同一份数据进入不同的管道

流式计算流式计算技巧某些节点可以作为同步节点，接收到来自多个上游的数据后触发下一个步骤同步节点实际上起到了数据开关的作用，控制管道开关

流式计算流式处理流程数据采集：获取数据数据计算：处理数据数据查询：提供结果

流式计算典型框架Twitter的StormYahoo的S4Facebook的DataFreewayandPumaLinkedin的KafkaMicrosoft的TimeStreamHadoop之上的数据分析系统HstreamingIBM的StreamBase…

内容提要1流式计算2图数据计算

图数据计算什么是图揭示对象与关系的一种抽象数学表达ABCD哥尼斯堡七桥示意图

图数据计算典型的图论问题一笔画问题四色问题六度空间理论关键路径问题…

图数据计算图的数学抽象定义1一个有序二元组(V,E)称为一个图,记为G=(V,E),其中V称为G的顶点集,V≠?,其元素称为顶点或结点,简称点E称为G的边集,其元素称为边,它联结V中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边如果V={v1,v2,…,vn}是有限非空点集,则称G为有限图或n阶图

图数据计算案例