Skip to content

Conflict Resolution & Consistency

✅ Required: How do you ensure convergence across all replicas?

✅ Required: What consistency guarantees do you provide (eventual, strong, causal)?

✅ Required: Provide concrete examples of conflict resolution including edge cases

✅ Optional: How do you handle network partitions and split-brain scenarios?

✅ Optional: How does your choice impact system scalability and partition tolerance?

1. Ensure convergence across all replicas with LSEQ

1.1 Comparing OT & CRDT

Operational Transformation is a great algorithm to resolve conflicts in collaborative document editor but it has some limitations that could make our challenge much harder.

1.2 OT limitations

OT algorithms requires that we keep tombstones (logical deletion) to ensure consistency while executing INSERT/REMOVE/UPDATE operations only to maintain the correct order of indexes (IDs) of the document, otherwise, while one user is typing a new character into some index of the text document, you can have other users doing concurrent operations that could get impacted by the previous ones operations.

OT uses a lot of memory as the document grow because of it's state and it require a garbage collector strategy, so it could get too complex to handle.

1.3 Why LSEQ (CRDT) Algorithm?

The List Sequence (LSEQ) algorithm is a type of CRDT algorithm that can handle different types of linear data structures such as lists and arrays. It was built to have deterministic IDs, to be idempotent, scalable, and to provide offline support.

By using LSEQ Algorithm we can resolve conflicts and keep great eventual consistency across replicas easily by propagating deterministic, idempotent and ordered operation events. As LSEQ has idempotency because of it's unique and deterministic IDs, this algorithm doesn't require garbage collector and has optimized memory usage.

LSEQ enable an Offline First approach to handle network partitions and split-brain scenarios. When we have any network failure we can keep editing the document and persisting it's state locally, then when we're back online, we synchronize our local state with the other servers.

1.4 Eventual consistency

Offline support improves partition tolerance across multiple servers and clients. The system provides eventual consistency, ensuring that all replicas of a document converge to the same state over time. Even when multiple users perform concurrent edits, the system guarantees that all changes are eventually applied and merged correctly.

1.5 Scalability

With LSEQ algorithm the horizontal scaling is facilitated as each client handle it's changes locally then send them throught the network to the service synchronization that can autoscale horizontally to handle peak periods.

1.6 Performance

When using LSEQ we don't need to handle centralized locks, so we don't need to block any resource. This improves the throughtput and reduces the average latency.

1.7 Complexity

LSEQ abstract the complexity of CRDT algorithms very well, reducing the learning curve for developers and accelerating the time to market for new products like a Collaborative Document Editor.

We can use NPM packages published by PhD's and papers authors such as @automerge/automerge and Y.js

Check LSEQ Overview for more details.

2. Examples of conflict resolution including edge cases

  • Concurrent inserts at the same position, per example two users insert different characters at the same position. LSEQ generates identifiers that determine a consistent order across all replicas.
  • Support concurrent deletions and inserts, per example when a user deletes a character while another inserts at the same position. LSEQ ensures that the insert is applied at the correct position relative to other elements.
  • Offline edits and later synchronization where users can make changes offline and upon reconnection, LSEQ merges all operations deterministically, maintaining order and idempotency.
  • Even when multiple inserts occur in rapid succession, LSEQ generates identifiers efficiently, avoiding excessive growth in metadata while preserving correct order.