mirror of
https://github.com/valkey-io/valkey.git
synced 2026-07-28 20:23:58 -04:00
33bfac37ba
By default, when the number of elements in a zset exceeds 128, the
underlying data structure adopts a skiplist. We can reduce memory usage
by embedding elements into the skiplist nodes. Change the `zskiplistNode`
memory layout as follows:
```
Before
+-------------+
+-----> | element-sds |
| +-------------+
|
+------------------+-------+------------------+---------+-----+---------+
| element--pointer | score | backward-pointer | level-0 | ... | level-N |
+------------------+-------+------------------+---------+-----+---------+
After
+-------+------------------+---------+-----+---------+-------------+
+ score | backward-pointer | level-0 | ... | level-N | element-sds |
+-------+------------------+---------+-----+---------+-------------+
```
Before the embedded SDS representation, we include one byte representing
the size of the SDS header, i.e. the offset into the SDS representation
where that actual string starts.
The memory saving is therefore one pointer minus one byte = 7 bytes per
element, regardless of other factors such as element size or number of
elements.
### Benchmark step
I generated the test data using the following lua script && cli command.
And check memory usage using the `info` command.
**lua script**
```
local start_idx = tonumber(ARGV[1])
local end_idx = tonumber(ARGV[2])
local elem_count = tonumber(ARGV[3])
for i = start_idx, end_idx do
local key = "zset:" .. string.format("%012d", i)
local members = {}
for j = 0, elem_count - 1 do
table.insert(members, j)
table.insert(members, "member:" .. j)
end
redis.call("ZADD", key, unpack(members))
end
return "OK: Created " .. (end_idx - start_idx + 1) .. " zsets"
```
**valkey-cli command**
`valkey-cli EVAL "$(catcreate_zsets.lua)" 0 0 100000
${ZSET_ELEMENT_NUM}`
### Benchmark result
|number of elements in a zset | memory usage before optimization |
memory usage after optimization | change |
|-------|-------|-------|-------|
| 129 | 1047MB | 943MB | -9.9% |
| 256 | 2010MB| 1803MB| -10.3%|
| 512 | 3904MB|3483MB| -10.8%|
---------
Signed-off-by: chzhoo <[email protected]>
Co-authored-by: Viktor Söderqvist <[email protected]>
110 lines
3.8 KiB
Tcl
110 lines
3.8 KiB
Tcl
set testmodule [file normalize tests/modules/zset.so]
|
|
|
|
start_server {tags {"modules"}} {
|
|
r module load $testmodule
|
|
|
|
test {Module zset rem} {
|
|
r del k
|
|
r zadd k 100 hello 200 world
|
|
assert_equal 1 [r zset.rem k hello]
|
|
assert_equal 0 [r zset.rem k hello]
|
|
assert_equal 1 [r exists k]
|
|
# Check that removing the last element deletes the key
|
|
assert_equal 1 [r zset.rem k world]
|
|
assert_equal 0 [r exists k]
|
|
}
|
|
|
|
test {Module zset add} {
|
|
r del k
|
|
# Check that failure does not create empty key
|
|
assert_error "ERR ZsetAdd failed" {r zset.add k nan hello}
|
|
assert_equal 0 [r exists k]
|
|
|
|
r zset.add k 100 hello
|
|
assert_equal {hello 100} [r zrange k 0 -1 withscores]
|
|
}
|
|
|
|
test {Module zset incrby} {
|
|
r del k
|
|
# Check that failure does not create empty key
|
|
assert_error "ERR ZsetIncrby failed" {r zset.incrby k hello nan}
|
|
assert_equal 0 [r exists k]
|
|
|
|
r zset.incrby k hello 100
|
|
assert_equal {hello 100} [r zrange k 0 -1 withscores]
|
|
}
|
|
|
|
test {Module zset rangebylex} {
|
|
# Should give wrong arity error
|
|
assert_error "ERR wrong number of arguments*" {r zset.rangebylex}
|
|
assert_error "ERR wrong number of arguments*" {r zset.revrangebylex}
|
|
|
|
# Should give wrong type error
|
|
r del k
|
|
r set k v
|
|
assert_error "WRONGTYPE Operation against a key*" {r zset.rangebylex k - +}
|
|
|
|
# Should give invalid range error
|
|
r del k
|
|
r zadd k 0 ele
|
|
assert_error "invalid range" {r zset.rangebylex k - a}
|
|
assert_error "invalid range" {r zset.revrangebylex k - a}
|
|
|
|
# Check if the data structure of the sorted set is skiplist
|
|
r del k
|
|
r config set zset-max-listpack-entries 2
|
|
r config set zset-max-listpack-value 64
|
|
for {set i 0} {$i < 4} {incr i} {
|
|
r zadd k 0 "ele$i"
|
|
}
|
|
assert_equal {ele0 ele1 ele2 ele3} [r zset.rangebylex k - +]
|
|
assert_equal {ele3 ele2 ele1 ele0} [r zset.revrangebylex k - +]
|
|
assert_equal {ele1 ele2} [r zset.rangebylex k "(ele0" "(ele3"]
|
|
assert_equal {ele2 ele1} [r zset.revrangebylex k "(ele0" "(ele3"]
|
|
|
|
# Check if the data structure of the sorted set is listpack
|
|
r del k
|
|
r config set zset-max-listpack-entries 128
|
|
r config set zset-max-listpack-value 64
|
|
for {set i 0} {$i < 4} {incr i} {
|
|
r zadd k 0 "ele$i"
|
|
}
|
|
assert_equal {ele0 ele1 ele2 ele3} [r zset.rangebylex k - +]
|
|
assert_equal {ele3 ele2 ele1 ele0} [r zset.revrangebylex k - +]
|
|
assert_equal {ele1 ele2} [r zset.rangebylex k "(ele0" "(ele3"]
|
|
assert_equal {ele2 ele1} [r zset.revrangebylex k "(ele0" "(ele3"]
|
|
}
|
|
|
|
test {Module zset members} {
|
|
# Should give wrong arity error
|
|
assert_error "ERR wrong number of arguments*" {r zset.members}
|
|
|
|
# Should give wrong type error
|
|
r del k
|
|
r set k v
|
|
assert_error "WRONGTYPE Operation against a key*" {r zset.members k}
|
|
|
|
# Check if the data structure of the sorted set is skiplist
|
|
r del k
|
|
r config set zset-max-listpack-entries 2
|
|
r config set zset-max-listpack-value 64
|
|
for {set i 0} {$i < 4} {incr i} {
|
|
r zadd k 0 "ele$i"
|
|
}
|
|
assert_equal {ele0 ele1 ele2 ele3} [lsort [r zset.members k]]
|
|
|
|
# Check if the data structure of the sorted set is listpack
|
|
r del k
|
|
r config set zset-max-listpack-entries 128
|
|
r config set zset-max-listpack-value 64
|
|
for {set i 0} {$i < 4} {incr i} {
|
|
r zadd k 0 "ele$i"
|
|
}
|
|
assert_equal {ele0 ele1 ele2 ele3} [lsort [r zset.members k]]
|
|
}
|
|
|
|
test "Unload the module - zset" {
|
|
assert_equal {OK} [r module unload zset]
|
|
}
|
|
}
|