Dragonfly makes B+ tree sorted sets the default

A sorted set has to support two different kinds of lookup. Applications ask for a member's score, but they also ask for members in score order or at a particular rank. Dragonfly's October 16 release changes the default implementation behind those operations to its own B+ tree design.

The release also announces BullMQ support and describes the Streams and ACL APIs as complete. These additions address compatibility around the datastore, while the sorted-set change replaces internal machinery beneath existing commands. The combination is relevant because a replacement engine needs both the expected operations and data structures suited to the workload.

I am drawn to Dragonfly's effort to use a single machine efficiently. Sorted sets are a useful test of that effort because a hash lookup alone cannot answer their ordering questions. The source shows how the implementation keeps member lookup separate from ordered traversal while sharing the stored objects between them.

Member lookup and ordering use different indexes

The sorted-map implementation contains a Dragonfly implementation with a ScoreMap and a ScoreTree. The map locates objects by member name. Its tree organizes those objects according to a comparator that first considers their numeric scores and then their member strings.

The score is stored alongside the member's string allocation. The tree receives a reference to that object, and comparison reads the stored score. This lets the two indexes answer different questions about the same member without requiring the tree to become a name-only lookup structure.

The comparator's secondary string comparison matters when two members have equal scores. Score alone does not define a complete ordering of distinct members. Using the member name to resolve ties supplies the stable ordering that ordered traversal needs.

A score lookup first finds the member in the map and returns the stored numeric value. A rank lookup finds the same object and asks the tree for its rank. The implementation computes reverse rank from the collection size and the forward rank. These paths make the division of responsibility visible in the code.

The public sorted-map header exposes operations for score ranges, lexical ranges, deletion, and iteration. Both the older Redis-backed implementation and the Dragonfly implementation sit behind this interface. That arrangement permits the internal choice to change while command handlers retain a common set of operations.

Updating a score changes tree position

An update to an existing member cannot change its stored score without also maintaining the ordered index. In the Dragonfly add path, the implementation deletes the object from the tree, updates its score, and reinserts it. The member map still identifies the same logical member.

Conditional add behaviour remains part of this path. The code handles insertion-only and update-only flags before changing the collection. For increment operations, it adds the supplied amount to the existing score and rejects an invalid resulting number. Replacing the index does not remove these command-level conditions.

A simple sequence illustrates the operations whose shared state must remain consistent:

redis-cli ZADD scores 10 alice 20 bob
redis-cli ZSCORE scores alice
redis-cli ZRANK scores alice
redis-cli ZADD scores 30 alice
redis-cli ZRANGE scores 0 -1 WITHSCORES

After the update, the score lookup and ordered view must agree about Alice's new score. The example does not require knowledge of the internal tree layout. That is the purpose of retaining the command interface while replacing the implementation.

Deletion has a corresponding consistency requirement. Removing an object from one index while leaving it in the other would make name lookup and ordered traversal disagree. The paired structures therefore introduce bookkeeping work in exchange for supporting both access patterns efficiently.

Rank queries need subtree information

The B+ tree implementation supports both locating an item and navigating to a rank. It tracks subtree counts and updates them during insertion and structural changes. A rank is consequently more than the position within one leaf.

The rank-navigation code examines child subtree counts while descending. It subtracts the portions that precede the requested position and continues into the relevant child. This avoids requiring the caller to start at the smallest member and visit every earlier element merely to reach an offset.

Insertion into a full leaf first attempts rebalancing through the parent. If that cannot handle the new item, the implementation splits the node and propagates a separator upward. A full parent can itself require rebalancing or splitting. The tree grows a new root when the propagation reaches the top.

Each structural change also has to preserve subtree counts. The implementation includes explicit count updates when elements move between sibling nodes and when a new child enters a parent. This is the additional work that makes order-statistic operations possible alongside ordinary sorted lookup.

The source also exposes paths to the first item greater than or equal to a search key and the last item less than or equal to it. Sorted-map range operations use these boundaries and then advance or reverse the path. Numeric bounds and iteration therefore compose into the score-range behaviour exposed by commands.

I find these mechanisms more informative than a blanket performance comparison. The tree's grouping of records changes allocation and traversal behaviour, while subtree metadata directly supports rank queries. The resulting advantage depends on which sorted-set operations dominate the workload.

Small sorted sets retain another representation

The default-switch patch changes use_zset_tree to true. It also restores the default maximum listpack entry count for sorted sets to 128. The patch explanation ties that threshold change to listpack optimizations already made by the author.

This means the release does not force every tiny sorted set into a tree. Compact listpack storage remains part of the design, and the tree replaces the older expanded representation when that representation is needed. Collection size and member characteristics still influence the representation selected by the server.

The same patch retains a separate maximum listpack value size. Entry count alone is therefore not a complete description of when a compact representation remains suitable. A collection with few large members can present a different storage problem from one with the same number of short members.

The release notes mention listpack memory and performance work alongside the tree change. Those changes address different sizes of collection. Explaining them together avoids attributing every sorted-set improvement to the B+ tree, including operations that continue to use compact storage.

Streams gain recovery and acknowledgment operations

The stream-command registration now includes XPENDING, XCLAIM, XACK, and XAUTOCLAIM alongside group reads. These commands extend the lifecycle beyond appending a record and reading it once.

The acknowledgment handler parses supplied entry IDs and executes the operation on the stream's owning shard. Automatic claiming parses a group, consumer, minimum idle interval, and starting ID. It can return records or only IDs, and its reply includes a continuation position and deleted IDs.

Those details matter to queue consumers because processing and completion are separate observations. A reader can receive work without having completed it. Pending inspection and claim operations provide ways to inspect or transfer that outstanding work within the stream's consumer-group model.

The release's BullMQ support is an explicit maintainer claim. The concrete command additions explain some of the datastore interactions behind broader queue compatibility, without implying that any single stream command establishes all of a framework's behaviour.

ACL configuration gains a file lifecycle

The ACL implementation now has an aclfile option and save and load handlers. Saving requires a configured path, writes the registry representation, and reports file-open, write, or close failures. Loading parses the file before applying user updates.

This supplies a configuration lifecycle beyond process-local user creation. The implementation also adds category inspection, individual-user inspection, logging, and a dry-run command. These operations make the configured policy inspectable in ways that the initial user-management commands could not provide.

The announcement changes HTTP authentication's default username to default and removes authentication from the metrics endpoint. Those are specific externally visible behaviours within the broader ACL work. They remain relevant even though an application continues to issue the same data commands.

Version 1.11 combines that operational completion with an internal sorted-set default change. The B+ tree and member map preserve separate access paths to shared objects, while listpacks remain relevant for compact collections. Streams and ACLs acquire commands that address work recovery and configuration management beyond the first successful request.