--- title: 'Key-Value Stores' source: 'https://academia.sh/en/courses/nosql/key-value-stores' course: 'Non-Relational Data Models' language: en updated: '2026-08-23T07:00:45+00:00' license: 'CC BY-SA 4.0' --- # Key-Value Stores The contract and cost of the simplest access model: the value's opacity to the store, measuring the same member page in the relational schema and the key-value model by round trips and records touched, the loss of the ability to query on a field and the application-maintained secondary index being read as a whole, and the trade-off key design sets up between write amplification and the number of read round trips. The Relational Database Administration course closed without asking a single question about the model itself: tables, rows, schema, and transactions were taken as given, and everything measured was measured inside that model. This course makes the given itself the subject, starting with the simplest case. A key-value store defines a single contract: you give a key, you get a value. The store knows nothing about the value. The naming of the families and their comparison by access pattern across four types was established in the Scaling the Data Layer course: there, a semester scan took 3,001 requests in a key-value store while finishing in a single request in a document or wide-column store, and a three-step traversal stayed at a single request in a graph store regardless of depth. That measurement is not repeated here — it is taken as input. This lesson's question is narrower and looks at **the data model itself**: how a store that cannot see inside the value carries library catalog and loan data, which work it makes cheaper, and which capability it loses. ## The Model's Contract In the key-value model, a record has two parts: a unique key and a byte sequence that carries no meaning for the store. The store knows the key, not the value. Three consequences follow from this single sentence. No condition can be written against the value and no part of the value can be updated, because the store recognizes no concept of a field. There is no operation for joining two records either, because a join is defined by matching fields. What is gained in return is a constant step: once the key is known, the record arrives in a single round trip, regardless of the number of records. For the measurement, the library data is built in both models at once; the relational side is genuinely built with `node:sqlite`. **NS1:** the catalog carries 20,000 members and each member has between 1 and 11 loans; the total is 119,993 loans. **NS2:** values are serialized with JSON; bytes read and written are counted from this representation, and on the relational side the result set is converted to the same representation. ```js // kv/model.mjs — the same member page measured in the relational schema and the // key-value model. The relational side is built with node:sqlite; the numbers are // independent of the run. import { DatabaseSync } from "node:sqlite"; const MEMBERS = 20_000, CITIES = ["Ankara", "Istanbul", "Izmir", "Bursa", "Konya"]; function* members() { // member i has 1 + (i % 11) loans for (let i = 1; i <= MEMBERS; i += 1) { const loans = Array.from({ length: 1 + (i % 11) }, (_, j) => ({ loan_id: i * 100 + j, book_id: 1 + ((i * 7 + j * 13) % 200_000), pickup_date: `2024-${String(1 + ((i + j) % 12)).padStart(2, "0")}-15`, penalty_cents: (i * 37 + j * 11) % 900, })); yield { member_id: i, name: `Member ${i}`, city: CITIES[i % 5], loans, penalty_cents: loans.reduce((t, o) => t + o.penalty_cents, 0) }; } } class KeyValueStore { // the value is a byte sequence to the store #table = new Map(); roundTrips = 0; records = 0; bytes = 0; write(key, value) { this.roundTrips += 1; this.records += 1; const s = JSON.stringify(value); this.bytes += Buffer.byteLength(s); this.#table.set(key, s); } read(key) { this.roundTrips += 1; const s = this.#table.get(key); if (s === undefined) return undefined; this.records += 1; this.bytes += Buffer.byteLength(s); return JSON.parse(s); } resetCounters() { this.roundTrips = 0; this.records = 0; this.bytes = 0; } } const db = new DatabaseSync(":memory:"); db.exec(`CREATE TABLE member (member_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL, penalty_cents INTEGER NOT NULL); CREATE TABLE loan (loan_id INTEGER PRIMARY KEY, member_id INTEGER NOT NULL, book_id INTEGER NOT NULL, pickup_date TEXT NOT NULL, penalty_cents INTEGER NOT NULL);`); const insertM = db.prepare("INSERT INTO member VALUES (?,?,?,?)"); const insertL = db.prepare("INSERT INTO loan VALUES (?,?,?,?,?)"); const store = new KeyValueStore(); db.exec("BEGIN"); for (const m of members()) { insertM.run(m.member_id, m.name, m.city, m.penalty_cents); for (const o of m.loans) insertL.run(o.loan_id, m.member_id, o.book_id, o.pickup_date, o.penalty_cents); store.write(`member:${m.member_id}`, m); // the same information as a single value } db.exec("COMMIT"); db.exec("CREATE INDEX loan_member ON loan(member_id); CREATE INDEX member_penalty ON member(penalty_cents);"); const bytes = (x) => Buffer.byteLength(JSON.stringify(x)); const TARGET = 4242; console.log(`model: ${MEMBERS} members, ${db.prepare("SELECT count(*) n FROM loan").get().n} loans; ` + `target member ${TARGET}, loan count ${1 + (TARGET % 11)}`); console.log(db.prepare("EXPLAIN QUERY PLAN SELECT * FROM loan WHERE member_id = ?").all()[0].detail); const row = []; { const m = db.prepare("SELECT member_id, name, city, penalty_cents FROM member WHERE member_id = ?").get(TARGET); const o = db.prepare("SELECT loan_id, book_id, pickup_date, penalty_cents FROM loan WHERE member_id = ?").all(TARGET); row.push(["relational, two queries", 2, 1 + o.length, bytes(m) + bytes(o)]); } { const r = db.prepare(`SELECT m.name, m.city, m.penalty_cents, o.loan_id, o.book_id, o.pickup_date FROM member m JOIN loan o ON o.member_id = m.member_id WHERE m.member_id = ?`).all(TARGET); row.push(["relational, single join", 1, r.length, bytes(r)]); } { store.resetCounters(); const v = store.read(`member:${TARGET}`); row.push([`key-value, single key (${v.loans.length} loans)`, store.roundTrips, store.records, store.bytes]); } console.log(`\n${"path".padEnd(40)}${"round trip".padStart(11)}${"record".padStart(7)}${"byte".padStart(7)}`); for (const [a, g, k, b] of row) console.log(a.padEnd(40) + String(g).padStart(11) + String(k).padStart(7) + String(b).padStart(7)); ``` ``` model: 20000 members, 119993 loans; target member 4242, loan count 8 SEARCH loan USING INDEX loan_member (member_id=?) path round trip record byte relational, two queries 2 9 732 relational, single join 1 8 953 key-value, single key (8 loans) 1 1 741 ``` The numbers are of the **measurement** class. The member page is a single round trip, a single record in the key-value model. In the relational schema, the same page either asks for two queries and nine records, or is reduced to a single join; the join brings the round trip down to one but, because it repeats the member's fields on every loan row, it raises the bytes carried from 732 to 953. The key-value value is 741 bytes: the same information, without repetition, in one piece. The gain here comes not from the join's absence but from modeling around the unit of reading: the value is the whole of what the application wants in one pass. The same thing can be done in a relational schema too — that is the denormalization measured in the Data Modeling and Relational Theory course — but there it is a choice; here it is the model's only shape. ## The Loss of Queryability The library's second question is: who are the members whose penalty exceeds a threshold. In the relational schema this calls for an index on a field of the member table; the key-value store has no such concept of a field. ```js // kv/query.mjs — three paths for the "members whose penalty exceeds a threshold" // question on the same data. The generator is identical to kv/model.mjs; the block // runs on its own. import { DatabaseSync } from "node:sqlite"; const MEMBERS = 20_000, CITIES = ["Ankara", "Istanbul", "Izmir", "Bursa", "Konya"], THRESHOLD = 8000; function* members() { for (let i = 1; i <= MEMBERS; i += 1) { const loans = Array.from({ length: 1 + (i % 11) }, (_, j) => ({ loan_id: i * 100 + j, book_id: 1 + ((i * 7 + j * 13) % 200_000), pickup_date: `2024-${String(1 + ((i + j) % 12)).padStart(2, "0")}-15`, penalty_cents: (i * 37 + j * 11) % 900, })); yield { member_id: i, name: `Member ${i}`, city: CITIES[i % 5], loans, penalty_cents: loans.reduce((t, o) => t + o.penalty_cents, 0) }; } } class KeyValueStore { #table = new Map(); roundTrips = 0; records = 0; bytes = 0; write(a, d) { const s = JSON.stringify(d); this.#table.set(a, s); } read(a) { this.roundTrips += 1; const s = this.#table.get(a); if (s === undefined) return undefined; this.records += 1; this.bytes += Buffer.byteLength(s); return JSON.parse(s); } keys() { return [...this.#table.keys()].filter((a) => a.startsWith("member:")); } reset() { this.roundTrips = 0; this.records = 0; this.bytes = 0; } } const db = new DatabaseSync(":memory:"); db.exec(`CREATE TABLE member (member_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL, penalty_cents INTEGER NOT NULL);`); const insert = db.prepare("INSERT INTO member VALUES (?,?,?,?)"); const store = new KeyValueStore(); const index = []; // the secondary index the application maintains by hand db.exec("BEGIN"); for (const m of members()) { insert.run(m.member_id, m.name, m.city, m.penalty_cents); store.write(`member:${m.member_id}`, m); index.push([m.penalty_cents, m.member_id]); } db.exec("COMMIT"); db.exec("CREATE INDEX member_penalty ON member(penalty_cents);"); index.sort((x, y) => x[0] - y[0]); store.write("index:penalty", index); // the index is also a value: read as a whole const bytes = (x) => Buffer.byteLength(JSON.stringify(x)); const row = []; { const r = db.prepare("SELECT member_id FROM member WHERE penalty_cents > ?").all(THRESHOLD); row.push(["relational, penalty index", 1, r.length, bytes(r), r.length]); } { store.reset(); const found = []; for (const a of store.keys()) { const m = store.read(a); if (m.penalty_cents > THRESHOLD) found.push(m.member_id); } row.push(["key-value, key scan", store.roundTrips, store.records, store.bytes, found.length]); } { store.reset(); const d = store.read("index:penalty"); const found = d.filter(([c]) => c > THRESHOLD).map(([, id]) => store.read(`member:${id}`).member_id); row.push(["key-value, application index", store.roundTrips, store.records, store.bytes, found.length]); } console.log(`model: ${MEMBERS} members, threshold ${THRESHOLD} cents; ` + `relational plan: ${db.prepare("EXPLAIN QUERY PLAN SELECT member_id FROM member WHERE penalty_cents > ?").all()[0].detail}`); console.log(`size of the index:penalty value ${bytes(index)} bytes, entry count ${index.length}`); console.log(`\n${"path".padEnd(32)}${"round trip".padStart(11)}${"record".padStart(7)}${"bytes read".padStart(13)}${"result".padStart(8)}`); for (const [a, g, k, b, n] of row) console.log(a.padEnd(32) + String(g).padStart(11) + String(k).padStart(7) + String(b).padStart(13) + String(n).padStart(8)); ``` ``` model: 20000 members, threshold 8000 cents; relational plan: SEARCH member USING COVERING INDEX member_penalty (penalty_cents>?) size of the index:penalty value 243132 bytes, entry count 20000 path round trip record bytes read result relational, penalty index 1 359 6980 359 key-value, key scan 20000 20000 11631090 359 key-value, application index 360 360 592319 359 ``` The numbers are of the **measurement** class. All three paths find the same 359 members; the difference is where the work happens. A covering index lets the relational engine touch only the 359 matching records in a single round trip, carrying 6,980 bytes. In the key-value store the filtering happens in the application, so the whole key space is walked: 20,000 round trips and 11.6 MB — roughly seventeen hundred times as much data as the result, read just to find the result. The third row carries the real lesson. When the application keeps a list sorted by penalty value and writes it to a single key, the round trips drop from 20,000 to 360. But this list is not an index, it is a value: all 243,132 bytes of it are read whole on every query. A relational index is a tree the engine can descend into; an application index can only be read and parsed whole. The bytes read therefore stay at 592,319 — roughly 85 times the relational path. ## Key Design Is the Only Setting In a relational schema, the designer has tables, columns, constraints, and indexes at hand. In the key-value model there is a single setting: what the key is, and where the value's boundary runs. Adding one loan means read-modify-write in the whole-value design: the whole value is read, a record is appended to the array, the whole value is written back. In the separate-key design, only the new record is written. ```js // kv/key-design.mjs — adding a single loan under two key designs, and the cost the // same designs impose on reading a member page. All byte counts come from real // serialization. class KeyValueStore { #table = new Map(); #ordered = false; roundTrips = 0; records = 0; bytesRead = 0; bytesWritten = 0; constructor(ordered) { this.#ordered = ordered; } write(a, d) { const s = JSON.stringify(d); this.roundTrips += 1; this.records += 1; this.bytesWritten += Buffer.byteLength(a) + Buffer.byteLength(s); this.#table.set(a, s); } read(a) { this.roundTrips += 1; const s = this.#table.get(a); if (s === undefined) return undefined; this.records += 1; this.bytesRead += Buffer.byteLength(s); return JSON.parse(s); } prefix(p) { // only exists in an ordered key space if (!this.#ordered) throw new Error("no prefix scan in a hashed key space"); this.roundTrips += 1; const c = []; for (const [a, s] of [...this.#table].sort(([x], [y]) => (x < y ? -1 : x > y ? 1 : 0))) if (a.startsWith(p)) { this.records += 1; this.bytesRead += Buffer.byteLength(s); c.push(JSON.parse(s)); } return c; } reset() { this.roundTrips = 0; this.records = 0; this.bytesRead = 0; this.bytesWritten = 0; } } const loan = (i, j) => ({ loan_id: i * 1000 + j, book_id: 1 + ((i * 7 + j * 13) % 200_000), pickup_date: `2024-${String(1 + ((i + j) % 12)).padStart(2, "0")}-15`, penalty_cents: (i * 37 + j * 11) % 900 }); console.log(`adding a single loan (the new record itself is ${Buffer.byteLength(JSON.stringify(loan(1, 0)))} bytes)`); console.log(`${"loan count k".padStart(14)}${"whole value: written".padStart(25)}` + `${"factor".padStart(8)}${"separate key: written".padStart(23)}${"factor".padStart(8)}`); for (const k of [1, 8, 64, 512]) { const whole = new KeyValueStore(true), separate = new KeyValueStore(true); const m = { member_id: 7, name: "Member 7", city: "Izmir", loans: Array.from({ length: k }, (_, j) => loan(7, j)) }; whole.write("member:0007", m); for (let j = 0; j < k; j += 1) separate.write(`member:0007:loan:${String(j).padStart(6, "0")}`, loan(7, j)); const next = loan(7, k); whole.reset(); separate.reset(); const v = whole.read("member:0007"); v.loans.push(next); whole.write("member:0007", v); // read-modify-write separate.write(`member:0007:loan:${String(k).padStart(6, "0")}`, next); // only the new record console.log(String(k).padStart(14) + String(whole.bytesWritten).padStart(25) + (whole.bytesWritten / separate.bytesWritten).toFixed(1).padStart(8) + String(separate.bytesWritten).padStart(23) + "1.0".padStart(8)); } const K = 64; const setup = (ordered) => { const d = new KeyValueStore(ordered); for (let j = 0; j < K; j += 1) d.write(`member:0007:loan:${String(j).padStart(6, "0")}`, loan(7, j)); d.write("member:0007", { member_id: 7, name: "Member 7", city: "Izmir" }); d.write("member:0007:loan-list", Array.from({ length: K }, (_, j) => j)); d.reset(); return d; }; console.log(`\nreading the same member's ${K}-loan page`); console.log(`${"key space".padEnd(34)}${"round trip".padStart(11)}${"record".padStart(7)}${"bytes read".padStart(13)}`); const s = setup(true); s.read("member:0007"); s.prefix("member:0007:loan:"); console.log("ordered, prefix scan".padEnd(34) + String(s.roundTrips).padStart(11) + String(s.records).padStart(7) + String(s.bytesRead).padStart(13)); const h = setup(false); h.read("member:0007"); for (const j of h.read("member:0007:loan-list")) h.read(`member:0007:loan:${String(j).padStart(6, "0")}`); console.log("hashed, application key list".padEnd(34) + String(h.roundTrips).padStart(11) + String(h.records).padStart(7) + String(h.bytesRead).padStart(13)); ``` ``` adding a single loan (the new record itself is 74 bytes) loan count k whole value: written factor separate key: written factor 1 223 2.3 99 1.0 8 767 7.7 100 1.0 64 5128 51.8 99 1.0 512 40459 400.6 101 1.0 reading the same member's 64-loan page key space round trip record bytes read ordered, prefix scan 2 65 4966 hashed, application key list 66 66 5149 ``` The top table shows write amplification: the information added is 74 bytes on every row, but the bytes written in the whole-value design climb from 223 to 40,459. The factor grows in direct proportion to the member's loan count and reaches 400.6 at 512 loans. In the separate-key design, the bytes written do not change as the member grows: between 99 and 101 bytes, a factor of 1. The bottom table shows the cost. Once loans are spread across separate keys, the member page no longer arrives in a single round trip. In an ordered key space — stores that keep keys in lexicographic order — a prefix scan counts as a single request and finishes in 2 round trips. In a hashed key space there is no concept of a prefix, because consecutive keys do not land in consecutive places; the application must also keep a list of keys and fetch every loan one at a time: 66 round trips. The same 65 records, the same order of magnitude in bytes, thirty-three times the round trips. Read together, the two tables yield the model's single rule: in a key-value store, the boundary of the value is the boundary of the application's unit of access. Keep the boundary wide and reading drops to a single round trip while write amplification grows; keep it narrow and writing gets cheap while reading becomes dependent on whether the key space is ordered. The decision is made through key naming, not schema; changing it later means rewriting all the data. ## Summary - The key-value model defines a single contract: give a key, get a value. The store cannot see inside the value; there is therefore no condition on a field, no partial update, and no join. - The member page is 1 round trip and 1 record in the key-value model; in the relational schema it is 2 round trips and 9 records, or 1 round trip and 8 records with a single join, at 953 bytes instead of 732. - Querying on a field disappears: the 359 members whose penalty exceeds the threshold are found in 1 round trip and 6,980 bytes with a relational index, while a key scan costs 20,000 round trips and 11.6 MB. - The secondary index the application keeps is not a tree but a value: it brings the round trips down to 360, but reads the 243,132-byte list whole on every query and leaves a window of inconsistency with the record. - Key design is the only setting: a 74-byte addition in the whole-value design writes 40,459 bytes for a member with 512 loans (a factor of 400.6), while the separate-key design keeps the factor at 1 — but then the member page costs 2 round trips in an ordered key space and 66 in a hashed one. ## Next Step Every gain in this lesson rested on one assumption: what the application wants is always a single whole with a known key. The moment the assumption fails, the model collapses — filtering on a field inside the value means 20,000 round trips. The question left standing is what would change if the store could see inside the value. The next lesson takes up that family and measures two things: the difference between a nested structure arriving in a single read and the same data assembled through a relational join, and the load that schema flexibility shifts onto the read side — the cost of checking, on every read, whether a field exists at all.