DSA Studio

WAL Replay

easy · distributed-systems, storage, durability

WAL Replay

A write-ahead log (WAL) records updates in the exact order they happened. To recover a key-value store after a crash, replay the log from the beginning.

Each log entry either:

  • sets a key to a value, or
  • deletes a key.

Return the final visible key-value state sorted by key ascending.

Input is the complete durable log prefix available after a crash. Torn records, filesystem synchronization, transaction commit, and table installation are outside this function. Do not mutate the input.

Types

type LogEntry struct {
    Key     string
    Value   string
    Deleted bool
}

type KV struct {
    Key   string
    Value string
}

Function signature

func ReplayWAL(entries []LogEntry) []KV

Exact semantics

  • Replay entries in input order, left to right.
  • For a set entry (Deleted=false), write state[Key] = Value.
  • For a delete entry (Deleted=true), remove Key from state.
  • Deleting a missing key is allowed and is a no-op.
  • A key may be deleted and later re-created by a newer set.
  • Final output must contain only existing keys, sorted by key.
Hint: represent replay state and build deterministic output 1. Create `state := map[string]string{}`. 2. Loop over `entries` in order. 3. If `entry.Deleted`, call `delete(state, entry.Key)`. 4. Else assign `state[entry.Key] = entry.Value`. 5. Collect keys from map into a slice. 6. Sort keys ascending. 7. Build result `[]KV` in sorted-key order.

Examples

entries = [
  {Key:"a", Value:"1"},
  {Key:"b", Value:"2"},
  {Key:"a", Deleted:true}
]
output = [{Key:"b", Value:"2"}]

entries = [
  {Key:"x", Deleted:true},
  {Key:"x", Value:"9"}
]
output = [{Key:"x", Value:"9"}]

entries = [
  {Key:"k", Value:"1"},
  {Key:"k", Value:"2"},
  {Key:"k", Value:"3"}
]
output = [{Key:"k", Value:"3"}]

Complexity target

  • Replay pass: O(n)
  • Sorting output keys: O(m log m), where m is number of remaining keys
  • Extra space: O(m)

Notes

  • If a key is deleted, it should not appear in the output.
  • Output must be sorted by key ascending.
Run tests to see results
No issues detected
    Join Discord