10 ms·

History of massive-scale sorting experiments at Google

204 points by vgt 11y ago

vijucat 11y ago
If you know the distribution of the data (which can be imputed as part of the sorting process by sampling the data), it is possible to guess if the next number is going to be larger or smaller than the current one 75% of the time without looking at it by using Cover's pick the largest number trick [1, 2, 3]. I wonder if distributed sorting algorithms know and incorporate this, which should reduce the cost of hitting the network in distributed algorithms considerably? (Asking because I don't work in that field; this is just an idea that I had). References 1. "Playing a Trick on Uncertainty" by Thomas Bruss, page 7 of http://www.emis.de/newsletter/newsletter50.pdf http://www.emis.de/newsletter/newsletter50.pdf 2. "Tom Cover’s Number Guessing Game" by Robert Snapp, http://www.ibrarian.net/navon/paper/Tom_Cover_s_Number_Guessing_Game.pdf?paperid=15348704 http://www.ibrarian.net/navon/paper/Tom_Cover_s_Number_Guess... 3. "Who discovered this number-guessing paradox?", https://math.stackexchange.com/questions/709984/who-discovered-this-number-guessing-paradox https://math.stackexchange.com/questions/709984/who-discover...
JavaScriptrr 11y ago
Only at Google
- fintler 11y ago
  I wonder how fast this could do it: http://www.lanl.gov/projects/trinity/specifications.php http://www.lanl.gov/projects/trinity/specifications.php They're claiming 87.0 TB/min on an 80PB filesystem, relative to Google's 36.2 TB/min.
  - cshimmin 11y ago
    That just their I/O bandwidth. There is computing overhead in actually doing the sort. Also google was using redundant persistence.
    - tyre 11y ago
      To add to this, Google's results were in 2012.
  - deleted 11y ago
    [deleted]
jlebar 11y ago
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)
- Klathmon 11y ago
  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.
  - dpe82 11y ago
    Part of the magic of working at Google is there are lots of projects that can make you feel that way.
    - fapjacks 11y ago
      From what I understand, those kinds of projects are only available to certain engineers, and the vast majority of engineers working at Google don't get to play those games. Six of my seven interviewers essentially said that they did not get to work on problems that challenged them when I asked "If you could change one thing without veto...." This is actually one of the two big reasons I chose not to accept an offer.
      - saalweachter 11y ago
        Eh, there's an important thing to realize about working at a company like Google. 1. As a programmer, you will feel most productive working on a project by yourself where you just pound out thousands of lines of code. 2. The secret to how you get 100x more done than any individual programmer can do is that you have 200 programmers working together feeling 50% productive. 3. Google has no interest in projects that can be accomplished by one brilliant engineer working by themselves. It can be really unsatisfying for a programmer, because we all learn to program individually and that's what we base our "am I being productive?" feeling on, but it turns out that you can do some really amazing things if you're willing to put that aside and work together, even if it means spending half your day in meetings and checking email or writing design docs that no one reads. And if you're feeling challenged, it's probably because you're doing something convoluted and even you won't remember how it works in six months and no one will be able to maintain it and you can actually get nearly equivalent performance out of three mapreduces and a drop-in machine learning model, so maybe you should just do that? It's not for everyone, but at the end of the day would you rather feel productive and challenged, or actually change the world a little bit at a time?
vgt 11y ago
"To reduce the impact of stragglers, we used a dynamic sharding technique called reduce subsharding. This is the precursor to fully dynamic sharding used in Dataflow." Fun ways in which internal Google tech makes its way to Google Cloud services.
- throwaway6497 11y ago
  I want to learn more about dynamic sharding. Will be great, if people can help me out here. I get the feeling "my googling" skills will fail me.
seanp2k2 11y ago
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.
- gefh 11y ago
  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 problems we face every day. Some of those are theoretical CS, many are not.
  - alexnewman 11y ago
    Lol normal Google arrogance. Yea they only seem to ask theoretical questions basically out of that famous book
    - alexnewman 11y ago
      Why did i get -4 vote here....
    - late2part 11y ago
      Maybe, maybe not. Most people's surface area of problems don't even approach Google's problems. The kind of things most companies aspire to solve, Google automated a decade ago. So, this esoteric CS theory may be more practical inside Google than your external vantage point can consider.
      - cmrdporcupine 11y ago
        The problems being automated years ago means the vast majority of Google engineers don't ever get close to having to work on those solutions. One of things that disappointed me after joining G was that many of the problems I found fun to solve at previous employers were a) solved already and b) solved by people much smarter and senior than me. It's a great place to work for all sorts of reasons. But working on cutting edge stuff, well, that requires that you be good at fighting on both meritocratic and political fronts. The majority of the people that came in the same acquisition as me left before their golden handcuff payouts finished, because of this.
azurezyq 11y ago
>> 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?
- mc808 11y ago
  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.
- rockinghigh 11y ago
  If you sort records by time you can perform time range queries. You can also create an index to access random keys (like a MapFile in Hadoop).
  - amelius 11y ago
    But isn't sorting by time easy, because records come in the correct order? I would say you don't need an algorithm for that.
    - rockinghigh 11y ago
      You may want to sort by settlement date instead of transaction date. There are plenty of examples where you need to sort before you can index: let's say you want to create a spatial index. You first need to sort/group spatially (by tile) to query an area.
seeing 11y ago
We haven’t found a single use case for the problem as stated. Impressive nonetheless.
- late2part 11y ago
  But, when the practical catches up with the theory, the problem is solved; and the implementation is trivial.
- matt_wulfeck 11y ago
  This is my favorite part! There's so much and learning to be had in engineering solving problems with no real practical use. I don't consider it a waste of time at all and I'm glad they went ahead with their experiment.
dzdt 11y ago
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!
AI_Overlord 11y ago
To each their own. While impressive I do not find it inspiring. Instead, working on strong AI is, in my mind, the ultimate challenge. Far more amazing by any measure than anything we have acomplished so far.
- seiji 11y ago
  working on strong AI is, in my mind, the ultimate challenge. So is working on antigravity, free energy, and backwards time travel, but people don't do that because they are no reasonable approaches we can try. Glorifying "AI AI AI" is silly because — there are no approaches we can try. Sure, we can identify ten million images per second, but none of that involves the least bit of "thinking."
  - AI_Overlord 11y ago
    Evolution has already proven that strong AI is possible. It is up to us to discover how. It is only a matter of time.
    - seiji 11y ago
      Just one summer of study and it'll be solved, right? It's always been "one summer away" for the past 60 years. Get back to us when you have an algorithm for love and art and petrichor.
      - AI_Overlord 11y ago
        Emotions are not a requirement for strong AI. I frankly would not waste any time with them. I just need an AI that can learn and solve problems at the human level. I'm not naive enough to think that it can be solved in a short time. I do think that it is worth it for a person to spend the rest of their life working on it. There is just nothing more exciting than AI in my opinion. Just imagine the possibilities...
        wantreprenr007 11y ago
trengrj 11y ago
It is interesting to compare this with Apache Spark, which won the open source Graysort competition of 2014 [1]. Apache Spark completed a 1PB sort on 190 EC2 (i2.8xlarge) instances in 234 mins. Google did their 2011 1PB sort on 8000 computers in 33 minutes. Moore's law is at work here and the results aren't very comparable but it would be interesting to see a head-to-head test on similarly speced clusters. [1] https://databricks.com/blog/2014/10/10/spark-petabyte-sort.html https://databricks.com/blog/2014/10/10/spark-petabyte-sort.h...
known 11y ago
I prefer to use "split -b 10G data.txt" and "sort -nrs"
isomorphism 11y ago
"We are best but we do not wanted to participate the competition." Whatever....

204 points by vgt 11y ago

If you know the distribution of the data (which can be imputed as part of the sorting process by sampling the data), it is possible to guess if the next number is going to be larger or smaller than the current one 75% of the time without looking at it by using Cover's pick the largest number trick [1, 2, 3]. I wonder if distributed sorting algorithms know and incorporate this, which should reduce the cost of hitting the network in distributed algorithms considerably? (Asking because I don't work in that field; this is just an idea that I had). References 1. "Playing a Trick on Uncertainty" by Thomas Bruss, page 7 of http://www.emis.de/newsletter/newsletter50.pdf http://www.emis.de/newsletter/newsletter50.pdf 2. "Tom Cover’s Number Guessing Game" by Robert Snapp, http://www.ibrarian.net/navon/paper/Tom_Cover_s_Number_Guessing_Game.pdf?paperid=15348704 http://www.ibrarian.net/navon/paper/Tom_Cover_s_Number_Guess... 3. "Who discovered this number-guessing paradox?", https://math.stackexchange.com/questions/709984/who-discovered-this-number-guessing-paradox https://math.stackexchange.com/questions/709984/who-discover...

JavaScriptrr 11y ago

Only at Google

fintler 11y ago
I wonder how fast this could do it: http://www.lanl.gov/projects/trinity/specifications.php http://www.lanl.gov/projects/trinity/specifications.php They're claiming 87.0 TB/min on an 80PB filesystem, relative to Google's 36.2 TB/min.
- cshimmin 11y ago
  That just their I/O bandwidth. There is computing overhead in actually doing the sort. Also google was using redundant persistence.
  - tyre 11y ago
    To add to this, Google's results were in 2012.
- deleted 11y ago
  [deleted]

jlebar 11y ago

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)

Klathmon 11y ago
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.
- dpe82 11y ago
  Part of the magic of working at Google is there are lots of projects that can make you feel that way.
  - fapjacks 11y ago
    From what I understand, those kinds of projects are only available to certain engineers, and the vast majority of engineers working at Google don't get to play those games. Six of my seven interviewers essentially said that they did not get to work on problems that challenged them when I asked "If you could change one thing without veto...." This is actually one of the two big reasons I chose not to accept an offer.
    - saalweachter 11y ago
      Eh, there's an important thing to realize about working at a company like Google. 1. As a programmer, you will feel most productive working on a project by yourself where you just pound out thousands of lines of code. 2. The secret to how you get 100x more done than any individual programmer can do is that you have 200 programmers working together feeling 50% productive. 3. Google has no interest in projects that can be accomplished by one brilliant engineer working by themselves. It can be really unsatisfying for a programmer, because we all learn to program individually and that's what we base our "am I being productive?" feeling on, but it turns out that you can do some really amazing things if you're willing to put that aside and work together, even if it means spending half your day in meetings and checking email or writing design docs that no one reads. And if you're feeling challenged, it's probably because you're doing something convoluted and even you won't remember how it works in six months and no one will be able to maintain it and you can actually get nearly equivalent performance out of three mapreduces and a drop-in machine learning model, so maybe you should just do that? It's not for everyone, but at the end of the day would you rather feel productive and challenged, or actually change the world a little bit at a time?

vgt 11y ago

"To reduce the impact of stragglers, we used a dynamic sharding technique called reduce subsharding. This is the precursor to fully dynamic sharding used in Dataflow." Fun ways in which internal Google tech makes its way to Google Cloud services.

throwaway6497 11y ago
I want to learn more about dynamic sharding. Will be great, if people can help me out here. I get the feeling "my googling" skills will fail me.

seanp2k2 11y ago

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.

gefh 11y ago
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 problems we face every day. Some of those are theoretical CS, many are not.
- alexnewman 11y ago
  Lol normal Google arrogance. Yea they only seem to ask theoretical questions basically out of that famous book
  - alexnewman 11y ago
    Why did i get -4 vote here....
  - late2part 11y ago
    Maybe, maybe not. Most people's surface area of problems don't even approach Google's problems. The kind of things most companies aspire to solve, Google automated a decade ago. So, this esoteric CS theory may be more practical inside Google than your external vantage point can consider.
    - cmrdporcupine 11y ago
      The problems being automated years ago means the vast majority of Google engineers don't ever get close to having to work on those solutions. One of things that disappointed me after joining G was that many of the problems I found fun to solve at previous employers were a) solved already and b) solved by people much smarter and senior than me. It's a great place to work for all sorts of reasons. But working on cutting edge stuff, well, that requires that you be good at fighting on both meritocratic and political fronts. The majority of the people that came in the same acquisition as me left before their golden handcuff payouts finished, because of this.

azurezyq 11y ago

>> 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?

mc808 11y ago
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.
rockinghigh 11y ago
If you sort records by time you can perform time range queries. You can also create an index to access random keys (like a MapFile in Hadoop).
- amelius 11y ago
  But isn't sorting by time easy, because records come in the correct order? I would say you don't need an algorithm for that.
  - rockinghigh 11y ago
    You may want to sort by settlement date instead of transaction date. There are plenty of examples where you need to sort before you can index: let's say you want to create a spatial index. You first need to sort/group spatially (by tile) to query an area.

seeing 11y ago

We haven’t found a single use case for the problem as stated. Impressive nonetheless.

late2part 11y ago
But, when the practical catches up with the theory, the problem is solved; and the implementation is trivial.
matt_wulfeck 11y ago
This is my favorite part! There's so much and learning to be had in engineering solving problems with no real practical use. I don't consider it a waste of time at all and I'm glad they went ahead with their experiment.

dzdt 11y ago

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!

AI_Overlord 11y ago

To each their own. While impressive I do not find it inspiring. Instead, working on strong AI is, in my mind, the ultimate challenge. Far more amazing by any measure than anything we have acomplished so far.

seiji 11y ago
working on strong AI is, in my mind, the ultimate challenge. So is working on antigravity, free energy, and backwards time travel, but people don't do that because they are no reasonable approaches we can try. Glorifying "AI AI AI" is silly because — there are no approaches we can try. Sure, we can identify ten million images per second, but none of that involves the least bit of "thinking."
- AI_Overlord 11y ago
  Evolution has already proven that strong AI is possible. It is up to us to discover how. It is only a matter of time.
  - seiji 11y ago
    Just one summer of study and it'll be solved, right? It's always been "one summer away" for the past 60 years. Get back to us when you have an algorithm for love and art and petrichor.
    - AI_Overlord 11y ago
      Emotions are not a requirement for strong AI. I frankly would not waste any time with them. I just need an AI that can learn and solve problems at the human level. I'm not naive enough to think that it can be solved in a short time. I do think that it is worth it for a person to spend the rest of their life working on it. There is just nothing more exciting than AI in my opinion. Just imagine the possibilities...
      - wantreprenr007 11y ago

trengrj 11y ago

It is interesting to compare this with Apache Spark, which won the open source Graysort competition of 2014 [1]. Apache Spark completed a 1PB sort on 190 EC2 (i2.8xlarge) instances in 234 mins. Google did their 2011 1PB sort on 8000 computers in 33 minutes. Moore's law is at work here and the results aren't very comparable but it would be interesting to see a head-to-head test on similarly speced clusters. [1] https://databricks.com/blog/2014/10/10/spark-petabyte-sort.html https://databricks.com/blog/2014/10/10/spark-petabyte-sort.h...

known 11y ago

I prefer to use "split -b 10G data.txt" and "sort -nrs"

isomorphism 11y ago

"We are best but we do not wanted to participate the competition." Whatever....