News for hackers. Stuff that matters.
Re:Bigger data; same laptop by eklavya on Thursday February 05, 2015 @04:36AM (#9002395)
All that investment and involvement, those big systems have got to be good for somethings! Please can anybody knowledgable share some insights? mrry?
Re:Bigger data; same laptop by mrry on Thursday February 05, 2015 @10:19AM (#9003604)
Our point in the COST paper was neither that distributed computation systems are bad per se, nor that a laptop is a fine substitute for many of the real-world deployments of distributed systems.

What these posts rail against is a tendency (post-MapReduce/Hadoop) to motivate and evaluate distributed systems solely in terms of their batch performance. This is a particularly common problem in graph processing research, where 2008-era general-purpose systems (i.e. Hadoop) have terrible performance, and so provide a straw-man baseline that a reasonably competent grad student should have had no difficulty in outperforming.

"Does my new system outperform a single thread?" seems like a proper hypothesis to test for a distributed system that claims only a performance motivation. Instead our grad student finds that there is a long list of peer-reviewed systems to compare against, and doing that should be enough, right? It would be fine if those systems had been tested against the first hypothesis, but in most cases they have not, so the new system can be much worse than a single thread (for a small set of benchmarks) and this will go undetected. The COST work is a remedy for this issue.

To return to your original question, I do think that distributed systems are good for some things. First, the OP concerns running graph algorithms on genuinely big data: 128 billion edges, and 3.5 billion vertices. A distributed system should be able to outperform Frank's laptop on that graph, and hopefully this post will encourage developers of new systems to aim higher and evaluate their systems on this scale of data.

The second is that distributed systems offer far more than pure batch performance. For example, geo-distribution is critical to providing a good user experience in web properties; and serving interactive queries with low latency and high availability is a particular interest of mine. We touched on the first part in the Naiad paper [1], and I expect this will become especially important for inference in online learning systems [2]. Hopefully the COST work will force the authors of these systems to try harder in their implementation, and we will all benefit as a result.

[1] http://dl.acm.org/citation.cfm?id=2522738

[2] http://www.cidrdb.org/cidr2015/Papers/CIDR15_Paper19u.pdf

Re:Bigger data; same laptop by eklavya on Thursday February 05, 2015 @01:27PM (#9004895)
Thanks a lot for the explanation :)

My concern was that I saw the blog did the run on real life big(actually big) data and outperform everything on the market. This got me thinking, are we still not there on the problem size/computing power curve so as to justify use of distributed computing?

Of course distributed makes sense in a lot of places specially web and where problem is embarrassingly parallel but running graph algos is a bug chunk of the market and it seems for most firms a laptop will do.

Again, thanks for sharing.

Re:Bigger data; same laptop by mrry on Thursday February 05, 2015 @08:35PM (#9007307)
I would wager that an appropriately-sized Spark, GraphLab, or Naiad cluster could outperform a laptop when running PageRank on this graph. Distributed graph processing research got stuck in a rut when the gold standards for evaluation were the Twitter crawl [1] and uk-2007-05 web graph [2]. Now that the Common Crawl has made a much bigger graph available, I hope that we'll see it used in more performance evaluations—with a COST baseline, of course!

I'd also wager that those Spark, GraphLab, or Naiad programs would be far from optimal, by at least an order of magnitude. My ideal would be to see someone attack the distributed graph processing problem with the same eye for systems performance issues that the TritonSort folks brought to the distributed sort problem [3] and MapReduce [4].

[1] http://law.di.unimi.it/webdata/twitter-2010/

[2] http://law.di.unimi.it/webdata/uk-2007-05/

[3] http://www.alexras.info/pdfs/tritonsort-tocs13.pdf

[4] http://www.alexras.info/pdfs/themis_socc12.pdf

Re:Bigger data; same laptop by bmh100 on Thursday February 05, 2015 @12:15PM (#9004412)
When you explain the purpose of COST in this way, it is insightful and the value becomes very apparent. Noting that so many systems have not been compared against a single thread is important, since many developers likely would assume that. Do you feel that your COST work helps provide scalability break points where a developer could choose one system over another when performance is the primary concern? I can see that being helpful in the prototype and early scaling stages, as well as for ad-hoc work.
Re:Bigger data; same laptop by mrry on Thursday February 05, 2015 @08:54PM (#9007361)
I think in its current form, COST simply provides a reality check: for some problems, a given system may be completely inappropriate when a simple single-machine implementation exists. Along with raising standards for distributed systems evaluation, I hope that it encourages people to innovate on the single-machine implementations: for example, the GAS idea in PowerGraph [1] is an antecedent of the Hilbert-curve implementation in Frank's first blog post, and it would have been great if the original GAS implementation were separable from the particular distributed system for which it was built.

I fantasize about this work inspiring a competition like the sort benchmark [2], but for single-threaded graph algorithms. Not only would this encourage people to develop usable single-threaded implementations, but it have the side effect of increasing the COST for all distributed implementations....

As for providing scalability break points, I think this work goes some of the way, but doesn't take into account the fact that the input data for a particular real-world computation might not reside in a conveniently-compressed format on a local SSD. Extracting the Common Crawl from an HDFS cluster just to replicate the blog post's experiments could take much longer than the computation itself; extracting the social graph from Facebook's Tao [3] to do offline processing might be similarly non-trivial. Academic experiments don't typically take this cost into account, but recent work like Musketeer [4] has started to consider it, and even offer ways to automate the system choice problem.

[1] https://www.usenix.org/conference/osdi12/technical-sessions/...

[2] http://www.sortbenchmark.org/

[3] https://www.usenix.org/conference/atc13/technical-sessions/p...

[4] http://www.cl.cam.ac.uk/research/srg/netos/camsas/musketeer/

Re:Bigger data; same laptop by harperlee on Thursday February 05, 2015 @09:25AM (#9003349)
Please understand that some of us are not native speakers and try really hard to understand your comments. Particularily in this place, making the effort seems to be obliged, as most of the community produce high-quality comments. What you want to convey with "mmry" is very opaque. I am still not sure of what you mean with it (I believe is "Am I right", but the reference is lost with me, and I don't think I'm the only one).
Re:Bigger data; same laptop by ShonM on Thursday February 05, 2015 @09:52AM (#9003466)
In this case it's OPs username.
Re:Bigger data; same laptop by harperlee on Thursday February 05, 2015 @12:27PM (#9004503)
Well now I feel a little bit embarrased, I was harsh without need. Also, thanks for pointing that out, it's better to know than to be treated with silence!
Re:Bigger data; same laptop by eklavya on Thursday February 05, 2015 @01:30PM (#9004913)
Don't be, it was easy to miss :) I should have added an @
Re:Bigger data; same laptop by bane on Thursday February 05, 2015 @07:59AM (#9002964)
If you think of the network as part of the memory hierarchy, transferring data to nodes in a distributed system is usually slower than even spinning disk storage. About the only thing slower are USB, floppy drives and tape.

So basically big systems only make sense if the computation time on a single system exceeds the transfer time off of that system to the remote nodes + the time for that data to work it's way up the local node memory hierarchy.

This can happen when the data is big and the computation has unavoidable serialism in each part of the computation. Otherwise you'r likely to be able to coax a single system to just do it faster and with far less complexity than working on a compute cluster.

(I'm ignoring big systems with fast shared memory, like classic super-computers, where there effectively is zero transfer time since each node uses the same memory pool)

Re:Bigger data; same laptop by e12e on Thursday February 05, 2015 @03:12PM (#9005673)
> If you think of the network as part of the memory hierarchy, transferring data to nodes in a distributed system is usually slower than even spinning disk storage.

According to Google quick search, the bandwidth of DDR3 is ~12.8 GB/s, or ~104 gbps. As I understand it second-hand (read: cheap) infiniband givies ~40 gpbs, and newer, high-end gives ~100gbps[1]. Now, if you're using regular gigabit ethernet (or even 10gps with cheap-ish switches) -- you'd probably see around 5-8 gbps -- or if we're being very generous, on the order of 1/10th of cpu-ram bandwidth.

Sata2 is rated at ~6 gbps for comparison. In other words, 10gpbs ethernet/infiniband should be on-par with local SSDs, but "proper" infiniband should push the node-node ram-ram performance up compared to that. It appears fiberchannel is also moving towards the ~100 gps mark[2], but isn't there quite yet. And you'd have to have something on the other end -- with high speed networking it is quite natural to assume that both source and destination is RAM.

It's actually pretty crazy with ~40gps infiniband -- I'm considering getting some second-hand gear just to play with at home. Seems both cheaper and more reliable to work with than try to get 10gps ethernet to work (on a home/hobby budget!).

Eg:

http://www.ebay.com/itm/Flextronics-F-X430066-8-Port-SDR-Inf...

Or:

http://www.ebay.com/itm/Mellanox-MHGA28-XTC-InfiniHost-III-E...

All that said, I think the article makes a lot of great points -- and it does seem a bit funny that people seemingly are thinking of 1 gbps as "fast" when so much has happened on the cpu/ram side since that was remotely true.

[1] http://www.hpcwire.com/2012/06/18/mellanox_cracks_100_gbps_w...

[2] http://www.pcworld.com/article/2096980/fibre-channel-will-co...

Re:Bigger data; same laptop by bane on Thursday February 05, 2015 @03:52PM (#9005996)
Good points.

Though, you'd be surprised at how often people get stuck on distributed problems where they just can't seem to get their cluster to process more than 80-100MB/sec and it turns out it's because they ran 1Gb ethernet between their nodes.

Re:Bigger data; same laptop by vardump on Thursday February 05, 2015 @03:21PM (#9005742)
And how about latency? DDR3 has 100 ns latency, give or take.
Re:Bigger data; same laptop by e12e on Thursday February 05, 2015 @03:42PM (#9005909)
If I'm reading the numbers right[1], and converting correctly, infiniband is on the order of 5000 - 500 ns. I didn't mean to imply that the network isn't slower, just that it's possible to do quite a lot better than gigabit ethernet quite cheaply.

[1] http://en.wikipedia.org/wiki/InfiniBand

Re:Bigger data; same laptop by vardump on Thursday February 05, 2015 @06:18PM (#9006828)
Yup. Infiniband + RDMA is pretty cool, but RDMA is also rather scary. I mean, writing remotely to another systems (physical) memory. In the same time I do wonder why this is not being used more nowadays.
Re:Bigger data; same laptop by eklavya on Thursday February 05, 2015 @01:35PM (#9004948)
Makes sense, thanks :)
Re:Bigger data; same laptop by jkot on Thursday February 05, 2015 @06:43AM (#9002728)
It is one thing to run short benchmark on laptop. Other thing to sustain load 24/7 with demand spikes and hw failures.
Re:Bigger data; same laptop by angersock on Thursday February 05, 2015 @12:03PM (#9004328)
In the spirit of the article:

If you can write it so that it runs in 1/100th the time, do you even have to worry about it running for 24/7?

Re:Bigger data; same laptop by mrry on Thursday February 05, 2015 @10:23AM (#9003631)
This is absolutely true! However, I'm not aware of anybody doing this for the graph processing systems being discussed in the post. Nor am I sure what that would mean. Admittedly if something takes 100 times longer to run on multiple machines than it does on a single laptop (as in the previous COST post [1]) then you might care about fault tolerance, but this is a contrived problem if you could achieve the same results faster on yor laptop.

[1] http://www.frankmcsherry.org/graph/scalability/cost/2015/01/...

Re:Bigger data; same laptop by jkot on Thursday February 05, 2015 @01:46PM (#9005028)
I was answering parent questions. There are usually good reasons for clustering and big iron.
Re:Bigger data; same laptop by felixgallo on Thursday February 05, 2015 @01:20PM (#9004848)
can't help but feel that maybe you missed the point. The point is that an inexpensive single computer, programmed properly, can be seen to blow away gigantic, extremely expensive "big data"-programmed clusters.

if you wanted to run this same algorithm on a 'real' single computer with ecc and high-performance cores, nothing would stop you, and it would get even faster, and still be radically less expensive in every dimension than the "big data" clusters, for this problem set.

Re:Bigger data; same laptop by vardump on Thursday February 05, 2015 @06:21PM (#9006841)
Didn't miss the point at all. Lamenting lack of reliable laptops. Well, at least with reliable memory. You can buy a laptop with ECC RAM in the display adapter, but not as main memory! Sigh.

Luckily networking is getting so good that remote desktops feel almost like local most of the time.

Re:Bigger data; same laptop by vardump on Thursday February 05, 2015 @12:48PM (#9004633)
So true. If you can't accept the risk of random bit flip in memory, laptops are only good for using a real computer remotely. Memory errors do happen all too often on laptops. Have had it happening in the middle of a AES CBC encrypted data file... How hard would it be to get ECC RAM on laptops for better reliability?