Skip to content

Memory: a big hash uses ~2.7x Redis's memory per field (3M fields: 296 MiB vs 109 MiB) #764

Open

Description

@murtazayusuf

Measured while working on #753: loading one hash with 3,000,000 fields (f0..f2999999 = v, the #753 repro), KiviDB's used_memory is 296 MiB vs Redis 8.10.2's 109 MiB, about 2.7x the bytes per hash field. Both on the same D4s_v5 VM, default settings.

Small fields with tiny values are a common hash shape (counters, flags, session fields), so this matters for memory per key (see the memory-per-key work: entries were cut from 218 to 177 bytes for strings).

Worth a breakdown of where the bytes go per field (hash table slot, key/field allocation, value allocation, field-TTL metadata, allocator overhead) and a design to bring it close to Redis's listpack/hashtable numbers, e.g. inline small field/value bytes, a compact encoding for small hashes, and not reserving field-TTL space until a field TTL is set. Measure the same way across sizes (10, 1k, 100k, 3M fields).

Activity

  1. magic-peach commented on Nov 18, 2026

    @magic-peach
    Contributor

    @murtazayusuf can I work on this?

  2. murtazayusuf commented on Nov 18, 2026

    @murtazayusuf
    ContributorAuthor

    @magic-peach thanks for asking first. Not this one yet: the large hash is the next step of the collection storage work (after #872, #886, #895 and #892), and what it needs is the table itself: our own field table in place of the one used today, which is also what #770's cursor waits for. Its design is not settled, and two people in that table at once would collide. Once the design is written down here there will be parts to hand out, and I'll say so on this issue.

    If you want engine code in the meantime, #670 is free and self-contained (the search field clock read once per query, and the double hash lookup in FT.AGGREGATE). I'm looking at your update on #887 now.

  3. magic-peach commented on Nov 18, 2026

    @magic-peach
    Contributor

    cool, will work on #670 now. Do let me know if anything is needed from my side for #887 and #870 to be merged

  4. murtazayusuf commented on Nov 19, 2026

    @murtazayusuf
    ContributorAuthor

    Design: the large form of hashes and sets

    The small forms are done (#872 sets, #886 hashes). This is the large form: one table type, CollectionTable (new src/collection_table.rs), used as Repr::Table by MemberSet (src/member_set.rs) and HashFields (src/hash_fields.rs). It also supplies the cursor #770 needs.

    1. Where the bytes go today, and the target

    used_memory counts the size each allocation asks for (memory_use), so the arithmetic below is exact and matches the measurements.

    Hash today (IndexMap<String, Arc<[u8]>>), the #764 load (3M fields f0..f2999999 = v):

    part bytes/field
    index table: 4,194,304 buckets x (8 B index + 1 control byte) 12.6
    entries Vec: capacity 3,670,016 x 48 B (hash 8, String 24, Arc 16), 18% unused room 58.7
    field String heap block (7.6 B average name) 7.6
    value Arc<[u8]>: 16 B counts + 1 B, padded 24
    total ~103 (x 3M = 295 MiB; measured 296)

    The same arithmetic gives suite 19's table rows exactly (100k fields of 14 B, 32 B values: 11.8 + 55.0 + 14 + 48 = 128.8, recorded 128.85). A field TTL adds a second copy of the name and a slot in Expiries (AHashMap<String, u64>, src/types.rs).

    Set today (hashbrown::HashTable<Arc<[u8]>>): 100k members of 14 B: 131,072 buckets x (16 + 1) = 22.3 B, plus an Arc of 16 + 14 -> 32 B: 54.3 (recorded 54.28). Integer members 0..99,999: 22.3 + 24 = 46.3 (recorded 46.28).

    Redis, by the same measure: 38 B a field for #764 (109 MiB). With its bucket array at about 11 B a field (one 8 B pointer per field at load factor <= 1), the remaining ~27 B is its per-field entry.

    Target layout:

    • Table: a power-of-two array of 64-byte groups (one cache line each): [7 control bytes][1 meta byte][7 x 8 B slots]. A control byte is 0 for an empty slot, or 0x80 | 7 bits of the hash (the same fingerprint idea as the packed forms). When a group is full, slot 6 links to an overflow group. Overflow groups come from a per-table arena allocated in chunks, so the arena never has to be copied.
    • Entry: one block per element, from the 16-byte slab classes (value_slab), as keyspace entries have been since 1.2.0. A hash entry is [flen:7|TTL:1][vlen:7|LONG:1] field value: 2 bytes of header, with u32 lengths after it when LONG is set. A set entry is [len:7|LONG:1] member. There is no refcount, no String and no Arc. Readers already accept borrowed bytes (element::Value::Bytes, Member::Bytes) and copy them when they keep them past the lock.
    • Short set members inline: a member of <= 7 bytes (every integer up to 7 digits) lives in the slot itself, tagged by its low bit (entry pointers are 16-aligned). It has no entry at all.
    • Field TTL: only when present, as [u32 list position][u64 deadline] inside the entry (12 B). This is the keyspace entry's own scheme (store/entry.rs, store/ttl_list.rs).
    bytes per element today target Redis
    #764 hash, 3M fields 103 ~30 (13.7 table + 16 entry) -> ~85 MiB 38
    suite 19 hash, 100k (14 B field, 32 B value) 128.8 ~61 (13.4 + 48) 76.8
    suite 19 hash, 1k 166.6 ~65 (17.1 + 48) 70.4
    suite 17 set, 14 B members, 100k / 1k 54.3 / 67.0 ~29 / ~33 36.8 / 30.2
    suite 17 set, integers, 100k / 1k 46.3 / 59.0 ~13 / ~17 28.8 / 22.0

    The ceiling, honestly. These are estimates from the layout, not measurements. The table's share depends on where the count sits relative to a doubling. It is about 13 B an element just before a growth (fill 0.875, overflow included) and about 23 B just after one (fill ~0.41). Entries round up to 16-byte classes. So #764 at 3.3M fields, just past a doubling, would be about 38.6 B: level with Redis, not below it. At 1k string members we would still be a little above Redis (33 vs 30). While a table grows, the old group array is still held, so the table's bytes are up to 1.5x for that time. The ~150 B per key for the entry and the Arc<RwLock<..>> (#297) is a separate item.

    2. The table

    • Chained groups, not open addressing. Every element sits in its home group or that group's overflow chain. That ownership is what gives an exact cursor (section 3) and a uniform random pick. A lookup reads one group line, compares 7 fingerprints in one u64 word, then reads one entry line, where the field and its value are side by side. Today a large-hash HGET touches the control bytes, the index slot, the entries Vec, the String block and the Arc block.
    • Home group = the top b bits of the hash, not the low bits (see section 3). The hasher is seeded randomly per table, as member_set::Table is today (ahash::RandomState::new()), so crafted fields cannot build long chains.
    • Load factor: grow above 0.875 of the main slots. Shrink below 1/8 (as shrink_if_sparse does today), to about 1/2 full, so a shrink and the next growth are 4x apart and cannot ping-pong.
    • Growth and shrink are incremental, as ShardMap::make_room/step_growth already do for the keyspace (Latency spikes while the keyspace grows: worst PING 74 ms vs Redis 20 ms during an 8M-key load #752): a new group array, a few elements moved per write, and lookups that miss in the new array look in the old one. Writes alone can leave a table mid-growth, so a table whose last write left it there is registered and finished by the background task, in bounded steps under the collection's write lock. The worst write then pays for allocating the zeroed array plus a fixed step of moves, never a pass over 3M entries. One-shot growth (today's IndexMap, which also reallocates its 176 MB entries Vec) is the latency cliff this removes.
    • Integer sets: keep the sorted array up to set-max-intset-entries (512, unchanged; its insert is a memmove). Past that, the inline slots cover integers of up to 7 digits at table cost only. Longer integers are 16 B entries.
    • Header size: HashFields must stay within its const assert (<= size_of::<IndexMap>()). The rarely used parts (old array during a resize, the overflow arena) sit behind one pointer.

    3. Cursor contract (for #770)

    /// Visits every element whose position is >= `cursor`, a group (and its chain) at a time,
    /// until at least `count` were visited. Returns the next cursor, 0 at the end.
    pub fn scan(&self, cursor: u64, count: usize, f: impl FnMut(E::Ref<'_>)) -> u64;
    • An element's position is hash >> 16 (48 bits, the cursor width helpers::scan_position uses today). With 2^b groups, group g holds exactly the positions [g << (48-b), (g+1) << (48-b)). So the cursor is a plain increasing number. Because the index is the top bits, a doubling splits group g into 2g and 2g+1 and keeps the order, so the reverse-binary trick that low-bit indexing needs is not required.
    • Guarantees: a growth between calls loses nothing and repeats nothing, because the old group boundaries are new group boundaries. A shrink can put the cursor inside a merged group, which is then visited whole: repeats are allowed, misses are not. During an incremental resize, a page visits the same range in both arrays, and an element is in exactly one of them.
    • Cost: proportional to the groups in the page, not to N. The len / 1024 minimum page in helpers::scan_page goes away for tables; packed forms are still returned whole.
    • Not kept: today's positions come from a fixed seed. A cursor taken before the upgrade, or on another server (restart, failover), is still accepted, but its guarantee no longer holds. This is the same as in Redis, where a cursor is only meaningful on the server that issued it.
    • COUNT and MATCH work as today. For HashEx, due fields are skipped per entry from the inline TTL instead of copying the hash (visible/shown).

    4. Random pick, TTLs, hot path, what stays

    • Uniform random (HRANDFIELD, SRANDMEMBER, SPOP): pick a uniformly random physical slot over the main groups and the arena, and retry while it is empty. The fill is at least 1/8, so a retry is expected about 1/fill times, with today's bounded fallback walk (random_bucket). Every element is equally likely, as with IndexMap::get_index today. The distinct-count paths keep their algorithms.
    • Field TTLs: a hash with TTLs keeps a TtlList of its TTL'd entries. Each entry knows its position in the list, as keyspace entries do. The sweep (field_expiry::sweep, Expiries::has_due with its earliest bound) walks the list, not the table. HGET on a HashEx then needs one lookup instead of two (is_field_expired looks up Expiries again today).
    • Hot path: small hashes and sets are not touched (they stay packed). Before any merge, scripts/perf/run.sh must show instructions per command for HGET, HSET, HSTRLEN, HEXISTS, HINCRBY, HDEL, SADD, SISMEMBER, SMISMEMBER and SREM at 10 / 128 / 512 elements (must be unchanged) and at 1k / 100k / 3M (must not rise). Cache misses at 3M are measured too. Also measured: HGETALL/SMEMBERS, SINTER/SUNIONSTORE/COPY (members are now copied rather than shared), HRANDFIELD/SPOP, DEL/UNLINK of a 3M hash, and save/load of a 3M hash.
    • Order: a table has none, as Redis's hashtable has none. One visible change: a hash that is a table only because of one long value currently keeps insertion order through IndexMap (HASH_ORDERED_FIELDS). It would lose it, as in Redis.
    • Unchanged: replies, OBJECT ENCODING (hashtable), the snapshot and AOF formats (written as count + pairs, in any order), the digest (a sum, independent of order: replication/digest.rs), and DUMP/RESTORE. MEMORY USAGE becomes groups x 64 + arena + sampled entries at their slab class size.

    5. Conversion thresholds

    • Packed -> table: as today. Hashes: more than hash-max-listpack-entries (512), a field or value longer than hash-max-listpack-value (64), or the block's u16 limit. Sets: set-max-intset-entries / set-max-listpack-entries (128) / set-max-listpack-value. The table is sized for the count at once.
    • Table -> packed: never on the command path, as in Redis and as today. Loading a snapshot or the AOF, and RESTORE, pick the form by size (with_capacity already does). The only hysteresis needed is the table's own: grow at 7/8, shrink at 1/8.

    6. Build order (small PRs, each based on master)

    1. CollectionTable alone, with no server change. Unit tests, plus a model test: random inserts, deletes and overwrites against a HashMap model, with checks taken mid-growth and mid-shrink. A scan-guarantee test with writes, growths and shrinks between calls, and a chi-square test of random. Measure lookup instructions and misses against HashTable<Arc<[u8]>> and IndexMap at 1k / 100k / 3M, and the worst single-insert time while filling to 3M.
    2. Sets on it. Suite 17's 1k and 100k rows get new recorded values; instructions as in section 4; SPOP/SRANDMEMBER distribution.
    3. Hashes on it, keeping the Expiries side map. Suite 19's table rows, the Memory: a big hash uses ~2.7x Redis's memory per field (3M fields: 296 MiB vs 109 MiB) #764 load, and write latency while loading 3M fields (max and p99.99 of HSET, plus PING from a second client, as Latency spikes while the keyspace grows: worst PING 74 ms vs Redis 20 ms during an 8M-key load #752 measured).
    4. Cursor (HSCAN/SSCAN/ZSCAN over a large collection are 10-20x slower than Redis (O(N^2/1024) full iteration) #770, @magic-peach, can start once step 1 lands): HSCAN/SSCAN call scan for tables. Tests of the guarantee across a resize; suite 01's scan rows; one page at COUNT 10 on 1M elements.
    5. Field TTLs inline with the per-hash TtlList. Suite 19's ttl rows, HEXPIRE/HTTL/HGET-on-HashEx instructions, sweep cost.
    6. Memory suites: add 1M-member rows to 17 and a 3M-field row to 19, and rows just before and just after a doubling, so the ceiling above is recorded and gated.

    7. Open questions (each needs a number first)

    • Maximum fill 0.75 / 0.82 / 0.875: overflow share, misses per HGET/SISMEMBER, bytes per element.
    • Entries in value_slab: compaction (active defrag) must be able to move a collection entry (find its slot and update it under the collection's lock), or keep those slabs out of evacuation. Otherwise entries go to the system allocator and pay its rounding.
    • Growth step per write, and when the background task finishes a resize; the worst-case write latency it gives.
    • Inline members of <= 7 bytes: memory gain against the cost of a tagged-slot branch on every compare.
    • Long integers as an 8-byte binary entry instead of text (19-digit IDs: 32 B class -> 16).
    • A hash with a few fields and one long value (Spring sessions, Small collections use significantly more memory than Redis compact encodings #297): keep it ordered and packed with the long value out of line, rather than a table?
    • Slab classes 8 B apart below 64 B (suite 19's 48 B entries fit; Memory: a big hash uses ~2.7x Redis's memory per field (3M fields: 296 MiB vs 109 MiB) #764's 11 B entries waste 5).

    Rejected:

    • Keep IndexMap/hashbrown and only inline the strings: still 48 B buckets plus spare room, and still no cursor.
    • Store a scan position per element (HSCAN/SSCAN/ZSCAN over a large collection are 10-20x slower than Redis (O(N^2/1024) full iteration) #770's first plan): +8 B per element and still a pass over N per page.
    • Redis-style chaining (bucket pointer + next pointer): ~19 B overhead, no fingerprints, a miss per hop.
    • Open addressing with a low-bit reverse-binary cursor: displaced elements do not belong to their bucket, so the cursor would have to rehash, and growth moves elements across buckets.
    • One-shot rehash: a pause proportional to N on a write.
    • A B-tree or radix tree for hashes: HGET becomes O(log n), slower on the hot path.
    • Packed blocks for large sizes: O(N) lookups.
  5. murtazayusuf commented on Nov 19, 2026

    @murtazayusuf
    ContributorAuthor

    Step 1 is up as #953: the table type on its own, unused by the server, with a model test, a scan-guarantee test and all tests clean under Miri. It is in review. Measured on a D4s_v5 (bytes per element as used_memory would count them, entries from slab classes):

    workload table today design estimate
    this issue's hash, 3M fields 29.7 103.3 ~30
    the same, just after a doubling 37.2 ~38.6
    suite 19 hash, 100k / 1k 61.8 / 65.7 138.8 / 176.5 ~61 / ~65
    14-byte members, 100k / 1k 29.8 / 33.7 54.3 / 66.8 ~29 / ~33
    integers, 100k / 1k 13.8 / 17.7 46.3 / 58.8 ~13 / ~17

    So the estimates hold to about a byte. The worst single insert while filling to 3M fields is under 1 ms (0.05-0.2 ms when the old array is freed off the command path), against 56-58 ms for today's hash and 98-100 ms for today's set, which is the pause this layout was meant to remove. A lookup hit costs 8-22 more instructions than today with fewer cache misses at 3M (2.23 last-level misses against 3.80); a miss costs more at 3M (0.5-0.7 against 0.1-0.2), which the next steps have to watch.

    Two of the open questions are answered:

    • Maximum fill: 0.875. It saves 7-10% of memory over 0.75 for about 0.1 more cache misses per hit at the fullest point; instructions do not change.
    • Entries and the slab: active defrag cannot move a collection entry today (it only walks the keyspace), and an entry in a shared slab class would pin that slab. But entries from the system allocator really take 32 bytes for an 11-15 byte entry while used_memory counts 11-15, so maxmemory would under-count. Decision: entries get their own slab pool that defrag skips, before sets move onto the table (a small step of its own); moving entries during defrag, using the scan cursor to walk a collection in batches, comes later.

    One change to the cursor contract in section 3, for @magic-peach: a page also stops after 10 × COUNT groups, so a long run of empty groups costs a bounded walk; the returned cursor is still a group boundary. One page at COUNT 10 on 1M elements reads 3.25 groups and returns 11.9 elements, each element exactly once over a full scan.

  6. added 2 commits that reference this issue on Nov 19, 2026
  7. murtazayusuf commented on Nov 19, 2026

    @murtazayusuf
    ContributorAuthor

    Scope note: #297 is closed (all four small encodings are merged), and its remainder moves here: the roughly 150 B a key that go to the entry and the lock around each collection. At 100k keys of ten elements that is what keeps a key at 1.5 to 2.3 times Redis (hash 494 B against 211, integer set 222 against 98, list 269 against 130, sorted set 274 against 186, RSS per key). It becomes a step of this issue after sets and hashes are on the table: one block for the keyspace entry and the collection's header, and a lock that does not cost an allocation per key.

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    memoryMemory use, slabs, evictionperformanceThroughput and latency

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions