Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Cloud applications and Google's GFS and BigTable

Cloud applications use distributed storage and scalable structured storage; this note explains Google File System (GFS) and Bigtable: their design, APIs, semantics, architecture and how they are used in cloud applications.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Cloud engineers use distributed storage systems to store very large data (logs, web crawl, backups) and to serve many clients with high throughput. Google File System (GFS) and Bigtable are foundational designs: GFS is a distributed file system optimized for large files and streaming reads/writes; Bigtable is a distributed, sparse, persistent, sorted map used as a scalable NoSQL database. Understanding them explains how cloud services scale, how consistency and replication are managed, and how to design data layout for performance.

Key ideas

  • Replica: a copy of some data stored on a different machine to tolerate failures.

  • Chunk: a contiguous byte range of a file stored as one unit on chunkservers (in GFS).

  • Master: a single (or logically single) server that stores metadata and coordinates (GFS master / Bigtable master).

  • Tablet: a contiguous range of rows of a Bigtable table, served by one tablet server.

  • SSTable: an immutable sorted file format for storing on-disk key-value pairs (used by Bigtable).

  • MemTable: an in-memory write buffer (in Bigtable) that holds recent updates before they are flushed to SSTables.

  • Chubby: a highly-available lock service used by Google for coordination (e.g., to store small metadata and elect masters).

  • GFS (design summary):

    • GFS is optimized for large files and large sequential reads/writes, where workloads include many large streaming reads, large sequential writes (e.g., appends), and component failures are common.
    • Files are split into fixed-size chunks (typical size used in original GFS design: 64 MB). Chunks are identified by a 64-bit chunk handle.
    • Each chunk is stored on multiple chunkservers (replication factor r, commonly 3). A single master stores namespace, file-to-chunk mappings and chunkserver locations; chunk data is on chunkservers.
    • Clients interact directly with chunkservers for data transfer; they ask the master for metadata and chunk locations.
    • For writes to a chunk, the master grants a lease to one replica as the primary and the rest as secondaries. The primary decides an order for concurrent writes and forwards that order to secondaries; the client pipelines the data through the replicas in a chain (closest first), with each replica forwarding to the next to reduce network load.
    • GFS provides relaxed consistency: after a successful write with no concurrent mutations, the affected region is defined (identical across replicas) and subsequent reads will reflect that write; with concurrent writes to overlapping regions, results may interleave but are consistent across replicas. GFS provides an atomic 'record append' operation: it appends the data at least once atomically, may insert padding to maintain atomicity at chunk boundaries, and may result in duplicate records under some failure conditions (at-most-once is not guaranteed).
    • Master maintains chunk leases (to determine primaries) and version numbers to detect stale replicas; chunkservers maintain per-block checksums (e.g., per 64 KiB) to detect corruption during reads/writes; the system re-replicates on failure or corruption.
    • Master is a metadata bottleneck in theory, but workload is designed so data transfer bypasses the master; master handles metadata and control.
  • Bigtable (design summary):

    • Bigtable provides a sparse, distributed, persistent, sorted map. Exactly: map<(row: string, column: string, timestamp: int64)> -> string. Rows are lexicographically ordered by row key.
    • Table schema: a set of column families (must be declared); within each family, columns (called qualifiers) can be created dynamically. Each cell (row, column, timestamp) stores a value.
    • Bigtable stores multiple versions per cell indexed by timestamp; the read API returns the latest version ≤ requested timestamp. All mutations to a single row are atomic; cross-row or cross-table transactions are not supported.
    • Data is split into tablets (ranges of rows). A Bigtable master assigns tablets to tablet servers. Tablet servers manage writing to memtables and flushing to SSTables. Tablets split automatically when they grow too large; a special METADATA table (and a root tablet, whose location is stored in Chubby) maps row ranges to tablet servers, which clients consult to locate tablets (the master is not in the data path).
    • Write flow: the tablet server appends each mutation to a commit log (on GFS) and then updates its in-memory memtable; when the memtable grows, it is flushed to disk as an immutable SSTable. Reads consult the memtable and a sequence of SSTables (newer SSTables first), use a block cache, and may use Bloom filters to avoid unnecessary disk seeks.
    • Compaction (merge): the system periodically merges SSTables to reduce number of files and remove deleted/old versions (minor and major compactions).
    • Bigtable relies on a small, highly-available service (Chubby) for master election and to store small metadata.
    • Design goals: low-latency reads/writes, high throughput, strong locality when row keys are chosen to colocate related rows.
  • Differences and interplay:

    • GFS stores files (byte streams, chunked), Bigtable stores structured sparse rows. Bigtable may store its SSTables and commit logs on a distributed filesystem like GFS.
    • GFS focuses on throughput for large streaming reads/writes; Bigtable focuses on random reads/writes on structured data with versioning.
  • Diagrams to draw in an exam (describe exactly):

    • GFS architecture: draw a box 'Master' at top center, several boxes 'Chunkserver' below (label each with stored chunk IDs and replica markers), and a 'Client' on the left with arrows: Client -> Master (metadata requests), Master -> Client (chunk locations), Client -> Chunkserver (read/write data). Show replication arrows between chunkservers for re-replication and label the primary/secondary for one chunk.
    • Bigtable architecture: draw a box 'Master', several boxes 'TabletServer' each with 'MemTable + SSTables', and clients that discover tablet locations by consulting the root tablet/METADATA (root location via Chubby) and then talk directly to the appropriate TabletServer; the Master is not in the data path. Show the tablet server appending to the commit log before updating the memtable. Indicate a Chubby box used for master lock and root tablet location.

Assumptions to state in answers: chunk size (use the value exam expects; original GFS uses 64 MB), replication factor default 3, master is a single logical server but implemented with master backup; Chubby is used for coordination.

Formulas

For this programming / architecture topic list the important API and sizing syntax to remember:

  • GFS API (basic operations): Create(filename), Open(filename) -> filehandle, Read(filehandle, offset, length) -> bytes, Write(filehandle, offset, data), RecordAppend(filehandle, data) -> offset(s), Snapshot(filename).
  • Bigtable API (basic operations): CreateTable(table, column_families), Set(table, rowkey, column_family:qualifier, value, timestamp?), Get(table, rowkey, column_family:qualifier, timestamp? -> value), Delete(table, rowkey, column_family:qualifier, timestamp?), Scan(table, start_row, end_row, filters?).
  • Chunk index calculation (useful numeric): chunk_index = floor(offset / chunk_size), chunk_internal_offset = offset - chunk_index * chunk_size.
    • Effective usable capacity (with replication factor r): usable_bytes = total_bytes / r.
    • Symbols: offset in bytes; chunk_size in bytes; chunk_index is an integer index of the chunk (0-based).

Worked examples

  1. Which GFS chunk holds offset 200 MiB? (use chunk size 64 MiB)

    • Given: chunk_size = 64 MiB, offset = 200 MiB.
    • Formula: chunk_index = floor(offset / chunk_size).
    • Compute: 64 * 3 = 192 MiB, 64 * 4 = 256 MiB, so floor(200/64) = 3.
    • chunk_internal_offset = 200 - 192 = 8 MiB.
    • Answer: The byte at offset 200 MiB is in chunk index 3 (zero-based) at internal offset 8 MiB. (Chunk 3, offset 8 MiB).
  2. Trace an append in GFS with replication factor 3 (step-by-step):

    • Setup: Three replicas A (primary), B, C hold chunk H. Client wants to RecordAppend(data D).
    • Steps:
      1. Client asks master for chunk locations of H.
      2. Master returns replicas A,B,C and current primary lease holder (A).
      3. Client sends data D to one replica (typically the closest); replicas forward it in a pipeline (A->B->C) so all hold the buffered data; each replica acknowledges receipt of the buffer (not yet committed).
      4. Client sends an Append RPC to primary A with names of replicas that have the buffer.
      5. Primary A chooses an offset (end of chunk) and assigns write order; primary sends write RPCs to secondaries B and C to commit the data at that offset in the chosen order.
      6. Secondaries commit and reply; primary, after collecting replies (or after its lease/timeout rules), replies success to client with the final offset(s). If a failure occurs, master re-replicates or client retries as specified.
    • Note: If concurrent appends occur, GFS guarantees that each append is atomic but may be applied more than once in rare failures, so clients should design idempotency when needed.
  3. Bigtable read after writes and compaction (example):

    • Scenario: Row 'r1', column 'cf:cq'. Writes:
      • t=100: Set('r1', 'cf:cq') = 'A'
      • t=200: Set('r1', 'cf:cq') = 'B'
    • Read: Get('r1', 'cf:cq', timestamp=150) -> returns latest ≤150 which is 'A'. Get with no timestamp returns latest (B). If memtable contains B and SSTable contains A, read consults memtable first then SSTables.
    • Answer: Get('r1',...,150) -> 'A'; Get('r1',...) -> 'B'.

Common mistakes

  • Mixing roles: in GFS, the primary does not hold all data; it coordinates ordering only. Data is stored on all chunkservers.
  • For Bigtable, forgetting that column families must be declared but qualifiers are dynamic.
  • Thinking SSTables are mutable: SSTables are immutable; memtable flush creates new SSTables.
  • Ignoring commit log: Bigtable writes go to a durable commit log before being visible; losing the log can lose recent writes.

For your exam

Kinds of questions you will see:

  • Definitions and short notes: define GFS, chunk, primary/secondary, Bigtable's data model (row, column family, timestamp).
  • Diagrams: draw GFS architecture (master, chunkservers, client paths) or Bigtable architecture (master, tabletservers, memtable/SSTable flow). Label all arrows and components.
  • Derivations/algorithms: show step-by-step how a client reads or writes a chunk in GFS or how Bigtable handles a write (commit log -> memtable -> SSTable -> compaction).
  • Numerical: chunk index/offset calculations, capacity planning using replication factor.
  • Short design question: propose a row-key design to colocate related rows for locality (explain lexicographic ordering and risks of hotspotting).

What full-marks answers must include:

  • Precise definitions of terms used (bold them in your notes if required) and assumptions (e.g., chunk size, replication factor) if not specified.
  • Correct control flow: which component is contacted for metadata and for data, and exact sequence of RPCs for write/read.
  • Diagrams with labels and arrows as described above.
  • For Bigtable answers, explain versioning/timestamp semantics and mention memtable + SSTable + commit log + compaction.

Quick check

  1. In GFS, who gives the client the chunk locations: master or chunkserver?
  2. In Bigtable, are column families declared or dynamic?
  3. If chunk size = 64 MiB and file offset = 0, what is chunk_index and internal offset? Answers: master; column families are declared, qualifiers are dynamic; chunk_index = 0, internal offset = 0.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?