¿Te resulta más fácil leer con fondo crema, un tono de color, más contraste o un texto más grande? Elige tus colores y tu texto una sola vez, para todas las páginas.

Lección gratuita

Texto que se fusiona: CRDT de secuencia

Después de esta lección: Puedo fusionar dos réplicas de un texto cuyos caracteres llevan posiciones.

Lección de 70 min2 comandosLaboratorio de CRDT: sincronización local-first con contadores, conjuntos, relojes y texto

Dos personas, una frase

Dos estudiantes escriben un informe de grupo en un documento compartido. Una corrige una palabra al principio mientras el otro añade una frase al final, los dos sin conexión.

El texto es lo más difícil de fusionar, porque cada carácter tiene un sitio, y los sitios se mueven cuando alguien escribe.

Al terminar esta lección

Nota

Puedo fusionar dos réplicas de un texto cuyos caracteres llevan posiciones.

Palabras clave

PalabraQué significaEjemplo
CRDT de secuenciaun CRDT para una lista ordenada, como un texto
Índiceel sitio de un carácter contado desde el principio0, 1, 2
Id de carácterun nombre que no comparte ningún otro carácter(6, 'ben')
Lápidaun carácter borrado que se guarda como marca
Entrelazadodos palabras escritas a la vez que se mezclan letra a letra

Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.

Un índice significa cosas distintas

La forma fácil de enviar un cambio es "inserta a en el índice 0" o "borra el índice 2". Pero un índice cuenta desde el principio de un texto que ya ha cambiado en la otra réplica.

Si Ana inserta al principio, todos los caracteres siguientes se mueven un sitio. El "borra el índice 2" de Ben apunta ahora a otro carácter.

Pruébalo: dos cambios por índice

Código: python
def apply(text, edit):
    kind, index, char = edit
    if kind == "insert":
        return text[:index] + char + text[index:]
    return text[:index] + text[index + 1:]

start = "sol"
ana = ("insert", 0, "a")     # Ana escribe una a al principio: "asol"
ben = ("delete", 2, "")      # Ben borra la l del índice 2: "so"

# Cada réplica aplica primero su cambio y después el de la otra.
on_ana = apply(apply(start, ana), ben)
on_ben = apply(apply(start, ben), ana)
print("Ana ve:", on_ana)
print("Ben ve:", on_ben)
# ¿Qué letra quería borrar Ben? ¿Cuál borró la copia de Ana?

Idea 1: una posición entre vecinos

Da a cada carácter un número de posición y ordena por él. Para escribir entre las posiciones 0.4 y 0.5, elige 0.45. No se mueve nada más.

Los sistemas reales usan una lista de números enteros, como [4, 5], para que siempre quepa uno más. El nombre de la réplica deshace los empates. Es la idea de Logoot.

Idea 2: un id y un padre

RGA da a cada carácter un id, un contador y el nombre de la réplica, y recuerda tras qué carácter se escribió. El texto se lee recorriendo desde el principio, primero los hijos más nuevos.

Un borrado solo marca el carácter como lápida, porque otra réplica aún puede escribir detrás de él. El rga.py del laboratorio funciona así.

Fusiona dos cambios en una línea

Comando
docker exec jupyter python3 steps/text.py

Se muestra aquí y no se ejecuta. Pulsa Iniciar laboratorio para escribirlo en el terminal de tu propio laboratorio.

Ejemplo: lo que imprimió el laboratorio

MomentoAnaBen
CompartidoHelloHello
Sin conexiónHello worldOh, ello (H borrada)
Tras sincronizarOh, ello worldOh, ello world
Guardadouna lápida, la Huna lápida, la H

Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.

Cuando dos palabras se mezclan

Ana escribe "cat" y Ben escribe "dog" en el mismo sitio y a la vez. Con posiciones entre vecinos, los dos eligen los mismos números, y el nombre de la réplica ordena cada pareja.

Las letras se alternan. RGA encadena cada letra a la anterior, así que cada palabra queda entera.

Mira cómo se entrelazan dos palabras

Comando
docker exec jupyter python3 steps/interleave.py

Se muestra aquí y no se ejecuta. Pulsa Iniciar laboratorio para escribirlo en el terminal de tu propio laboratorio.

Un error frecuente

Advertencia

Mucha gente cree que si todas las réplicas acaban con el mismo texto, la fusión está bien. "cdaotg" es igual en todas las réplicas y nadie lo escribió. Converger es obligatorio, pero un buen CRDT de texto además mantiene junto lo que escribió cada persona.

Sobre este laboratorio y su código: Laboratorio de CRDT: sincronización local-first con contadores, conjuntos, relojes y texto

¿Enseñas a una clase? Asigna este módulo a tus alumnos con guía del profesor, tareas con corrección automática y un laboratorio para cada alumno.