48. Google Papers: GFS, Bigtable, Spanner, MapReduce, Borg

Google publishes its internal systems via papers. The ideas in those papers seeded most modern distributed-systems infrastructure. For a Google interview, knowing them — at least at high level — signals fluency with the field's foundations.

48.1 GFS: Google File System (2003)

The first big paper. A distributed filesystem for huge files (GB+) and write-once, read-many workloads.

Architecture

One master (and shadow): metadata only (filename → chunks → replicas), in memory.
Many chunkservers: store fixed-size 64 MB chunks; commodity hardware.
Clients: ask master for chunk locations; transfer data directly with chunkservers.

Key ideas

Append-mostly: optimized for sequential writes; small random writes ignored.
Large chunks (64 MB): fewer master interactions, more sequential I/O.
Triple replication by default; rack-aware placement.
Master is a single point, but only on metadata path; data goes peer-to-peer.
Eventual consistency for atomic record append; clients tolerate.

Lineage

HDFS = open-source GFS clone.
Colossus: Google's GFS successor (2010s+); finer chunks, distributed metadata, erasure coding, better small-file support.

What an interviewer wants

Single-master metadata + commodity chunkservers + replication.
Why large chunks and append-mostly were the right trade-off.

48.2 MapReduce (2004)

Programming model for batch processing on a cluster. (See chapter 30.)

Map function: key/value → list of key/value.
Reduce function: key + list of values → list of values.
Framework handles distribution, shuffle, fault tolerance.

Importance

Made big-data computation accessible to ordinary engineers. Inspired Hadoop, Spark, Beam.

Now

Inside Google, MapReduce mostly replaced by FlumeJava (higher-level), and Dataflow (unified batch+stream). Externally, Spark dominates.

48.3 Bigtable (2006)

Sparse, distributed, multi-dimensional sorted map.

(row_key, column_family:column, timestamp) → value

Built on GFS for storage.
Tablet servers manage row ranges; master coordinates.
LSM internals (memtable + SSTable).
Used by: Search, Maps, Gmail, Analytics.

Properties

Single-row transactions (atomic per row).
Petabyte scale.
Schemas: column families predefined; columns arbitrary within.

Lineage

HBase: open-source clone.
Cassandra: combines Bigtable's data model with Dynamo's leaderless replication.

What to know

Row key design = the most important decision.
LSM trees + SSTables + Bloom filters in every storage layer descended from this.

48.4 Chubby (2006)

Distributed lock service + small file storage. Provides:

Coarse-grained locks.
Leader election.
Service discovery.
Configuration storage.

Built on Paxos. Inspired ZooKeeper, etcd.

Most Google services use Chubby (e.g., Bigtable master election, GFS root metadata).

Lineage

ZooKeeper (Yahoo) → ZAB (similar protocol).
etcd (CoreOS) → Raft.

48.5 Dremel (2010)

Interactive SQL on petabytes.

Columnar storage with nested data (Protocol Buffers shape).
Tree-structured execution (root → intermediate → leaves) for parallel aggregation.
Sub-second on TB+.

Lineage

BigQuery (Google Cloud).
Apache Drill, Apache Impala — open-source clones.
Influenced Snowflake, Athena, Presto/Trino designs.

48.6 Spanner (2012)

Globally distributed, ACID, relational, scalable. The "have your cake and eat it" system.

Key innovations

TrueTime: bounded clock uncertainty (~1-7 ms) via GPS + atomic clocks.
Commit wait: every transaction waits out the uncertainty before acknowledging → external consistency.
Paxos per shard for replication.
2PC + TrueTime for cross-shard transactions.

Result

SQL queries.
ACID transactions.
Globally distributed.
Automatic sharding and rebalancing.

Cost

~7ms commit wait per transaction.
Operationally complex (atomic clocks, GPS).

Lineage

Cloud Spanner (managed offering).
CockroachDB, YugabyteDB, TiDB — open-source distributed SQL approximating Spanner.
F1: relational layer on top of Spanner used internally for ad system.

What to know

TrueTime is the killer idea: physical clock uncertainty made operational.
Strict serializability across continents.
Most "distributed SQL" today traces lineage here.

48.7 Borg (2015 paper)

Google's cluster manager. Predates Kubernetes by ~10 years.

Key ideas

Declarative job specs.
Tasks share machines (bin-packing).
Priority + preemption: high-pri jobs preempt low-pri.
Two-level priority (production + batch): batch fills idle.
Quotas for fairness across teams.
Allocs: resource reservations.
Borgmaster + Borglet (control + agent), like Kubernetes.

Lineage

Kubernetes is Borg's open-source successor (Brendan Burns and others started K8s after working on Borg).
Omega (research successor): more flexible scheduler.

48.8 MillWheel (2013)

Low-latency stream processing.

Per-key state.
Strong consistency despite failures.
Watermarks for time semantics.

Lineage

Cloud Dataflow / Apache Beam.
Influenced Flink and Spark Streaming.

48.9 Photon (2013)

Joining streams of click logs in real time.

Lossless, exactly-once joining of two streams within a window.
Multiple datacenters.
Per-record IDempotent IDs.

The technique is now common in stream processing libraries.

48.10 Mesa (2014)

Petabyte-scale data warehousing for ads.

Strong consistency.
Real-time updates.
Multi-tier storage.

Internal to Google ads systems.

48.11 Maglev (2016)

Software L4 load balancer at Google scale.

Consistent hashing.
Stateless on the data plane (no flow tracking required).
Each packet handled independently → easy scaling.

Now imitated in software LBs across the industry.

48.12 Zanzibar (2019)

Global authorization service.

Models permissions as relations: (object, relation, user).
Group inheritance, cross-tenant.
Causal consistency via Spanner.
New permission grants visible globally in seconds.

Open-source counterparts: SpiceDB, OpenFGA, Ory Keto.

48.13 Borg → Kubernetes diffs

	Borg	Kubernetes
Unit	Job (with tasks)	Pod
Multi-tenant priority	Yes (production / batch)	Less native
Bin packing	Aggressive	Configurable
Storage abstraction	Limited	PV / PVC / CSI
Service discovery	Built into infra	Labels + Services
Multi-cluster	Native	Federation (less mature)

48.14 BeyondCorp (2014+)

Zero-trust network model.

No VPN; every request from any device authenticated, authorized, encrypted.
Identity-aware proxy at the front.
Device trust (managed device registry).

Heavily influential on the broader zero-trust movement.

48.15 Tip for Google interviews

You don't need to recite papers verbatim. You do need to:

Recognize the names when invoked ("Bigtable-style storage," "Spanner-like consistency").
Know what each contributes ("TrueTime makes external consistency possible").
Connect them ("Cassandra = Bigtable data model + Dynamo replication").
Use the patterns when designing ("for write-heavy time-series, I'd use a wide-column store like Bigtable").

48.16 Reading order if you have time

If you read any: read Bigtable, Spanner, MapReduce, GFS, Borg, in roughly that order. Each ~15-20 pages and well-written.

Key takeaways

Google's papers seeded modern distributed-systems infrastructure.
GFS / Bigtable / Spanner / Borg are the foundational set.
TrueTime + Spanner = the planet-scale SQL story.
Borg = Kubernetes's intellectual ancestor.
Knowing these signals fluency in a Google interview.