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

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

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

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

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

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

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

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

1.1 csr和csc格式介紹

csr是使用三個(gè)數(shù)組來表示一個(gè)稀疏矩陣，稀疏矩陣用A表示，三個(gè)數(shù)組分別是values、rowptrs和columns；values中按行順序存儲著A中的非零單元的值。Columns中存儲著values數(shù)組中的單元的列索引，values(k) = A(i, j)，則columns[k] = j。Rowptrs中存儲著行在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中按列順序存儲著A中的非零值；rows中存儲著values數(shù)組中單元的行索引,values(k) = A(i, j),則rows(k) = i；columnptrs中存儲著列在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ù)。對每一個(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ù)組的長度，是按從小到大對原始數(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ù)組中存儲著整型值（可能有重復(fù)），如下圖所示：

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

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

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

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

***P數(shù)組存儲著排序后的數(shù)值在原數(shù)組中的下標(biāo)。c數(shù)組中的每個(gè)單元c[i]中則存儲著在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存儲圖

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

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

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

2.1 CSR格式存儲

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

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

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

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

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

2. 使用P對輸入邊集合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)對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]值對應(yīng)的邊的列的值。如edges_values[2]的列為columns[2]，等于3。

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

拿上面的例子，頂點(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格式存儲

使用csc來存儲邊集合E的邊關(guān)系和值，與csr基本相同。首先將target vertex數(shù)組作為輸入數(shù)組進(jìn)行counting_sort，得到P和I，I為csc的columnptrs。使用P對E的source vertex數(shù)組和value數(shù)組進(jìn)行排序，生成了csc的rows和values。E以csc格式存儲的最終結(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]值對應(yīng)的邊的列的值。

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

#p#

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

Graphlab對圖的靜態(tài)存儲是同時(shí)采用了csr和csc格式。在graphlab中，會首先對邊集合按照csr方式進(jìn)行存儲（通過對source vertex進(jìn)行counting_sort），然后再建立csc格式，通過shuffle方式，在csc和csr之間進(jìn)行轉(zhuǎn)換。把csr和csc整合到一起，同時(shí)實(shí)現(xiàn)對頂點(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)存中存儲邊集合E，需要維持邊的值數(shù)組，csr和csc。CSR有兩個(gè)整型數(shù)組，rowptrs和columns，分別用來存儲行偏移地址和列索引。CSC有三個(gè)整型數(shù)組，shuffleptrs、rows和columnptrs，分別存儲著從按列順序排序的稀疏矩陣到按行順序排列的稀疏矩陣轉(zhuǎn)換的下標(biāo)，行索引和列偏移地址，shuffleptrs和rows具有相同的下標(biāo)，可以合并成一個(gè)數(shù)組。

具體步驟如下：

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

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)

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

7. rows = source_arr; shuffleptrs = P.

8. csc = {columnptrs, rows, shuffleptrs}

Graphlab中的具體類：

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

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

std::vector<EdgeData> edges：存儲邊的值的數(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存儲在同一個(gè)vector中。

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

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

動(dòng)態(tài)存儲格式的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是對鏈表的行建立索引，rowIterator[i]指向行i在columns中的起始位置偏移地址。

3. 對于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是對鏈表的列建立索引，colIterators[j]指向列j在rows中的起始位置偏移地址。

#p#

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

源碼中對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. 對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. 對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. 首先會找到rowIterators[i+1]所指向的第i行的結(jié)束位置Pos，將此block中位于Pos之后的第i+1行的數(shù)據(jù)段預(yù)先保存起來。

B. 將第i行的新數(shù)據(jù)拷貝到Pos之后位置上，如果新插入的數(shù)據(jù)過長，那么會創(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中會產(chǎn)生一些空隙，如上圖block中的白色空格，所以會在所有行都插入后，進(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)存儲的底層數(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)存儲的數(shù)據(jù)結(jié)構(gòu)，將底層的數(shù)組替換為鏈表，然后使用鏈表的迭代器數(shù)組來實(shí)現(xiàn)記錄行或列的起始位置。

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

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