scalability distributed paxos raft crdt

scalability - Tipos de datos replicados(CRDT) libres de conflicto frente a Paxos o Raft



distributed (7)

¿Cuándo es una buena idea usar algo como CRDT en lugar de paxos o balsa?

Comentario a una respuesta por @btilly:

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

  • CRDT se relaciona con la familia de algoritmos de consistencia eventual ,
  • La familia de algoritmos PAXOS se relaciona con la consistencia / Linerizability (sincronización de cliente a servidor),
  • RAFT es equivalent a PAXOS de forma algorítmica y de consistencia, pero se considera más fácil de 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 usar 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 db-dist y en todos los demás casos en los que la coherencia eventual sea adecuada.

PAXOS se usa principalmente en sistemas propietarios que soportan infraestructura de sistemas (es decir, Chubby), o para implementar la 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 OSS como ETCD, Cónsul, ...

(No recuerdas en qué se basan CockroachDB y TiDB)

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

ps PAXOS! = ZooKeeper. ZooKeeper utiliza un algoritmo diferente llamado ZAB y no es una máquina de estado replicada, sino una máquina de instantáneas replicadas con un solo escritor y un modelo de lectura relajada. Chubby de Google basado en Paxos, pero su propietario.

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

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 un número menor de réplicas);
  • confiabilidad (CRDT es más débil que Paxos porque escribe en un número menor de réplicas (más pequeño que la mayoría) lo que puede resultar en un estado perdido);
  • consistencia (CRDT es más débil que Paxos porque permite escrituras simultáneas sin punto de sincronización (básicamente no hay réplicas superpuestas), mientras que las escrituras Paxos siempre requieren una réplica superpuesta para realizar la serialización).

Mi sugerencia es que deberíamos usar Paxos cuando las réplicas no están muy alejadas unas de otras (por ejemplo, dentro de un centro de datos), y usar CRDT cuando la partición de la red es normal (por ejemplo, móvil desconectado).

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

Después de que esto suceda, ya no es posible que los sistemas se inserten entre las entradas que tienen claves idénticas pero diferentes desambiguadores, ya que esto requiere que el sistema inserte otra clave idéntica pero que controle el ordenamiento de los mismos. Los desambiguadores no son densos, por lo que no siempre es posible. Si los desambiguadores fueran otro árbol, solucionas un problema pero luego necesitas otro mecanismo de resolución de conflictos más profundo ... etc.

Este problema no mencionado, más el hecho de que necesita hacer un compromiso de dos fases para poner en orden los metadatos me hace pensar que las CRDT aún son un trabajo en progreso.

Si puedes usar algo como CRDT, hazlo. Deberías obtener un rendimiento mucho mejor. También permite casos de uso interesantes, como trabajar sin conexión y luego fusionarlos más tarde. Sin embargo, no siempre es posible diseñar cosas de manera que una CRDT funcione para usted. En ese caso, paxos puede resolver los problemas difíciles para usted.

Pero incluso si ha decidido usar paxos, generalmente debería limitar la cantidad de trabajo que se realiza directamente a través del algoritmo de paxos. En su lugar, por razones de rendimiento, desea reservar paxos para operaciones necesarias como la elección maestra y luego dejar que una configuración maestra replicada maneje la mayoría de las decisiones. (En un entorno de alto rendimiento, es probable que el maestro haga algo como delegar la responsabilidad de fragmentos específicos a niños específicos, que se replican entre sí. No permita que el maestro se convierta en un cuello de botella ...)

Dicho esto, es mucho más fácil afirmar que agitará la varita mágica de paxos que hacerlo en la práctica. En ese sentido, puede encontrar http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/archive/chubby-osdi06.pdf como una descripción interesante de las dificultades que un mundo real Es probable que encuentre la implementación de paxos.

Siempre que sea apropiado. Sin embargo, PaxOS no es tan malo ya que su rendimiento suele ser el mismo que con CRDT, sin mencionar que la fiabilidad es mucho mayor (CRDT puede resultar en un estado perdido), y su latencia no es tan mala, ya que solo requiere una mayoría De las réplicas responde en lugar de todas.

Los CRDT y los 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. Las CRDT son tipos de datos que suponen que se producirán actualizaciones simultáneas. Paxos es un protocolo que obliga a no hacerlo, al imponer un orden total en 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 todas las réplicas en el mismo orden ejecutarán las escrituras en el conjunto. De manera más general, garantiza que todas las réplicas ACEPTAN cómo evoluciona el estado del conjunto.

Si, por ejemplo, user1 realiza update1 en replica1, agregando elemento 1 al conjunto replicado mientras que user2 realiza update2 simultáneamente, agrega element2 a replica2, Paxos hará que las réplicas estén de acuerdo en un orden dado para esas actualizaciones, o posiblemente esté de acuerdo en elegir una de las dos actualizaciones y descartar la segunda, dependiendo de cómo lo use y lo que quiera lograr. Si el resultado de Paxos es, digamos, 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, SOLAMENTE los siguientes estados del conjunto (suponiendo que el conjunto estaba vacío al principio):

{} (conjunto vacio)

{element1}

{element1, element2}

Además, estos estados solo se pueden ver en ese orden, lo que significa que una vez que el estado del conjunto sea {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: No disponible: si las réplicas no pueden comunicarse entre sí (partición de red), su conjunto no puede actualizarse, 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 la 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, copia única. Se supone que no hay acuerdo ni orden total sobre cómo se actualizan las réplicas.

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

En nuestro ejemplo de dos usuarios que realizan actualizaciones al mismo tiempo, un sistema que no ejecuta Paxos para ordenar operaciones en el conjunto (esto sucede, por ejemplo, bajo una eventual o causal coherencia), permitirá que réplica1 agregue elemento1 mientras que réplica2 agrega elemento2

entonces, el estado en réplica1 será: {elemento1}

y el estado en réplica2 será: {elemento2}

En este punto en el tiempo, las réplicas divergen. Más adelante, cuando las réplicas se sincronicen, intercambiarán sus actualizaciones y finalmente mostrarán este estado:

el estado en la réplica1 será: {elemento1, elemento2}

El estado en la réplica2 será: {element2, element1}

En este punto en el tiempo, 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) lean, los siguientes estados del conjunto (suponiendo que el conjunto estaba vacío al principio):

{} (conjunto vacio)

{element1} (si leen desde réplica1)

{element2} (si se leen desde réplica2)

{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. Los agregados y eliminaciones simultáneos son más complejos Hay muchos tipos de datos con diferentes problemas:

Un estudio exhaustivo de los tipos de datos replicados convergentes y conmutativos.

Lado positivo: alta disponibilidad: si las réplicas no pueden comunicarse entre sí (partición de red), su conjunto PUEDE actualizarse. 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.