Redis 4.0.8 fixes a cluster crash in radix-tree deletion

Deleting a key in Redis Cluster also updates an index that maps hash slots to keys. Redis 4.0.8 fixes an out-of-bounds read in the radix tree supporting that index. Most memory layouts conceal the error because the extra word remains readable. At the edge of a mapped memory region, the same deletion can crash the process.

The February 2 release entry assigns critical urgency specifically to Redis Cluster users. The version-pinned release notes say this patch addresses a single critical bug and gives other users no reason to upgrade for this change. That scope matters. The relevant distinction is whether the server maintains cluster key-slot tracking, not whether the application uses a complicated Redis value.

I like Redis's data structures because they provide concrete operations that applications can reason about. This bug illustrates the additional structures the server maintains on the application's behalf. Even a straightforward deletion depends on bookkeeping that is invisible in the command's result.

Cluster tracking uses keys with null values

The 4.0.8 database implementation shows how the slot index works. Redis computes the key's hash slot, prefixes the key name with two bytes representing that slot, and inserts the resulting byte sequence into slots_to_keys. It passes a null associated value to the radix-tree insertion.

That representation allows iteration beginning at a slot prefix. The code for finding keys in a slot seeks to the prefix and walks entries until their prefix changes. It reconstructs Redis key names by removing those first two bytes. A separate counter records how many keys belong to each slot.

Deletion removes the same prefixed byte sequence from the radix tree. This is why an application does not need to request a special tree operation to reach the bug. Ordinary key lifecycle operations update the cluster index as part of maintaining the database.

Using a null value is meaningful here. The byte sequence already contains the information the index needs. The radix tree can mark that sequence as a key without allocating a separate pointer for an associated non-null value. Deletion must respect that representation when calculating the node's length.

This differs from treating every marked key as a node with a stored value pointer. Both represent a key, but their physical layouts differ. The old deletion calculation failed to preserve that distinction.

The deletion length included a pointer that was absent

The radix-tree header defines separate iskey and isnull flags. It documents that the optional value pointer exists only when the node represents a key and its associated value is non-null. Children and their pointers share the variable-sized allocation with that optional data.

Removing a child requires moving the remaining bytes into the correct positions. The release's radix-tree update changes the length calculation in raxRemoveChild. Previously, the move included space for a value pointer whenever iskey was set. The correction includes that space only when iskey is set and isnull is clear.

The source therefore explains why the cluster index is a relevant caller. Its entries deliberately use null values. A key node in this index can legitimately have no value pointer at the end of its allocation. Reading one more pointer-sized region is outside the object even if the operating system permits the read.

The patch's condition is short, but the invariant is specific. A logical property, being a key, does not completely determine the stored layout. The associated-value state also participates in deciding which bytes exist.

The same commit updates other radix-tree behavior, including insertion and iterator handling. The release notes identify the deletion over-read as the critical cluster problem motivating the patch. Listing every changed function as a separate production defect would go beyond that account.

A rare crash is still a deterministic memory error

The notes explain that the failing memory access is a read. When it falls within readable memory, the process often continues. When the removed node lies at a mapped-area boundary, the invalid access can reach unreadable memory and terminate the server.

This makes a successful repetition of the logical deletion an incomplete reproduction strategy. The operation can be identical while allocator placement differs. Key contents and command ordering alone do not necessarily specify where the relevant node lands in the process address space.

The absence of a crash therefore says little about whether the calculation is correct. Comparing the header and patch provides a stronger argument. Previously, the length included bytes absent from the documented representation. The new length matches the flags that describe whether those bytes exist.

Slot maintenance also includes deleting all keys assigned to a slot. That implementation repeatedly obtains a key from the same radix index and calls database deletion. This connects administrative slot work to the same bookkeeping mechanism used by individual key removals.

I regard that source-level explanation as the reason to take the cluster upgrade guidance seriously. The project's urgency applies to an invalid access in normal bookkeeping, even though a particular instance may have run without reaching an unreadable boundary.

The correction existed but missed the stable branch

The release notes say the bug had been fixed in unstable about ten months earlier. That correction arrived in work associated with Streams and was mistakenly not backported to 4.0. Redis 4.0.8 brings the radix-tree update into the maintained release.

That history explains an otherwise surprising situation. A data-structure correction can exist in development while a stable branch retains the defect because the surrounding feature work looks unrelated to that branch. The shared dependency connects them. Cluster key tracking already uses the tree, even if the development commit also supports a different feature.

For cluster operators, the release's value is this specific backport. It corrects the byte-count calculation used during child removal in a structure that normal key deletion updates. The documented affected use is Redis Cluster, and the published upgrade urgency follows that use directly.