antirezwants to merge 1 commit into
Conversation #
Hi, this is a draft implementation that reimplements large sorted sets by replacing the skiplist and general-purpose dictionary with one packed B+ tree (score ordered) and a compact member index, that is, a specialized hash table.
No changes to RDB / AOF. Memory drops between 45 - 60% in many common use cases. Many operations are now faster, sometimes much faster (70% faster). ZSCAN can be slower, but not much slower.
Please tell me if you like this direction, I'll do more QA and refine the PR more.
AI Disclaimer This PR was generated with massive AI help.
Note
High Risk
Core zset storage and hot paths change across persistence, replication, modules, and defrag; regressions would affect data integrity, memory, and latency at scale despite extensive QA described in the PR.
Overview
Large sorted sets no longer default to skiplist + dictionary once they exceed listpack limits. They use a new ** OBJ_ENCODING_BTREE** (
btree
in OBJECT ENCODING
): a score-ordered B+ tree with a compact open-addressing member index (hash tag + leaf id), packed scores in leaves, and external allocation for members ≥320 bytes so one huge member does not force a whole-key skiplist fallback.
** zset_btree.c** is wired into the server build;
routes create/convert/add/del/rank/range/set-ops through the btree API, with skiplist retained for explicit conversion and temporary bulk-command paths.
t_zset.c
RDB still writes
RDB_TYPE_ZSET_2
; loads large sets via into btree (or listpack) instead of building skiplist first.
zsetAdd
AOF rewrite,
ZSCAN,
active defrag,
fork dismiss,
modules(range/scan iterators), geo,
sort, and
DEBUG DIGEST gain btree branches.
A large ** ZSET_MEMSAVING_ALT_REPORT.md** documents design, benchmarks (~45–60% memory on cited workloads), review fixes (ZSCAN cursor/reply, scan completeness), and follow-ups (direct bulk B+ build, compaction). Observable command results and on-disk types stay compatible; encoding,
MEMORY USAGE
, ZSCAN order/cursors, and internal scan behavior can differ within SCAN’s contract.Reviewed by Cursor Bugbot for commit
5b1e9dd. Bugbot is set up for automated code reviews on this repo. Configure here.
reviewed
cursorBotAug 13, 2026
** **cursor Bot left a comment
left a comment
cursorBot There was a problem hiding this comment.
Cursor Bugbot has reviewed your changes using high effort and found 1 potential issue.
Reviewed by Cursor Bugbot for commit
5b1e9dd. Configure here.
| if (!valid) goto end; | || | } | || | key->u.zset.current = (void *)(uintptr_t)(rank + 1); | || | return 1; |
There was a problem hiding this comment.
Module iterator ranks go stale
Medium Severity
B+ tree module range iteration stores a numeric rank in current
. After a module callback deletes or inserts members with a lower rank, that saved rank still looks valid but now names a different element. RM_ZsetRangeCurrentElement
can therefore return the wrong member, and RM_ZsetRangeNext
/ RM_ZsetRangePrev
can skip survivors. Out-of-range ranks end cleanly, but in-range shifted ranks do not.
Additional Locations (2) #
Reviewed by Cursor Bugbot for commit
5b1e9dd. Configure here.
Learn more about bidirectional Unicode characters