Library / Papers

The Google File System (paper)

How Google built a file system for huge files and constant machine failures: one master for metadata, many chunk servers, and append-heavy workloads. The ancestor of HDFS.

AdvancedDistributed Systems Storage Engines Replication

By Ghemawat, Gobioff and Leung · Google · Added 2026-10-12

Read the paper

All content belongs to Ghemawat, Gobioff and Leung / Google. We only link to it and give credit. Report a problem

Learn this paper

About 37 min left. Your work is saved as you go.

What you are about to study

Google wrote this paper. Read the abstract and headings first. It assumes you are comfortable with distributed systems.

Ideas you will meet

Distributed Systems: Consensus, time, failure and the fundamentals of scale-out.
Storage Engines: Write-ahead logs, B-trees and LSM-trees.
Replication: Leader/follower, multi-leader and leaderless replication.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

Classic System Designs · 14 minDesign a key-value storeA Dynamo-style distributed store: partitioning, replication, quorums, conflict handling and how reads and writes reach disk.Read here

The problem

A key-value store supports put(key, value) and get(key). A distributed one must also:

Store far more than one machine can hold.
Keep serving when machines or networks fail.
Have low latency for both reads and writes.
Let you tune consistency against availability.

We use a Dynamo-style design, which is the model behind several widely used stores.

Partition the data

Spread keys across nodes with consistent hashing (previous lesson). Virtual nodes keep the load even and let you add capacity gradually. Any node can act as the coordinator for a request, so there is no single leader to bottleneck on.

Replicate each key

Copy every key to N nodes: the owner and the next N-1 distinct nodes clockwise on the ring. Spread replicas across racks or zones so one failure does not take out all copies.

Figure SDA-CSD-03-1 · Replicating each key to N nodes · © forcsguy.com

Tunable consistency with quorums

Choose three numbers:

N: number of replicas.
W: replicas that must acknowledge a write.
R: replicas that must answer a read.

Setting	Behaviour
`W + R > N`	Reads overlap the latest write: strong-ish consistency
`W = 1, R = 1`	Fastest and most available, but reads can be stale
`W = N, R = 1`	Fast reads, writes fail if any replica is down

You pick the trade-off per use case, which is what makes this design flexible.

A quorum write, step by step

Figure SDA-CSD-03-2 · Coordinator and a write quorum (N=3, W=2) · © forcsguy.com

When replicas disagree

Replicas can hold different versions, for example after a partition.

Versioning: attach a version (a vector clock) to each value so the system can tell whether one version supersedes another or they were concurrent.
Reconciliation: for concurrent versions, either the application merges them (shopping cart: union the items) or the system uses a simple rule such as last-write-wins, which can silently discard data.

Two writers at once: conflicts and vector clocks

Figure SDA-CSD-03-3 · Concurrent writes create two versions · © forcsguy.com

Figure SDA-CSD-03-4 · Vector clocks across writes · © forcsguy.com

A clock A is an ancestor of B if every counter in A is less than or equal to the matching counter in B. If each has some counter larger than the other's, the versions are siblings and need merging.

Failure handling

Detection: nodes exchange gossip messages about who is alive, so there is no central monitor to fail.
Temporary failure: if a replica is down, another node accepts the write and stores a hint, handing it over when the replica returns (hinted handoff).
Permanent repair: periodically compare replicas using Merkle trees (hashes of key ranges) and copy only what differs (anti-entropy).
Data centre failure: replicate across regions for the keys that need it.

Noticing failures: gossip

Figure SDA-CSD-03-5 · Gossip failure detection · © forcsguy.com

Staying available through a short outage

Figure SDA-CSD-03-6 · Sloppy quorum and hinted handoff · © forcsguy.com

Repairing replicas for good: Merkle trees

Figure SDA-CSD-03-7 · Comparing replicas with Merkle trees · © forcsguy.com

More failure-handling detail

Do not trust one witness. One node saying "that server is down" is not enough; require agreement from several independent sources (gossip gives this naturally: a node is marked down only after others also see its heartbeat counter stall).
Sloppy quorum. A strict quorum can block when the usual replicas are down. Instead, take the first healthy servers on the ring for the write or read, and let a stand-in hold the data with a "hint". When the real replica returns, the stand-in hands the data back (hinted handoff). You gain availability and give up the strict overlap guarantee for a while.
Replica placement. When walking the ring for N replicas, skip virtual nodes that belong to a server already chosen, and spread replicas across data centers, because nodes in one site often fail together.
Bigger machines. Give a more powerful server more virtual nodes so it takes a proportionally larger share.
Conflicting versions. Vector clocks grow as more servers touch a key; cap their length and accept that, rarely, old entries dropped make some conflicts harder to untangle.

Inside one node: how writes and reads hit disk

Figure SDA-CSD-03-8 · Write and read path on one node · © forcsguy.com

Write path

Append to a commit log (sequential, fast, crash-safe).
Apply to an in-memory sorted structure (the memtable).
When the memtable is full, flush it to an immutable sorted file on disk; background compaction merges files.

Read path

Check the memtable.
If missing, check the files, using a Bloom filter per file to skip files that definitely do not contain the key.
Merge results, newest wins.

This log-structured design turns random writes into sequential ones, which is why such stores handle huge write volumes.

One node, many jobs

Figure SDA-CSD-03-9 · What every node does · © forcsguy.com

Summary of the design

Concern	Technique
Scale out	Consistent hashing with virtual nodes
Durability and availability	N replicas across zones
Consistency dial	Quorums (W, R)
Conflicts	Vector clocks and merge logic
Failure detection	Gossip
Temporary and permanent repair	Hinted handoff, Merkle-tree anti-entropy
Fast writes	Commit log, memtable, sorted files

Worked numbers: how many nodes?

Target: 1 billion keys averaging 1 KB, with 3 replicas, serving 100,000 operations per second.

Raw data: 1 B x 1 KB = 1 TB. With three replicas, 3 TB of storage across the cluster, before overhead for indexes and compaction (plan for about 2x headroom on disk for compaction, so around 6 TB).
Per-node capacity: if one node comfortably holds 1 TB of data and serves about 10,000 operations per second, 12 to 15 nodes cover both storage (3 TB / 1 TB, with room) and throughput (100,000 / 10,000 x 3 for replication on writes and headroom).
With a 20-node ring each node owns about 5% of the keys, and losing one node moves its 5% (about 150 GB of replicas) to its neighbours: repair takes minutes to hours, which is why you keep spare capacity.

When a replica is down: hinted handoff

With W = 2 of N = 3, a write must reach two replicas. Suppose node C is down.

The coordinator sends the write to A, B and C; A and B acknowledge, so the write succeeds.
For C, a hint ("this write was meant for C") is stored on a healthy node.
When C returns, the holder of the hint replays the write to C.

If the node is down for too long the hints are dropped, and a slower anti-entropy repair takes over.

Figure SDA-CSD-03-10 · A write while one replica is down · © forcsguy.com

Anti-entropy with Merkle trees

Replicas can still drift apart (a hint was lost, a disk was corrupted). Comparing every key between two replicas is far too expensive. A Merkle tree summarises a key range with hashes: each leaf is a hash of a small bucket of keys, and each parent is a hash of its children. Two replicas compare root hashes; if equal, the whole range matches. If not, they compare the children and descend only into the branches that differ, until they find the few buckets that actually disagree and exchange just those keys.

Figure SDA-CSD-03-11 · Finding differences without comparing every key · © forcsguy.com

Mistakes people make

Hot keys. One extremely popular key overloads its replicas whatever the cluster size. Cache it in front or split it into several keys.
Large values. Multi-megabyte values hurt latency and replication; store big blobs in object storage and keep a pointer.
Expecting joins and secondary queries. A key-value store answers "get by key". If you need other queries, add an index structure or use another database.
Resolving conflicts with wall-clock time alone. Skewed clocks lose writes; prefer version vectors or let the application merge.
Forgetting tombstones. Deletes leave markers that must live long enough to reach all replicas, and be compacted away later. Skipping this resurrects deleted data.
Never running repair. Without regular anti-entropy, rarely read data can silently diverge.

Try it yourself

Build the consistent hash ring lab to see how few keys move when a node joins, the Bitcask lab for one node's storage engine, and the write-ahead log lab for crash recovery. Then read the consistency and CAP lesson for the quorum rule used above.

More on this site

Replication: keep copies

Replication keeps the same data on more than one machine. Reasons:

Availability: if one machine dies, another has the data.
Read capacity: reads can go to any copy.
Locality: place a copy near users in another region.

The most common arrangement is leader and followers. All writes go to the leader, which sends the changes to followers. Reads can use followers.

Figure SDA-FND-05-1 · Leader and follower replication · © forcsguy.com

Many teams hide the split between the primary and the replicas behind a small router, so the application does not need to know:

Figure SDA-FND-05-2 · Read and write splitting through a router · © forcsguy.com

Synchronous or asynchronous

Synchronous: the leader waits for followers to confirm before saying "done". Safer, but slower, and a down follower can block writes.
Asynchronous: the leader confirms immediately and followers catch up. Fast, but a follower can be behind, and a leader crash can lose the most recent writes.

Most systems use asynchronous replication for most followers, sometimes with one synchronous follower as a safety net.

Replication lag

Because followers can lag, a user may write something and then read an older value from a follower. Fixes include reading the user's own recent writes from the leader, or tracking how fresh each replica is. This is the first taste of a bigger idea, consistency, covered in lesson 7.

When the leader fails

A follower must be promoted (failover). That needs failure detection and agreement on who the new leader is, so that two machines do not both believe they are the leader (a split brain). This is why teams rely on tested tooling or managed databases for failover rather than hand-written scripts.

Read-after-write consistency

With asynchronous replicas, a user can save something and then not see it: the write went to the primary, the next read hit a replica that is a few seconds behind. Three common fixes:

Send reads that must be fresh (the user's own profile, an order just placed) to the primary.
For a short window after a user writes, route that user's reads to the primary.
Let the router check whether a replica has caught up to the user's last write; if not, read from the primary or wait.

A database proxy in front of the cluster can do this routing so application code stays simple, at the cost of one more hop and one more component that must itself be highly available.

Before: one database

After: primary with read replicas

What changed

Reads are spread across copies
A copy can be promoted if the primary fails
Replicas may lag slightly behind the primary

Sharding: split the data

Replication does not help when the data or the writes no longer fit on one machine. Sharding (partitioning) divides the data so each shard holds a part. Each shard is usually replicated too.

Choosing a shard key

The shard key decides which shard owns a row. A good key:

Spreads data evenly, so no shard is much bigger than the others.
Spreads traffic evenly, so no shard is a hot spot.
Matches your queries, so most queries touch one shard.

Common schemes:

Scheme	How	Watch out for
Range	key ranges per shard	hot spots, e.g. newest dates
Hash	hash(key) mod N	adding shards remaps most keys
Directory	a lookup table says where each key lives	the directory is another thing to run and scale
Consistent hashing	keys and nodes placed on a ring	needs virtual nodes to balance well

Consistent hashing in one picture

Place both servers and keys on a ring. A key belongs to the first server clockwise from it. Adding a server only takes keys from its neighbour; the rest do not move.

Horizontal and vertical partitioning

Sharding is horizontal partitioning: the rows of a table are split across machines, each shard holding the same columns for a different set of rows. Vertical partitioning splits by columns or by feature instead: rarely used or large columns (a profile photo, a long description) move to a separate table or store, or whole groups of tables go to different databases (users on one, orders on another). It is simpler than sharding and keeps frequently read data small and fast, but it does not help when a single table's rows outgrow one machine.

What sharding costs you

Cross-shard queries and joins become slow or need extra work.
Transactions across shards are hard (lesson 8 touches on how systems cope).
Rebalancing when a shard gets too big is operational work.
More moving parts to monitor.

A worked example: sizing replicas and shards

Replicas for reads. A social app has 20,000 reads and 1,000 writes per second. One database node can do about 5,000 simple operations per second. A primary alone is hopeless. With writes of 1,000 per second on the primary, you have capacity left for about 4,000 reads, so you need at least four replicas to serve 20,000 reads (16,000 on replicas plus 4,000 on the primary) with no headroom, so six in practice. Adding replicas scales reads almost linearly. It does nothing for the 1,000 writes, which still all go to one primary.

Shards for writes. If writes grow to 12,000 per second, no single primary can take them. Split the data into shards, each with its own primary: with 4 shards each takes about 3,000 writes per second. Each shard then has its own replicas for reads. Your final count is shards x (1 primary + replicas), for example 4 x (1 + 2) = 12 database nodes.

Walking through a failover

Replication is only useful if you know what happens when a primary dies. With asynchronous replication:

The primary acknowledges writes 100 to 140, but the follower has only received up to 135 (replication lag).
The primary crashes. Writes 136 to 140 exist only on the dead machine.
A monitor notices missing heartbeats, usually after several seconds, and promotes the most up-to-date follower to primary.
Clients are redirected. Writes 136 to 140 are lost (or recoverable only when the old primary returns).
When the old primary comes back it must not accept writes as if nothing happened (that would create two primaries, "split brain"); it rejoins as a follower and discards or reconciles what the new primary does not have.

With synchronous replication to at least one follower, step 2 loses nothing, but every write waits for that follower, adding latency and making writes fail if the follower is unavailable. Many systems choose a compromise: wait for one follower to confirm (semi-synchronous), accepting a little latency to avoid losing acknowledged writes.

Choosing a shard key: three examples

User id for a messaging app. Almost every query is "this user's messages", so a hash of the user id keeps each user's data together and spreads users evenly. The pain: a query across all users (an admin search) must ask every shard.
Order date for an orders table. Range sharding by date makes "last month's orders" cheap, but all new writes land on the newest shard, a hot spot, while old shards sit idle. A better key adds a hash of the customer id.
Country for a multi-region product. Good for keeping data near users and meeting data-residency rules, but shards are uneven: one country may hold half your users.

A good key has high cardinality (many distinct values), even load and matches your most common query. Changing it later means moving most of your data, so test it against a sample of real traffic first.

Mistakes people make

Reading from a replica right after writing. The replica may not have the write yet, so users do not see their own change. Read your own writes from the primary for a short time, or route that user to the primary.
Sharding too early. Sharding multiplies operational work: backups, schema changes, cross-shard queries and transactions all get harder. First try indexes, caching, replicas and a bigger machine.
Counting on replicas as backups. A mistaken delete is replicated within milliseconds. Keep real backups and test restoring them.
Forgetting to rebalance. Shards grow unevenly. Plan how to split a shard, ideally with consistent hashing or many small virtual shards that you can move between machines.

Try it yourself

In the System Builder, open "The database goes down". Run it with no replicas and see reads and writes fail, then add replicas and a write queue and compare. For hashing itself, build the consistent hash ring lab and measure how many keys move when you add a node. To place replicas and a queue yourself, open the database-outage design on the free canvas and kill the database.

More on this site

Go deeper on this

A path through videos, articles, other case studies and code on the same ideas as The Google File System (paper).

1
Warm upGet the vocabulary first.
- Courses
  MIT 6.824: Distributed Systems
  Free university course on fault tolerance, replication and consensus with Go labs.
  MITAdvanced
  Study this Original (opens in a new tab)
- Books · Free from the author
  Concurrent and Distributed Systems (Cambridge lecture notes)
  Eight lectures on time, broadcast, replication, consensus and transactions, with notes, slides and video. Free from the author under CC BY-SA.
  University of CambridgeIntermediate
  Study this Original (opens in a new tab)
WatchHow others solve the same problem, on video.
Videos belong to their creators and play from YouTube. More on YouTube (opens in a new tab)
3
ReadEngineers explain it in their own words.
- Papers · Read here
  Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases (paper)
  Why Aurora moves the redo log to a distributed storage layer, so replication and crash recovery become cheap.
  Amazon Web ServicesAdvanced
  Study this Original (opens in a new tab)
- Papers · Read here
  Bigtable: A Distributed Storage System for Structured Data (paper)
  Google's wide-column store: tablets split by key range, a commit log plus sorted files on disk, and the design later copied by HBase and Cassandra.
  GoogleAdvanced
  Study this Original (opens in a new tab)
4
See it in another companyThe same ideas, a different system.
- Case Studies · Read here
  Inside the Magic Pocket
  How Dropbox built its own exabyte-scale block storage, including durability and cost choices.
  DropboxAdvanced
  Study this Original (opens in a new tab)
- Case Studies
  High-performance Replicated Log Service at Twitter
  Building DistributedLog: High-performance replicated log service
  TwitterIntermediate
  Study this Original (opens in a new tab)
5
Read the codeSee how it looks when it is real.
- GitHub
  Kafka Source & Docs
  Apache Kafka source code: read the log, replication and consumer-group internals first-hand.
  apacheAdvanced
  Study this Original (opens in a new tab)
- GitHub
  CockroachDB
  A distributed SQL database built on ranges, Raft and MVCC.
  GitHubAdvanced
  Study this Original (opens in a new tab)

Keep learning

Loading community…

Cookie preferences

The Google File System (paper)

Learn this paper

What you are about to study

The problem

Partition the data

Replicate each key

Tunable consistency with quorums

A quorum write, step by step

When replicas disagree

Two writers at once: conflicts and vector clocks

Failure handling

Noticing failures: gossip

Staying available through a short outage

Repairing replicas for good: Merkle trees

More failure-handling detail

Inside one node: how writes and reads hit disk

One node, many jobs

Summary of the design

Worked numbers: how many nodes?

When a replica is down: hinted handoff

Anti-entropy with Merkle trees

Mistakes people make

Try it yourself

More on this site

Why replicate

Single-leader (primary and replicas)

Multi-leader

Leaderless (Dynamo-style)

Multi-region designs

Partitioning and replication together

Master/slave naming

Checklist

Real-world reading

Replication: keep copies

Synchronous or asynchronous

Replication lag

When the leader fails

Read-after-write consistency

Sharding: split the data

Choosing a shard key

Consistent hashing in one picture

Horizontal and vertical partitioning

What sharding costs you

A worked example: sizing replicas and shards

Walking through a failover

Choosing a shard key: three examples

Mistakes people make

Try it yourself

More on this site

Go deeper on this

Warm upGet the vocabulary first.

WatchHow others solve the same problem, on video.

ReadEngineers explain it in their own words.

See it in another companyThe same ideas, a different system.

Read the codeSee how it looks when it is real.

Keep learning