Data Reliability and Fault Tolerance Questions

Direct answer

At billions of event IDs with limited RAM per partition, exact deduplication (a hash set of every ID) does not fit in memory, so the design combines a Bloom filter (or the more space-efficient counting-filter variant) as a fast, in-memory FIRST-PASS check that can definitively say "definitely new" but only "probably seen" for the rest, with a persistent compaction store (an on-disk, compacted key-value store, RocksDB or a compacted Kafka topic) as the authoritative, exact source of truth for anything the Bloom filter flags as a possible duplicate. This hybrid gets the Bloom filter's O(1)-in-memory speed for the common case (most IDs are genuinely new) while never actually LOSING correctness to a false positive, since every "probably seen" result is confirmed (or refuted) against the exact store before a decision is made.

Structured elaboration

Why a Bloom filter alone is insufficient here. A Bloom filter's false positives mean it can incorrectly report "seen" for a genuinely new ID, silently dropping real data if trusted alone, unacceptable for a deduplication mechanism whose entire job is correctness. Used correctly, the Bloom filter is a FILTER, not a decision-maker: "definitely not seen" (a negative result) can be trusted immediately (fast path, no exact-store lookup needed, this is the common case for genuinely new data and where the Bloom filter earns its keep), but "possibly seen" (a positive result) must be confirmed against the exact store before treating the ID as a true duplicate.

Counting filters versus plain Bloom filters. A counting Bloom filter (each slot is a small counter, not a single bit) supports DELETION (decrementing a counter when an ID ages out of relevance), which a plain Bloom filter cannot do without a full rebuild; this matters for a sliding-window dedup scenario where old IDs need to be forgotten, at the cost of more memory per slot (a counter needs several bits, versus one bit for a plain filter).

The persistent compaction store. A compacted, on-disk key-value store (RocksDB with native compaction, or a Kafka topic with log compaction keyed by event ID) holds the EXACT set of recently-seen IDs, persisted to disk (not memory-bound the way the Bloom filter is), with compaction periodically removing IDs old enough to be outside the relevant dedup window. This store is the authoritative check for anything the Bloom filter flags as a possible duplicate, and its own disk-based capacity is what actually scales to billions of IDs, the Bloom filter's job is purely to avoid paying a disk lookup for the (common) case where the answer is trivially "no."

Hybrid architecture, put together. On each incoming event ID: check the Bloom filter first. If NEGATIVE ("definitely new"): process as new, and asynchronously add the ID to both the Bloom filter and the compaction store (no blocking disk read needed on this fast path). If POSITIVE ("possibly seen"): look up the exact compaction store; if the ID IS actually present there, it is a true duplicate (skip); if NOT present (a Bloom filter false positive), it is genuinely new, process it and add it to both structures. This means every disk lookup is reserved for the (hopefully small) fraction of IDs that trigger a Bloom filter positive, most of which will genuinely be true duplicates in a healthy pipeline, keeping disk I/O proportional to the ACTUAL duplicate rate, not to total event volume.

Validating and monitoring false-positive rates in production. Periodically sample a batch of IDs the Bloom filter flagged POSITIVE and measure what fraction were confirmed FALSE POSITIVES by the exact-store lookup (a genuinely free-to-compute metric, since every positive already triggers an exact-store check as part of normal operation, this is just aggregating those results); alert if the measured rate drifts meaningfully above the Bloom filter's theoretically configured rate, which would indicate the filter is under-sized relative to actual ID cardinality (more distinct IDs inserted than the filter was sized for) rather than a bug, a capacity-planning signal, not a correctness bug, since correctness is preserved by the exact-store fallback regardless.

Worked example

At 2 billion distinct event IDs per partition per day, with 4 GB of RAM available per partition for the Bloom filter, targeting a 1% false-positive rate:

comfortably within the 4 GB budget, leaving headroom for the hash-function computation overhead and other process memory. If the actual observed cardinality grows to 4 billion IDs (2x the planned capacity) without resizing the filter, the effective false-positive rate does NOT merely double, it degrades steeply: using the exact closed-form Bloom filter formula, $p = (1 - e^{-kn/m})^k$, with the same $m \approx 1.917\times10^{10}$ bits and $k=7$ hash functions sized for the planned $n=2\times10^9$ (which correctly reproduces the target $p \approx 1.00\%$), doubling $n$ to $4\times10^9$ with $m$ and $k$ unchanged gives $p \approx 15.7\%$, roughly a 16x increase, not 2x. This is not an approximation error, it is how the formula behaves: false-positive rate is an EXPONENTIAL function of the load factor $n/m$, so a fixed bit array under 2x its designed cardinality does not degrade linearly with the overrun ratio, it degrades far faster once the filter's designed load factor is exceeded. This is directly visible via the monitored false-positive-rate metric described above, and the correct operational takeaway is sharper than 'roughly doubles' would suggest: a capacity review (resize the filter, or shard into more partitions) needs to trigger on a SMALL overrun, well before 2x, since by the time cardinality has doubled the fast path has already degraded by an order of magnitude, not a modest, easily-absorbed factor of two.

Trade-offs and pitfalls

• Common mistake: trusting a Bloom filter positive as a definitive duplicate without the exact-store confirmation. This silently drops genuinely new data at exactly the filter's configured false-positive rate, a correctness bug hiding behind what looks like a performance optimization; the hybrid architecture's entire value depends on NEVER skipping the confirmation step for a positive result.
• Common mistake: sizing the Bloom filter for a snapshot cardinality without planning for growth. As the worked example shows, actual item count exceeding planned capacity degrades the false-positive rate predictably; monitoring (per the dedicated subsection above) is what catches this before it becomes a meaningfully increased disk-lookup rate.
• The compaction store's own compaction cadence is a real trade-off. Compacting too aggressively risks removing an ID still within the relevant dedup window (reopening a genuine duplicate-acceptance risk); too infrequently, and the store's disk footprint grows past what it needs to for the actual dedup window: the same checkpoint/compaction trade-off any bounded store faces, applied here specifically to a dedup-metadata store.
• A counting filter's extra memory cost per slot is a real, not negligible, trade for supporting deletion. For a workload where the dedup window is genuinely sliding (old IDs must be actively forgotten, not just left to a periodic rebuild), the extra memory is usually worth it; for a workload with a simpler, append-only "have we EVER seen this ID" semantic, a plain Bloom filter (rebuilt periodically if needed at all) may be sufficient and cheaper.

Direct answer

Recovery has two distinct phases that must not be conflated: first, replay the WAL sequentially to rebuild the operator's in-memory state exactly as it stood right before the crash; second, reconcile with every external sink using each WAL record's own sequence number as an idempotency key, so a sink that ALREADY received some of those writes before the crash (a real case: the write succeeded, but the operator crashed before it could note that fact) treats a replayed write as a safe no-op instead of double-applying it. Below is executable pseudocode-as-real-Python implementing both phases, including a negative control proving what happens without the idempotency-key guard.

Structured elaboration

Phase 1: WAL replay to rebuild operator state. Read WAL records strictly in append order (their sequence number), applying each record's delta to an in-memory state dict. Reading in order is what preserves ordering guarantees: if state updates were non-commutative (a "last write wins" field instead of a running sum), applying them out of order would silently produce the wrong final state even though every record was individually applied correctly.

Corruption handling during replay. Each record carries a checksum. On the first corrupt or truncated record (a torn write from a crash mid-append, the exact scenario a WAL exists to survive), replay stops there rather than guessing at the record's content; anything after that point is treated as never durably written, which is the conservative, correct choice, since a torn write's own outcome is genuinely unknown.

Phase 2: idempotent reconciliation with external sinks. The WAL's own monotonic sequence number IS a natural idempotency key: it uniquely identifies one logical write. The sink's apply(seq, key, delta) checks whether that seq has already been applied; if so, no-op (deduplication); if not, apply and remember the seq. This is necessary because the crash could have happened AFTER a sink write succeeded but BEFORE the operator's own bookkeeping (a checkpoint, or an internal "last-reconciled-seq" watermark) recorded that fact, exactly the general crash-after-write-before-confirm gap any idempotency-store design has to close, here solved at the sink itself via a persistent per-seq applied-set rather than a separate claim-then-confirm protocol.

Ordering guarantee, stated precisely. WAL replay yields records in seq order; the reconciliation step processes them in that same order, so if two records touch the SAME key, the sink observes them in the correct original order even during recovery, not merely eventually-consistent-in-some-order.

Complexity. Replay is $O(n)$ in the number of WAL records since the last durable checkpoint (each record is read and its checksum verified exactly once). State reconstruction is $O(1)$ per record (a dict update). Sink reconciliation is $O(1)$ amortized per record (a set membership check plus insert). Total recovery time is $O(n)$, linear in WAL size since the last checkpoint, which is exactly why checkpoint frequency directly bounds worst-case recovery time.

Worked example

"""
Checkpoint recovery: replay a WAL to restore operator state, then reconcile
external sinks using idempotency keys (the WAL's own seq number) so replay
is safe even if the sink already received some writes before the crash.
"""
import os, struct, zlib


class WAL:
    HEADER_FMT = "!IQ"
    HEADER_SIZE = struct.calcsize(HEADER_FMT)

    def __init__(self, path):
        self.path = path
        self._next_seq = 0

    def append(self, key, delta):
        payload = f"{key}|{delta}".encode()
        seq = self._next_seq
        self._next_seq += 1
        crc = zlib.crc32(payload)
        with open(self.path, "ab") as f:
            f.write(struct.pack(self.HEADER_FMT, len(payload), seq))
            f.write(payload)
            f.write(struct.pack("!I", crc))
            f.flush()
            os.fsync(f.fileno())
        return seq

    def replay(self):
        if not os.path.exists(self.path):
            return
        with open(self.path, "rb") as f:
            while True:
                header = f.read(self.HEADER_SIZE)
                if len(header) < self.HEADER_SIZE:
                    break
                length, seq = struct.unpack(self.HEADER_FMT, header)
                payload = f.read(length)
                crc_bytes = f.read(4)
                if len(payload) < length or len(crc_bytes) < 4:
                    break
                if zlib.crc32(payload) != struct.unpack("!I", crc_bytes)[0]:
                    break
                key, delta = payload.decode().split("|")
                yield seq, key, int(delta)


class ExternalSink:
    def __init__(self):
        self.applied_seqs = set()
        self.totals = {}

    def apply(self, seq, key, delta):
        if seq in self.applied_seqs:
            return "duplicate_noop"
        self.applied_seqs.add(seq)
        self.totals[key] = self.totals.get(key, 0) + delta
        return "applied"


def recover(wal, sink):
    state = {}
    applied = duplicates = 0
    for seq, key, delta in wal.replay():
        state[key] = state.get(key, 0) + delta
        if sink.apply(seq, key, delta) == "applied":
            applied += 1
        else:
            duplicates += 1
    return state, applied, duplicates


def main():
    wal_path = os.path.join(os.path.dirname(__file__), "s24_test.wal")
    if os.path.exists(wal_path):
        os.remove(wal_path)
    wal = WAL(wal_path)
    for key, delta in [("a", 5), ("b", 3), ("a", 2), ("c", 10), ("a", -1), ("b", 7)]:
        wal.append(key, delta)

    sink = ExternalSink()
    # Simulate: sink ALREADY applied seq 0,1,2 before the crash.
    sink.apply(0, "a", 5); sink.apply(1, "b", 3); sink.apply(2, "a", 2)
    pre_crash_totals = dict(sink.totals)
    print("Sink totals BEFORE recovery (pre-applied seq 0,1,2):", pre_crash_totals)

    state, applied, duplicates = recover(wal, sink)
    print("Recovered operator state (from full WAL replay):", state)
    print("Sink totals AFTER recovery:", sink.totals)
    print(f"Reconciliation: {applied} newly applied, {duplicates} correctly recognized as duplicates")

    expected_state = {"a": 5 + 2 - 1, "b": 3 + 7, "c": 10}
    assert state == expected_state
    assert sink.totals == expected_state
    assert duplicates == 3 and applied == 3

    # Negative control: WITHOUT the idempotency-key check, naive replay
    # double-counts seq 0,1,2.
    naive_totals = dict(pre_crash_totals)
    for seq, key, delta in wal.replay():
        naive_totals[key] = naive_totals.get(key, 0) + delta
    print("\nWITHOUT idempotency-key reconciliation, naive replay gives:",
          naive_totals, "(WRONG: double-counts seq 0,1,2)")
    assert naive_totals != expected_state
    os.remove(wal_path)


if __name__ == "__main__":
    main()

Output (actually executed with python3):

Sink totals BEFORE recovery (pre-applied seq 0,1,2): {'a': 7, 'b': 3}
Recovered operator state (from full WAL replay): {'a': 6, 'b': 10, 'c': 10}
Sink totals AFTER recovery: {'a': 6, 'b': 10, 'c': 10}
Reconciliation: 3 newly applied, 3 correctly recognized as duplicates

WITHOUT idempotency-key reconciliation, naive replay gives: {'a': 13, 'b': 13, 'c': 10} (WRONG: double-counts seq 0,1,2)

The correct run shows operator state and sink totals converging to the identical {'a': 6, 'b': 10, 'c': 10}, and the reconciliation counters (3 applied, 3 duplicates) confirm the guard actually distinguished the pre-crash-applied records from the genuinely new ones. The negative control is the deliberately non-vacuous proof: replaying the full WAL against the SAME pre-crash sink state WITHOUT the seq-based guard produces 'a': 13 instead of the correct 6 (double-counting the +5 and +2 deltas at seq 0 and seq 2), concretely demonstrating why the idempotency check is load-bearing, not defensive boilerplate.

Trade-offs and pitfalls

• Common mistake: reconstructing operator state from the WAL but skipping sink reconciliation entirely, assuming "the sink will just get whatever we send it now." As the negative control shows, this silently double-applies any write that succeeded before the crash but was not yet acknowledged back to the operator.
• Common mistake: treating the sink's own idempotency as automatic. The applied_seqs set itself must be durable (backed by the sink's own storage, not the crashed operator's now-lost memory), or the sink has no way to know it already saw seq 0 through 2 after ITS OWN restart; this is the same durability requirement any idempotency-key store has.
• Stopping replay at the first corrupted record is a real, deliberate data-loss trade-off, not a bug: it guarantees recovery only ever trusts CONFIRMED-INTACT records, at the cost of potentially losing a record that was actually fine but happened to be written just before an unrelated corruption; the alternative (skip and continue past a bad record) risks silently applying a record whose content cannot be trusted.
• Recovery cost scales with WAL length since the last checkpoint, not total historical WAL size, which is why in production this algorithm always runs against the WAL segment(s) since the last completed checkpoint, never the entire WAL history, tying recovery time directly to the checkpoint-interval trade-off.

Direct answer

The right consistency model is a function of what a wrong-but-available answer costs versus what a correct-but-delayed answer costs, evaluated per use case, not chosen once for the whole analytics stack. Near-real-time dashboards tolerate eventual consistency well (a metric that is a few seconds stale is rarely actionable-wrong), served by materialized views refreshed incrementally from a change log. Financial reconciliation needs strong consistency at the POINT OF RECORD (the ledger itself must never show two conflicting "true" balances), typically via a database's native ACID transactions or, across systems, a 2PC-style protocol for the narrow set of operations that genuinely require cross-system atomicity. Fraud detection sits in between: it needs LOW-LATENCY eventual consistency (acting on stale-by-seconds data is far better than acting too late), but with a strong requirement that once a decision is made, it is auditable and never silently reversed without an explicit compensating record.

Structured elaboration

Near-real-time dashboards: eventual consistency, materialized views. A dashboard showing "current active users" or "orders in the last hour" is read far more often than it is written, and its consumers make decisions on TRENDS, not exact-to-the-second values. A materialized view, incrementally maintained from a change log (CDC from the source-of-record, or a streaming aggregation), gives fast reads at the cost of a small, bounded staleness window (the lag between a source change and the view reflecting it). This is the textbook case for prioritizing availability and latency over strict consistency, per the CAP-theorem trade-off, since the cost of staleness here is low and the cost of unavailability (a dashboard that cannot load) or high latency (a slow dashboard nobody uses) is comparatively higher.

Financial reconciliation: strong consistency. A ledger showing account balances must never present two different "current balance" values to two concurrent readers, since a decision based on either value (approving a withdrawal, say) could be wrong if the OTHER value is the true one. This requires ACID transactions at the database level for single-system operations, and, for operations genuinely spanning multiple systems (a transfer touching two separate ledgers), either a 2PC-style protocol (real atomicity, but with a real blocking cost that must be justified) or, more commonly in practice, a saga/compensating-transaction pattern (an append-only ledger of original entries plus explicit compensating entries) that achieves eventual correctness with an explicit, auditable reconciliation step rather than blocking availability on strict cross-system atomicity.

Fraud detection: latency-first eventual consistency with an audit trail. A fraud model scoring a transaction in real time cannot wait for strongly-consistent, fully-reconciled data across every system; it acts on the freshest available signal, accepting that signal may be a few seconds stale (eventual consistency, prioritizing low latency, since a fraud check that arrives after the transaction has already completed is largely useless). Critically, though, the fraud DECISION itself (block, allow, flag) must be recorded as an immutable, auditable event, so if a later, more-consistent view of the data reveals the decision was wrong (the fraud signal was stale), the correction is a new, explicit, auditable follow-up action, not a silent overwrite of history, the same append-only, compensating-entry pattern any auditable ledger needs.

Worked example

An e-commerce platform's fraud model scores a transaction using a customer's rolling 24-hour transaction-count feature, computed via eventually-consistent stream aggregation with a typical 2-second lag:

For a $50 transaction, a 2-second-stale fraud signal is essentially always the right trade-off: blocking on a strongly-consistent, fully-reconciled feature computation would add latency to EVERY transaction (including the overwhelming majority that are legitimate) to protect against a rare case where the 2-second staleness matters, a poor trade for the actual risk. Contrast with the SAME platform's ledger recording that the $50 was actually charged: this MUST be strongly consistent, since the customer's actual account balance (used for subsequent purchase-approval decisions) cannot be allowed to show two different values depending on which replica happens to answer a read. The platform runs BOTH consistency models simultaneously, on different subsystems, deliberately, not because of an oversight, but because the fraud-scoring feature's cost of staleness (rare, cheap to correct after the fact) differs fundamentally from the ledger's cost of inconsistency (an incorrect balance driving a wrong downstream financial decision).

Trade-offs and pitfalls

• Common mistake: picking one consistency model for the entire analytics platform. As the worked example shows, a single platform legitimately runs multiple consistency models simultaneously across different subsystems; the question is never "eventual or strong" in the abstract, it is "eventual or strong FOR THIS SPECIFIC READ/WRITE PATH."
• Common mistake: assuming strong consistency is always "safer." For the dashboard case, forcing strong consistency (e.g., reading directly from a heavily-loaded transactional source instead of a materialized view) can make the SYSTEM less reliable overall (higher load on the source of record, higher latency, more contention), a real cost with no corresponding benefit given the use case's actual tolerance for staleness.
• Fraud detection's "eventual consistency with an audit trail" is a genuinely hybrid, not a compromise. It deliberately accepts staleness on the DECISION INPUT (for latency) while refusing to accept staleness or silent mutation on the DECISION RECORD (for auditability); conflating these two properties, thinking "eventually consistent" means "the decision itself can be silently revised," is a common and costly misunderstanding.
• The 2PC option named in the question is rarely the right choice even for financial reconciliation, given its blocking failure mode; a saga/compensating pattern more often matches the actual availability requirements of a financial system that still needs to keep functioning during a partial outage.

Direct answer

The compacted view keeps exactly one row per entity_id: the write with the HIGHEST version, and among ties on version, the LATEST written_at. This is a window-function rank query (ROW_NUMBER() OVER (PARTITION BY entity_id ORDER BY version DESC, written_at DESC), filtered to rank 1), the same window-function ranking shape used for SQL dedup and CDC-MERGE ordering generally, applied here to a versioned write-attempts table. Tombstones (a NULL payload) represent a logical delete: if the WINNING row (highest version) for an entity is a tombstone, that entity should be EXCLUDED from the live compacted view entirely, not shown with a null payload. Concurrent same-version writes are resolved purely by the written_at tiebreak, and, critically, VERSION must take precedence over written_at in the ordering, not the reverse, since a lower-version write can legitimately arrive and be recorded LATER (network reordering) than a higher-version write.

Structured elaboration

Why version must outrank written_at in the ORDER BY. written_at records when a write attempt was RECORDED, not necessarily the logical order of the underlying changes; a network delay or retry can cause an OLDER logical change (lower version) to be durably written AFTER a NEWER logical change (higher version) already landed. If written_at were the primary sort key, this out-of-order arrival would incorrectly make the STALE lower-version write win. version is the authoritative logical-order signal (the same discipline as LSN-based ordering in a CDC pipeline); written_at is only a tiebreak for the case where version itself does not distinguish two rows.

Tombstone handling. A tombstone (NULL payload) is not "missing data to be ignored," it is an explicit, meaningful WRITE recording "this entity was deleted as of this version." If it is the WINNING row for its entity (highest version, or the written_at-tiebroken winner among same-version rows), the entity is logically deleted and must not appear in the live view at all. Critically, a tombstone should still be considered in the ranking alongside non-tombstone rows for the SAME entity_id (it competes for "latest" on equal footing), just excluded from the FINAL output once it wins.

Concurrent same-version writes. Two writers racing to write the SAME version for the SAME entity (a retry race, or a genuine concurrent-write conflict) is resolved by written_at DESC as the tiebreak, keeping whichever was recorded later. This is a deliberate, simple last-writer-wins policy for the tie case specifically; it does not attempt to detect or flag the conflict as an application-level anomaly (a system that needs conflict detection, not just resolution, would need additional logic beyond this compaction query, e.g., a count of distinct payloads per (entity_id, version) as a data-quality signal).

Worked example

"""
Compacted view: latest successful write per entity_id, preferring higher
version, then latest written_at as tiebreak. Tombstones (payload IS NULL)
represent a logical delete and must be treated as the winning write when
they have the highest version/written_at for their entity, not silently
skipped, so a deleted entity correctly disappears from the compacted view.
"""
import sqlite3

conn = sqlite3.connect(":memory:")
cur = conn.cursor()
cur.execute("""
CREATE TABLE writes (
    entity_id TEXT, version INTEGER, payload TEXT, written_at TIMESTAMP
)
""")

rows = [
    # e1: normal case, version 3 (latest) should win
    ("e1", 1, '{"name":"a"}', "2026-01-01 10:00:00"),
    ("e1", 2, '{"name":"b"}', "2026-01-01 10:05:00"),
    ("e1", 3, '{"name":"c"}', "2026-01-01 10:10:00"),
    # e2: concurrent SAME-version writes -- tiebreak on written_at
    ("e2", 1, '{"name":"x"}', "2026-01-01 09:00:00"),
    ("e2", 2, '{"name":"y-early"}', "2026-01-01 09:05:00"),
    ("e2", 2, '{"name":"y-late"}', "2026-01-01 09:07:00"),
    # e3: tombstoned -- highest version is a NULL payload (a delete)
    ("e3", 1, '{"name":"z"}', "2026-01-01 11:00:00"),
    ("e3", 2, None, "2026-01-01 11:05:00"),
    # e4: OUT-OF-ORDER ARRIVAL -- lower version has a LATER written_at
    ("e4", 2, '{"name":"newer-version"}', "2026-01-01 08:00:00"),
    ("e4", 1, '{"name":"older-version-but-later-arrival"}', "2026-01-01 08:30:00"),
]
cur.executemany("INSERT INTO writes VALUES (?, ?, ?, ?)", rows)
conn.commit()

query = """
WITH ranked AS (
    SELECT entity_id, version, payload, written_at,
           ROW_NUMBER() OVER (
               PARTITION BY entity_id ORDER BY version DESC, written_at DESC
           ) AS rn
    FROM writes
)
SELECT entity_id, version, payload, written_at
FROM ranked
WHERE rn = 1 AND payload IS NOT NULL
ORDER BY entity_id;
"""
result = cur.execute(query).fetchall()
print("Compacted LIVE view (tombstoned entities excluded):")
for r in result:
    print(" ", r)

full_result = cur.execute(query.replace("WHERE rn = 1 AND payload IS NOT NULL", "WHERE rn = 1")).fetchall()
print("\nFull compacted view (includes the tombstoned winning row for e3):")
for r in full_result:
    print(" ", r)

by_entity = {r[0]: r for r in result}
assert by_entity["e1"][1] == 3 and "c" in by_entity["e1"][2]
assert by_entity["e2"][1] == 2 and "y-late" in by_entity["e2"][2]
assert "e3" not in by_entity
assert by_entity["e4"][1] == 2 and "newer-version" in by_entity["e4"][2]
print("\nAll assertions passed: e1 highest-version wins; e2 same-version tie broken by")
print("written_at; e3 tombstone correctly excluded from live view; e4 version ordering")
print("correctly wins over written_at ordering.")

wrong_query = """
WITH ranked AS (
    SELECT entity_id, version, payload, written_at,
           ROW_NUMBER() OVER (PARTITION BY entity_id ORDER BY written_at DESC) AS rn
    FROM writes WHERE entity_id = 'e4'
)
SELECT entity_id, version, payload, written_at FROM ranked WHERE rn = 1;
"""
wrong_result = cur.execute(wrong_query).fetchall()
print(f"\nWITHOUT version-first ordering (written_at-only) for e4: {wrong_result}")
print("(WRONG: picks version 1, the stale out-of-order-arrival row.)")
assert wrong_result[0][1] == 1

Output (actually executed with python3's built-in sqlite3 module):

Compacted LIVE view (tombstoned entities excluded):
  ('e1', 3, '{"name":"c"}', '2026-01-01 10:10:00')
  ('e2', 2, '{"name":"y-late"}', '2026-01-01 09:07:00')
  ('e4', 2, '{"name":"newer-version"}', '2026-01-01 08:00:00')

Full compacted view (includes the tombstoned winning row for e3):
  ('e1', 3, '{"name":"c"}', '2026-01-01 10:10:00')
  ('e2', 2, '{"name":"y-late"}', '2026-01-01 09:07:00')
  ('e3', 2, None, '2026-01-01 11:05:00')
  ('e4', 2, '{"name":"newer-version"}', '2026-01-01 08:00:00')

All assertions passed: e1 highest-version wins; e2 same-version tie broken by
written_at; e3 tombstone correctly excluded from live view; e4 version ordering
correctly wins over written_at ordering.

WITHOUT version-first ordering (written_at-only) for e4: [('e4', 1, '{"name":"older-version-but-later-arrival"}', '2026-01-01 08:30:00')]
(WRONG: picks version 1, the stale out-of-order-arrival row.)

Four distinct correctness properties are each proven, not asserted: e1 confirms basic highest-version selection; e2 confirms the written_at tiebreak actually fires for a genuine same-version tie; e3 confirms tombstone exclusion (visible in the "full" view, absent from the "live" view); and e4 is the deliberately non-vacuous case, its version-1 row has a LATER written_at than its version-2 row, so the negative control (written_at-only ordering) demonstrably picks the WRONG, stale row, proving the version-first ordering is load-bearing, not redundant caution.

Trade-offs and pitfalls

• Common mistake: ordering by written_at first (or alone). As e4 and the negative control prove concretely, this silently prefers a stale write whenever out-of-order arrival happens, exactly the class of bug this query's ORDER BY precedence is designed to prevent.
• Common mistake: filtering out NULL payloads BEFORE ranking, instead of after. Excluding tombstones from the input to ROW_NUMBER() would let a NON-tombstone row with a LOWER version win for an entity that was actually deleted at a higher version, incorrectly resurrecting deleted data; tombstones must compete in the ranking and only be filtered from the FINAL output.
• The same-version tiebreak (written_at DESC) is a policy choice, not a universal law. For a system that needs to DETECT (not just silently resolve) concurrent-write conflicts, this query would need to be paired with a separate data-quality check counting (entity_id, version) groups with more than one row, since the compaction query alone makes conflicts invisible by design.
• Performance at scale. As with any large-scale window-function dedup, this approach benefits from partitioning/clustering the underlying table by entity_id, and for a large, continuously-growing writes table, running this as an INCREMENTAL materialization (only re-ranking entities with new writes since the last run) rather than a full re-scan is the production-scale version of this pattern.

Direct answer

A write-ahead log (WAL) is an append-only log that records every state mutation before the mutation is applied to the actual data structure, so if the process crashes mid-update, replaying the WAL from the last known-good point reconstructs exactly the state that existed right before the crash. It trades a small amount of write latency (every change is logged first) for a strong recovery guarantee (no acknowledged write is ever lost) and for cheap durability (sequential appends are fast even on spinning disks, let alone SSDs). PostgreSQL's WAL, RocksDB's WAL, and a Kafka topic used as a commit log are all instances of the same idea: an ordered, append-only, replayable record of intent.

Structured elaboration

The core mechanism. Before any change is applied to the in-memory or on-disk data structure, a record describing that change is appended to the log and (usually) fsynced to durable storage. The system acknowledges the write only after the log record is durable. On crash, recovery replays every log record after the last confirmed checkpoint, in order, reconstructing state deterministically. This gives crash recovery without requiring every single mutation to be immediately reflected in the final data structure (which would be far slower, since random-access updates to a B-tree or an in-memory table are expensive compared to a sequential append).

Benefits.

• Durability with sequential I/O: appending to a log is cheap relative to random-access updates to the primary data structure, so the WAL buys durability without forcing every write to be a slow in-place update.
• Deterministic, replayable recovery: replaying the same log from the same starting point always produces the same end state, which is what makes crash recovery predictable and testable.
• Decouples "durable" from "applied": a write can be considered safely committed as soon as it is in the log, even before the corresponding in-memory structure or index is updated, which is what lets systems batch or defer the expensive part of a write.

Drawbacks.

• Extra write amplification: every logical write becomes at least two physical writes (the log record, then eventually the applied change to the primary structure), and often more once compaction and replication are counted.
• Unbounded growth without compaction: a log that is never truncated grows forever; something must periodically fold applied changes into a checkpoint and discard (or archive) the WAL segments before that point.
• Recovery time scales with log length: if a system crashes long after its last checkpoint, replay has to walk a long WAL, which increases the time-to-recover. This is precisely why WALs are paired with periodic checkpoints.

Corruption detection. Every WAL record typically carries a checksum (a CRC over the record's bytes) and often a monotonically increasing sequence number (Postgres calls this the LSN, log sequence number). On replay, the recovery process verifies each record's checksum before applying it and confirms sequence numbers are contiguous; a checksum mismatch or a gap in the sequence signals a torn write (a partial disk write from a crash mid-fsync) or on-disk corruption, and recovery stops there rather than applying a possibly-corrupt record, treating everything after that point as "not durably committed."

Concrete examples.

• PostgreSQL's WAL: every row-level change is logged before the corresponding heap page is modified on disk; checkpoints periodically flush all dirty pages so WAL segments before the checkpoint can be recycled or archived, and streaming replication ships WAL records to replicas so they can replay the same log independently.
• RocksDB's WAL: writes go to an in-memory memtable plus a WAL simultaneously; when the memtable is flushed to an immutable, sorted on-disk file (an SST file), the WAL segment covering those writes becomes unnecessary and is deleted, so the WAL only ever holds "not yet flushed to SST" data, bounding its size to roughly one memtable's worth of writes.
• A Kafka topic as commit log: the topic itself is the durable, ordered, replayable record of every event; a stream processor's local state (say, a RocksDB-backed aggregation store) can be fully reconstructed at any time by replaying the topic from the earliest retained offset (or from the last checkpointed offset), which is why Kafka's own retention window functions as the outer bound on how far back "replay" can reach.

Interaction with checkpoints and compaction. A checkpoint is a snapshot statement: "everything up to WAL position X is durably reflected in the primary data structure." Once a checkpoint completes, WAL segments entirely before position X are no longer needed for crash recovery (though they may still be retained for other purposes, like point-in-time recovery or replication) and can be reclaimed. Compaction is the analogous idea applied within a log-structured store itself: periodically merging and rewriting data to remove obsolete or duplicate entries, bounding the on-disk footprint. Together, checkpoint-then-truncate is what keeps a WAL's storage usage bounded instead of growing linearly with total lifetime write volume.

Worked example

Consider a stream processor doing stateful aggregation at 50,000 events/sec, checkpointing every 30 seconds, where each event produces roughly a 200-byte WAL record (event payload plus metadata: sequence number, timestamp, checksum).

If the process crashes 29 seconds after the last checkpoint (worst case, just before the next one completes), recovery must replay up to that ~286 MiB of WAL, deserializing and applying roughly 1.5 million records. Halving the checkpoint interval to 15 seconds halves the worst-case replay volume to ~143 MiB (750,000 records), cutting recovery time roughly in half, at the cost of checkpointing twice as often (more overhead on the steady-state write path). This is the concrete shape of the trade-off the drawbacks section names abstractly: shorter checkpoint intervals bound recovery time tighter, at a steady-state throughput cost.

Trade-offs and pitfalls

• Common mistake: treating the WAL as a permanent audit log. A WAL's job is crash recovery up to the next checkpoint; using it as a long-term event history without a separate retention/archival policy either grows storage unboundedly or gets silently truncated by the very compaction process meant to bound it, losing history nobody intended to lose.
• Common mistake: fsync-ing to the wrong barrier. If the acknowledgment to the caller happens before the WAL record is actually durable (e.g. the OS write() call returned but the data is still in a page cache with no fsync), a crash can lose "acknowledged" writes despite the WAL's presence; the durability guarantee only holds up to whatever barrier (fsync, or a replicated quorum ack) the system actually waits on.
• Group commit as the standard mitigation for fsync cost. Fsync-ing after every single write is safe but slow; most production WAL implementations batch multiple concurrent writers' log records into one fsync (group commit), trading a small amount of added latency per write for dramatically higher throughput, since the fsync cost is amortized across the batch.
• A WAL alone does not give you exactly-once, only durable, replayable at-least-once recovery of the log itself; combining it with an idempotent apply step (a keyed upsert or dedup check on write) is what turns "replay never loses data" into "replay never double-applies data" as well.