Files
1ac3bc07d6 Implement the new Redis Array type (#15162)
# Redis Array

For years, Redis has been missing a real indexed data structure for the
use cases where the index and the spatial relationship of elements are
semantic. Hashes give you random lookups, but you have to store an index
as a key, and have no range visibility. Lists give you appending and
trimming, but what is in the middle remains hard to access. Streams give
you append-only events, which is another (useful, indeed) beast. None of
these is what you want when the *position itself* has business meaning —
slot 37, step 4, row 18552, day from 2934 to 2949, file line 11, 12, 15
and so forth. And, all those types, for different reasons, are all
suboptimal when you want a **ring buffer** able to store the latest N
observed samples of something.

Up to now, users found ways (they always do \o/) using the fact that the
data structures that are obvious in this universe are also extremely
powerful, if well implemented. But this forces compromises. Arrays
handle these index-first requirements natively, and usually with much
better memory and CPU usage than the workarounds. If the use case is the
right one, Arrays often provide much better space, time and usability at
the same time.

## Internal encoding

1. When dense, an Array is essentially a more fancy C array. You don't
pay anything for storing the index.
2. Yet, instead of going really flat, arrays are sliced into
4096-element slices, and each slice, when it contains just a few
elements, uses a special sparse encoding. When a slice is empty it's
just a `NULL` stored in the directory.
3. Small ints, floats, and short strings are pointer-tagged, so they
cost zero additional memory beyond the pointer slot itself.
4. When very sparse, a super-directory of windowed directories is used.
This allows the data type to be safe, instead of exhibiting pathological
space or time behavior. This representation is only triggered when there
are more than 8 million elements or very high indexes set.

## Use cases

Arrays are mostly stateless if not for the fact that each array
remembers the index of the latest added item, allowing `ARINSERT` and
`ARRING` to work properly. Otherwise it is a set/get at this index game,
with solid support for both setting / getting ranges, server-side
scanning, returning only populated elements in a time which is
proportional not to the range size, but to the population size.

A few concrete examples, that may work as mental models for the set of
problems that are similar to them (from the POV of the data modeling).

**Thermometer.** A sensor reporting once per minute, with gaps:

```
ARSET       temp:room12:day7 123 22.3
ARGETRANGE  temp:room12:day7 600 660     # the 10:00–11:00 window, with NULLs
ARSCAN      temp:room12:day7 600 660     # only populated elements
AROP        temp:room12:day7 0 1439 MAX  # peak of the day, server-side
```

Missing minutes cost little to nothing. Numeric aggregation runs inside
Redis. Telemetry, IoT, meter readings, KPI rollups.

**Calendar.** A clinic with 96 fifteen-minute slots per day:

```
ARSET       sched:room12:day 32 booking:991
ARSCAN      sched:room12:day 0 95      # only occupied slots
ARGETRANGE  sched:room12:day 48 63     # the afternoon full view to render
```

The slot number is the business key in this case. Room booking, parking
spaces, warehouse bins, lockers, ...

**Ring buffer.** ARRING replaces the classic LPUSH+LTRIM pattern.
Imagine remote `dmesg`.

```
ARRING       machine:123 200 "[141087.430123]: arm_cpu_init(): cpu 14 online" # Capped to 200 entries
ARLASTITEMS  machine:123 50 REV       # 50 newest first
```

Faster than LPUSH+LTRIM, keep indexed access to past elements. Last-N
alarms, recent fraud scores, access history, remote logs, device events.
Ok here the use cases are mainly the ones of the old pattern: it is just
a better fit and allows to access random items in the middle, aggregate
server-side, and so forth.

**Workflow.** Step number is the index, value is the status. Gaps are
meaningful:

```
ARSET       claim:99172 0 received
ARSET       claim:99172 3 waiting:reviewer42
ARSET       claim:99172 5 approved
ARGETRANGE  claim:99172 0 5     # full workflow view, with NULLs for missing steps
ARSCAN      claim:99172 0 5     # only steps that have a state
ARCOUNT     claim:99172         # number of recorded steps
ARLEN       claim:99172         # highest reached step + 1
```

**Skills knowledge base for agents.** Arrays are good at representing /
grepping into Markdown files:

```
ARSET   skill:metal_gpu 0 "...."
ARSET   skill:metal_gpu 1 "...."
ARSET   skill:metal_gpu 2 "...."
ARGREP  skill:metal_gpu - + RE "M3|M4" WITHVALUES
```

ARGREP has EXACT, MATCH, GLOB, RE, you can have multiple predicates, can
select AND or OR behavior.

**Bulk import results.** Sparse row annotations over millions of rows /
CSV / ...:

```
ARSET  import:job551 18552 ERR:bad_email
ARSCAN import:job551 0 1000000        # Provides only rows that have something
```

## TLDR

If the position is part of the meaning, use an Array. If you want to
aggregate or grep remotely, use an Array. Feedback welcome :)

---------

Co-authored-by: debing.sun <[email protected]>
Co-authored-by: Shubham S Taple <[email protected]>
Co-authored-by: Yuan Wang <[email protected]>
Co-authored-by: Marc Gravell <[email protected]>
2026-05-14 00:56:44 +08:00

297 lines
10 KiB
Tcl

# This unit has the potential to create huge .reqres files, causing log-req-res-validator.py to run for a very long time...
# Since this unit doesn't do anything worth validating, reply_schema-wise, we decided to skip it
start_server {tags {"aofrw external:skip logreqres:skip"} overrides {save {}}} {
# Enable the AOF
r config set appendonly yes
r config set auto-aof-rewrite-percentage 0 ; # Disable auto-rewrite.
waitForBgrewriteaof r
foreach rdbpre {yes no} {
r config set aof-use-rdb-preamble $rdbpre
test "AOF rewrite during write load: RDB preamble=$rdbpre" {
# Start a write load for 10 seconds
set master [srv 0 client]
set master_host [srv 0 host]
set master_port [srv 0 port]
set load_handle0 [start_write_load $master_host $master_port 10]
set load_handle1 [start_write_load $master_host $master_port 10]
set load_handle2 [start_write_load $master_host $master_port 10]
set load_handle3 [start_write_load $master_host $master_port 10]
set load_handle4 [start_write_load $master_host $master_port 10]
# Make sure the instance is really receiving data
wait_for_condition 50 100 {
[r dbsize] > 0
} else {
fail "No write load detected."
}
# After 3 seconds, start a rewrite, while the write load is still
# active.
after 3000
r bgrewriteaof
waitForBgrewriteaof r
# Let it run a bit more so that we'll append some data to the new
# AOF.
after 1000
# Stop the processes generating the load if they are still active
stop_write_load $load_handle0
stop_write_load $load_handle1
stop_write_load $load_handle2
stop_write_load $load_handle3
stop_write_load $load_handle4
# Make sure no more commands processed, before taking debug digest
wait_load_handlers_disconnected
# Get the data set digest
set d1 [debug_digest]
# Load the AOF
r debug loadaof
set d2 [debug_digest]
# Make sure they are the same
assert {$d1 eq $d2}
}
}
}
start_server {tags {"aofrw external:skip debug_defrag:skip"} overrides {aof-use-rdb-preamble no}} {
test {Turning off AOF kills the background writing child if any} {
r config set appendonly yes
waitForBgrewriteaof r
# start a slow AOFRW
r set k v
r config set rdb-key-save-delay 10000000
r bgrewriteaof
# disable AOF and wait for the child to be killed
r config set appendonly no
wait_for_condition 50 100 {
[string match {*Killing*AOF*child*} [exec tail -5 < [srv 0 stdout]]]
} else {
fail "Can't find 'Killing AOF child' into recent logs"
}
r config set rdb-key-save-delay 0
}
foreach d {string int} {
foreach e {listpack quicklist} {
test "AOF rewrite of list with $e encoding, $d data" {
r flushall
if {$e eq {listpack}} {
r config set list-max-listpack-size -2
set len 10
} else {
r config set list-max-listpack-size 10
set len 1000
}
for {set j 0} {$j < $len} {incr j} {
if {$d eq {string}} {
set data [randstring 0 16 alpha]
} else {
set data [randomInt 4000000000]
}
r lpush key $data
}
assert_equal [r object encoding key] $e
set d1 [debug_digest]
r bgrewriteaof
waitForBgrewriteaof r
r debug loadaof
set d2 [debug_digest]
if {$d1 ne $d2} {
error "assertion:$d1 is not equal to $d2"
}
}
}
}
foreach d {string int} {
foreach e {intset hashtable} {
test "AOF rewrite of set with $e encoding, $d data" {
r flushall
if {$e eq {intset}} {set len 10} else {set len 1000}
for {set j 0} {$j < $len} {incr j} {
if {$d eq {string}} {
set data [randstring 0 16 alpha]
} else {
set data [randomInt 4000000000]
}
r sadd key $data
}
if {$d ne {string}} {
assert_equal [r object encoding key] $e
}
set d1 [debug_digest]
r bgrewriteaof
waitForBgrewriteaof r
r debug loadaof
set d2 [debug_digest]
if {$d1 ne $d2} {
error "assertion:$d1 is not equal to $d2"
}
}
}
}
foreach d {string int} {
foreach e {listpack hashtable} {
test "AOF rewrite of hash with $e encoding, $d data" {
r flushall
if {$e eq {listpack}} {set len 10} else {set len 1000}
for {set j 0} {$j < $len} {incr j} {
if {$d eq {string}} {
set data [randstring 0 16 alpha]
} else {
set data [randomInt 4000000000]
}
r hset key $data $data
}
assert_equal [r object encoding key] $e
set d1 [debug_digest]
r bgrewriteaof
waitForBgrewriteaof r
r debug loadaof
set d2 [debug_digest]
if {$d1 ne $d2} {
error "assertion:$d1 is not equal to $d2"
}
}
}
}
foreach d {string int} {
foreach e {listpack skiplist} {
test "AOF rewrite of zset with $e encoding, $d data" {
r flushall
if {$e eq {listpack}} {set len 10} else {set len 1000}
for {set j 0} {$j < $len} {incr j} {
if {$d eq {string}} {
set data [randstring 0 16 alpha]
} else {
set data [randomInt 4000000000]
}
r zadd key [expr rand()] $data
}
assert_equal [r object encoding key] $e
set d1 [debug_digest]
r bgrewriteaof
waitForBgrewriteaof r
r debug loadaof
set d2 [debug_digest]
if {$d1 ne $d2} {
error "assertion:$d1 is not equal to $d2"
}
}
}
}
test "AOF rewrite functions" {
r flushall
r FUNCTION LOAD {#!lua name=test
redis.register_function('test', function() return 1 end)
}
r bgrewriteaof
waitForBgrewriteaof r
r function flush
r debug loadaof
assert_equal [r fcall test 0] 1
r FUNCTION LIST
} {{library_name test engine LUA functions {{name test description {} flags {}}}}}
# Array AOF rewrite tests
test "AOF rewrite of array with mixed value types" {
r flushall
# Create array with various value types
r arset myarray 0 12345 ;# int
r arset myarray 1 "hello" ;# small string
r arset myarray 2 3.14159 ;# float
r arset myarray 100 [string repeat x 50] ;# large string
r arset myarray 10000 "sparse" ;# sparse index
set d1 [debug_digest]
r bgrewriteaof
waitForBgrewriteaof r
r debug loadaof
set d2 [debug_digest]
if {$d1 ne $d2} {
error "assertion:$d1 is not equal to $d2"
}
}
test "AOF rewrite of array with insert_idx (circular buffer)" {
r flushall
# Create circular buffer using ARRING
for {set i 0} {$i < 25} {incr i} {
r arring myarray 10 "v$i"
}
# insert_idx should be 4 ((25-1) % 10 = 4)
set next_before [r arnext myarray]
set d1 [debug_digest]
r bgrewriteaof
waitForBgrewriteaof r
r debug loadaof
set d2 [debug_digest]
if {$d1 ne $d2} {
error "assertion:$d1 is not equal to $d2"
}
# Verify insert_idx preserved
assert_equal $next_before [r arnext myarray]
# Continue inserting - should continue from correct position
set new_idx [r arring myarray 10 "after_aof"]
assert_equal $next_before $new_idx
}
test "AOF rewrite of array spanning multiple slices" {
r flushall
# Create array across multiple slices (slice_size = 4096)
for {set slice 0} {$slice < 5} {incr slice} {
set base [expr {$slice * 4096}]
for {set i 0} {$i < 20} {incr i} {
r arset myarray [expr {$base + $i * 100}] "s${slice}_v$i"
}
}
set d1 [debug_digest]
r bgrewriteaof
waitForBgrewriteaof r
r debug loadaof
set d2 [debug_digest]
if {$d1 ne $d2} {
error "assertion:$d1 is not equal to $d2"
}
}
test {BGREWRITEAOF is delayed if BGSAVE is in progress} {
r flushall
r set k v
r config set rdb-key-save-delay 10000000
r bgsave
assert_match {*scheduled*} [r bgrewriteaof]
assert_equal [s aof_rewrite_scheduled] 1
r config set rdb-key-save-delay 0
catch {exec kill -9 [get_child_pid 0]}
while {[s aof_rewrite_scheduled] eq 1} {
after 100
}
}
test {BGREWRITEAOF is refused if already in progress} {
r config set aof-use-rdb-preamble yes
r config set rdb-key-save-delay 10000000
catch {
r bgrewriteaof
r bgrewriteaof
} e
assert_match {*ERR*already*} $e
r config set rdb-key-save-delay 0
catch {exec kill -9 [get_child_pid 0]}
}
}