3 ms·

Jeff Dean on Google's 25th anniversary

4 points by guiambros 3y ago

dekhn 3y ago
Jeff's impact on Google simply cannot be overstated. I was privileged to sit near him and be invited to coffee on a regular basis when I was working on a skunkworks project back in 2009. I took advantage of that access to ask a number of questions, even though I was quite knowledgeable about Google history from following it on Slashdot since the late 90s. In the very early days of google.com, Larry and Sergey and the earliest search engineers built crawl, index, and serving systems that were fairly good but building a new index with fresh pages was challenging. Google had chosen to do the "large amounts of unreliable hardware" approach and so individual server failures were common and the indexing system jobs would die half-way through and had to be restarted from scratch. The entire system was documented in a README file telling you what commands to run and when to complete and index, and apparently, it was more or less impossible to make a new index at a critically important phase (around the time people were starting to use Google in favor of Altavista). Jeff's good friend Sanjay had just joined, leaving DEC WRL where they were both compiler optimization engineers (before that, Jeff was a grad student at UW, working for Craig Chambers, who later lead the Flume project that replaced mapreduce). Sanjay convinced Jeff that joining was a good idea and they worked together in the early days to build a new index using flaky hardware, applying techniques that Jeff and Sanjay had learned during their academic and DEC days. In particular, one key step of indexing is building an inverted index. For every query term in your corpus, make a list of documents that contain that term. The document list is typically ordered, by decreasing document frequency. Parts of this computation can be spend up by partitioning by document and then merging the partition's results. If you have a fast enough filesystem that scales with many clients, you can greatly speed up indexing with a cluster of machines, but the merge step has to be extremely fast, resource efficient, and restartable (without too much work that has to be redone) in case of machine failure. Jeff and Sanjay looked at the problem and realized it could be implemented using the already well-known functional paradigm, "map and reduce": the map function is called with a document argument, and it emits term, document pairs (one for every term in the document). The term, document pairs, after some processing, are passed to a reducer, which operates per-term, merging all the documents with a mapreduce function. The result is a k/v table of term to document for the entire corpus, which can be used to implement keyword search efficiently. The key innovation wasn't map, or reduce, but the shuffle step between the two. The mapreduce shuffler was a powerful and well-implemented system that was extremely resource efficient, parallelizable and restartable without much loss. Those who are familiar with the early Google interview question """Let's say you have a computer with 2M RAM. This computer has a hard drive (with lots of free space) and a 100M file which you should sort. Let me know how you, as effectivly as possible, sort the file.""" (from 2007: https://tech.slashdot.org/comments.pl?sid=232757&cid=18925745 https://tech.slashdot.org/comments.pl?sid=232757&cid=1892574...). that question is literally what Jeff and Sanjay worked on while implementing the shuffle: it's a merge sort that runs in very little RAM MapReduce later turned out to be useful for a wide range of tasks. Beyond the initial indexing steps, it was used for PageRank calculation. While I normally think of PageRank as a giant eigenvector problem to be calculated in one shot on a single machine with tons of RAM, they solved it with an iterative mapreduce, which allowed the company to scale PR calculations. Even trivial things like frequency counting to provide ranking signals work well in mapreduce, but it's very much a hammer that makes everything look like a nail. I could write more details about the early days, for example their contributions to Ads, generations of storage systems (from GFS to spanner and beyond), data encoding (protocol buffers, while not perfect, have been an excellent tool for data storage and exchange), file formats (recordio and sstable and leveldb). But to be honest it's just enough to say that they played absolutely essential roles in both the existence of google, and its unbelievable success. For example, tensorflow got its start as a little project Jeff wrote after working on a previous machine learning system, and I believe his original code is still in the examples dir (calculating the eigenvalues of a matrix). Around the time i was getting invited to coffee with Jeff and Sanjay, I was also writing documents saying that Google should get involved in health care research (I believe in a simple premise: we are massively underutilizing biological scientific data in large-scale health care research, and few groups have the knowledge, skill, and impetus to prove that). This was pretty successful, as I know people read my doc and made projects based on my ideas, and one day, a chat window opened up. It was a group chat with Jeff and Sanjay! They had written a mapreduce to compress genomic sequences "if we get them small enough we can fit all the world's genomes on SSD!" (jeff is a performance nerd) and wanted my help seeing if it was competitive and useful (unfortunately, it wasn't). But I certainly learned a bunch of cool tricks, and variations on the original technology eventually were launched through Google Cloud Genomics. I will be forever thankful that I got to hang around engineers who were far smarter than me and learn from them, even if my path deviated and I never got to do the large-scale machine learning research I had long wanted to work on. I will conclude by saying that while Jeff had INT 18, Sanjay was had WIS 21, and it was the combination of their skills that was truly powerful. They pair programmed all day long and it was kind of crazy watching them communicate telepathically, then send out a changelist that optimized a single hot function that sped up most server binaries across the fleet by 1%.

4 points by guiambros 3y ago

Jeff's impact on Google simply cannot be overstated. I was privileged to sit near him and be invited to coffee on a regular basis when I was working on a skunkworks project back in 2009. I took advantage of that access to ask a number of questions, even though I was quite knowledgeable about Google history from following it on Slashdot since the late 90s. In the very early days of google.com, Larry and Sergey and the earliest search engineers built crawl, index, and serving systems that were fairly good but building a new index with fresh pages was challenging. Google had chosen to do the "large amounts of unreliable hardware" approach and so individual server failures were common and the indexing system jobs would die half-way through and had to be restarted from scratch. The entire system was documented in a README file telling you what commands to run and when to complete and index, and apparently, it was more or less impossible to make a new index at a critically important phase (around the time people were starting to use Google in favor of Altavista). Jeff's good friend Sanjay had just joined, leaving DEC WRL where they were both compiler optimization engineers (before that, Jeff was a grad student at UW, working for Craig Chambers, who later lead the Flume project that replaced mapreduce). Sanjay convinced Jeff that joining was a good idea and they worked together in the early days to build a new index using flaky hardware, applying techniques that Jeff and Sanjay had learned during their academic and DEC days. In particular, one key step of indexing is building an inverted index. For every query term in your corpus, make a list of documents that contain that term. The document list is typically ordered, by decreasing document frequency. Parts of this computation can be spend up by partitioning by document and then merging the partition's results. If you have a fast enough filesystem that scales with many clients, you can greatly speed up indexing with a cluster of machines, but the merge step has to be extremely fast, resource efficient, and restartable (without too much work that has to be redone) in case of machine failure. Jeff and Sanjay looked at the problem and realized it could be implemented using the already well-known functional paradigm, "map and reduce": the map function is called with a document argument, and it emits term, document pairs (one for every term in the document). The term, document pairs, after some processing, are passed to a reducer, which operates per-term, merging all the documents with a mapreduce function. The result is a k/v table of term to document for the entire corpus, which can be used to implement keyword search efficiently. The key innovation wasn't map, or reduce, but the shuffle step between the two. The mapreduce shuffler was a powerful and well-implemented system that was extremely resource efficient, parallelizable and restartable without much loss. Those who are familiar with the early Google interview question """Let's say you have a computer with 2M RAM. This computer has a hard drive (with lots of free space) and a 100M file which you should sort. Let me know how you, as effectivly as possible, sort the file.""" (from 2007: https://tech.slashdot.org/comments.pl?sid=232757&cid=18925745 https://tech.slashdot.org/comments.pl?sid=232757&cid=1892574...). that question is literally what Jeff and Sanjay worked on while implementing the shuffle: it's a merge sort that runs in very little RAM MapReduce later turned out to be useful for a wide range of tasks. Beyond the initial indexing steps, it was used for PageRank calculation. While I normally think of PageRank as a giant eigenvector problem to be calculated in one shot on a single machine with tons of RAM, they solved it with an iterative mapreduce, which allowed the company to scale PR calculations. Even trivial things like frequency counting to provide ranking signals work well in mapreduce, but it's very much a hammer that makes everything look like a nail. I could write more details about the early days, for example their contributions to Ads, generations of storage systems (from GFS to spanner and beyond), data encoding (protocol buffers, while not perfect, have been an excellent tool for data storage and exchange), file formats (recordio and sstable and leveldb). But to be honest it's just enough to say that they played absolutely essential roles in both the existence of google, and its unbelievable success. For example, tensorflow got its start as a little project Jeff wrote after working on a previous machine learning system, and I believe his original code is still in the examples dir (calculating the eigenvalues of a matrix). Around the time i was getting invited to coffee with Jeff and Sanjay, I was also writing documents saying that Google should get involved in health care research (I believe in a simple premise: we are massively underutilizing biological scientific data in large-scale health care research, and few groups have the knowledge, skill, and impetus to prove that). This was pretty successful, as I know people read my doc and made projects based on my ideas, and one day, a chat window opened up. It was a group chat with Jeff and Sanjay! They had written a mapreduce to compress genomic sequences "if we get them small enough we can fit all the world's genomes on SSD!" (jeff is a performance nerd) and wanted my help seeing if it was competitive and useful (unfortunately, it wasn't). But I certainly learned a bunch of cool tricks, and variations on the original technology eventually were launched through Google Cloud Genomics. I will be forever thankful that I got to hang around engineers who were far smarter than me and learn from them, even if my path deviated and I never got to do the large-scale machine learning research I had long wanted to work on. I will conclude by saying that while Jeff had INT 18, Sanjay was had WIS 21, and it was the combination of their skills that was truly powerful. They pair programmed all day long and it was kind of crazy watching them communicate telepathically, then send out a changelist that optimized a single hot function that sped up most server binaries across the fleet by 1%.