Physalia: Millions of Tiny Databases

Avoiding Hard CAP Tradeoffs

A few years ago, when I was still working on EBS, we started building a system called Physalia. Physalia is a custom transactional key-value store, designed to play the role of configuration master in the EBS architecture. Last year, we wrote a paper about Physalia, and were thrilled that it was accepted to NSDI’20.

Millions of Tiny Databases describes our problem and solution in detail. Here’s the abstract:

Starting in 2013, we set out to build a new database to act as the configuration store for a high-performance cloud block storage system Amazon EBS. This database needs to be not only highly available, durable, and scalable but also strongly consistent. We quickly realized that the constraints on availability imposed by the CAP theorem, and the realities of operating distributed systems, meant that we didn’t want one database. We wanted millions. Physalia is a transactional key-value store, optimized for use in large-scale cloud control planes, which takes advantage of knowledge of transaction patterns and infrastructure design to offer both high availability and strong consistency to millions of clients. Physalia uses its knowledge of datacenter topology to place data where it is most likely to be available. Instead of being highly available for all keys to all clients, Physalia focuses on being extremely available for only the keys it knows each client needs, from the perspective of that client. This paper describes Physalia in context of \amazon \ebs, and some other uses within \awsFull. We believe that the same patterns, and approach to design, are widely applicable to distributed systems problems like control planes, configuration management, and service discovery.

I also wrote a post about Physalia for the Amazon Science blog.

One aspect of Physalia that I’m particular proud of is the work that we put in to correctness. We used TLA+ extensively throughout the design, and as documentation during implementation. As we’ve published about before, TLA+ is really well suited to these kinds of systems. We also automatically generated unit tests, an approach I haven’t seen used elsewhere:

In addition to unit testing, we adopted a number of other testing approaches. One of those approaches was a suite of automatically-generated tests which run the Paxos implementation through every combination of packet loss and re-ordering that a node can experience. This testing approach was inspired by the TLC model checker, and helped usbuild confidence that our implementation matched the formal specification.

Check out our paper if you’d like to learn more.

Other Posts

• 25 Mar 2024 » Finding Needles in a Haystack with Best-of-K
• 04 Mar 2024 » The Builder's Guide to Better Mousetraps
• 12 Feb 2024 » Better Benchmarks Through Graphs