¿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

Relojes vectoriales, operaciones y deltas

Después de esta lección: Puedo comparar dos relojes vectoriales y decir qué cambio ocurrió primero.

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

Una respuesta que llega antes que la pregunta

En un chat de grupo, a veces aparece una respuesta antes que el mensaje al que responde. La red los entregó en mal orden.

Las réplicas tienen el mismo problema. Para fusionar bien, una réplica necesita saber qué cambio fue primero, y qué dos cambios no ordenó nadie.

Al terminar esta lección

Nota

Puedo comparar dos relojes vectoriales y decir qué cambio ocurrió primero.

Palabras clave

PalabraQué significaEjemplo
Ocurrió antesun cambio ya se conocía cuando se hizo el otro
Reloj vectorialun contador por réplica, enviado con cada cambio{"a": 1, "b": 2}
CRDT basado en operacioneslas réplicas envían operaciones en vez de estados enteros
Entrega causalun cambio se aplica solo después de los cambios que vio
Deltasolo la parte de un estado que cambió

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

Un reloj vectorial cuenta cada réplica

Cada réplica guarda un contador para cada réplica. Antes de un cambio, suma uno a su propio contador. Cuando oye a otra réplica, toma el mayor de cada contador.

Compara dos relojes sitio a sitio. Si cada sitio de a es como mucho el de b, y alguno es menor, a ocurrió antes que b. Si cada uno es mayor en algún sitio, son concurrentes.

Compara relojes vectoriales

Comando
docker exec jupyter python3 steps/clocks.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

RelojesComparaciónPor qué
a {a: 1} y b {b: 1}concurrentcada uno es mayor en un sitio
a {a: 1} y b {a: 1, b: 2}a before bb oyó a a y luego escribió
c {a: 1, b: 2, c: 1} y ac after ac oyó a b, que había oído a a
a y una copia de aequaltodos los sitios iguales

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

Enviar operaciones en lugar de estados

Un CRDT basado en estado envía su estado entero, que puede ser grande. Uno basado en operaciones envía cada operación, como "añade leche", que es pequeña.

Pero cada operación tiene que llegar exactamente una vez, y un cambio tiene que llegar después de los cambios que vio. Si no, una baja puede llegar antes que el alta que quitaba.

Pruébalo: dos operaciones, cambiadas de orden

Código: python
# Basado en operaciones: las réplicas envían operaciones, no estados enteros.
# Ana añade leche y luego la quita. Cai recibe las dos operaciones.
def apply(items, op):
    kind, item = op
    if kind == "add":
        return items | {item}
    return items - {item}

first = ("add", "leche")
second = ("remove", "leche")

in_order = apply(apply(set(), first), second)
swapped = apply(apply(set(), second), first)
print("llegan en orden:  ", sorted(in_order))
print("llegan cambiadas: ", sorted(swapped))
# La red cambió de orden dos mensajes. ¿Qué tendría que haber hecho
# Cai con la baja cuando llegó primero?

Un error frecuente

Advertencia

Mucha gente cree que basta una marca de hora para ordenar los cambios. Los relojes de dos dispositivos no coinciden, y una hora no puede decir que dos cambios fueron concurrentes. Un reloj vectorial sí, porque registra lo que había oído cada réplica.

Deltas: lo mejor de los dos

Un CRDT de estado por deltas envía solo la parte de su estado que cambió desde que la otra réplica lo oyó por última vez. Se fusiona con la misma unión que un estado entero.

Así un delta perdido o repetido no hace daño, como un estado, y el mensaje sigue siendo pequeño, como una operación. Un reloj vectorial dice lo que ya tiene la otra réplica.

Envía un delta en vez del estado entero

Comando
docker exec jupyter python3 steps/delta.py

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

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.