The Google Technology Stack
Posts
PageRank and MapReduce
- Introduction to PageRank (video)
- Building our PageRank intuition (video)
- The PageRank distribution for the web (no video, short supplement extending the last post)
- Using your laptop to compute PageRank for millions of webpages
- Write your first MapReduce program in 20 minutes
- Using MapReduce to compute PageRank
- Consistent Hashing
- A Number-Theoretic Approach to Consistent Hashing
- To be added: We’ll put MapReduce on a cluster, use it to compute PageRank, and much more.
Data mining and machine learning
- Introduction to statistical machine translation. Good background is Peter Norvig’s introduction to spelling correction.
- Implementing statistical machine translation using MapReduce
- Much more to be added
About
Part of what makes Google such an amazing engine of innovation is their internal technology stack: a set of powerful proprietary technologies that makes it easy for Google developers to generate and process enormous quantities of data. According to a senior Microsoft developer who moved to Google, Googlers work and think at a higher level of abstraction than do developers at many other companies, including Microsoft: “Google uses Bayesian filtering the way Microsoft uses the if statement” (Credit: Joel Spolsky). This series of posts describes some of the technologies that make this high level of abstraction possible. The technologies I’ll describe include:
- The Google File System: a simple way of accessing enormous amounts of data spread across a large cluster of machines. Acts as a “virtual file system” that makes the cluster look to developers more like a single machine, and eliminates the need to think about details like what happens when a machine fails.
- Bigtable: Building on the Google File System, Bigtable provides a simple database model which can be run across large clusters. This allows developers to ignore many of the underlying details of the cluster, and concentrate on getting things done.
- MapReduce: A powerful programming model for processing and generating very large data sets on large clusters, MapReduce makes it easy to automatically parallelize many programming tasks. It is used internally by Google developers to process many petabytes of data every day, enabling developers to code and run simple but large parallel jobs in minutes, instead of days.
Together, these technologies make it easy to run large parallel jobs on very big data sets. Running on top of this technology stack are many powerful data mining and machine learning algorithms. I’ll describe at least two of these:
- Web Crawling
- PageRank
and may describe more, including statistical approaches to spell checking and machine translation, and recommendation algorithms.
In addition to understanding how these technologies work, we’ll also:
- Develop toy implementations of some of the technologies.
- Investigate some related open source technologies, such as Hadoop, CouchDB, Nutch, Lucene, and others.
I’ve never worked at Google. The posts are based on the published literature, especially some key technical publications released by Google describing the Google File System, Bigtable, MapReduce, and PageRank. I’m sure there are some significant differences between the material I will describe, and the current internal state-of-the-art. Still, we should be able to build up a pretty good picture of a data-intensive web company, even if it’s not accurate about Google’s particulars.
Exercises and problems: The posts will contain exercises for you to do to master the material, and also some more challenging and often open-ended problems. Note that while I’ve worked on many of the problems, I by no means have full solutions.
FriendFeed room: There is a FriendFeed room for the series.
Accompanying lectures: I’m basing a lecture series in Waterloo, Ontario, on the posts. Here’s some details about the lectures.
Audience: The audience will include both theoretical physicists and developers; the lectures should be accessible to both sets of people.
Time: Lectures will be held every Tuesday, 7:00-8:30pm. The exception is the first lecture, which will be Thursday, December 4, 2008, 7:00-8:30pm.
Location: AideRSS have kindly offered us a room for the course, at 505-180 King Street South, Waterloo – it’s opposite the Brick Brewery, and near the Hospital. To get into the building, you need someone from AideRSS to let you in. If no one from AideRSS is by the entrance, call (519) 498 1476.
Background reading
The lectures are based primarily on the following sources:
- Original PageRank paper: “The PageRank Citation Ranking: Bringing Order to the Web”, by Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd (1998).
- Textbook on PageRank and related ideas: “Google’s PageRank and Beyond: The Science of Search Engine Rankings”, by Amy N. Langville and Carl~D.~Meyer (2006).
- Overview of Google’s early architecture: “The Anatomy of a Large-Scale Hypertextual Web Search Engine”, by Sergey Brin and Lawrence Page (1998).
- More recent overview of Google’s architecture: “Web Search for a Planet: The Google Cluster Architecture”, by Luiz Barroso, Jeffrey Dean, and Urs Hoelze (2003).
- Original Google File System paper: “The Google File System”, by Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung (2003).
- Original Bigtable paper: “Bigtable: A distributed storage system for structured data”, by Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, Robert E. Gruber (2006).
- Original MapReduce paper: “MapReduce: Simplified Data Processing on Large Clusters”, by Jeffrey Dean and Sanjay Ghemawat (2004).
Related resources include:
- First of five lectures on MapReduce.
- Lecture course on scalable systems at the University of Washington, covering many similar topics. Videos of the lectures are included.
Many more resources will be posted in the FriendFeed room for the course.