# GraphLab 入门实例指南

> 因为课程的机会接触了一下 GraphLab，许多概念以及对应的思维方式需要改变。这里主要介绍一下基本概念，以及如何启动 GraphLab 集群并进行简单的计算。

- 作者：[小土刀](https://wdxtub.com/about)
- 发布日期：2016-04-13
- 原文（引用请使用此链接）：https://wdxtub.com/blog/bigdata/graphlab-guide
- 所属系列：bigdata 大数据之旅
- 标签：大数据
- 许可：CC BY-NC-SA 4.0（https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh）
- 正文中的站内图片路径以 https://wdxtub.com 为根目录。

> 阅读提示：这是 2016 年整理的历史学习笔记，工具、服务和示例保留当时的版本背景。

---

因为课程的机会接触了一下 GraphLab，许多概念以及对应的思维方式需要改变。这里主要介绍一下基本概念，以及如何启动 GraphLab 集群并进行简单的计算。

---

更新记录

- 2016.04.13: 初稿

GraphLab 是 CMU 开发的分布式 graph parallel 框架，用来在大数据上执行机器学习和数据挖掘算法。GraphLab 把具体的计算抽象成为节点(vertex)，而计算之间的数据关系抽象成为边(edge)。

简单来说就是具体的计算会在每个节点上进行，有三个步骤：

1. Gather: 对于每个节点来说，其 master 和 mirror 节点会从相邻的边和节点收集所需信息
2. Apply: 所有收集到的信息会在 master 节点完成计算并更新节点，完成之后这个改动会同步到其他的 mirror 节点中
3. Scatter: master 和 mirror 节点选择更新对应相邻的边和节点，收到消息的节点会被激活，继续执行对应的计算

![步骤过程](/images/old-site/images/14604025416778.jpg)

另外有一个需要注意的地方是在最新的版本中，采用 Vertex-Cut 来进行数据分隔。这样的好处是，一条边连接的两个节点肯定在一台机器上，对于每个节点来说，可能会有几个不同的复制，其中一个将成为 master，其他的则是 mirror。

## 安装部署

手动配置的步骤还是比较繁琐的，不过 GraphLab 提供了启动 Amazon EC2 的脚本，可以自动进行机器的申请和部署。这里也主要以这种方式来进行之后的步骤。

从[官方 Github](https://github.com/dato-code/PowerGraph) 下载好源代码之后，解压之后进入 ` scripts ` 文件夹。然后需要在环境变量中进行如下配置（这个只对当前的终端有效）：

- ` export AWS_ACCESS_KEY_ID=[your AWS access key] `
- ` export AWS_SECRET_ACCESS_KEY=[your AWS secret key] `

完成之后可以通过如下的命令来启动集群

` ./gl-ec2 -k [密钥名] -i [密钥文件路径] -t [实例类型] -s [slave 数量] -r us-east-1 launch [集群名称] `

这里的实例类型默认是 ` m1.large `，这里我们可以简单测试一下（对于大的图可能 m4.large 内存会不够），我使用的命令是

` ./gl-ec2 -k demo -i demo.pem -t m4.large -s 10 -r us-east-1 -a ami-89adafe3 launch p423 `

没啥意外的话（如果有意外的话一般是当前区域没有足够的主机，换一个机器类型即可），就可以看到机器正在启动，如下图所示

![](/images/old-site/images/14605602879933.jpg)

启动脚本执行完毕之后。我们就可以进行登录了，命令为：

` ./gl-ec2 -k [keypair] -i [key-file] -r us-east-1 login [cluster-name] `

对于当前的例子来说就是

` ./gl-ec2 -k demo -i demo.pem -r us-east-1 login p422 `

执行的话也可以用脚本进行，编译之后（具体参考官方的例子）使用 ` ~/graphlab/scripts/mpirsync ` 把程序分发到集群的每一台机器上，然后使用 ` mpiexec ` 命令来具体执行。

如果要关闭集群的话，命令为：

` ./gl-ec2 -k [keypair] -i [key-file] -r us-east-1 destroy [cluster-name] `

对于当前的例子就是

` ./gl-ec2 -k demo -i demo.pem -r us-east-1 destroy p422 `

## PageRank

接下来我们试着用 GraphLab 把 PageRank 实现一次。首先当然是要搞到文档，用如下命令 ` brew install doxygen; doxygen `。等待一段时间之后，就可以在 ` doc/doxygen/index.html ` 中查看文档了。

PageRank 的具体介绍可以查看[维基](https://en.wikipedia.org/wiki/PageRank)，这里做一个简要介绍。我们先来看看具体的公式

![](/images/old-site/images/14606382712570.png)

这个公式是什么意思呢？这里我们取 ` N = 1, d = 0.85 `，也就是说，一个页面的 PageRank 值，等于一个常数加上其他指向它的页面所贡献的 PageRank 值。每个指向该页面的页面具体贡献的数值，是指向该页面的页面自己的 PageRank 值除以外链的个数，即简单的平均数，一个页面把自己的 PageRank 分散出去。一个简单的例子

```text
page1, rank: 1.0, point to: page2, page3
page2, rank: 1.0, point to: page3, page1
```

经过第一次迭代之后，会得到如下的分布，这里稍微解释一下，为什么 page1 得到的是 0.5 呢？因为我们可以看到只有 page2 指向 page1，而 page2 一共有 2 个外链，所以其权重被平均分成两份，于是就是 0.5；page2 得到 0.5 也是同理。而 page1 和 page2 都指向 page3，page3 从他们身上拿到了 0.5，所以是 1.

```text
key: page1 contributions received: 0.5 point to: page2 page3 
key: page2 contributions received: 0.5 point to: page3 page1 
key: page3 contributions received: 1.0 point to:
```

这里 page3 没有外链，就成了『异类』，所以必须把这类节点的权重平均分给所有的节点，这里 user3 的初始权重是 1，因为一共有 3 个用户，可得：

```text
page1 = 0.15 + 0.85 * (0.5 + 1.0/3) = 0.8583
page2 = 0.15 + 0.85 * (0.5 + 1.0/3) = 0.8583
page3 = 0.15 + 0.85 * (1.0 + 1.0/3) = 1.2834
```

之后就继续按照这样的模式计算下去，直到指定次数或者收敛（排名不再变动）。

## 具体实现

我们从官方给出的[例子](https://github.com/dato-code/PowerGraph/blob/master/demoapps/pagerank/simple_pagerank.cpp)中可以大概了解具体要如何编写。还是用之前提到的几个步骤：` gather `, ` apply `, ` scatter ` （以下代码来自官方例子）

```cpp
float gather(icontext_type& context, const vertex_type& vertex, 
    edge_type& edge) const {
    
    return ((1.0 - RESET_PROB) / edge.source().num_out_edges()) * edge.source().data();
}

/* Use the total rank of adjacent pages to update this page */
void apply(icontext_type& context, vertex_type& vertex,
        const gather_type& total) {

    const double newval = total + RESET_PROB;
    last_change = std::fabs(newval - vertex.data());
    vertex.data() = newval;
}


/* The scatter edges depend on whether the pagerank has converged */
edge_dir_type scatter_edges(icontext_type& context,
        const vertex_type& vertex) const {
        
    if (last_change > TOLERANCE) return graphlab::OUT_EDGES;
    else return graphlab::NO_EDGES;
}

/* The scatter function just signal adjacent pages */
void scatter(icontext_type& context, const vertex_type& vertex,
          edge_type& edge) const {

    context.signal(edge.target());
}
```

因为我们现在是针对于某个节点在运算，所以不需要考虑全局的状况，甚至也不需要在意怎么获取邻接节点，都可以认为框架会帮我们处理好，我们直接专注于需要在节点上进行的计算即可！所以可以看到整个 PageRank 在 GraphLab 上的实现非常简单明了！

不过需要注意的是，这个例子中并没有处理没有外链的页面，也就是 dangling page 的情况，如果想要得到更准确的 pagerank，需要进行处理。

## 参考链接

- [官方 Github](https://github.com/dato-code/PowerGraph)
- [PageRank Code](https://github.com/dato-code/PowerGraph/blob/master/demoapps/pagerank/simple_pagerank.cpp)

