Module array 

A sparse array: a sequence indexed by a u64, with holes.

This is the type behind the AR* commands Redis added in 8.9, and it is the only collection here whose index is unsigned. A list is indexed from either end and -1 is the last element. An array is indexed by position in a space that runs to 2^64 - 2, so -1 is not the end of anything, it is an error, and most of that space is empty at any moment.

  slices, sorted by id, binary searched
+---------+---------+-------------------+---------+
| id 0    | id 7    |        ...        | id 9e12 |
| sparse  | dense   |                   | sparse  |
+---------+---------+-------------------+---------+
     \                                        /
      \--- offsets and words -----------------/
                    |
            +-------------------------------+
            | one blob per array, for the   |
            | values too long to inline     |
            +-------------------------------+

Two numbers that are not the same number

Array::len is the highest populated index plus one and Array::count is how many indices are populated. ARSET k 1000000 x gives a length of a million and one and a count of one. Every other collection here has one number for both and it is worth saying out loud, because a caller that reaches for the wrong one gets an answer rather than an error.

Where the slices live

Redis keeps a flat directory of slice pointers indexed by slice id, and then a second structure over that for when the ids get far apart, because a flat array indexed by idx >> 12 is nine billion entries for an index of nine trillion. Here it is one Vec of (id, slice) kept sorted and binary searched, which covers the whole index space in one structure with no second mode to get wrong, and costs a handful of compares on a get instead of one load. A key with a thousand slices is ten compares, and a key with a thousand slices is four million elements, so the compares are noise next to what the caller is doing with the data.

Where the values live

A value of eight bytes or more is a slice of one blob owned by the array, and everything shorter is inlined in the word itself. Redis heap allocates each of those, paying a malloc header and the rounding on every one. One blob per key pays the bytes and nothing else, at the cost of having to compact when enough of it is dead. See Word for the four things a word can be.

Structs

Array

A sparse array of values, indexed by a u64.

Info

What ARINFO reports, which is the shape of the array and not its contents.

Short

A string short enough that it was stored inside the word.

Enums

Element

What is stored at one index, in whichever form it was worth keeping.

Constants

BLOB_TOO_LONG

The message when one key’s long values pass four gigabytes in total.

ELEMENT_MAX

Room for the longest text an Element can turn into.

INDEX_MAX

The largest index an array will accept.

INSERT_OVERFLOW

What ARINSERT says when the cursor has nowhere left to go.

SLICE_SIZE

How many indices one slice covers.

VALUE_TOO_LONG

The message when one value on its own passes a gigabyte.