¿Cómo contar los éxitos de la página google.com? ¿Y cómo almacenar el contador de Me gusta de usuarios muy populares? Este artículo propone considerar la solución de estos problemas utilizando CRDT (Tipos de datos replicados libres de conflictos, que en ruso se traduce aproximadamente como Tipos de datos replicados libres de conflictos) y, en el caso más general, tareas de sincronización de réplicas en un sistema distribuido con varios nodos principales.

1. Introducción

Hace tiempo que estamos acostumbrados a usar aplicaciones como un calendario o un servicio de notas como Evernote. Están unidos por el hecho de que le permiten trabajar sin conexión, desde múltiples dispositivos y a varias personas al mismo tiempo (en los mismos datos). El desafío que enfrentan los desarrolladores de cada una de estas aplicaciones es cómo garantizar la sincronización más "fluida" de los datos modificados simultáneamente en varios dispositivos. Idealmente, la participación del usuario no debería ser necesaria para resolver conflictos de fusión.

En un artículo anterior, ya consideramos un enfoque para resolver tales problemas: Transformación operativa, también describirá un método muy similar que tiene ventajas y desventajas (por ejemplo, CRDT para JSON aún no se ha inventado. Upd: Gracias a msvn por el enlace, aquí Aquí hay un proyecto de los autores de un artículo de investigación sobre la implementación de JSON en CRDT)

2. Fuerte consistencia eventual

Recientemente, se ha escrito mucho trabajo y se han realizado muchas investigaciones en el campo de la consistencia eventual. En mi opinión, ahora hay una fuerte tendencia hacia un cambio de una consistencia fuerte a varias opciones de consistencia, a investigar qué consistencia en qué situaciones / sistemas es más rentable aplicar, a repensar las definiciones existentes. Esto lleva a cierta confusión, por ejemplo, cuando los autores de algunos trabajos, hablando de consistencia, significan consistencia eventual con alguna propiedad adicional, y otros autores usan cierta terminología para esto.

La pregunta planteada por los autores de uno de los artículos critica la definición actual de consistencia eventual: de acuerdo con esto, si su sistema siempre responde "42" a todas las solicitudes, entonces todo está bien, eventualmente es consistente.

Sin violar la exactitud de este artículo, yo, siguiendo a los autores de los artículos originales, utilizaré la siguiente terminología (tenga en cuenta que estas no son definiciones estrictas, son diferencias):

• Consistencia fuerte (SC): todas las operaciones de escritura están estrictamente ordenadas, una solicitud de lectura en cualquier réplica devuelve el mismo último resultado registrado. Se necesita un consenso en tiempo real para resolver conflictos (con las consecuencias resultantes), puede soportar una caída a n / 2 - 1 nodos.
• Consistencia eventual (EC): actualice los datos localmente, envíe la actualización aún más. Leer en diferentes réplicas puede devolver datos obsoletos. En caso de conflictos, retrocedemos o de alguna manera decidimos qué hacer. T.O. Todavía se necesita consenso, pero ya no en tiempo real .
• Fuerte consistencia eventual (SEC): EC + para resolver conflictos, las réplicas tienen un algoritmo predefinido. T.O. no se necesita consenso ; puede soportar una caída a n - 1 nodos.

Tenga en cuenta que SEC (por así decirlo) resuelve el problema del teorema CAP: se satisfacen las tres propiedades.

Por lo tanto, estamos listos para donar SC y queremos tener un cierto conjunto de tipos de datos básicos para nuestro sistema distribuido potencialmente inestable que resolverá automáticamente los conflictos de escritura por nosotros (no se requiere la interacción del usuario ni la solicitud a algún árbitro)

3. Tareas sobre Me gusta y éxitos.

Sin lugar a dudas, existen varios algoritmos para resolver tales problemas. CRDT ofrece una manera bastante elegante y fácil.

Recuento de visitas de Google.com:

google.com procesa aproximadamente 150,000 solicitudes por segundo de todo el mundo. Obviamente, el contador debe actualizarse de forma asíncrona. Las colas resuelven parcialmente el problema; por ejemplo, si proporcionamos una API externa para obtener este valor, tendremos que hacer una replicación para no colocar el repositorio con solicitudes de lectura. Y si ya hay replicación, ¿tal vez sin colas globales?

Contando los gustos de los usuarios:

La tarea es muy similar a la anterior, solo que ahora necesita contar golpes únicos.

4. Terminología

Para una comprensión más completa del artículo, debe conocer los siguientes términos:

1. Idempotencia
   Dice que la aplicación de la operación varias veces no cambia el resultado.
   Ejemplos: operación GET o adición con cero: $$$f (x) = x + 0$
   
2. Conmutatividad
   $$$f (x, y) = f (y, x)$
   
3. Orden parcial
   Reflexividad + Transitividad + Antisimetría
   
4. Medio enrejado
   Conjunto parcialmente ordenado con cara superior (inferior) exacta
   
5. Vector de versión
   Un vector de dimensión es igual al número de nodos, y cada nodo, cuando ocurre un determinado evento, incrementa su valor en el vector. Durante la sincronización, los datos se transmiten con este vector y esto introduce una relación de orden, que le permite determinar qué réplica tiene datos antiguos / nuevos.

5. Modelos de sincronización

Basado en el estado:

También llamada sincronización pasiva, forma el tipo de datos replicados convergentes - CvRDT.
Se utiliza en sistemas de archivos como NFS, AFS, Coda y en almacenes KV Riak, Dynamo
En este caso, las réplicas intercambian estados directamente, la réplica receptora fusiona el estado recibido con su estado actual.


Para realizar la convergencia de réplicas utilizando esta sincronización, es necesario que:

• Los datos formaron un entramado
• La función de fusión produjo un límite superior exacto
• Las réplicas formaron un gráfico conectado.

Un ejemplo:

• Conjunto de datos: números naturales $$$\ mathbb {N}$
• Artículo mínimo: $$$- \ infty$
• $$$merge (x, y) = max (x, y)$

Dichos requisitos nos dan una función de fusión conmutativa e idempotente que crece de manera monotónica en un conjunto de datos dado:


Esto garantiza que las réplicas converjan tarde o temprano y le permite no preocuparse por el protocolo de transferencia de datos: podemos perder mensajes con un nuevo estado, enviarlos varias veces e incluso enviarlos en cualquier orden .

Basada en operaciones:

También se llama Sincronización activa, forma el Tipo de datos replicados conmutativos - CmRDT.
Utilizado en sistemas cooperativos como Bayou, Rover, IceCube, Telex.

En este caso, las réplicas intercambian operaciones de actualización de estado. Al actualizar los datos, la réplica original:

• Llama al método generate (), que devuelve el método efector () para ejecutarse en las réplicas restantes. En otras palabras, efector () es el cierre para cambiar el estado de las réplicas restantes.
• Aplicando un efector a un estado local
• Envía efector a todas las demás réplicas

Para realizar la convergencia de réplicas, se deben cumplir las siguientes condiciones:

• Protocolo de entrega confiable
• Si el efector se entrega a todas las réplicas de acuerdo con el orden ingresado (para un tipo dado), los efectores simultáneos son conmutativos, o
• Si el efector se entrega a todas las réplicas sin tener en cuenta el orden, todos los efectores son conmutativos.
• En caso de que el efector se pueda entregar varias veces, entonces debe ser idempotente
• Algunas implementaciones usan colas (Kafka) como parte del protocolo de entrega.

Basado en Delta:

Teniendo en cuenta el estado / operación, es fácil notar que si una actualización cambia solo una parte del estado, entonces no tiene sentido enviar el estado completo, y si una gran cantidad de cambios afectan un estado (por ejemplo, un contador), puede enviar un cambio agregado y no todas las operaciones. cambios

La sincronización Delta combina ambos enfoques y envía mutadores delta que actualizan el estado de acuerdo con la última fecha de sincronización. En la sincronización inicial, es necesario enviar el estado por completo, y algunas implementaciones en tales casos ya tienen en cuenta el estado de las réplicas restantes al construir mutadores delta.

El siguiente método de optimización es comprimir el registro basado en operaciones, si se permiten retrasos.

Puro basado en la operación:

Hay un retraso en la creación del operador en la sincronización basada en operaciones. En algunos sistemas esto puede no ser aceptable, entonces debe enviar el cambio original a costa de complicar el protocolo y la cantidad adicional de metadatos.

Enfoques de uso estándar:

• Si las actualizaciones se envían inmediatamente en el sistema, entonces sería una mala elección, ya que enviar todo el estado es más costoso que una operación de actualización. El basado en Delta funciona mejor, pero en este caso particular, la diferencia con el basado en estado será pequeña.
• Si necesita sincronizar la réplica después de una falla , entonces las opciones basadas en estado y delta son la elección perfecta. Si tiene que usar operaciones basadas en operaciones, las opciones son:
  
  1) Tira todas las operaciones perdidas desde el momento del fallo
  2) Una copia completa de una de las réplicas y la reversión de operaciones perdidas
• Como se señaló anteriormente, las operaciones basadas en operaciones requieren que las actualizaciones se entreguen exactamente una vez a cada réplica. El requisito de entrega solo se puede omitir una vez si el efector es idempotente. En la práctica, es mucho más fácil implementar el primero que el segundo.

La relación entre Op-based y State-based:

Se pueden emular dos enfoques entre sí, por lo que en el futuro consideraremos CRDT sin referencia a ningún modelo de sincronización específico.

6. CRDT

6.1 Contador

Un entero que admite dos operaciones: inc y dec. Como ejemplo, considere posibles implementaciones para sincronizaciones basadas en operaciones y basadas en estado:

Contador basado en operaciones:

Obviamente, solo enviando actualizaciones. Ejemplo para inc:

function generator() { return function (counter) { counter += 1 } } 

Contador basado en el estado:

La implementación ya no es tan obvia, ya que no está claro cómo debería ser la función de fusión.

Considere las siguientes opciones:

Contador que aumenta monotónicamente (contador de solo incremento, contador G):

Los datos se almacenarán como un vector de dimensión igual al número de nodos (vector de versión) y cada réplica aumentará el valor en posición con su id.

La función de fusión tomará un máximo en las posiciones correspondientes, y el valor final es la suma de todos los elementos del vector.

$$

$$\ begin {align} inc () &: V [id ()] = V [id ()] + 1 \\ value () &: \ sum_ {i = 0} ^ {n} V [i] \\ fusionar (C_1, C_2) &: i \ in [1..n] \ Result [i] = max (C_1.V [i], C_2.V [i]) \ end {align}$$

También puedes usar el G-Set (ver más abajo)

Aplicación:

• Contando clics / golpes (sic!)

Contador con soporte de decremento (contador PN)

Comenzamos dos contadores G, uno para operaciones de incremento, el segundo, para disminución

Aplicación:

• El número de usuarios registrados en una red p2p, como Skype

Contador no negativo

Aún no existe una implementación simple. Sugiera sus ideas en los comentarios, discuta.

6.2 Registrarse

Una celda de memoria con dos operaciones: asignar (escribir) y valor (leer).
El problema es que asignar no es conmutativo. Hay dos enfoques para resolver este problema:

Último registro de victorias de escritura (LWW-Register):

Ingresamos el pedido completo a través de la generación de una identificación única para cada operación (marca de tiempo, por ejemplo).

Un ejemplo de sincronización es el intercambio de pares (valor, id):


Aplicación:

• Columnas en cassandra
• NFS - archivo en su totalidad o en parte

Regístrese con varios valores (registro de valores múltiples, registro MV):

El enfoque es similar a un contador G: almacenamos el conjunto (valor, vector de versión). Valor de registro - todos los valores, al fusionar - LWW por separado para cada valor en el vector.


Aplicación:

• Cesta en Amazon. Un error conocido está asociado con esto, cuando después de eliminar un artículo de la cesta, aparece allí nuevamente. La razón es que, a pesar de que el registro almacena un conjunto de valores, no es un conjunto (vea la imagen a continuación). Amazon, por cierto, ni siquiera lo considera un error, de hecho, aumenta las ventas.
• Riak En un caso más general, cambiamos el problema de elegir el valor real (nota: ¡no hay conflicto!) Para la aplicación.

Explicación del error en Amazon:

6.3 lotes

El conjunto es el tipo básico para construir contenedores, mapas y gráficos, y admite operaciones: add y rmv, que no son conmutativas.

Considere la implementación ingenua del conjunto basado en operaciones, en el que se ejecutan add y rmv a medida que llegan (add llega a 1 y 2 réplicas al mismo tiempo, luego rmv va a 1)


Como puede ver, las réplicas eventualmente se dispersaron. Considere las diversas opciones para construir conjuntos libres de conflictos:

Conjunto de cultivo (conjunto G):

La solución más fácil es evitar que se eliminen elementos. Todo lo que queda es la operación de agregar, que es conmutativa. La función de fusión es la unión de conjuntos.

Conjunto de dos fases (2P-Set):

Le permitimos eliminar, pero no puede agregarlo nuevamente después de eliminarlo. Para implementar, configuramos un conjunto separado de elementos remotos del conjunto G (dicho conjunto se llama conjunto de lápidas)
Ejemplo para basado en estado:

$$

$$\ begin {align} lookup (e) &: e \ in A \ land e \ notin R \\ add (e) &: A = A \ cup \ {e \} \\ rmv (e) &: R = R \ cup \ {e \} \\ merge (S_1, S_2) &: \\ Res & ult.A = S_1.A \ cup S_2.A \\ Res & ult.R = S_1.R \ cup S_2.R \ end {alinear}$$

Conjunto de elementos LWW:

La siguiente forma de implementar un conjunto libre de conflictos es introducir un orden completo, una de las opciones es generar marcas de tiempo únicas para cada elemento.

Obtenemos dos conjuntos: add-set y remove-set, cuando se llama a add (), add (element, unique_id ()), cuando se verifica si hay un elemento en el conjunto, mira dónde la marca de tiempo es mayor, en remove-set o en add-set

PN-Set:

Variación con el orden del conjunto: comenzamos un contador para cada elemento, cuando lo agregamos, lo aumentamos, cuando lo eliminamos lo disminuimos. Un elemento está en el conjunto si su contador es positivo.

Tenga en cuenta el efecto interesante: en la tercera réplica, agregar un elemento no conduce a su aparición.

Observar-Eliminar conjunto, OR-Conjunto, Agregar-Ganar conjunto:

En este tipo, agregar tiene prioridad sobre eliminar. Ejemplo de implementación: a cada elemento recién agregado se le asigna una etiqueta única (relativa al elemento, y no al conjunto completo). Rmv elimina un elemento del conjunto y envía todos los pares vistos (elemento, etiqueta) a las réplicas para su eliminación.

Conjunto Quitar-ganar:

Similar al anterior, pero al mismo tiempo agrega / rmv rmv gana.

6.4 Gráfico

Este tipo se construye sobre la base de muchos. El problema es este: si hay operaciones simultáneas addEdge (u, v) y removeVertex (u), ¿qué debo hacer? Son posibles las siguientes opciones:

• Eliminar la prioridad de vértice, se eliminan todos los bordes incidentes con este vértice
• Prioridad AddEdge, vértices eliminados restaurados
• Retrasamos la ejecución de removeVertex hasta que se ejecuten todos los addEdge simultáneos.

La opción más fácil es la primera, para su implementación (2P2P-Graph) es suficiente obtener dos 2P-Set, uno para los vértices, el segundo para los bordes

6.5 Mapa

Mapa de literales:

Dos problemas a resolver:

• ¿Qué hacer con las operaciones de venta simultáneas? Por analogía con los contadores, puede elegir semántica LWW o MV
• ¿Qué hacer con put / rmv simultáneo? Por analogía con los conjuntos, puedes poner semánticas de put-wins, rmv-wins o last-put-wins.

Mapeo de CRDT (Mapa de CRDT):

Un caso más interesante, porque le permite construir asignaciones anidadas. No consideramos casos de cambio de tipos anidados; esto debería decidirlo el propio CRDT anidado.

Eliminar-como-recursivo-restablecer mapa

La operación de eliminación "restablece" el valor de tipo a un cierto estado inicial. Por ejemplo, para un contador, este es un valor cero.

Considere un ejemplo: una lista de compras general. Uno de los usuarios agrega harina, y el segundo realiza un pago (esto lleva a una llamada a la operación de eliminación en todos los elementos). Como resultado, una unidad de harina permanece en la lista, lo que parece lógico.


Eliminar-gana mapa

La operación rmv tiene prioridad.

Ejemplo: en un juego en línea, un jugador de Alice tiene 10 monedas y un martillo. Luego ocurren dos eventos simultáneamente: en la réplica A, ella produjo un clavo, y en la réplica B, su personaje se elimina con la eliminación de todos los objetos:



Tenga en cuenta que al usar remove-as-recursive, eventualmente quedaría un clavo, que no es el estado correcto cuando se elimina el personaje.

Actualización-gana mapa

Las actualizaciones tienen prioridad, o más bien, cancelan las operaciones anteriores para eliminar rmv simultáneo.

Ejemplo: en un juego en línea, el personaje de Alice en la réplica B se elimina debido a la inactividad, pero la actividad se produce en la réplica A al mismo tiempo. Obviamente, la operación de eliminación debe cancelarse.


Hay un efecto interesante cuando se trabaja con una implementación de este tipo: supongamos que tenemos dos réplicas, A y B, y que almacenan el conjunto con alguna clave k. Luego, si A elimina el valor de la clave k y B elimina todos los elementos del conjunto, al final las réplicas dejarán un conjunto vacío con la clave k.

Tenga en cuenta que una implementación ingenua no funcionará correctamente: no puede simplemente deshacer todas las operaciones de eliminación anteriores. En el siguiente ejemplo, con este enfoque, el estado final sería el estado inicial, que es incorrecto:

Lista

El problema con este tipo es que los índices de elementos en diferentes réplicas serán diferentes después de las operaciones locales de inserción / eliminación. Para resolver este problema, se aplica el enfoque de transformación operativa: al aplicar el cambio obtenido, se debe tener en cuenta el índice del elemento en la réplica original.

7. Riak

Como ejemplo, considere CRDT en Riak:

• Contador: PN-Counter
• Conjunto: Conjunto OR
• Mapa: Actualización-gana Mapa de CRDT
• (Boolean) Flag: OR-Set donde máximo 1 elemento
• Registro: pares (valor, marca de tiempo)

8. Quién usa CRDT

La sección wiki contiene buenos ejemplos.

9. Referencias

• Tiendas Key-CRDT
• Un tipo de datos JSON replicado sin conflictos
• Un estudio exhaustivo de los tipos de datos replicados convergentes y conmutativos
• Tipo de datos replicados convergentes y conmutativos
• Tipo de datos replicados sin conflictos
• Una guía de Bluffers para CRDT en Riak
• CRDT: una ACTUALIZACIÓN (o simplemente un PUT)
• Tipos de datos replicados sin conflictos: una descripción general
• Fuerte consistencia eventual y tipos de datos replicados libres de conflictos
• Estructuras de datos eventualmente consistentes