DragonflyDB’s Distributed Transactions in a Shared-Nothing Architecture

DragonflyDB is a high-performance, multi-threaded in-memory data store designed as a drop-in replacement for Redis, offering significantly higher throughput. A key aspect of its architecture is its unique approach to implementing transactions, especially in a shared-nothing setup.

Shared-Nothing Architecture Overview

Unlike traditional systems that might use a single global hash table, DragonflyDB adopts a shared-nothing architecture. This means that the data is partitioned and split across N mutually exclusive hash tables, each managed by a dedicated thread (often referred to as a Shard thread). This design choice has significant implications for how transactions, particularly those affecting multiple keys across different hash tables (shards), are handled.

Transaction Requirements

For any transaction, two fundamental properties are essential:

1. Atomicity: All operations within a transaction must either complete successfully or none of them should. There is no partial completion. For example, if a transaction involves PUT K1 V1 and PUT K2 V2 where K1 and K2 belong to different shards, either both operations commit, or neither does.
2. Serializability: The concurrent execution of transactions must produce the same result as if they were executed sequentially in some order. This ensures consistency and correctness.

The Coordinator Fiber and Message Passing

When a client initiates a transaction with DragonflyDB, a specific I/O fiber (thread) on the server handles this connection. This fiber assumes the role of the coordinator for that transaction. The coordinator is responsible for managing the entire transaction lifecycle from beginning to end.

In a shared-nothing architecture, the coordinator fiber cannot directly access data owned by other shards. Instead, it must communicate with the relevant shard threads using a message passing paradigm. This is analogous to Go channels for inter-goroutine communication, but here it’s between threads within the same machine. DragonflyDB leverages a message bus pattern for this inter-thread communication.

Two-Phase Commit (2PC) in DragonflyDB

DragonflyDB implements transactions using a mechanism similar to the Two-Phase Commit (2PC) protocol, commonly found in distributed systems. However, in DragonflyDB’s context, 2PC is applied across multiple threads within the same machine rather than across multiple machines. This is a crucial distinction, as the shared-nothing architecture makes individual threads behave like independent nodes in a distributed system.

The two phases of a DragonflyDB transaction are:

1. Schedule Phase
2. Execution Phase

1. Schedule Phase

The schedule phase is initiated by the coordinator fiber and involves all shards that own keys participating in the transaction.

Process:

1. Coordinator Initiates Schedule: The coordinator fiber sends a SCHEDULE call with all transaction details (including involved keys) to each corresponding shard thread. For example, if K1 is on Shard 1 and K2 is on Shard 2, the coordinator sends SCHEDULE messages to both Shard 1 and Shard 2.
2. Coordinator Waits for Acknowledgement: The coordinator then waits for acknowledgements from all involved shards.
3. Throughput Preservation: During this waiting period, only the coordinator fiber itself is blocked. All other I/O fibers and shard threads continue processing other client connections and operations, ensuring that overall system throughput is not compromised.
4. Shard Thread Actions:
   • Upon receiving a SCHEDULE call, each shard thread adds the transaction to its local transaction queue.
   • Every transaction is assigned a unique integer identification (e.g., Transaction 1, Transaction 9).
   • The local transaction queue is ordered by a sequence number.
   • Scheduling Algorithm: A scheduling algorithm runs on the shard to arrange the incoming transaction within its local queue in a way that maintains serializability. This might involve reordering transactions if necessary to prevent conflicts.
   • Transaction Failure: If the scheduling algorithm cannot arrange the transaction to maintain serializability, the transaction is failed by the shard. The coordinator would then remove it from its internal tracking and potentially retry the transaction from the first step.
   • Intent Locks: When a transaction is added to a shard’s queue, the shard maintains an “intent lock” for the keys involved. This is not an exclusive lock. It merely signifies that a transaction is interested in modifying that specific key.
   • No Exclusivity: It’s critical to understand that the schedule phase does not grant exclusivity over the keys. Other transactions can still mutate the key even if another transaction has completed its schedule phase for that key. The intent lock simply indicates an intention to modify and allows the transaction to be enqueued and ordered for serializability.

2. Execution Phase

Once the coordinator receives acknowledgements from all involved shards for the schedule phase, it proceeds to the execution phase.

Process:

1. Coordinator Sends Execute Messages: The coordinator sends EXECUTE messages to the corresponding shard threads for each command within the transaction (e.g., “execute PUT K1 V1”, “execute PUT K2 V2”).
2. Shard Thread Execution Logic:
   • When a shard thread receives an EXECUTE message, it checks its local transaction queue.
   • Head-of-Queue Execution: A shard only executes the command for the transaction that is currently at the head of its queue.
   • Blocking for Order: If a shard receives an EXECUTE message for a transaction that is not at the head of its queue, it will block temporarily. It waits until the transaction at the head of the queue has been executed (and removed), and its own transaction moves to the head. This mechanism strictly enforces the order determined by the scheduling algorithm, thereby guaranteeing serializability.
3. Completion and Resource Release:
   • For the very last command in a transaction, the coordinator sends an EXEC+FIN (Execute + Finish) message.
   • Upon receiving EXEC+FIN, the shard executes the command, releases any internal locks or resources associated with that transaction, and removes the transaction from its local transaction queue, marking it as complete.

Conclusion

DragonflyDB’s implementation of transactions, leveraging a shared-nothing architecture and a two-phase commit-like protocol across threads, is a sophisticated approach to achieving atomicity and serializability within a single machine. By treating individual threads as independent entities and using message passing, it effectively mimics distributed system patterns to manage concurrent operations on partitioned data, all while maintaining high throughput.