Loading page…
Acknowledge writes from the cache, coalesce and batch them to the database by count and by age, flush dirty entries before evicting them, and recover from a write-ahead log with versions so no acknowledged write is lost or overwritten by an older one.
A write-back (write-behind) cache acknowledges a write as soon as the cache has it and updates the database later, in batches (Day 1, section 2.4). Writes are fast, ten updates to one hot key become one database write, and the database sees far fewer, bigger writes. The price, in the lesson's table (section 3.1), is a high data-loss risk: anything acknowledged but not yet flushed dies with the process.
This lab removes that risk the way databases do: every write is appended to a durable write-ahead log (WAL) before it is acknowledged, and recovery replays the log. Replaying means old writes get flushed again, so every row carries a version (the WAL's log sequence number, LSN) and the database applies a row only if its version is newer than the one it has.
You get a FakeWAL (durable: it survives crashes), a FakeDB with versioned batch writes, and a FakeClock (see Given). Build WriteBackCache(db, wal, clock, capacity=100, batch_size=10, max_age=5.0):
| Method | Does |
|---|---|
put(key, value) |
lsn = wal.append(key, value, clock.now()) first, then stores the value in the cache as dirty with version lsn. When put returns, the write is acknowledged |
get(key) |
the newest value: from the cache, or on a miss from db.get(key) (cached as clean; None if the database doesn't have it either) |
flush_due() |
flushes every dirty entry that has been dirty for at least max_age seconds, in batches of up to batch_size, oldest first. Returns how many it flushed |
flush_all() |
flushes every dirty entry, in batches of up to batch_size, oldest first (a clean shutdown). Returns how many it flushed |
dirty_keys() |
the dirty keys, the one that became dirty first first |
recover() |
called on a brand-new cache after a crash: replays wal.read_all() in order, as if each record were put again with its own lsn as the version and its own at time (without appending to the WAL) |
The rules the tests check:
put (or a replayed record) leaves batch_size or more dirty entries, flush one batch: the batch_size oldest.db.write_batch(rows) call with rows {"key", "value", "version"}. If it raises DBUnavailable, nothing was written: the entries stay dirty, the flush stops there, and nothing is raised to the caller. On success they become clean.capacity counts every entry, clean or dirty. When there are more, evict the least recently used (get and put both count as a use). A dirty victim is flushed on its own (write_batch with one row) before it is dropped; if that fails, keep it for now and stop evicting.Crash is the process dying (a BaseException, so except Exception won't catch it). Let it propagate. The test then builds a new cache on the same db and wal and calls recover().In JavaScript and TypeScript the methods are put, get, flushDue(), flushAll(), dirtyKeys() and recover(); the constructor is new WriteBackCache(db, wal, clock, capacity = 100, batchSize = 10, maxAge = 5), the WAL is wal.append(key, value, at) and wal.readAll(), and the database is db.writeBatch(rows) and db.get(key). JavaScript has no BaseException, so Crash is an ordinary error: catch only DBUnavailable and rethrow anything else.
Yes: appending to a log is about as cheap as a durable write gets (one sequential append, no index to update), which is why databases use one themselves. A write-back cache backed by a local or replicated log keeps fast writes and coalescing without the data-loss risk. Without the log, write-behind is only for data you can afford to lose: view counters, likes, analytics (section 3.3).
Write your code, then run 3 example tests and 10 hidden tests. Each run is limited to 8 seconds: an infinite loop gets stopped and the runtime restarts, your code stays.