Key-Value Stores

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.

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

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

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