Cosa sono i CRDT e perché servono

Immagina una applicazione collaborativa dove due utenti modificano il medesimo documento offline. Alice aggiunge "Ciao " a inizio riga, Bob aggiunge " Mondo" a fine riga. Quando si riconnettono, come integri le due modifiche senza perdere dati e senza conflitti espliciti?

Questo è il problema del conflict-free replication. Le soluzioni tradizionali (merge a tre vie, CRDTs con versioni vettoriali) sono complesse e richiedono un server centrale. I CRDT offrono un'alternativa elegante: ogni operazione è indipendente e commutativa, il che significa che l'ordine di applicazione non importa — il risultato sarà sempre lo stesso in tutte le repliche.

Un CRDT è una struttura dati che garantisce:

• Convergenza: tutte le repliche arrivano allo stesso stato dopo aver ricevuto le stesse operazioni
• Assenza di conflitti: nessuna operazione di merge manuale richiesta
• Commutatività: l'ordine di applicazione delle operazioni non influenza il risultato finale
• Tolleranza ai ritardi: funziona in reti di cattiva qualità, offline e con latenza arbitraria

Last-Write-Wins (LWW) CRDT

La strategia più semplice è Last-Write-Wins (LWW): ogni modifica è contrassegnata con un timestamp (o un identificativo univoco dell'utente se i timestamp non sono sincronizzati), e il valore più recente vince.

Consideriamo un esempio di Map LWW:

interface ValueWithTimestamp {
  value: unknown;
  timestamp: number;
  replicaId: string;
}

class LWWMap {
  private map: Map = new Map();

  set(key: string, value: unknown, timestamp: number, replicaId: string) {
    const existing = this.map.get(key);

    // Il nuovo valore vince se ha timestamp più alto
    // Se timestamp uguale, usiamo l'ID replica per tie-breaking deterministico
    if (!existing || timestamp > existing.timestamp ||
        (timestamp === existing.timestamp && replicaId > existing.replicaId)) {
      this.map.set(key, { value, timestamp, replicaId });
    }
  }

  get(key: string): unknown {
    return this.map.get(key)?.value;
  }

  // Merge riceve una replica remota e applica i cambiamenti
  merge(remote: Map) {
    for (const [key, remoteValue] of remote) {
      this.set(key, remoteValue.value, remoteValue.timestamp, remoteValue.replicaId);
    }
  }
}
    

Il vantaggio di LWW è la semplicità; lo svantaggio è che piccole perdite di dati sono possibili. Se due utenti modificano lo stesso campo "quasi contemporaneamente", la modifica del primo è silenziosamente sovrascritta.

Operazioni commutative: il fondamento dei CRDT

La chiave dei CRDT è costruire operazioni commutative (l'ordine non importa) e idempotenti (applicare due volte non causa problemi). Un semplice esempio è un Counter CRDT:

class CounterCRDT {
  // Ogni replica mantiene il proprio contatore
  // Il valore globale è la somma di tutti i contatori locali
  private increments: Map = new Map();

  increment(replicaId: string) {
    const current = this.increments.get(replicaId) || 0;
    this.increments.set(replicaId, current + 1);
  }

  decrement(replicaId: string) {
    const current = this.increments.get(replicaId) || 0;
    this.increments.set(replicaId, current - 1);
  }

  get value(): number {
    let sum = 0;
    for (const count of this.increments.values()) {
      sum += count;
    }
    return sum;
  }

  // Il merge è semplicemente: per ogni replica, prendi il valore massimo
  merge(remote: Map) {
    for (const [replicaId, remoteCount] of remote) {
      const local = this.increments.get(replicaId) || 0;
      this.increments.set(replicaId, Math.max(local, remoteCount));
    }
  }
}
    

Notare che l'ordine di applicazione delle operazioni non importa. Se la replica A fa +1, +2, -1 e la replica B riceve solo l'ultimo stato (+2, -1), il risultato è identico: +1 complessivamente.

Tipi di CRDT comuni

Oltre al Counter e al Map, esistono CRDT per Set, List, Text e strutture più complesse:

1. OR-Set (Observed-Remove Set)

Un Set CRDT che permette add/remove senza conflitti. Ogni elemento ha un UUID univoco per ogni add:

class ORSet {
  private elements: Map> = new Map(); // elemento -> set di UUIDs

  add(element: string): string {
    const id = crypto.randomUUID();
    if (!this.elements.has(element)) {
      this.elements.set(element, new Set());
    }
    this.elements.get(element)!.add(id);
    return id; // Restituisci l'ID per poter fare remove in seguito
  }

  remove(element: string, id: string) {
    this.elements.get(element)?.delete(id);
  }

  contains(element: string): boolean {
    return this.elements.has(element) && this.elements.get(element)!.size > 0;
  }

  toArray(): string[] {
    return Array.from(this.elements.entries())
      .filter(([_, ids]) => ids.size > 0)
      .map(([elem]) => elem);
  }
}
    

2. RGA (Replicated Growable Array) per Text CRDT

Per editor collaborativi, è cruciale preservare l'ordine dei caratteri. RGA (e il più moderno YATA) assegna a ogni carattere un identificativo univoco basato su (replicaId, clock):

interface CharWithId {
  id: string; // "replicaId:clock"
  char: string;
  tombstone: boolean; // Segnalato come eliminato, ma non rimosso
}

class RGATextCRDT {
  private chars: CharWithId[] = [];
  private clock = 0;
  private replicaId: string;

  constructor(replicaId: string) {
    this.replicaId = replicaId;
  }

  insert(position: number, char: string): void {
    this.clock++;
    const id = `${this.replicaId}:${this.clock}`;
    this.chars.splice(position, 0, { id, char, tombstone: false });
  }

  delete(position: number): void {
    this.chars[position].tombstone = true; // Mark-and-sweep, non rimuovere subito
  }

  getText(): string {
    return this.chars
      .filter(c => !c.tombstone)
      .map(c => c.char)
      .join('');
  }
}
    

3. Map con nested CRDT

Per strutture complesse, puoi comporre CRDT: una Map dove ogni valore è un Counter, Set o List CRDT:

class NestedCRDT {
  private map: Map = new Map();

  getOrCreateCounter(key: string): CounterCRDT {
    if (!this.map.has(key)) {
      this.map.set(key, new CounterCRDT());
    }
    return this.map.get(key) as CounterCRDT;
  }

  // Merge ricorsivo: per ogni chiave, fai merge del CRDT nested
  merge(remote: Map) {
    for (const [key, remoteValue] of remote) {
      const local = this.map.get(key);
      if (local && typeof local.merge === 'function') {
        local.merge(remoteValue);
      } else {
        this.map.set(key, remoteValue);
      }
    }
  }
}
    

Algoritmi CRDT riconosciuti: Yjs, Automerge, OT

Tre approcci dominano nel panorama del conflict-free replication:

Yjs

Yjs è una libreria JavaScript per CRDT che usa una versione ottimizzata dell'algoritmo YATA (Yet Another Text Algorithm). È estremamente popolare per editor collaborativi (Figma-like, Google Docs-like).

import * as Y from 'yjs';
import { WebsocketProvider } from 'y-websocket';

// Creiamo un documento Yjs
const ydoc = new Y.Doc();
const ytext = ydoc.getText('shared-text');
const ymap = ydoc.getMap('shared-map');

// Osserviamo i cambiamenti locali
ytext.observe(event => {
  console.log('Text changed:', event.changes);
});

// Sync con server via WebSocket
const provider = new WebsocketProvider(
  'ws://localhost:1234',
  'my-room',
  ydoc
);

// Modifichiamo il testo
ytext.insert(0, 'Hello ');
ymap.set('name', 'Alice');

// Yjs gestisce automaticamente la sincronizzazione
// e la convergenza delle repliche
    

Automerge

Automerge è una libreria JSON-like CRDT con focus su immutabilità e history. Perfetta per applicazioni dove hai bisogno di track dei cambiamenti e di branching (come Git per dati).

import * as Automerge from '@automerge/automerge';

// Crea un documento
let doc1 = Automerge.from({ tasks: [] });

// Fai una modifica
doc1 = Automerge.change(doc1, d => {
  d.tasks.push({ text: 'Learn CRDT', done: false });
});

// Clona il documento per una seconda replica
let doc2 = Automerge.clone(doc1);

// Modifiche divergenti
doc1 = Automerge.change(doc1, d => {
  d.tasks[0].done = true;
});

doc2 = Automerge.change(doc2, d => {
  d.tasks.push({ text: 'Deploy', done: false });
});

// Merge: Automerge lo fa automaticamente senza conflitti
const merged = Automerge.merge(doc1, doc2);
console.log(merged);
// { tasks: [{ text: 'Learn CRDT', done: true }, { text: 'Deploy', done: false }] }
    

Operational Transform (OT)

Mentre i CRDT sono commutativi, Operational Transform usa un approccio diverso: registra le operazioni e le trasforma in modo che mantengano intento anche quando conflittuali. È usato in Google Docs. OT richiede un server centrale per linearizzare gli ordini, mentre CRDT no.

Performance, memoria e trade-off

I CRDT hanno costi:

• Overhead di memoria: ogni elemento deve avere un identificativo unico. Text CRDT con milioni di caratteri possono essere ingombranti.
• Complessità di implementazione: alcuni CRDT (come YATA per Text) sono intricati e richiedono attenzione ai dettagli.
• Garbage collection: gli elementi eliminati (tombstone) devono essere puliti periodicamente, altrimenti la memoria cresce indefinitamente.
• Serializzazione: la trasmissione di un intero documento CRDT può essere più voluminosa di un delta JSON.

Librerie come Yjs mitigano questi problemi con:

• Encoding binario efficiente
• State vector + deletion vector per la sincronizzazione incrementale
• Garbage collection automatico

Applicazioni pratiche e casi d'uso

I CRDT abilitano:

• Editor collaborativi offline-first: Google Docs-like senza server obbligatorio (Notion, Figma usano architetture simili)
• Note-taking decentralizzate: app come Obsidian Sync usano CRDT per la sincronizzazione tra dispositivi
• Whiteboard e diagramming: Excalidraw, Tldraw supportano CRDT per real-time collaboration
• Database locali replicati: RxDB, Replicache usano CRDT-like per i loro sync engine
• Sistemi P2P e mesh: IPFS, Dat Protocol, e app su Bluetooth mesh usano CRDT per consensus distribuito
• Version control decentralizzato: sistemi come Pijul e Jujutsu usano CRDT-like merging per evitare conflitti Git

Testing e Prototyping di CRDT

Testare CRDT significa verificare che convergenza e commutatività funzionano. Qui entra in gioco Ollama per il prototyping e la generazione di test case casuali:

// Pseudo-codice: usa un modello AI locale (via Ollama)
// per generare sequenze randomiche di operazioni e verificare convergenza

import fetch from 'node-fetch';

async function generateTestScenario(): Promise {
  const response = await fetch('http://localhost:11434/api/generate', {
    method: 'POST',
    body: JSON.stringify({
      model: 'llama3.1:8b',
      prompt: 'Generate 5 random CRDT operations in JSON format for testing: add(x), remove(x), increment(x). Format: ["op1", "op2", ...]',
      stream: false
    })
  });
  const data = await response.json();
  return JSON.parse(data.response);
}

async function testCRDTConvergence() {
  const operations = await generateTestScenario();

  const replicaA = new CounterCRDT();
  const replicaB = new CounterCRDT();

  // Apply operations in different orders
  for (const op of operations) {
    if (op.includes('increment')) replicaA.increment('replicaA');
    if (op.includes('decrement')) replicaA.decrement('replicaA');
  }

  for (const op of operations.reverse()) {
    if (op.includes('increment')) replicaB.increment('replicaB');
    if (op.includes('decrement')) replicaB.decrement('replicaB');
  }

  console.assert(replicaA.value === replicaB.value, 'Convergence failed!');
}
    

Ollama fornisce un modello AI locale (default llama3.1:8b) per generare fixture di test, scenari e casi edge. Non è il provider AI del sito, ma uno strumento utile per sviluppo e testing locale.

Come iniziare: Yjs step-by-step

Se vuoi aggiungere CRDT a un editor Angular o React:

npm install yjs y-websocket y-protocols lib0

# Per editor Monaco o CodeMirror:
npm install y-monaco  # oppure y-codemirror
    

// In un component Angular:
import { Component, OnInit, OnDestroy } from '@angular/core';
import * as Y from 'yjs';
import { WebsocketProvider } from 'y-websocket';

@Component({
  selector: 'app-collab-editor',
  template: '<div #editor></div>'
})
export class CollabEditorComponent implements OnInit, OnDestroy {
  private ydoc = new Y.Doc();
  private provider: WebsocketProvider;
  private ytext: Y.Text;

  ngOnInit() {
    this.ytext = this.ydoc.getText('shared-text');
    this.provider = new WebsocketProvider(
      'ws://your-sync-server.com',
      'editor-room',
      this.ydoc
    );

    // Osserva i cambiamenti
    this.ytext.observe(event => {
      this.updateLocalView(event);
    });
  }

  onUserEdit(text: string) {
    this.ytext.delete(0, this.ytext.length);
    this.ytext.insert(0, text);
  }

  ngOnDestroy() {
    this.provider.disconnect();
    this.ydoc.destroy();
  }

  private updateLocalView(event: any) {
    console.log('Remote changes:', event.changes);
  }
}
    

Domande frequenti (FAQ)