6 ms·

One trillion edges: graph processing at Facebook scale [pdf]

201 points by mrry 11y ago

logicrime 11y ago
I kinda hate these papers that just humble-brag clusterized setups without providing any abstract insights. This doesn't bring me any closer to understanding graph data any better, but I'm now ready to begin installation of a multi-million-dollar cluster of machines and storage. The bit about k-means was interesting, but the rest was an irrelevant bore.
- cbsmith 11y ago
  The purpose of the paper isn't to help you to understand graph data better. Heck, this is a VLDB presentation. It is to help you to understand frameworks for working on graph data better. If you see it as a humble brag that is an irrelevant bore, you aren't the intended audience.
- Hytosys 11y ago
  Imagine being one of the five authors of this paper, browsing this comments section. It's natural to distance yourself from people when you're behind a keyboard, but for fuck's sake — these are your peers. If you're going to be critical, do it with attention and care.
  - lcswi 11y ago
    The people were not critized, the paper was.
  - logicrime 11y ago
    If you think the authors give half a shit what HackerNews think, you've missed the point.
- nl 11y ago
  Given than this is a paper for VLDB[1] (the conference on Very Large Databases) perhaps there is some small chance that your personal judgement of what is an insight or relevant is... wrong? Also, your idea that it is a humble-brag to talk about a computer cluster at VLDB seems more indicative of a lack of knowledge on your part rather than a lack of "abstract insights". Irrelevant bore indeed. [1] http://www.vldb.org/2015/ http://www.vldb.org/2015/
  - chimtim 11y ago
    VLDB accepts 150 papers and SIGMOD perhaps another 150. This is just top tier. I am pretty sure science can live without about more than 50% of those papers. I disagree with the tone of the original comment. But I do not disagree with the sentiment. Just having a large installation does not make it interesting. However, Google's large systems almost always push the boundaries of science -- MapReduce, GFS, Spanner, Distbelief and have been a joy to read.
Smerity 11y ago
If anyone is interested in graph processing at scale, the largest Web Data Commons Hyperlink Graph[1] (created from Common Crawl[2] data) is 3.5 billion web pages and 128 billion hyperlinks. To my knowledge, it's the largest freely available real world based graph dataset. Numerous graph systems have been made that can scale to this data, frequently on just a single powerful node, including FlashGraph[3] (using SSDs for high), Frank McSherry's single laptop Rust implementation[4], and Dato's GraphLab Create[5]. As Frank McSherry points out at [6], there's a lot of room to improve state of the art in graph computation systems, especially as the current academic evaluations are broken. (where "broken" means that a single threaded graph system written in Rust on a laptop can beat the benchmarks created by a cluster of high performance machines) [1]: http://webdatacommons.org/hyperlinkgraph/ http://webdatacommons.org/hyperlinkgraph/ [2]: http://commoncrawl.org/ http://commoncrawl.org/ [3]: https://github.com/icoming/FlashGraph https://github.com/icoming/FlashGraph [4]: http://www.frankmcsherry.org/graph/scalability/cost/2015/02/04/COST2.html http://www.frankmcsherry.org/graph/scalability/cost/2015/02/... [5]: https://twitter.com/CommonCrawl/status/623615774909857792 https://twitter.com/CommonCrawl/status/623615774909857792 [6]: http://blog.commoncrawl.org/2015/04/evaluating-graph-computation-systems-performance-and-scale/ http://blog.commoncrawl.org/2015/04/evaluating-graph-computa...
- shoo 11y ago
  That post from Frank McSherry is excellent. His earlier post [1] is also worth reading. I was curious to read more about the Hilbert ordering of edges, and the delta-encoding. There is a related article from Yzelman & Bisseling titled "A cache-oblivious sparse matrix–vector multiplication scheme based on the Hilbert curve"[2] which discusses Hilbert ordering combined with a delta-encoded version of the usual CSR encoding for sparse matrices [3]. > A Hilbert curve thus can be projected on any [2^m * 2^m] matrix, which in turn can embed the sparse matrix A, thus imposing a 1D ordering on its nonzeroes. The largest sparse matrix considered for the experimental results from this article was "wikipedia-20070206" with 45,030,389 nonzeros (aka weighted edges). Ignoring the weights, this is about 1/3000th of the size of the 128 billion edge graph that McSherry mentions in his post. Yzelman & Bisseling also measure the additional preprocessing time required to convert their sparse matrices using the Hilbert-ordered delta-encoded CSR scheme -- this is roughly 30x the time for a single matrix-vector product evaluation [4]. Clearly this approach is only going to pay off if one plans to do a bunch of analysis using the single matrix / graph, without changing the matrix / graph. McSherry mentions a similar issue but points out that he could preprocess the graph using his approach faster than he could download the data, so the preprocessing speed wasn't really an issue. [1] http://www.frankmcsherry.org/graph/scalability/cost/2015/01/15/COST.html http://www.frankmcsherry.org/graph/scalability/cost/2015/01/... [2] https://lirias.kuleuven.be/bitstream/123456789/400709/1/yzelman11c-pp.pdf https://lirias.kuleuven.be/bitstream/123456789/400709/1/yzel... [3] sparse matrices are a fairly obvious representation of directed graphs with edge weights, I searched for an article about sparse matrices as I am more familiar with linear algebra than graph processing. [4] edit: perhaps an crude intuitive way to think about "30x matvec products" in the context of graph algorithms would be "about one pagerank", as each pagerank iteration is doing a matvec product and a bit of other stuff, and McSherry talks about 10 or 20 iterations per pagerank evaluation.
anotherangrydev 11y ago
>we were able to execute PageRank on over a trillion social connections in less than 3 minutes per iteration with only 200 machines Colour me skeptical, that's around 28M edges per second per machine.
- cbsmith 11y ago
  Let's reframe that as ~1700 instructions per edge. Seem more plausible? These are 16 core machines with 10GbE links. Each core is processing maybe 2 million edges per second with highly data parallel instructions. Ignoring hyperthreading, if these are 3GHz cores (pretty conservative), that means you are burning ~1500 cycles per edge to process an edge. You've got 2 FP ALU's and 2 integer ALU's in each core, not to mention the AGU. You've got prefetchers and completion units that are designed to handle 4-6 instructions per cycle, and that's not for no reason. You can get a lot of work done in one core with just 1000 cycles, let alone 1500. So I'm not so sure why that would seem incredible.
  - deleted 11y ago
    [deleted]
  - anotherangrydev 11y ago
    Their test machines have 16-cores. They're running 2.9Gops/core. Plausible, yeah. I'm not used to see real things achieve almost 100% efficiency, sounds really good.
    - cbsmith 11y ago
      Data parallel problems are essentially the use case that should allow you to get to 100% efficiency. The hardware/software just aren't going to get it easier than that. In this case, I'd speculate that you'd not even need 50% efficiency to get this result.
    - cbsmith 11y ago
      To provide perhaps more perspective, here's a paper using 2004 technology: http://www.leonidzhukov.net/papers/ParallelPageRank-2004.pdf http://www.leonidzhukov.net/papers/ParallelPageRank-2004.pdf With 70 machines & 140 processors, they did pagerank over 6.6 billion edges in 35 minutes. Using 285% the machines, you'd expect them to be able to do it in 12.25 minutes. Moore's Law should put each machine at 160x more powerful, and with 300x the edges they are finishing in 19 minutes. So we've improved by 2x over an 11 year-old software stack that we've long since abandoned for better approaches, using a hardware stack that is much more optimized for SIMD computations than the 11 year-old hardware.
Xyik 11y ago
I thought facebook was located at 1 Hacker Way not Hacker Lane

201 points by mrry 11y ago

I kinda hate these papers that just humble-brag clusterized setups without providing any abstract insights. This doesn't bring me any closer to understanding graph data any better, but I'm now ready to begin installation of a multi-million-dollar cluster of machines and storage. The bit about k-means was interesting, but the rest was an irrelevant bore.

cbsmith 11y ago
The purpose of the paper isn't to help you to understand graph data better. Heck, this is a VLDB presentation. It is to help you to understand frameworks for working on graph data better. If you see it as a humble brag that is an irrelevant bore, you aren't the intended audience.
Hytosys 11y ago
Imagine being one of the five authors of this paper, browsing this comments section. It's natural to distance yourself from people when you're behind a keyboard, but for fuck's sake — these are your peers. If you're going to be critical, do it with attention and care.
- lcswi 11y ago
  The people were not critized, the paper was.
- logicrime 11y ago
  If you think the authors give half a shit what HackerNews think, you've missed the point.
nl 11y ago
Given than this is a paper for VLDB[1] (the conference on Very Large Databases) perhaps there is some small chance that your personal judgement of what is an insight or relevant is... wrong? Also, your idea that it is a humble-brag to talk about a computer cluster at VLDB seems more indicative of a lack of knowledge on your part rather than a lack of "abstract insights". Irrelevant bore indeed. [1] http://www.vldb.org/2015/ http://www.vldb.org/2015/
- chimtim 11y ago
  VLDB accepts 150 papers and SIGMOD perhaps another 150. This is just top tier. I am pretty sure science can live without about more than 50% of those papers. I disagree with the tone of the original comment. But I do not disagree with the sentiment. Just having a large installation does not make it interesting. However, Google's large systems almost always push the boundaries of science -- MapReduce, GFS, Spanner, Distbelief and have been a joy to read.

Smerity 11y ago

If anyone is interested in graph processing at scale, the largest Web Data Commons Hyperlink Graph[1] (created from Common Crawl[2] data) is 3.5 billion web pages and 128 billion hyperlinks. To my knowledge, it's the largest freely available real world based graph dataset. Numerous graph systems have been made that can scale to this data, frequently on just a single powerful node, including FlashGraph[3] (using SSDs for high), Frank McSherry's single laptop Rust implementation[4], and Dato's GraphLab Create[5]. As Frank McSherry points out at [6], there's a lot of room to improve state of the art in graph computation systems, especially as the current academic evaluations are broken. (where "broken" means that a single threaded graph system written in Rust on a laptop can beat the benchmarks created by a cluster of high performance machines) [1]: http://webdatacommons.org/hyperlinkgraph/ http://webdatacommons.org/hyperlinkgraph/ [2]: http://commoncrawl.org/ http://commoncrawl.org/ [3]: https://github.com/icoming/FlashGraph https://github.com/icoming/FlashGraph [4]: http://www.frankmcsherry.org/graph/scalability/cost/2015/02/04/COST2.html http://www.frankmcsherry.org/graph/scalability/cost/2015/02/... [5]: https://twitter.com/CommonCrawl/status/623615774909857792 https://twitter.com/CommonCrawl/status/623615774909857792 [6]: http://blog.commoncrawl.org/2015/04/evaluating-graph-computation-systems-performance-and-scale/ http://blog.commoncrawl.org/2015/04/evaluating-graph-computa...

shoo 11y ago
That post from Frank McSherry is excellent. His earlier post [1] is also worth reading. I was curious to read more about the Hilbert ordering of edges, and the delta-encoding. There is a related article from Yzelman & Bisseling titled "A cache-oblivious sparse matrix–vector multiplication scheme based on the Hilbert curve"[2] which discusses Hilbert ordering combined with a delta-encoded version of the usual CSR encoding for sparse matrices [3]. > A Hilbert curve thus can be projected on any [2^m * 2^m] matrix, which in turn can embed the sparse matrix A, thus imposing a 1D ordering on its nonzeroes. The largest sparse matrix considered for the experimental results from this article was "wikipedia-20070206" with 45,030,389 nonzeros (aka weighted edges). Ignoring the weights, this is about 1/3000th of the size of the 128 billion edge graph that McSherry mentions in his post. Yzelman & Bisseling also measure the additional preprocessing time required to convert their sparse matrices using the Hilbert-ordered delta-encoded CSR scheme -- this is roughly 30x the time for a single matrix-vector product evaluation [4]. Clearly this approach is only going to pay off if one plans to do a bunch of analysis using the single matrix / graph, without changing the matrix / graph. McSherry mentions a similar issue but points out that he could preprocess the graph using his approach faster than he could download the data, so the preprocessing speed wasn't really an issue. [1] http://www.frankmcsherry.org/graph/scalability/cost/2015/01/15/COST.html http://www.frankmcsherry.org/graph/scalability/cost/2015/01/... [2] https://lirias.kuleuven.be/bitstream/123456789/400709/1/yzelman11c-pp.pdf https://lirias.kuleuven.be/bitstream/123456789/400709/1/yzel... [3] sparse matrices are a fairly obvious representation of directed graphs with edge weights, I searched for an article about sparse matrices as I am more familiar with linear algebra than graph processing. [4] edit: perhaps an crude intuitive way to think about "30x matvec products" in the context of graph algorithms would be "about one pagerank", as each pagerank iteration is doing a matvec product and a bit of other stuff, and McSherry talks about 10 or 20 iterations per pagerank evaluation.

anotherangrydev 11y ago

>we were able to execute PageRank on over a trillion social connections in less than 3 minutes per iteration with only 200 machines Colour me skeptical, that's around 28M edges per second per machine.

cbsmith 11y ago
Let's reframe that as ~1700 instructions per edge. Seem more plausible? These are 16 core machines with 10GbE links. Each core is processing maybe 2 million edges per second with highly data parallel instructions. Ignoring hyperthreading, if these are 3GHz cores (pretty conservative), that means you are burning ~1500 cycles per edge to process an edge. You've got 2 FP ALU's and 2 integer ALU's in each core, not to mention the AGU. You've got prefetchers and completion units that are designed to handle 4-6 instructions per cycle, and that's not for no reason. You can get a lot of work done in one core with just 1000 cycles, let alone 1500. So I'm not so sure why that would seem incredible.
- deleted 11y ago
  [deleted]
- anotherangrydev 11y ago
  Their test machines have 16-cores. They're running 2.9Gops/core. Plausible, yeah. I'm not used to see real things achieve almost 100% efficiency, sounds really good.
  - cbsmith 11y ago
    Data parallel problems are essentially the use case that should allow you to get to 100% efficiency. The hardware/software just aren't going to get it easier than that. In this case, I'd speculate that you'd not even need 50% efficiency to get this result.
  - cbsmith 11y ago
    To provide perhaps more perspective, here's a paper using 2004 technology: http://www.leonidzhukov.net/papers/ParallelPageRank-2004.pdf http://www.leonidzhukov.net/papers/ParallelPageRank-2004.pdf With 70 machines & 140 processors, they did pagerank over 6.6 billion edges in 35 minutes. Using 285% the machines, you'd expect them to be able to do it in 12.25 minutes. Moore's Law should put each machine at 160x more powerful, and with 300x the edges they are finishing in 19 minutes. So we've improved by 2x over an 11 year-old software stack that we've long since abandoned for better approaches, using a hardware stack that is much more optimized for SIMD computations than the 11 year-old hardware.

Xyik 11y ago

I thought facebook was located at 1 Hacker Way not Hacker Lane