Causal consistency concept in MongoDB - Time & Space Complexity

Time Complexity: Causal consistency concept

O(n)

Understanding Time Complexity

When using causal consistency in MongoDB, we want to understand how the time to read or write data changes as more operations happen.

We ask: How does the system keep track of cause-and-effect relationships without slowing down too much?

Scenario Under Consideration

Analyze the time complexity of reading data with causal consistency enabled.

const session = client.startSession({
  causalConsistency: true
});

const collection = client.db('test').collection('items');

session.withTransaction(async () => {
  await collection.insertOne({ item: 'apple' }, { session });
  const doc = await collection.findOne({ item: 'apple' }, { session });
  console.log(doc);
});
    

This code starts a session with causal consistency, inserts a document, then reads it within a transaction.

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Reading and writing documents with causal tracking.
• How many times: Each read or write checks causal history, which grows with the number of related operations.

How Execution Grows With Input

As more operations happen, the system tracks more cause-effect links.

Input Size (n)	Approx. Operations
10	Checks causal info for about 10 operations
100	Checks causal info for about 100 operations
1000	Checks causal info for about 1000 operations

Pattern observation: The time to verify causal order grows roughly with the number of related operations.

Final Time Complexity

Time Complexity: O(n)

This means the time to maintain causal consistency grows linearly with the number of related operations.

Common Mistake

[X] Wrong: "Causal consistency means reads and writes always take the same time regardless of history."

[OK] Correct: The system must track past operations to keep order, so more history means more work and longer time.

Interview Connect

Understanding how causal consistency affects time helps you explain real-world trade-offs in databases, showing you know how systems balance correctness and speed.

Self-Check

"What if we disabled causal consistency? How would the time complexity of reads and writes change?"