🪢 A fast native data type for manipulating large strings in Redis
A fast and versatile rope data type for large strings in Redis, distributed as a native module.
Ropes are a more efficient data structure for large strings (indexed sequences of bytes). Unlike ordinary strings, ropes let you do some operations up to exponentially faster than their counterparts:
The ropes in this module are backed by splay trees, which are a self-adjusting data structure that has logarithmic amortized worst-case performance, while recently-accessed indices are also quick to access in subsequent operations. Each splay tree node stores between 64 and 127 bytes of data.
Some data structures tend to be too theoretical. This module attempts to provide practical guarantees:
Ropes are particularly good at speeding up complex operations on large strings. The following graph shows how performance for ropes scales on 1000 random string SPLICE operations, compared to an equivalent implementation with ordinary Redis strings. (These operations are pipelined to better measure their CPU performance; see the benchmark code in Rust.)
For small strings, there is not much difference. However, each time the length of the string doubles, the basic type gets exponentially slower because it does not scale to large data as well, while the redis-rope
type provided by this module stays fast.
The redis-rope
module has been tested with Redis 7.0+. To install, download the appropriate shared library libredisrope.so
for your platform and load the module from the command line:
redis-server --loadmodule path/to/libredisrope.so
Or by configuration directive in redis.conf
:
loadmodule path/to/libredisrope.so
Or from the Redis CLI, using the MODULE LOAD
command:
> MODULE LOAD path/to/libredisrope.so
We will build shared libraries for each version of redis-rope on Linux and macOS, using x86-64 and ARM64 architectures. These files are small, portable artifacts and are available on the releases page.
redis-rope
is written in Zig, which makes building the module from source and cross-compiling very fast (<10 seconds). This is a reasonable option, especially if you want to try out the latest version of the module from the main branch.
zig build -Drelease-fast
This requires Zig 0.9, which you can install here. The project can also be built targeting different platforms with a command-line flag, for example:
zig build -Drelease-fast -Dtarget=x86_64-linux-gnu
zig build -Drelease-fast -Dtarget=aarch64-linux-gnu
Build outputs are located in the zig-out/lib
folder.
These are fairly straightfoward: get the length of the rope, any individual byte, or a range of bytes as a string.
ROPE.LEN
key: O(1)
ROPE.GET
key index: O(log N)
ROPE.GETRANGE
key start stop: O(log N + K), where K is the length of the returned stringAll operations support negative indices, which count backward from the end of the rope.
The append and insert operations push data to the end of the rope, or at an index in the middle of the rope, while the delrange operation deletes a byte range from the rope.
The splice operation is the most complicated and powerful. Given the keys of two ropes, source
and destination
, it appends destination
to the end of source
and deletes destination
. If start
is provided, the string is inserted at that index rather than appended to the end. If stop
is provided, then the range of bytes from start
to stop
is also deleted from source
and swapped with the rope at destination
.
ROPE.APPEND
key str: O(1)
ROPE.INSERT
key index str: O(log N), or O(1) if index is 0ROPE.DELRANGE
key start stop: O(log N)
ROPE.SPLICE
source destination [start [stop]]: O(log N)
Despite being quite powerful, each operation above takes logarithmic time, so they will remain fast for arbitrarily long ropes.
The rope data type supports exact calculations from the MEMORY USAGE
command, both methods of Redis persistence using RDB and AOF, asynchronous DEL
operations, and primary-replica replication.
redis:6379> ROPE.APPEND key1 "hello"
(integer) 5
redis:6379> ROPE.LEN key1
(integer) 5
redis:6379> ROPE.GET key1 2
"l"
redis:6379> ROPE.APPEND key1 " world!"
(integer) 12
redis:6379> ROPE.GETRANGE key1 0 -1
"hello world!"
redis:6379> ROPE.INSERT key1 6 "rope "
(integer) 17
redis:6379> ROPE.GETRANGE key1 0 -1
"hello rope world!"
redis:6379> ROPE.DELRANGE key1 -9 -3
(integer) 10
redis:6379> ROPE.GETRANGE key1 0 -1
"hello rod!"
redis:6379> ROPE.APPEND key2 "goodbye"
(integer) 7
redis:6379> ROPE.SPLICE key1 key2 0 4
1) (integer) 12
2) (integer) 5
redis:6379> ROPE.GETRANGE key1 0 -1
"goodbye rod!"
redis:6379> ROPE.GETRANGE key2 0 -1
"hello"
redis:6379> ROPE.SPLICE key1 key2
1) (integer) 17
2) (integer) 0
redis:6379> ROPE.GETRANGE key1 0 -1
"goodbye rod!hello"
redis:6379> MEMORY USAGE key1
(integer) 128
redis:6379> GET key2
(nil)
redis:6379> DEL key1
(integer) 1
redis:6379> GET key1
(nil)
Created by Eric Zhang (@ekzhang1). Licensed under the MIT license.
Thanks to antirez for creating Redis and Sleator & Tarjan for discovering splay trees.