前段时间参与了一个迭代计算平台的开发，对内存计算和图计算产生了浓厚的兴趣。期间也看了spark和pregel的相关论文，学习了BSP模型，但是总觉得看论文太抽象了，所以选择阅读graphlab源码作为对图计算更深入理解的机会.接下来有时间的话，我会详细记录一下对graphlab的一些粗浅理解。在graphlab中，用一个邻接矩阵来表示顶点之间的邻接关系。给定一个图G(V,E)，用一维数组存储V的顶点信息，用稀疏矩阵存储E的边信息。在graphlab中，图分布在多个机器，每台机器存储图的一部分。这里我们讨论各个节点如何在graphlab中实现图的本地存储。graphlab的图相关接口中有两个接口，分别是inedges和outedges，用于获取顶点。那么在graphlab中，需要考虑如何有效的存储一个图的边集，快速索引顶点的入边和出边，尽可能减少空间开销。Graphlab采用的思想是同时使用稀疏矩阵的csr（compressedsparserow）和csc（compressedsparsecolumn）存储格式来存储图的边集，并高效实现获取in边和顶点的边缘。Graphlab分别实现了图的静态存储和动态存储。静态存储是指一旦存储了图的顶点和边，就不会再添加新的顶点和边。使用动态存储，您可以动态地向图中添加顶点和边，这两者都不会删除顶点和边。静态存储和动态存储的思路是同时使用稀疏矩阵的csr和csc格式来存储边集，但是csr和csr使用的数据结构不同。静态存储用数组实现，动态存储用链表实现。本篇博客只介绍静态存储，动态存储会在下一篇博客介绍。本篇博客将首先介绍稀疏矩阵和计数排序的csr和csc格式，然后通过实例分析graphlab图的静态存储，最后介绍graphlab实现图静态存储的相关类。1稀疏矩阵csr和csc格式及计数排序介绍1.1csr和csc格式介绍csr用三个数组表示一个稀疏矩阵，稀疏矩阵用A表示，三个数组分别是values、rowptrs和columns;A中非零单元格的值是顺序存储的。Columns存放的是values数组中单元的列索引，values(k)=A(i,j)，则columns[k]=j。rowptrs在values中存储该行的起始地址，如果values(k)=A(i,j)，则rowptrs(i)<=kvertices：一个数组存储顶点数据，顶点的ID为0到数组的长度。std::vectoredges：存储边值的数组，相当于edges_values。csr_type_csr_storage：表示csr，由类csr_storage实现。csc_type_csc_storage：表示csc，由类csr_storage实现。csr_storage中有两个成员变量，分别是：std::vectorvalue_ptrs；std::vector值；当csr_storage代表csr时，value_ptrs相当于rowptrs，是一个uint64_t数组；values相当于columns，也是一个uint64_t的数组。当csr_storage代表csc时，value_ptrs相当于columnptrs，是一个uint64_t数组；values定义为std::vector>，相当于将rows和shuffleptrs存储在同一个vector中。3.存储结构Graphlab实现了基于csr和csc格式的图的动态存储。不过在csr和csc的底层数据结构设计上做了一些调整，数组换成了块链表。如果实现图的动态存储，需要将底层的数据结构从数组改为链表，但需要对原本用于静态图存储的算法集做一些调整。动态存储格式中的CSR、CSC、边值数组如下图所示：1.edges是一个数组，数据结构使用vector，但是批量插入的边的权值放入vector中命令。2.CSR由行迭代器数组rowIterators和columns组成。columns是blocks的链表，意思是按相邻矩阵的行（即边的源顶点）的大小排序的列的链表。如上图所示，Block的内容如下，Block是一对定长数组。多个块组成一条链，pair中的第一个是邻接矩阵的列（即边的目标顶点），第二个是边在edges数组中列所在的位置。CSR的rowIterators索引链表的行，rowIterator[i]指向第i行起始位置在列中的偏移地址。3.对于CSC，由列迭代器数组colIterators和rows组成。Rows是blocks的链表，意思是按邻接矩阵（即边的目标顶点）的列的大小排序的行链表。如上图所示，Block的内容如下，Block是一个定长pair的数组，多个block组成一条链，pair的第一个是邻接矩阵的行（即边的目标顶点），第二个是该行所在的边在edges数组中的位置。colIterators是对链表的列进行索引，colIterators[j]指向第j列起始位置在行中的偏移地址。#p#4在源码中实现csr和csc构建和动态插入的整体流程：批量输入的边可以用三个数组表示，source_vertex数组（边的源顶点），target_vertex数组（边的目标顶点）和edge值数组edge_values。1.对source_vertex数组进行计数排序，输出P1和rowptrs。P1为source_vertex按行升序排列生成的序列数组；rowptrs[i]指向P1中第i行的起始偏移地址。P1[rowptrs[i]+k]表示第i行的第k个元素在边缘数组中的位置，其中0<=k<(rowptrs[i+1]-rowptrs[i])。2.对target_vertex数组进行计数排序，输出P2和colptrs，P2是对target_vertex按列升序排序生成的序列数组；colptrs[j]指向P2中第j列的起始偏移地址，P2[colptrs[j]+k]表示第j列第k个元素在edges数组中的位置，其中0<=k<(colptrs[j+1]-colptrs[j]);3、由于CSR底层数据结构是块链表和行迭代器数组指针，所以需要将计数排序后得到的rowptrs、P1、target_vertex转化为迭代器数组和pair数组。block链表的block是一个定长的pair数组，所以用p1和target_vertex构造pair数组csr_values，csr_values中第i条输入边的值是{target_vertex[P1[i]],length(edges)+P1[i]}。3.1如果图片为空，使用rowptrs和csr_values初始化CSR，即将csr_values中的值赋给CSR的列，然后将rowptrs的行起始位置转换为列中的迭代器并将其放入rowIterators。3.2如果图不为空，逐行往CSR中插入数据，一次插入一行，csr_values中第i行的值为csr_values[P1[i]]到csr_values[P1[i]中的数据+1]]。在下图所示的CSR中，rowIterators是一个迭代器数组，rowIterators[i]存储的是列中第i行的起始位置，rowIterators[i+1]是第i行的结束位置，也是第i+1行的起始位置；columns是一个块列表。蓝色是第i行的数据，橙色是第i+1行的数据。绿色是需要新插入的第i行的数据。向第i行插入新数据，CSR插入行的步骤如下：A.首先找到rowIterators[i+1]指向的第i行的结束位置Pos，插入本块Pos后第i+1行数据段提前保存。B、将第i行的新数据复制到Pos之后的位置。如果新插入的数据太长，则会创建一个或多个新块来容纳它。C、复制新插入数据后第i+1行的预存数据。如下图所示：D.上述操作完成后，第i+1行的迭代器指针失效，指向的数据位置为第i行新插入的数据，所以第i+1行的迭代器需要待调整指针。E.***因为按行向CSR中插入数据会产生一些空隙，比如上图中block中的空白，所以在所有行插入后，会进行repack操作，压缩空白内存并变成下图所示：CSC的处理和CSR类似，这里不再赘述。这种方式只能支持动态批量插入，随机插入的性能开销太大。5Graphlab中的相关类dynamic_block：图动态存储的底层数据结构，使用内存块链表，可以动态插入。dynamic_block就是实现这个内存块的类，dynamic_block形成一个块的链表。block_linked_list：块链表，是由dynamic_block组成的单向链表。dynamic_csr_storage：实现csr和csc动态存储的数据结构，将底层数组替换为链表，然后使用链表的迭代器数组实现记录行或列的起始位置。dynamic_local_graph：实现图动态存储的类。图的动态存储旨在批量更新而不是随机插入。原文链接：http://my.oschina.net/zhengyang841117/blog/194826
