Strings and Counters

Every write in the previous lesson overwrote the entire value. Most of what the library needs to count does not fit that pattern: how many times a book has been borrowed, a branch’s daily loan total, how many times a member has been late — each of these is a single number that goes up by one on every event. This lesson takes up that number with two questions: what changes depending on who increments the counter, and what a single number actually costs in memory.

The store holds a value as a byte string; a number is also a string. But the store can interpret that string as a number and increment it in a single step. This capability is called atomic increment, and at first glance it looks like a convenience. Measured, it turns out to be not a convenience but accuracy itself.

Who Increments the Counter

There are two paths. Read-modify-write is three separate steps: the value is read, incremented in the application, and written back. Atomic increment is a single step: the store reads the value, adds to it, and writes it; nothing else can interleave in between. The difference only shows up under concurrency.

The measurement uses a popular book’s loan counter. DS1: the same book is loaned out concurrently by 1, 2, 4, 8, and 16 branches, and each branch records 500 loans; the expected counter value is the branch count times 500. DS2: concurrency is built with generators, every yield is a suspension point, and the scheduler picks among ready clients with a generator whose seed is visible; the run is deterministic.

// memory/counter.mjs — the same loan counter incremented two ways. Clients are
// generators, the scheduler is seeded; step order is run-independent.
class InMemoryStore {
  #table = new Map();
  roundTrips = 0;
  get(key) { this.roundTrips += 1; const s = this.#table.get(key); return s === undefined ? 0 : Number(s); }
  set(key, value) { this.roundTrips += 1; this.#table.set(key, String(value)); }
  increment(key, delta) {                      // reads, adds, and writes in a single step
    this.roundTrips += 1;
    const value = (this.#table.has(key) ? Number(this.#table.get(key)) : 0) + delta;
    this.#table.set(key, String(value)); return value; }
}

function* readModifyWrite(store, key, times) {
  for (let i = 0; i < times; i += 1) { const value = store.get(key); yield; store.set(key, value + 1); yield; }
}
function* atomic(store, key, times) {
  for (let i = 0; i < times; i += 1) { store.increment(key, 1); yield; }
}

const SEED = 20240115, TIMES = 500, KEY = "book:100427:loan";
function schedule(generators) {                // seeded selection among ready clients
  let state = SEED;
  const rand = () => (state = (state * 1103515245 + 12345) % 2147483648) / 2147483648;
  const live = [...generators];
  while (live.length > 0) {
    const i = Math.floor(rand() * live.length);
    if (live[i].next().done) live.splice(i, 1);
  }
}

console.log(`seed ${SEED}; each branch records ${TIMES} loans, key ${KEY}`);
console.log(`${"branches".padStart(9)}${"expected".padStart(10)}${"read-modify-write".padStart(19)}` +
  `${"lost".padStart(7)}${"round trips".padStart(13)}${"atomic increment".padStart(18)}${"lost".padStart(7)}${"round trips".padStart(13)}`);
for (const branches of [1, 2, 4, 8, 16]) {
  const expected = branches * TIMES;
  const rmwStore = new InMemoryStore();
  schedule(Array.from({ length: branches }, () => readModifyWrite(rmwStore, KEY, TIMES)));
  const atomicStore = new InMemoryStore();
  schedule(Array.from({ length: branches }, () => atomic(atomicStore, KEY, TIMES)));
  const rmwFinal = rmwStore.get(KEY), atomicFinal = atomicStore.get(KEY);
  console.log(String(branches).padStart(9) + String(expected).padStart(10) + String(rmwFinal).padStart(19) +
    String(expected - rmwFinal).padStart(7) + String(rmwStore.roundTrips - 1).padStart(13) + String(atomicFinal).padStart(18) +
    String(expected - atomicFinal).padStart(7) + String(atomicStore.roundTrips - 1).padStart(13));
}

seed 20240115; each branch records 500 loans, key book:100427:loan
 branches  expected  read-modify-write   lost  round trips  atomic increment   lost  round trips
        1       500                500      0         1000               500      0          500
        2      1000                620    380         2000              1000      0         1000
        4      2000                747   1253         4000              2000      0         2000
        8      4000                871   3129         8000              4000      0         4000
       16      8000                938   7062        16000              8000      0         8000

With a single branch running, both paths give the correct result; the divergence starts at the second branch. At two branches, 380 of 1,000 loans go missing; at sixteen branches, 7,062 of 8,000. The counter stalls at 938: the library handed out eight thousand loans, and its record reads nine hundred thirty-eight. A lost update is not a delay or a slowdown — it is a wrong number, and it shows up nowhere as an error.

The cause is the gap between the read and the write. By the time one branch reads 41 and writes 42, other branches have also read 41; all of them write 42, and all four of them together have made a single increment. Atomic increment has no such gap — the store reads, adds, and writes as one operation that cannot be split. At sixteen branches, the loss is zero.

The round-trip column shows the second gain: read-modify-write spends two round trips per increment, while atomic increment finishes in one — 8,000 instead of 16,000. Getting the same correctness out of read-modify-write means holding a lock in the application, which in turn means keeping the lock itself in memory and lining the branches up in a queue. Atomic increment removes both a round trip and the lock’s memory — and asks for no extra bytes in return, because the increment is the store’s own job.

The Memory Price of a Number

The counter now increments correctly; the real question comes next. How much memory does holding a loan counter for the entire catalog take up. DS3: the catalog carries 200,000 books, each book’s counter value comes from a deterministic function and falls between 1 and 4,096; the loan ledger is 119,993 records and sits outside the in-memory store — scanning it counts steps, not bytes. DS4: the query load is 10,000 “how many times was this book borrowed” questions, skewed toward popularity; the skew comes from the same seeded generator.

// memory/budget.mjs — the memory price of one counter and two options that skip it.
// The loan ledger is outside the in-memory store; scanning it counts steps, not bytes.
const OVERHEAD = 56, BOOKS = 200_000, LEDGER = 119_993, QUERIES = 10_000, HOT = 1_000, SEED = 20240115;
let state = SEED;
const rand = () => (state = (state * 1103515245 + 12345) % 2147483648) / 2147483648;

// counter value: daily loan count for book i (deterministic)
const counterValue = (i) => 1 + ((i * 7919) % 4096);
const key = (i) => `book:${100_000 + i}:loan`;

let totalKey = 0, totalValue = 0, totalOverhead = 0;
for (let i = 1; i <= BOOKS; i += 1) {
  totalKey += Buffer.byteLength(key(i));
  totalValue += Buffer.byteLength(String(counterValue(i)));
  totalOverhead += OVERHEAD;
}
const full = totalKey + totalValue + totalOverhead;
console.log(`${BOOKS} books, sample entry "${key(427)}" -> "${counterValue(427)}"`);
console.log(`full counter: key ${totalKey} + value ${totalValue} + overhead ${totalOverhead} = ${full} bytes` +
  ` (per entry ${(full / BOOKS).toFixed(1)}; value's share %${(100 * totalValue / full).toFixed(1)})`);

// query load: "how many times was this book borrowed" — skewed to popularity, seeded
const queries = Array.from({ length: QUERIES }, () => 1 + Math.floor(BOOKS * rand() ** 6));
const hotQueries = queries.filter((i) => i <= HOT).length;
const partial = Array.from({ length: HOT }, (_, j) =>
  Buffer.byteLength(key(j + 1)) + Buffer.byteLength(String(counterValue(j + 1))) + OVERHEAD)
  .reduce((t, x) => t + x, 0);

const baseline = QUERIES * LEDGER;              // steps when no counter is held
const paths = [
  ["no counter, ledger scan", 0, 0, baseline],
  [`partial counter (top ${HOT})`, HOT, partial, hotQueries + (QUERIES - hotQueries) * LEDGER],
  ["full counter", BOOKS, full, QUERIES],
];
console.log(`\n${QUERIES} queries, ${hotQueries} of them to the first ${HOT} books (%${(100 * hotQueries / QUERIES).toFixed(1)})`);
console.log(`${"path".padEnd(27)}${"entries".padStart(8)}${"bytes held".padStart(14)}` +
  `${"steps per query".padStart(19)}${"steps prevented per byte".padStart(27)}`);
for (const [name, n, b, steps] of paths)
  console.log(name.padEnd(27) + String(n).padStart(8) + String(b).padStart(14) +
    (steps / QUERIES).toFixed(1).padStart(19) + (b === 0 ? "-" : ((baseline - steps) / b).toFixed(1)).padStart(27));

200000 books, sample entry "book:100427:loan" -> "2214"
full counter: key 3200000 + value 745901 + overhead 11200000 = 15145901 bytes (per entry 75.7; value's share %4.9)

10000 queries, 4149 of them to the first 1000 books (%41.5)
path                        entries    bytes held    steps per query   steps prevented per byte
no counter, ledger scan           0             0           119993.0                          -
partial counter (top 1000)     1000         75662            70208.3                     6579.9
full counter                 200000      15145901                1.0                       79.2

The first line carries the lesson’s headline: 200,000 counters hold 15,145,901 bytes, 75.7 per entry. Yet the information stored is a four-digit number. The number itself takes up only 4.9 percent of the total; the key name takes 21.1 percent, entry overhead takes 73.9 percent. Holding a number in an in-memory store costs not four bytes but seventy-six. This ratio holds for every small value, and the real lever is not the value itself, it is how many keys are opened.

The lower table compares three options under the same load. If the counter is never held, memory is zero and every query scans the 119,993-record ledger. With the full counter, memory rises to 15.1 MB and steps per query drop to 1: 15.1 MB buys 119,992 steps per query.

The last column is the number that actually decides. Holding a counter only for the first 1,000 books costs 75,662 bytes — one two-hundredth of the full counter — and it drops 41.5 percent of the queries to a single step. Every byte it holds prevents 6,579.9 steps; the same figure for the full counter is 79.2. The partial counter is roughly eighty-three times more byte-efficient. But the raw number is still unforgiving: 70,208 steps per query, because each of the missed 58.5 percent scans the entire ledger. If the memory budget is tight, the partial counter is the more efficient purchase; if a fixed step count per query is required, there is no alternative to the 15.1 MB. What decides between the two is not “speed” — it is the product of the miss rate and the budget.

Summary

• A counter has two update paths: read-modify-write is three steps and is open to other clients between the read and the write; atomic increment is the store’s single, unsplittable step.
• Loss grows with concurrency: at 2 branches, 380 of 1,000 loans go missing; at 16 branches, 7,062 of 8,000, and the counter stalls at 938. With atomic increment, the loss is zero at every level.
• Atomic increment also halves round trips (8,000 instead of 16,000) and removes the need to hold a lock in the application for correctness; a lock means both memory and waiting.
• 200,000 loan counters hold 15,145,901 bytes. The number itself is 4.9 percent of that, the key name is 21.1 percent, entry overhead is 73.9 percent: a number in an in-memory store costs 75.7 bytes.
• Three options under the same load: no counter, 0 bytes and 119,993 steps per query; partial counter, 75,662 bytes and 70,208 steps; full counter, 15,145,901 bytes and 1 step.
• Steps prevented per byte are 6,579.9 for the partial counter and 79.2 for the full counter. The partial counter is far more efficient per unit of budget, but it gives no guarantee of a fixed step count per query.

Next Step

A counter answers the “how many” question at the scale of a single byte, but it never meets the library’s second question: who is waiting for a popular book, and in what order. A waiting list is not a number, it is a sequence; the order itself is part of the information, and if the store is to preserve it, it has to hold every member individually. The next lesson takes up the list and measures three things: the step count of inserting and removing from both ends, the effect of the list’s growth on memory, and what a bounded list — one trimmed to a fixed length — cheapens compared to an unbounded one, and what it silently loses.