Transformación operacional y resolución sin conflictos para aplicaciones de colaboración en tiempo real

Ahora mismo estoy en procesos de selección con varias empresas del Reino Unido, y eso me da la oportunidad de conocer los retos que tiene cada negocio. Uno de ellos es la colaboración en tiempo real dentro de la aplicación de una empresa.

Eso me ha despertado la curiosidad por cómo se implementan las tecnologías de colaboración en tiempo real.

Que varios usuarios editen el mismo documento es bastante habitual. Tan habitual que Google Docs, Microsoft Word, Canva, Figma, Miro, Notion, Linear y muchas más lo traen de serie. Es tan, tan habitual que lo raro es encontrar una aplicación sin ello.

Ahora solo quiero saber cómo funciona.

Técnicas

Al explorarlo, he encontrado dos técnicas bastante comunes que pueden ayudar.

Transformación operacional (OT)

Este algoritmo es el más usado en la colaboración en tiempo real. Procesa los cambios sobre el estado actual del documento y los aplica en el servidor de manera que el orden de las operaciones no afecte a la coherencia.

Tipos de datos replicados sin conflictos (CRDT)

Igual que OT, los CRDT garantizan que las copias de los datos acaben convergiendo, sea cual sea el orden de los cambios. Las acciones en un CRDT se diseñan para ser conmutativas, idempotentes y asociativas, lo que simplifica la fusión. Los CRDT son estupendos porque no dependen necesariamente de un servidor y pueden funcionar de igual a igual. Eso significa que los usuarios pueden seguir trabajando sin conexión y sincronizarse sin problemas al reconectar, sin miedo a que sus cambios provoquen incoherencias.

Consideraciones

Hay otras cuantas consideraciones que conviene tener en cuenta, pero no voy a entrar en mucho detalle.

Latencia de red y desconexiones

Gestionar bien la latencia de red y las desconexiones en el cliente es fundamental. Implementar estrategias para caducar cambios de estado antiguos puede ayudar a reducir las incoherencias en la interfaz y los conflictos.

Actualizaciones en tiempo real

En lugar de hacer polling, tecnologías como WebSockets o gRPC pueden gestionar con eficiencia las actualizaciones de estado en tiempo real desde el servidor.

UX de la resolución de conflictos

La interfaz debe ofrecer mecanismos intuitivos para que los usuarios entiendan y resuelvan los conflictos cuando aparezcan.

Cronología y antigüedad de un cambio de estado

Los CRDT no dependen del orden de los cambios, pero OT depende del estado anterior y del siguiente. La distancia cronológica entre cambios puede complicar la resolución de conflictos. Además, la antigüedad de un cambio de estado puede afectar a los cambios futuros si el cliente no los descarta como es debido pasado un TTL razonable. Dicho de otro modo: no envíes cambios de estado viejísimos de cuando se cortó la conexión, envía solo el último. (A menos que guardes la cronología y la uses después para resolver conflictos en el servidor.)

Implementaciones

Transformación operacional

En pocas palabras, OT consiste en garantizar que, hagas lo que hagas, el estado final sea coherente, sea cual sea el orden de las operaciones. Es crucial porque en el mundo real nunca sabes en qué orden llegarán al servidor los cambios de los usuarios. Puedes recoger las marcas de tiempo de los dispositivos, pero sincronizarlas entre muchos clientes es casi imposible (aunque, como decía antes, pueden ser utilísimas para resolver conflictos si guardas un historial de cambios).

Conceptos

Idempotencia: el superhéroe de los conceptos en la edición en tiempo real. Idempotencia significa que, no importa cuántas veces se ejecute una operación, el resultado es el mismo que si se hubiera ejecutado una sola vez. Piensa en un botón de publicar de Facebook que volviera a enviar tus últimos pensamientos una y otra vez: te quedarías sin amigos. En las aplicaciones colaborativas, la idempotencia garantiza que las actualizaciones repetidas no alteren el estado final más allá de la primera aplicación, algo crucial para mantener la cordura en las sesiones colaborativas.
Asociatividad: piensa en ella como la batidora. Significa que, agrupes como agrupes las operaciones, el resultado final será el mismo. Por ejemplo, (a * b) * c = a * (b * c). Resulta utilísima cuando tienes un montón de cambios que fusionar y no quieres perder tiempo desenredando qué depende de qué.
Conmutatividad: este concepto garantiza que el orden de las operaciones no importa, a * b = b * a. Así, tanto si se aplican antes los cambios del usuario A como los del usuario B, el resultado final es el mismo. Vale su peso en oro en entornos donde los cambios llegan de todas partes o incluso se hacen sin conexión.

Ejemplo de implementación básica

Este es un ejemplo de implementación muy básico que usa una sola cadena de texto como estado. Para mutar el estado, simplemente tomamos un índice e insertamos o borramos texto.

Por ejemplo:

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 datos replicados sin conflictos

Los CRDT son otra técnica para gestionar el estado en aplicaciones colaborativas en tiempo real. Adoptan un enfoque distinto: garantizan que cada cambio pueda converger por su cuenta hacia el mismo resultado final, sea cual sea el orden en que se apliquen. Eso los hace especialmente robustos en entornos con cortes de red importantes.

Los CRDT destacan cuando la latencia es bastante más que una molestia menor, como cuando trabajas en un tren con una conexión a internet intermitente. Cada acción o edición en un sistema CRDT está diseñada para fusionarse de forma independiente, sin consultar de inmediato a un servidor central. Eso significa que los usuarios pueden seguir trabajando sin conexión y sincronizarse sin problemas al reconectar, sin miedo a que sus cambios provoquen incoherencias.

Conceptos

Ejemplo de implementación 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;
}

Conclusión

Me ha gustado mucho explorar cómo funcionan estos conceptos. Aunque hoy estamos superconectados, sigue siendo crítico que las aplicaciones gestionen bien este tipo de complejidad para mejorar la experiencia de usuario.

Obviamente, en un caso real no usaría un único campo de texto para gestionar el estado, pero quería enseñarte cómo podrían funcionar en la práctica.

Además, probablemente intentaría evitar procesar los cambios de estado en la capa de aplicación. Aunque es posible, no sé qué impacto tendría en el cumplimiento ACID de la base de datos cuando varios clientes envían actualizaciones con frecuencia. Quizá algo que una cola podría gestionar.

Probé varias herramientas que me ayudaron a entender cómo funcionan. Espero que te sirvan.

Agradecimientos

Un gran agradecimiento a Tuhin Banerjee en Medium, cuyo post me ayudó a empezar con mi propia implementación.