Graphlab怎么實現(xiàn)分析圖的存儲

Graphlab怎么實現(xiàn)分析圖的存儲，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

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

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

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

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

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

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

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

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

1.1 csr和csc格式介紹

csr是使用三個數(shù)組來表示一個稀疏矩陣，稀疏矩陣用A表示，三個數(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 = 

假設下標都從0開始，那么行是{0,1,2}，列也是{0,1,2}；稀疏矩陣A的csr格式就可以用如下三個數(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)。

關于csr的詳細描述見：http://web.eecs.utk.edu/~dongarra/etemplates/node373.html

1.2 計數(shù)排序

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

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

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

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

運行結(jié)果：

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

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

第15-16的運行步驟如下，總共有：

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

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

這三個數(shù)組之間的關系如下：

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

2 使用csr和csc存儲圖

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

因為稀疏矩陣的csr存儲格式是對row進行壓縮，可以根據(jù)row來快速對稀疏矩陣的某一行進行檢索，所以使用csr來對out_edges進行檢索（邊(v,w)是頂點v的out edges,頂點v對于邊(v,w)相當于行）。同理，稀疏矩陣的csc存儲格式是對column進行壓縮，可以根據(jù)column來快速對稀疏矩陣的某一列進行檢索，所以使用csc對in_edges進行檢索。

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

2.1 CSR格式存儲

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

假設E中邊的輸入順序如下所示：

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

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

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

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

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

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

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

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

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

拿上面的例子，頂點1的out edges的數(shù)目為rowptrs[2] &ndash; rowptrs[1] = 2，那么可以得到頂點1的兩個out edges在edges_values數(shù)組的下標分別為1和2，那么out edges集合為{edges_values[1], edges_values[2]} = {(1,2), (1, 3)}。

2.2 CSC格式存儲

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

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

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

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

通過csc獲取一個頂點的in edges類似于在csr中獲取out edges，不在贅述。

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

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

edges_value：同CSR中的rowptrs。

rowptrs：同CSR中的rowptrs。

columns：同CSR中的columns。

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

rows：同CSC中的rows。

columnptrs：同CSC中的columnptrs。

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

具體步驟如下：

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

1. counter_sort(source_arr, P, rowptrs)

2. sort(P, E)

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

3. columns = target_arr

4. csr = {rowptrs, columns}

5. counter_sourt(target_arr, P, columnptrs)

6. sort(P, source_arr)

//對source_arr按列順序進行排列，***作為行索引

7. rows = source_arr; shuffleptrs = P.

8. csc = {columnptrs, rows, shuffleptrs}

Graphlab中的具體類：

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

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

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

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

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

csr_storage中有兩個成員變量，分別是：

std::vector<sizetype> value_ptrs;

std::vector<valuetype> values;

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

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

3 存儲結(jié)構

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

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

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

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

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

4 實現(xiàn)步驟

源碼中對csr和csc的構建和動態(tài)插入的整體流程：

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

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

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

3. 由于CSR的底層數(shù)據(jù)結(jié)構是分塊鏈表和行迭代器數(shù)組指針，所以需要將計數(shù)排序后得到的rowptrs、P1和target_vertex轉(zhuǎn)化為迭代器數(shù)組和pair<col,pos>數(shù)組。分塊鏈表的block是固定長度的pair<col, pos>數(shù)組，所以利用P1和target_vertex來構建pair<col, pos>數(shù)組csr_values，第i個輸入的邊在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是一個迭代器的數(shù)組，rowIterators[i]存放第i行在columns中的起始位置，rowIterators[i + 1]為第i行的結(jié)束位置也是第i + 1行的起始位置；columns是一個分塊鏈表。藍色為第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ù)段預先保存起來。

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

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

如下圖所示：

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

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

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

5 Graphlab中相關的類

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

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

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

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

看完上述內(nèi)容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業(yè)資訊頻道，感謝您對億速云的支持。