You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Small collections use significantly more memory than Redis compact encodings #297
Dataset: 100,000 keys per workload, 10 elements per collection
Runs: Three independent runs with fresh server processes
Validation: All 100,000 key cardinalities checked, plus six sampled content checks per workload
Memory was measured as:
(RSS after loading - RSS of empty server) / number of keys
The measurements were taken after a three-second settling period.
Results
Average process RSS increase across three verified runs:
Workload
Redis B/key
KiviDB B/key
Ratio
String (control)
76.0
66.4
0.87×
Hash (10 fields)
286.2
1,621.5
5.67×
Set (10 integers)
108.9
823.0
7.56×
List (10 elements)
174.4
629.8
3.61×
Hash, set, and list measurements were consistent across all three runs.
Sorted-set observation
I also tested sorted sets containing 10 members per key.
KiviDB's measured process RSS varied significantly between runs, despite stable logical data and successful cardinality checks.
The variation was large enough that I excluded sorted sets from the main comparison until the cause is understood.
Possible explanation
Redis uses compact encodings for small collections, including listpacks and integer sets.
KiviDB uses general-purpose in-memory data structures for these values, which may introduce additional allocations and metadata overhead.
This could explain why strings remain close to Redis while small collections consume substantially more memory.
The exact contribution of collection representations, container allocations, and allocator behavior still needs investigation.
Impact
Applications storing many small collections, such as user profiles, tags, sessions, and activity lists, may require substantially more process memory than equivalent Redis workloads.
This is a memory-efficiency concern, not a data-correctness or security issue.
Possible improvements
It may be worth investigating:
Compact representations for small integer sets and hashes.
Reducing per-element allocation overhead.
Alternative representations for small sorted sets.
Memory-versus-throughput trade-offs before adopting a different representation.
I'm happy to investigate the implementation and benchmark potential improvements if this is something you'd like to optimize.
Thanks, @Parikalp-Bhardwaj, this is a clear measurement, and it matches what our own data-types benchmark found from another angle (100-byte hash fields at about 1.8× Redis; benchmarks/1.2.0/datatypes on the release branch). Small collections are the obvious next step for memory after 1.2.0, and yes, please take it; it's assigned to you.
Because a compact representation touches a lot (every command on those types, the snapshot format, replication and AOF, and the hot path), please start with a short design proposal here before code:
Which types first. Small hashes and integer sets look like the biggest wins from your table.
The representation. What it is, and when a value converts to and from the general one (sizes, element lengths), and what that costs on the way.
What it saves and costs. Bytes per key at 10 / 100 / 1,000 elements, and the throughput and instructions per command of the common commands (HSET/HGET/HGETALL, SADD/SISMEMBER/SMEMBERS). scripts/perf/run.sh gives instructions per command without the noise of a shared machine.
Compatibility. How it is written to dump.kdb and read back, including by a release that doesn't know it, and OBJECT ENCODING / MEMORY USAGE / DEBUG output.
Please design it from what you measure rather than from Redis's code: KiviDB's licence keeps us away from Redis 8.x sources. Valkey (BSD) is fine to read.
The sorted-set variance you saw is interesting on its own: could you attach the script you used? Run-to-run RSS swings with the same logical data may be the allocator or active defrag, and worth a separate look.
I spent some time looking into why small hashes and sets use more memory than expected in KiviDB. I think there is a useful opportunity here to reduce allocations without changing the persistence format or redesigning the locking model.
What I found
A large part of the overhead comes from storing each field or member as a separate allocation. Even when the values are small, the strings, Arcs, and collection bookkeeping add up.
Here are a few examples from the investigation. The current figures are measured on KiviDB; the compact figures are estimates from an isolated Rust experiment, not a working server implementation.
Collection
Current KiviDB
Compact estimate
Redis reference
Hash with 10 fields
1,316 B
~296 B
272 B
Integer set with 10 members
668 B
~156 B
96 B
Integer set with 100 members
4,735 B
~519 B
500 B
This suggests that a compact representation could save a meaningful amount of memory for small collections. The benefit should be most noticeable when the stored values are short.
Design direction
I would start with integer sets, then look at small hashes as a separate change. Both could remain inside the existing Arc<RwLock<...>> structure, so we would not need to change the outer concurrency model.
1. Integer sets first
For sets containing only integers that can be represented without changing their original string meaning, we could use a compact internal representation rather than allocating an Arc for every member. When a set grows beyond a measured threshold, or a member cannot be represented safely, we would convert it to the current representation.
The conversion must preserve Redis-visible behavior. For example, 1 and 01 cannot silently become the same member. We also need to test negative values, integer overflow, removals, iteration, and conversion boundaries.
In the isolated benchmark, SISMEMBER improved from about 93 ns to 21 ns for a 10-member set. But there is a trade-off: reconstructing string members makes SMEMBERS more expensive. Callgrind showed roughly 21% more instructions at 10 members and 45% more at 100. Because of that, I would not lock in a 512-member cutoff yet. I would prototype with a conservative limit and measure several thresholds inside KiviDB.
2. Small hashes afterward
The same allocation overhead appears in hashes, so a packed representation of small field/value pairs is worth exploring. In the isolated benchmark, HSET went from about 456 ns to 114 ns, and HGET from about 182 ns to 127 ns at 10 fields.
I would use packed bytes, not just field count, to decide when to switch back to the normal hash. The experiments suggest HGET reaches roughly today's performance near 1.1–1.2 KiB of packed data. A possible 64-field / 1.5 KiB limit is only a starting hypothesis; the byte cutoff needs verification in the actual server. Hash field expiration also needs careful treatment before this is ready.
Compatibility and scope
My preference is to change only the in-memory representation. The existing snapshot (dump.kdb) encoding should remain unchanged, along with the serialization behavior used by AOF, replication, and DUMP/RESTORE. That should make mixed-version persistence compatibility possible, but it needs explicit tests rather than an assumption. I would avoid introducing a new on-disk type tag.
I also noticed two related issues that are probably best handled separately:
MEMORY USAGE appears to under-report the actual memory cost of small collections by several times.
Updating an existing hash field currently creates a new String and Arc; that allocation could potentially be avoided without introducing a compact hash representation.
Suggested next step
I suggest a small integer-set prototype first, with tests for command semantics, encoding conversion, snapshots, AOF, replication, and restore. Then we can measure actual server memory, command latency, and instruction counts at different collection sizes before choosing the cutoff. If those results hold up, compact hashes can follow in a separate PR.
The estimated savings look promising, but I don't want to present them as production results yet. I'd rather validate one representation end to end and use that evidence to guide the rest of the design.
Thanks, @Parikalp-Bhardwaj, this is a good plan: in-memory only, integer sets first, byte-based cutoffs measured in the server. Go ahead with the integer-set prototype on master (after 1.2.0 ships), as a draft PR. A few
8000
things it should cover:
Hot path. No cost to single-key GET/SET or to large collections: instructions per command with scripts/perf/run.sh. Since SMEMBERS gets more expensive, measure SMEMBERS, SINTER and SRANDMEMBER throughput too, not only SISMEMBER.
Which integers. Only the canonical decimal form goes compact (no leading zeros, + or -0): anything that doesn't read back as the same string stays in the normal set.
Memory accounting.maxmemory, eviction and MEMORY USAGE should count the compact size, and active defrag should either move the compact buffers or skip them on purpose.
Thresholds.CONFIG already accepts set-max-intset-entries, hash-max-listpack-entries and hash-max-listpack-value (src/commands/server.rs), and OBJECT ENCODING already reports intset/listpack by size, so let the real cutoffs come from those settings.
Hash field TTLs. For hashes later, keep hashes with field TTLs in today's layout at first.
The MEMORY USAGE under-count and the extra allocation when a field is updated are worth separate issues: please file them. We'll run the memory and latency A/B on an Azure VM when the prototype is ready.
I will start working on the integer-set prototype next, with 64 members as an initial experimental limit. will focus on preserving existing command behavior and persistence compatibility, then measure actual memory savings and performance before deciding on the final threshold.
Sounds good. 64 is fine to start with. If the prototype reads the limit from set-max-intset-entries (CONFIG SET already accepts it), you can sweep several limits in one run without rebuilding.
So it has 5 fields, one of them about 1.5 KB. We measured the memory increase after loading 200,000 of these hashes (used_memory, m
8BD0
easured as a delta on top of the same preloaded dataset):
Redis 8.10
Valkey 8.1
KiviDB 1.2.2
+200k session hashes
+383 MB
+370 MB
+449 MB (+21% vs Valkey)
Same-run strings + other hashes, before sessions
566 MB
570 MB
522 MB (−8%)
Throughput is fine: HGETALL / EXISTS / HSET / PEXPIREAT 1:1:1:1 runs at 339k ops/s on KiviDB --threads 4, against 314k on Valkey io-threads 4 (+8%), with 100% hits. The gap is only memory per small hash. It flips KiviDB's memory advantage on strings (−16% overall) into a disadvantage for every Spring app that keeps sessions in Redis.
Harness: r19b/ in the outreach scratchpad, 4 pinned cores per server.
@murtazayusuf good to see the compact-set changes merged. The extra optimizations look good too. Happy to help with small hashes or other collection types next.
Lists: in progress on our side (chunks of elements, room at both ends), a PR in a day or so.
Sorted sets: yours. refactor(zset): encapsulate sorted set storage #892 (closing SortedSetInner off) is the step everything else there needs, and it is next in the review queue, with instruction counts for ZADD/ZSCORE/ZRANGE so we know it costs nothing. After it there are two pieces, and you can have either or both: the counted B-tree for large sets (Sorted-set rank and range commands are slow on large datasets #875: prototype and numbers first, as you planned), and small sorted sets in one block. For the small ones the shape that worked for sets and hashes should carry over: members end to end with a fingerprint byte each for ZSCORE-style lookups, scores beside them, kept in score order so a range is a slice; up to 128 members of 64 bytes as Redis does. src/packed_hash.rs and src/hash_fields.rs are the closest example, including how the type picks a form and never goes back, and what had to be measured (bytes per member at 10/100, and the instruction rows on the shipped profile: with LTO off the numbers mislead).
Still open for all types: about 150 bytes a key go to the key's entry and the Arc<RwLock<..>> around every collection. That is the next memory win for small collections and nobody has it yet; say if you want to look at it after the sorted sets.
This issue can stay open as the tracker until sorted sets and lists are in.
Lists are on master too (#895): elements in chunks with room at both ends. Bytes an element at 32-byte elements: 76.0 → 48.8 at 10 elements, 65.2 → 38.4 at 100, 69.8 → 36.7 at 3 million (Redis 45.0, 36.4, 34.3). LRANGE is 18 to 47% cheaper, pushes and pops 1 to 3%, LMOVE/RPOPLPUSH about 3%.
So of the four types in this issue, sets, hashes and lists are done; sorted sets are next (#892, then the small block and the counted tree, #875). Two things remain for every type and are open to anyone: the roughly 150 bytes a key that go to the entry and the lock around each collection, and large hashes and sets (tables), which are unchanged.
Where this stands on master (b75b064): sets (#872), hashes (#886) and lists (#895) are packed. Measured with this issue's method (100k keys x 10 elements, RSS delta per key) on one Azure D4s_v5:
master
1.2.2
Redis 8.10.2
hash
494 B
1,693
211
integer set
222 B
781
98
list
269 B
621
130
sorted set
1,247 B
1,248
186
What is left here: small sorted sets in one block, and the roughly 150 B per key that go to the entry and the lock around each collection.
#926 is merged: small sorted sets (up to 128 members of up to 64 bytes) are now one packed block, like sets, hashes and lists before them. By this issue's method (100k keys x 10 members, RSS per key, D4s_v5): sorted set 273.6 B a key, against 1,249.5 before and 186.3 on Redis 8.10.2. Per member with whole-number scores: 29.6 B at 10 members and 19.0 B at 128 (Redis 24.8 and 20.4).
What is left here is the same for all four types now: the per-key overhead of the entry and the lock around each collection (about 150 B a key), which is the next step.
Closing: the compact encodings this issue asked for are on master for all four types. Sets (#872), hashes (#886), lists (#895) and small sorted sets (#926) are each one packed block. By this issue's method (100k keys x 10 elements, RSS per key, one Azure D4s_v5), 1.2.2 → master, with Redis 8.10.2 beside it: hash 1,693 → 494 B (Redis 211), integer set 781 → 222 B (98), list 621 → 269 B (130), sorted set 1,248 → 274 B (186).
What is left is no longer the encoding but the roughly 150 B a key that go to the entry and the lock around each collection, which is why a key of ten elements is still 1.5 to 2.3 times Redis. That is the same per-entry overhead the table work in #764 is removing, so it is tracked there from now on rather than in a new issue. Thank you @Parikalp-Bhardwaj for the measurements and MEMORY USAGE fixes that started this.
Activity
murtazayusuf commentedon Nov 2, 2026
Thanks, @Parikalp-Bhardwaj, this is a clear measurement, and it matches what our own data-types benchmark found from another angle (100-byte hash fields at about 1.8× Redis;
benchmarks/1.2.0/datatypeson the release branch). Small collections are the obvious next step for memory after 1.2.0, and yes, please take it; it's assigned to you.Because a compact representation touches a lot (every command on those types, the snapshot format, replication and AOF, and the hot path), please start with a short design proposal here before code:
HSET/HGET/HGETALL,SADD/SISMEMBER/SMEMBERS).scripts/perf/run.shgives instructions per command without the noise of a shared machine.dump.kdband read back, including by a release that doesn't know it, andOBJECT ENCODING/MEMORY USAGE/DEBUGoutput.Please design it from what you measure rather than from Redis's code: KiviDB's licence keeps us away from Redis 8.x sources. Valkey (BSD) is fine to read.
The sorted-set variance you saw is interesting on its own: could you attach the script you used? Run-to-run RSS swings with the same logical data may be the allocator or active defrag, and worth a separate look.
Parikalp-Bhardwaj commentedon Nov 2, 2026
Okay, Cool! Thank you @murtazayusuf, I’ll start with small hashes and integer sets and prepare a short design proposal covering:
I’ll use Valkey as a reference and avoid Redis 8.x source code.
I’ll also share my benchmark script and look into the sorted-set RSS variation separately.
I’ll post the proposal here for your feedback before making any code changes.
Parikalp-Bhardwaj commentedon Nov 2, 2026
Hi @murtazayusuf ,
I spent some time looking into why small hashes and sets use more memory than expected in KiviDB. I think there is a useful opportunity here to reduce allocations without changing the persistence format or redesigning the locking model.
What I found
A large part of the overhead comes from storing each field or member as a separate allocation. Even when the values are small, the strings,
Arcs, and collection bookkeeping add up.Here are a few examples from the investigation. The current figures are measured on KiviDB; the compact figures are estimates from an isolated Rust experiment, not a working server implementation.
This suggests that a compact representation could save a meaningful amount of memory for small collections. The benefit should be most noticeable when the stored values are short.
Design direction
I would start with integer sets, then look at small hashes as a separate change. Both could remain inside the existing
Arc<RwLock<...>>structure, so we would not need to change the outer concurrency model.1. Integer sets first
For sets containing only integers that can be represented without changing their original string meaning, we could use a compact internal representation rather than allocating an
Arcfor every member. When a set grows beyond a measured threshold, or a member cannot be represented safely, we would convert it to the current representation.The conversion must preserve Redis-visible behavior. For example,
1and01cannot silently become the same member. We also need to test negative values, integer overflow, removals, iteration, and conversion boundaries.In the isolated benchmark,
SISMEMBERimproved from about 93 ns to 21 ns for a 10-member set. But there is a trade-off: reconstructing string members makesSMEMBERSmore expensive. Callgrind showed roughly 21% more instructions at 10 members and 45% more at 100. Because of that, I would not lock in a 512-member cutoff yet. I would prototype with a conservative limit and measure several thresholds inside KiviDB.2. Small hashes afterward
The same allocation overhead appears in hashes, so a packed representation of small field/value pairs is worth exploring. In the isolated benchmark,
HSETwent from about 456 ns to 114 ns, andHGETfrom about 182 ns to 127 ns at 10 fields.I would use packed bytes, not just field count, to decide when to switch back to the normal hash. The experiments suggest
HGETreaches roughly today's performance near 1.1–1.2 KiB of packed data. A possible 64-field / 1.5 KiB limit is only a starting hypothesis; the byte cutoff needs verification in the actual server. Hash field expiration also needs careful treatment before this is ready.Compatibility and scope
My preference is to change only the in-memory representation. The existing snapshot (
dump.kdb) encoding should remain unchanged, along with the serialization behavior used by AOF, replication, and DUMP/RESTORE. That should make mixed-version persistence compatibility possible, but it needs explicit tests rather than an assumption. I would avoid introducing a new on-disk type tag.I also noticed two related issues that are probably best handled separately:
MEMORY USAGEappears to under-report the actual memory cost of small collections by several times.StringandArc; that allocation could potentially be avoided without introducing a compact hash representation.Suggested next step
I suggest a small integer-set prototype first, with tests for command semantics, encoding conversion, snapshots, AOF, replication, and restore. Then we can measure actual server memory, command latency, and instruction counts at different collection sizes before choosing the cutoff. If those results hold up, compact hashes can follow in a separate PR.
The estimated savings look promising, but I don't want to present them as production results yet. I'd rather validate one representation end to end and use that evidence to guide the rest of the design.
murtazayusuf commentedon Nov 2, 2026
Thanks, @Parikalp-Bhardwaj, this is a good plan: in-memory only, integer sets first, byte-based cutoffs measured in the server. Go ahead with the integer-set prototype on master (after 1.2.0 ships), as a draft PR. A few 8000 things it should cover:
scripts/perf/run.sh. SinceSMEMBERSgets more expensive, measure SMEMBERS, SINTER and SRANDMEMBER throughput too, not only SISMEMBER.+or-0): anything that doesn't read back as the same string stays in the normal set.maxmemory, eviction andMEMORY USAGEshould count the compact size, and active defrag should either move the compact buffers or skip them on purpose.CONFIGalready acceptsset-max-intset-entries,hash-max-listpack-entriesandhash-max-listpack-value(src/commands/server.rs), andOBJECT ENCODINGalready reportsintset/listpackby size, so let the real cutoffs come from those settings.The
MEMORY USAGEunder-count and the extra allocation when a field is updated are worth separate issues: please file them. We'll run the memory and latency A/B on an Azure VM when the prototype is ready.Parikalp-Bhardwaj commentedon Nov 2, 2026
I will start working on the integer-set prototype next, with 64 members as an initial experimental limit. will focus on preserving existing command behavior and persistence compatibility, then measure actual memory savings and performance before deciding on the final threshold.
murtazayusuf commentedon Nov 2, 2026
Sounds good. 64 is fine to start with. If the prototype reads the limit from
set-max-intset-entries(CONFIG SETalready accepts it), you can sweep several limits in one run without rebuilding.Merge pull request #872 from kividbio/perf/packed-small-sets
packed_set: a small set of short members in one block (kividbio#297)
packed_set: lookups by vector compare, members compared by words; a b…
perf(set): small sets in one block, integer sets up to 512 (kividbio#297
bench: regression suite 17, memory of small sets (kividbio#297); CHAN…
murtazayusuf commentedon Nov 17, 2026
Spring Session data point (2026-11-17)
spring-session-data-redisstores each session as one small hash:So it has 5 fields, one of them about 1.5 KB. We measured the memory increase after loading 200,000 of these hashes (
used_memory, m 8BD0 easured as a delta on top of the same preloaded dataset):Throughput is fine:
HGETALL/EXISTS/HSET/PEXPIREAT1:1:1:1 runs at 339k ops/s on KiviDB--threads 4, against 314k on Valkey io-threads 4 (+8%), with 100% hits. The gap is only memory per small hash. It flips KiviDB's memory advantage on strings (−16% overall) into a disadvantage for every Spring app that keeps sessions in Redis.Harness:
r19b/in the outreach scratchpad, 4 pinned cores per server.Parikalp-Bhardwaj commentedon Nov 17, 2026
@murtazayusuf good to see the compact-set changes merged. The extra optimizations look good too. Happy to help with small hashes or other collection types next.
murtazayusuf commentedon Nov 17, 2026
@Parikalp-Bhardwaj thank you, and your integer sets are the base all of this stands on. Where the collection work is, so we don't cross:
SortedSetInneroff) is the step everything else there needs, and it is next in the review queue, with instruction counts for ZADD/ZSCORE/ZRANGE so we know it costs nothing. After it there are two pieces, and you can have either or both: the counted B-tree for large sets (Sorted-set rank and range commands are slow on large datasets #875: prototype and numbers first, as you planned), and small sorted sets in one block. For the small ones the shape that worked for sets and hashes should carry over: members end to end with a fingerprint byte each forZSCORE-style lookups, scores beside them, kept in score order so a range is a slice; up to 128 members of 64 bytes as Redis does.src/packed_hash.rsandsrc/hash_fields.rsare the closest example, including how the type picks a form and never goes back, and what had to be measured (bytes per member at 10/100, and the instruction rows on the shipped profile: with LTO off the numbers mislead).Arc<RwLock<..>>around every collection. That is the next memory win for small collections and nobody has it yet; say if you want to look at it after the sorted sets.This issue can stay open as the tracker until sorted sets and lists are in.
murtazayusuf commentedon Nov 17, 2026
Lists are on master too (#895): elements in chunks with room at both ends. Bytes an element at 32-byte elements: 76.0 → 48.8 at 10 elements, 65.2 → 38.4 at 100, 69.8 → 36.7 at 3 million (Redis 45.0, 36.4, 34.3).
LRANGEis 18 to 47% cheaper, pushes and pops 1 to 3%,LMOVE/RPOPLPUSHabout 3%.So of the four types in this issue, sets, hashes and lists are done; sorted sets are next (#892, then the small block and the counted tree, #875). Two things remain for every type and are open to anyone: the roughly 150 bytes a key that go to the entry and the lock around each collection, and large hashes and sets (tables), which are unchanged.
murtazayusuf commentedon Nov 18, 2026
Where this stands on master (b75b064): sets (#872), hashes (#886) and lists (#895) are packed. Measured with this issue's method (100k keys x 10 elements, RSS delta per key) on one Azure D4s_v5:
What is left here: small sorted sets in one block, and the roughly 150 B per key that go to the entry and the lock around each collection.
murtazayusuf commentedon Nov 18, 2026
#926 is merged: small sorted sets (up to 128 members of up to 64 bytes) are now one packed block, like sets, hashes and lists before them. By this issue's method (100k keys x 10 members, RSS per key, D4s_v5): sorted set 273.6 B a key, against 1,249.5 before and 186.3 on Redis 8.10.2. Per member with whole-number scores: 29.6 B at 10 members and 19.0 B at 128 (Redis 24.8 and 20.4).
What is left here is the same for all four types now: the per-key overhead of the entry and the lock around each collection (about 150 B a key), which is the next step.
murtazayusuf commentedon Nov 19, 2026
Closing: the compact encodings this issue asked for are on master for all four types. Sets (#872), hashes (#886), lists (#895) and small sorted sets (#926) are each one packed block. By this issue's method (100k keys x 10 elements, RSS per key, one Azure D4s_v5), 1.2.2 → master, with Redis 8.10.2 beside it: hash 1,693 → 494 B (Redis 211), integer set 781 → 222 B (98), list 621 → 269 B (130), sorted set 1,248 → 274 B (186).
What is left is no longer the encoding but the roughly 150 B a key that go to the entry and the lock around each collection, which is why a key of ten elements is still 1.5 to 2.3 times Redis. That is the same per-entry overhead the table work in #764 is removing, so it is tracked there from now on rather than in a new issue. Thank you @Parikalp-Bhardwaj for the measurements and
MEMORY USAGEfixes that started this.