Resume tokens for reliability in MongoDB - Time & Space Complexity

Time Complexity: Resume tokens for reliability

O(1)

Understanding Time Complexity

When using resume tokens in MongoDB change streams, it's important to understand how the time to resume watching changes as the data grows.

We want to know how the cost of resuming a stream scales with the size of the data or events.

Scenario Under Consideration

Analyze the time complexity of resuming a change stream using a resume token.

const changeStream = collection.watch([], { resumeAfter: resumeToken });
changeStream.on('change', (change) => {
  console.log(change);
});
    

This code resumes watching changes from a specific point using a resume token.

Identify Repeating Operations

Look at what happens when resuming the stream.

• Primary operation: The database locates the resume token in the oplog (operation log).
• How many times: This is a single lookup operation to find the resume point before streaming new changes.

How Execution Grows With Input

The time to find the resume token depends on how the oplog is indexed and stored.

Input Size (n)	Approx. Operations
10	Few operations to find token
100	Still a few operations due to indexing
1000	Still a few operations, efficient lookup

Pattern observation: The lookup time stays roughly the same because the oplog is indexed, so finding the resume token does not slow down as data grows.

Final Time Complexity

Time Complexity: O(1)

This means resuming with a token takes about the same time no matter how many changes have happened before.

Common Mistake

[X] Wrong: "Resuming a change stream takes longer as more changes happen because it has to scan all previous events."

[OK] Correct: MongoDB uses an index on the oplog, so it can jump directly to the resume token without scanning all earlier events.

Interview Connect

Understanding how resume tokens work and their time cost shows you know how databases keep streams reliable and efficient, a useful skill for real-world applications.

Self-Check

What if the oplog was not indexed? How would the time complexity of resuming with a token change?