Megastore: Providing Scalable, Highly Available Storage for Interactive Services

Google, “Megastore: Providing Scalable, Highly Available Storage for Interactive Services,” CIDR, 2011. [PDF]


Megastore is a highly available, scalable storage system built on top of Google’s BigTable system for scalable storage and Chubby for locks and configuration data. It supports full ACID semantics and specially suited for interactive services, even though BigTable itself does not provide ACID guarantees. Megastore supports fine-grained partitioning of data based on the concept of entity groups, provides strong ACID properties within each entity group but not necessarily across them, and performs synchronous replication of partitions across multiple data centers using Paxos underneath for seamless failover.

Megastore has been designed keeping its administrators, developers of services based on it, and end users of those services in mind. It tries to ensure low latency for end users, performance, scalability, and ease-of-use for developers, and ease-of-maintenance for the admins. However, as the authors point out, each application must carefully choose its partitioning into entity groups. Megastore involves some interesting tweaks for ensuring a fast Paxos implementation: one WAN RTT on writes and zero WAN RTT for reads on average (i.e., reads are local). It replicates transaction log entries across datacenters on each write.


While Megastore has been successful in achieving many of goals, it does not support any query language (i.e., applications must implement query plans) and allows limited update rate for individual entity groups. There assumption about high latency writes (due to synchronous replication) is probably acceptable for Google’s workload, but it is not clear how important it is to have failover support at the expense of performance.

One key difference between Megastore and other Google systems (e.g., GFS, BigTable, MapReduce etc.) is that it is closer to the applications it wants to support, more tied to their requirements, and consequently, the authors had to take decisions that have made it less general than other systems. While I believe that Megastore is useful for Google’s business, it is less likely to spawn as much following in the open-source world as GFS and MapReduce have done.

Leave a Reply

Your email address will not be published. Required fields are marked *