Real-Time Collaborative Text Editor Using CRDTs

This project was implemented as a part of the Distributed Systems (CS3.401) coursework at IIIT Hyderabad by

• M P Samartha (2023102038)
• Vinay R (2019112020)

A fully distributed collaborative text editor implementing Conflict-Free Replicated Data Types (CRDTs). This project demonstrates how to build a system where multiple users can edit the same document concurrently without a central server resolving conflicts.

Features

• Real-time collaborative editing - Multiple users can edit the same document simultaneously
• Two CRDT implementations - LWW (state-based) and WOOT (operation-based)
• Rich-text formatting - Bold, italic, underline, text color, highlight
• Live cursor tracking + user list - See who is editing and where
• Local undo/redo - Per-client undo/redo stacks
• State persistence - Documents are automatically saved to disk
• Causal ordering - Vector clocks ensure causally consistent updates
• Benchmark harness - Latency, bandwidth, throughput measurements + notebook visualization

Architecture

The system consists of three layers:

1. CRDT Engine (Backend)

• LWW Element Set (state-based CRDT)
  • Each character assigned a unique (site_id, logical_timestamp) pair
  • Order is maintained with a floating order value to insert between neighbors
  • Deterministic merge ensures convergence
  • Vector clocks prevent causal inconsistencies
• WOOT Sequence CRDT (operation-based CRDT)
  • Inserts reference prev_id and next_id neighbors
  • Missing dependencies are queued and integrated later
  • Tombstones preserve deletions while keeping IDs stable

2. Networking Layer (Backend)

• WebSocket relay server - Routes operations between clients
• Dumb routing - Server doesn't resolve conflicts; just relays messages
• JSON-based messaging - Simple and debuggable protocol
• Connection management - Handles client add/remove with graceful cleanup

3. Client Editor (Frontend)

• Vue.js UI - Responsive, modern editor interface
• Client-side CRDT - Each client maintains local CRDT state
• Immediate feedback - Local edits appear instantly
• Automatic sync - Changes synced to server and other clients
• Formatting + cursors - Rich text styling and remote cursor labels

Tech Stack

• Backend: Python 3.11+, WebSockets (websockets library)
• Frontend: HTML5, Vue.js 3, vanilla JavaScript
• Storage: JSON files (in ./data/ directory)
• Testing: pytest
• Benchmarking: Python multiprocessing, CSV outputs, Jupyter notebook visualization

Project Structure

.
├── backend/
│   ├── crdt/
│   │   ├── base.py          # Abstract CRDT interface
│   │   ├── factory.py       # CRDT factory + type normalization
│   │   ├── lww_set.py       # LWW CRDT implementation
│   │   ├── vector_clock.py  # Causal ordering
│   │   └── woot.py          # WOOT CRDT implementation
│   ├── networking/
│   │   ├── server.py        # WebSocket server
│   │   ├── message.py       # Message serialization
│   │   └── document_manager.py  # Document state management
│   ├── storage/
│   │   └── persistence.py   # JSON persistence layer
│   ├── main.py              # Server entry point
│   ├── config.py            # Configuration constants
│   └── requirements.txt      # Python dependencies
├── benchmarks/
│   ├── bench_client.py      # Headless benchmark client
│   ├── metrics.py           # Aggregation helpers
│   ├── run_benchmarks.py    # Benchmark runner
│   └── workloads.py         # Workload generators
├── data/
├── frontend/
│   ├── index.html           # Editor UI
│   ├── styles.css           # Styling
│   ├── editor.js            # Vue.js app and UI logic
│   └── crdt-client.js       # Client-side CRDT implementation
├── tests/
│   ├── test_integration.py  # Integration tests
│   ├── test_lww_crdt.py     # LWW CRDT tests
│   ├── test_vector_clock.py # Vector Clock tests
│   └── test_woot_crdt.py    # WOOT CRDT tests
├── benchmark_results.ipynb
├── run_server.py
├── report.tex
├── README.md
└── .gitignore

Setup & Installation

Prerequisites

• Python 3.11 or higher
• pip (Python package manager)
• Modern web browser (Chrome, Firefox, Safari, Edge)

Backend Setup

# Install Python dependencies
cd backend
pip install -r requirements.txt

# Create data directory for persistence
mkdir -p ../data

Frontend Setup

No additional setup needed! The frontend is pure HTML/JS/CSS with Vue.js loaded from CDN.

Running the Project

Quick Start: Run Both Servers

Open TWO terminal windows:

Terminal 1: Start the Backend Server

python run_server.py --crdt lww

Use --crdt woot to switch the server to WOOT:

python run_server.py --crdt woot

You should see:

INFO:backend.main:Starting Collaborative Text Editor Server
INFO:backend.main:Listening on ws://localhost:8765

Terminal 2: Start the Frontend HTTP Server

cd frontend
python -m http.server 8000

You should see:

Serving HTTP on 0.0.0.0 port 8000 (http://0.0.0.0:8000/) ...

Open the Editor

1. Open your browser and navigate to: http://localhost:8000
2. You should see the login modal
3. Enter a Document ID (e.g., "my-doc")
4. Enter your name (or leave blank for auto-generated name)
5. Click Connect

Using Multiple Clients

1. Open http://localhost:8000 in multiple browser tabs/windows
2. Connect each to the same document ID
3. Type in one editor - see it appear in others instantly!

---

Start the Server (if using Python module)

Option 2: Using Python module

python -m backend.main --crdt lww

Option 3: From backend directory

cd backend
python -m main --crdt lww

Testing

Run All Tests

# From project root
python -m pytest tests/ -v

Run Specific Test Suites

# Vector Clock tests only
python -m pytest tests/test_vector_clock.py -v

# LWW CRDT tests only
python -m pytest tests/test_lww_crdt.py -v

# WOOT CRDT tests only
python -m pytest tests/test_woot_crdt.py -v

# Integration tests
python -m pytest tests/test_integration.py -v

# Run with coverage
python -m pytest tests/ --cov=backend --cov-report=html

Benchmarking

The benchmark harness runs the server locally and spawns multiple headless clients to measure latency, bandwidth, throughput, and convergence time for both LWW and WOOT under different workloads and scale settings.

Run Benchmarks (Default Matrix)

python -m benchmarks.run_benchmarks

Default matrix:

• CRDTs: lww, woot
• Clients: 3, 4
• Ops per client: 10, 100, 500
• Doc sizes: 1000, 5000, 10000
• Workloads: sequential, concurrent_same, concurrent_random, mixed

Custom Benchmark Runs

python -m benchmarks.run_benchmarks \
  --crdt lww,woot \
  --clients 3,4 \
  --ops 10,100,500 \
  --doc-size 1000,5000,10000 \
  --workloads sequential,concurrent_same,concurrent_random,mixed \
  --output-dir benchmarks/results \
  -j 2

Output Files

Each run produces two CSV files under benchmarks/results/:

• <run_id>_summary.csv — p50/p95/p99 latency, bandwidth totals, throughput, and convergence time.
• <run_id>_latencies.csv — per-op latency samples for plotting.

The notebook Team26_GossipGang_Benchmark_Results.ipynb contains tables and plots for comparing LWW vs WOOT across the default matrix.

Notes

• Benchmarks run the WebSocket server automatically per CRDT. Use --reuse-server if you want to start the server manually.
• Convergence time is measured as the delay between the last sent operation and the last applied operation across all clients.

Usage Example

Scenario: Two users editing simultaneously

1. User 1: Opens browser, connects to document "collab-doc"

   • Types: "Hello"
   • Content: "Hello"

2. User 2: Opens another browser, connects to same "collab-doc"

   • Receives initial state: "Hello"
   • Types: " World"
   • Content: "Hello World"

3. User 1: Receives User 2's changes instantly

   • Content: "Hello World"

4. User 1: Deletes "World", types "CRDT"

   • Content: "Hello CRDT"

5. User 2: Sees the change

   • Content: "Hello CRDT"

No conflicts! CRDTs automatically handle concurrent edits.

API

Client → Server Messages

// Connect to document
{
  "type": "connect",
  "doc_id": "my-doc",
  "user_id": 12345,
  "site_id": 67890,
  "data": { "username": "Alice" }
}

// Insert character (LWW)
{
  "type": "insert",
  "doc_id": "my-doc",
  "user_id": 12345,
  "site_id": 67890,
  "data": {
    "position": 0,
    "char": "a",
    "timestamp": 1,
    "id": "67890:1",
    "order": 0.5,
    "attrs": { "bold": false, "italic": false, "underline": false }
  }
}

// Insert character (WOOT)
{
  "type": "insert",
  "doc_id": "my-doc",
  "user_id": 12345,
  "site_id": 67890,
  "data": {
    "id": "67890:5",
    "char": "a",
    "prev_id": "HEAD",
    "next_id": "TAIL",
    "attrs": { "bold": false, "italic": false, "underline": false }
  }
}

// Delete character (LWW)
{
  "type": "delete",
  "doc_id": "my-doc",
  "user_id": 12345,
  "site_id": 67890,
  "data": { "position": 0, "timestamp": 2, "id": "67890:1" }
}

// Delete character (WOOT)
{
  "type": "delete",
  "doc_id": "my-doc",
  "user_id": 12345,
  "site_id": 67890,
  "data": { "id": "67890:5" }
}

// Format range
{
  "type": "format",
  "doc_id": "my-doc",
  "user_id": 12345,
  "site_id": 67890,
  "data": {
    "ids": ["67890:1", "67890:2"],
    "attrs": { "bold": true }
  }
}

// Move cursor
{
  "type": "cursor_move",
  "doc_id": "my-doc",
  "user_id": 12345,
  "site_id": 67890,
  "data": { "position": 5, "username": "Alice", "client_id": 1 }
}

Server → Client Messages

// Ack (assigned client ID)
{
  "type": "ack",
  "doc_id": "my-doc",
  "user_id": 12345,
  "site_id": 67890,
  "data": { "client_id": 1 }
}

// State sync (on connection)
{
  "type": "state_sync",
  "doc_id": "my-doc",
  "user_id": 0,
  "site_id": 0,
  "data": {
    "crdt_type": "lww",
    "crdt_state": {
      "site_id": 67890,
      "logical_clock": 10,
      "elements": { ... }
    }
  }
}

// User list update
{
  "type": "user_list",
  "doc_id": "my-doc",
  "user_id": 0,
  "site_id": 0,
  "data": {
    "users": [
      { "client_id": 1, "username": "Alice", "cursor_position": 5, "user_id": 12345 }
    ]
  }
}

How CRDTs Work

LWW Element Set (state-based)

Each character is tagged with:

• value: The character
• site_id and timestamp: A unique ID per insertion
• order: A floating-point position value used to insert between neighbors
• deleted: Tombstone flag

On merge, replicas combine their element sets deterministically, using vector clocks to preserve causal ordering and last-write-wins semantics for conflicts.

WOOT Sequence CRDT (operation-based)

Each character is a node with a stable ID and two references:

• prev_id / next_id: Neighbor pointers used to place the character
• visible: Whether the character is deleted (tombstone)

If an insert arrives before its neighbors, it is queued in a pending list until dependencies are present. This yields deterministic convergence without a central transformer.

Limitations & Future Work

Current Limitations

• Single relay server (no P2P gossip protocol yet)
• No offline queue (edits require an active connection)
• No authentication or access control
• Single-document UI (one document per client session)
• WOOT integration is not optimized (linear scans under heavy concurrency)

Future Enhancements

1. P2P Gossip Sync - Peer-to-peer document sync
2. Offline operation queue - Replay local edits on reconnect
3. Authentication - Access control per document
4. WOOT indexing - Faster insert integration using indexed structures
5. Multi-document support - Edit multiple docs per client
6. Benchmark automation - Extended workloads and visualization reports

Configuration

Edit backend/config.py to customize:

# Server
SERVER_HOST = "localhost"
SERVER_PORT = 8765

# Document
MAX_DOCUMENT_SIZE = 10 * 1024 * 1024  # 10MB

# Storage
STORAGE_DIR = "./data"
AUTO_PERSIST_INTERVAL = 30  # seconds

# Logging
LOG_LEVEL = "INFO"

Troubleshooting

"426 Upgrade Required" or "invalid Connection header" Error

This happens when you open the HTML file directly with file:// protocol instead of via HTTP.

Solution:

1. ✗ Do NOT do this:

   • Double-click frontend/index.html
   • Use file:///path/to/index.html

2. ✓ Do this instead:

   cd frontend
   python -m http.server 8000
   # Then open http://localhost:8000 in browser

"Connection refused" error

• Ensure backend server is running on ws://localhost:8765
• Check that you ran python run_server.py --crdt lww (or --crdt woot) in the first terminal
• Check firewall settings
• Try a different port in config.py
• Check browser console (F12 → Console tab) for detailed error messages

Debugging WebSocket Connection

1. Open browser developer tools: Press F12
2. Go to Console tab: You'll see logs like:
   • Connecting to WebSocket: ws://localhost:8765
   • WebSocket connected (if successful)
   • Error messages if connection fails
3. Check Network tab: Look for the WebSocket connection (filter by "ws")
   • Should see ws://localhost:8765 with status 101 Switching Protocols
4. Server logs: Check the terminal running python run_server.py --crdt lww for server-side errors

"Failed to connect" in UI

• ✓ Check that both servers are running:
  • Backend: python run_server.py --crdt lww
  • Frontend: cd frontend && python -m http.server 8000
• Check browser console (F12) for detailed error
• Verify URLs:
  • Frontend: http://localhost:8000 (not file://)
  • WebSocket: ws://localhost:8765
• Try a fresh page reload (Ctrl+Shift+R or Cmd+Shift+R)
• Check that firewall allows connections to ports 8000 and 8765

"CRDT type mismatch" error

• The server enforces a single CRDT type. Restart the server with the same --crdt option for all clients and documents.

Documents not persisting

• Check that ./data/ directory exists and is writable
• Look for errors in server console
• Verify STORAGE_DIR in config.py

Cursor positions not syncing

• Cursor sync is for UI display; documents always converge
• Check browser console for WebSocket errors

Tests failing

• Ensure pytest and pytest-asyncio are installed: pip install -r backend/requirements.txt
• Run tests from project root: cd /path/to/project
• Use -p no:asyncio flag to skip async plugin issues

Verification & Validation

Unit Tests

python -m pytest tests/ -v -p no:asyncio

Validates:

• Vector clock causal ordering
• LWW CRDT insertion/deletion
• WOOT CRDT insertion/deletion
• State merging and convergence
• Serialization/deserialization

Manual Testing Scenarios

Test 1: Concurrent Inserts

1. Open two browsers to "test-doc"
2. User 1 types "A", User 2 types "B" simultaneously
3. Both see "AB" (deterministic ordering by site_id) ✓ Pass: Document converges without conflicts

Test 2: Formatting Propagation

1. Select text in User 1 and toggle bold/highlight
2. User 2 sees the same formatting ✓ Pass: Formatting converges across clients

Performance Characteristics

See benchmark_results.ipynb and benchmarks/results/ for measured latency, bandwidth, throughput, and convergence time across workloads.

Citation & References

This implementation is based on:

• CRDT Theory: Shapiro et al., "Conflict-free Replicated Data Types"
• LWW Element Set: Common state-based CRDT design
• Vector Clocks: Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System"

License

MIT License - feel free to use and modify for your projects!

---