bits.

Distributed storage · 2003 · Sanjay Ghemawat, Howard Gobioff & Shun-Tak Leung

The Google File System

Redesign storage around measured workload facts: routine component failure, huge files, streaming reads, append-heavy writes, and commodity machines.

How to read the original

  1. Read Design Overview, especially Assumptions and the consistency discussion.
  2. Read Leases and Mutation Order to trace control separately from data movement.
  3. Read Atomic Record Appends and distinguish an atomic record from exactly-once application processing.

Workload assumptions justify the architecture

GFS is designed around large files, streaming access, frequent component failures, and append-heavy workloads. It separates metadata coordination from bulk data transfer and uses replicated chunks. The paper’s consistency discussion is essential: its interface is not simply a conventional local filesystem distributed across machines with every familiar promise preserved. Read each mechanism against the workload and failure assumptions that make its costs acceptable.

Original reconstruction: locate data without routing it through the master

For a toy store, choose 64 MiB chunks and three replicas per chunk. A 160 MiB file requires three chunks with logical lengths 64, 64, and 32 MiB. The replicated payload occupies 480 MiB if we count only actual file bytes, before metadata and implementation overhead. Counting every chunk as a fully allocated 64 MiB object would instead give 576 MiB, so storage estimates must state whether they describe capacity, reserved space, or actual written payload.

A client reading an offset determines the corresponding chunk index, asks the master for the chunk identity and replica locations, then reads the data from an appropriate chunkserver. Caching location information reduces repeated metadata requests. The master remains a control-plane dependency even though it is not required to relay every payload byte. A client using stale locations must handle failures and refresh its metadata rather than assuming that cached placement is permanent.

Trace an append with a lost reply

A client wants to append record R with application identifier 42. A designated primary orders the mutation, and replicas apply the operation according to the protocol. Suppose the record is appended successfully but the acknowledgement is lost. The client cannot distinguish this from an unsuccessful attempt using the timeout alone, so it retries.

The storage contract can permit the record to appear more than once. Atomic placement of a record does not imply exactly one occurrence across retries. A consumer should therefore parse valid records and use application identifiers to suppress duplicate processing when that is the application’s required behavior. If the consumer sends an email for every encountered copy of identifier 42, storage-level atomicity has not protected the external effect.

Now imagine a partial failure leaves replicas differing around an unsuccessful mutation. The consistency model tells the application which regions and operation outcomes can be relied upon. Assuming byte-for-byte identity everywhere after every failed operation would erase precisely the boundary the paper asks readers to understand.

Leases order mutations, but failure handling still matters

A primary lease delegates mutation ordering for a limited interval. The master must avoid overlapping authority that allows incompatible primaries to order the same chunk simultaneously. A delayed message from a former primary, a restarted server with stale state, and a missing replica all require protocol treatment. Replica count alone does not establish correctness; the system must know which replicas are current and eligible.

For a lab, draw separate arrows for metadata requests, data transfer, mutation ordering, and acknowledgements. Kill a replica after data has arrived but before the response completes. Record what the client knows, what each replica stores, and which recovery action is safe. This is more informative than testing only whether three files were copied successfully.

The design’s strengths do not make it universally suitable. Many small files increase metadata pressure, and applications demanding different write semantics need a different contract or additional machinery. The transferable method is to expose workload facts, select an interface that the application can actually use, and analyze ordinary failures as expected operating cases.

Reconstruction exercise

A toy system uses 32 MiB chunks and three replicas. A 70 MiB file is written completely. Calculate chunk count and replicated payload bytes in MiB, then contrast the result with reserving three full chunk capacities per replica. Next, a record with ID 9 appears twice after a lost append acknowledgement. Explain why this does not by itself contradict at-least-once append behavior and design a consumer rule for one logical update.

Worked solution

The file occupies three logical chunks of 32, 32, and 6 MiB. Three replicas of the actual payload require 70×3=210 MiB, excluding metadata and overhead. Reserving three full 32 MiB chunks on each of three replicas would reserve 288 MiB, a different accounting quantity. For the append, a successful first operation followed by a lost reply can cause the client to retry, producing another copy of the same logical record. At-least-once placement permits this duplication. A consumer can persist an operation ID alongside the state change and atomically reject a repeated ID, so both copies represent one logical update. The persistence boundary matters: keeping the seen-ID set only in volatile memory can replay the update after a crash. External effects such as notifications need their own deduplication or transactional delivery contract.

Test the limits and transfer the idea

1. Failure and storage trace · allow 45 minutes

Separate append success from exactly-once delivery

Scale the paper's record-append mechanism to 1,024-byte chunks. A file's last chunk currently contains 900 bytes. An application record is 200 bytes, including its framing and stable record id. Assume all replicas receive every write in this particular trace, but the first success reply to the client is lost. The client retries the same record, and the second reply arrives.

Trace padding, both append offsets, and the final file length. Calculate how many new bytes are unique application record data, duplicate data, and padding. Design a reader rule that produces one application event. Explain why the favorable replica behavior here must not be generalized to every failed GFS append.

Get a starting hint

The record cannot fit in the current chunk, so the primary pads to the boundary and the append is retried in the next chunk. Losing a success reply can cause a second complete copy at a later offset.

Compare your reasoning with the worked solution

Only 124 bytes remain in the first chunk, so the 200-byte record cannot fit. Padding fills offsets 900 through 1,023. The first complete append begins at global offset 1,024 and occupies bytes through 1,223. Its reply is lost. Retrying the same logical record appends another 200-byte copy at offset 1,224, ending at 1,423. The resulting length is 1,424 bytes.

The extension beyond the initial 900 bytes is 524 bytes: 124 padding bytes, 200 bytes for one unique record, and 200 duplicate bytes. The record satisfies the scaled one-fourth-chunk size restriction because 200 ≤ 256. Neither padding nor a duplicate indicates that the successful returned record was torn across chunks.

A reader first validates framing, lengths, and checksums to distinguish complete records from padding or damaged fragments. It then uses the stable application record id to suppress repeats. If processing has durable side effects, recording the id and applying the effect must be coordinated atomically; a volatile set alone does not survive a consumer crash. Reusing an id for a different payload must be treated as a conflict, not silently discarded.

In this chosen execution all replicas receive both copies, but the paper explicitly permits differing fragments and duplicates in regions affected by failures. Its successful append guarantee identifies a complete record at the returned offset, not bytewise identity of every intervening region or exactly-once application effects. The tiny chunk size and particular lost-reply trace are teaching choices, not reported GFS measurements.

Check your reasoning

  • Computes padding 124, offsets 1,024 and 1,224, and final length 1,424.
  • Separates unique bytes, duplicates, and padding and checks the size restriction.
  • Designs framing plus durable deduplication without claiming all replicas always match.

2. Concurrency trace · allow 45 minutes

Construct a consistent but undefined write result

Use two-byte chunks and a four-byte file initially 0000. Two applications concurrently write the entire four-byte region: writer A writes abcd and writer B writes WXYZ. Each application write is split into one mutation per chunk. The first chunk's primary orders A then B; the second chunk's primary orders B then A. Every replica applies each chunk's specified order successfully.

Trace the final bytes at each replica. Classify the combined region using the paper's distinction between consistent and defined. Then show what happens if one secondary applies first-chunk mutations in data-arrival order B then A instead of the primary's order. Explain why changing ordinary writes into record appends is a semantic change, not a drop-in fix for every overwrite workload.

Get a starting hint

Agreement among replicas is different from preserving an entire application write. GFS separates the route by which data arrives from the order in which mutations are committed.

Compare your reasoning with the worked solution

The first chunk starts as 00, becomes ab under A, then WX under B. The second starts as 00, becomes YZ under B, then cd under A. Every correctly ordered replica therefore ends with WXcd. The replicas agree, so the combined region is consistent. It is not the complete output of either writer, so the concurrent application writes do not establish a defined four-byte result. Atomicity of each ordered chunk mutation did not make the multi-chunk application operation atomic.

If a secondary instead applies the first chunk in arrival order B then A, it ends with ab while the primary ends with WX. Keeping the second chunk cd gives that secondary abcd while the primary has WXcd. Readers can now obtain different bytes from different replicas, so the region is inconsistent. Receiving data earlier is not authority to commit it earlier.

The paper's control path assigns mutation order independently of the data-transfer pipeline. The example uses a deliberately tiny chunk size to expose the distinction, not the real system's chunk geometry. It also assumes all listed writes succeed; failure introduces additional outcomes.

Record append supplies a different contract: append this record contiguously at a chosen offset, at least once. It can preserve complete records from concurrent producers but does not replace bytes at the caller's requested position. A workload that requires an atomic in-place update across several chunks needs additional coordination, a different data representation, or a different storage contract. Calling both operations writes must not hide their semantic difference.

Check your reasoning

  • Produces WXcd on every correctly ordered replica and classifies the combined region.
  • Shows a replica-order violation yielding abcd versus WXcd.
  • Explains data-flow/control-order separation and the different record-append contract.

Check your understanding

Why does a client read payload directly from a chunkserver after consulting metadata?

  • It removes every master failure mode.
  • It makes replica state permanently immutable.
  • It keeps bulk data traffic off the metadata coordinator’s path.
  • It guarantees a cached location never changes.
Explanation

Separating control and data paths reduces master involvement in payload transfer.

An append retry produces two intact copies of one record. Which application requirement remains unsolved?

  • Exactly-once processing of that logical operation.
  • Whether each copy has an intact record boundary.
  • Whether every replica must invent a different record identifier.
  • Whether a successful append can ever have a byte offset.
Explanation

Atomic record boundaries and retry deduplication are different properties.

Original paper and sources

Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. The Google File System. Proceedings of SOSP, 2003.

Read the original paper →

Read the primary paper: Google Research