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
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Ocurrió antes | un cambio ya se conocía cuando se hizo el otro | |
| Reloj vectorial | un contador por réplica, enviado con cada cambio | {"a": 1, "b": 2} |
| CRDT basado en operaciones | las réplicas envían operaciones en vez de estados enteros | |
| Entrega causal | un cambio se aplica solo después de los cambios que vio | |
| Delta | solo 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
docker exec jupyter python3 steps/clocks.pySe muestra aquí y no se ejecuta. Pulsa Iniciar laboratorio para escribirlo en el terminal de tu propio laboratorio.
Ejemplo: lo que imprimió el laboratorio
| Relojes | Comparación | Por qué |
|---|---|---|
| a {a: 1} y b {b: 1} | concurrent | cada uno es mayor en un sitio |
| a {a: 1} y b {a: 1, b: 2} | a before b | b oyó a a y luego escribió |
| c {a: 1, b: 2, c: 1} y a | c after a | c oyó a b, que había oído a a |
| a y una copia de a | equal | todos 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
# 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
docker exec jupyter python3 steps/delta.pySe muestra aquí y no se ejecuta. Pulsa Iniciar laboratorio para escribirlo en el terminal de tu propio laboratorio.