What does one entry in an in-memory store cost beyond the bytes of its key and value?
answer
- the bytes are not the cost
- the store must find it again
- slot, header, stored key, rounding
- a lifetime may or may not add
- fixed per entry, not per byte
basics
~20 sAn entry also costs a slot in the store's lookup structure, a small header of lengths and pointers, a lifetime field or record if it carries one, and whatever the allocator rounds each of its several allocations up to.
solid answer
~50 sStoring an entry is not the same as storing its bytes. The store has to find it again, so the entry occupies a slot in a lookup structure, and that structure is deliberately kept less than full, so the slot costs more than one pointer's worth. The entry carries a header — lengths, flags, references to the key and the value — and the key's own bytes are kept, because the store must confirm a match rather than guess at one. If the entry carries a lifetime, the deadline has to live somewhere: some stores reserve a field in every entry, others keep a separate structure listing only the entries that have one. Finally the allocator rounds every request up to a step it supports, and there is usually more than one allocation per entry. The fixed part is commonly tens of bytes — invisible beside a 10 KB value, dominant beside a 20-byte one.
go deeper
Recall that an entry is the key, the value and the store's bookkeeping together, and be able to name two costs beyond the payload — a lookup slot and the key bytes themselves. Saying "more than its bytes, and it is charged per entry" already beats most answers.
Explain the mechanics: why the lookup structure is kept less than full, why the key is kept rather than fingerprinted, and why the allocator rounds several allocations per entry separately. Then say why all of it is invisible beside a large value and dominant beside a small one.
Show that you have looked. Say what you would measure to turn this from a list into a number for your own entries, and flag where implementations diverge — particularly whether a lifetime costs anything extra — rather than presenting one store's shape as the general model.
Treat the fixed per-entry cost as an input to a capacity model that has to survive an upgrade and a migration. The interesting question is not what the components are but who re-derives the constant, how often, and what breaks silently when nobody does.
## What an entry actually is In an in-memory store, an **entry** is not a pair of byte strings. It is the key, the value, and the store's own bookkeeping for that pair taken together. That bookkeeping exists because the store must do more than hold bytes: it has to find the value again from the key, tell a genuine match from two keys that landed in the same place, know how long each part is, and — when the entry carries a lifetime — know when the deadline falls. All of that is memory, and nearly all of it is charged **per entry**, not per byte. A cost that scales with the number of entries behaves completely differently from one that scales with the size of the data, which is the whole reason this is a subject. ## Where the memory goes | Component | What it is | What it scales with | |---|---|---| | Lookup slot | A position in the structure that maps a key to its entry | Entry count | | Entry header | Lengths, flags and references to the key and the value | Entry count | | The stored key | The key bytes the store keeps to confirm a match | Key length | | Lifetime field or record | Where the deadline lives, when the entry carries one | Entries that carry a lifetime | | Allocator rounding | Each request rounded up to the next step the allocator serves | Allocations per entry | ### The lookup slot The store keeps a structure that turns a key into a position. Whatever it is, it is deliberately kept **less than full**, because one packed to capacity degrades badly, so an entry's real share is its own slot plus a proportion of the empty ones held beside it. It also grows in steps rather than smoothly, so the marginal cost of one more entry is not perfectly flat. The slot is a fixed charge per entry with no relationship to the size of the value. ### The header, and the key it points at Every entry carries a small descriptor: the length of the key, the length of the value, a few flags, and references reaching both. Some stores place small values directly inside that descriptor; others always reach them through a reference. The key's own bytes are held too — a store that kept only a fingerprint could not tell a real match from a collision, so it keeps enough of the key to confirm one, and in practice that is the key itself. An estimate built from value sizes alone has already lost the key bytes and their share of the rounding. ### The lifetime, when there is one Here implementations genuinely diverge, and an honest answer says so. Some stores reserve a deadline field in every entry's header whether it is used or not, so attaching a lifetime costs nothing beyond what was already reserved. Others keep a separate structure listing only the entries that have deadlines, so attaching one adds a second record. Neither is *the* model, and the planning consequence is identical: measure entries shaped the way production shapes them. ### Allocator rounding Memory does not arrive in arbitrary sizes. The allocator serves a request from a step it supports and rounds up to it, so a request for 33 bytes may occupy noticeably more. A store typically makes **more than one allocation per entry**, each rounded separately, so the rounding is charged repeatedly, and the size of the step differs by allocator, by build and by store. Schemes exist that attack this overhead directly; they are a separate subject. The point here is that the rounding is real and invisible in payload arithmetic. ## Why the size of the value decides whether this matters The fixed part is commonly measured in tens of bytes. In practice: - Beside a 10 KB value it is a rounding error, and payload arithmetic is roughly right. - Beside a 20-byte value it is several times the payload, so payload arithmetic is wrong by a multiple rather than a percentage. - The crossover is not a universal number — it is the ratio of your measured fixed part to your own payload size. ## What varies between stores, and what does not - **Varies:** the size of the entry header and what it contains. - **Varies:** whether attaching a lifetime costs anything at all. - **Varies:** how coarse the allocator's rounding step is. - **Varies:** how much spare capacity the lookup structure carries per entry. - **Varies:** whether small values sit inside the descriptor or are reached through a reference. - **Does not vary:** that there is a fixed part, charged per entry rather than per byte. - **Does not vary:** that it is invisible in the sizes of the things you chose to store. ## Getting from the list to a number Because every component above differs by store, by build and by entry shape, a figure read somewhere else describes somebody else's store. Three steps replace it: 1. Write a representative sample of your own entries — real key lengths, real value sizes, a lifetime attached if production attaches one. 2. Read the store's own accounting of memory attributed to entries before and after, and divide the difference by the count. 3. Record the store, the version, the entry shape and the date beside the number, so the next reader knows what it measures. That number is specific to the thing you are about to run, which is the only kind worth planning with.
- Does attaching a lifetime to an entry always make it cost more memory?No, and this is one of the places stores genuinely differ. Where the deadline sits in a header field that exists whether it is used or not, the marginal cost is essentially nothing. Where the store keeps a separate structure listing entries that have deadlines, attaching one adds a record there. The only way to know which you are on is to measure the same entries with and without a lifetime attached.
- Which parts of the per-entry cost grow with key length and which stay fixed?The stored key bytes grow with key length, and so does the rounding step applied to whatever allocation holds them. The lookup slot, the header fields and the references do not — they are the same whether the key is eight characters or eighty. That is why the decomposition matters: two entries with identical values can cost visibly different amounts because of the key alone, while both still carry the same fixed part.
- Why does the store keep the key's bytes rather than just its computed position?Because a computed position is not proof of identity. Two different keys can reach the same position, and a store that had discarded the key bytes could not tell which entry it had found. Keeping the key lets the store confirm a match. The cost is that key bytes are part of every entry's footprint, which payload arithmetic based on value sizes quietly omits.
A parcel service charges for the box, the label and the shelf position, not only for the thing inside. Ship one grand piano and the packaging disappears into the price. Ship a hundred thousand postage stamps, each in its own box on its own shelf slot, and the packaging is the shipment.
saying these in an interview costs you the question
- Says an entry costs its key bytes plus its value bytes and nothing more.
- Assumes only the value is stored and the key is discarded after lookup.
- Quotes a single per-entry overhead figure as if it held for every in-memory store.
- Believes attaching a lifetime is free on every store in this class.
- Dismisses allocator rounding as too small to affect a total.
- Thinks per-entry overhead scales with how large the values are.