Tipos de Datos Replicados sin Conflictos (CRDT) frente a Paxos o Raft

Creo que este tipo sabe de lo que está hablando:

Blog

Video

Conclusión sobre los sistemas distribuidos

Los CRDT y Paxos tienen diferentes objetivos y se utilizan en diferentes escenarios. Tienen en común que ayudan a los programadores a lidiar con la concurrencia/replicación. Los CRDT son tipos de datos que asumen que se producirán actualizaciones simultáneas. Paxos es un protocolo que hace cumplir lo que no harán, haciendo cumplir una orden total sobre ellos. Veamos esto con más detalle.

Digamos que tenemos un conjunto replicado que se replica en dos lugares diferentes.

El uso de Paxos garantiza que escribe para el conjunto será ejecutado por cada réplica en el mismo orden. Más generalmente, garantiza que todas las réplicas están de ACUERDO en cómo evoluciona el estado del conjunto.

Si, por ejemplo, user1 realiza update1 en replica1, agrega el elemento 1 al conjunto replicado mientras que simultáneamente user2 realiza update2, agrega element2 en replica2, Paxos hará que las réplicas estén de acuerdo en un orden dado para esas actualizaciones, o posiblemente acuerden elegir una de las dos actualizaciones y descartar el segundo, dependiendo de cómo lo uses y de lo que quieras lograr. Si el resultado de Paxos es, por ejemplo, que update1 viene antes de update2, cada réplica actualizará el conjunto en ese orden. Como consecuencia, los usuarios que leen el conjunto simultáneamente con esas actualizaciones pueden observar, independientemente de dónde (en qué réplica) lean, SOLO los siguientes estados del conjunto (suponiendo que el conjunto estaba vacío al principio):

{} (conjunto vacío)

{element1}

{element1, element2}

Además, estos estados se pueden ver SOLO en ese orden, lo que significa que una vez que el estado del conjunto es {element1, element2} (en cada réplica), ninguna lectura posterior devolverá {} o {element1}.

Lado positivo: Este conjunto es fácil de razonar, ya que es equivalente a un conjunto que no se replica.

Lado negativo: Indisponibilidad: Si las réplicas no pueden comunicarse entre sí (partición de red), su conjunto no se puede actualizar, ya que no puede haber acuerdo. Bajo rendimiento, alta latencia: El acuerdo requiere que las réplicas se sincronicen antes de responder al cliente. Esto incurre en latencia proporcional a la latencia entre réplicas.

Las CRDT tienen garantías más débiles. Un conjunto CRDT no es equivalente a uno secuencial de copia única. Supone que no hay acuerdo o pedido total sobre cómo se actualizan las réplicas.

Los CRDT garantizan que si ambas réplicas del conjunto han visto las mismas actualizaciones (independientemente del orden en que vean ellos), entonces exhibirán el mismo estado; las réplicas convergerán.

En nuestro ejemplo de dos usuarios que realizan actualizaciones simultáneamente, un sistema que no ejecuta Paxos para ordenar operaciones en el conjunto (esto sucede, por ejemplo, bajo consistencia eventual o causal), permitirá a replica1 agregar element1 mientras replica2 agrega element2

Entonces, el estado en replica1 será: {element1}

Y el estado en replica2 será: {element2}

En este momento, las réplicas divergir. Más tarde, cuando las réplicas se sincronicen, intercambiarán sus actualizaciones, finalmente exhibiendo este estado:

El estado en replica1 será: {element1, element2}

El estado en replica2 será: {element2, element1}

En este momento, las réplicas han convergido.

Los usuarios que leen el conjunto simultáneamente con esas actualizaciones pueden observar, dependiendo de dónde (en qué réplica) leen, los siguientes estados del conjunto (suponiendo que el conjunto estaba vacío en el beggining):

{} (conjunto vacío)

{element1} (si leen de replica1)

{element2} (si leen de replica2)

{element1, element2}

{element2, element1}

Lado negativo: Este conjunto es difícil de razonar, ya que muestra estados que no podrían ocurrir en un conjunto secuencial. En nuestro ejemplo, hemos observado solo el caso de dos adiciones simultáneas a un conjunto, lo cual es sencillo. Las adiciones y eliminaciones simultáneas son más complejas Hay muchas tipos de datos con diferentes problemas:

A comprehensive study of Convergent and Commutative Replicated Data Types

Lado Positivo: Alta disponibilidad: Si las réplicas no pueden comunicarse entre sí (partición de red), su conjunto SE PUEDE actualizar. Las réplicas se sincronizarán cuando se conecten de nuevo. Alto rendimiento, baja latencia: Las réplicas responden inmediatamente a los clientes y se sincronizan en segundo plano, después de responder al cliente.

Hay un defecto en el ejemplo de CRDT Treedoc. Cada nodo requiere un desambiguador para el caso cuando dos sistemas insertan al mismo tiempo con la misma clave.

Después de que esto suceda, ya no es posible para los sistemas insertar entre las entradas que tienen claves idénticas pero diferentes desambiguadores, ya que eso requiere que el sistema inserte otra clave idéntica pero que controle el orden del desambiguador. Los desambiguadores no son densos, por lo que esto no siempre es posible. Si el los desambiguadores eran otro árbol, se resuelve un problema pero luego se necesita otro mecanismo de resolución de conflictos una profundidad más abajo ... sucesivamente.

Este problema no mencionado, más el hecho de que necesita hacer un commit de dos fases para ordenar los metadatos me hace pensar que los CRDT todavía son un trabajo en progreso.

Hay múltiples métricas que tenemos:

• rendimiento (CRDT y Paxos son iguales porque todas las solicitudes se replican en todas las réplicas al final, sin importar CRDT o Paxos);
• latencia (CRDT es mejor que Paxos porque escribe en menor número de réplicas);
• fiabilidad (CRDT es más débil que Paxos porque escribe a un número menor de réplicas (menor que la mayoría) que puede resultar en estado perdido);
• consistencia (CRDT es más débil que Paxos porque permite escrituras concurrentes sin punto de sincronización (básicamente no hay réplicas superpuestas), mientras que las escrituras Paxos siempre requieren una réplica superpuesta para hacer la serialización).

Mi sugerencia es que debemos usar Paxos cuando las réplicas no están lejos unas de otras (por ejemplo, dentro de un centro de datos), y usar CRDT cuando el particionamiento de red es normal (por ejemplo, móvil desconectado).

Comentario a una respuesta de @btilly:

La pregunta en el tema está relacionada con diferentes modelos de consistencia y, por lo tanto, patrones de diseño:

• CRDT se relaciona con la Consistencia Final familia de algoritmos,
• La familia de algoritmos PAXOS se relaciona con la consistencia fuerte / Linerizability (client to server sync,),
• RAFT es equivalente al PAXOS en una forma algorítmica y consistente, pero se considera más fácil implementar.

CRDT y Paxos son cosas muy diferentes y el uso debe decidirse en función de los requisitos de su arquitectura. Creo que la mejor manera de manejarlo, es revisar los casos de uso donde esos algoritmos se han aplicado con éxito.

Patrones de uso:

CRDT se puede utilizar para la sincronización de datos entre clientes (es decir, dispositivos móviles) y servidores, edición colaborativa en tiempo real, sincronización de valores en implementaciones de dist-db y todos los demás casos donde la consistencia eventual es fino.

PAXOS se usa principalmente en sistemas propietarios que soportan infraestructura de sistemas (es decir, Chubby), o para implementar sincronización en sistemas de bases de datos distribuidas como BigTable, Datastore, Spinnaker, Spanner y etc.

RAFT es más popular en proyectos de infraestructura de OSS como ETCD, Consul,...

(no recuerdo en qué se basan Cucaracha DB y TiDB)

También hay un BFT, pero se usa menos.

P. S. s. Es interesante cómo PAXOS está evolucionando todos estos años. En los últimos 20 años, se inventaron muchas variantes que manejan varias optimizaciones de casos de borde, tamaños de quórum y reconfiguración de clústeres.

Cuando sea apropiado. Sin embargo, PaxOS no es tan malo como su rendimiento es típicamente el mismo que con CRDT, por no mencionar que la fiabilidad es mucho mayor (CRDT puede resultar estado perdido), y, su latencia no es tan malo, ya que solo requiere una mayoría de las réplicas respuestas en lugar de todos.