Contar "me gusta" en tres móviles
Una publicación recibe "me gusta" desde tres móviles, y cada uno pasa un rato sin conexión. Al sincronizar, el total debe contar cada "me gusta" una vez. No debe faltar ninguno ni contarse ninguno dos veces.
Un número compartido no puede hacerlo solo. Un contador CRDT sí.
Al terminar esta lección
Nota
Puedo fusionar dos réplicas de un contador para que todas tengan el mismo total.
Palabras clave
| Palabra | Qué significa |
|---|---|
| CRDT | un tipo de datos cuyas réplicas siempre se fusionan en el mismo estado |
| Basado en estado | las réplicas envían su estado entero y lo fusionan |
| Unión | una fusión que no depende del orden y se puede repetir |
| G-Counter | un contador que solo sube, con una entrada por réplica |
| PN-Counter | dos G-Counter, uno para subidas y otro para bajadas |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Una fusión que no puede salir mal
Un CRDT basado en estado envía su estado entero, y la otra réplica lo fusiona. La fusión tiene que ser una unión, con tres propiedades:
Conmutativa: a fusionado con b es igual que b fusionado con a. Asociativa: tres fusiones dan lo mismo agrupadas de cualquier forma. Idempotente: fusionar dos veces el mismo estado no cambia nada.
Así un mensaje puede llegar tarde, repetido o desordenado, y las réplicas siguen coincidiendo.
Un G-Counter guarda un número por réplica
Cada réplica solo suma en su propia entrada. El valor es la suma de todas las entradas.
Para fusionar, toma el número mayor de cada réplica. Quedarse con el mayor de dos números es conmutativo, asociativo e idempotente, así que la fusión entera es una unión. Sumar en lugar de tomar el mayor no es idempotente.
Fusiona tres G-Counter en dos órdenes
docker exec jupyter python3 steps/gcounter.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
| Momento | Móvil | Portátil | Tableta |
|---|---|---|---|
| Antes de sincronizar | 3 | 5 | 2 |
| Tras sincronizar, en cualquier orden | 10 | 10 | 10 |
| El móvil fusiona el portátil dos veces más | 10 | 10 | 10 |
| Un número normal con un aviso repetido | 19 | nada | nada |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Pruébalo: seis órdenes, un total
from itertools import permutations
def merge(a, b):
out = dict(a)
for name, count in b.items():
out[name] = max(out.get(name, 0), count)
return out
# Pasos contados por tres móviles, sin conexión
ana = {"ana": 4}
ben = {"ben": 7}
cai = {"cai": 2, "ana": 1} # cai ya había oído a ana antes
for order in permutations([ana, ben, cai]):
state = {}
for replica in order:
state = merge(state, replica)
print(sum(state.values()), state)
# Todos los órdenes dan el mismo total. Cambia merge para que sume en vez de usar max.
Un error frecuente
Advertencia
Mucha gente cree que una fusión debe sumar los dos contadores. Así se cuenta dos veces un estado que llega dos veces, y las redes lo hacen. Toma el número mayor de cada réplica, y repetir una fusión no hará daño.
Para bajar hace falta un segundo contador
Un G-Counter no puede bajar, porque un número menor perdería todas las fusiones. Por eso un PN-Counter guarda dos G-Counter: uno cuenta las subidas y otro las bajadas.
Cada uno se fusiona tomando el número mayor por réplica. El valor es subidas menos bajadas.
Fusiona "me gusta" y "ya no me gusta"
docker exec jupyter python3 steps/pncounter.pySe muestra aquí y no se ejecuta. Pulsa Iniciar laboratorio para escribirlo en el terminal de tu propio laboratorio.