Replay a key-value log

Many databases never update data in place on disk. They append each change to a log, and rebuild their state after a restart by reading the log from the top. Write the reader.

Write replay(ops):

• ops is a list of operations, oldest first. Each one is a list:
  • ["SET", key, value] sets key to value.
  • ["DEL", key] removes key. Deleting a missing key is fine.
  • ["CLEAR"] removes every key.
• Return the final state as a dict.
• Any other operation name raises ValueError.

>>> replay([["SET", "a", 1], ["SET", "b", 2], ["DEL", "a"], ["SET", "b", 3]])
{'b': 3}

Approach

Fold the log into a dict, one operation at a time.

def replay(ops):
    state = {}
    for op in ops:
        name = op[0]
        if name == "SET":
            state[op[1]] = op[2]
        elif name == "DEL":
            state.pop(op[1], None)
        elif name == "CLEAR":
            state.clear()
        else:
            raise ValueError(f"unknown operation: {name!r}")
    return state

Raising on an unknown operation is deliberate. Skipping it would hand back a state that is quietly wrong, and you’d only find out much later.

Complexity

O(n) for n operations. CLEAR is O(keys) but each key it removes was added by an earlier SET, so the total stays linear.

Why this matters

The log is the source of truth. The dict is a cache you can always rebuild. Redis’s append-only file, a database write-ahead log and a Kafka topic all work this way. The cost is replay time, which grows with the log. So real systems snapshot the state now and then, and replay only the operations after the snapshot. They also compact: once b has been set three times, only the last SET matters.