Live data from Hacker News

The Cost of Scalability in Graph Processing

frankmcsherry.org

11–20 of 31 posts

Re: The Cost of Scalability in Graph Processing

#11

I'm concerned that articles like this paint multiprocessing in a bad light. Yes, there are issues like http://en.wikipedia.org/wiki/Amdahl's_law but many real-world tasks are "embarrassingly parallel” and it takes little effort to break them into segments that can be processed concurrently. After skimming the article, I’m thinking the real bottleneck here is latency since it mentions Hilbert curves. Currently network…

Of course networks are always going to be orders of magnitude slower. That's because we're already at the very point where sheer distance becomes a limiting factor to performance.

Remember Grace Hopper:

https://www.youtube.com/watch?v=JEpsKnWZrJ8

Re: The Cost of Scalability in Graph Processing

#12
While I understand the sentiment behind this post, I think it misses one crucial point: It costs time, effort, and very smart people to build the "Bugati"-like system as they describe, instead of the current systems (that are more like "Toyotas", to name one).

I haven't seen the paper yet, so I can't be sure, but I think the numbers might ignore many factors: First, you need some kind of abstract, exchangeable storage (e.g., protobufs) to work with the data in many languages. Third, there's the file-system and all its intricacies. Fourth, it's unlikely that any compute environment will be dedicated only to one application (there's scheduling, resource management, and all that, which means there are hidden costs to doing network IO due to contention, protocol quirks, etc.). And finally, any realistic application is more than just "solving" the problem in the fastest way possible. Requirements change all the time, new features will be added, the code needs to be readable, understandable, maintainable, etc.

It's possible to do all the above AND be super efficient, but it requires a tremendous level of understanding of a system at all levels that it can be quite challenging, and frankly, with business requirements, it's probably not worth the time. If there's a framework that gives you abstraction but compiles to the fastest possible specific implementation AND makes a programmer productive, I would love to read up more!

Re: The Cost of Scalability in Graph Processing

#13
post #8

Lots of people make the mistake of thinking there's only two vectors you can go to improve performance, high or wide. High - throw hardware at the problem, on a single machine Wide - Add more machines There's a third direction you can go, I call it "going deep". Today's programs run on software stacks so high and so abstract that we're just now getting around to redeveloping (again for like the 3rd or 4th time) softw…

Please turn this comment into a blogpost or a book.

> Bane's rule, you don't understand a distributed computing problem until you can get it to fit on a single machine first.

Excellent :)

Re: The Cost of Scalability in Graph Processing

#14
post #2

This raises so many questions that I can't even really comprehend that it worries me. Please, if there are well formed responses or dialogues that form based on this, somebody make sure to link them back. Very very interesting read.

The basic point is: You think your dataset is big, but it probably isn't. A well written C program running on a modern laptop can handle a few billion node sized graph dataset fine. Before paying for 128 cores running a "scalable" implementation, first check your dataset size. Is it in the terabytes? If not, you're probably fine running any computations on a single core. Google and Facebook need cluster computing sol…

In the article he's dealing with a graph of billions of edges - probably not billions of nodes. That's been my experience, too, with loading a graph in memory on a laptop: billions of edges and hundreds of millions of nodes is fine but getting close to being too much.

Re: The Cost of Scalability in Graph Processing

#15
If the dataset and/or computation fits in your laptop, why would you use a cluster framework?

If you want to use multi-core, why would you not use the pthread library instead of using Spark, GraphX etc. The authors never show a pthread comparison.

The article shows just one algorithm for toy datasets. For certain algorithms such as stochastic gradient descent, multiple-cores can process data in parallel and go through the data very quickly. Again, if everything fits in memory, doing a gradient descent on entire dataset will be much faster and give a better quality result. This fact is pretty much well known to end-users i.e. folks who actually try to solve big-data problems.

However, most papers use small datasets like twitter or MNIST because their convergence behavior is well-understood (rather than to demonstrate scaling).

Re: The Cost of Scalability in Graph Processing

#16
post #4

The GraphChi paper from OSDI 2012 made a similar observation: http://select.cs.cmu.edu/publications/paperdir/osdi2012-kyro... From the abstract: "In this work, we present GraphChi, a disk-based system for computing efficiently on graphs with billions of edges. By using a well-known method to break large graphs into small parts, and a novel parallel sliding windows method, GraphChi is able to execute several advanced…

There is another paper, XStream from SOSP 2013, which ran a facebook sized graph on a single machine. I wonder what is "hot" in this HotOS submission?

Re: The Cost of Scalability in Graph Processing

#17
post #8

Lots of people make the mistake of thinking there's only two vectors you can go to improve performance, high or wide. High - throw hardware at the problem, on a single machine Wide - Add more machines There's a third direction you can go, I call it "going deep". Today's programs run on software stacks so high and so abstract that we're just now getting around to redeveloping (again for like the 3rd or 4th time) softw…

Please turn this comment into a blogpost or a book. > Bane's rule, you don't understand a distributed computing problem until you can get it to fit on a single machine first. Excellent :)

You know what, I think I will. It's tied into a bunch of different threads, but if I plan it out, it could make a nice series of posts.

Re: The Cost of Scalability in Graph Processing

#18
post #17

Earlier quoted context omitted.

Please turn this comment into a blogpost or a book. > Bane's rule, you don't understand a distributed computing problem until you can get it to fit on a single machine first. Excellent :)

You know what, I think I will. It's tied into a bunch of different threads, but if I plan it out, it could make a nice series of posts.

It resonates strongly with me because I keep coming across clustered solutions where a single machine with appropriately designed software would work just as well or better.

Clusters have a habit of becoming their own reason for existence. Looking forward to your article. If you need a proofreader I'm game.

Scale up, scale out or scale in.

Re: The Cost of Scalability in Graph Processing

#19
post #8

Lots of people make the mistake of thinking there's only two vectors you can go to improve performance, high or wide. High - throw hardware at the problem, on a single machine Wide - Add more machines There's a third direction you can go, I call it "going deep". Today's programs run on software stacks so high and so abstract that we're just now getting around to redeveloping (again for like the 3rd or 4th time) softw…

I'd second the jacquesm's post: you should write a book or a blog post on those.

One of the reason I've noticed for everyone's wanting to use "distributed" and "cluster" stuffs is that we have no intuition/ experience on how much can be processed within the limit of a single machine: when someone start designing a data pipeline, even if they know how big (in term of GBs/TBs/ whatever criteria it is) the dataset is, they still don't know if it can fit in a machine or not. So the safe solution is to design a distributed system: if it doesn't fit, you throws more hardware at it. It's somewhat similar to the "no one got fired for buying IBM"

Re: The Cost of Scalability in Graph Processing

#20
Perhaps another takeaway from this article is that it'd be nice if more research papers benchmarked with vastly larger data sets.

Many researchers would love to do just that, of course. However, as many researchers will lament, it's not always easy to get 10+-figure node and 11+-figure edge data sets appropriate to a space being explored.

The best research benchmarks I see do compare to a single-core (often multithread or multiprocess) implementation. And they also show benchmark results on datasets of increasing sizes.

I agree with the authors that those sorts of papers aren't common enough, though. And we should strive to do better. Moreover, I agree that in practice in industry, many people over-optimize for horizontal scalability early, and/or do not realize potential savings and benefit by doing vertical optimizations after gaining initial scale.

Post reply on HN