Megastore: Providing Scalable, Highly Available Storage for Interactive Services

✨ Summary

Overview

Megastore presents a middle-ground storage architecture combining the scalability and locality of a NoSQL system with selected relational-database features. The datastore is divided into independently replicated entity groups, each functioning as a small database. Transactions within an entity group provide serializable ACID semantics, while operations spanning entity groups use asynchronous queues or, when necessary, higher-latency two-phase commit.

Architecture and data model

The system uses Bigtable as its per-datacenter storage layer and maintains a replicated write-ahead log for each entity group. Entity-group boundaries are chosen by applications, typically around naturally related data such as a user account, blog, calendar, or geographic region. Key ordering and hierarchical schemas colocate related records, reducing the need for joins and making query costs more predictable. The data model supports strongly typed entities, hierarchical relationships, repeated properties, local and global secondary indexes, denormalization through storing and inline indexes, full-text indexing, queues, backups, and encryption at rest.

Replication and consistency

Megastore synchronously replicates each entity group across geographically separated replicas using Paxos. A majority of replicas must acknowledge a log append before consensus is reached, allowing the system to tolerate replica failures without losing committed data. The design avoids a permanent master: leaders are selected for individual log positions, and a fast-write path can often complete in a single inter-datacenter round trip. Coordinators track which replicas are sufficiently up to date to serve local current reads; if that state is unavailable or uncertain, the system falls back to majority-based reads and replica catch-up.

The transaction lifecycle separates consensus from application of mutations. A write is first committed to the replicated log, after which its entity and index mutations are applied to full replicas. Coordinator invalidation prevents a write from being acknowledged before replicas can satisfy the paper’s read-after-write guarantees. MVCC allows readers and writers to proceed without blocking one another, with current, snapshot, and inconsistent read modes providing different latency and freshness trade-offs.

Performance and operational trade-offs

The design achieves scalability by distributing load across many independently replicated entity groups rather than synchronously replicating one monolithic database. The reported production measurements describe read latencies generally in the tens of milliseconds and typical write latencies of roughly 100–400 milliseconds, depending on replica placement, datacenter distance, and write size. The paper reports deployment across more than 100 Google production applications, handling more than three billion writes and 20 billion reads per day at the time of publication.

The main limitation is that each entity group is a serialization and throughput boundary. The paper reports that a few writes per second per entity group generally yield low conflict rates; higher rates require finer sharding, locality-aware replica placement, batching, server affinity, or advisory locks. Cross-group operations are deliberately weaker or more expensive than intra-group transactions, making data modeling and physical layout central to application performance.

Influence and subsequent industry use

Megastore’s entity-group model and its combination of strong consistency, transactions, locality, and wide-area replication became part of Google App Engine and Cloud Datastore. Current Google Cloud documentation continues to describe entity groups as units of organization, locality, strong consistency, and transactionality, while retaining the associated write-contention and transaction-scope trade-offs. (docs.cloud.google.com)

A 2024 Google Research paper states that Datastore was built over Google’s internal Megastore system and describes the subsequent migration of more than one million Datastore databases from Megastore-backed storage to Firestore backed by Spanner. This documents a concrete industry lineage in which Megastore’s design served as an earlier production foundation, while Spanner provided broader transaction capabilities and stronger consistency features. (research.google)

Related Google systems extended this design direction. F1 combined scalable distributed storage, synchronous cross-datacenter replication, and relational SQL features for Google’s advertising business, while Spanner generalized globally distributed synchronous replication and distributed transactions beyond Megastore’s entity-group scope. The relationship is architectural rather than a claim that every feature was directly inherited from this paper. (research.google)