8000 Small collections use significantly more memory than Redis compact encodings · Issue #297 · kividbio/kividb · GitHub
[go: up one dir, main page]

Skip to content

Small collections use significantly more memory than Redis compact encodings #297

Closed

Description

@Parikalp-Bhardwaj

Summary

I noticed substantial memory overhead when comparing KiviDB with Redis 8.10.3 on workloads containing many small collections.

Strings are close to Redis, but small hashes, integer sets, and lists consume considerably more process memory.

The largest consistent difference is for integer sets, where KiviDB uses approximately 7.6× the additional RSS per key.

Environment

  • KiviDB: v1.2.0-rc4 (a6b1bf388582dd6b343b34471864145c97dab74d)
  • Redis: 8.10.3
  • Build: Release, Tokio I/O
  • Persistence: Disabled
  • Memory limit: Unlimited
  • 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.

Activity

  1. murtazayusuf commented on Nov 2, 2026

    @murtazayusuf
    Contributor

    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.

  2. Parikalp-Bhardwaj commented on Nov 2, 2026

    @Parikalp-Bhardwaj
    CollaboratorAuthor

    Okay, Cool! Thank you @murtazayusuf, I’ll start with small hashes and integer sets and prepare a short design proposal covering:

    • Compact representation and conversion thresholds.
    • Memory savings and performance trade-offs.
    • Snapshot, AOF, replication, and command compatibility.

    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.

  3. Parikalp-Bhardwaj commented on Nov 2, 2026

    @Parikalp-Bhardwaj
    CollaboratorAuthor

    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.

    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.

  4. murtazayusuf commented on Nov 2, 2026

    @murtazayusuf
    Contributor

    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.

  5. Parikalp-Bhardwaj commented on Nov 2, 2026

    @Parikalp-Bhardwaj
    CollaboratorAuthor

    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.

  6. murtazayusuf commented on Nov 2, 2026

    @murtazayusuf
    Contributor

    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.

  7. added a commit that references this issue on Nov 17, 2026
  8. murtazayusuf commented on Nov 17, 2026

    @murtazayusuf
    Contributor

    Spring Session data point (2026-11-17)

    spring-session-data-redis stores each session as one small hash:

    HSET spring:session:sessions:<id> creationTime <ms> lastAccessedTime <ms> maxInactiveInterval 1800 sessionAttr:SPRING_SECURITY_CONTEXT <1.5 KB> sessionAttr:locale en_US
    

    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.

  9. Parikalp-Bhardwaj commented on Nov 17, 2026

    @Parikalp-Bhardwaj
    CollaboratorAuthor

    @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.

  10. murtazayusuf commented on Nov 17, 2026

    @murtazayusuf
    Contributor

    @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:

    • Sets: on master (perf(set): small sets in one block; integer sets (#297) #872).
    • Hashes: on master since today (perf(hash): small hashes in one block (collection storage, step 2) #886): one block of fields and values up to 512 fields of 64 bytes; 162.8 → 71.8 bytes a field at 10 fields, 129.2 → 55.8 at 100 (Redis 57.8 and 51.7).
    • 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.

  11. murtazayusuf commented on Nov 17, 2026

    @murtazayusuf
    Contributor

    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.

  12. murtazayusuf commented on Nov 18, 2026

    @murtazayusuf
    Contributor

    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.

  13. murtazayusuf commented on Nov 18, 2026

    @murtazayusuf
    Contributor

    #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.

  14. murtazayusuf commented on Nov 19, 2026

    @murtazayusuf
    Contributor

    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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Labels

enhancementNew feature or request

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions

    0