#!/usr/bin/env python3
"""A log-compacted changelog rebuilds the EXACT database, sized by distinct keys, DDIA 2e Ch. 12.

Write ~1,000,000 (key, value) updates -- spread over only ~1,000 distinct keys,
with some deletes (tombstones) -- to an append-only changelog. Then COMPACT the
log: keep only the LATEST record per key, and drop keys whose latest record is a
tombstone. The compacted log holds only ~1,000 records -- its size is set by the
number of DISTINCT LIVE KEYS, not the million writes.

The surprise: you threw away 99.9% of the records, yet the compacted log is a
COMPLETE backup. Start a fresh consumer at offset 0, replay ONLY the compacted
log into a new dict, and it EQUALS the live database exactly -- no separate
snapshot needed. State is a fold over the log; the current value of a key is its
LAST write, so every earlier write is redundant for reconstructing state, and
compaction discards exactly those.

Pure standard library, seeded -> deterministic and reproducible.
"""
import random

N_WRITES = 1_000_000     # total append-only updates to the changelog
N_KEYS = 1_000           # distinct key space the writes are spread over
DELETE_PROB = 0.05       # fraction of writes that are deletes (tombstones)
SEED = 42

TOMBSTONE = object()     # sentinel meaning "this key is deleted"


def build_log():
    """Generate the append-only changelog: a list of (key, value-or-TOMBSTONE)."""
    rng = random.Random(SEED)
    log = []
    for i in range(N_WRITES):
        key = f"key-{rng.randrange(N_KEYS):04d}"
        if rng.random() < DELETE_PROB:
            log.append((key, TOMBSTONE))          # a delete -> tombstone record
        else:
            log.append((key, f"v{i}"))            # a normal update; value carries its offset
    return log


def replay(log):
    """Fold the log into a dict: last write per key wins; a tombstone removes the key."""
    db = {}
    for key, value in log:
        if value is TOMBSTONE:
            db.pop(key, None)
        else:
            db[key] = value
    return db


def compact(log):
    """Keep only the LATEST record per key; drop keys whose latest record is a tombstone.

    Walk the log once. The final surviving value of a key is whatever its last
    record said -- an update keeps the key, a tombstone deletes it. That is
    exactly the set of records needed to reproduce the current state, one per
    live key, in a stable order.
    """
    latest = {}                                   # key -> latest value (or TOMBSTONE)
    for key, value in log:
        latest[key] = value
    compacted = [(k, v) for k, v in latest.items() if v is not TOMBSTONE]
    return compacted


def main():
    print("append-only changelog -> compact -> rebuild a fresh consumer from offset 0")
    print(f"    writes appended        = {N_WRITES:,}")
    print(f"    distinct key space     = {N_KEYS:,}")
    print(f"    deletes (tombstones)   ~ {int(DELETE_PROB * 100)}% of writes\n")

    # 1. The append-only log: a million updates over a thousand keys.
    log = build_log()
    print(f"full log records           = {len(log):,}")

    # 2. The LIVE database = fold the entire log (last write wins; tombstones remove).
    live = replay(log)
    print(f"live database (distinct live keys) = {len(live):,}\n")

    # 3. Compact: keep only the latest surviving record per key.
    compacted = compact(log)
    print(f"compacted log records      = {len(compacted):,}")
    ratio = len(log) / len(compacted)
    print(f"compression ratio          = {ratio:,.1f}x  (full / compacted)")
    dropped = len(log) - len(compacted)
    print(f"records discarded          = {dropped:,}  ({dropped * 100 / len(log):.1f}% of the log)\n")

    # 4. Rebuild: a FRESH consumer replays ONLY the compacted log from offset 0.
    rebuilt = replay(compacted)
    print(f"rebuilt database records   = {len(rebuilt):,}")
    print(f"rebuilt == live            : {rebuilt == live}\n")

    # 5. Size is set by distinct live keys, not the number of writes.
    print(f"compacted size == live key count : {len(compacted) == len(live)}")
    print(f"    the compacted log is a complete backup, sized by distinct keys -- "
          f"not the {N_WRITES:,} writes.")


if __name__ == "__main__":
    main()