search

jasperzhong / read-papers-and-code

My paper/code reading notes in Chinese
43 stars 3 forks source link

ICDE '15 | LLAMA: Efficient graph analytics using Large Multiversioned Arrays #300

Closed jasperzhong closed 2 years ago

jasperzhong commented 2 years ago

https://web.archive.org/web/20180723172259id_/https://dash.harvard.edu/bitstream/handle/1/22713050/17549207.pdf?sequence=1

jasperzhong commented 2 years ago

image

总之，维护的数据结构是

  1. one vertex table. shared by all snapshots.
  2. multiple edge tables, one per snapshot.

其实我感觉算是一个树状结构...虽然作者说自己是CSR，但也的确采用了CSR. 怎么说，感觉是delta CSR，所以我觉得算是tree + CSR. 但其实每次update都是增加一个snapshot，然后只保存delta信息.

比如上图，snapshot 1是加了一条边(2, 1)，删了一条边 (2, 0). 首先拷贝indirection tables（可以理解为树根），只修改了vertex 2的信息，所以拷贝page 1，然后修改里面vertex 2的信息（snapshot ID, offset to edge table），然后edge table也是delta保存，一样的地方直接就link过去（比如图中的C: 0, 3，表示后面和edge table 0 index 3开始的地方一样）. deletion是用一个deletion table表示，但这样好像有点问题？那么后面取snapshot 0的时候，(2, 0) 这条边还是标记为deleted. 费解. 后面会merge snapshots，节约空间.

snapshot也可以存在disk上，格式与in-memory一样. access时候用mmap（mmap只在page fault的时候将对应的page放到memory里面，所以没有访问到的就不需要load）. 原来如此，这就是LLAMA如何处理out-of-memory的...

后面有提到usage ：支持全图查询和从特定vertex查询（使用最近的数据或者一个特定的snapshot）. 他们的输入就是a batch of edges.

做了很多优化，page aligned什么的.. 过.

实验终于是以查询为主了，考虑了PageRank, BFS和三角形计数. 他们考虑了两个数据集，一个是LiveJournal，只有601MB，还有一个是Twitter,有11.9GB. 然后考虑了两个机器，一个是BigMem，有256GB RAM，另一个是commodity，只有8GB RAM. 所以Twitter数据集是无法放进memory的. 所以就有了这个结果. 其中，GraphLab和GreenMarl都是in-memory处理，而GraphChi和X-Stream应该是可以handle out-of-memory. 可以看到LLAMA速度还行. 但LLAMA用了mmap，所以速度更快. 这里LLAMA应该都是没用到update，都是一开始就把图load好.

image

下面一个实验才evaluate了online update. 他们把twitter数据集80% edges作为第一个snapshot（那么就是一开始就load），其余20% edges作为剩下n-1次data ingest. #snapshots数量从1-201不等. 下面几个图可以看到LLAMA赢麻了. 那么，他们这里说的BFS, PageRank的处理时间是啥，是指处理graph完全弄好后再做算法的时间吗？论文里没提. 随着snapshots数量增多，可以看到计算效率在下降，符合预期，因为数据结构更多fragramented.

image

——————————————————————

所以给人感觉是，他们搞streaming graph的motivation似乎是内存放不下全部的图....其次才是online query啥的.

不过既然都是静态图算法，所以他们维护multi-snapshot的目的是啥？

jasperzhong commented 2 years ago

cuSTINGER #299 对其评价

Lastly, LLama [14] offers an alternative data structure for dynamic graph algorithms that is based on checkpointing the network as updates are added. An adjacency list of a vertex might be split across multiple checkpoints in LLama. This makes the LLama data structure an unlikely candidate for the GPU as accessing an edge in each check will cause low system utilization.

有意思.