Transformação operacional e resolução sem conflitos em aplicações de colaboração em tempo real
Nesta página
Ando a fazer entrevistas com várias empresas no Reino Unido e isso dá-me a oportunidade de perceber os desafios de cada negócio. Um deles é a colaboração em tempo real dentro da aplicação de uma empresa.
Isto despertou-me o interesse em saber como se implementam as tecnologias colaborativas em tempo real.
Várias pessoas a editar o mesmo documento é algo bastante comum. Tão comum que aplicações como o Google Docs, o Microsoft Word, o Canva, o Figma, o Miro, o Notion, o Linear e muitas outras já o suportam de origem. É tão, mas tão comum, que até estranhamos quando uma aplicação não o tem.
Agora só quero saber como funciona.
Técnicas
Ao explorar o assunto, encontrei duas técnicas bastante comuns que ajudam.
Transformação operacional (OT)
Este algoritmo é o mais usado em colaboração em tempo real. Processa as alterações ao estado atual do documento e aplica-as no servidor de maneira a que a ordem das operações não afete a consistência.
Tipos de dados replicados sem conflitos (CRDTs)
Tal como a OT, os CRDTs garantem que as cópias dos dados acabam por convergir, seja qual for a ordem das alterações. As ações nos CRDTs são desenhadas para serem comutativas, idempotentes e associativas, o que simplifica a fusão. Os CRDTs são ótimos porque não dependem necessariamente de um servidor e funcionam ponto a ponto. Isto significa que os utilizadores podem continuar a trabalhar offline e sincronizar tudo quando voltarem a ligar-se, sem medo de que as alterações causem inconsistências.
Considerações
Há outras tantas considerações a ter em conta, mas não vou aprofundá-las aqui.
Latência da rede e desligações
Tratar bem a latência da rede e as desligações no cliente é fundamental. Implementar estratégias para expirar alterações de estado mais antigas pode ajudar a reduzir inconsistências na interface e conflitos.
Atualizações em tempo real
Em vez de polling, usar tecnologias como WebSockets ou gRPC gere de forma eficiente as atualizações de estado em tempo real vindas do servidor.
UX da resolução de conflitos
A interface deve oferecer mecanismos intuitivos para os utilizadores perceberem e resolverem conflitos quando surgem.
Cronologia e idade de uma alteração de estado
Os CRDTs não dependem da ordem das alterações, mas a OT depende do estado anterior e do seguinte. A distância cronológica entre alterações pode complicar a resolução de conflitos. Além disso, a idade de uma alteração de estado pode afetar alterações futuras, se o cliente não a descartar como deve ser passado um TTL razoável. Por outras palavras, não envies alterações de estado antiquíssimas, de quando a ligação à rede se perdeu. Envia só a mais recente. (A não ser que guardes a cronologia e a uses mais tarde na resolução de conflitos no servidor.)
Implementações
Transformação operacional
Resumindo, a OT serve para garantir que, façam o que fizerem, o estado final é consistente, seja qual for a ordem das operações. Isto é crucial porque, no mundo real, nunca sabes por que ordem as alterações dos utilizadores chegam ao servidor. Podes recolher os timestamps dos dispositivos, mas sincronizá-los entre muitos clientes é quase impossível (mas, como disse acima, pode ser muito útil na resolução de conflitos se guardares um histórico das alterações).
Conceitos
- Idempotência: é o super-herói dos conceitos na edição em tempo real. Idempotência significa que, por muitas vezes que uma operação seja executada, o resultado é o mesmo que se tivesse sido executada uma só vez. Imagina que carregar no botão de publicar do Facebook voltava a submeter os teus últimos pensamentos sem parar: ficavas sem amigos! Nas aplicações colaborativas, a idempotência garante que as atualizações repetidas não afetam o estado final para lá da primeira aplicação. É essencial para manter a sanidade mental nas sessões colaborativas.
- Associatividade: pensa nela como a batedeira. Quer dizer que, seja qual for a maneira como agrupas as operações, o resultado final é o mesmo. Veja-se o exemplo de
(a * b) * c = a * (b * c). É muito útil quando tens um monte de alterações para fundir e não queres perder tempo a desembaraçar o que depende de quê. - Comutatividade: este conceito garante que a ordem das operações não importa:
a * b = b * a. Assim, quer as alterações do utilizador A sejam aplicadas antes das do utilizador B, quer depois, o resultado final é o mesmo. Vale ouro em ambientes onde as alterações chegam de todos os lados ou são feitas offline.
Exemplo de implementação básica
Este é um exemplo de implementação muito básico, com uma única string como estado. Ao mudar o estado, limitamo-nos a receber um índice e a inserir ou apagar texto.
Por exemplo:
interface Operation {
id: string;
index: number;
length: number;
text: string;
type: 'insert' | 'delete';
timestamp: number;
}
function applyOperation(currentState: string, operation: Operation): string {
switch (operation.type) {
case 'insert':
return (
currentState.slice(0, operation.index) +
operation.text +
currentState.slice(operation.index)
);
case 'delete':
return (
currentState.slice(0, operation.index) +
currentState.slice(operation.index + operation.length)
);
default:
return currentState;
}
}
function transformOperation(
baseOperation: Operation,
newOperation: Operation
): Operation {
if (newOperation.index > baseOperation.index) {
switch (baseOperation.type) {
case 'insert':
newOperation.index += baseOperation.text.length;
break;
case 'delete':
newOperation.index -= baseOperation.length;
break;
}
}
return newOperation;
}
function compareAndApplyOT(
operations: Operation[],
currentState: string
): string {
let appliedOperations = new Map<string, Operation>();
operations.sort((a, b) => a.timestamp - b.timestamp);
for (const operation of operations) {
if (!appliedOperations.has(operation.id)) {
let transformedOperation = operation;
appliedOperations.forEach((appliedOp) => {
transformedOperation = transformOperation(
appliedOp,
transformedOperation
);
});
currentState = applyOperation(currentState, transformedOperation);
appliedOperations.set(operation.id, transformedOperation);
}
}
return currentState;
}Tipos de dados replicados sem conflitos
Os CRDTs são outra técnica para gerir o estado em aplicações colaborativas em tempo real. Seguem uma abordagem diferente: garantem que cada alteração converge, de forma independente, para o mesmo resultado final, seja qual for a ordem em que são aplicadas. Isto torna os CRDTs particularmente robustos em ambientes com falhas de rede significativas.
Os CRDTs destacam-se quando a latência é bem mais do que um pequeno incómodo. Pensa em trabalhar num comboio com internet intermitente. Cada ação ou edição num sistema CRDT é desenhada para se fundir de forma independente, sem precisar de consultar de imediato um servidor central. Isto significa que os utilizadores podem continuar a trabalhar offline e sincronizar tudo quando voltarem a ligar-se, sem medo de que as alterações causem inconsistências.
Conceitos
Exemplo de implementação básica
interface CRDTOperation {
id: string;
index: number;
text: string;
type: 'insert' | 'delete';
}
function applyOperation(currentState: string, operation: Operation): string {
switch (operation.type) {
case 'insert':
return (
currentState.slice(0, operation.index) +
operation.text +
currentState.slice(operation.index)
);
case 'delete':
return (
currentState.slice(0, operation.index) +
currentState.slice(operation.index + operation.length)
);
default:
return currentState;
}
}
function compareAndApplyCRDT(
operations: CRDTOperation[],
currentState: string
): string {
let operationMap = new Map<string, CRDTOperation>();
operations.forEach((op) => operationMap.set(op.id, op)); // Ensures idempotency by overwriting duplicates
let sortedOperations = Array.from(operationMap.values());
// Sort by ID for consistency, but order does not change the result
sortedOperations.sort((a, b) => a.id.localeCompare(b.id));
for (const operation of sortedOperations) {
currentState = applyOperation(currentState, operation); // Re-using the applyOperation function from OT
}
return currentState;
}Conclusão
Gostei mesmo de explorar como estes conceitos funcionam. Apesar de hoje estarmos todos tão ligados, continua a ser crítico que as aplicações lidem bem com este tipo de complexidade, para melhorar a experiência do utilizador.
Claro que, num cenário real, não usaria um único campo de texto para gerir o estado, mas queria mostrar-te como poderiam funcionar na prática.
Além disso, provavelmente tentaria evitar processar as alterações de estado na camada da aplicação. Apesar de ser possível, não sei que impacto teria na conformidade ACID da base de dados quando há vários clientes a submeter atualizações com frequência. Talvez seja algo que uma fila consiga tratar.
Experimentei algumas ferramentas que me ajudaram a perceber como funcionam. Espero que também te sejam úteis.
Agradecimentos
Um grande obrigado ao Tuhin Banerjee, no Medium, cujo post me ajudou a começar a minha própria implementação.