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

History of massive-scale sorting experiments at Google

cloud.google.com

Post reply on HN
Print view View original

21–30 of 82 posts

Re: History of massive-scale sorting experiments at Google

#21

Post by mc808 »

azurezyq wrote: post #8

>> Nobody really wants a huge globally sorted output. We haven’t found a single use case for the problem as stated. Do anyone has a real world use case of global sorting other than top-k?

If the key is a sizable part of the data, then sorting could allow you to shave a few bytes from the key and reduce the overall storage needed. (Going from 50,000 drives to 40,000 drives is pretty significant even for someone who can afford 50,000 drives.) But I have no idea if there are real world cases where that is the right way to compress the data.

Re: History of massive-scale sorting experiments at Google

#22

Post by dzdt »

I think the alphago program is getting similar crazy scale burn-in access to the gpu computing that google will soon offer in its cloud. Recall alphago was the first program to beat a professional in a tournament setting. They published in nature. The emphasis was on their deep learning approach, but the technical details were pretty impressive. Alphago beat Fan Hui, a 2 dan professional, using a 1202 cpu/776 gpu diatributed system. They don't give hardware details, but my back-of-the-envelope estimate based on recent hardware is they were at around the petaflop calculation rate. In the nature paper they examine how the program's ELO rating varies with computation power; it looks like to reach world champion level they need at least an order of magnitude more computation. They challenged a player at that level (Lee Sedol) for a series in March and express a quiet confidence in winning. On their blog they give google cloud credit for supplying the compute power, but google cloud doesn't yet have gpu units available publicly. I am thinking alphago is getting to do burn-in on a massive gpu cloud computing center. Look for public availability shortly after the Sedol match!

Re: History of massive-scale sorting experiments at Google

#23

Post by asuffield »

existencebox wrote: post #14
gefh wrote: post #10

Earlier quoted context omitted.

You may well be asked how a distributed sort would work in principle, and be asked to code a small part of it. Any reasonable answer that shows you can think on your feet would be evidence in favor of hiring. It sounds like you didn't get hired, and I'm sorry about that. Interviewers' preferences are of course diverse, but for at least the last 5 years, probably 10, Google interviews favor practical solutions to prob…

As a datapoint, a while back I was asked (for a G interview within the last 10 years) to code an RB tree from start to finish. I'll admit I was a little miffed at how distanced this seemed from anything I would potentially do; I was not interviewing for a high theory/deep algorithms group. That being said, in my other experience with a G interview, the entire process was much more mundane and as expected. For the rec…

(Tedious disclaimer: not speaking for anybody else, my opinion only, etc. I'm an SRE at Google.)

"Within the last 10 years" covers several generations of refinement to the interview process. I'd suggest forgetting about anything more than a couple of years old.

The major thing to keep in mind is that these days, your recruiter will ask you up front what subject areas you are strongest in, and you should expect to get interviews about those things.

Re: History of massive-scale sorting experiments at Google

#25

Post by theoh »

KMag wrote: post #19
seanp2k2 wrote: post #7

I'm sure they're asking about this in interviews now. My experience with Google interviews was that the interviewers were very keen on proving that they knew more theoretical CS than I did vs talking about what the actual work would require or entail.

I worked at Google, and performed quite a few interviews. At least at that time, the interviewer had no idea where in the company the software engineer would go. The people who got hired would go into a pool, and the managers who needed staff would then horse-trade for them. They needed to hire people who could be plugged in to tons of different positions, including some that genuinely had tough problems where if the…

"an idea of the dimensions of your skillset" sounds like a really reductive way of thinking. It's as if the skillset is restricted to something easy to quickly explore and visualize, like a convex object in a few dimensions. Maybe those assumptions are necessary for interviewing but they're nothing to be proud of.

Re: History of massive-scale sorting experiments at Google

#26

Post by drx »

asuffield wrote: post #23
existencebox wrote: post #14

Earlier quoted context omitted.

As a datapoint, a while back I was asked (for a G interview within the last 10 years) to code an RB tree from start to finish. I'll admit I was a little miffed at how distanced this seemed from anything I would potentially do; I was not interviewing for a high theory/deep algorithms group. That being said, in my other experience with a G interview, the entire process was much more mundane and as expected. For the rec…

(Tedious disclaimer: not speaking for anybody else, my opinion only, etc. I'm an SRE at Google.) "Within the last 10 years" covers several generations of refinement to the interview process. I'd suggest forgetting about anything more than a couple of years old. The major thing to keep in mind is that these days, your recruiter will ask you up front what subject areas you are strongest in, and you should expect to get…

What's the process like these days?

Re: History of massive-scale sorting experiments at Google

#27

Post by skj »

theoh wrote: post #25
KMag wrote: post #19

Earlier quoted context omitted.

I worked at Google, and performed quite a few interviews. At least at that time, the interviewer had no idea where in the company the software engineer would go. The people who got hired would go into a pool, and the managers who needed staff would then horse-trade for them. They needed to hire people who could be plugged in to tons of different positions, including some that genuinely had tough problems where if the…

"an idea of the dimensions of your skillset" sounds like a really reductive way of thinking. It's as if the skillset is restricted to something easy to quickly explore and visualize, like a convex object in a few dimensions. Maybe those assumptions are necessary for interviewing but they're nothing to be proud of.

Why would they be something to be ashamed of?

Re: History of massive-scale sorting experiments at Google

#28

Post by Outdoorsman »

KMag wrote: post #19
seanp2k2 wrote: post #7

I'm sure they're asking about this in interviews now. My experience with Google interviews was that the interviewers were very keen on proving that they knew more theoretical CS than I did vs talking about what the actual work would require or entail.

I worked at Google, and performed quite a few interviews. At least at that time, the interviewer had no idea where in the company the software engineer would go. The people who got hired would go into a pool, and the managers who needed staff would then horse-trade for them. They needed to hire people who could be plugged in to tons of different positions, including some that genuinely had tough problems where if the…

>>Also, part of the point of a Google style interview is to keep pushing you to the point where your ability fails, then push in another direction to the point your ability fails. That way, they get an idea of the dimensions of your skill-set. The vast majority of the people I recommended hiring didn't answer the questions perfectly.I can't even begin to tell you how valuable I consider this approach to be...pushing (or leading) a candidate in every conceivable direction until failure is reached or limits are exposed...

HR professionals in almost any profession would benefit from implementing this technique to the extent that their resources allow...most don't have the luxury of time...

Example: As a member of a non-profit board I was once tasked with performing screening interviews for 5 candidates who were applying for a Camp Ranger position at one of the organization's youth camps...

I was not an HR expert then (or now), so I jotted down a few interview questions and scheduled interviews with the candidates...each one to begin at 8:00am at the site, and to last as long as it took...one per day...

I simply walked around the site, visited with the candidates, asked about their experience, and did everything I could to encourage them to "reveal" themselves...

I eliminated 2 candidates by around 10:00am, 2 more around 11:00am, and ended up driving to town for a burger lunch with the 5th...I later recommended the fifth...

He was hired, and ended up doing an incredible job...

I ended up giving other board members the impression that I knew what I was doing...at the time I most certainly did not...but I filed that lesson away...

I am convinced that a commitment to open-ended interview time, combined with "soft" skills probing, are critical if you want to properly evaluate candidates...

Re: History of massive-scale sorting experiments at Google

#29

Post by dpe82 »

Klathmon wrote: post #17
jlebar wrote: post #4

Note that this sort [in 2012] was 500 times larger than the GraySort large-scale requirement and twice as fast in throughput as the **current 2015** official GraySort winner. (emphasis mine)

It had to feel fucking amazing to be an engineer that was part of that at the time. To know (even if it was publicly unknown) that you were able to so massively destroy a record which still stands 4 years later.

Part of the magic of working at Google is there are lots of projects that can make you feel that way.

Re: History of massive-scale sorting experiments at Google

#30

Post by p4wnc6 »

KMag wrote: post #19
seanp2k2 wrote: post #7

I'm sure they're asking about this in interviews now. My experience with Google interviews was that the interviewers were very keen on proving that they knew more theoretical CS than I did vs talking about what the actual work would require or entail.

I worked at Google, and performed quite a few interviews. At least at that time, the interviewer had no idea where in the company the software engineer would go. The people who got hired would go into a pool, and the managers who needed staff would then horse-trade for them. They needed to hire people who could be plugged in to tons of different positions, including some that genuinely had tough problems where if the…

> genuinely had tough problems where if they accidentally did something in O(N^2), their half-day compute job would suddenly literally take centuries to complete.

Yes, but this has almost zero bearing on the actual interview. Being able to avoid this in real life means that you measure twice and cut once, you pay attention, and you ask for help and training. Being able to do something similar with dynamic programming or tree riddles in an interview has absolutely nothing to do with those longer-view skills.

> Google really needs most of their engineers that will naturally spot this kind of thing in code reviews, because if every engineer on the indexing team made a mistake like that once a year, the indexing system would always run at half speed, sometimes even 1/3 or 1/4 speed.

Again, this has nothing to do with puzzle interviews. In this case, you could hire smart people almost independently of whether they had encountered certain data structures before, and certainly without much concern about how fast they could spot things like this in an interview setting. And instead, hire for general aptitude, and then invest in training someone to be able to spot these things to the necessary degree.

Even though you can provide impressive-seeming examples of problems where minor tweaks in complexity or subtle implementation-specific points about data structures can result in huge problems, it's still not supportive of whiteboard-hazing style interviews that test more for interview aptitude than anything else.

After all, whoever it was that wrote the ML regex job, that person passed the interviews (and that person may have rightfully passed the interviews and deserved to work for Google, even after this later evidence that they weren't careful enough in one case).

Post reply on HN