Replicación y modelos de consistencia

📐 Fundamento

Modelos de consistencia (de más fuerte a más débil):

1. Linearizabilidad (Linearizability):

El sistema se comporta como si fuera un único servidor. Toda operación parece ocurrir en un momento puntual entre su inicio y su fin. Si A escribe y luego B lee, B ve el valor escrito por A.

• El modelo más intuitivo para el programador.
• El más costoso: requiere coordinación entre réplicas para cada operación.
• Usado en: etcd, ZooKeeper, Spanner.

2. Consistencia secuencial (Sequential Consistency):

Las operaciones de cada proceso parecen ejecutarse en orden, y hay algún orden total consistente con todos los procesos. Pero ese orden no tiene que respetar el tiempo real.

• Más débil que linearizabilidad: no garantiza "tiempo real".
• Usado en: algunos protocolos de memoria compartida.

3. Consistencia causal (Causal Consistency):

Si A causa B (A happenend-before B), todos los nodos ven A antes que B. Operaciones sin relación causal pueden verse en cualquier orden.

• Mucho más eficiente que linearizabilidad.
• Usado en: Dynamo, algunas implementaciones de CRDTs.

4. Consistencia eventual (Eventual Consistency):

Si no hay nuevas actualizaciones, eventualmente todas las réplicas convergen al mismo valor. Sin garantías de cuándo.

• El modelo más débil y más eficiente.
• Aceptable para: contadores de "likes", carritos de compra, DNS.
• No aceptable para: saldos bancarios, inventario crítico.

Resumen:

Linearizabilidad     ← más fuerte, más lento
         ↓
Secuencial
         ↓
Causal
         ↓
Eventual Consistency ← más débil, más rápido

📐 Fundamento

Last Write Wins (LWW):

La escritura con mayor timestamp gana. Simple, pero problemático: los relojes no están sincronizados perfectamente, y puede perder datos.

# Problema con LWW:
# Nodo A (reloj adelantado): actualiza precio a $2.00 a las 12:00:01
# Nodo B (reloj atrasado):   actualiza precio a $1.50 a las 12:00:00.5

# Al sincronizar: LWW elige $2.00 (ts mayor) → ¡correcto por accidente!
# Pero si el reloj de B fuera el adelantado, elegiría $1.50 → ¡incorrecto!

Relojes vectoriales (Vector Clocks):

Un vector de contadores, uno por nodo. Capturan la causalidad perfectamente.

from typing import Dict

class VectorClock:
    def __init__(self, nodos: list):
        self.clock: Dict[str, int] = {n: 0 for n in nodos}
        self.nodo = None
    
    def incrementar(self, nodo: str):
        self.clock[nodo] += 1
    
    def actualizar(self, otro: 'VectorClock'):
        for nodo, tiempo in otro.clock.items():
            self.clock[nodo] = max(self.clock[nodo], tiempo)
    
    def precede(self, otro: 'VectorClock') -> bool:
        """¿Este reloj precede causalmente a otro?"""
        return (all(self.clock[n] <= otro.clock[n] for n in self.clock)
                and any(self.clock[n] < otro.clock[n] for n in self.clock))
    
    def concurrente(self, otro: 'VectorClock') -> bool:
        """¿Estos eventos son concurrentes (sin relación causal)?"""
        return not self.precede(otro) and not otro.precede(self)

# Ejemplo: dos escrituras concurrentes
vc_a = VectorClock(['A', 'B', 'C'])
vc_b = VectorClock(['A', 'B', 'C'])

vc_a.incrementar('A')  # A escribe: {A:1, B:0, C:0}
vc_b.incrementar('B')  # B escribe: {A:0, B:1, C:0}

print(vc_a.concurrente(vc_b))  # True — escrituras concurrentes, hay conflicto

¿Qué hacer con el conflicto?

1. Elegir automáticamente (LWW) — puede perder datos.
2. Guardar ambas versiones — la aplicación resuelve el conflicto (Amazon Dynamo).
3. Prevenir el conflicto — usar CRDT (siguiente sección).

Amazon Dynamo: Guarda ambas versiones con sus relojes vectoriales. La aplicación (o el usuario) decide cuál es la "correcta". El carrito de compras puede tener dos versiones — se hace la unión de los ítems.

📐 Fundamento

G-Counter (Grow-Only Counter) — el CRDT más simple:

class GCounter:
    """Contador que solo puede incrementarse. Sin conflictos posibles."""
    
    def __init__(self, nodos: list, nodo_id: str):
        self.contadores = {n: 0 for n in nodos}
        self.nodo_id = nodo_id
    
    def incrementar(self, cantidad: int = 1):
        self.contadores[self.nodo_id] += cantidad
    
    def valor(self) -> int:
        return sum(self.contadores.values())
    
    def merge(self, otro: 'GCounter') -> 'GCounter':
        """Merge: tomar el máximo de cada nodo."""
        resultado = GCounter(list(self.contadores.keys()), self.nodo_id)
        for nodo in self.contadores:
            resultado.contadores[nodo] = max(
                self.contadores[nodo],
                otro.contadores.get(nodo, 0)
            )
        return resultado

# Ejemplo: contador de pedidos distribuido
nodos = ['local_smi', 'local_smn', 'local_usulutan']

pedidos_smi = GCounter(nodos, 'local_smi')
pedidos_smn = GCounter(nodos, 'local_smn')

pedidos_smi.incrementar(50)  # 50 pedidos en SMI
pedidos_smn.incrementar(30)  # 30 pedidos en SMN

# Al sincronizar (merge):
total = pedidos_smi.merge(pedidos_smn)
print(f"Total pedidos: {total.valor()}")  # 80

# Si el merge se hace en el otro orden, el resultado es el mismo
total2 = pedidos_smn.merge(pedidos_smi)
print(f"Total pedidos: {total2.valor()}")  # 80 (commutativo)

Otros CRDTs comunes:

Sistemas que usan CRDTs: Riak, Redis (tipos de datos distribuidos), Apple Notes (sincronización offline), figma (edición colaborativa de diseños).