Optimize skiplist query efficiency by embedding the skiplist header

[chzhoo]

Description

Embedding the skiplist header reduces memory jumps, thus optimizing sorted set query speed.

// Before
typedef struct zskiplist {
        struct zskiplistNode *header, *tail;
        unsigned long length;
        int level; /* Height of the skiplist. */
} zskiplist;


// After
typedef struct zskiplist {
        unsigned long length; 
        struct zskiplistNode *tail;
        /* Since the span at level 0 is always 1 or 0 , 
         * this field is instead used for storing the height of the skiplist. */
        struct zskiplistLevel {
                struct zskiplistNode *forward;
                unsigned long span;
        } level[ZSKIPLIST_MAXLEVEL];
} zskiplist;

Benchmark

Step 1

Generate the test data using the following lua script and cli command

lua script

local start_idx = 0
local end_idx = tonumber(ARGV[1])
local elem_count = 129 -- Skiplist storage is activated when element count surpasses 128

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"

cli command

valkey-cli eval "$(cat load.lua)" 0 $ZSET_COUNT

Step 2

Run benchmark 5 times through the following command and select the peak value as the result

valkey-benchmark -n 5000000 -r $ZSET_COUNT --threads 2 zrange zset:__rand_int__ 0 0

Benchmark result

ZSET_COUNT	QPS before optimization	QPS after optimization	Performance Boost
10000	293875.62	294100.34	0.0%
40000	270241.03	277531.06	2.7%
100000	249775.20	259713.27	4.0%
1000000	224678.72	235260.91	4.7%
2000000	219751.23	229863.91	4.6%

Benchmark Env

CPU: AMD EPYC 9K65 192-Core Processor * 8 OS: Ubuntu Server 24.04 LTS 64bit Memory: 32GB VM: Tencent Cloud | SA9.2XLARGE32

[codecov[bot]]

Codecov Report

:x: Patch coverage is 95.68966% with 5 lines in your changes missing coverage. Please review. :white_check_mark: Project coverage is 72.42%. Comparing base (8ea7f13) to head (47dc765). :warning: Report is 7 commits behind head on unstable.

Files with missing lines	Patch %	Lines
src/object.c	50.00%	3 Missing :warning:
src/t_zset.c	97.95%	2 Missing :warning:

Additional details and impacted files

@@             Coverage Diff              @@
##           unstable    #2867      +/-   ##
============================================
- Coverage     72.44%   72.42%   -0.03%     
============================================
  Files           128      128              
  Lines         70415    70491      +76     
============================================
+ Hits          51011    51050      +39     
- Misses        19404    19441      +37     

Files with missing lines	Coverage Δ
src/defrag.c	80.66% <100.00%> (-0.07%)	:arrow_down:
src/lazyfree.c	85.41% <100.00%> (-7.07%)	:arrow_down:
src/rdb.c	77.19% <100.00%> (-0.18%)	:arrow_down:
src/server.h	100.00% <ø> (ø)
src/sort.c	94.82% <100.00%> (+0.01%)	:arrow_up:
src/t_zset.c	96.76% <97.95%> (+0.01%)	:arrow_up:
src/object.c	82.04% <50.00%> (ø)

... and 11 files with indirect coverage changes

:rocket: New features to boost your workflow:

• :snowflake: Test Analytics: Detect flaky tests, report on failures, and find test suite problems.
• :package: JS Bundle Analysis: Save yourself from yourself by tracking and limiting bundle sizes in JS merges.