Skip to main content

Design a Collaborative Real-time Rich-Text Editor (CRDT/OT Engine)

Problem Statement

Design a collaborative real-time rich-text editing engine (similar to the synchronization cores of Notion, Figma, or Google Docs). The system must allow multiple users to edit the same document concurrently over a simulated network. It must guarantee that all collaborators eventually converge on the exact same document state (Eventual Consistency) without requiring a central database lock, handling concurrent insert and delete conflicts smoothly.

Asked In Companies
Notion Figma Slack Atlassian

Design Decisions & Patterns Used

To design a collaborative editor, we have two primary paradigms: Operational Transformation (OT) and Conflict-free Replicated Data Types (CRDTs). OT requires a smart, centralized server to rewrite index positions on the fly. CRDTs, on the other hand, are decentralized: every character in the document is assigned a unique, globally sortable, fractional position index. As long as operations are applied, the document naturally converges to the same state on all client machines. We will implement a Sequence CRDT using fractional indexing.

We will utilize the following Design Patterns:

  • Command Pattern: Wrapping network operations (inserts/deletes) as serializable payloads to execute locally and transmit across client boundaries.
  • Mediator Pattern: Decoupling collaborators by routing events through a simulated network coordinator.

Functional Requirements

  • Represent a document as an ordered, globally sortable sequence of characters.
  • Support local insert and delete operations, dynamically allocating unique fractional indexes.
  • Support applying remote incoming modifications (insert/delete) from other network nodes.
  • Ensure that even when network events arrive out of order, the text on all client editors converges identical to the character level.

Objects Required

  • CharIdentifier (Globally sortable position index representation)
  • CRDTChar (Value object wrapping character data and its unique position index)
  • CRDTDocument (In-memory document sequence maintaining sorting logic)
  • Collaborator (Representing individual users and client logic)
  • NetworkMediator (Simulated message router syncing collaborators)

CharIdentifier Class

The CharIdentifier class handles fractional positioning. We represent positions as a list of integers to allow infinite nesting (e.g., generating [1, 5] between [1] and [2]) and pair it with a site ID to break ties when two users type at the exact same location.


import java.util.ArrayList;
import java.util.List;

public class CharIdentifier implements Comparable<CharIdentifier> {
    private final List<Integer> position;
    private final String siteId;

    public CharIdentifier(List<Integer> position, String siteId) {
        this.position = new ArrayList<>(position);
        this.siteId = siteId;
    }

    public List<Integer> getPosition() { return position; }
    public String getSiteId() { return siteId; }

    @Override
    public int compareTo(CharIdentifier other) {
        int len1 = this.position.size();
        int len2 = other.position.size();
        int minLen = Math.min(len1, len2);

        for (int i = 0; i < minLen; i++) {
            int comp = Integer.compare(this.position.get(i), other.position.get(i));
            if (comp != 0) return comp;
        }

        if (len1 != len2) {
            return Integer.compare(len1, len2);
        }

        return this.siteId.compareTo(other.siteId);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof CharIdentifier)) return false;
        CharIdentifier other = (CharIdentifier) obj;
        return this.position.equals(other.position) && this.siteId.equals(other.siteId);
    }

    @Override
    public int hashCode() {
        return 31 * position.hashCode() + siteId.hashCode();
    }
}

Let's break down the logic of this class:

  • The constructor copies the positional array to prevent external mutations.
  • The overridden compareTo() method compares position indices element by element. If they are equal, it compares the site/user ID. This ensures that even when users insert text concurrently at the same index, their characters are ordered deterministically.
  • The equals() and hashCode() overrides ensure we can safely lookup and compare identifiers in collections.

CRDTChar Class

The CRDTChar class couples the character value with its immutable sorting identifier.


public class CRDTChar implements Comparable<CRDTChar> {
    private final char value;
    private final CharIdentifier identifier;

    public CRDTChar(char value, CharIdentifier identifier) {
        this.value = value;
        this.identifier = identifier;
    }

    public char getValue() { return value; }
    public CharIdentifier getIdentifier() { return identifier; }

    @Override
    public int compareTo(CRDTChar other) {
        return this.identifier.compareTo(other.getIdentifier());
    }
}

The constructor binds the properties. The overridden compareTo() method delegates to the underlying identifier, keeping document lists sorted by mathematical coordinates.

CRDTDocument Class

The CRDTDocument class maintains the in-memory sequence of characters. It handles fractional index generation when typing locally, and sorts incoming remote characters.


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CRDTDocument {
    private final List<CRDTChar> chars;

    public CRDTDocument() {
        chars = new ArrayList<>();
        // Sentinel limits to ease boundary allocations: root start [0] and max limit [1000]
        CharIdentifier startSentinel = new CharIdentifier(Collections.singletonList(0), "ROOT_START");
        CharIdentifier endSentinel = new CharIdentifier(Collections.singletonList(1000), "ROOT_END");
        
        chars.add(new CRDTChar('\u0000', startSentinel));
        chars.add(new CRDTChar('\u0000', endSentinel));
    }

    public synchronized CRDTChar insert(int index, char value, String siteId) {
        // Adjust index by 1 to skip start sentinel boundary
        int adjIdx = index + 1;
        
        CharIdentifier before = chars.get(adjIdx - 1).getIdentifier();
        CharIdentifier after = chars.get(adjIdx).getIdentifier();
        
        CharIdentifier newId = generateIdentifierBetween(before, after, siteId);
        CRDTChar newChar = new CRDTChar(value, newId);
        
        chars.add(adjIdx, newChar);
        return newChar;
    }

    public synchronized CharIdentifier delete(int index) {
        int adjIdx = index + 1;
        CRDTChar removed = chars.remove(adjIdx);
        return removed.getIdentifier();
    }

    public synchronized int applyInsert(CRDTChar newChar) {
        int insertIdx = Collections.binarySearch(chars, newChar);
        if (insertIdx < 0) {
            insertIdx = -(insertIdx + 1);
        }
        chars.add(insertIdx, newChar);
        return insertIdx - 1; // convert back to client logical index
    }

    public synchronized int applyDelete(CharIdentifier identifier) {
        for (int i = 1; i < chars.size() - 1; i++) {
            if (chars.get(i).getIdentifier().equals(identifier)) {
                chars.remove(i);
                return i - 1;
            }
        }
        return -1;
    }

    private CharIdentifier generateIdentifierBetween(CharIdentifier before, CharIdentifier after, String siteId) {
        List<Integer> posBefore = before.getPosition();
        List<Integer> posAfter = after.getPosition();
        List<Integer> newPos = new ArrayList<>();

        int i = 0;
        while (true) {
            int valBefore = i < posBefore.size() ? posBefore.get(i) : 0;
            int valAfter = i < posAfter.size() ? posAfter.get(i) : 1000;

            if (valAfter - valBefore > 1) {
                // Midpoint found, allocate coordinate between values
                newPos.add(valBefore + (valAfter - valBefore) / 2);
                break;
            } else {
                newPos.add(valBefore);
                i++;
            }
        }
        return newCharIdentifier(newPos, siteId);
    }

    private CharIdentifier newCharIdentifier(List<Integer> newPos, String siteId) {
        return new CharIdentifier(newPos, siteId);
    }

    public synchronized String getPlainText() {
        StringBuilder sb = new StringBuilder();
        // Skip sentinels at index 0 and size() - 1
        for (int i = 1; i < chars.size() - 1; i++) {
            sb.append(chars.get(i).getValue());
        }
        return sb.toString();
    }
}

Here is an explanation of the core operations in the CRDTDocument class:

  • The constructor configures sentinel boundaries so we always have neighbors to calculate relative coordinates.
  • insert() finds the adjacent identifiers, generates a midpoint coordinate, instantiates a new character, and inserts it.
  • applyInsert() uses binary search to find the correct index based on the character's coordinate, integrating remote edits deterministically.
  • applyDelete() scans for a matching coordinate ID and removes the character.
  • generateIdentifierBetween() compares coordinates digit-by-digit. If the difference between adjacent coordinates is 1 or less, it appends a digit to generate a nested fraction (e.g., generating [1, 5] between [1] and [2]).
  • getPlainText() reconstructs the text by stripping the boundary sentinels.

Collaborator & NetworkMediator Classes

These classes orchestrate client logic and simulate net transfers. We apply the **Mediator Pattern** to decouple the collaborator instances.


import java.util.ArrayList;
import java.util.List;

public class NetworkMediator {
    private final List<Collaborator> peers = new ArrayList<>();

    public void registerPeer(Collaborator collaborator) {
        peers.add(collaborator);
    }

    public void broadcastInsert(Collaborator sender, CRDTChar c) {
        for (Collaborator peer : peers) {
            if (peer != sender) {
                peer.receiveRemoteInsert(c);
            }
        }
    }

    public void broadcastDelete(Collaborator sender, CharIdentifier identifier) {
        for (Collaborator peer : peers) {
            if (peer != sender) {
                peer.receiveRemoteDelete(identifier);
            }
        }
    }
}

The NetworkMediator coordinates operations. broadcastInsert() and broadcastDelete() route modification payloads to registered collaborators.


public class Collaborator {
    private final String siteId;
    private final CRDTDocument document;
    private final NetworkMediator network;

    public Collaborator(String siteId, NetworkMediator network) {
        this.siteId = siteId;
        this.document = new CRDTDocument();
        this.network = network;
        network.registerPeer(this);
    }

    public void localInsert(int index, char value) {
        CRDTChar newChar = document.insert(index, value, siteId);
        network.broadcastInsert(this, newChar);
    }

    public void localDelete(int index) {
        CharIdentifier removedId = document.delete(index);
        network.broadcastDelete(this, removedId);
    }

    public void receiveRemoteInsert(CRDTChar c) {
        document.applyInsert(c);
    }

    public void receiveRemoteDelete(CharIdentifier identifier) {
        document.applyDelete(identifier);
    }

    public String getEditorContent() {
        return document.getPlainText();
    }
    
    public String getSiteId() { return siteId; }
}

Here is an explanation of the core operations in the Collaborator class:

  • The constructor registers the collaborator instance in the network pool.
  • localInsert() inserts a character locally, generates coordinates, and broadcasts the change.
  • receiveRemoteInsert() and receiveRemoteDelete() integrate remote changes directly.

Main Driver Class

This class tests our collaborative CRDT editor by simulating concurrent typing and verifying document convergence.


public class Main {
    public static void main(String[] args) {
        NetworkMediator network = new NetworkMediator();

        // Instantiate two collaborators sharing the simulated network
        Collaborator alice = new Collaborator("Alice", network);
        Collaborator bob = new Collaborator("Bob", network);

        System.out.println("--- Initial State ---");
        System.out.println("Alice's editor: '" + alice.getEditorContent() + "'");
        System.out.println("Bob's editor: '" + bob.getEditorContent() + "'");

        // Alice types "CAT"
        System.out.println("\n--- Alice types 'C', 'A', 'T' ---");
        alice.localInsert(0, 'C');
        alice.localInsert(1, 'A');
        alice.localInsert(2, 'T');

        System.out.println("Alice's editor: '" + alice.getEditorContent() + "'");
        System.out.println("Bob's editor: '" + bob.getEditorContent() + "'");

        // Bob inserts 'S' at index 3 (appending) and Alice concurrently inserts 'S' at index 0 (prepending)
        System.out.println("\n--- Concurrent Edits: Alice prepends 'S', Bob appends 'S' ---");
        alice.localInsert(0, 'S'); // Expected document: SCAT
        bob.localInsert(3, 'S');   // Expected document: CATS

        // Verify that their documents converge
        System.out.println("\n--- Final States (Should match and read 'SCATS') ---");
        System.out.println("Alice's editor: '" + alice.getEditorContent() + "'");
        System.out.println("Bob's editor: '" + bob.getEditorContent() + "'");
    }
}

The main() driver initializes the network, registers clients, triggers concurrent edits, and verifies that the documents converge on the identical value (SCATS) on both editors.

Also See

Comments

Post a Comment

Popular posts from this blog

Designing a Parking Lot - Low Level Design

Problem Statement Design a parking lot that can handle vehicles entering and leaving while managing parking across multiple floors. Each vehicle should be assigned a suitable parking spot based on its type, and the spot should be freed once the vehicle exits. The design should also support generating a ticket at entry and optionally calculating the parking fee based on the duration of stay. Asked In Companies Amazon Google Microsoft Uber Walmart Flipkart Meta PayPal Oracle Salesforce Adobe Apple Intuit LinkedIn Atlassian Functional Requirements The design should support multiple vehicle types such as bikes, cars, and trucks A vehicle must be assigned a parking spot compatible with its type A parking spot cannot be assigned to more than one vehicle at a time The parking lot should support multiple levels (floors) The design should search and allocate an availa...
Post a Comment
Read more

Most Frequently Asked Low Level Design(LLD) Interview Questions

Below are the curated list of most commonly asked Low Level Design (LLD) interview problems. Each problem includes a short description and a link to the complete solution with code and class diagrams. Design Parking Lot System The system should handle parking for different vehicle types such as bikes, cars, and trucks. It should manage slot allocation, availability tracking, and entry/exit flow. The design also ensures efficient usage of parking space under varying load conditions. View Solution Design Elevator / Lift System The system should support multiple elevators operating across floors with request handling logic. It focuses on scheduling algorithms to minimize wait time and optimize movement. It also manages direction control and concurrent floor requests. View Solution Design Movie Ticket Booking System The system should allow users to browse movies, select shows, and book seats. It handles seat ...
Post a Comment
Read more

Software Design Patterns for LLD Interviews: A Complete Guide

Software Design Patterns for LLD Interviews: A Complete Guide In Software Development Engineer (SDE) interviews—especially for mid-level and senior roles—low-level design (LLD) rounds assess your ability to write clean, reusable, maintainable, and extensible code. The foundation of resolving these architectural challenges lies in the standard Gang of Four (GoF) Design Patterns. Rather than memorizing theoretical definitions, interviewers expect you to apply these patterns to real-world scenarios, identifying the trade-offs of each. Below is a comprehensive guide to the 12 most frequently asked design patterns in LLD interviews, categorized by their classification (Creational, Structural, and Behavioral). Each pattern contains a concrete, real-world Java implementation and a detailed breakdown of design decisions. Creational Design Patterns Creational design patterns deal with object creation mechanisms. They abstract the instantiation process, making a system independent of how...
Post a Comment
Read more