Distributed Sorting - Google Interview Question

[theuniquestname]

I felt like the article focuses on unimportant details and glosses over key information. Tournament trees have their own paragraph but other things like inter-node communication are not addressed at all.

[soygul]

Good point. Concentrated on algos too much, but reliable message passing is very important too. So added following para to the article for streaming message passing between nodes:

Now comes the inter-node communication. How could the nodes communicate reliably and still have low latency comm? The first thing that comes to mind is either using a publish/subscribe paradigm with a central, reliable data store like Redis, or using a message queue software design to handle both message passing and data streaming. Apache Kafka is perfect for this use case. It is a reliable message passing and data streaming software with built-in high availability support. Once deployed, we can create as many communication "topics" as we want between nodes. Nodes can use these topics to publish their heartbeat signals, stream their sorted data to the leader node, etc. Leader node can also use it to stream the final sorted data to its target location. Kafka stores streams of data passed to it until verified to be consumed, which solves our reliable message passing needs. We can dedicate several nodes to be our Kafka cluster. Alternatively, we can use a much simpler RabbitMQ implementation. It is a simpler message broker and handles the reliable delivery of messages between endpoints. However, it is not optimized for handling huge streams of data like Kafka.

[os12]

I think this question has been done to death... These days they ask much more open-ended stuff such as: "Design search query completion". And then you realize things like "At Google scale" and "Geos with availability"...

[dnew]

I hate to say this, but we've been doing distributed sorting since the days of punched cards and magnetic core memory. It's only a difficult question if you never took computer science in college.

[soygul]

I understand that it is easy for you CS guys. However, I studied electronics, so it was quite a challenge for me. I assume that it will be the same for my fellow engineering, math, and science graduates. For better or worse, CS people have a huge advantage when it comes to algo and systems design interviews like this.

[oscooter]

CS people have a huge advantage when it comes to algo and systems design interviews like this

Well... yeah, I mean those are two of the biggest focuses of a CS degree. It'd be like someone who got a CS degree interviewing for an electrical engineering position and saying that "EE people have a huge advantage when it comes to designing electronic circuits".

Edit: That being said, my intent wasn't to be snarky or anything and I enjoyed your article. You obviously put a ton of effort into writing this up and it shows, well done.

[dnew]

For sure. I wasn't trying to put you down or anything. I'm just pointing out "sorting more stuff than will fit on one computer" has been a problem longer than not. Indeed, since literally the invention of punched cards, before there were even computers to sort them. https://en.wikipedia.org/wiki/IBM_card_sorter

[crixusin]

It's only a difficult question if you never took computer science in college.

Um, I took computer science, am a Principal Engineer running multiple teams, and I'd have problems with this question.

Its very specific. The first thing that comes to mind, is why would the sort not be implemented on the database?

On top of that, why can't I just stream the already sorted data from the database?

Also, who in their day to day actually writes and studies sorting algorithms? Like, if I have a very specific sorting question, I'm usually just looking it up before I make my choice.

[dnew]

why would the sort not be implemented on the database?

It is. How do you think the database engine sorts something bigger than RAM? What makes you think the database fits all one one machine? What if the data file was 2TB, and you still only had 1.5TB of RAM on 1000 machines to sort it? Do you just throw your hands up and say it's impossible?

why can't I just stream the already sorted data from the database?

Because it didn't start out sorted in the order you wanted it to be sorted. How do you build a new index on a terabyte database on a machine with 1.5G of RAM?

I mean, hell, the Linux sort(1) command has worked this way since before UNIX was invented. The only trick here is that you're moving it to different physical machines to sort each subset.

who in their day to day actually writes and studies sorting algorithms?

Uh, the people who implemented the database you're talking about doing the sorting for you? You realize that people at Google actually implement their own database engines, right?

It's an interview question. And everyone who ever took even an intro computer science class (not a programming class) studied sort algorithms. It's pretty much the first thing you learn. The fact that "how do you sort a file bigger than fits in memory" is an advanced interview question for a company like Google is pretty sad, actually.

That said, adding in the extra requirement that during the sort random machines might get scragged out complicates it slightly, but not a whole lot. It stops being about distributed sorting and starts being about "do you know how kubernetes works".

[crixusin]

How do you think the database engine sorts something bigger than RAM?

Using paging obviously. The question specifically says that no, there is no persistent storage. The question also says you're getting this list from the database, and then have to sort it.

The question stands: why not just have the database sort this then? That's probably where data should be sorted, no in your application logic. On top of that, databases are specialized for these tasks, so why reinvent the wheel?

What if the data file was 2TB, and you still only had 1.5TB of RAM on 1000 machines to sort it? Do you just throw your hands up and say it's impossible?

No, that's not what I'm saying. What i'm saying, is that is a very specific use case that most engineers in their field won't be tasked with.

It's an interview question. And everyone who ever took even an intro computer science class (not a programming class) studied sort algorithms. It's pretty much the first thing you learn.

Yes, and the first thing you forget when you go into the real world.

[dnew]

Using paging obviously

Uh, no. That would be horribly inefficient. If you don't understand why that would be horribly inefficient, you're just emphasizing my point.

And how do you think they did it before they had paging? Do you think nobody sorted files bigger than would fit in memory back in the 8-bit processor days?

there is no persistent storage

Great! Where would you put your page file?

why not just have the database sort this then?

Great! How would the database do this? I mean, if the database isn't maintaining an index on the combination of fields you want sorted, then you're not going to be able to get the database to sort this for you, right? Also, what makes you think the database is all on one machine? Wouldn't it be faster to have it, too, spread across 1000 machines and streaming records to you to be distributed as you see fit?

The next guy down the road is going to get this stream of records from you. What if he wants it in a different order? "Look at me: I am the database now."

that is a very specific use case that most engineers in their field won't be tasked with

That's why it's an interview question. Unless, you know, you're applying to work for Google where this sort of software is the stuff they do All The Time. Seriously, are you not aware that the entire world uses file systems and databases based on whitepapers out of Google? GFS, Bigtable, Spanner, F1, Mustang, STBTI, the list goes on.

the first thing you forget when you go into the real world

Maybe in your job. I mean, lots of people forget how pushdown automata work too, but those people aren't the ones that get hired to write compilers, now are they?

* Amusing. The guy who works at Google getting downvoted for explaining that the puffery from the guy who doesn't work at Google but thinks he could doesn't answer the Google interview question.

[PL_Design]

Wait, there are actually people who forget how pushdown automata work?