Notes on collaborative document editing

Lesson plan:

Introduction:

• Introduction and Motivation for collaborative editing service (interesting problem from CRTDs video)
• Summary of the rest of the lessons.

Requirements:

• Functional and non-functional req.
• Estimations

Design (to be planned)

• Discuss the API and detailed design
• Explanation why each component is used and what services it can facilitate.

Concurrency in Collaborative Editing

• Operational Transformation
• CRTD

Evaluation

• Concurrency
• Scalability
• Availability
• Consistency

---

Intro

A document is an ordered list of characters. Text editor helps editing the characters in the document. Each character has a value and a positional index. Basic operations are insert and delete. Each insert or delete changes not only the new inserted or deleted character but in some cases the positions of existing characters as well. https://www.youtube.com/watch?v=hy0ePbpna5Y

Collaborative editing: users in different locations editing a document at the same time. There is a local copy of each user. Operations apply locally first and then sent over the network of collaborating users.

document can be anything. Multiple users will be working on the same document at the same time called as collaborative editing.

Problems

• concurrency issues
• latency between users sharing the same document

solution

Locking is not a solution. So we need a lock-free architecture. It will be referred to as a pessimistic approach. The next approach is optimistic which can be either versioning or conflicts resolution or anything similar.

Sync strategies

Depends on the bandwidth.

1. Event passing: also called operational transformation (google docs using this)
2. Differential synchronization. https://www.youtube.com/watch?v=jIR0Ngov7vo (problem statement from here perhaps)
3. CRDTS: Conflict-free replicated data types

Operations in operational transformation (OT) Insert, delete, update, retain. there could be other operations too like formatting changes, creating tables etc.

GIVE AN EXAMPLE OF HOW TYPICAL OPERATIONS LIKE INSERTION AND DELETION WILL LOOK LIKE.

---

Martin Klepman https://www.youtube.com/watch?v=B5NULPSiOGw CRDTs and the Quest for distributed consistency