Amazon MemoryDB: A Fast and Durable Memory-First Cloud Database

-

Key-value stores have simple semantics which make it cumbersome to perform complex operations involving multiple keys. Redis addresses this by providing low latency access to complex data structures like lists, sets, and hashes. Unfortunately, Redis lacks strong consistency guarantees and durability in the face of node failures, which limits its applicability beyond caching use cases.

Amazon MemoryDB is a fully managed in-memory database service that leverages Redis's performance strengths while overcoming its durability limitations. It uses Redis as the in-memory data processing engine but offloads persistence to an AWS-internal transaction log service (internally known as the journal). This decoupled architecture provides in-memory performance with microsecond reads and single-digit millisecond writes, while ensuring across availability zone (AZ) durability, 99.99% availability, and strong consistency in the face of failures.

This Sigmod 2024 paper describes MemoryDB's architecture. Unfortunately, it doesn't provide any description of the transaction log/journal service. We will have to wait for another paper to be published on the journal service.


Redis/Valkey

Redis (or now Valkey) supports over 200 commands on 10 data structures like hash tables, sorted sets, and hyperloglogs. It allows combining commands into all-or-nothing transactions, and also supports executing Lua scripts atomically on the server.

For horizontal scaling, Redis splits its key space into 16,384 slots across shards, each with a primary node for writes and optional read-only replicas. Clients discover the slot-to-shard mapping and directly interact with the appropriate shard. Multi-key transactions work as long as all keys belong to the same slot.

Redis uses asynchronous logical replication. Writes are executed and performed on the primary and then are asynchronously replicated to secondaries. Replicas offer a consistent view of past data without any control over the lag from the primary. This approach ensures high availability but does not guarantee durability in the event of primary failures. Redis uses a quorum-based approach for election, however, due to asynchronous replication, a failover will cause a permanent loss of the writes that were not replicated to the new leader at the time of failure.


MemoryDB

MemoryDB decouples durability from the in-memory execution engine by offloading it to the transaction log/journal service. This transaction log provides strongly consistent commits across multiple AZs and is responsible for propagating writes to replicas. This allows offering the full Redis API without invasive modifications, because as far as the Redis replicas are concerned the Redis's original asynchronous replication strategy is being used. However, behind the curtains, the internal AWS transaction log service provides multi-AZ durability by acknowledging writes only after they are durably committed across multiple AZs, providing 11 9s of durability.


The paper does not explain this but I infer from the architecture and paper that, the transaction log is per shard, and is used for connecting the shard primary to the secondaries. Transaction log does not seem to be shared across different shards/primaries.


Availability, Recovery and Resilience

MemoryDB also addresses several challenges with Redis leader election and recovery processes. Unlike Redis, MemoryDB's leader election mechanism ensures only fully caught-up replicas can be promoted as the new primary, maintaining data consistency across failures. This is achieved by leveraging the transaction log's conditional append API. In the transaction log, each log entry is assigned a unique identifier, and it is required that each conditional append request must specify the identifier of the entry it intends to follow as a precondition. Acquiring leadership is done by appending a specific log entry to the transaction log. Mutual exclusion and serialization is satisfied thanks to this conditional append. 

I initially taught, why would they need to require replicas to be fully-caught-up before they can run for leader election? Since the transaction log would have all the acknowledged writes, the replica that has been elected leader can get caught up from the log afterwards. However, after reading their leader election procedure and seeing how simple that is, I appreciated how this requirement keeps the overall recovery simple (cornercase-free) as well: "Ensuring consistent failover becomes simpler leveraging the append API. Only replicas that have observed the latest write’s unique identifier will succeed at appending the leadership entry to the log." If they allowed any replica to be a leader, recovery may still have some edge cases. It might be possible that for that new leader replica, the transaction log service node in its AZ may be out, and this would delay the catching up or would require interference.

A leader once elected is also granted a predetermined lease period. The leader can append entries to the log to extend the lease before it expires. To enforce leader singularity, secondaries are preventing from campaigning during the backoff period after observing a renewal. The lease granularity is at the shard level.

The paper includes this cryptic sentence without elaboration: "This [lease or leadership singularity] optimization improves read throughput and latency, but also improves write performance by reducing the total number of operations that must be handled through consensus [30]." The reasoning for the read throughput is clear because the leaseholding primary can serve linearizable/strong-consistency reads locally. Thanks to the lease, it is guaranteed that no other leader could have been elected and updated the data. But what should we make of "but also improves write performance". Is this due to avoiding a conditional put operation to the transaction log when you are the leader? This is unclear. While the writing in the paper is generally OK, it has this problem of assuming the reader has more context/information about the system then they do. And the lack of any description about the transaction log service makes the problem worse. (Update: see the postscript at the end of the post.)

For efficient recovery, MemoryDB relies on its durable snapshots stored in S3 rather than requiring a primary node. Recovering replicas fetch the latest snapshot and replay the log up to a recorded position to rebuild a recent data view. By making recovery snapshot-dominant and bounding the log replay, MemoryDB optimizes for faster restarts. Its monitoring service continuously tracks cluster data and snapshot freshness to trigger new snapshots when staleness exceeds thresholds.


Evaluation

The performance of MemoryDB and open-source Redis (version 7.0.7) was evaluated across several Amazon EC2 Graviton3 instance types (r7g.large to r7g.16xlarge) using read-only, write-only, and mixed read-write workloads. The workloads were generated using redis-benchmark with 10 EC2 instances sending traffic to the databases, pre-filled with 1 million keys.

For read-only workloads, MemoryDB outperformed Redis across all instance types, leveraging its Enhanced IO multiplexing feature to aggregate multiple client connections into a single connection, which improves processing efficiency.

However, for write-only workloads, as expected Redis outperformed MemoryDB, achieving a maximum throughput close to 300K ops/sec compared to MemoryDB's 185K ops/sec. Since MemoryDB commits every write to the transaction log to ensure multi-AZ durability for every write operation, this results in higher request latency and lower throughput for sequential blocking write requests.  Pushing a single shard in ideal conditions (with higher client counts, pipelining, or larger payloads), they say they can achieve up to 100MB/s write throughput.

In terms of latency, Redis delivered sub-millisecond median latencies and up to 3ms at p99 for write-only workloads, while MemoryDB had 3ms median and up to 6ms p99 latencies due to the transaction log commitment. For mixed read-write workloads, both offered sub-millisecond median latencies, with Redis up to 2ms and MemoryDB up to 4ms at p99.


Validating and Maintaining Consistency at Scale

MemoryDB employs several mechanisms to ensure safety:

  • During upgrades, replicas are upgraded first, and the leader node is upgraded last. This preserves read throughput capacity from replicas while the leader is still running the old version.
  • An upgrade protection mechanism safeguards the replication stream by indicating the engine version that produced it. If a replica with an older engine version observes a replication stream from a newer version, it stops consuming the transaction log to prevent data corruption.
  • MemoryDB maintains a running checksum of the entire transaction log and periodically injects the current checksum into the log itself. Snapshots store the checksum value and a positional identifier for the last log entry they capture, as well as a checksum covering the snapshot data itself. Snapshot correctness is verified by rehearsing the restoration process on an off-box cluster before applying the snapshot to the primary cluster.

As far as protocol and software safety is concerned, the internal transaction log replication protocol is modeled and verified using TLA+ to reason about the system's behavior and catch bugs early in the development process.  MemoryDB uses P as well for new feature development, which proved helpful in catching bugs early. Finally, MemoryDB uses Porcupine, a linearizability checker, to test the consistency of concurrent client command histories, ensuring linearizability guarantees are met.


PS: I missed this earlier, but Brooker's post on MemoryDB (which emphasizes the compositionality aspect of the architecture) has a Bonus material on fencing that goes into detail about how interacting with the journal works. https://brooker.co.za/blog/2024/04/25/memorydb.html

Comments

Post a Comment

Popular posts from this blog

Hints for Distributed Systems Design

-
This is with apologies to Butler Lampson, who published the " Hints for computer system design " paper 40 years ago in SOSP'83. I don't claim to match that work of course. I just thought I could draft this post to organize my thinking about designing distributed systems and get feedback from others. I start with the same  disclaimer Lampson gave. These hints are not novel, not foolproof recipes, not laws of design, not precisely formulated, and not always appropriate. They are just hints.  They are context dependent, and some of them may be controversial. That being said, I have seen these hints successfully applied in distributed systems design throughout my 25 years in the field, starting from the theory of distributed systems (98-01), immersing into the practice of wireless sensor networks (01-11), and working on cloud computing systems both in the academia and industry ever since. These heuristic principles have been applied knowingly or unknowingly and has proven
Read more >>

Learning about distributed systems: where to start?

-
This is definitely not a "learn distributed systems in 21 days" post. I recommend a principled, from the foundations-up, studying of distributed systems, which will take a good three months in the first pass, and many more months to build competence after that. If you are practical and coding oriented you may not like my advice much. You may object saying, "Shouldn't I learn distributed systems with coding and hands on? Why can I not get started by deploying a Hadoop cluster, or studying the Raft code." I think that is the wrong way to go about learning distributed systems, because seeing similar code and programming language constructs will make you think this is familiar territory, and will give you a false sense of security. But, nothing can be further from the truth. Distributed systems need radically different software than centralized systems do.  --A. Tannenbaum This quotation is literally the first sentence in my distributed systems syllabus. Inst
Read more >>

Making database systems usable

-
Image
C. J. Date's Sigmod 1983 keynote, "Database Usability", was prescient. Usability is the most important thing to the customers. They care less about impressive benchmarks or clever algorithms, and more about whether they can operate and use a database efficiently to query, update, analyze, and persist their data with minimal headache. (BTW, does anyone have a link to the contents of this Sigmod'83 talk? There is no transcript around, except for this short abstract .) The paper we cover today is from Sigmod 2007. It takes on the database usability problem raised in that 1983 keynote head-on, and calls out that the king is still naked.  Let's give some context for the year 2007. Yes, XML format was still popular then. The use-case in the paper is XQuery. The paper does not contain any  reference to json. MongoDB would be released in 2009 with the document model; and that seems to be great timing for some of the usability pains mentioned in the paper! Web 2.0 was in
Read more >>

Looming Liability Machines (LLMs)

-
As part of our zoom reading group ( wow, 4.5 years old now ), we discussed a paper that uses LLMs for automatic root cause analysis (RCA) for cloud incidents. This was a pretty straightforward application of LLMs. The proposed system employs an LLM to match incoming incidents to incident handlers based on their alert types, predicts the incident's root cause category, and provides an explanatory narrative. The only customization is through prompt-engineering. Since this is a custom domain, I think a more principled and custom-designed  machine learning system would be more appropriate rather than adopting LLMs. Anyways, the use of LLMs for RCAs spooked me vicerally. I couldn't find the exact words during the paper discussion, but I can articulate this better now. Let me explain. RCA is serious business Root cause analysis (RCA) is the process of identifying the underlying causes of a problem/incident, rather than just addressing its symptoms. One RCA heuristic is asking 5 Why&#
Read more >>

Foundational distributed systems papers

-
I talked about the importance of reading foundational papers last week. To followup, here is my compilation of foundational papers in the distributed systems area. (I focused on the core distributed systems area, and did not cover networking, security, distributed ledgers, verification work etc. I even left out distributed transactions, I hope to cover them at a later date.)  I classified the papers by subject, and listed them in chronological order. I also listed expository papers and blog posts at the end of each section. Time and State in Distributed Systems Time, Clocks, and the Ordering of Events in a Distributed System. Leslie Lamport, Commn. of the ACM,  1978. Distributed Snapshots: Determining Global States of a Distributed System. K. Mani Chandy Leslie Lamport, ACM Transactions on Computer Systems, 1985. Virtual Time and Global States of Distributed Systems.  Mattern, F. 1988. Practical uses of synchronized clocks in distributed systems. B. Liskov, 1991. Expository papers
Read more >>

Advice to the young

-
Image
I notice I haven't written any advice posts recently. Here is a collection of my advice posts pre 2020. I've been feeling all this elderly wisdom pent up in me, ready to pour at any moment. So here it goes. Get ready to quench your thirst from my fount of wisdom. No man, think for yourself, only get what works for you. It is called foundations, not theory Foundations of computer science (or rather any field of study) are the most important topics you can learn. These lay down the frame of thinking/perspective for that area of study. Yet, I am saddened to hear these called as "theory", and labeled as "unpractical". This couldn't be farther from the truth. Take a look at how I recommend studying distributed systems . Don't you dare call this "theory" and "unpractical". This lays the bedrock that you build your practice on. Don't skimp on the foundations. Don't build your home on quicksand. Keep your hands dirty, your mind cl
Read more >>

Linearizability: A Correctness Condition for Concurrent Objects

-
Image
This paper is from Herlihy and Wing appeared in ACM Transactions on Programming Languages and Systems 1990. This is the canonical reference for the linearizability definition. I had not read this paper in detail before, so I thought it would be good to go to the source to see if there are additional delightful surprises in the original text. Hence, this post. I will dive into a technical analysis of the paper first, and then discuss some of my takes toward the end. I had written an accessible explanation of linearizability earlier; you may want to read that first. I will assume an understanding of linearizability to keep this review at reasonable length. Introduction I love how the old papers just barge in with the model, without bothered by pleasantries such as motivation of the problem. These are the first two sentences of the introduction. "A concurrent system consists of a collection of sequential processes that communicate through shared typed objects . This model encompass
Read more >>

Scalable OLTP in the Cloud: What’s the BIG DEAL?

-
Image
This paper is from Pat Helland, the apostate philosopher of database systems, overall a superb person, and a good friend of mine. The paper appeared this week at CIDR'24. (Check out the program for other interesting papers). The motivating question behind this work is: " What are the asymptotic limits to scale for cloud OLTP (OnLine Transaction Processing) systems? " Pat says that the CIDR 2023 paper "Is Scalable OLTP in the Cloud a Solved Problem?" prompted this question.  The answer to the question? Pat says that the answer lies in the joint responsibility of database and the application. If you know of Pat's work, which I have summarized several in this blog , you would know that Pat has been advocating along these lines before. But this paper provides a very crisp, specific, concrete answer. Read on for my summary of the paper. Disclaimer: This is a wisdom and technical information/detail packed 13-page paper, so I will try my best to summarize the sa
Read more >>

Understanding the Performance Implications of Storage-Disaggregated Databases

-
Image
Storage-compute disaggregation in databases has emerged as a pivotal architecture in cloud environments, as evidenced by Amazon ( Aurora ), Microsoft ( Socrates ), Google (AlloyDB), Alibaba ( PolarDB ), and Huawei (Taurus). This approach decouples compute from storage, allowing for independent and elastic scaling of compute and storage resources. It provides fault-tolerance at the storage level. You can then share the storage for other services, such as adding read-only replicas for the databases. You can even use the storage level for easier sharding of your database. Finally, you can also use this for exporting a changelog asynchronously to feed into peripheral cloud services, such as analytics. Disaggregated architecture was the topic of Sigmod 23 panel . I think this quote summarizes the industry's thinking on the topic. "Disaggregated architecture is here, and is not going anywhere. In a disaggregated architecture, storage is fungible, and computing scales independently.
Read more >>

Designing Data Intensive Applications (DDIA) Book

-
Image
We started reading this book as part of Alex Petrov's book club . We just got started, so you can join us, by joining the discord channel above. We meet Wednesday's 11am Eastern Time.  Previously we had read transaction processing book by Grey and Reuters. This page links to my summaries of that book. Chp 1. Reliable, Scalable, and Maintainable Applications I love the diagrams opening each chapter. Beautiful! The first chapter consists of warm up stuff. It talks about the definitions of reliabilty, scalability, and maintainability. It is still engaging, because  it is written with an educator and technical blogger voice, rather than a dry academic voice. This book came out on 2017. Martin is working on the new version. So if you have comments for things to focus on for the new version, it would be helpful to collect them in a document and email it to Martin. For example, I am curious about how the below paragraph from the Preface will get revised with 8 more years of hindsight:
Read more >>