Design a collaborative offline text editor: why index-based operations diverge, and how a sequence CRDT converges whatever order operations arrive in.

26.6.1 · L8 · Interview

Predict first

Concurrent inserts and a delete are delivered in all 120 orders. How do index-based and id-based operations compare?

struct ID: Hashable, Comparable { let c: Int; let r: Int; static func < (a: ID, b: ID) -> Bool { (a.c, a.r) < (b.c, b.r) } }
struct Op { let id: ID; let after: ID?; let ch: Character?; let del: ID? }   // insert after `after`, or delete `del`
struct Replica {
    var items: [(id: ID, ch: Character, dead: Bool)] = []; var pending: [Op] = []
    mutating func apply(_ op: Op) {
        pending.append(op)
        var progress = true
        while progress {
            progress = false
            for (i, p) in pending.enumerated() {
                if let d = p.del {
                    guard let k = items.firstIndex(where: { $0.id == d }) else { continue }
                    items[k].dead = true
                } else {
                    var pos = 0
                    if let a = p.after { guard let k = items.firstIndex(where: { $0.id == a }) else { continue }; pos = k + 1 }
                    while pos < items.count && items[pos].id > p.id { pos += 1 }   // RGA rule: skip newer siblings
                    items.insert((p.id, p.ch!, false), at: pos)
                }
                pending.remove(at: i); progress = true; break
            }
        }
    }
    var text: String { String(items.filter { !$0.dead }.map(\.ch)) }
}
// "ab" typed by replica 1; then concurrently replica 1 inserts X after a, replica 2 inserts Y after a, replica 2 deletes b
let a = ID(c: 1, r: 1), b = ID(c: 2, r: 1)
let ops = [Op(id: a, after: nil, ch: "a", del: nil), Op(id: b, after: a, ch: "b", del: nil),
           Op(id: ID(c: 3, r: 1), after: a, ch: "X", del: nil), Op(id: ID(c: 3, r: 2), after: a, ch: "Y", del: nil),
           Op(id: ID(c: 4, r: 2), after: nil, ch: nil, del: b)]
func perms(_ x: [Op]) -> [[Op]] { x.count <= 1 ? [x] : x.indices.flatMap { i in perms(Array(x[..<i] + x[(i+1)...])).map { [x[i]] + $0 } } }
var results = Set<String>(); var count = 0
for p in perms(ops) { var r = Replica(); p.forEach { r.apply($0) }; results.insert(r.text); count += 1 }
print("delivery orders tried:", count, "distinct final texts:", results.sorted())
// the naive version: ops carry an index into the visible string
func naive(_ order: [(Int, Character)]) -> String { var s = Array("ab"); for (i, c) in order { s.insert(c, at: min(i, s.count)) }; return String(s) }
print("index-based inserts, two orders:", naive([(1, "X"), (1, "Y")]), naive([(1, "Y"), (1, "X")]))

The id-based version always ends with "aYX"; index-based inserts give "aYXb" or "aXYb" depending on order
Both always converge
The id-based version needs a central server to converge

Mental model. Instead of saying “write on line 3”, every sentence is stuck to the one before it with a numbered tag. Reorder the arrivals however you like; the tags still tell you where each piece goes.

Two people edit the same document, one of them offline. If an edit is “insert X at index 1”, the meaning of the index depends on what has been applied before it, so applying concurrent edits in different orders gives different texts. The check shows it for the simplest case: starting from ab, inserting X and Y at index 1 gives aYXb in one order and aXYb in the other, so the replicas diverge for good. There are two families of fix. Operational transformation rewrites incoming operations against concurrent ones and needs a central server to order them. A sequence CRDT (here RGA, replicated growable array) instead gives every character a unique id (counter, replica) and expresses an insert as “after the character with id r”; deletes mark a character as a tombstone. The operations then commute: the same set applied in any causally valid order produces the same document.

The check applies five operations (two concurrent inserts after a and a delete of b) in all 120 delivery orders, buffering an operation until the character it refers to exists (causal delivery), and every order ends with the text aYX. The insert rule that makes ties deterministic is that, among siblings inserted after the same character, the one with the larger id comes first. Costs to name in an interview: tombstones and per-character ids make documents bigger (production libraries compress runs and garbage-collect tombstones once every replica has seen them), cursors and selections must be mapped by id rather than index, undo is per user and must be an inverse operation, and a server is still useful for relay, persistence, access control and presence. On iOS keep the CRDT state in the local database, persist unsent operations (Q340), render through a diffable text storage so remote edits do not reset the caret, and debounce network sends. This is a model, not a full editor: rich-text attributes, moves and very large documents need a real library and more design.

Commuting operations converge in any causal order; index-based operations do not.

Common traps

Sending positions as integers. The index changes meaning as other edits land, so replicas diverge.
Applying an operation before its reference exists. Buffer it until the character it points to has arrived.

They might follow up with

OT or CRDT? OT keeps documents small but needs a central transformer and is notoriously hard to get right; CRDTs work peer to peer and offline at the cost of metadata.
What about simple fields? Per-field last-writer-wins is enough for a title; only the text body needs a sequence type.

Design a collaborative offline text editor: why index-based operations diverge, and how a sequence CRDT converges whatever order operations arrive in.

Predict first

Common traps

They might follow up with

Related questions