System Design · Module 12

Google Search and Gmail: Crawl to Index to Serve, and the GFS/Bigtable/Spanner Lineage

This is the first case study in the course: it takes the storage, consensus, and consistency mechanisms from Part A and shows what they actually hold up. Google's own three-stage account of Search — crawl, index, serve — is read against the primary papers that disclose the machinery underneath it: the 1998 prototype's architecture, the 2003 cluster paper, the 2010 shift from batch to incremental indexing, and the GFS→Bigtable→Megastore→Spanner storage lineage that both Search and Gmail sit on. Where Google has not published something — Gmail's internal architecture, current ranking signals — this module says so instead of filling the gap.

Course 40 min read 10 sources As of 2026-09-17 Prerequisite: Modules 3, 5, 6, 7
Google's three-stage Search pipeline: crawling, indexing with a not-guaranteed branch, and serving 1. Crawling discover URLs, fetch, render JS in Chrome 2. Indexing analyze content, store in the index 3. Serving rank hundreds of factors, return results to a query Not indexed crawled, never added indexing is not guaranteed Index: 100s of billions of pages, over 100,000,000 GB (≈ 100 PB) Ranking relevancy: hundreds of factors, undisclosed in detail — Google states it does not accept payment to rank pages higher (out of scope for this module: current ranking-signal internals are not published by Google)
Figure 1. The three stages of Google Search exactly as Google's own developer documentation frames them, with the branch it states explicitly: not every crawled page is indexed1. The rest of this module opens each stage against the primary systems papers Google has separately published.

1. The pipeline, in Google's own words

Google's developer documentation states the shape of Search plainly: "Google Search works in three stages... Crawling: Google downloads text, images, and videos from pages it found on the internet with automated programs called crawlers... Indexing: Google analyzes the text, images, and video files on the page, and stores the information in the Google index... Serving search results: When a user searches on Google, Google returns information that's relevant to the user's query"1. That is the entire official architecture description — three verbs, no internals. This module's job is to attach the systems underneath each verb, using what Google has separately published as engineering papers rather than as marketing copy.

Two scale numbers anchor the rest of the module. First, index size: "the Google Search index covers hundreds of billions of webpages and is over 100,000,000 gigabytes in size"1. Converting units makes the number legible: 100,000,000 GB ÷ 1,000,000 GB/PB = 100 PB — the disclosed index is described as being over 100 petabytes, not gigabytes or terabytes, and covering hundreds of billions of individual pages. Second, rendering: crawling in 2026 is not a text fetch. "During the crawling process, Google renders the page and runs any JavaScript it finds using a recent version of Chrome, similar to how your browser renders pages you visit"1 — a full browser engine executes the page's script before any text reaches the indexer, which is why a page whose content is generated client-side by JavaScript can still be indexed at all.

The branch drawn in Figure 1 is stated as directly as the pipeline itself: "indexing isn't guaranteed; not every page that Google processes will be indexed"1. A page can be successfully crawled — fetched, rendered, parsed — and still never appear in the index. Google does not enumerate every reason in the developer documentation, and this module does not speculate about the missing cases beyond what is stated.

Ranking is the one stage this module deliberately does not open further. Google states that "relevancy is determined by hundreds of factors" and, separately, that "Google doesn't accept payment to rank pages higher, and ranking is done programmatically"1 — a factor count and a policy statement, not a specification. This is the manifest boundary for this module: ranking-algorithm internals are not disclosed by Google beyond such statements, and the rest of this module does not attempt to reconstruct them. What Search's 1998 prototype disclosed about its own ranking signal — PageRank — is covered in §2.2 as a historical, publicly specified mechanism, distinct from whatever the hundreds of factors are today.

2. Crawling and indexing at prototype scale: the 1998 paper

Google's developer documentation describes crawling and indexing as they exist today, without internals. Sergey Brin and Larry Page's 1998 paper describes the same two stages as they existed in the original prototype, with the internals in full — a documented, if not current, block diagram of what "crawl" and "index" actually meant in code2. The prototype indexed 24 million pages2, roughly nine orders of magnitude smaller than today's disclosed index1, but the architecture it discloses is the direct ancestor of the pipeline in Figure 1, and it is the only point in this module's source set where crawling and indexing are described down to the level of named processes and data structures.

Brin and Page's 1998 Google architecture: URL server, crawlers, store server, repository, indexer, barrels, sorter, lexicon, and searcher URL server Crawlers Store server Repositorycompressed HTML,53.5 GB @ 24M pages Indexerreads, parses, emits hits Anchors filelink src/dest + text URL resolverrel → abs URLs → docIDs Links database3.9 GB, docID pairs PageRankiterative eigenvector calc Barrels (64)partially-sorted forward index Sorterre-sorts barrels by wordID Lexicon293 MB Searcherquery → ranked docIDs
Figure 2. The 1998 Google prototype's own architecture diagram, redrawn: URL server feeds distributed crawlers, which write through a store server into a compressed repository; the indexer reads the repository and both emits partially-sorted "barrels" (the forward index) and extracts an anchors file that the URL resolver and links database turn into PageRank's input graph; the sorter re-sorts the barrels into an inverted index the searcher answers queries from2.

2.1 What each box actually does

"In Google, the Web crawling (downloading of Web pages) is done by several distributed crawlers... There is a URLserver that sends lists of URLs to be fetched to the crawlers. The Web pages that are fetched are then sent to the storeserver. The storeserver then compresses and stores the Web pages into a repository"2. Every fetched page gets an integer identifier the moment it is first referenced: "every Web page has an associated ID number called a docID which is assigned whenever a new URL is parsed out of a Web page"2 — assignment happens at link-discovery time, not at crawl time, which is why the URL resolver later has to reconcile docIDs assigned before a page was ever fetched.

The indexer does two jobs from one pass over the repository: "the indexing function is performed by the indexer and the sorter. The indexer... reads the repository, uncompresses the documents, and parses them. Each document is converted into a set of word occurrences called hits... The indexer distributes these hits into a set of 'barrels', creating a partially sorted forward index"2, and separately, "it parses out all the links in every Web page and stores important information about them in an anchors file. This file contains enough information to determine where each link points from and to, and the text of the link"2. The forward index (barrels, keyed roughly by document) and the link graph (anchors file) are produced by the same pass but consumed by two different downstream systems: barrels feed the sorter toward a queryable inverted index, and the anchors file feeds the URL resolver and links database toward PageRank.

The last step converts the forward index into something a query can actually use: "the sorter takes the barrels... and resorts them by wordID to generate the inverted index... The searcher is run by a Web server and uses the lexicon built by DumpLexicon together with the inverted index and the PageRanks to answer queries"2. A forward index (document → words) and an inverted index (word → documents) are not the same structure, and the gap between them is exactly the sorter's job — this is the same forward/inverted distinction that shows up in any full-text search engine, and the 1998 paper is unusually explicit about which stage produces which one.

2.2 Storage stats, and PageRank as the one disclosed ranking signal

The paper reports its own resource footprint at 24 million pages in a single table, reproduced in Table 1.

Table 1. Storage statistics for the 1998 Google prototype at 24 million fetched pages2.
Data structureSize
Total size of fetched pages147.8 GB
Compressed repository53.5 GB
Short inverted index4.1 GB
Full inverted index37.2 GB
Lexicon293 MB
Links database3.9 GB
Total without repository55.2 GB
Total with repository108.7 GB

Two things are worth noticing in that table. First, the compressed repository (53.5 GB) is smaller than the raw fetched pages (147.8 GB) but is still the single largest structure — "the raw HTML repository uses roughly half of the necessary storage"2. Second, Google kept two separate inverted-index barrels rather than one: "we chose a compromise between these options, keeping two sets of inverted barrels — one set for hit lists which include title or anchor hits and another set for all hit lists. This way, we check the first set of barrels first and if there are not enough matches within those barrels we check the larger ones"2 — a cheap, high-precision index consulted first, falling back to an expensive, complete one only when the cheap one doesn't return enough matches. That two-tier read pattern is a caching decision made inside the index format itself, not at a separate cache layer.

PageRank is the one ranking mechanism this era of Google disclosed in full, and it is worth stating precisely because it is not what "hundreds of undisclosed factors" in §1 refers to today. The paper gives the recurrence directly: assume page A has pages T1...Tn pointing to it, a damping factor d (the paper sets d = 0.85), and C(A) as the number of outbound links on page A; then

$$ PR(A) = (1-d) + d\left(\frac{PR(T_1)}{C(T_1)} + \cdots + \frac{PR(T_n)}{C(T_n)}\right) $$

which "can be calculated using a simple iterative algorithm, and corresponds to the principal eigenvector of the normalized link matrix of the Web... a PageRank for 26 million Web pages can be computed in a few hours on a medium size workstation"2. The intuitive reading the paper gives is a random-surfer model: "PageRank can be thought of as a model of user behavior. We assume there is a 'random surfer' who is given a Web page at random and keeps clicking on links, never hitting back... The probability that the random surfer visits a page is its PageRank"2, with the damping factor d as the probability the surfer gets bored and jumps to a random page instead of following a link. PageRank was one input among several even in 1998 — the paper also used anchor text and word-proximity information alongside it2 — and it is not a claim about what any of the "hundreds of factors" Google cites today are. It is included here because it is the only ranking mechanism in this module's source set that is a fully specified formula rather than a policy statement.

2.3 Worked derivation: how fast the 1998 crawler actually ran

The paper states its own crawl-completion numbers in two different units, which makes them a useful cross-check rather than a single opaque figure: "in total it took roughly 9 days to download the 26 million pages (including errors). However, once the system was running smoothly, it ran much faster, downloading the last 11 million pages in just 63 hours, averaging just over 4 million pages per day or 48.5 pages per second"2. Checking that arithmetic directly:

$$ \frac{11 \times 10^{6}\ \text{pages}}{63\ \text{hours} \times 3600\ \text{s/hour}} = \frac{11{,}000{,}000}{226{,}800\ \text{s}} \approx 48.5\ \text{pages/s} $$

which matches the paper's own stated figure exactly, and scaling that rate up to a full day, 48.5 pages/s × 86,400 s/day ≈ 4.19 million pages/day, matches "just over 4 million pages per day" as well. This single-machine-era rate was achieved with a small, explicitly stated degree of parallelism: "each crawler keeps roughly 300 connections open at once... At peak speeds, the system can crawl over 100 web pages per second using four crawlers"2 — 300 concurrent connections per crawler because "a major performance stress is DNS lookup," and four crawler processes because that was sufficient concurrency to exceed 100 pages/s in aggregate2. The paper's own closing estimate on where this scales is a useful sanity check against the growth numbers in §4: "we expect to be able to build an index of a substantial portion of the Web — 24 million pages, in less than one week. We expect to be able to build an index of 100 million pages in less than a month"2.

3. Serving at cluster scale: the 2003 architecture

The 1998 prototype ran on a handful of donated workstations2. Five years later, Barroso, Dean, and Hölzle published the architecture that replaced it: "Google's architecture features clusters of more than 15,000 commodity-class PCs with fault-tolerant software"23. The stage this paper documents is exactly the "serving" box in Figure 1, and it opens it with a control-flow diagram of one query's path through a cluster.

Google's 2003 query-serving path: a Google Web Server coordinating spell checker, ad server, index servers, and document servers, each sharded and replicated query (after DNS-based geographic load balancing to a cluster) Google Web Servercoordinates the query Spell checker Ad server docids scored title + snippet Index servers — sharded by docID, replicated shard 0 shard 1 shard 2 shard N replica replica replica replica Document servers — sharded, replicated shard 0 shard 1 shard M Phase 1 (index servers): intersect hit lists, score, rank → ordered docids. Phase 2 (doc servers): docid → title, URL, snippet.
Figure 3. The 2003 Google Web Server coordinates two independent, sharded, replicated server pools — index servers producing ranked document IDs, and document servers turning those IDs into titles and snippets — plus a spell checker and ad server on the same request3.

3.1 Two phases, both embarrassingly shardable

The paper decomposes query execution into exactly two phases, matching the two server pools in Figure 3: "in the first phase, the index servers consult an inverted index that maps each query word to a matching list of documents (the hit list). The index servers then determine a set of relevant documents by intersecting the hit lists of the individual query words, and they compute a relevance score for each document"3. The second phase is a separate lookup against separate machines: "the final result of this first phase of query execution is an ordered list of document identifiers (docids)... [the second phase] involves taking this list of docids and computing the actual title and uniform resource locator of these documents, along with a query-specific document summary. Document servers (docservers) handle this job"3.

Both pools use the identical sharding-and-replication pattern independently: "the search is highly parallelizable by dividing the index into pieces (index shards)... A pool of machines serves requests for each shard... Each request chooses a machine within a pool using an intermediate load balancer"3, and document serving repeats the pattern by "randomly distributing documents into smaller shards, having multiple server replicas responsible for handling each shard, and routing requests through a load balancer"3. Replication here is deliberately dual-purpose — the same replicas that provide throughput also provide fault tolerance for free: "because we already replicate services across multiple machines to obtain sufficient capacity, this type of fault tolerance almost comes for free"3. When one replica of a shard fails, "the load balancer will avoid using it for queries... During the downtime, the system capacity is reduced in proportion to the total fraction of capacity that this machine represented. However, service remains uninterrupted, and all parts of the index remain available"3 — a graceful capacity degradation, not an outage, because the index shard the failed machine held is still served by its other replicas.

Read-mostly access is the property that makes this whole design tractable without invoking general-purpose database consistency machinery: "most accesses to the index and other data structures involved in answering a query are read-only: updates are relatively infrequent, and we can often perform them safely by diverting queries away from a service replica during an update. This principle sidesteps many of the consistency issues that typically arise in using a general-purpose database"3. The consistency model this section describes for search's own read path is not the linearizable, transactional model Module 5 covers for Spanner — it is a much weaker, deliberately chosen one that is sufficient only because writes are rare and can be scheduled around reads.

3.2 Why 15,000 cheap PCs instead of fewer expensive servers

The paper's cost argument is stated as an explicit comparison, not a general preference, and it is worth reproducing in a table because the two configurations it compares cost almost the same amount of money for very different resources.

Table 2. Two roughly comparable-generation server configurations Google's 2003 paper prices against each other3.
ConfigurationPrice (2002)CPUsRAMDisk
Rack of 88 commodity 2-way PCs$278,000176176 GB7 TB
One 8-way high-end server$758,000864 GB8 TB

The paper's own reading of that table: "the multiprocessor server is about three times more expensive but has 22 times fewer CPUs, three times less RAM, and slightly more disk space. Much of the cost difference derives from the much higher interconnect bandwidth and reliability of a high-end server, but again, Google's highly redundant architecture does not rely on either of these attributes"3. Search's own workload is what makes that trade acceptable: "because individual shards don't need to communicate with each other, the resulting speedup is nearly linear. In other words, the CPU speed of the individual index servers does not directly influence the search's overall performance, because we can increase the number of shards to accommodate slower CPUs, and vice versa"3. A workload that needs high single-node interconnect bandwidth and low cross-node communication latency (a distributed join, a tightly-coupled simulation) would not make this trade — the entire argument depends on shards being independent, which is a property of the search workload, not a property of clusters in general. The paper is explicit about the resulting design principle: "price/performance beats peak performance. We purchase the CPU generation that currently gives the best performance per unit price, not the CPUs that give the best absolute performance"3.

4. Ten years of scaling, and the index-partitioning choice

Jeff Dean's WSDM 2009 keynote, "Challenges in Building Large-Scale Information Retrieval Systems," gives a single slide's worth of numbers that quantify a decade of growth on top of the 2003 architecture — a rare case of a Google engineer stating before/after magnitudes directly rather than only a snapshot4.

Table 3. Google Search parameters, 1999 vs. 2009, as stated in Jeff Dean's WSDM 2009 keynote4.
Parameter19992009Change
Documents indexed~70 millionmany billion~100×
Queries processed / day——~1,000×
Per-document info kept in index——~3×
Index update latencymonthsminutes~10,000×
Average query latency<1 s<0.2 s~5×
Combined: more machines × faster machines~1,000×

The keynote's own framing of that table is a warning against static designs: "parameters change over time, often by many orders of magnitude. Right design at X may be very wrong at 10X or 100X... design for ~10X growth, but plan to rewrite before ~100X"4, and it reports that Google's search systems underwent "7 significant revisions in last 10 years... often rolled out without users realizing we've made major changes"4. The 10,000× improvement in update latency — months to minutes — is the single number in this table that §5 exists to explain: no amount of buying faster machines under the 2003 architecture's batch update process gets you from months to minutes; that required a different algorithm, not a bigger cluster.

4.1 By-document vs. by-term index sharding

The 2003 paper states that Google shards its inverted index "by dividing the index into pieces (index shards), each having a randomly chosen subset of documents from the full index"3 — sharding by document — without spelling out the alternative it rejected. The 2009 keynote states both options and the trade-off explicitly. Sharding by document means "each shard has index for subset of docs," with the query fanning out to every shard and each shard doing its own disk seeks; sharding by term means "shard has subset of words for all docs," with a query for K words touching at most K shards but requiring the results for each word, potentially scattered across shards, to be gathered into one place before they can be intersected4.

Table 4. Index partitioning by document vs. by term, and why Google's serving environment favors the former4.
PropertyBy documentBy term
Disk seeks for a K-word query on N shardsO(K · N)O(K)
Shards touched per queryall Nat most K
Network bandwidth neededlowhigh — per-doc data for each matching word must be collected in one place
Per-document infoeasy to keep additional metadataharder
Query independence across shardseach shard processes independentlyneeds cross-shard gather

The keynote's own conclusion, stated as a single line: "in our computing environment, by doc makes more sense"4. The reasoning is a direct match to the cost argument in §3.2 — Google's clusters are built from many cheap, high-count, comparatively bandwidth-constrained commodity machines rather than few machines on a fast interconnect3, and by-term sharding is exactly the strategy that shifts cost onto network bandwidth to save disk seeks. By-doc sharding costs a bounded number of disk seeks per shard per query, which the 2003 architecture already amortizes across thousands of cheap machines3; by-term sharding would have shifted that cost onto the network, which is the resource Google's own commodity-cluster design intentionally under-provisions relative to CPU and disk count.

4.2 How index updates worked before incremental processing

The same keynote describes, for the 1998–1999 era specifically, the batch mechanism the 2003 architecture inherited and that the 10,000× latency improvement in Table 3 eventually replaced: "1998–1999: index updates (~once per month): wait until traffic is low, take some replicas offline, copy new index to these replicas, start new frontends pointing at updated index and serve some traffic from there"4. The mechanism used the physical geometry of a spinning disk as a performance trick during the swap: "index server disk: outer part of disk gives higher disk bandwidth... copy new index to inner half of disk (while still serving old index)... restart to use new index... wipe old index... re-copy new index to faster [outer] half of disk"4 — the new index is staged on the slower inner tracks first so the old index keeps serving from the fast outer tracks throughout the copy, then swapped to the fast tracks only once it is verified and the old copy is gone. This is a real, once-a-month, multi-step operational procedure, not a background process — and it is the direct target of the "months to minutes" line in Table 3.

5. From batch MapReduce to incremental processing: Percolator and Caffeine

Daniel Peng and Frank Dabek's 2010 OSDI paper describes exactly the system that produced the 10,000× index-update-latency improvement in Table 3, and it states the batch predecessor's cost in the same breath as introducing its replacement: "in our previous system, each day we crawled several billion documents and fed them along with a repository of existing documents through a series of 100 MapReduces... though not all 100 MapReduces were on the critical path for every document, the organization of the system as a series of MapReduces meant that each document spent 2-3 days being indexed before it could be returned as a search result"5. A hundred sequential-ish batch jobs, each waiting on the slowest straggler in the previous stage, is precisely the kind of design the 2009 keynote warned would become "very wrong" once update latency needed to move from months to minutes4 — and a monthly full-index rebuild (§4.2) is not even a candidate for a 2–3 day figure; the 100-MapReduce pipeline described here is an intermediate architecture between the 1999 monthly rebuild and the system this section describes replacing it.

The replacement, internally named Caffeine, is built directly on top of the storage layers §6 covers next: "Percolator is built on top of the Bigtable distributed storage system... A running Bigtable consists of a collection of tablet servers... A tablet is stored as a collection of read-only files in the Google SSTable format. SSTables are stored in GFS; Bigtable relies on GFS to preserve data in the event of disk loss"5. Percolator adds exactly two things Bigtable does not natively provide: "the challenge, then, in implementing Percolator is providing the features that Bigtable does not: multirow transactions and the observer framework"5 — cross-row ACID transactions with snapshot isolation, and a trigger mechanism ("observers") that lets a write to one column kick off the next stage of processing automatically.

5.1 Transactions on Bigtable, and notifications instead of MapReduce stages

Percolator's transactions run at snapshot isolation, coordinated by a single small service: "the timestamp oracle is a server that hands out timestamps in strictly increasing order... Batching increases the scalability of the oracle... Our oracle serves around 2 million timestamps per second from a single machine"5. Every transaction reads at a start timestamp and commits at a later commit timestamp, and the paper is explicit that this buys efficient reads at the cost of write-skew exposure it does not try to prevent: "snapshot isolation does not provide serializability... The main advantage of snapshot isolation over a serializable protocol is more efficient reads. Because any timestamp represents a consistent snapshot, reading a cell requires only performing a Bigtable lookup at the given timestamp; acquiring locks is not necessary"5.

The mechanism that replaces "the next MapReduce stage" is a table-level trigger: "in Percolator, the user writes code ('observers') to be triggered by changes to the table, and we link all the observers into a binary running alongside every tablet server. Each observer registers a function and a set of columns with Percolator, and Percolator invokes the function after data is written to one of those columns in any row"5. Chaining stages together is then just one observer's transaction writing to a column another observer watches: "Percolator applications are structured as a series of observers; each observer completes a task and creates more work for 'downstream' observers by writing to the table. An external process triggers the first observer in the chain by writing initial data into the table. In our indexing system, a MapReduce loads crawled documents into Percolator by running loader transactions, which trigger the document processor transaction to index the document"5. The paper reports this collapses the pipeline dramatically in observer count alone: "the Google indexing system has roughly 10 observers"5 — 10 chained transactional steps in place of 100 MapReduce jobs.

5.2 What incremental processing actually bought, and what it cost

The paper's own headline result is stated in two different units that agree with each other: "the median document moves through Caffeine over 100x faster than the previous system... the average age of a document appearing in a search result dropped by nearly 50 percent (the age of a search result includes delays other than indexing such as the time between a document being changed and being crawled)"5. The two numbers measure different things — 100× is the median per-document indexing latency improvement; the roughly 50% figure is the average freshness improvement across all documents in a live search result, which also includes crawl-scheduling delay that Percolator does not touch — and the paper is careful to distinguish them rather than conflate a median-latency win with an average-freshness win.

This did not come free. The paper reports the resource cost directly rather than only the latency win: "compared to the system it replaced, Caffeine uses roughly twice as many resources to process the crawl rate. However, the radically-lower latency of the new system also enables us to remove the rigid distinctions between large, slow-to-update indexes and smaller, more rapidly updated indexes. Because Percolator frees us from needing to process the repository each time we index documents, we can also make it larger: Caffeine's document collection is currently 3x larger than the previous system's"5. And the trade is not universal — the paper is explicit that Percolator loses to a MapReduce-based pipeline at high enough crawl rates, because random Bigtable lookups per document are more expensive per byte than streaming the whole repository through disk: "at the cross-over point the total cost of the lookups required to cluster the new documents under Percolator equals the cost to stream the documents and the repository through MapReduce. At crawl rates higher than that, one is better off using MapReduce"5, measured in the paper's own synthetic benchmark at roughly a 40% crawl rate per hour5 — far above the single-digit hourly crawl rates the paper says real systems actually operate at.

Table 5. Batch (100-MapReduce) indexing vs. incremental Percolator/Caffeine indexing, by the numbers Google published5.
PropertyBatch (pre-2010)Incremental (Caffeine)
Per-document indexing latency2–3 days≈100× faster (median)
Average document age in resultsbaseline≈50% lower
Pipeline stages100 MapReduces≈10 observers
Resources to process a fixed crawl rate1×≈2×
Document collection size1×3× larger
Wins below crawl rate>~40% of repository/hour<~40% of repository/hour

6. The storage lineage underneath both stages: GFS, Bigtable, Megastore, Spanner

Section 5 already named the two layers Percolator sits on — Bigtable and GFS. This section is about how those two layers, plus the two that came after them, form a single lineage that both Search and Gmail sit on, each layer built explicitly to fix a limitation of the one before it. Module 7 covers GFS's own mechanics (single-master metadata, 64MB chunks, atomic record append) and Module 3/4/6 cover Bigtable's and Spanner's replication, transaction, and consensus mechanics in depth; this section does not re-derive any of that. It only places the four systems on one timeline and states, from each paper directly, who used each one and why the next layer had to exist.

Storage lineage timeline: GFS 2003, Bigtable 2006, Megastore, Spanner 2012, with each layer's documented consumers 2003 2006 ~2008 2012 GFSfile layerSOSP '03 Bigtablestructured store on GFSOSDI '06 Megastoreon Bigtable, 300+ appsdescribed in Spanner §2.3 SpannerPaxos + TrueTimeOSDI '12 Consumers:every layer above it Consumers:web indexing, Percolator,Google Finance, Earth Consumers (300+ apps):Gmail, Picasa, Calendar,Android Market, AppEngine— despite lower performance Each layer's own paper states why the next one had to exist: no cross-row transactions (Bigtable) → simpler but slower model (Megastore) → externally-consistent transactions at global scale (Spanner)
Figure 4. The storage lineage from GFS through Spanner, with each layer's documented consumers from its own or a successor's paper678. Megastore's publication and internal rollout predate Spanner's 2012 paper; it is placed on the timeline by the period its 300+ applications were live, as described retrospectively in Spanner's own related-work section.

6.1 GFS as the file layer, Bigtable as the structured layer on top of it

Bigtable's own abstract states its position in the stack and one of its uses directly: "many projects at Google store data in Bigtable, including web indexing, Google Earth, and Google Finance"7 — web indexing named explicitly, in the paper's own first paragraph, as one of Bigtable's demanding workloads. The paper's worked example of its data model is, not coincidentally, a table of crawled web pages: "let us call this particular table the Webtable. In Webtable, we would use URLs as row keys, various aspects of web pages as column names, and store the contents of the web pages in the contents: column"7, with an anchor: column family whose "qualifier is the name of the referring site; the cell contents is the link text"7 — the same anchor-text-as-a-ranking-input idea Brin and Page's 1998 anchors file captured (§2.1), now expressed as Bigtable columns instead of a flat file.

Bigtable's own persistence guarantee depends entirely on the file layer underneath it: "a tablet is stored as a collection of read-only files in the Google SSTable format. SSTables are stored in GFS; Bigtable relies on GFS to preserve data in the event of disk loss"7 — Bigtable does not replicate bytes itself; it delegates that job to GFS's own chunk replication (Module 3, Module 7) and adds structured indexing, column families, and row-range sharding (tablets) on top. This is the general pattern the rest of the lineage repeats: each new layer adds exactly one capability the layer below lacks, and delegates everything else downward.

6.2 What each layer added, and what it still didn't provide

Table 6. The four storage layers in Search and Gmail's lineage, and the one capability each added over the layer beneath it678.
LayerUnit of dataWhat it addedWhat it still lacked
GFS64 MB chunks, replicated 3×6fault-tolerant bytes at cluster scale via a single in-memory-metadata master6no structure, no indexing, no transactions
Bigtablerows in a tablet (~100–200 MB), on GFS SSTables7sparse sorted multi-dimensional map, column families, single-row atomic read-modify-write7"does not currently support general transactions across row keys"7
Megastoreentity groups, on Bigtablea simpler data model for interactive applications, used by 300+ Google apps8"despite its relatively low performance"8
Spannerdirectories over Paxos-replicated tablets8externally-consistent cross-row, cross-datacenter transactions via TrueTime8higher write latency than Bigtable's single-row path (2PC + clock-uncertainty wait)

Spanner's own paper states the motivating gap directly: "at least 300 applications within Google use Megastore (despite its relatively low performance) because its data model is simpler to manage... than Bigtable's, and because of its support for synchronous replication across datacenters"8. Megastore already chose synchronous cross-datacenter replication over Bigtable's eventually-consistent replication — the performance cost the quote refers to is largely that synchronization cost, paid in exchange for a simpler-to-reason-about consistency model than raw Bigtable's per-row-only guarantees. Spanner's contribution was making that trade-off unnecessary: general-purpose, externally-consistent transactions across rows, tables, and datacenters, "shard[ing] data across many sets of Paxos state machines in datacenters spread all over the world"8, with the TrueTime API bounding clock uncertainty to "generally less than 10ms" using GPS and atomic clock references8 — the mechanism Module 5 covers as the answer to the consistency/latency trade-off, and Module 6 covers as an application of Paxos consensus.

7. Megastore's 300+ applications, and what Google has not published about Gmail

Spanner's paper names Megastore's consumers directly, and this is the single most concrete, citable fact this module has about Gmail's storage: "examples of well-known Google applications that use Megastore are Gmail, Picasa, Calendar, Android Market, and AppEngine"8, out of "at least 300 applications within Google" that used it despite its cost8.

Megastore's fan-out: 300+ Google applications on one storage layer, with Gmail, Picasa, Calendar, Android Market, and AppEngine named Megastoreon Bigtable, sync cross-DC Gmail Picasa Calendar Android Market AppEngine + ≥295 more named-but-unlisted applications8
Figure 5. At least 300 Google applications ran on Megastore; Spanner's own paper names five of them by name, Gmail included8. This is the extent of what this module's sources say about Gmail's storage layer.

7.1 Why this module stops here for Gmail

The single quoted sentence above is the entirety of what a Google-authored primary source in this module's research says about Gmail's storage architecture: that it was, at some point, one of at least 300 applications using Megastore. No paper in this module's source set describes Gmail's schema, its message-storage format, its search-indexing mechanism for a user's own mailbox, its spam-filtering pipeline, its attachment-storage path, or whether and how it migrated off Megastore onto Spanner or another system since 2012. The manifest for this module is explicit about why: Gmail has no dedicated Google-published architecture account, unlike Search, GFS, Bigtable, Spanner, or Borg, each of which has at least one full engineering paper devoted to it.

The Borg paper's mention (§8) is one datapoint later than the Spanner paper's: Borg's 2015 paper lists Gmail as a current example of a latency-sensitive production service, three years after Spanner's 2012 paper described Megastore's 300+-application fan-out9. That is consistent with Gmail having existed on Borg-scheduled infrastructure across both eras, but it is not a claim that Gmail's storage layer specifically was still Megastore in 2015 rather than Spanner or Bigtable directly — the Borg paper does not name Gmail's storage backend at all, only its compute scheduling.

8. Borg: the compute substrate scheduling both workloads

Every server in Figures 1–5 — crawler, indexer, index server, docserver, Percolator worker, Bigtable tablet server, Spanner spanserver — runs as a job on Borg, Google's own cluster manager and the direct design ancestor of Kubernetes9. Borg's own paper names both of this module's case-study workloads in one sentence: "long-running services should never go down, and their latency should be low... Such services are used for end-user-facing products such as Gmail, Google Docs, and web search, and for internal infrastructure services (e.g., BigTable)"9 — Gmail and web search named side by side as examples of the same job category, "prod" (production, latency-sensitive), distinguished from the batch category covering the crawling and indexing jobs in §2 and §5.

A Borg cell scheduling a Search-serving prod job and a Gmail-class prod job side by side, both drawing from the same quota-checked resource pool Borg cell — median ~10,000 machines9 Job: web-search-index-serve alloc class: prod tasks: index-server-shard-0..N BNS name written to Chubby quota checked at submission Job: gmail-frontend alloc class: prod tasks: mail-serve-0..M BNS name written to Chubby quota checked at submission Both are “prod”: ~70% of a representative cell's allocated CPU, ~60% of CPU used, ~85% of memory used9 Batch jobs: crawling, MapReduce/Percolator (§2, §5) share the same machines, lower priority Preempted on SIGTERM ~80% of the time before SIGKILL9
Figure 6. A Borg cell scheduling a Search-serving job and a Gmail-class job as two independent "prod" jobs sharing one cell's admission-control quota and physical machines with lower-priority batch work9. Job and task names are illustrative of Borg's naming scheme, not literal published identifiers — Borg's paper does not disclose Google's actual internal job names.

8.1 What "scheduled on the same cell" actually means

A cell is Borg's unit of a managed cluster: "Borg cells run hundreds of thousands of jobs, from many thousands of different applications, across a number of clusters each with up to tens of thousands of machines... our median cell size is about 10k machines"9. Search and Gmail, as prod jobs, are two of "hundreds of thousands" of jobs a single cell might be running concurrently, competing for the same machines' CPU and memory as batch work, but with a resource-allocation guarantee batch work does not get: "prod jobs are allocated about 70% of the total CPU resources and represent about 60% of the total CPU usage; they are allocated about 55% of the total memory and represent about 85% of the total memory usage"9 — prod jobs are allocated more CPU than they typically use (headroom for latency spikes), while batch jobs opportunistically consume the difference.

Admission itself is quota-gated before scheduling ever runs: "quota-checking is part of admission control, not scheduling: jobs with insufficient quota are immediately rejected upon submission"9 — a Search-serving job and a Gmail job each hold a separate quota grant, checked once at submission time, independent of whatever the scheduler later decides about machine placement. And every task, regardless of which product it belongs to, gets the same discovery mechanism: "Borg creates a stable 'Borg name service' (BNS) name for each task that includes the cell name, job name, and task number. Borg writes the task's hostname and port into a consistent, highly-available file in Chubby with this name"9 — the same Chubby lock service Bigtable uses for master election (Module 6) doubles as the address book every other service on the cell uses to find a Search index-server shard or a Gmail frontend task. This is the concrete, cited answer to "what does it mean for Search and Gmail to run on the same infrastructure": they are two named jobs, admitted against two quota grants, competing for CPU and memory headroom on the same 10,000-machine cell, discoverable through the same lock service — and nothing about that shared substrate implies anything about whether they share a storage layer, which §7 already stated is undocumented for Gmail beyond its historical Megastore membership.

Where experts disagree

Module 6 introduces this disagreement in the abstract: is Raft's understandability advantage over Paxos decisive in practice? This module is where it has to be tested against a concrete case, because two of the systems this module has just walked through — Bigtable's Chubby lock service and Spanner's spanservers — are Google's own production answer, and neither uses Raft.

Understandability should decide the winner

Ongaro and Ousterhout, Raft's designers10

Raft was built specifically to be easier to reason about and implement correctly than Paxos, and its own user study measured that difference directly: "a user study with 43 students at two universities shows that Raft is significantly easier to understand than Paxos: after learning both algorithms, 33 of these students were able to answer questions about Raft better than questions about Paxos"10. The argument is that an algorithm's safety proof is only as good as an implementer's ability to reproduce it correctly under deadline pressure, and Paxos's single-decree formulation famously leaves practitioners to invent their own multi-decree, membership-change, and leader-election extensions — exactly the parts Raft specifies as one coherent design instead of "a series of independent sub-protocols."

  • A measured, replicated (43-subject) result, not an assertion — rare for a claim about implementation difficulty
  • Directly targets the failure mode that causes real outages: a subtly wrong from-scratch Paxos implementation, not a correctly-implemented one
  • The study measures comprehension by students learning both algorithms for the first time in an afternoon, not the reliability of a production implementation built and hardened over a decade
  • Says nothing about whether an already-correct, already-battle-tested Paxos implementation should be thrown away

Operational maturity of an existing implementation dominates

Google's own production choices, as documented in the Bigtable and Spanner papers78

Bigtable's master election runs on Chubby, and "Chubby uses the Paxos [9, 23] algorithm to keep its replicas consistent in the face of failure"7. Spanner, published six years after Chubby was already in wide production use and two years after Raft's own extended paper, still chose Paxos for its spanservers: "it is a database that shards data across many sets of Paxos state machines"8, with "long-lived leaders with time-based leader leases, whose length defaults to 10 seconds"8. Bigtable's own measured Chubby-outage cost — averaging 0.0047% of server-hours across 14 clusters, worst single cluster 0.0326%3 — is a number that only exists because the implementation has already been run, measured, and incrementally fixed for years; a from-scratch rewrite in a more understandable algorithm forfeits that accumulated operational knowledge and restarts the reliability curve from zero.

  • A hardened implementation's failure modes are known, monitored, and already mitigated; a rewrite's are not, regardless of the new algorithm's textbook clarity
  • Google shipped Spanner in 2012 with full knowledge that Raft's extended paper (2014, but circulating from 2013) existed in the same research community and still chose Paxos
  • This is a survivorship argument, not a counter-claim about understandability — it says switching costs were high, not that Paxos is easier to get right the first time
  • Neither paper states that Google evaluated Raft and rejected it; the absence of a migration is consistent with "never considered" as much as with "considered and rejected"
Assessment

These two positions are not actually in conflict once "decisive" is read as a question about when in a system's life the understandability advantage is realized. For a team choosing a consensus algorithm today, before any implementation exists, Raft's decomposition and the 43-student result are a real, measured argument for lower defect risk during initial implementation — this is the moment the advantage is decisive, and it is why nearly every consensus library built after 2014 (etcd, CockroachDB's Raft-based ranges, Consul) chose Raft over rolling a new Paxos variant. For a team that already has a hardened, measured, decade-old Paxos implementation underneath a production system as consequential as Bigtable's master election or Spanner's replication — Google's actual position in 2012 — the calculus is different: the cost being compared is not "Raft vs. Paxos in the abstract" but "a rewrite of a working system vs. its current failure rate," and Bigtable's own 0.0047% number3 shows that failure rate was already very low. What would settle this for a specific team is neither paper's argument but a direct cost estimate: the defect rate of new Paxos implementations built without Raft's decomposition, compared against the migration cost and interim-outage risk of replacing an already-hardened Paxos deployment — a comparison neither the Raft paper nor Google's papers attempt, because each is answering a different question at a different point in a system's lifecycle.

References

  1. officialGoogle Search Central. In-Depth Guide to How Google Search Works. Live documentation, 2026. https://developers.google.com/search/docs/fundamentals/how-search-works. Accessed 2026-09-17. Used for: the three-stage crawl/index/serve description, index scale (hundreds of billions of pages, over 100,000,000 GB), headless-Chrome JS rendering, ranking-factor and no-pay-to-rank statements, indexing-not-guaranteed statement.
  2. paperBrin, S. & Page, L. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Computer Networks and ISDN Systems, vol. 30, 1998, pp. 107-117. http://infolab.stanford.edu/pub/papers/google.pdf. Accessed 2026-09-17. Used for: the 1998 prototype's system architecture (§4.1), storage statistics (Table 1), the PageRank formula and random-surfer model (§2.1), and the crawl-rate arithmetic (§4.3, §4.4).
  3. paperBarroso, L.A., Dean, J. & Hölzle, U. Web Search for a Planet: The Google Cluster Architecture. IEEE Micro, vol. 23, no. 2, March-April 2003, pp. 22-28. https://barroso.org/publications/ieeemicro_google.pdf. Accessed 2026-09-17. Used for: the 2003 query-serving architecture (GWS, index servers, docservers), index sharding and replication for throughput/fault tolerance, the commodity-PC vs. high-end-server cost/performance comparison, and Bigtable's measured Chubby-outage percentage cited in the disagreement section.
  4. talkDean, J. Challenges in Building Large-Scale Information Retrieval Systems. WSDM 2009 keynote. https://research.google.com/people/jeff/WSDM09-keynote.pdf. Accessed 2026-09-17. Used for: the 1999-vs-2009 growth table (Table 3), the by-document vs. by-term index-partitioning trade-off (Table 4), and the 1998-99 monthly batch index-update mechanism (§4.2).
  5. paperPeng, D. & Dabek, F. Large-scale Incremental Processing Using Distributed Transactions and Notifications. OSDI 2010. https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Peng.pdf. Accessed 2026-09-17. Used for: the batch (100-MapReduce) indexing system's 2-3 day latency, Percolator's architecture on Bigtable/GFS, the timestamp oracle, snapshot isolation, the observer/notification mechanism, and Caffeine's measured latency, freshness, resource, and index-size figures (Table 5).
  6. paperGhemawat, S., Gobioff, H. & Leung, S-T. The Google File System. SOSP 2003. https://research.google.com/archive/gfs-sosp2003.pdf. Accessed 2026-09-17. Used for: GFS's place at the base of the storage lineage (Table 6); detailed GFS mechanics are covered in Module 7 rather than repeated here.
  7. paperChang, F. et al. Bigtable: A Distributed Storage System for Structured Data. OSDI 2006. https://www.usenix.org/legacy/event/osdi06/tech/chang/chang.pdf. Accessed 2026-09-17. Used for: Bigtable's web-indexing use (abstract), the Webtable example, Bigtable's dependence on GFS/SSTables, the lack of cross-row transactions, and Chubby's use of Paxos, cited in the disagreement section.
  8. paperCorbett, J.C. et al. Spanner: Google's Globally-Distributed Database. OSDI 2012. https://research.google.com/archive/spanner-osdi2012.pdf. Accessed 2026-09-17. Used for: Megastore's 300+ application fan-out naming Gmail, Picasa, Calendar, Android Market, and AppEngine (§7); Spanner's Paxos spanservers, leader leases, and TrueTime; and the Paxos-in-production position in the disagreement section.
  9. paperVerma, A., Pedrosa, L., Korupolu, M., Oppenheimer, D., Tune, E. & Wilkes, J. Large-scale cluster management at Google with Borg. EuroSys 2015. https://research.google.com/pubs/archive/43438.pdf. Accessed 2026-09-17. Used for: Borg cell size, Gmail and web search named as prod workloads, prod CPU/memory allocation-vs-usage figures, quota-at-admission-control, and the BNS naming mechanism (§8).
  10. paperOngaro, D. & Ousterhout, J. In Search of an Understandable Consensus Algorithm (Extended Version). 2014. https://raft.github.io/raft.pdf. Accessed 2026-09-17. Used for: the 43-student understandability user study, cited only in the disagreement section.