dragonfly Documentation

File: README.md Copy Chapter

Before moving on, please consider giving us a GitHub star ⭐️. Thank you!

Other languages: 简体中文 日本語 한국어 Português

Website • Docs • Quick Start • Community Discord • Dragonfly User Conference • Join the Dragonfly Community

GitHub Discussions • GitHub Issues • Contributing • AI Agents Guide • Dragonfly Cloud

The world's most efficient in-memory data store Copy Chapter

Dragonfly is an in-memory data store built for modern application workloads.

Fully compatible with Redis and Memcached APIs, Dragonfly requires no code changes to adopt. Compared to legacy in-memory datastores, Dragonfly delivers 25X more throughput, higher cache hit rates with lower tail latency, and can run on up to 80% less resources for the same sized workload.

Contents Copy Chapter

• Benchmarks
• Quick start
• Configuration
• Design decisions
• Background
• Build from source
• Contributors

Benchmarks Copy Chapter

memtier_benchmark --ratio ... -t  -c 30 -n 200000 --distinct-client-seed -d 256 \
     --expiry-range=...

With a comparable latency, Dragonfly throughput outperformed Memcached throughput in both write and read workloads. Dragonfly demonstrated better latency in write workloads due to contention on the write path in Memcached.

SET benchmark

GET benchmark

Memcached exhibited lower latency for the read benchmark, but also lower throughput.

Memory efficiency Copy Section

To test memory efficiency, we filled Dragonfly and Redis with ~5GB of data using the debug populate 5000000 key 1024 command, sent update traffic with memtier, and kicked off the snapshotting with the bgsave command.

This figure demonstrates how each server behaved in terms of memory efficiency.

Dragonfly was 30% more memory efficient than Redis in the idle state and did not show any visible increase in memory use during the snapshot phase. At peak, Redis memory use increased to almost 3X that of Dragonfly.

Dragonfly finished the snapshot faster, within a few seconds.

For more info about memory efficiency in Dragonfly, see our Dashtable doc.

Configuration Copy Chapter

• memcached_port: The port to enable Memcached-compatible API on (default: disabled).

• keys_output_limit: Maximum number of returned keys in keys command (default: 8192). Note that keys is a dangerous command. We truncate its result to avoid a blowup in memory use when fetching too many keys.

• dbnum: Maximum number of supported databases for select.

• cache_mode: See the novel cache design section below.

• hz: Key expiry evaluation frequency (default: 100). Lower frequency uses less CPU when idle at the expense of a slower eviction rate.

• snapshot_cron: Cron schedule expression for automatic backup snapshots using standard cron syntax with the granularity of minutes (default: "").
  Here are some cron schedule expression examples below, and feel free to read more about this argument in our documentation.

  Cron Schedule Expression	Description
  * * * * *	At every minute
  */5 * * * *	At every 5th minute
  5 */2 * * *	At minute 5 past every 2nd hour
  0 0 * * *	At 00:00 (midnight) every day
  0 6 * * 1-5	At 06:00 (dawn) from Monday through Friday

• primary_port_http_enabled: Allows accessing HTTP console on main TCP port if true (default: true).

• admin_port: To enable admin access to the console on the assigned port (default: disabled). Supports both HTTP and RESP protocols.

• admin_bind: To bind the admin console TCP connection to a given address (default: any). Supports both HTTP and RESP protocols.

• admin_nopass: To enable open admin access to console on the assigned port, without auth token needed (default: false). Supports both HTTP and RESP protocols.

• cluster_mode: Cluster mode supported (default: ""). Currently supports only emulated.

• cluster_announce_ip: The IP that cluster commands announce to the client.

• announce_port: The port that cluster commands announce to the client, and to replication master.

Example start script with popular options: Copy Section

./dragonfly-x86_64 --logtostderr --requirepass=youshallnotpass --cache_mode=true -dbnum 1 --bind localhost --port 6379 --maxmemory=12gb --keys_output_limit=12288 --dbfilename dump.rdb

Arguments can be also provided via:

• --flagfile <filename>: The file should list one flag per line, with equal signs instead of spaces for key-value flags. No quotes are needed for flag values.
• Setting environment variables. Set DFLY_x, where x is the exact name of the flag, case sensitive.

For more options like logs management or TLS support, run dragonfly --help.

Design decisions Copy Chapter

For more detailed differences between Dragonfly expiration deadlines and Redis implementations, see here.

Native HTTP console and Prometheus-compatible metrics Copy Section

By default, Dragonfly allows HTTP access via its main TCP port (6379). That's right, you can connect to Dragonfly via Redis protocol and via HTTP protocol — the server recognizes the protocol automatically during the connection initiation. Go ahead and try it with your browser. HTTP access currently does not have much info but will include useful debugging and management info in the future.

Go to the URL :6379/metrics to view Prometheus-compatible metrics.

The Prometheus exported metrics are compatible with the Grafana dashboard, see here.

Important! The HTTP console is meant to be accessed within a safe network. If you expose Dragonfly's TCP port externally, we advise you to disable the console with --http_admin_console=false or --nohttp_admin_console.

Background Copy Chapter

Our first challenge was how to fully utilize CPU, memory, and I/O resources using servers that are available today in public clouds. To solve this, we use shared-nothing architecture, which allows us to partition the keyspace of the memory store between threads so that each thread can manage its own slice of dictionary data. We call these slices "shards". The library that powers thread and I/O management for shared-nothing architecture is open-sourced here.

To provide atomicity guarantees for multi-key operations, we use the advancements from recent academic research. We chose the paper "VLL: a lock manager redesign for main memory database systems” to develop the transactional framework for Dragonfly. The choice of shared-nothing architecture and VLL allowed us to compose atomic multi-key operations without using mutexes or spinlocks. This was a major milestone for our PoC and its performance stood out from other commercial and open-source solutions.

Our second challenge was to engineer more efficient data structures for the new store. To achieve this goal, we based our core hashtable structure on the paper "Dash: Scalable Hashing on Persistent Memory". The paper itself is centered around the persistent memory domain and is not directly related to main-memory stores, but it's still most applicable to our problem. The hashtable design suggested in the paper allowed us to maintain two special properties that are present in the Redis dictionary: The incremental hashing ability during datastore growth the ability to traverse the dictionary under changes using a stateless scan operation. In addition to these two properties, Dash is more efficient in CPU and memory use. By leveraging Dash's design, we were able to innovate further with the following features:

• Efficient record expiry for TTL records.
• A novel cache eviction algorithm that achieves higher hit rates than other caching strategies like LRU and LFU with zero memory overhead.
• A novel fork-less snapshotting algorithm.

Once we had built the foundation for Dragonfly and we were happy with its performance, we went on to implement the Redis and Memcached functionality. We have to date implemented ~185 Redis commands (roughly equivalent to Redis 5.0 API) and 13 Memcached commands.

And finally,
Our mission is to build a well-designed, ultra-fast, cost-efficient in-memory datastore for cloud workloads that takes advantage of the latest hardware advancements. We intend to address the pain points of current solutions while preserving their product APIs and propositions.

Contributors Copy Chapter

File: contrib/docker/README.md Copy Chapter

Dragonfly DB with Docker Compose

This guide will have you up running DragonflyDB with docker-compose in just a few minutes.

| This guide assumes you have docker and docker-compose installed on your machine. If not, Install Docker and Install Docker Compose before continuing.

Step 1 Copy Chapter

# Download Official Dragonfly DB Docker Compose File
wget https://raw.githubusercontent.com/dragonflydb/dragonfly/main/contrib/docker/docker-compose.yml

# Launch the Dragonfly DB Instance
docker-compose up -d

# Confirm image is up
docker ps | grep dragonfly
# ac94b5ba30a0   docker.dragonflydb.io/dragonflydb/dragonfly   "entrypoint.sh drago…"   45 seconds ago   Up 31 seconds         0.0.0.0:6379->6379/tcp, :::6379->6379/tcp   docker_dragonfly_1

# Log follow the dragonfly container
docker logs -f docker_dragonfly_1

Dragonfly DB will answer to both http and redis requests out of the box!

You can use redis-cli to connect to localhost:6379 or open a browser and visit http://localhost:6379

Step 2 Copy Chapter

Connect with a redis client.

From a new terminal:

redis-cli
127.0.0.1:6379> set hello world
OK
127.0.0.1:6379> keys *
1) "hello"
127.0.0.1:6379> get hello
"world"
127.0.0.1:6379>

Step 3 Copy Chapter

Continue being great and build your app with the power of DragonflyDB!

Tuning Dragonfly DB Copy Chapter

If you are attempting to tune Dragonfly DB for performance, consider NAT performance costs associated with containerization.

Performance Tuning Copy Chapter

---

In docker-compose, there is a meaningful difference between an overlay network(which relies on docker NAT traversal on every request) and using the host network(see docker-compose.yml).
 
For more information, see the official docker-compose network_mode Docs
 

More Build Options Copy Section

• Docker Quick Start
• Kubernetes Deployment with Helm Chart
• Build From Source

File: contrib/charts/dragonfly/README.md Copy Chapter

dragonfly

Dragonfly is a modern in-memory datastore, fully compatible with Redis and Memcached APIs.

Homepage: https://dragonflydb.io/

Source Code Copy Chapter

• https://github.com/dragonflydb/dragonfly

Requirements Copy Chapter

Kubernetes: >=1.23.0-0

Installing from a pre-packaged OCI Copy Chapter

Pick a version from https://github.com/dragonflydb/dragonfly/pkgs/container/dragonfly%2Fhelm%2Fdragonfly

Example:

VERSION=v1.12.1
helm upgrade --install dragonfly oci://ghcr.io/dragonflydb/dragonfly/helm/dragonfly --version $VERSION

Values Copy Chapter

Autogenerated from chart metadata using helm-docs v1.11.0

File: docs/quick-start/README.md Copy Chapter

Quick Start

Starting with docker run is the simplest way to get up and running with DragonflyDB.

If you do not have docker on your machine, Install Docker before continuing. On Windows you can configure WSL Containers for lower resource usage.

Step 1 Copy Chapter

On linux Copy Section

docker run --network=host --ulimit memlock=-1 docker.dragonflydb.io/dragonflydb/dragonfly

On macOS Copy Section

network=host doesn't work well on macOS, see this issue

docker run -p 6379:6379 --ulimit memlock=-1 docker.dragonflydb.io/dragonflydb/dragonfly

On Windows Copy Section

network=host doesn't work on Windows

wslc run -p 6379:6379 --ulimit memlock=-1 docker.dragonflydb.io/dragonflydb/dragonfly

Dragonfly DB will answer to both http and redis requests out of the box!

You can use redis-cli to connect to localhost:6379 or open a browser and visit http://localhost:6379

NOTE: On some configurations, running with the docker run --privileged ... flag can fix some
initialization errors.

Step 2 Copy Chapter

Connect with a redis client

redis-cli
127.0.0.1:6379> set hello world
OK
127.0.0.1:6379> keys *
1) "hello"
127.0.0.1:6379> get hello
"world"
127.0.0.1:6379>

Step 3 Copy Chapter

Continue being great and build your app with the power of DragonflyDB!

Known issues Copy Chapter

More Build Options Copy Chapter

• Docker Compose Deployment
• Kubernetes Deployment with Helm Chart
• Build From Source

File: docs/build-from-source.md Copy Chapter

Build DragonflyDB From Source

Running the server Copy Chapter

Dragonfly runs on linux. We advise running it on linux version 5.11 or later
but you can also run Dragonfly on older kernels as well.

Step 1 - install dependencies Copy Chapter

On Debian/Ubuntu:

sudo apt install ninja-build libunwind-dev libboost-context-dev libssl-dev \
     autoconf-archive libtool cmake g++ bison  zlib1g-dev

On Fedora:

sudo dnf install -y automake boost-devel g++ git cmake libtool ninja-build \
     openssl-devel libunwind-devel autoconf-archive patch bison libstdc++-static

On openSUSE:

sudo zypper install automake boost-devel gcc-c++ git cmake libtool ninja \
     openssl-devel libunwind-devel autoconf-archive patch bison \
     libboost_context-devel libboost_system-devel

On FreeBSD:

pkg install -y git bash cmake ninja libunwind boost-libs autoconf automake libtool gmake bison

Step 2 - clone the project Copy Chapter

git clone --recursive https://github.com/dragonflydb/dragonfly && cd dragonfly

Step 3 - configure & build it Copy Chapter

# Configure the build
./helio/blaze.sh -release

# Build
cd build-opt && ninja dragonfly

Build options Copy Section

Minimal debug build:

./helio/blaze.sh -DWITH_GPERF=OFF -DWITH_AWS=OFF -DWITH_GCP=OFF -DWITH_TIERING=OFF -DWITH_SEARCH=OFF -DWITH_COLLECTION_CMDS=OFF -DWITH_EXTENSION_CMDS=OFF

ccache Copy Section

For local builds, ccache is enabled automatically whenever the ccache binary is on your PATH, so incremental rebuilds recompile only the files you changed. (In CI it is enabled per-workflow, and the production make release build forces it off.) If you do not want ccache, disable it in any of these ways:

• configure with -DENABLE_CCACHE=OFF (e.g. ./helio/blaze.sh -DENABLE_CCACHE=OFF)
• set the CCACHE_DISABLE=1 environment variable
• set disable = true in your ccache config (ccache -o disable=true)

Cache size

Dragonfly is large, so ccache's default size (5 GB, or ~5% of disk on ccache ≥ 4.10) fills up quickly - more so with several build configs or multiple worktrees — and hit rates drop once it's full. The right size depends on your free disk space and how many projects share the (per-user) cache, so it's left to you. If rebuilds feel slow, raise it (50 GB is a comfortable value):

ccache -M 50G              # per-user, global; applies to all projects
ccache -p | grep max_size  # verify

Step 4 - voilà Copy Chapter

# Run
./dragonfly --alsologtostderr

Dragonfly DB will answer to both http and redis requests out of the box!

You can use redis-cli to connect to localhost:6379 or open a browser and visit http://localhost:6379

Step 5 Copy Chapter

Connect with a redis client

redis-cli
127.0.0.1:6379> set hello world
OK
127.0.0.1:6379> keys *
1) "hello"
127.0.0.1:6379> get hello
"world"
127.0.0.1:6379>

Step 6 Copy Chapter

Continue being great and build your app with the power of DragonflyDB!

File: docs/dashtable.md Copy Chapter

Dashtable in Dragonfly

Dashtable is a very important data structure in Dragonfly. This document explains
how it fits inside the engine.

Each selectable database holds a primary dashtable that contains all its entries. Another instance of Dashtable holds an optional expiry information, for keys that have TTL expiry on them. Dashtable is equivalent to Redis dictionary but have some wonderful properties that make Dragonfly memory efficient in various situations.

Redis dictionary Copy Chapter

“All problems in computer science can be solved by another level of indirection”

This section is a brief refresher of how redis dictionary (RD) is implemented.
We shamelessly "borrowed" a diagram from this blogpost, so if you want a deep-dive, you can read the original article.

Each RD is in fact two hash-tables (see ht field in the diagram below). The second instance is used for incremental resizes of the dictionary.
Each hash-table dictht is implemented as a classic hashtable with separate chaining. dictEntry is the link-list entry that wraps each key/value pair inside the table. Each dictEntry has three pointers and takes up 24 bytes of space. The bucket array of dictht is resized at powers of two, so usually its utilization is in [50, 100] range.

Let's estimate the overhead of dictht table inside RD.

Case 1: it has N items at 100% load factor, in other words, buckets count equals to number of items. Each bucket holds a pointer to dictEntry, i.e. it's 8 bytes. In total we need: $8N + 24N = 32N$ bytes per record.
Case 2: N items at 75% load factor, in other words, the number of buckets is 1.33 higher than number of items. In total we need: $N*1.33*8 + 24N \approx 34N$ bytes per record.
Case 3: N items at 50% load factor, say right after table growth. Number of buckets is twice the number of items, hence we need $N*2*8 + 24N = 40N$ bytes per record.

In best possible case we need at least 16 bytes to store key/value pair into the table, therefore
the overhead of dictht is on average about 16-24 bytes per item.

Now lets take incremental growth into account. When ht[0] is full (i.e. RD needs to migrate data to a bigger table), it will instantiate a second temporary instance ht[1] that will hold additional 2*N buckets. Both instances will live in parallel until all data is migrated to ht[1] and then ht[0] bucket array will be deleted. All this complexity is hidden from a user by well engineered API of RD. Lets combine case 3 and case 1 to analyze memory spike at this point: ht[0] holds N items and it is fully utilized. ht[1] is allocated with 2N buckets.
Overall, the memory needed during the spike is $32N + 16N=48N$ bytes.

To summarize, RD requires between 16-32 bytes overhead.

Dash table Copy Chapter

Dashtable is an evolution of an algorithm from 1979 called extendible hashing.

Similarly to a classic hashtable, dashtable (DT) also holds an array of pointers at front. However, unlike with classic tables, it points to segments and not to linked lists of items. Each segment is, in fact, a mini-hashtable of constant size. The front array of pointers to segments is called directory. Similarly to a classic table, when an item is inserted into a DT, it first determines the destination segment based on item's hashvalue. The segment is implemented as a hashtable with open-addressed hashing scheme and as I said - constant in size. Once segment is determined, the item inserted into one of its buckets. If an item was successfully inserted, we finished, otherwise, the segment is "full" and needs splitting. The DT splits the contents of a full segment in two segments, and the additional segment is added to the directory. Then it tries to reinsert the item again. To summarize, the classic chaining hash-table is built upon a dynamic array of linked-lists while dashtable is more like a dynamic array of flat hash-tables of constant size.

In the diagram above you can see how dashtable looks like. Each segment is comprised of K buckets. For example, in our implementation a dashtable has 60 buckets per segment (it's a compile-time parameter that can be configured).

Segment zoom-in Copy Section

Below you can see the diagram of a segment. It comprised of regular buckets and stash buckets. Each bucket has k slots and each slot can host a key-value record.

In our implementation, each segment has 56 regular buckets, 4 stash buckets and each bucket contains 14 slots. Overall, each dashtable segment has capacity to host 840 records. When an item is inserted into a segment, DT first determines its home bucket based on item's hash value. The home bucket is one of 56 regular buckets that reside in the table. Each bucket has 14 available slots and the item can reside in any free slot. If the home bucket is full,
then DT tries to insert to the regular bucket on the right. And if that bucket is also full,
it tries to insert into one of 4 stash buckets. These are kept deliberately aside to gather
spillovers from the regular buckets. The segment is "full" when the insertion fails, i.e. the home bucket and the neighbour bucket and all 4 stash buckets are full. Please note that segment is not necessary at full capacity, it can be that other buckets are not yet full, but unfortunately, that item can go only into these 6 buckets,
so the segment contents must be split. In case of split event, DT creates a new segment,
adds it to the directory and the items from the old segment partly moved to the new one,
and partly rebalanced within the old one. Only two segments are touched during the split event.

Now we can explain why seemingly similar data-structure has an advantage over a classic hashtable
in terms of memory and cpu.

1. Memory: we need ~N/840 entries or 8N/840 bytes in dashtable directory to host N items on average.
   Basically, the overhead of directory almost disappears in DT. Say for 1M items we will
   need ~1200 segments or 9600 bytes for the main array. That's in contrast to RD where
   we will need a solid 8N bucket array overhead - no matter what.
   For 1M items, it will obviously be 8MB. In addition, dash segments use open addressing collision
   scheme with probing, that means that they do not need anything like dictEntry.
   Dashtable uses lots of tricks to make its own metadata small. In our implementation,
   the average tax per entry is short of 20 bits compared to 64 bits in RD (dictEntry.next).
   In addition, DT incremental resize does not allocate a bigger table - instead
   it adds a single segment per split event. Assuming that key/pair entry is two 8
   byte pointers like in RD, then DT requires $16N + (8N/840) + 2.5N + O(1) \approx 19N$
   bytes at 100% utilization. This number is very close to the optimum of 16 bytes.
   In unlikely case when all segments just doubled in size, i.e.
   DT is at 50% of utilization we may need $38N$ bytes per item.
   In practice, each segment grows independently from others,
   so the table has smooth memory usage of 22-32 bytes per item or 6-16 bytes overhead.

2. Speed: RD requires an allocation for dictEntry per insertion and deallocation per deletion. In addition, RD uses chaining, which is cache unfriendly on modern hardware. There is a consensus in engineering and research communities that classic chaining schemes are slower than open addressing alternatives.
   Having said that, DT also needs to go through a single level of indirection when
   fetching a segment pointer. However, DT's directory size is relatively small:
   in the example above, all 9K could resize in L1 cache. Once the segment is determined,
   the rest of the insertion, however, is very fast an mostly operates on 1-3 memory cache lines.
   Finally, during resizes, RD requires to allocate a bucket array of size 2N.
   That could be time consuming - imagine an allocation of 100M buckets for example.
   DT on the other hand requires an allocation of constant size per new segment. DT is faster
   and what's more important - it's incremental ability is better. It eliminates latency spikes
   and reduces tail latency of the operations above.

Please note that with all efficiency of Dashtable, it can not decrease drastically the
overall memory usage. Its primary goal is to reduce waste around dictionary management.

Having said that, by reducing metadata waste we could insert dragonfly-specific attributes
into a table's metadata in order to implement other intelligent algorithms like forkless save. This is where some of the Dragonfly's disrupting qualities can be seen.

Benchmarks Copy Chapter

There are many other improvements in dragonfly that save memory besides DT. I will not be
able to cover them all here. The results below show the final result as of May 2022.

Populate single-threaded Copy Section

To compare RD vs DT I often use an internal debugging command "debug populate" that quickly fills both datastores with data. It just saves time and gives more consistent results compared to memtier_benchmark.
It also shows the raw speed at which each dictionary gets filled without intermediary factors like networking, parsing etc.
I deliberately fill datasets with a small data to show how overhead of metadata differs between two data structures.

I run "debug populate 20000000" (20M) on both engines on my home machine "AMD Ryzen 5 3400G with 8 cores".

When looking at Redis6 "info memory" stats, you can see that used_memory_overhead field equals
to 1.0GB. That means that out of 1.73GB bytes allocated, a whooping 1.0GB is used for
the metadata. For small data use-cases the cost of metadata in Redis is larger than the data itself.

Populate multi-threaded Copy Section

Now I run Dragonfly on all 8 cores. Redis has the same results, of course.

Due to shared-nothing architecture, Dragonfly maintains a dashtable per thread with its own slice of data. Each thread fills 1/8th of 20M range it owns - and it much faster, almost 8 times faster. You can see that the total usage is even smaller, because now we maintain
smaller tables in each
thread (it's not always the case though - we could get slightly worse memory usage than with
single-threaded case, depends where we stand compared to hash table utilization).

Forkless Save Copy Section

This example shows how much memory Dragonfly uses during BGSAVE under load compared to Redis. Btw, BGSAVE and SAVE in Dragonfly is the same procedure because it's implemented using fully asynchronous algorithm that maintains point-in-time snapshot guarantees.

This test consists of 3 steps:

1. Execute debug populate 5000000 key 1024 command on both servers to quickly fill them up
   with ~5GB of data.
2. Run memtier_benchmark --ratio 1:0 -n 600000 --threads=2 -c 20 --distinct-client-seed --key-prefix="key:" --hide-histogram --key-maximum=5000000 -d 1024 command in order to send constant update traffic. This traffic should not affect substantially the memory usage of both servers.
3. Finally, run bgsave on both servers while measuring their memory.

It's very hard, technically to measure exact memory usage of Redis during BGSAVE because it creates a child process that shares its parent memory in-part. We chose cgroupsv2 as a tool to measure the memory. We put each server into a separate cgroup and we sampled memory.current attribute for each cgroup. Since a forked Redis process inherits the cgroup of the parent, we get an accurate estimation of their total memory usage. Although we did not need this for Dragonfly we applied the same approach for consistency.

As you can see on the graph, Redis uses 50% more memory even before BGSAVE starts. Around second 14, BGSAVE kicks off on both servers. Visually you can not see this event on Dragonfly graph, but it's seen very well on Redis graph. It took just few seconds for Dragonfly to finish its snapshot (again, not possible to see) and around second 20 Dragonfly is already behind BGSAVE. You can see a distinguishable cliff at second 39
where Redis finishes its snapshot, reaching almost x3 times more memory usage at peak.

Expiry of items during writes Copy Section

Efficient Expiry is very important for many scenarios. See, for example,
Pelikan paper'21. Twitter team says
that their memory footprint could be reduced by as much as by 60% by employing better expiry methodology. The authors of the post above show pros and cons of expiration methods in the table below:

They argue that proactive expiration is very important for timely deletion of expired items.
Dragonfly, employs its own intelligent garbage collection procedure. By leveraging DashTable
compartmentalized structure it can actually employ a very efficient passive expiry algorithm with low CPU overhead. Our passive procedure is complimented with proactive gradual scanning of the table in background.

The procedure is a follows:
A dashtable grows when its segment becomes full during the insertion and needs to be split.
This is a convenient point to perform garbage collection, but only for that segment.
We scan its buckets for the expired items. If we delete some of them, we may avoid growing the table altogether! The cost of scanning the segment before potential split is no more the
split itself so can be estimated as O(1).

We use memtier_benchmark for the experiment to demonstrate Dragonfly vs Redis expiry efficiency.
We run locally the following command:

memtier_benchmark --ratio 1:0 -n 600000 --threads=2 -c 20 --distinct-client-seed \
   --key-prefix="key:"  --hide-histogram --expiry-range=30-30 --key-maximum=100000000 -d 256

We load larger values (256 bytes) to reduce the impact of metadata savings
of Dragonfly.

Please note that Redis could sustain 30% less qps. That means that the optimal working sets for Dragonfly and Redis are different - the former needed to host at least 20s*131k items
at any point of time and the latter only needed to keep 20s*100K items.
So for 30% bigger working set Dragonfly needed 25% less memory at peak.

*Please ignore the performance advantage of Dragonfly over Redis in this test - it has no meaning.
I run it locally on my machine and it does not represent a real throughput benchmark.

All diagrams in this doc are created in drawio app.

File: docs/dense_set.md Copy Chapter

DenseSet in Dragonfly

DenseSet uses classic hashtable with separate chaining similar to the Redis dictionary for lookup of items within the set.

The main optimization present in DenseSet is the ability for a pointer to point to either an object or a link key, removing the need to allocate a set entry for every entry. This is accomplished by using pointer tagging exploiting the fact that the top 12 bits of any userspace address are not used and can be set to indicate if the current pointer points to nothing, a link key, or an object.

The following is what each bit in a pointer is used for

Further, to reduce collisions items may be inserted into neighbors of the home chain (the chain determined by the hash) that are empty to reduce the number of unused spaces. These entries are then marked as displaced using pointer tagging.

An example of possible bucket configurations can be seen below.

Created using excalidraw

Insertion Copy Section

To insert an entry a DenseSet will take the following steps:

1. Check if the entry already exists in the set, if so return false
2. If the entry does not exist look for an empty chain at the hash index ± 1, prioritizing the home chain. If an empty entry is found the item will be inserted and return true
3. If step 2 fails and the growth prerequisites are met, increase the number of buckets in the table and repeat step 2
4. If step 3 fails, attempt to insert the entry in the home chain.
   • If the home chain is not occupied by a displaced entry insert the new entry in the front of the list
   • If the home chain is occupied by a displaced entry move the displaced entry to its home chain. This may cause a domino effect if the home chain of the displaced entry is occupied by a second displaced entry, resulting in up to O(N) "fixes"

Searching Copy Section

To find an entry in a DenseSet:

1. Check the first entry in the home and neighbour cells for matching entries
2. If step 1 fails iterate the home chain of the searched entry and check for equality

Pending Improvements Copy Section

Some further improvements to DenseSet include allowing entries to be inserted in their home chain without having to perform the current O(N) steps to fix displaced entries. By inserting an entry in their home chain after the displaced entry instead of fixing up displaced entries, searching incurs minimal added overhead and there is no domino effect in inserting a new entry. To move a displaced entry to its home chain eventually multiple heuristics may be implemented including:

• When an entry is erased if the chain becomes empty and there is a displaced entry in the neighbor chains move it to the now empty home chain
• If a displaced entry is found as a result of a search and is the root of a chain with multiple entries, the displaced node should be moved to its home bucket

Benchmarks Copy Chapter

At 100% utilization the Redis dictionary implementation uses approximately 32 bytes per record (read the breakdown for more information)

In comparison using the neighbour cell optimization, DenseSet has ~21% of spaces unused at full utilization resulting in $N*8 + 0.2*16N \approx 11.2N$ or ~12 bytes per record, yielding ~20 byte savings. The number of bytes per record saved grows as utilization decreases.

Command memtier_benchmark -p 6379 --command "sadd __key__ __data__" -n 10000000 --threads=1 -c 1 --command-key-pattern=R --data-size=10 --key-prefix="key:" --hide-histogram --random-data --key-maximum=1 --randomize --pipeline 20
produces two sets entries with lots of small records in them.

This is how memory usage looks like with DenseSet:

File: docs/df-share-nothing.md Copy Chapter

Dragonfly Architecture

Dragonfly is a modern replacement for memory stores like Redis and Memcached. It scales vertically on a single instance to support millions of requests per second. It is more memory efficient, has been designed with reliability in mind, and includes a better caching design.

Threading model Copy Chapter

Dragonfly uses a single process with a multiple-thread architecture. Each Dragonfly thread is indirectly assigned several responsibilities via fibers.

One such responsibility is handling incoming connections. Once a socket listener accepts a client connection, the connection spends its entire lifetime bound to a single thread inside a fiber. Dragonfly is written to be 100% non-blocking; it uses fibers to provide asynchronicity in each thread. One of the essential properties of asynchronicity is that a thread cannot be blocked as long as it has pending CPU tasks. Dragonfly preserves this property by wrapping each unit of execution context in a fiber; we wrap units of execution that can potentially be blocked on I/O. For example, a connection loop runs within a fiber; a function that writes a snapshot runs inside a fiber, and so on.

As a side comment - asynchronicity and parallelism are different terms. Nodejs, for example, provides asynchronous execution but is single-threaded. Similarly, each Dragonfly thread is asynchronous on its own; therefore, Dragonfly is responsive to incoming events even when it handles long-running commands like saving to disk or running Lua scripts.

Thread actors in DF Copy Section

The DF in-memory database is sharded into N parts, where N is less or equal to the number of threads in the system. Each database shard is owned and accessed by a single thread.
The same thread can handle TCP connections and simultaneously host a database shard.
See the diagram below.

Here, our DF process spawns 4 threads, where threads 1 through 3 handle I/O (i.e., manage client connections) and threads 2 through 4 manage DB shards. Thread 2, for example, divides its CPU time between handling incoming requests and processing DB operations on the shard it owns.

So when we say that thread 1 is an I/O thread, we mean that Dragonfly can pin fibers that manage client connections to thread 1. In general, any thread can have many responsibilities that require CPU time; database management and connection handling are only two of those responsibilities.

Fibers Copy Chapter

I suggest reading my intro post about Boost.Fibers to learn more about fibers.

By the way, I want to compliment Boost.Fibers library–it has been exceptionally well designed:
it's unintrusive, lightweight, and efficient. Moreover, its default scheduler can be overridden. In the case of helio, the I/O library that powers Dragonfly, we overrode the Boost.Fibers scheduler to support shared-nothing architecture and integrate it with the I/O polling loop.

Importantly, fibers require bottom-up support in the application layer to preserve their asynchronicity. For example, in the snippet below, a blocking write into fd won't magically allow a fiber to preempt and switch to another fiber. No, the whole thread will be blocked.

...
write(fd, buf, 1000000);

...
pthread_mutex_lock(...);

Similarly, with a pthread_mutex_lock call, the whole thread might be blocked, wasting precious CPU time.. Therefore, the Dragonfly code uses fiber-friendly primitives for I/O, communication, and coordination. These primitives are supplied by the helio and Boost.Fibers libraries.

Life of a command request Copy Chapter

This section explains how Dragonfly handles a command in the context of shared-nothing architecture. In most architectures used today, multi-threaded servers use mutex locks to protect their data structures, but Dragonfly does not. Why is this?

Inter-thread interactions in Dragonfly occur only via passing messages from thread to thread. For example, consider the following sequence diagram of handling a SET request:

@startuml

actor       User       as A1
boundary    connection  as B1
entity      "Shard K"   as E1
A1 ->  B1 : SET KEY VAL
B1 -> E1 : SET KEY VAL / k = HASH(KEY) % N
E1 -> B1 : OK
B1 -> A1 : Response

@enduml

Here, a connection fiber resides in a thread different from one that handles the KEY entity. We use hashing to decide which shard owns which key.

Another way to think of this flow is that a connection fiber serves as a coordinator for issuing transactional commands to other threads. In this simple example, the external "SET" command requires a single message passed from the coordinator to the destination shard thread. When we think of the Dragonfly model in the context of a single command request, I prefer to use the following diagram instead of the one above.

Here, a coordinator (or connection fiber) might even reside on one of the threads that coincidently owns one of the shards. However, it is easier to think of it as a separate entity that never directly accesses any shard data.

The coordinator serves as a virtualization layer that hides all the complexity of talking to multiple shards. It employs start-of-the-art algorithms to provide atomicity (and strict serializability) semantics for multi-key commands like "mset, mget, and blpop." It also offers strict serializability for Lua scripts and multi-command transactions.

Hiding such complexity is valuable to the end customer, but it comes with some CPU and latency costs. We believe the trade-off is worthwhile given the value that Dragonfly provides.

If you want to deep dive into Dragonfly architecture without the complexities of transactional code, it's worth checking Midi Redis,
which implements a toy backend supporting PING, SET, and GET commands.

In fact, Dragonfly grew from that project; they share a common commit history.

By the way, to learn how to build even simpler TCP backends than midi-redis, helio library provides sample backends like these: echo_server and ping_iouring_server.cc. These backends reach millions of QPS on multi-core servers much like Dragonfly and midi-redis do.

File: docs/differences.md Copy Chapter

Differences with Redis

String lengths, indices. Copy Chapter

String sizes are limited to 256MB.
Indices (say in GETRANGE and SETRANGE commands) should be signed 32 bit integers in range
[-2147483647, 2147483648].

String handling. Copy Section

SORT does not take any locale into account.

Expiry ranges. Copy Chapter

Expirations are limited to 8 years. For commands with millisecond precision like PEXPIRE or PSETEX,
expirations greater than 2^28ms are quietly rounded to the nearest second losing precision of less than 0.001%.

Lua Copy Chapter

We use lua 5.4.4 that has been released in 2022.
That means we also support lua integers.

File: docs/faq.md Copy Chapter

Dragonfly Frequently Asked Questions

• Dragonfly Frequently Asked Questions
  • What is the license model of Dragonfly? Is it an open source?
  • Can I use dragonfly in production?
  • We benchmarked Dragonfly and we have not reached 4M qps throughput as you advertised.
  • Dragonfly provides vertical scale, but we can achieve similar throughput with X nodes in a Redis cluster.
  • If only Dragonfly had this command I would use it for sure

What is the license model of Dragonfly? Is it an open source? Copy Chapter

Dragonfly is released under BSL 1.1 (Business Source License).
BSL 1.1 is considered to be "source available" license and it's not strictly open-source license.
We believe that a BSL 1.1 license is more permissive
than licenses like AGPL, and it will allow us to
provide a competitive commercial service using our technology. In general terms,
it means that Dragonfly's code is free to use and free to change as long as you do not sell services directly related to
Dragonfly or in-memory datastores.
We followed the trend of other technological companies like Elastic, Redis, MongoDB, Cockroach labs,
Redpanda Data to protect our rights to provide service and support for the software we are building.

Can I use dragonfly in production? Copy Chapter

License wise you are free to use dragonfly in your production as long as you do not provide Dragonfly as a managed service.
From a code maturity point of view, Dragonfly's code is covered with unit testing and the regression tests.
However as with any new software there are use cases that are hard to test and predict.
We advise you to run your own particular use case on dragonfly for a few days before considering production usage.

We benchmarked Dragonfly and we have not reached 4M qps throughput as you advertised. Copy Chapter

We conducted our experiments using a load-test generator called memtier_benchmark,
and we run benchmarks on AWS network-enhanced instance c6gn.16xlarge on recent Linux kernel versions.
Dragonfly might reach smaller throughput on other instances, but we would
still expect to reach around 1M+ qps on instances with 16-32 vCPUs.

Dragonfly provides vertical scale, but we can achieve similar throughput with X nodes in a Redis cluster. Copy Chapter

Dragonfly optimizes the use of underlying hardware, allowing it to run efficiently on instances as small as 8GB,
and scale vertically to large 2TB machines with 128 cores. This versatility significantly
reduces the complexity of running cluster workloads on a single node, saving hardware resources and costs.
More importantly, it diminishes the total cost
of ownership associated with managing multi-node clusters. In contrast, Redis in cluster
mode imposes limitations on multi-key and transactional operations, whereas Dragonfly maintains
the same semantics as a single-node Redis system.
Furthermore, scaling out horizontally with small instances can lead to instability
in production environments.
We believe that large-scale deployments of in-memory stores require both vertical and horizontal scaling,
which is not efficiently achievable with an in-memory store like Redis.

If only Dragonfly had this command I would use it for sure Copy Chapter

Dragonfly implements ~190 Redis commands which we think represent a good coverage of the market.
However this is not based on empirical data. Having said that, if you have commands that are not covered,
please feel free to open an issue for that or vote for an existing issue.
We will do our best to prioritise those commands according to their popularity.