前一段時(shí)間參與了一個(gè)迭代計(jì)算平臺(tái)的開發(fā)，對(duì)于內(nèi)存計(jì)算和圖計(jì)算產(chǎn)生了比較濃厚的興趣，這期間也閱讀了spark和pregel的相關(guān)論文，了解一下BSP模型，但總覺得看論文太抽象了，于是選擇閱讀graphlab源碼，作為深入了解圖計(jì)算的一個(gè)契機(jī)。接下去如果有時(shí)間的話，會(huì)詳細(xì)記錄下我對(duì)graphlab的一些膚淺的理解。

在graphlab中，采用鄰接矩陣來表示頂點(diǎn)之間的相鄰關(guān)系，給定一個(gè)圖G(V, E)，使用一個(gè)一維數(shù)組存儲(chǔ)V的頂點(diǎn)信息，使用一個(gè)稀疏矩陣來存儲(chǔ)E的邊信息。

在graphlab中，圖是分布在多個(gè)機(jī)器之上，每個(gè)機(jī)器中存儲(chǔ)著圖的一部分，在這里我們討論graphlab中，每個(gè)節(jié)點(diǎn)是如何實(shí)現(xiàn)圖的本地存儲(chǔ)。

在graphlab的圖相關(guān)接口中有兩個(gè)接口，分別是獲取頂點(diǎn)的in edges和out edges。那么在graphlab中需要考慮如何有效地存儲(chǔ)一個(gè)圖的邊集合，并可以快速地對(duì)頂點(diǎn)的in edges和out edges進(jìn)行快速索引，并盡可能地減少空間開銷。

Graphlab中采用的思路是同時(shí)采用稀疏矩陣的csr(compressed sparse row)和csc(compressed sparse column)存儲(chǔ)格式來存儲(chǔ)圖的邊集合，并高效地實(shí)現(xiàn)獲取頂點(diǎn)的in edges和out edges的接口。

Graphlab分別實(shí)現(xiàn)了圖的靜態(tài)存儲(chǔ)和動(dòng)態(tài)存儲(chǔ)，靜態(tài)存儲(chǔ)是指一旦完成對(duì)圖的頂點(diǎn)和邊的存儲(chǔ)之后，不會(huì)添加新的頂點(diǎn)和邊。而動(dòng)態(tài)存儲(chǔ)，可以動(dòng)態(tài)地往圖中新增頂點(diǎn)和邊，這兩者都沒有刪除頂點(diǎn)和邊的操作。靜態(tài)存儲(chǔ)和動(dòng)態(tài)存儲(chǔ)的思路都是同時(shí)采用稀疏矩陣的csr和csc格式來存儲(chǔ)邊集合，不過csr和csr采用的數(shù)據(jù)結(jié)構(gòu)不一樣，靜態(tài)存儲(chǔ)采用數(shù)組實(shí)現(xiàn)，動(dòng)態(tài)存儲(chǔ)采用鏈表實(shí)現(xiàn)。在本篇博客中，只對(duì)靜態(tài)存儲(chǔ)進(jìn)行介紹，動(dòng)態(tài)存儲(chǔ)會(huì)在下一篇博客中進(jìn)行介紹。

本篇博客首先會(huì)介紹一下稀疏矩陣的csr和csc格式以及計(jì)數(shù)排序，然后會(huì)舉一個(gè)實(shí)際的例子來分析graphlab圖的靜態(tài)存儲(chǔ)，***介紹一下graphlab實(shí)現(xiàn)圖靜態(tài)存儲(chǔ)的相關(guān)類。

1 稀疏矩陣csr和csc格式和計(jì)數(shù)排序簡介

1.1 csr和csc格式介紹

csr是使用三個(gè)數(shù)組來表示一個(gè)稀疏矩陣，稀疏矩陣用A表示，三個(gè)數(shù)組分別是values、rowptrs和columns；values中按行順序存儲(chǔ)著A中的非零單元的值。Columns中存儲(chǔ)著values數(shù)組中的單元的列索引，values(k) = A(i, j)，則columns[k] = j。Rowptrs中存儲(chǔ)著行在values中的起始地址，如果values(k) = A(i, j)，則rowptrs(i) <= k <rowptrs(i + 1)，行i中的非零單元的數(shù)目為rowptrs(i + 1) - rowptrs(i)。

比如稀疏矩陣A = 

假設(shè)下標(biāo)都從0開始，那么行是{0,1,2}，列也是{0,1,2}；稀疏矩陣A的csr格式就可以用如下三個(gè)數(shù)組表示：

csc格式類似于，只不過是把行換成了列,csc可以用values，columnptrs和rows表示矩陣A。values中按列順序存儲(chǔ)著A中的非零值；rows中存儲(chǔ)著values數(shù)組中單元的行索引,values(k) = A(i, j),則rows(k) = i；columnptrs中存儲(chǔ)著列在values中的起始地址，values(k) = A(i,j)，則columns(j) <= k < columns(j + 1)，j列的非零單元數(shù)目為columns(j + 1) - columns(j)。

關(guān)于csr的詳細(xì)描述見：http://web.eecs.utk.edu/~dongarra/etemplates/node373.html

1.2 計(jì)數(shù)排序

計(jì)數(shù)排序的思路如下：假設(shè)n個(gè)輸入元素中的每一個(gè)都是介于0-k的整數(shù)，此處k為某個(gè)整數(shù)。對(duì)每一個(gè)輸入元素x，統(tǒng)計(jì)小于x的數(shù)目s，那么可以通過s來確定x在最終輸出數(shù)組中的位置。

在graphlab中，計(jì)數(shù)排序的輸入是一個(gè)未經(jīng)排序的原始數(shù)組A；輸出是兩個(gè)數(shù)組，分別是P和I；P數(shù)組長度等于原始數(shù)組的長度，是按從小到大對(duì)原始數(shù)組進(jìn)行排序后生成的序列數(shù)組，P[i]表示排序后的第i個(gè)值在原始數(shù)組中的下標(biāo)；I數(shù)組表示值為i的整型在排序后的數(shù)組中的起始位置，I數(shù)組的長度為max{A[i]} + 1（+1的原因是從0開始計(jì)數(shù)）。

Graphlab中計(jì)數(shù)排序算法的偽碼：

比如給定一個(gè)原始數(shù)組A，數(shù)組長度為7，數(shù)組中存儲(chǔ)著整型值（可能有重復(fù)），如下圖所示：

運(yùn)行結(jié)果：

在counting_sort函數(shù)中12-13行的循環(huán)運(yùn)行完后，原始數(shù)組（A）和統(tǒng)計(jì)數(shù)組（c）如下所示：

c[i]存儲(chǔ)著在A中，值小于等于i的元素?cái)?shù)目。

第15-16的運(yùn)行步驟如下，總共有：

***P數(shù)組存儲(chǔ)著排序后的數(shù)值在原數(shù)組中的下標(biāo)。c數(shù)組中的每個(gè)單元c[i]中則存儲(chǔ)著在A數(shù)組中，值小于i的元素?cái)?shù)目。i在A中的數(shù)目等于：c[i + 1] - c[i]，i < k或n - c[i] ，i == k；c[i]表示i值在P數(shù)組出現(xiàn)的***個(gè)值的下標(biāo)。

最終I數(shù)組的結(jié)果等于stem 6中的c：

這三個(gè)數(shù)組之間的關(guān)系如下：

給定一個(gè)值2，那么2在A中的數(shù)目為：I[3] - I[2] = 1；2在A中的位置為A[P[I[2]] ] = A[1]。

#p#

2 使用csr和csc存儲(chǔ)圖

我們可以將邊集合表示為一個(gè)鄰接矩陣，使用稀疏矩陣的csr和csc格式來存儲(chǔ)鄰接矩陣。

因?yàn)橄∈杈仃嚨腸sr存儲(chǔ)格式是對(duì)row進(jìn)行壓縮，可以根據(jù)row來快速對(duì)稀疏矩陣的某一行進(jìn)行檢索，所以使用csr來對(duì)out_edges進(jìn)行檢索（邊(v,w)是頂點(diǎn)v的out edges,頂點(diǎn)v對(duì)于邊(v,w)相當(dāng)于行）。同理，稀疏矩陣的csc存儲(chǔ)格式是對(duì)column進(jìn)行壓縮，可以根據(jù)column來快速對(duì)稀疏矩陣的某一列進(jìn)行檢索，所以使用csc對(duì)in_edges進(jìn)行檢索。

我們先單獨(dú)分別從csr和csc角度考慮邊集合的存儲(chǔ)。然后再分析graphlab是如何同時(shí)使用csr和csc巧妙地實(shí)現(xiàn)對(duì)邊集合進(jìn)行存儲(chǔ)，并實(shí)現(xiàn)對(duì)頂點(diǎn)的in edges和out edges快速檢索。

2.1 CSR格式存儲(chǔ)

如上圖所示，給定以一個(gè)有向圖G（V，E），V為頂點(diǎn)集合，E為邊集合。一條邊包括頂點(diǎn)對(duì)（邊從source vertex指向targe vertex）和值，邊集合可以表示成如下的鄰近矩陣，對(duì)于邊(v,w)，將v作為行，w作為列(source vertex對(duì)應(yīng)行，target vertex對(duì)應(yīng)列)。

假設(shè)E中邊的輸入順序如下所示：

那么我們就可以用如下三個(gè)數(shù)組來表示輸入的邊集合E：

那么如何將輸入的E轉(zhuǎn)化為按照csr格式存儲(chǔ)的稀疏矩陣呢？

1. 將source vertex數(shù)組作為輸入數(shù)組，使用1.2張中的counting_sort進(jìn)行排序，輸出的數(shù)組為P和I。因?yàn)閟ource vertex相當(dāng)于鄰接矩陣的行，這一步驟等同于將稀疏矩陣的非零單元按照行順序存儲(chǔ)在一個(gè)數(shù)組中（這里不需要考慮同一行內(nèi)的各個(gè)邊的順序）。那么P是按行的從小到大順序?qū)υ紨?shù)組進(jìn)行排序后生成的序列數(shù)組；I等于csr中的rowptrs；

2. 使用P對(duì)輸入邊集合E的target vertex數(shù)組和value數(shù)組按照行大小進(jìn)行重新排序，那么排序后的target vertex數(shù)組就是csr中的columns，value數(shù)組就是csr的values。這里的排序可以使用不同的方式實(shí)現(xiàn)，最簡單的方法就是引入一個(gè)臨時(shí)數(shù)組，按照P數(shù)組中的下標(biāo)對(duì)target vertex和value進(jìn)行排序。

counting_sort具體過程見1.2章（1.2張的例子就是本例），最終E的CSR格式如下圖所示。

1.edges_values數(shù)組：是按行順序進(jìn)行排序后邊集合的值數(shù)組。

2.rowptrs數(shù)組：保存行在edges_values中的起始偏移地址， rowptrs[i]是第i行在edges_values中的起始偏移位置；那么第i行的邊數(shù)目等于rowptrs[i + 1] –rowptrs[i]或edges_values長度 – rowptrs[i ]；rowptrs數(shù)組的長度為頂點(diǎn)的***值。

3.columns數(shù)組：列索引，columns[i]是edges_values[i]值對(duì)應(yīng)的邊的列的值。如edges_values[2]的列為columns[2]，等于3。

那么用csr存儲(chǔ)的邊集合E，給定一個(gè)頂點(diǎn)v，可以快速檢索v的所有out edges的值。v的值相當(dāng)于行，那么v的所有out edges的值可以通過如下的方式獲?。?/p>

拿上面的例子，頂點(diǎn)1的out edges的數(shù)目為rowptrs[2] – rowptrs[1] = 2，那么可以得到頂點(diǎn)1的兩個(gè)out edges在edges_values數(shù)組的下標(biāo)分別為1和2，那么out edges集合為{edges_values[1], edges_values[2]} = {(1,2), (1, 3)}。

2.2 CSC格式存儲(chǔ)

使用csc來存儲(chǔ)邊集合E的邊關(guān)系和值，與csr基本相同。首先將target vertex數(shù)組作為輸入數(shù)組進(jìn)行counting_sort，得到P和I，I為csc的columnptrs。使用P對(duì)E的source vertex數(shù)組和value數(shù)組進(jìn)行排序，生成了csc的rows和values。E以csc格式存儲(chǔ)的最終結(jié)果如下所示。

1.edges_values數(shù)組：是按列順序進(jìn)行排序后邊集合的值數(shù)組。

2.columnptrs數(shù)組：保存列在edges_values中的起始偏移地址，columnptrs[i]是第i列在edges_values中的起始偏移位置；

3.rows數(shù)組：列索引，rows[i]是edges_values[i]值對(duì)應(yīng)的邊的列的值。

通過csc獲取一個(gè)頂點(diǎn)的in edges類似于在csr中獲取out edges，不在贅述。

#p#

2.3 Graphlab圖的靜態(tài)存儲(chǔ)

Graphlab對(duì)圖的靜態(tài)存儲(chǔ)是同時(shí)采用了csr和csc格式。在graphlab中，會(huì)首先對(duì)邊集合按照csr方式進(jìn)行存儲(chǔ)（通過對(duì)source vertex進(jìn)行counting_sort），然后再建立csc格式，通過shuffle方式，在csc和csr之間進(jìn)行轉(zhuǎn)換。把csr和csc整合到一起，同時(shí)實(shí)現(xiàn)對(duì)頂點(diǎn)的out edges和in edges的快速索引。如下圖所示。

edges_value：同CSR中的rowptrs。

rowptrs：同CSR中的rowptrs。

columns：同CSR中的columns。

shuffleptrs：這個(gè)數(shù)組用于將按列順序排列的稀疏矩陣轉(zhuǎn)換為按行順序排列的稀疏矩陣。Shuffleptrs[i]表示按列順序排序的邊集合的第i條邊在edges_value數(shù)組中的下標(biāo)。

rows：同CSC中的rows。

columnptrs：同CSC中的columnptrs。

如上圖所示，在內(nèi)存中存儲(chǔ)邊集合E，需要維持邊的值數(shù)組，csr和csc。CSR有兩個(gè)整型數(shù)組，rowptrs和columns，分別用來存儲(chǔ)行偏移地址和列索引。CSC有三個(gè)整型數(shù)組，shuffleptrs、rows和columnptrs，分別存儲(chǔ)著從按列順序排序的稀疏矩陣到按行順序排列的稀疏矩陣轉(zhuǎn)換的下標(biāo)，行索引和列偏移地址，shuffleptrs和rows具有相同的下標(biāo)，可以合并成一個(gè)數(shù)組。

具體步驟如下：

E的原始輸入由三個(gè)相同長度的數(shù)組組成，source_arr、target_arr和data_arr，分別存儲(chǔ)著邊的source vertex、target vertex和邊的值。source vertex相當(dāng)于鄰接矩陣的行，target vertex相當(dāng)于鄰近矩陣的列。如果要形成最終的結(jié)果，需要以下這些步驟，才能形成上圖中的存儲(chǔ)。

1. counter_sort(source_arr, P, rowptrs)

2. sort(P, E)

//使用P按照行順序?qū)中的三個(gè)數(shù)組進(jìn)行排序,P數(shù)組是按照行的順序保存著E的下標(biāo)，

3. columns = target_arr

4. csr = {rowptrs, columns}

5. counter_sourt(target_arr, P, columnptrs)

6. sort(P, source_arr)

//對(duì)source_arr按列順序進(jìn)行排列，***作為行索引

7. rows = source_arr; shuffleptrs = P.

8. csc = {columnptrs, rows, shuffleptrs}

Graphlab中的具體類：

在graphlab中，圖的本地靜態(tài)存儲(chǔ)是由local_graph來實(shí)現(xiàn)，local_graph中保存圖使用了四個(gè)數(shù)據(jù)結(jié)構(gòu)：

std::vector<VertexData> vertices：存儲(chǔ)頂點(diǎn)數(shù)據(jù)的數(shù)組，頂點(diǎn)的ID為0到數(shù)組的長度。

std::vector<EdgeData> edges：存儲(chǔ)邊的值的數(shù)組，相當(dāng)于edges_values。

csr_type _csr_storage：表示csr，由csr_storage這個(gè)類來實(shí)現(xiàn)。

csc_type _csc_storage：表示csc，由csr_storage這個(gè)類來實(shí)現(xiàn)。

csr_storage中有兩個(gè)成員變量，分別是：

std::vector<sizetype> value_ptrs;

std::vector<valuetype> values;

當(dāng)csr_storage表示csr時(shí)，value_ptrs等同于rowptrs，是一個(gè)uint64_t數(shù)組；values等同于columns，也是一個(gè)uint64_t數(shù)組。

當(dāng)csr_storage表示csc時(shí)，value_ptrs等同于columnptrs，是一個(gè)uint64_t數(shù)組；values則被定義成std::vector< std::pair<lvid_type, edge_id_type> >，相當(dāng)于將rows和shuffleptrs存儲(chǔ)在同一個(gè)vector中。

3 存儲(chǔ)結(jié)構(gòu)

Graphlab實(shí)現(xiàn)對(duì)圖的動(dòng)態(tài)存儲(chǔ)也是基于csr和csc格式，不過在csr和csc的底層數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)上做了一些調(diào)整，將數(shù)組替換為分塊鏈表。如果實(shí)現(xiàn)對(duì)圖的動(dòng)態(tài)存儲(chǔ)，那么需要把底層的數(shù)據(jù)結(jié)構(gòu)從數(shù)組換成鏈表，但需要對(duì)原先在靜態(tài)圖存儲(chǔ)中所用的那套算法做些調(diào)整。

動(dòng)態(tài)存儲(chǔ)格式的CSR、CSC和邊的值數(shù)數(shù)組如下圖所示：

1. Edges是一個(gè)數(shù)組，數(shù)據(jù)結(jié)構(gòu)使用vector，只是將批量插入的邊的權(quán)值按順序放入到vector中。

2. CSR是由行迭代器數(shù)組rowIterators和columns組成。columns是一個(gè)分塊鏈表，表示按鄰近矩陣的行（即邊的source vertex）大小排序的列的鏈表，如上圖所示，Block的內(nèi)容如下，Block是固定長度的pair< uint64_t, uint64_t>數(shù)組，多個(gè)block組成一個(gè)鏈，pair的first是鄰接矩陣的列（即邊的target vertex），second是列所在的邊在edges數(shù)組中的位置。CSR的rowIterators是對(duì)鏈表的行建立索引，rowIterator[i]指向行i在columns中的起始位置偏移地址。

3. 對(duì)于CSC是有列迭代器數(shù)組colIterators和rows組成。Rows是一個(gè)分塊鏈表，表示按鄰接矩陣的列（即邊的target vertex）大小排序的行的鏈表，如上圖所示，Block的內(nèi)容如下，Block是固定長度的pair<uint64_t, uint64_t>的數(shù)組，多個(gè)block組成一個(gè)鏈，pair的first是鄰接矩陣的行（即邊的target vertex），second是行所在的邊在edges數(shù)組中的位置。colIterators是對(duì)鏈表的列建立索引，colIterators[j]指向列j在rows中的起始位置偏移地址。

#p#

4 實(shí)現(xiàn)步驟

源碼中對(duì)csr和csc的構(gòu)建和動(dòng)態(tài)插入的整體流程：

批量輸入的邊可以用三個(gè)數(shù)組來表示，source_vertex數(shù)組（邊的源頂點(diǎn)），target_vertex數(shù)組（邊的目標(biāo)頂點(diǎn)）和邊的值數(shù)組edge_values。

1. 對(duì)source_vertex數(shù)組進(jìn)行計(jì)數(shù)排序，輸出P1和rowptrs，P1是按行從小到大順序?qū)ource_vertex進(jìn)行排序后生成的序列數(shù)組；rowptrs[i]指向第i行在P1中的起始偏移地址，P1[rowptrs[i] + k ]表示第i行的第k個(gè)元素在edges數(shù)組中的位置，其中 0 <= k < (rowptrs[i + 1] - rowptrs[i])。

2. 對(duì)target_vertex數(shù)組進(jìn)行計(jì)數(shù)排序，輸出P2和colptrs，P2是按列從小到大順序?qū)arget_vertex進(jìn)行排序后生成的序列數(shù)組；colptrs[j]指向第j列在P2中的起始偏移地址，P2[colptrs[j] + k]表示第j列的第k個(gè)元素在edges數(shù)組中的位置，其中0 <= k < (colptrs[j + 1] - colptrs[j])；

3. 由于CSR的底層數(shù)據(jù)結(jié)構(gòu)是分塊鏈表和行迭代器數(shù)組指針，所以需要將計(jì)數(shù)排序后得到的rowptrs、P1和target_vertex轉(zhuǎn)化為迭代器數(shù)組和pair<col,pos>數(shù)組。分塊鏈表的block是固定長度的pair<col, pos>數(shù)組，所以利用P1和target_vertex來構(gòu)建pair<col, pos>數(shù)組csr_values，第i個(gè)輸入的邊在csr_values中的值為{target_vertex[P1[i]], length(edges) + P1[i]}。

3.1 如果圖為空，則用rowptrs和csr_values，來初始化CSR，即將csr_values中的值賦值給CSR的columns，然后將rowptrs的行起始位置轉(zhuǎn)化為columns中的迭代器，放入到rowIterators中。

3.2 如果圖不為空，則按行向CSR插入數(shù)據(jù)，一次插入一行，第i行在csr_values中的值是從csr_values[P1[i]]至csr_values[P1[i + 1]]這一段數(shù)據(jù)。如下圖所示的CSR，rowIterators是一個(gè)迭代器的數(shù)組，rowIterators[i]存放第i行在columns中的起始位置，rowIterators[i + 1]為第i行的結(jié)束位置也是第i + 1行的起始位置；columns是一個(gè)分塊鏈表。藍(lán)色為第i行的數(shù)據(jù)，橙色為i+1行的數(shù)據(jù)。綠色為需要新插入的第i行的數(shù)據(jù)。

往第i行插入新數(shù)據(jù)，CSR插入行的步驟如下：

A. 首先會(huì)找到rowIterators[i+1]所指向的第i行的結(jié)束位置Pos，將此block中位于Pos之后的第i+1行的數(shù)據(jù)段預(yù)先保存起來。

B. 將第i行的新數(shù)據(jù)拷貝到Pos之后位置上，如果新插入的數(shù)據(jù)過長，那么會(huì)創(chuàng)建一個(gè)或多個(gè)新的block來容納。

C. 將預(yù)先保存的第i+1行的數(shù)據(jù)重新拷貝到新插入數(shù)據(jù)之后。

如下圖所示：

D. 在上述操作完成之后，第i+1行的迭代器指針變?yōu)闊o效，指向的數(shù)據(jù)位置為第i行新插入的數(shù)據(jù)，所以要調(diào)整第i+1行的迭代器指針。

E. ***因?yàn)榘葱袑?shù)據(jù)插入到CSR中會(huì)產(chǎn)生一些空隙，如上圖block中的白色空格，所以會(huì)在所有行都插入后，進(jìn)行repack操作，將空白的內(nèi)存進(jìn)行壓縮，變?yōu)橄聢D所示：

CSC的處理類似于CSR，不在贅述，這種做法的只能支持動(dòng)態(tài)地批量插入，隨機(jī)插入的性能開銷太大。

5 Graphlab中相關(guān)的類

dynamic_block：圖的動(dòng)態(tài)存儲(chǔ)的底層數(shù)據(jù)結(jié)構(gòu)采用內(nèi)存塊的鏈表，可以進(jìn)行動(dòng)態(tài)的插入。Dynamic_block就是實(shí)現(xiàn)這個(gè)內(nèi)存塊的類，dynamic_block組成了一個(gè)塊的鏈表。

block_linked_list：分塊鏈表，是使用dynamic_block組成的一個(gè)單向鏈表。

dynamic_csr_storage：實(shí)現(xiàn)csr和csc動(dòng)態(tài)存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，將底層的數(shù)組替換為鏈表，然后使用鏈表的迭代器數(shù)組來實(shí)現(xiàn)記錄行或列的起始位置。

dynamic_local_graph：實(shí)現(xiàn)圖的動(dòng)態(tài)存儲(chǔ)的類，圖的動(dòng)態(tài)存儲(chǔ)針對(duì)的情況是批量更新，而不是隨機(jī)插入。

原文鏈接：http://my.oschina.net/zhengyang841117/blog/194826