Video在线视频

好 我们刚刚讲了Neo4j

一种这种图的这个数据库

那么大家也发现

在图的数据库里面

实际上我们有了更灵活的

对这种图的数据的一个操作

我们可以直接去match

图中的这些结构

我们可以用非常短的这种语句

来做一个简单的这种人的

这种推荐的一个算法出来

那么用图的这种数据库的语言

对图数据进行操作

实际上会变得非常的简洁

那么和关系数据库或者说和我们

直接在分布式文件系统中

对注意进行处理相比

它可以提供到一个比较高效的

这种编程的这样一个方式

那我们接下来就要去看一下

这种图的这种数据

图的数据库它对应到底层

他到底是怎么样去实现

在大规模的这种计算平台

和网络资源上

它到底是怎么样去做得到的

那么这一节

我们会通过这个

一个叫做graphlab的

这种图的这种计算引擎

来给大家介绍一下

对图的这种分布并行的算法

进行实践

他有一些什么样的这个思路

那么graphlab

它是一个图的引擎

那么它可以支持分布式的

这种图的数据挖掘

图的这种算法的实现

那么它能够用上多个服务器

可以用上每个服务器中

不同的CPU的资源

和存储和计算的这种资源

那么graphlab

它到底是个什么东西

我们现在来做一个正式定义

那么它是一个分布并行的

图的计算引擎

那么它可以对图的数据进行挖掘

对图的算法进行实现

那么它具有大数据系统的这样的

一些特征

那么它对图的数据

进行计算的时候

使用了这个in memory的

一个模式

比如将图的边和图的节点的数据

实际上在内存中进行一个处理

那么它有比较高的可扩展性

通过了一种类似于P2P的

一个结构

加入了server

进行一个组织

然后能够自动的进行容错

当服务器失败的时候

能够重新对相应的这些节点

和边上的这个处理

进行重新的调度

然后它能够对比较复杂的

这种图的算法

比较经典的图的算法

进行描述

就像我们用mapreduce

去描述很多这种关系数据

表格数据的处理的时候的

情况一样

它能够通过图这种引擎里面

提供的一些编程的原语

来对上层的算法进行实现

然后它使用了这种内存共享的

这种编程模式进行实现

我们在后面会进一步给大家提到

那么graphlab实际上

它的一个架构

大概是在我们图中

给出的这个样子

那么它基于一些有的

这种分布并行的系统

比如说分布式文件系统

然后积存的资源管理

然后来做了这个

graphlab

然后来实现了它的这种编程的

一个环境

我们简单来看一下

那么在graphlab中

它的图的这个原始数据

使用了分布式文件系统进行存储HDFS

那么它使用了mapreduce

进行图的一个数据的预处理

就是在进入内存之前

它进行了一个处理

那么把它划分成这个

图的path和图的partition两部分

那么path是将原始数据

变成graphlab

处理的图数据

partition将这些数据

给分配到各种各样的服务器上

那么建立起它的图的

这种数据结构

那么在graphlab里边

把它叫做这些item

那么建立了这些item的

index和item的文件

那么这些就是

通过mapreduce

原始的图文件

变成graphlab

可以处理的一个图文件

那么这些item的文件实际上

记录了边节点

它的一些这种属性

和它们的连接关系

那么到这边之后

就是在graphlab里面

进行图的计算的一个过程

实际上graphlab是这样

去实现的

它在graphlab的集群上

那么会运行一系列的

graphlab的引擎

这些引擎运行在各个服务器上

它们会对节点进行索引

对边进行索引

可以在节点和边上

执行一定量的代码

那么这些操作会被迭代地进行

进行完成之后

会将数据最终又输出到这个

分布式文件系统

得到这个数据的持久化

那这是它整个这个处理的思路

和它的一个架构

实际上

基于这个和分布式文件系统的

一个整合

然后使用了特定的文件的格式

定义了图

然后将图读取到内存当中

进行图的算法的并行

由GraphLab的engine来执行

然后最终把这些数据写入到

这个分布式文件系统里面

生成好的这个数据

那么我们来看它的这个计算模式

到底是怎么样的

因为我们在介绍mapreduce

或者spark的时候

我们都会去介绍数据处理的模式

mapreduce是map和reduce两过程

那么sbark是transformation

和action两部分

那么我们来看在graphlab

它是怎么样对图的算法

进行抽象的

或者说它怎么样去理解各种各样

不同的图算法

能够通过什么样的这种

操作的抽象

能够最终被表达出来

那么在graphlab中

它处理图实际上包含了

下面几个层面的概念

首先我们来看

它对图的一个定义

那么在graphlab里面

它的这个图实际上和之前

Neo4j的图的定义是一样的

它有一系列的节点和边来组成

那么在节点和边上

我们是可以把这些数据给

分布到不同的server上的

那我们认为这些数据

包含比较大的属性

这个属性可能会非常大

也可能会比较小

但这个是由用户自己定义的

但是graphlab提供给用户的

就是说我们可以对这上面的数据

进行某种操作

就像我们对Neo4j里面的

这个属性进行某种操作

那这个操作我们认为是需要

去得到分布并行的

这是GraphLab设计的时候

做的一个假设

节点上的数据

边上的数据

那么有了这样的一个定义之后

实际上graphlab

它通过一个叫做update的

这样一个函数

来给用户提供一个接口

这个接口用户需要去实现

然后它起到的作用

就是对图上的数据节点

或者边上的数据

进行操作的一个过程

我们来看

这个过程它又分成两个子步骤

第一个就是说我们找着一个节点

它的一个范围

叫做scope

第二个我们会通过update的函数

对这样的一个范围进行查看

同时进行一定的更新操作

那我们来看这个含义是什么样子

那么我们有一个节点叫做v

那么通过这个节点

我们可以拿到它的一个范围

那么在graphlab里面

它的范围是和节点相连的边

以及其它的邻居节点

它的这样一个结构

那么v的scope

我们把它记作SV的话

它的这样一个范围

就是图中给出来的这样一个样子

所以当我们对v

进行update的时候

进行更新

进行计算

进行操作的时候

我们可以参考的数据就是V的

这样一个scope

那大家可能会有疑问

我的某些算法会不会

对V进行操作的时候

还需要看整个系统里面

其他的数据?

那这种模式是实际上

在graphLab里面

就没有办法

或者说没有很好的办法

得到直接的这样一个支持

所以它也是有所取舍

我们通过了这样一个

scope的定义

实际上我们数据能够参考的范围

是变小了

但是我们分步并行

以及我们这种进行高效计算的

这种能力就提升了

那么这边给到

当我们看到一个V的scope之后

我们可以拿到它相邻的边

邻居节点的这些数据

然后来对V进行一个操作

那我们来看

这个操作它从算法的描述上

是一个什么样子的

那么这个算法它的执行的过程

实际上是这样的

我们有整个数据

定义了节点

定义了每个节点和边上的数据

那么我们有一系列初始的节点的

这个组成的集合

那么整个过程进行避规

进行迭代

那么当我们从初始节点的集合

或者说这个节点集合里面

拿到一个元素之后

我们会根据它的一个领域

它的一个scope

对节点进行更新的操作

这个操作可能会改变数据

然后得到新的一个领域的范围

所谓新的领域范围

就是说当我们在对V

进行操作的时候

我们达到他邻居的这个列表

来到他邻居的这个节点

我们就去看V会带来哪些新的

这个邻居节点进来

那么我们可以理解就是把v的

这个邻居节点加入进来

当然如果各位同学

在实现自己的engine的时候

实际上也可以考虑是不是有满足

其他高级算法的不同的

领域加入的一个方法

然后我们把新发现的这个

没有处理过的节点

加入到原始的这个节点列表里面

整个过程会叠加进行

那么经过这样一轮之后实际上

我们就会对图中能够便利到的

这些由初始节点

能够便利到的这些节点

都进行了一轮更新

数据被更新到原始的数据D里面

然后我们完成了一轮的这个操作

这是我们的更新函数

这是我们在进行调度的时候

发现的一个节点

那么我们来看在真实的

这样一个并行环境下

这个操作是怎么样进行的

我们在这边没有举更多的服务器

我们是通过两个CPU

来给大家展示这样一个例子

实际上完全可以想象成

两个不同的服务器

或者说两个服务器上

不同的CPU

这是不影响大家的理解的

那我们来看这个过程

我们说这个算法在进行的过程中

我们会有一系列的初始节点

或者说进行到某一步

我们会有一系列

当前要处理的节点列表

那么假设这到这一步的时候

我们可以发现

有两个节点是系统会去调度的

通过scheduler他们知道

这些是我们当前应该去弄的

那么并行的过程开始往下进行

找着了这两个节点

在做更新的时候

他们的一个领域

相邻的边

邻的邻居节点

那么这些信息会被这次更新函数

读取到

然后他们利用这些数据

来对这个节点进行一个操作

那么会把相邻节点

给加入到系统当中

也就是B和I

然后会把A和B从当前处理节点

给移除出去

已经在这一轮中处理过了

那么有了这两个节点之后

我们进一步往下看

开始对他们俩进行update

进行更新

然后同时找到了他们的scope

它们的领域

那么B对应的是ACEF

那么H对应的是

这个I对应的是HJEF

找到他们的领域

同时大家要理解这两个过程

依然是并行进行的

那么对这些数据进行读取

然后对B和A上的这个当前数据

进行更新

这整个过程会不断的迭代进行

直到我们将没有发现的节点

都处理完

整个系统会进入下一轮的迭代

根据用户写的这个算法

那么这一次update

算是执行结束

那么有了这次update之后

我们还有一个后续的工作要做

第三步我们需要进行数据的同步

我们需要把刚刚的这些数据

给实施到整个数据结构的

这些节点的数据当中

那么这个操作叫做同步

那么在这个同步里面

实际上graphlab

通过了一些这种

使用的一些策略

来做到尽可能同步的时候

它的冲突会比较小

因为刚刚我们发现

在我们处理的这个过程中

可能会有什么样的同步

可能会有这个读的这种操作

和写的操作发生并行的情况

我们刚刚举的例子是两个节点

但是在真正当我们系统中

有大量节点存在的时候

我们的这种读写

它可能会发生某些情况下的这种

不一致性

那么同步帮我们解决了

类似这样的一些问题

那么同步操作

我们使用了一些类似于这个

Pregel里面的

一些aggregator

这样的这种操作

那么它的操作的好处就是

我们可以尽可能的将某一些这种

并行的行为给它给串行化

同时我们在划分的时候

也会考虑这种数据的不一致

使得我们在选取初始节点

然后再做任务顺序的时候

能够考虑到数据的

这种冲突的问题

然后我们使用了

当我们无法处理这种串行

无法进行串行的这个写

或者是串行的读的时候

我们依然会通过一些

内存保护的办法

来进行数据的一个保护

那这种通常是通过

单台server上的这种信号量

或者是一些互质变量来做到的

对这种需要争议的这个数据的

读和写进行一个同步的操作

总之在同步里面

我们重点去解决数据生成之后

写入到图中的这些结构

它的这样一个过程

使得这个过程尽可能的能够容错

然后能够保证一致性

同时还能保证有效性

那么我们来看一下

在这个graphlab里面

它的这种编程的模型是什么样的

实际上

graph它实现的时候

使用了这种共享内存的

一个编程的方式

也就是说

不同的graphlab

引擎的进程

它们是可以去共同访问

这个节点的数据

或者边的数据

有的进程可能正在对它进行写

有的进程可以对它进行读

那这是共享内存

它面临的这样一个挑战

但是就我刚刚所说的

实际上在graphlab中

通过这种信号量

互质变量

或者说一些其他的保护方式

串行的这种方式

来达到了对这种争议的

这种内存段

它的一个处理

大家在使用多线程的

这种程序的时候

实际上可能会对这部分内容

已经有所体验

那如果大家想了解graphlab

所用的一些具体策略的话

可以对应到graphlab的这个文档

那么在这里我们会介绍它的一些

比较宏观的思路

那么这是我们在处理图的时候

我们假设这几个节点是我们当前

并行的需要更新的这样一个过程

那么它们能看到的数据是这样的

一个样子

那么当我们下一步

再往前扩展的时候

我们就会发现

它们会对这样的一些操作可能会

就会有一个争议

那么如果我们碰巧是这3个的话

那么很好

我们的这种数据可能是

没有问题的

我们可以独立地进行

但是当我们处理的节点

增加了这一个之后

也就是说

如果我们碰巧调度到这样的一个

情况的时候

实际上我们会发现

它们会有一些数据可能存在着

不一致的现象

比如说

当我们对这个数据进行写的时候

可能另外的节点

会对另外的这个进程

可能会对这个数据进行读

那么当这两个操作没有有效的

进行这个顺序化

或者说是进行定义的话

那这个操作可能会得到一些

我们事先意想不到的这种结果

那我们来看在graphLab里面

对这种情况

他们会做什么样的处理

那么graphLab定义了几种

一致性的这个模型

一种叫Full的consistency

就是要保证这个邻居节点

和邻居的边

都能够保证一致

那么vertex这个consistency

仅保证节点

然后vertex保证边的

我们来看这三种

它从范围上

会是什么样的一个样子

那么这是我们说到了一个

vertex当前update函数

会去讨论的一个位置

那么full consistency就是说要保证

在整个这个节点的领域里面

包含了它的邻居节点

和邻居边上的数据

在读写的过程中

都具有这个一致性

最强的一种保证

edge只保证它邻居的边

具有一致性

范围缩小了

不再考虑他邻居的节点

因为离得更远了

然后vertex

把范围进一步缩小

我们更新当前的节点的时候

我们仅保证当前的节点

它的这个数据能够一致性

也就是说能够被锁定

或者说能够被顺序化

那么这边有几个例子

大家可以看看当读写发生的时候

它的这种一致性

在不同的这个一致性模式底下

它的一个情况是什么样的

那么在这个full consistency的模式下

我们有一系列的节点

同样我们假设节点三

是我们当前需要去处理的

那么它的存储空间在这里

那么当进行这个写在操作的时候

在full的这种模式底下

我们写的操作会将它的邻居节点

和邻居的边同时锁定

也就是说

这时候当我们争抢到锁之后

实际上其它的进程是没有办法

对这些数据进行操作的

然后它和读的这个范围是一致的

那么读的范围也是这样的

一个邻居节点加邻居边的一个范围

那么达到最大的一个范围的一个保证

那么在edge的

这样一个模式下

那么它的读是这样的一个范围

我可以参考这样的一个范围

那么它的写保护的是邻居节点

和邻居边的这样一个数据

也就是说仅对边上的这个数据

当我在写的时候会进行一个互斥

或者会进行一个加锁操作

而这时候如果有另外的进程在写

邻居节点的数据的时候

实际上系统是不知道

会允许这样的写发生

这是这样的一个模式

那么第三种模式就是

我们对保护的范围进一步缩小

我们只保护vertex当前节点

这样的一个范围

而当读这个其它的这个

邻居的边和邻居的节点

都不会得到保护

那这样的一个现象就是说

当我们对当前节点

进行操作的时候

实际上我们不能保证它的邻居边

和邻居节点

在这个时候会不会发生变化

因为我们保我们锁定的

这样一个空间是非常的小的

所以这是不同的这个consistency模式底下

这个graphLab它保护的

这样一个范围

读的保护

写的保护

那么大家在具体去使用的时候

实际上会根据自己的算法

比如你的算法

并不在意别的进程会对你当前的

邻居节点或者邻居边进行调整

那么你可以尽可能减少写的

这个保护的范围

比如说这样的话

可能可以使整个并行度提升

因为你的这个其他进程

可以运行的可能性就变多了

从直观的这种角度

可能会提升你整个系统的

运行的效率

那么大家在算法设计的时候

需要去重点考虑使用什么样的

一致性的模型

好 那我们进一步来看一下

它的系统架构graphlab在里面

它是一个什么样的情况

那graphlab使用了相对对等的一个架构

也就是每个进程

实际上它都可以在自己的节点上

去从一个节点

或者一个节点组出发

进行数据的运算

数据的一个操作

那么节点是对等的

同时在这个节点之间

通过进程间通讯

来进行数据的共享

比如当某一个服务器

需要访问他的邻居节点

而邻居节点位于

另外一个服务器的时候

可以通过进程间的通讯

这个网络间的远程调用来使用

同时它使用了这种

共享内存的模式

来进行数据的共享

效率上是比较高的

当然它需要通过锁得方式

进行一个性能上

这种安全上的一个保护

那么它的优点

就是它的可扩展性是比较高的

因为每一个节点运行的程序

是完全一致的

加入的节点可以迅速的

分配到一部分

这个处理的边和节点数据

然后它的缺点主要是在于

它的复杂度

我们刚刚说到它有两种锁

需要去保护

同一个server上

需要对共享内存进行保护

然后不同的server之间

它还需要进行远程调用

可能又会涉及到比较复杂的

这种架构的

以及同步性的这种问题

这是它的一个缺点

下面我们通过一个具体的例子来

给大家展示一下

怎么样通过graphlab

它提供的这种编成的原语

来实现图的算法

graphlab提供了一个update

这样操作 对吧

我们可以针对一系列初始的

这个节点

然后对它进行update

update的时候

我们可以参考它的领域

S里面的这些边

和节点上的这个数据

然后这个过程不断地迭代

不断扩展到系统中其他的

这个节点

我们来看

通过这样的一个编程的接口

或者编程的原语

我们怎么样来实现一些

比较复杂的这种图的算法

我们这边给的算法的原型

叫做page rank

是大家熟悉的这个page rank算法

我们来看page rank

在graphlab上

它是怎么样实现的

这个page rank实际上我们是希望

都通过图中一个节点

它的相邻节点的相连的情况

然后来对节点对节点的这种影响

进行一个估计

那么它的这种估计的算法

在这边我们已经提到

那我们来看

这个算法它通过

graphlab

是怎么实现的

那么我们来看

从一个节点出发

它的这样一个例子

我们有了这样一个节点

我们要对这个节点的状态

进行更新

这个节点当我们在做更新的时候

什么是我们可以用的

什么是我们的输入

就是它的scope

它的领域的列表

它有这个边上的数据

有节点上的数据

那我们来看这段代码是怎么写的

我们有节点R

然后我们有这个scope

然后我们进行的操作是什么样的

我们把这个scope

首先给提取出来

那么因为scope

可以让我们访问到

相邻的节点的信息

以及相邻的这个边的信息

所以我们是可以把

R它的一个权重

J它的一个权重

以及它们两之间的

这个weight的

能够提取得到

那么我们来做update

有了这些信息之后

那么根据page rank的这个算法

我们做了alpha加1-alpha

然后后面是这个权重加节点的

这个本身的这个R值

它的一个相乘

然后把数据更新到R里面去

完成了对R的一个

这个update

然后我们可以去reschedule

其他的这些节点

也就是说让其他节点

也来做这样的事

实际上

这两部是我们整个算法的核心

把相邻节点的信息提取出来

把节点的数据进行更新

那么大家要注意的就是

我们怎么样把这个数据

分散到边和节点上去的

那我们让节点数据记录了

它自身的这样一个R值

然后我们让边来记住了这个节点

对节点的这样一个weight

所以我们实际上是做了这样的

一个转化

当然page rank是一个

比较简单的这样一个算法

当大家需要做相对比较复杂的

算法的时候

可能这个过程就会变得

有一些技巧

比如说要做一个这个

最长路径的时候

我们可能就需要去考虑

这个最长路径

我们的输入节点到底是什么

可能是从一个节点出发

然后我们的输出节点是什么

我们可能要把到这些节点的距离

给更新到这个当前节点

或者说我们需要从不同的节点

同时出发来做一个更新

总之我们通过这个例子

给大家演示了

怎么样用这个graphLab

提供的update

提供的scope

以及提供的这种同步的

这样一个机制

来进行一些特定的算法的

一个设定

好 那么我们今天的

关于这种图的数据库

和图的这种分布式系统

就讲到这里

那么我们希望同学们

可以通过今天的课程

大概的了解

我们将sql

这种关系数据库的处理的

这种查询语句

移植到图里面

变成类似于Neo4j里面

这种Cypher

它会有什么样的优势

比如说我们可以对图

进行模式的匹配

对一些图的算法

进行比较简易的实现

那我们也给大家介绍了

我们怎么样在图的

这种数据结构下

做分布式的这种算法

graphLab通过对这个节点和边

进行划分

通过对这种节点的更新

进行一种原子化操作的

这样的一个定义

实际上做到了这个分布式

进行图数据处理的这样一个目标

那么我们希望大家能够

通过今天的课程

后面能够进一步去思考

怎么样设计好一个图的这种算法

在分布式的这种环境底下

怎么样充分的利用分布式的

这种图的这种处理的这种思路

来对现实生活中碰到的一些问题

进行有效的这个计算

能对图的这种大数据

进行有效的分析

好 谢谢大家