Detailed Component Design
Concurrent edits and conflict resolution via CRDT
- Supose two users, Alice and Bob
- And document current = ABC
- Alice inserts X after A, and Bob inserts Y after A simultaneously
- Alice will see = AXBC, and bob will see = AYBC
- Both of their operations will receive a globally unique ID.
- Common pattern is: (clientId, sequenNumber)
- Eg: (Alice123, 30), (Bob123, 2) where 30 and 2 are the number of edit's seq no of the client
- Their operations will reach the server
- server's CRDT will then apply these operations
- In this case where both of the edits happened at same time, CRDT defines a deterministic ordering rule over the operation unique Ids to resolve any conflicts like this one
- For eg: the algo can determins (alice123, 30) < (Bob123,2)
- So it will then apply and new doc state is : AXYBC
- These operations are broadcast to Alice and Bob too.
- Their local CRDT follows the same ordering rule so alice and bob will also see: AXYBC
How do collaboration server detect concurrent edits?
- The operation sent to the server also carries a base operation version metadata of the document, meaning the version on which the edit was made to;
- So eg: Alcie and bob both would have sent V100 plus other metadata
- The server uses this metadata to determine whether the operation is causally after existing operations or concurrent with them. If concurrent, the CRDT applies its deterministic conflict-resolution rules.
How do then these two concurrent edits are sent to Kafka and saved to Cassandra to persist
- Both of them are sent independently
- The collaboration server is the authoritative CRDT state machine for an active document. It resolves concurrent operations and assigns a monotonically increasing document version. Kafka stores these accepted operations in that document order. The materializer consumes the ordered operations and persists the resulting document state to Cassandra; it does not independently resolve concurrency.
Kafka:
partition(doc123)
V101 → Alice: insert X after A
V102 → Bob: insert Y after A
Materializer:
Cassandra V100 = ABC
consume V101
→ AXBC
consume V102
→ AXYBC
persist V102
Write/Edit path
- Doc = ABC , User Alice, bob both editing this doc
- Suppose Alice inserts X
- Operation is sent to server via websocket connection
- Server applies the edit to in-mem CRDT state and sends back ACK to alice
- Server then broadcast the cahgne to bob, so bob will then ahve latest doc state too
- The operaiton is then sent to kafka eg
- Materializer consumes this and saves to Cassandra
Now this is very simple eg, in real world, there will be much more edits coming in concurrently and a lot of traffic.,
So we do couple of things,
- first, Load balancer actually uses a hashing to determine which server to send to, this hashing happens via documentid, eg
- hash(documentId) % N - so all req of same doc will always go to same server
- Second, not every keystroke from client is send over to server as opertiaon, rather its batched
- The edit is applied immiediatbltye to their local, but in background those edits are batched, but as we want real time sync with other users - these are batches are flushed in very small interval too.
- So if Alice types 'Hello' instead of 5 oepriaton, 1 operation is send as a batched operation
- Lastly, even materializer does not send each and every operation save to cassandra, rather it will also batch all operations - applies them agains the current version in cassandra, then flush that to save it in cassandra
Reconnecting to doc after being offline
- Suppose Alice was working on doc123, Alice disconnected and reconnected to the document after some time.
- Scenario A:
- Alice reconnected just after few days and her local doc version is V100 while lastest doc state in cassandra has version v105
- SO alice is missing 5 edits
- When Alice reconnects, we would just replay those 5 edits back from kafka operation logs.
- How would we know the offset ID to replay from?
- This is bit tricker part and what i would do here is have a checkpoint store in cassandra.
- So every like at every 50th vestion, we store kafka offset id and partition id,
- eg:
V50, offset123, partion123
v100, offset456, partion456
- So then when we need to repaly, we raply from the closeset checkpoint to current version
- Eg, for our eg, we would check closest checkpoint from loval verstiom which is v100 and they replay 5 vestion until V105 back
- Scnerio B:<ul>
- Alice reconnects after several days/months
- By this time there might be a lot of edits happend to doc as well as, older operation logs are no longer in kafka
- So for thsi, we would just fetch lastest state from kafka and send back to Alice
- And any change that alice has locally is applied/merged on top of this latest doc state vai local CRDT
Failure Handling:
Server crashed
- In-memory cache of CRDT will be lost when server crashes, but again thats just cache no source of truth
- When server is back up again we just built the in-mem state again from cassandra and replay any newer version in kafka pending to be materialized
Cassandra crashes
- Cassandra replicates each document across multiple nodes. If one node fails, requests can be served by other replicas according to the configured consistency level. Failed replicas are repaired through mechanisms such as hinted handoff/read repair/anti-entropy depending on the configuration.
CRDT VS OT tradeoff
CRDT
Pros:
- local optimistic edits
- offline support
- deterministic convergence
- no central transformation algorithm required
Cons:
- more metadata
- more complex
- potentially larger state
OT
Pros:
- mature collaborative-editing approach
- can have lower metadata overhead
Cons:
- transformation logic is complicated
- concurrency handling is harder to reason about
For this design:
I'd choose CRDT because it gives us strong convergence properties and works naturally with local optimistic editing/offline scenarios.