Q3 - MongoDB Oplog Replay (Keeping a Replica in Sync)
We believe this interview question and close variations of it have frequently appeared in MongoDB's software engineering interviews.
This one is pure MongoDB internals, and exactly the kind of problem MongoDB likes to use: it looks nothing like a textbook LeetCode exercise, yet it is built entirely from fundamentals you already know (a hash map and a sort). What you are really implementing here is the heart of replication.
Every MongoDB replica set has a primary and one or more secondaries. The primary records every write into an ordered log called the oplog (operations log). Each secondary stays in sync by replaying that oplog against its own copy of the data. Change Streams, point-in-time recovery, and initial sync are all built on this same idea. So the task is simple to state and deeply real: given the oplog, reconstruct the data.
A MongoDB oplog is an ordered sequence of entries. Each entry records one write operation against a key/value collection, and every entry carries a logical timestamp ts (a monotonically increasing number that defines order across the replica set).
For this problem an entry has four fields: a timestamp ts, an operation op, a key, and a value.
op = "i"(insert): setkeytovalue(create it, or overwrite if it already exists).op = "u"(update): setkeytovalue, but only if the key already exists. An update to a missing key is a no-op (the document is not there to update).op = "d"(delete): removekey(a delete of a missing key is a harmless no-op).
A secondary applies these entries in order to reconstruct the exact state the primary has.
The oplog is an ordered log. A secondary replays it top to bottom:
ts | op | key | value state after applying this entry
----+----+--------+------- -----------------------------------
1 | i | user:1 | alice { user:1: alice }
2 | i | user:2 | bob { user:1: alice, user:2: bob }
3 | u | user:1 | alice2 { user:1: alice2, user:2: bob }
4 | u | user:3 | carol ( no-op: user:3 does not exist )
5 | d | user:2 | { user:1: alice2 }
6 | i | user:2 | bob2 { user:1: alice2, user:2: bob2 }
Part 1: Replay the oplog (~10 minutes)
Implement replay(entries) that takes the oplog (a list of entries already in ts order) and returns the final key/value state as a map.
Example 1
Input:
entries = [
(ts=1, i, user:1, alice),
(ts=2, i, user:2, bob),
(ts=3, u, user:1, alice2),
(ts=4, u, user:3, carol), # no-op, user:3 absent
(ts=5, d, user:2),
(ts=6, i, user:2, bob2),
]
Output: { user:1: alice2, user:2: bob2 }
The whole problem is one pass: walk the entries in order, and for each one mutate the map according to its op. The single detail that separates a careful answer from a sloppy one is the update semantics: an update to a key that is not present must do nothing, not create it. Say that out loud, because it is the behaviour a real oplog has, and it is the case an interviewer will test.
Why insert and update differ. In a real replica set the primary has already decided what each operation means; the secondary just applies the result. Treating u on a missing key as a no-op is what keeps a secondary faithful to the primary: if the key was deleted earlier (or never existed), an update must not silently resurrect it.
def replay(entries: list[dict]) -> dict:
store = {}
for e in entries:
op, key = e["op"], e["key"]
if op == "i":
store[key] = e["value"]
elif op == "u":
if key in store: # update only an existing key
store[key] = e["value"]
elif op == "d":
store.pop(key, None) # delete is a no-op if absent
return store
Complexity Analysis
- Time: O(n), a single pass over the
noplog entries, with O(1) map operations each. - Space: O(k), where
kis the number of distinct live keys in the final state.
If you reach this point comfortably and quickly, the interviewer will almost always escalate to Part 2. That escalation is the real signal: Part 1 shows you can apply a log, Part 2 shows you understand why replaying a log in the real world is hard. Solving Part 2 is what separates a solid candidate from a strong one.
Part 2: Resumable, idempotent replay (for strong candidates)
In a real replica set, a secondary can crash and restart at any moment. When it comes back, it has already applied the oplog up to some point, recorded as a resume token (the ts of the last entry it durably applied). It then reconnects and re-reads the oplog from the source, and the stream it receives is messy:
- It may redeliver entries the secondary already applied (any entry with
ts <= resumeTs). - It may contain duplicates (the same
tsdelivered more than once after a reconnect). - Entries may arrive out of
tsorder.
Your job is to apply each genuinely new operation exactly once, in ts order, so the secondary lands in the same state it would have reached with a clean replay, and to return the new resume token.
Implement replayFrom(store, entries, resumeTs) that takes the secondary's current store, the freshly delivered entries (possibly redelivered, duplicated, and out of order), and the current resumeTs. It returns the updated store and the new resume token (the largest ts it applied, or the old resumeTs if nothing was new).
Example 2
State: store = { a: 1, b: 2 }, resumeTs = 100
Incoming (messy) oplog:
(ts=90, i, a, 0) -> ts <= 100, already applied, skip
(ts=100, u, b, 2) -> ts <= 100, already applied, skip
(ts=120, u, a, 9) -> new
(ts=110, i, c, 3) -> new, but out of order
(ts=120, u, a, 9) -> duplicate ts, apply once
(ts=130, d, b) -> new
After filter (ts > 100) + dedup by ts + sort: [110, 120, 130]
Apply 110 (i c 3), 120 (u a 9), 130 (d b):
Output: store = { a: 9, c: 3 }, newResumeTs = 130
The shape of the solution is three guards layered on top of the Part 1 apply loop:
- Skip the already-applied. Drop any entry with
ts <= resumeTs. This is what makes replay resumable, you only do new work. - Deduplicate by
ts. A correct oplog has a uniquetsper operation, so a repeatedtsis the same operation redelivered. Keep the first, drop the rest. This is what makes replay idempotent, re-processing the stream changes nothing. - Sort by
ts. Restore the canonical order before applying, since delivery order is not guaranteed.
Then apply with the exact Part 1 semantics, and the new resume token is simply the largest ts you applied.
The sentence that earns the senior nod: "Idempotency and resumability are not extra features here, they are the whole point of a replication protocol. A secondary must be able to crash, reconnect, and re-read an overlapping, out-of-order slice of the oplog and still converge to exactly the primary's state. That is also precisely how Change Streams resume tokens work."
def replay_from(store: dict, entries: list[dict], resume_ts: int):
seen = set()
fresh = []
for e in entries:
ts = e["ts"]
if ts <= resume_ts or ts in seen: # skip applied + duplicates
continue
seen.add(ts)
fresh.append(e)
fresh.sort(key=lambda e: e["ts"]) # restore ts order
for e in fresh:
op, key = e["op"], e["key"]
if op == "i":
store[key] = e["value"]
elif op == "u":
if key in store:
store[key] = e["value"]
elif op == "d":
store.pop(key, None)
new_resume = fresh[-1]["ts"] if fresh else resume_ts
return store, new_resume
Complexity Analysis
- Time: O(n log n), dominated by the sort of the new entries. The filter and dedup pass is O(n), and applying is O(n) with O(1) map operations.
- Space: O(n) for the
seenset and thefreshlist, plus O(k) for the live keys in the store.
A scale-up worth mentioning. If the source guarantees entries arrive sorted within a batch (MongoDB's oplog cursor does return entries in ts order), you can drop the sort entirely and stream with a single running check: skip anything with ts <= lastApplied, apply the rest, advance lastApplied. That turns Part 2 into an O(n), O(1)-extra-space pass. Naming that you would lean on the source's ordering guarantee in production, rather than re-sorting defensively, is the systems instinct MongoDB is listening for.
Final Notes
This problem is a small window into how MongoDB actually works. The same (ts, op, key, value) log, applied idempotently and resumably, is the backbone of replica set sync, Change Streams (whose resume token is conceptually the resumeTs here), and point-in-time recovery. Naming those connections turns a clean coding answer into a "this person understands our database" answer.
A few things that turn a correct answer into a strong one:
1. State the update semantics before you code. The one subtlety in Part 1 is that u on a missing key is a no-op. Saying it out loud (and ideally giving the reason: a secondary must not resurrect a key the primary does not have) signals that you are thinking about correctness, not just translating a spec.
2. Treat idempotency and ordering as the real problem. Anyone can apply a clean log. The interview is won in Part 2, by recognising that a real replication stream overlaps, duplicates, and reorders, and that resumeTs + dedup-by-ts + sort is what makes re-reading it safe. This is the difference between "I can code" and "I understand distributed data."
3. Know when you can drop the sort. If you can rely on the source delivering in ts order (the oplog does), the resumable replay collapses to an O(n), O(1)-extra-space streaming pass. Leading with the general, defensive version and then offering the optimisation under the stated guarantee is the right order, do not over-optimise before you have the guarantee in hand.
4. Walk the boundaries. An empty oplog (state unchanged, token unchanged), a batch where every entry is already applied (ts <= resumeTs), a delete or update of a key that is not present (no-op), and a reinsert after a delete. Each solution above handles these, and stepping through them quickly shows you thought past the happy path.
The bottom line: an original, database-native problem built on the same fundamentals MongoDB always rewards, clean code, careful edge handling, and the systems awareness to see that replaying a log safely is the entire job of a replica.