La modifica collaborativa è più difficile di quanto pensi

Google Docs gestisce la modifica collaborativa in tempo reale per milioni di utenti. Sembra senza sforzo: digiti, il cursore si muove e le modifiche del collega compaiono all'istante. Questa semplicità è ingannevole. Sotto il cofano, la modifica collaborativa è uno dei problemi più difficili nei sistemi distribuiti, e i due approcci principali per risolverlo (Operational Transformation e CRDT) hanno compromessi che non sono ovvi finché non provi a costruire qualcosa con essi.

La promessa dei CRDT (Conflict-free Replicated Data Types) è seducente: strutture dati che si fondono automaticamente senza conflitti, nessun server centrale necessario, consistenza eventuale garantita dalla matematica. Ma la realtà, come hanno scoperto diversi team dopo aver scelto i CRDT per i loro editor collaborativi, è più caotica. La teoria è bellissima. L'ingegneria è brutale.

Il problema: modifiche concorrenti

La sfida di fondo: due utenti modificano lo stesso documento contemporaneamente, con un ritardo di rete tra loro. L'utente A inserisce 'Hello' in posizione 5. L'utente B, che non ha ancora visto la modifica di A, elimina il carattere in posizione 5. Come dovrebbe apparire il documento finale?

È ambiguo. La cancellazione di B dovrebbe applicarsi al carattere che era in posizione 5 prima dell'inserimento di A, o dopo? Se prima, la cancellazione rimuove il carattere originale e appare 'Hello'. Se dopo, la cancellazione rimuove la 'H' di 'Hello'. Entrambe le interpretazioni sono ragionevoli. Il sistema deve sceglierne una e garantire che tutti i client convergano sullo stesso risultato: la divergenza significa che due utenti vedono documenti diversi, ed è l'unico errore imperdonabile.

The convergence problem:
Initial document: "The quick brown fox"
^ position 10
User A (at time T):  Insert "very " at position 10
User B (at time T):  Delete character at position 10
A sees locally: "The quick very brown fox"
B sees locally: "The quick rown fox"  (deleted 'b')
Now A receives B's operation: delete at position 10
But A already inserted 5 chars at position 10...
Should B's delete now apply at position 10? (deletes 'v' from 'very')
Or at position 15? (deletes 'b' from 'brown' — the original target)
Both A and B must arrive at the same document.
This is the problem OT and CRDTs solve differently.

Operational Transformation (OT)

L'OT, l'approccio più vecchio (1989), risolve il problema trasformando le operazioni l'una rispetto all'altra. Quando A riceve la 'cancellazione in posizione 10' di B, il sistema di A controlla quali operazioni ha già applicato che B non ha ancora visto. Trasforma l'operazione di B per tenerne conto: dato che A ha inserito 5 caratteri in posizione 10, la cancellazione di B ora dovrebbe applicarsi in posizione 15 (il carattere originale è slittato a destra).

Funziona, e Google Docs lo usa. Il problema sono le funzioni di trasformazione. Per un editor di testo con operazioni di inserimento e cancellazione, bisogna definire come ogni coppia di operazioni si trasforma rispetto all'altra. Con due tipi di operazione sono quattro casi di trasformazione. Aggiungi formattazione, tabelle, immagini, liste e commenti, e il numero di casi esplode combinatoriamente. Ogni caso deve essere corretto, e bug sottili causano divergenze del documento quasi impossibili da riprodurre e debuggare.

L'OT richiede tradizionalmente anche un server centrale per stabilire un ordinamento totale delle operazioni. Senza server, le operazioni concorrenti possono essere trasformate in ordini diversi da client diversi, producendo risultati differenti. Google può permettersi un server centrale per Docs. Un'applicazione peer-to-peer non può usare l'OT facilmente.

CRDT: la promessa teorica

I CRDT seguono un approccio fondamentalmente diverso. Invece di trasformare le operazioni, usano strutture dati in cui tutti i possibili ordini di fusione producono lo stesso risultato. È una garanzia matematica: se la struttura dati è un CRDT valido, la convergenza è automatica. Niente funzioni di trasformazione, niente server centrale, niente dipendenza dall'ordinamento.

Per la modifica di testo, le varianti CRDT principali sono RGA (Replicated Growable Array) e altri CRDT di sequenza simili. Invece di tenere traccia delle posizioni (che cambiano man mano che avvengono le modifiche), assegnano a ogni carattere un identificatore unico e ordinato globalmente. Gli inserimenti creano nuovi ID tra quelli esistenti. Le cancellazioni contrassegnano un ID come tombstone (non viene rimosso, ne parliamo più avanti).

CRDT sequence representation:
Document: "cat"
Internal representation (simplified):
ID: (A,1) → 'c'   (user A, logical clock 1)
ID: (A,2) → 'a'   (user A, logical clock 2)
ID: (A,3) → 't'   (user A, logical clock 3)
User B inserts 'h' between 'c' and 'a':
ID: (B,1) → 'h'   position: between (A,1) and (A,2)
Document: "chat"
User A (concurrently) inserts 'r' between 'c' and 'a':
ID: (A,4) → 'r'   position: between (A,1) and (A,2)
Both IDs go between the same characters.
The CRDT uses a deterministic tie-breaking rule
(e.g., higher user ID wins) to order them.
Final document: "chart" or "chrat"
(deterministic — all clients get the same result)

CRDT: la realtà pratica

La promessa dei CRDT (senza conflitti, decentralizzata, convergenza garantita matematicamente) è reale. Ma le sfide ingegneristiche sono significative.

I tombstone si accumulano. Quando cancelli un carattere in un CRDT, non può essere rimosso dalla struttura dati: altre repliche potrebbero non averlo ancora visto e hanno bisogno dell'ID per posizionare correttamente le proprie modifiche. Quindi i caratteri cancellati vengono marcati come tombstone: invisibili ma ancora presenti. Un documento molto modificato accumula migliaia di tombstone. Un documento di 1000 caratteri può avere 50.000 tombstone dalla cronologia delle modifiche. Questo gonfia la memoria e rallenta le operazioni.

L'overhead dei metadati è enorme. Ogni carattere richiede un ID unico (identificatore utente più timestamp logico), puntatori agli ID vicini e flag di tombstone. I metadati per carattere possono arrivare a 50-100 byte. Per un documento di 100KB, la rappresentazione CRDT può occupare 5-10MB. Questo pesa sulla sincronizzazione: inviare lo stato CRDT completo sulla rete è costoso.

Le prestazioni peggiorano con la cronologia. Le operazioni su un CRDT di sequenza non sono O(1): inserire un carattere richiede di trovare la posizione corretta nella sequenza ordinata per ID, che dipende dal numero totale di ID (inclusi i tombstone). Per documenti con cronologie di modifica lunghe, diventa misurabilmente lento.

Preservare l'intenzione è difficile. I CRDT garantiscono la convergenza: tutte le repliche raggiungono lo stesso stato. Ma raggiungono lo stato giusto? Quando due utenti modificano contemporaneamente la stessa parola, il CRDT intercala i caratteri in modo deterministico. Il risultato converge ma potrebbe non avere senso. L'OT può essere progettato per mantenere intatta la modifica di un utente e applicare quella dell'altro attorno ad essa. I CRDT fondono in modo meccanico.

Yjs e la via di mezzo pratica

Yjs è la libreria CRDT più popolare per JavaScript e alimenta le funzionalità collaborative di molte applicazioni web. È ben progettata e affronta molti problemi teorici dei CRDT con ottimizzazioni pratiche: la codifica binaria compatta riduce l'overhead dei metadati, e la garbage collection dei tombstone funziona quando tutti i client sono online.

Ma Yjs non è magia. I team che lo adottano scoprono che una libreria CRDT risolve il problema della convergenza, ma non il problema della collaborazione. Ti servono ancora: un server di segnalazione per la scoperta dei peer, un livello di persistenza per le modifiche offline, la risoluzione dei conflitti per operazioni di alto livello (cosa succede se due utenti ristrutturano la stessa sezione?), il tracciamento della presenza (cursori, selezioni), undo/redo che rispetti le modifiche degli altri utenti e la gestione dei permessi.

Alcuni team, dopo aver costruito un editor collaborativo su Yjs, hanno concluso che l'approccio CRDT aggiunge complessità di cui non hanno bisogno. Se la tua applicazione ha un server centrale (e la maggior parte ce l'ha), l'OT o approcci ancora più semplici (last-write-wins con rilevamento dei conflitti) possono essere più pratici. I CRDT brillano in scenari davvero peer-to-peer: applicazioni offline-first, software local-first e sistemi in cui non si può presumere un'autorità centrale.

Cosa dovrebbero fare la maggior parte delle applicazioni

Se stai aggiungendo la modifica collaborativa alla tua applicazione, ecco il framework decisionale pragmatico.

• Se hai un server centrale e i documenti sono piccoli: usa l'OT. L'approccio di Google funziona. Librerie come ShareDB implementano l'OT per Node.js. Il server centrale semplifica tutto: ordinamento, persistenza, risoluzione dei conflitti, permessi.
• Se ti servono il supporto offline o il peer-to-peer: usa i CRDT (Yjs o Automerge). I CRDT sono l'unico approccio che gestisce correttamente la modifica offline reale e la sincronizzazione peer-to-peer. Accetta l'overhead dei metadati e l'accumulo di tombstone come costo della decentralizzazione.
• Se i tuoi collaboratori raramente modificano la stessa sezione contemporaneamente: potresti non aver bisogno di nessuno dei due. Un semplice lock (un solo editor per sezione) o il last-write-wins con una buona UI per i conflitti copre molti casi d'uso reali senza la complessità di OT o CRDT.
• Se stai costruendo un concorrente di Google Docs: ti serve un team di ingegneri di sistemi distribuiti e anni di sviluppo. Non è un progetto da weekend. La semplicità superficiale della modifica collaborativa nasconde una complessità straordinaria.

La valutazione onesta

La modifica collaborativa è uno di quei problemi in cui la difficoltà non è ovvia. Il percorso felice, con due utenti che fanno modifiche non sovrapposte, funziona con quasi qualsiasi approccio. I casi difficili (modifiche concorrenti sulla stessa regione, modifica offline con sincronizzazione successiva, strutture di documento complesse come tabelle, liste annidate e oggetti incorporati) richiedono una comprensione profonda dei compromessi tra OT e CRDT.

Nessuno dei due approcci è strettamente migliore. L'OT è più semplice con un server, più difficile senza. I CRDT funzionano senza server ma portano overhead di metadati e accumulo di tombstone. Entrambi richiedono un'ingegneria attenta che va oltre l'algoritmo centrale, e quell'ingegneria (presenza, persistenza, permessi, undo) è spesso più difficile del problema della convergenza stesso.

Il settore sta lentamente convergendo verso un ibrido pragmatico: CRDT per il modello dei dati (garanzie di fusione automatica), con un server per il coordinamento (presenza, permessi, garbage collection). Così ottieni il meglio di entrambi i mondi: convergenza matematica più infrastruttura pratica. Ma ottieni anche la complessità di entrambi i mondi, ed è per questo che la modifica collaborativa resta un problema difficile dopo 35 anni di ricerca.