Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Cost of Scalability in Graph Processing

frankmcsherry.org

Post reply on HN
Print view View original

21–30 of 31 posts

Re: The Cost of Scalability in Graph Processing

#21

Post by ploxiln »

xtacy wrote: post #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 storag…

I've worked at a place had a good excuse for using a real "big data" processing system - a large hadoop cluster on bare metal - because the dataset was way bigger than would fit on a single machine. The cluster had over 20 machines that had 10 or so 3TB disks each, and a large computation might use half the dataset. Even if you could put all the data in a storage appliance and read it from a single machine, you needed the separate memories and data busses to just sift through the data and keep the relevant bits in non-swapped memory in less than a day.

I think the important lesson from this paper, and which a few researchers also learned from our cluster, is that the amount of inefficiency that can be in software, and then removed by competent programming, is astronomical these days. You see many arguments like yours - programmer time is expensive, you need to be a super expensive expert, just pay for the systems, blah blah... it underestimates the cost of the ridiculous inefficiency, and overestimates the cost of competency.

Even scientists in-experienced with serious programming can often get appreciably better at writing their data processing jobs before their first job finishes when you're dealing with the really big data. What a lot of people call big data isn't even big data. They'd rather go through the motions of setting up and using a big-data processing system and using it poorly, than learn better software engineering skills, even if that would take less of (theirs + others) time, amortized over the next few months of their work.

This isn't toyota vs bugatti. This is... freight train with conductor, engineer, station staff, and one car of payload... vs getting a drivers license for a large van.

Re: The Cost of Scalability in Graph Processing

#22

Post by taeric »

herdrick wrote: post #14
arjunnarayan wrote: post #3

Earlier quoted context omitted.

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.

Aren't most of these algorithms limited by the edges?

Re: The Cost of Scalability in Graph Processing

#23

Post by frankmcsherry »

chimtim wrote: post #16
scott_s wrote: 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?

The thrust of the post wasn’t meant to be that it is surprising that you can even do these things on one core; sorry if it came across that way.

Rather, it’s that when doing the work on one core (with a way simple implementation) you go faster than many of the measurements that popular scalable systems put forward as evidence that they improve on the state of the art. Which sort of invalidates that evidence. Some of the papers end up left with fairly scant evidence, which should be a serious issue for researchers.

GraphChi and X-Stream (http://infoscience.epfl.ch/record/188535) are much more sophisticated implementations, ones you might not be embarrassed to be beaten by, so they don’t make the same point. And they aren’t any faster than the systems above, and so have the same issues (though perhaps less explaining to do).

Re: The Cost of Scalability in Graph Processing

#24

Post by dmoney »

bane wrote: 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…

An example of "scaling in" is this talk, "How to speed up a Python program 114,000 times": https://m.youtube.com/watch?v=e08kOj2kISU

Re: The Cost of Scalability in Graph Processing

#25

Post by hga »

NhanH wrote: post #19
bane wrote: 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, t…

I strongly suspect a lot of this is a problem of the "no one got fired for buying IBM" type. Surely many if not most organizations have much greater faith in their ability to go high and wide than deep. The former requires opening their checkbook, the latter is "magic" from wizards/non-managers who are notoriously difficult for many to manage, assuming they really even care that much.

You're also looking at this from the viewpoint of the good of the organization, whereas we know that's generally not how things play out in the long term, e.g. Pournelle's Iron Law of Bureaucracy: http://www.jerrypournelle.com/reports/jerryp/iron.html

The deep approach results in a different balance of resources in an organization, which inevitably produces losers, like those responsible for those big fleets of machines. I can't help but notice that half of your examples were done on surplus desktop machines, and if I remember correctly jacquesm's latest reported experience was with a company that was desperate.

This is not to pour cold water on the deep approach, just to suggest in many situation how to target your advocacy and opportunities, to be prepared for blowback if you embarrass people expending massive resources for what you can fit on one idle surplus desktop, etc.

Re: The Cost of Scalability in Graph Processing

#26

Post by jerf »

NhanH wrote: post #19
bane wrote: 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, t…

We probably need to collectively start doing the same thing that people do when they ask "How can I speed up my code?"... "Profile, profile, profile."

"How can I make my code cloud-scale?" "Profile, profile, profile." First make it fast. Not hyper-ultra fast, optimized to within an inch of its life with embedded ASM and crazy data structures, but as far as you can get it while still writing simple, sensible code. Then, only if you have a problem do you even worry about whether it should go cloud-scale, and by the time you're done with this you'll probably already have a good idea how to partition the problem better because you learned a lot more about it while profiling.

Re: The Cost of Scalability in Graph Processing

#27

Post by gaalze »

frankmcsherry wrote: post #23
chimtim wrote: post #16

Earlier quoted context omitted.

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?

The thrust of the post wasn’t meant to be that it is surprising that you can even do these things on one core; sorry if it came across that way. Rather, it’s that when doing the work on one core (with a way simple implementation) you go faster than many of the measurements that popular scalable systems put forward as evidence that they improve on the state of the art. Which sort of invalidates that evidence. Some of…

So you are saying a naive implementation on a single core is showing that people are prematurely scaling graph processing?

Re: The Cost of Scalability in Graph Processing

#28

Post by PaulHoule »

frankmcsherry wrote: post #23
chimtim wrote: post #16

Earlier quoted context omitted.

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?

The thrust of the post wasn’t meant to be that it is surprising that you can even do these things on one core; sorry if it came across that way. Rather, it’s that when doing the work on one core (with a way simple implementation) you go faster than many of the measurements that popular scalable systems put forward as evidence that they improve on the state of the art. Which sort of invalidates that evidence. Some of…

I had to propagate colors across a graph with a billion or so edges and had an easy time doing it in-memory in Java with a 32GB laptop and sub-byte data structures. In fact, it takes more time to serialize and deserialize the data than it takes to do the actual calculation.

I'd say, however, the trend is towards data sets being much bigger and I break non-scalable tools frequently in the data profiling process; you can extend the non-scalable ways of doing it by using multiple cores (which is sometimes easy) or SIMD instructions or the GPU. I have even sometimes gone down the rabbit hole of optimizing something non-scalable and hitting the wall. So I am using scalable systems increasingly.

Re: The Cost of Scalability in Graph Processing

#29

Post by agumonkey »

bane wrote: 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…

Talking about memory, this is the kind of articles that I love to read http://sites.utexas.edu/jdm4372/2010/11/11/optimizing-amd-op...

Trying to get the most out of the machine/arch you have.

Re: The Cost of Scalability in Graph Processing

#30

Post by scott_s »

frankmcsherry wrote: post #23
chimtim wrote: post #16

Earlier quoted context omitted.

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?

The thrust of the post wasn’t meant to be that it is surprising that you can even do these things on one core; sorry if it came across that way. Rather, it’s that when doing the work on one core (with a way simple implementation) you go faster than many of the measurements that popular scalable systems put forward as evidence that they improve on the state of the art. Which sort of invalidates that evidence. Some of…

I don't think it's accurate to say it's a different point, but it's a weaker version. And I don't feel that the GraphChi folks have any explaining to do, as I would expect that using a more general framework to solve a problem will have some performance penalty over an expert hand-coding a solution. What that performance penalty would buy us (hopefully) is it's quicker to write the application, and perhaps easier to port elsewhere.

But, I'm also not an expert in graph algorithms, so it's difficult for me to evaluate how much domain knowledge you needed to implement yours.

Post reply on HN