当前课程知识点:大数据平台核心技术 > 第四讲 分布式编程模型的设计与演化 > 分布式图计算模型 > 分布式图计算模型(主讲人:吴威)
我对关系型数据
及其运算的介绍先告一段落
接下来我们要接触另一类
重要的数据结构图
一个图的结构很简单
难点是如何把图的存储分布式化
把计算也分布式化
MapReduce和关系型运算
虽然在处理关系型的数据上
非常在行
但是在图类型的数据处理上
还是有很多问题
比如因为IO的问题
导致迭代计算效率低
数据之间只能通过key
进行关联等
而图里面的边是很难表达的
我们来看图的具体结构
这是一个有向图的示例
在一个图里
最主要的是顶点和边两种对象
每个顶点都有ID号
边是顶点和顶点之间的关系
这里的边是一条有向边
它从顶点1指向了顶点2
每个顶点和边都有它们的属性
比如每一条边
可以有一个距离属性
表示两个点之间的距离
右下展示的是一个实际的图
它表示了某个支付网站的会员关系
其中的点可能是某位会员
也可能是会员登录的某台电脑
会员和会员之间
可能有朋友关系
或者转帐关系
这都可以用关系图里的边来表示
会员和电脑之间
也可能发生关系
比如Alice登录了Joe的电脑
则Alice的顶点到Joe的电脑之间
会产生一条有向边
在介绍图计算模型之前
我们需要先介绍一下
BSP计算模型
在BSP模型里
计算的任务分成多个计算单元
所以计算可以并发执行
其次计算单元之间可以相互通信
比如发送数据
或者同步各自的状态信息
最后BSP模型
还有定期同步点的概念
每个超步可分为三个阶段
第一阶段是本地计算
只对计算单元中的
内存数据做计算
第二阶段是全局通信
第三阶段是栅栏同步阶段
BSP计算模型
不仅是一种体系结构模型
也是一种设计并行程序的方法
BSP程序设计准则
是代码块之间的同步
其独特之处在于超步概念的引入
一个BSP程序同时具有水平
和垂直两个方面的结构
从垂直上看
一个BSP程序
有一系列串行的超步组成
这种结构
类似于一个串行程序结构
在一个超步中
所有的进程并行执行局部计算
这是在维基百科上
BSP模型的简化图
展示了超步的三个阶段
蓝色的竖线表示不同的计算单元
它们之间相互独立
各自进行运算
中间的通信过程
可以看到计算单元之间
两两进行数据交换
最后是同步的过程
虽然蓝线表示的计算单元运算量
或者运算速度不同
通信过程可能也会有快有慢
但是通过栅栏同步
多个计算单元的全局信息
又一致了
并且被拉回了同一个起跑线
我们来看一下同步阶段
在本地运算结束后
各个计算单元将消息传递到
其他的计算单元
但是它们的下游的计算单元
并不是直接处理这些消息
而是通过栅栏进行同步
确保所有的单元都发送完消息
并且处理完全局的信息
才让各个计算单元接收
来自其他结点的
同步前发送的信息
代码展现的是一个
BSP模型的例子
这段代码里展示的是
超步的三个阶段
我们这边代码里没有写出来
这是第一步
要做一些本地的运算
第二步
是接收或者发送
来自于邻居结点的数据
这里有While循环
对每一条消息都做了处理
处理完之后
这个bspPeer会对指定的节点
最后发送一条消息
第三步是栅栏同步阶段
在我们的代码里
就是一个bspPeer的sync操作
最后总结一下
适合BSP计算模型的场景
在多轮迭代的运算时
如果数据可以完全保存在内存里
一般用BSP模型
处理起来比较高效
同时
BSP对于数据本地化的要求很高
其次从前面的例子可以看到
BSP提供了一个简单的编程模型
可以让我们更加灵活地处理数据
最后
因为有了全局的同步
这个模型不会产生思索
简化了编程方式
另外通用的BSP框架
解决了容错
负载均衡等问题
这些都是
分布式系统里的典型问题
在BSP模型里有统一的解决方案
当然BSP模型也有缺点
比如栅栏同步开销比较大
我们需要大量的消息通信
才得到全局的同步和一致性
特别是当并发的计算单元
数目超过一千时
通信开销
可能会超过实际计算的开销
这在某些注重效率的产品下
是无法承受的
另外因为计算单元间
可能存在数据不均衡
或者因为某些结点的硬件问题
导致硬件速度变慢
可能会发生上百个结点
在空等某几个结点的情况
这会造成大量的资源浪费
这是BSP模型很难解决的问题
-主讲人:武永卫
-主讲人:程永
-QUIZ--作业
-大纲
-初步认识大数据对分布式存储系统的需求
-理解大数据对分布式存储系统的需求
-具体说明大数据对分布式存储系统的需求
-大规模分布式存储的挑战
-小概率事件-Raid卡故障
-分布式存储系统举例
-分布式存储系统重要功能设计要点剖析
-链式写正常流程
-写流程的另一种常见方式:主从模式
-链式写异常流程
-写异常处理的另一种方法-Seal and New
--写异常处理的另一种方法-Seal and New(主讲人:姚文辉)
-读正常流程
-读流程优化-BackupRead
-IO QoS
-数据正确性:checksum
-数据可靠性-Replication
-数据均衡-Rebalance
-垃圾回收-Garbage collection
--垃圾回收-Garbage collection(主讲人:姚文辉)
-Erasure coding
-Erasure coding(3,2)写入和读取过程
--Erasure coding(3,2)写入和读取过程(主讲人:姚文辉)
-元数据管理的高可用性和可扩展性
-元数据管理的高可用性
-Paxos概要
-Raft
-元数据管理的可扩展性
-不同存储介质的特性
-盘古混合存储
-QUIZ--作业
-阿里云飞天分布式调度
-任务调度
-资源调度
-容错机制
-规模挑战
-安全域性能隔离
-分布式调度的发展方向
-QUIZ--作业
-数据格式和抽象
-分布式编程模型
-MapReuduce编程模型
-关系型数据编程模型
-分布式图计算模型
-分布式编程未来展望
-QUIZ--作业
-分布式事务
-分布式一致性算法
-两阶段提交与三阶段提交
-实践--介绍
-关系型计算基本原理_1
-关系型计算基本原理_2
-分布式环境中的连接计算和聚合计算
-其他计算和物理优化
-QUIZ--作业
-提纲
-课程背景介绍
-前序知识
-分布式节点距离计算法则
-数据分布策略
-分布式计算调度
-数据就近原则计算如何容错
-ODPS跨集群数据依赖
-QUIZ--作业
-主讲人:谢德军
--实践2:编写MR完成Group By+Join操作(主讲人:谢德军)
-增量计算和流式计算
-与批量计算的区别
-业界典型系统技术概要分析
-核心技术
-消息机制
-有状态计算、并行DAG、抢占式调度和资源隔离、Failover机制
--有状态计算、并行DAG、抢占式调度和资源隔离、Failover机制(主讲人:强琦)
-StreamSQL
-QUIZ--作业
-软硬件趋势、分布式计算简史与内存计算
-分布式计算
-内存计算
-统一的计算框架
-业界经典系统技术分析-spark&flink
--业界经典系统技术分析-spark&flink(主讲人:强琦)
-QUIZ--作业
-主讲人:褚葳
-QUIZ--作业
-分布式环境下的新问题
-工程实现范例
-课程设计相关问题