CSE Roadmap

Specialist tier · about 5 hours · 8 parts

Part 3 of 8 · 2 min read

Conflicts

Two edits at the same moment.

Replicas. Each user has a local copy. A change is applied at once locally and sent to the server and to others asynchronously. This is like multi-leader replication (Level 5), where every user's copy accepts writes.

Locking is too slow. One option is to lock the document, so only one person edits at a time. This is equal to single-leader replication with a transaction. It guarantees no conflict, but others must wait. For live typing, a lock per document is unacceptable. The unit of change is made very small (one keystroke) and no locks are used. That brings the conflict problem back.

A conflict example. The text is "CAT". User 1 inserts "H" at position 0, giving "HCAT". User 2, at the same time, deletes the character at position 2 ("T"), intending "CA". Each applies their own change first. Then each receives the other's change.

  • User 1 gets "delete at position 2" and applies it to "HCAT": it removes "A", giving "HCT". Wrong. User 2's intent was to delete "T".
  • User 2 gets "insert H at 0" and applies it to "CA": gives "HCA".

The two copies differ ("HCT" and "HCA"). The positions in an operation no longer mean the same thing after another edit came first. Two goals appear:

  1. Convergence: all copies end identical.
  2. Intention preservation: each user's change does what the user meant.

Two families of solution.

  • Operational transformation (OT): change each operation to account for others that came before it. Used by Etherpad and Google Docs, as Kleppmann says. Designed for an ordered list of items such as the characters of text.
  • CRDTs (conflict-free replicated data types): data structures that merge automatically in a sensible way, with no central ordering needed. They exist for sets, maps, lists, counters and more.

Convergence

Convergence means that all replicas of the document end in the same state after they have received all edits, whatever the order of arrival.

Example: two users each type a letter at the same place. After both letters arrive everywhere, every screen shows the same two letters in the same order.

Check yourself: 1. Why is locking unsuitable for live typing? 2. What goes wrong when positions are applied unchanged? 3. What are convergence and intention preservation?