Skip to content

Optimize skiplist query efficiency by embedding the skiplist header#2867

Merged
zuiderkwast merged 9 commits into
valkey-io:unstablefrom
chzhoo:embedded_zsl_header
Jan 29, 2026
Merged

Optimize skiplist query efficiency by embedding the skiplist header#2867
zuiderkwast merged 9 commits into
valkey-io:unstablefrom
chzhoo:embedded_zsl_header

Conversation

@chzhoo

@chzhoo chzhoo commented Nov 24, 2025 •
edited
Loading

Copy link
Copy Markdown
Contributor

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

codecov Bot commented Nov 24, 2025 •
edited
Loading

Copy link
Copy Markdown

Codecov Report

❌ Patch coverage is 95.53571% with 5 lines in your changes missing coverage. Please review.
✅ Project coverage is 74.23%. Comparing base (35fdcea) to head (7e0918e).
⚠️ Report is 46 commits behind head on unstable.

Files with missing lines Patch % Lines
src/object.c 50.00% 3 Missing ⚠️
src/t_zset.c 97.87% 2 Missing ⚠️
Additional details and impacted files 
@@             Coverage Diff              @@
##           unstable    #2867      +/-   ##
============================================
- Coverage     74.38%   74.23%   -0.15%     
============================================
  Files           129      129              
  Lines         70972    70974       +2     
============================================
- Hits          52791    52691     -100     
- Misses        18181    18283     +102
Files with missing lines Coverage Δ
src/defrag.c 80.75% <100.00%> (-1.22%) ⬇️
src/lazyfree.c 79.16% <100.00%> (-6.25%) ⬇️
src/rdb.c 76.51% <100.00%> (-0.09%) ⬇️
src/server.h 100.00% <ø> (ø)
src/sort.c 94.85% <100.00%> (-1.60%) ⬇️
src/t_zset.c 96.98% <97.87%> (-0.14%) ⬇️
src/object.c 91.16% <50.00%> (-0.49%) ⬇️

... and 22 files with indirect coverage changes

🚀 New features to boost your workflow:
  • ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.
  • 📦 JS Bundle Analysis: Save yourself from yourself by tracking and limiting bundle sizes in JS merges.

@chzhoo chzhoo changed the title Optimize skiplist query by embedding the skiplist header Optimize skiplist query efficiency by embedding the skiplist header Nov 25, 2025
@chzhoo
Optimize skiplist query by embedding the skiplist header node
58d172f 
Signed-off-by: chzhoo <czawyx@163.com>
Signed-off-by: GitHub <noreply@github.com>
@chzhoo
Update defrag.c
bfafdcf 
Signed-off-by: chzhoo <czawyx@163.com>
Signed-off-by: GitHub <noreply@github.com>
@chzhoo
union
c2c63b9 
Signed-off-by: GitHub <noreply@github.com>
@chzhoo chzhoo force-pushed the embedded_zsl_header branch from 00c9a4b to c2c63b9 Compare November 25, 2025 09:53
ranshid
ranshid reviewed Nov 25, 2025
View reviewed changes

@ranshid ranshid left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nice!

I will do a deeper review, I just want to first eliminate concerns about potential future extensions of the skiplist metadata.

Comment thread src/server.h
@chzhoo
Refactor zskiplist metadata access and helpers
81a22d2 
Signed-off-by: chzhoo <czawyx@163.com>
@chzhoo
Fix small issue
47dc765 
Signed-off-by: chzhoo <czawyx@163.com>
ranshid
ranshid reviewed Dec 4, 2025
View reviewed changes
Comment thread src/server.h Outdated
chzhoo added 2 commits December 8, 2025 22:45
@chzhoo
Refactor zskiplist structure
7785194 
Signed-off-by: chzhoo <czawyx@163.com>
@chzhoo
Clarify skiplist level references in comments
dbd1087 
Signed-off-by: chzhoo <czawyx@163.com>
@rainsupreme

rainsupreme commented Jan 1, 2026

Copy link
Copy Markdown
Contributor

This looks good to me! I very much like the move towards making an interface (like for defrag.c) and keeping the implementation details more componentized.

FYI, since a lot of skiplist work has been going on, I am currently working on a proof of concept for replacing skiplist with a B+ tree. My main goal is memory savings and my secondary goal is performance. I hope to have some real test numbers to back up my proposal in a few weeks. It's great that you're making it harder to show an improvement over skiplist though 😆

@rainsupreme rainsupreme self-requested a review January 1, 2026 21:36
rainsupreme
rainsupreme approved these changes Jan 1, 2026
View reviewed changes

@rainsupreme rainsupreme left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

👍

Comment thread src/t_zset.c Outdated
chzhoo added 2 commits January 4, 2026 14:39
@chzhoo
Refactor zskiplist structure
5a1e2ad 
Signed-off-by: chzhoo <czawyx@163.com>
@chzhoo
Merge remote-tracking branch 'origin/unstable' into embedded_zsl_header
7e0918e 
Signed-off-by: chzhoo <czawyx@163.com>
@zuiderkwast zuiderkwast added the release-notes This issue should get a line item in the release notes label Jan 7, 2026
@zuiderkwast zuiderkwast moved this to In Progress in Valkey 9.1 Jan 7, 2026
rainsupreme
rainsupreme approved these changes Jan 28, 2026
View reviewed changes

@rainsupreme rainsupreme left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

lgtm!

@zuiderkwast zuiderkwast merged commit 920bf12 into valkey-io:unstable Jan 29, 2026
57 checks passed
@github-project-automation github-project-automation Bot moved this from In Progress to Done in Valkey 9.1 Jan 29, 2026
@chzhoo chzhoo deleted the embedded_zsl_header branch February 2, 2026 11:59
harrylin98 pushed a commit to harrylin98/valkey_forked that referenced this pull request Feb 19, 2026
@chzhoo
Optimize skiplist query efficiency by embedding the skiplist header (v…
ff4edd8 
…alkey-io#2867)

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;
```

---------

Signed-off-by: chzhoo <czawyx@163.com>
hpatro pushed a commit to hpatro/valkey that referenced this pull request Mar 5, 2026
@chzhoo @hpatro
Optimize skiplist query efficiency by embedding the skiplist header (v…
98dc455 
…alkey-io#2867)

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;
```

---------

Signed-off-by: chzhoo <czawyx@163.com>
Signed-off-by: Harkrishn Patro <bunty.hari@gmail.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@ranshid ranshid ranshid approved these changes
@zuiderkwast zuiderkwast zuiderkwast approved these changes
+1 more reviewer
@rainsupreme rainsupreme rainsupreme approved these changes
Reviewers whose approvals may not affect merge requirements

Assignees

@chzhoo chzhoo

Labels

release-notes This issue should get a line item in the release notes

Projects

Valkey 9.1
Status: Done

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

4 participants

@chzhoo @rainsupreme @zuiderkwast @ranshid