Ensuring Atomicity: A Tale of Dragonfly Transactions

Introduction

Dragonfly is a multi-threaded data store. It uses multiple threads not only to manage I/O operations but also to execute data operations in parallel. One thread might be computing the intersection of a few sets; another might be extending a list with data; and a third might be preparing to flush the data store.

Developers generally know that thread synchronization is difficult and expensive, both from a logical and computational perspective. Firstly, we need to ensure exclusive access to keys, but we certainly don't want to slow the whole system down by lock contentions and burning all our computational resources on a single hot key. Secondly, the data store itself has dozens of state parameters that control replication, snapshotting, memory limits, client pauses, cluster mode, and many other aspects. Some of these state parameters have to be changed carefully without interrupting any running commands; others are accessed frequently, so global synchronization across many threads would have a devastating cost.

Shared-Nothing Architecture

Our shared-nothing architecture addresses the problems described above. Its philosophy is dead simple: making each thread as independent as possible. The first problem, exclusive access to keys, is solved by dividing the entire dataset into smaller sections called shards. Keys in a single shard are managed exclusively by one dedicated thread, which is known as a shard-thread. Conversely, most of our state parameters are copied across all threads and are updated with specific routines on the threads themselves. Eventually, it's consistent, but it very well could be that one thread is starting to snapshot all of its keys while another, unknowingly, is still finishing an expensive operation.

Navigating through this seemingly sophisticated architecture of Dragonfly might lead one to wonder: How does it manage to maintain atomicity and serializability for complex multi-key operations? Consider commands like SINTERSTORE or the execution of Lua scripts with atomicity guarantees. How does Dragonfly ensure these operations are performed efficiently without hindering the system's ability to handle other non-overlapping commands, especially when such multi-key operations are in progress? To find out the answer, we have to examine Dragonfly's transactional framework. It is based on the very lightweight locking (VLL) algorithm, though it has evolved over time and grown with custom optimizations and logic.

Let's start our journey by exploring the transactional framework through a metaphorical lens.

A Metaphorical Journey - Transactions in Dragonfly

Imagine yourself as the trade master in a small, mystical kingdom composed of three distinct towns: one red, one green, and one blue. The people in each town have a unique preference—they only appreciate items in their town's color and strongly disapprove of any other hues. Your role involves managing the distribution and storage of colorful goods, which are regularly brought to you by pilgrims and visitors. These goods vary in color, requiring careful allocation to the respective towns based on their color preferences.

You employ couriers to transport these goods to the appropriate towns. However, there's a catch: the kingdom is full of curious pilgrims and visitors who often inquire about the inventory across all three towns. Providing accurate information is crucial, as any mistake or inconsistency in your reports can disappoint them. They will get upset and won't come back again.

You might quickly spot similarities to our problems and realize the metaphor we are using:

The towns represent different shards in Dragonfly, each handles specific keys.
The pilgrims and visitors are client SDKs, issuing write and read commands.
And you, the trade master, are carrying out the role of the transactional framework.

One day, you receive a blue teacup and dispatch a courier to store it in the Blue Town. Shortly thereafter, you're asked about the total number of blue cookware items in preparation for a tea party. You send another courier to Blue Town to calculate. It's crucial that this count includes the newly dispatched teacup, even if it hasn't physically arrived yet, because the visitors exchanging this information expect immediate and accurate answers.

To avoid any mistakes in relaying information, you instruct all your couriers to travel only along a single road to Blue Town and never overtake each other. Moreover, recognizing that couriers might not arrive at the destination in the order they were sent, you also assign successive numbers to couriers, so they know how to reorder themselves once they queue up on the road.

In Dragonfly, this orderly procession is mirrored by what's called a shard's transaction queue. This queue holds all pending operations for a specific shard. The sequential numbers of couriers are reflected as transaction IDs (txid), assigned by incrementing a single global atomic counter. Multi-key operations, such as MSET, which mimics storing multiple goods in different colors, are broken into separate operations. These operations are then managed by the corresponding shards, but share the same transaction ID.

Tricky Questions by Visitors - Shard Locks

The concept of sharding, as we've discussed, might seem straightforward to those familiar with distributed systems. However, the scenario complicates when we consider more unpredictable interactions, much like dealing with capricious pilgrimage visitors in our metaphorical kingdom.

Imagine a pilgrim man who has whimsical thoughts and asks the number of flowers you possess, with his offering depending on your answer. If you report plenty, he might worry that you will forget to water them and leave you without more flowers. His decision could vary—he might choose to give you something else or ask additional questions. More importantly, your answers can't change while you're talking to him, even though you might be interrupted by other pilgrims offering you goods. If another visitor wants to discuss flowers, you'd need to politely ask them to wait, ensuring the first pilgrim's inquiry is addressed with undivided attention.

Technically speaking, the interaction with you, the trade master, should be atomic—as if no two visitors spoke with you at the same time. Those complicated interactions might remind us of MULTI/EXEC transactions, Lua scripts, or regular multi-key commands like SINTERSTORE, where the write operation depends on the preceding read.

A strategy is employed for these prolonged conversations: the courier locks the town upon departure, ensuring that any information collected won’t change by the time they return. Although the courier must queue to enter the town for the first visit, subsequent visits allow bypassing the queue, effectively locking the town for their exclusive access. As shown below, the whole Blue Town is locked because of this traveling courier. This is called a shard lock in Dragonfly.

This strategy ensures each prolonged conversation, or transaction, is atomic, eliminating the need to keep track of all ongoing interactions. Couriers, upon their return, provide updates and necessary information, streamlining the process and maintaining the integrity of each transaction.

In Dragonfly, a transaction occupying the shard is called a continuation because, as the name suggests, it aims to proceed without interruption. While active, no other transactions can be processed on that shard. The shard's transaction queue is effectively paused until the continuation concludes. Now the importance of our linear order with unique transaction IDs comes into play—if such an order is ensured on all the roads, it is impossible to reach a deadlock. As couriers with lower IDs always have priority, the system is guaranteed to be lively.

Avoid Locking Entire Towns - Intent Locks

As your kingdom expands and the flow of trading goods increases, you realize that locking up entire towns is becoming prohibitively expensive. The roads are clogged with queues, and you have to lock down all towns for a single question about various items of different colors—the whole country will come to a standstill!

To tackle this problem, you devise a clever strategy: sending couriers in pairs. One courier holds a spot in the queue, ensuring their place is secure and preventing any accidental overtaking. Meanwhile, the other courier advances, checking with those ahead in the queue and the town guard to see if the town is locked for a reason relevant to their mission. If there's no conflict of interest, they can proceed into town to fulfill the delivery. This method not only streamlines the process but also allows for flexibility. Sometimes, the fellow courier in the queue can withdraw without needing to enter the town, reducing unnecessary congestion.

This kind of record system is technically known as intent locks. Unlike traditional locks, where actors gain exclusive control of resources, intent locks are about declaring a future intention to acquire such control. This mechanism relies on a predetermined order—fortunately, something we have already established in our system. In the meantime, to avoid the inefficiency of scanning the entire transaction queue, Dragonfly keeps a compact table of intent locks in every thread.

Different kinds of items in our metaphor are simply different keys. A transaction that can execute before it reaches the front of the queue is known as an out-of-order transaction. In practice, most commands in Dragonfly are expected to execute out-of-order. Long transaction queues are only accumulated if excessively frequently accessed keys are involved.

Conclusion

In this journey, we have demonstrated in a metaphorical way how Dragonfly, with its sophisticated yet accessible transactional framework, brings order and efficiency to complex data operations. By implementing effective mechanisms and leveraging clever optimizations, Dragonfly achieves the atomicity and serializability standards expected of a modern in-memory data store.

Dragonfly is officially integrated with background job processing systems like BullMQ and Sidekiq, which heavily rely on Lua scripts and multi-key operations. The transactional framework ensures that these operations are executed efficiently, which makes Dragonfly an outstanding choice as the backend store for these libraries. Get started with Dragonfly today and experience the power of a high-throughput, multi-threaded in-memory data store!