DragonflyDB’s DashTables: A Deep Dive into High-Performance Data Storage

DragonflyDB, a drop-in replacement for Redis, distinguishes itself by employing a novel data structure called DashTables instead of traditional hash tables. This architectural choice results in significantly faster performance—up to 4-15 times faster—and reduced memory overhead. This article delves into the internals of both Redis’s hash table implementation and DragonflyDB’s DashTables to understand the fundamental differences that lead to such dramatic performance gains.

Redis Hash Table Internals

Redis dictionaries are not simply single hash tables; they are designed with a sophisticated rehashing mechanism to optimize performance.

Data Structure and Rehashing

A Redis dictionary typically consists of two hash tables:

• Active Hash Table: Used for regular operations (reads, writes).
• Rehashing Hash Table: Used during the rehashing process.

Redis employs lazy rehashing rather than eager rehashing. This means that when a hash table needs to expand (e.g., to accommodate more items), it doesn’t immediately rehash all elements. Instead, it gradually moves elements from the old hash table to the new one during subsequent operations.

Rehashing is triggered when the load factor of the hash table exceeds a certain threshold, typically between 50% and 75%. When rehashing occurs, the new hash table is usually doubled in size to ensure sufficient capacity.

dictEntry Structure and Memory Overhead

Each entry in a Redis dictionary (dictEntry) is structured as follows:

• Key Pointer: 8 bytes
• Value: 8 bytes (pointer to value)
• Next Pointer: 8 bytes (for chaining)

Thus, the bare minimum size for a dictEntry is 8 + 8 + 8 = 24 bytes. For N elements, the minimum memory required is 24 * N bytes.

Redis uses chaining for conflict resolution. Each bucket in the hash table is a pointer to a linked list of dictEntry objects.

Considering the overhead:

• Load Factor 100%: Total size 32N bytes (24N for entries + 8N for bucket pointers).
• Load Factor 75%: Total size 34N bytes.
• Load Factor 50%: Total size 40N bytes.

The data structure overhead per entry in Redis is 16 to 24 bytes (total entry size minus 16 bytes for key and value pointers). During a resize operation, this overhead can increase to 16 to 32 bytes per entry, as a new hash table of double the size needs to be allocated and elements potentially moved. This complete rehashing of all elements is a significant performance bottleneck.

DragonflyDB DashTables: A Superior Approach

DragonflyDB’s DashTables are designed to overcome the limitations of traditional hash tables, particularly the overhead associated with resizing and rehashing. DashTables achieve a significantly lower memory overhead of 6 to 16 bytes per entry.

DashTable Architecture

A DashTable is fundamentally an array of pointers at the front. Each pointer in this array points to a segment.

• Segments: Each segment acts as a mini hash table of a constant, fixed size. This is a crucial design choice.
• Dynamic Sizing: The length of the front array (array of segment pointers) is N / S, where N is the total number of entries and S is the fixed capacity of a single segment. For example, if a segment can hold 1,000 entries, the front array’s size is N / 1000. This keeps the front array relatively small.

The overall structure is an array of segments, and each segment is an array of dictEntry objects (or similar key-value pairs).

Insertion Mechanism

The insertion process in a DashTable is optimized to minimize data movement:

1. Hash Key: The key is hashed to determine which segment it belongs to.
2. Attempt Insertion: The system attempts to insert the key-value pair into the identified segment.
3. Segment Full Condition: If the target segment is full (as segments have a fixed size):
   • The segment is split.
   • A new segment is created and added to the array of segments.
   • Only the elements within the original, full segment are rehashed and redistributed between the old and new segments.

This approach contrasts sharply with Redis, where a full hash table resize requires rehashing and potentially moving all elements. DashTables only affect a small subset of data, leading to minimal data movement and significantly better performance.

Deep Dive into Segment Implementation

Each segment in a DashTable is itself a specialized hash table designed for efficiency. A typical segment consists of:

• Regular Buckets: 56 regular buckets.
• Stash Buckets: 4 stash buckets.
• Slots per Bucket: Each bucket (regular or stash) has 14 slots.

This configuration allows each segment to hold a total of (56 + 4) * 14 = 60 * 14 = 840 key-value pairs. This fixed size of 840 entries per segment is a key aspect of DashTables.

Insertion within a Segment

When inserting an item into a specific segment:

1. Find Home Bucket: The key is hashed (e.g., hash(key) % 56) to determine its “home bucket” among the 56 regular buckets.
2. Open Addressing: The system attempts to find the first free slot within this home bucket using open addressing (not chaining).
3. Overflow Handling:
   • If the home bucket is full, it attempts to insert into the next bucket (e.g., (home_bucket_index + 1) % 56).
   • If the next bucket is also full, it attempts to insert into one of the stash buckets.
   • If all stash buckets are also full, it signifies that the segment is truly full. This triggers a segment split, as described above.

This localized search (home bucket, next bucket, stash) provides sufficient chances for insertion while quickly identifying when a segment needs to be split, avoiding extensive lookups. On average, a segment split might occur approximately every 1,000 new insertions.

Key Performance Benefits and Trade-offs

The DashTable design offers several compelling advantages:

• Minimal Data Movement: The most significant benefit is that only a small portion of data (elements within a single segment) is affected during a split. Most elements in the DashTable remain in their original locations, unlike the complete rehashing required in traditional hash tables. This leads to higher throughput.
• Fixed-Size Segments: The constant size of segments simplifies memory management and reduces pointer overhead.
• Lower Memory Overhead: The design results in a significantly lower memory footprint per entry (6-16 bytes) compared to Redis (16-32 bytes).
• Predictable Performance: While segment splits introduce a slight latency spike, they are localized and infrequent, leading to generally more predictable performance.

Performance Benchmarks

DragonflyDB’s DashTables demonstrate superior performance across various benchmarks:

Insertion Time and Memory Consumption

For inserting 20 million rows:

• DragonflyDB: 2.43 seconds, 896 MB memory.
• Redis 6: 16 seconds, 1.73 GB memory.

This shows DragonflyDB is significantly faster and more memory-efficient.

Latency Analysis

When observing latency metrics (average, P99, P999, Max latency) on a log scale, DashTables consistently outperform Redis dictionaries, often being 4-15 times faster.

A notable anomaly is observed at P99.9 latency. This slight spike is attributed to the segment split operations that occur approximately every 1,000 insertions. However, this trade-off is beneficial:

• Lower Max Latency: By accepting a slightly higher P99.9 latency, DashTables achieve much lower overall maximum latencies.
• Consistent Snapshotting: This design choice leads to more consistent snapshotting performance, which is crucial for massive data dumps and recovery operations in an in-memory key-value store.

Conclusion

DragonflyDB’s DashTables represent a sophisticated and highly optimized data structure for in-memory key-value stores. By moving away from traditional hash table resizing mechanisms and introducing fixed-size segments with localized rehashing, DashTables achieve remarkable improvements in insertion speed, memory efficiency, and overall throughput compared to Redis. This innovative approach highlights how fundamental data structure decisions can profoundly impact the performance of high-performance systems.