Google Internals

Answers in 0.2 Seconds or Your Money Back

Toby DiPasquale

Cipher Block Chain Gang

Who the hell am I?

• I work for Symantec because they bought TurnTide
• I have never worked for Google
• No one I know works for Google
• I have been tracking them heavily for about 2 years now
• Also, I interviewed with them (twice)
  • Me: "I hear you guys build your own custom, 1000-port GigE switches; is that right?"
  • Interviewer: "Hey, you're not supposed to know that."

What are we talking about?

• The pieces that make up Google's key infrastructure
• Cluster design/manangement
• Google File System
• MapReduce
• Sawzall
• BigTable
• NOT PageRank
  • I'm not an SEO huckster

You do not want that power bill

• Currently estimated to have ~450,000 active machines
• No, that's not a typo... 450,000
• Search is expensive
• Massive parallelism yields major performance boost
• With that many machines, cluster management becomes a huge problem

Pile on at the datacenter!

• Tons of cheap x86 boxes
• Price/performance is king
• Power is a major issue, too
• Dataset is split up over multiple machines
  • Index servers
  • Document servers
  • Spellcheck servers
  • etc.

The Idea...

• Replication, replication, replication
• Each piece of data is available on multiple machines
• Literally dozens of copies of the Web across their clusters
• Requests are split up over the logical clusters and handled in parallel

Hardware

• Cheap x86 boxes, ~40-80/rack
• Modest disk space/box (250GB?; one per box)
• Intra-rack network is 100baseT
• Inter-rack network is 1000baseT
• They build their own servers and switches
• Have many patents on cable/rack/power innovations

Hardware (cont)

• Traditional big-iron box (circa 2003)
  • 8 2GHz Xeons
  • 64GB RAM
  • 8TB disk
  • $758,000 USD
• Prototypical GOOG rack (circa 2003)
  • 176 2GHz Xeons
  • 176GB RAM
  • ~7TB disk
  • $278,000 USD

Google File System

• Distributed filesystem w/constraints
• Implemented entirely in userspace
• "Chunks" (i.e. blocks) stored on machines as regular files
  • 64MB block size
• Designed to optimize multiple-reader/multiple-appender files/workloads
  • Crawlers atomically append to a file
  • Readers read file at the same time
  • No races/corruption issues
• Each logical chunk is replicated across 3+ boxes

Google File System (cont)

Workqueue

• Key piece of infrastructure at Google
• Schedules and starts tasks on the machines of a cluster
• Similar to Condor
• Those tasks run on same as GFS boxes
  • Keep that data close, baby
• Can reschedule jobs which fail

MapReduce

• Method for processing data in massive parallel
  • map(fn1, list) -> list
  • reduce(fn2, init, list) -> scalar
• Mappers spawned for each GFS chunk of input and apply fn1 to each record in chunk
  • Intermediate data output according to "partitions" (some hash function)
• Reducers aggregate mappers' intermediate data according to fn2
  • One reducer job per partition
• Brian Goetz: It's the mutable state, stupid.

MapReduce (cont)

• Pseudocode for a "word count" job:



map(String key, String value):
  for each word w in value:
    EmitIntermediate(w, "1")

reduce(String key, Iterator values):
  int result = 0
  for each v in values:
    result += ParseInt(v)
  Emit(AsString(result))
   

MapReduce (cont)

• Lots of uses for this paradigm
  • grep-style jobs
  • log file analysis
  • reverse web-link graph
  • inverted index
• GOOG search index is built using a series of MR jobs
  • The output of one becomes the input to the next
  • Last I heard, it was 24 MR jobs, but its almost certainly more now

Sawzall

• DSL built on top of MapReduce (statically typed)
• Think of it as "distributed awk"
• Filters read data and pass to aggregator which passes to coallater
• Only allows tasks which are both commutative and associative
  • Allows intermediate steps to be executed in any order (read: on any box)
• Error handling then becomes trivial: a worker dies, restart it

Sawzall (cont)

• Sawzall script to generate geographic query distribution data:



proto "querylog.proto"

queries_per_degree: table sum[lat: int][lon: int] of int;

log_record: QueryLogProto = input;

loc: Location = locationinfo(log_record.ip);
emit queries_per_degree[int(loc.lat)][int(loc.lon)] <- 1;
   

Sawzall (cont)

• That script's data is used to generate this map:

BigTable

• A Google-style "database"
• More like the most bad-ass spreadsheet you've ever used
• Built on top of GFS, Workqueue and MapReduce
• Each BigTable is a multidimensional sparse map
• Stored on immutable structures called SSTables
  • also, a journal per machine

BigTable (cont)

• For each table, there's one META0 table for the locs of all META1 "tablets"
• The META1s contain the locs of the actual "tablets" (with data in them, even)
• Tablets are based on GFS files/chunks
• Makes heavy use of prefetching/caching for performance

BigTable (cont)

• Columns are in form "family:qualifier"
  • e.g. anchor:phillylinux.org
  • columns are typed
• Cells are addressed by 3-tuple
  • row:column:timestamp
• Each cell has a timestamp
  • Multiple versions of a cell can coexist simultaneously

BigTable (cont)

• Column families can be split into "locality groups"
  • increases performance by splitting SSTables
  • small, hot columns can be separate from large, cold ones
• SSTable data is compressed
  • BMDiff (~100MB/s write, ~1000MB/s read)
  • Zippy (fast variation on LZW)
• Used by Google Maps, Orkut, Google Print, Search History, etc.

Conclusion

• Thanks for not falling asleep
• Any questions?