Cache Key Design

In the previous lesson, the key took three different forms: first book:7, then a form carrying the version, then a list key carrying the branch’s generation counter. Each time, the key was built by hand through string concatenation.

The key is the cache’s only addressing mechanism. When it is built wrong, the cache silently returns the wrong response — it does not error, it does not slow down, it just serves someone else’s data. This lesson demonstrates, by running them, two flaws of hand concatenation, then writes a generator that treats the key as a design object.

Two Flaws

The measurements run against a seven-book catalog. One of the books carries a colon in its title; this is necessary to bring out the first flaw.

# setup.sh — book data for search and list queries (M16/K04 seed)
rm -f library.db
sqlite3 library.db <<'SQL'
CREATE TABLE branch (branch_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL);
CREATE TABLE book (book_id INTEGER PRIMARY KEY, title TEXT NOT NULL, author TEXT NOT NULL,
                    publication_year INTEGER, branch_id INTEGER REFERENCES branch(branch_id));
INSERT INTO branch VALUES (1,'Central','Ankara'),(2,'Bahcelievler','Ankara'),(3,'Kadikoy','Istanbul');
INSERT INTO book VALUES
  (1,'Blindness','José Saramago',1995,1),(2,'The Disconnected','Oğuz Atay',1972,1),
  (3,'The Book of Sand','Jorge Luis Borges',1975,2),(4,'Yaban','Yakup Kadri',1932,2),
  (5,'Silent House','Orhan Pamuk',1983,3),(6,'Motherland Hotel','Yusuf Atılgan',1973,3),
  (7,'Sand: Borges Selection','Anthology',2010,1);
SQL
sqlite3 library.db "SELECT branch_id, count(*) FROM book GROUP BY branch_id;"

1|3
2|2
3|2

The block below runs two scenarios. In the first, the search criteria are concatenated with a colon; in the second, the branch list key carries only the page number.

// collision.mjs — two flaws of a hand-concatenated key: collision and tenant leak
import { DatabaseSync } from "node:sqlite";

const db = new DatabaseSync("library.db");
const search = (title, author) => db.prepare(
  "SELECT title FROM book WHERE title LIKE ? AND author LIKE ? ORDER BY book_id")
  .all(`%${title}%`, `%${author}%`).map((k) => k.title);
const branchList = (branchId, page) => db.prepare(
  "SELECT title FROM book WHERE branch_id = ? ORDER BY book_id LIMIT 2 OFFSET ?")
  .all(branchId, (page - 1) * 2).map((k) => k.title);

const box = new Map();
const cached = (key, produce) => {
  if (box.has(key)) return { key, result: box.get(key), source: "cache" };
  const result = produce();
  box.set(key, result);
  return { key, result, source: "origin" };
};

console.log("--- collision: two different queries land on the same key");
const a = cached(`search:Sand:Borges`, () => search("Sand", "Borges"));
const b = cached(`search:Sand:Borges`, () => search("Sand: Borges", ""));
console.log(`A title="Sand" author="Borges"   key=${a.key} ${a.source}: ${a.result.join(", ")}`);
console.log(`B title="Sand: Borges" author=""  key=${b.key} ${b.source}: ${b.result.join(", ")}`);
console.log(`The correct result B would get from the origin: ${search("Sand: Borges", "").join(", ")}`);

console.log("--- tenant leak: the key does not carry branch information");
const s2 = cached("list:page:1", () => branchList(2, 1));
const s3 = cached("list:page:1", () => branchList(3, 1));
console.log(`branch 2 page 1 -> ${s2.source}: ${s2.result.join(", ")}`);
console.log(`branch 3 page 1 -> ${s3.source}: ${s3.result.join(", ")}`);
const correct = branchList(3, 1);
const leaked = s3.result.filter((x) => !correct.includes(x));
console.log(`records served to branch 3 that do not belong to branch 3: ${leaked.length} -> ${leaked.join(", ")}`);
db.close();

--- collision: two different queries land on the same key
A title="Sand" author="Borges"   key=search:Sand:Borges origin: The Book of Sand
B title="Sand: Borges" author=""  key=search:Sand:Borges cache: The Book of Sand
The correct result B would get from the origin: Sand: Borges Selection
--- tenant leak: the key does not carry branch information
branch 2 page 1 -> origin: The Book of Sand, Yaban
branch 3 page 1 -> cache: The Book of Sand, Yaban
records served to branch 3 that do not belong to branch 3: 2 -> The Book of Sand, Yaban

The first flaw is a collision: the moment the character used as the separator also occurs inside a value, two different sets of criteria produce the same string. The second search got the first one’s answer from the cache, and no one noticed.

The second flaw is a tenant leak. In the library system, a branch is a tenant: each branch sees only its own data. Because the key did not carry the branch, the Kadikoy branch’s list showed Bahcelievler’s books. The authorization check set up server-side in the Authentication and Authorization course is not in play here at all; the query never ran, the response came from the cache. The cache is the one layer that can walk around behind an authorization check.

The Parts of a Key

Both flaws came from building the key by hand. A single function that generates the key gathers the rules in one place.

// key.mjs — a function that generates a cache key from namespace, tenant, and canonical criteria
import { createHash } from "node:crypto";

const SCHEMA = 1;                                   // key schema version
const escape = (m) => encodeURIComponent(String(m));

export function generateKey({ namespace, operation, tenant, generation = 1, criteria = {} }) {
  const criteriaString = Object.entries(criteria)
    .filter(([, v]) => v !== undefined && v !== null && v !== "")
    .sort(([a], [b]) => (a < b ? -1 : 1))          // order-independent: the same criteria set gives the same key
    .map(([k, v]) => `${escape(k)}=${escape(v)}`)
    .join("&");
  const body = `${escape(namespace)}:s${SCHEMA}:g${generation}:t${escape(tenant)}:${escape(operation)}`;
  const tail = criteriaString.length <= 48 ? criteriaString : `c_${createHash("sha256").update(criteriaString).digest("hex").slice(0, 16)}`;
  return tail ? `${body}:${tail}` : body;
}

if (import.meta.url === `file://${process.argv[1]}`) {
  const A = (o) => generateKey({ namespace: "library", generation: 4, ...o });

  console.log("--- the two colliding queries are now in separate keys");
  console.log(A({ operation: "search", tenant: "branch-2", criteria: { title: "Sand", author: "Borges" } }));
  console.log(A({ operation: "search", tenant: "branch-2", criteria: { title: "Sand: Borges", author: "" } }));

  console.log("--- tenant in the key: same query, different branch");
  console.log(A({ operation: "list", tenant: "branch-2", criteria: { page: 1 } }));
  console.log(A({ operation: "list", tenant: "branch-3", criteria: { page: 1 } }));

  console.log("--- criteria order does not change the key");
  const s1 = A({ operation: "search", tenant: "branch-1", criteria: { author: "Atay", title: "The Disconnected" } });
  const s2 = A({ operation: "search", tenant: "branch-1", criteria: { title: "The Disconnected", author: "Atay" } });
  console.log(`${s1}\nequal: ${s1 === s2}`);

  console.log("--- a long criteria set gets summarized");
  const long = A({ operation: "search", tenant: "branch-1", criteria: {
    title: "The Disconnected", author: "Oğuz Atay", yearFrom: 1970, yearTo: 1980,
    lang: "tr", status: "on_shelf", sort: "title", page: 3 } });
  console.log(`${long}\nlength=${long.length}`);
}

--- the two colliding queries are now in separate keys
library:s1:g4:tbranch-2:search:author=Borges&title=Sand
library:s1:g4:tbranch-2:search:title=Sand%3A%20Borges
--- tenant in the key: same query, different branch
library:s1:g4:tbranch-2:list:page=1
library:s1:g4:tbranch-3:list:page=1
--- criteria order does not change the key
library:s1:g4:tbranch-1:search:author=Atay&title=The%20Disconnected
equal: true
--- a long criteria set gets summarized
library:s1:g4:tbranch-1:search:c_648d4755bc125b8e
length=49

The key has five parts. The namespace separates different applications that share the same cache store. The schema version versions the key structure itself: when the value format changes, this number is incremented, and every entry in the old format becomes unreachable in a single move. The generation carries the bulk invalidation from the previous lesson. The tenant places the authorization boundary inside the key. The operation and the canonical criteria are the query’s identity.

Canonical form is achieved with three rules: empty criteria are dropped, criteria are sorted by name, and the name and value are escaped. Sorting keeps the same query from producing two separate entries when its criteria arrive in a different order. Escaping makes the collision in the first flaw structurally impossible: the colon inside a value becomes %3A and stops being a separator.

The last part is the length limit. When the criteria set grows long, it gets summarized, but the key’s readable body is preserved. This distinction is valuable at operating time: which application, which branch, and which operation an entry in the cache belongs to can be seen just by looking at the key; only which criteria produced it stays hidden.

Extra Fields and Missing Fields

Which fields the key carries is a correctness decision, and it can break in both directions.

// cardinality.mjs — extra fields in the key break the hit ratio, missing fields break correctness
import { DatabaseSync } from "node:sqlite";
import { generateKey } from "./key.mjs";

const db = new DatabaseSync("library.db");
const list = (branchId, page) => db.prepare(
  "SELECT title FROM book WHERE branch_id = ? ORDER BY book_id LIMIT 2 OFFSET ?")
  .all(branchId, (page - 1) * 2).map((k) => k.title).join(", ");

const requests = [];                               // 400 requests, 3 branches x 2 pages
for (let i = 0; i < 400; i++) requests.push([(i % 3) + 1, (i % 2) + 1, `r-${i}`]);

function run(name, makeKey) {
  const box = new Map();
  const m = { hit: 0, miss: 0, wrong: 0 };
  for (const [branchId, page, requestId] of requests) {
    const key = makeKey(branchId, page, requestId);
    let value;
    if (box.has(key)) { m.hit += 1; value = box.get(key); }
    else { m.miss += 1; value = list(branchId, page); box.set(key, value); }
    if (value !== list(branchId, page)) m.wrong += 1;
  }
  const ratio = ((m.hit / requests.length) * 100).toFixed(1);
  return `${name.padEnd(29)}${String(m.hit).padStart(8)}${String(m.miss).padStart(8)}` +
    `${(ratio + "%").padStart(10)}${String(m.wrong).padStart(9)}${String(box.size).padStart(8)}`;
}

const base = { namespace: "library", operation: "list", generation: 1 };
console.log(["key form", "hits", "misses", "ratio", "wrong", "entries"]
  .map((h, i) => (i === 0 ? h.padEnd(29) : h.padStart(i === 3 ? 10 : i === 4 ? 9 : 8))).join(""));
console.log(run("correct (tenant + criteria)", (b, p) =>
  generateKey({ ...base, tenant: `branch-${b}`, criteria: { page: p } })));
console.log(run("extra field (request id)", (b, p, r) =>
  generateKey({ ...base, tenant: `branch-${b}`, criteria: { page: p, request: r } })));
console.log(run("missing field (no tenant)", (b, p) =>
  generateKey({ ...base, tenant: "shared", criteria: { page: p } })));
db.close();

key form                         hits  misses     ratio    wrong entries
correct (tenant + criteria)       394       6     98.5%        0       6
extra field (request id)            0     400      0.0%        0     400
missing field (no tenant)         398       2     99.5%      200       2

An extra field zeroes out the hit ratio. Because the request id differs on every request, no key is ever looked up a second time; the cache fills with four hundred entries and produces not a single hit. A timestamp, a session id, or a header that does not affect the response produces the same result.

The missing-field row is more dangerous. It is the row with the highest hit ratio — 99.5% — with all but two of the four hundred requests served from two entries. That same row has two hundred wrong responses. The highest hit ratio belongs to the wrong implementation. The hit ratio alone is not a quality measure; correctness must be proven separately.

The rule that follows is this: the key must carry every input that changes the response, and none that does not. Among the ones that change the response, the authorization context — tenant, role, visibility level — is always present. Among the ones that do not, there are the request id, tracing headers, and the session token. The token entering the key is also a security flaw: a secret value ends up written somewhere that anyone listing cache keys can see.

Summary

• A key hand-concatenated with a separator character collides the moment a value itself carries that character; two different searches were served from the same entry.
• When the key does not carry the tenant, the cache walks around behind the authorization check: one branch’s list was served to another branch.
• The key generator carries five parts: namespace, schema version, generation, tenant, and canonical criteria. Escaping prevents collision, and sorting prevents the same query from splitting into two entries.
• Long criteria sets get summarized, but the readable body is preserved; which application and which tenant an entry belongs to stays readable from the key.
• Putting an extra field in the key zeroed out the hit ratio; putting a missing field in produced 200 wrong responses at a 99.5% hit ratio. The hit ratio alone is not proof of correctness.

Next Step

Up to this lesson, every measurement ran in a single sequence of operations: one request takes a miss, goes to the origin, stores the entry, and the next request gets a hit. On a real server, hundreds of requests look up the same key at the same time. The moment that key’s entry drops, all of them take a miss at once and all of them go to the origin at once; the origin the cache is protecting sees its highest load at exactly the moment the cache goes empty. The next lesson measures this behavior with concurrent requests and builds the lock that collapses the call reaching the origin for the same key down to a single production.