CRDT (Tipos de datos replicados sin conflicto)

De Wikipedia, la enciclopedia libre

Los tipos de datos replicados sin conflicto (CRDT) son un tipo de dato abstracto que está diseñado para poder replicarse en múltiples máquinas o procesos.[1]​[2]​ Estos tipos de datos se utilizan en sistemas de replicación que siguen una estrategia optimista.[3]​

Utilizar estos tipos de datos simplifica los sistemas de almacenamiento de datos distribuidos,[3]​ pues asegura autonomía y consistencia ya que las réplicas pueden actualizarse sin necesidad de sincronizarse con otras réplicas, de forma independiente y concurrente.[2]​

Al ser un tipo de datos abstracto, CRDT necesita una interfaz bien definida con la cual interactuarán las aplicaciones que quieran comunicarse con los tipos de datos replicados sin conflicto.[2]​

El concepto de tipos de datos replicados sin conflicto fue expuesto con alto grado de detalle en 2011 por Marc Shapiro, Nuno Preguiça, Carlos Baquero y Marek Zawirski. Aunque anteriormente algunos de estos autores ya habían publicado investigaciones en las que describían o hacían referencia a este tipo de datos.[4]​[5]​

Propagación de actualizaciones en CRDT[editar]

Cuando se produce una modificación en algún CRDT este cambio se propaga de forma asíncrona al resto de las réplicas. Hay dos mecanismos para enfocar esta propagación: Peer to peer o siguiendo un modelo cliente servidor. En el primer caso el par modificado es el responsable de actualizar cada uno de sus pares individualmente, mientras que en el segundo caso un CRDT es designado como réplica primaria, será el responsable de recibir todas las notificaciones de cambios en las réplicas y propagará estas modificaciones al resto de réplicas.[6]​

Tipos de CRDTs[editar]

Los tipos de datos replicados libres de conflicto se pueden clasificar en dos estrategias diferentes en función del punto de vista que se siga para conseguir la consistencia. Estas dos estrategias son los CRDTs basados en estado y los CRDTs basados en operación.

Ambos tipos de CRDT pueden garantizar la consistencia y son intercambiables, la diferencia radica en la sencillez de la implementación y el coste de la comunicación. Los CRDTs basados en estado son menos complejos en cuanto a la implementación, pero el coste del envío de los estados puede ser mayor. Por otro lado, la implementación de los CRDTs basados en operación puede ser más compleja pero el coste de la comunicación es menor.[7]​

CRDTs basados en estado (CvRDTs)[editar]

Diagrama de aplicación de un CRDT basado en estado. Cada estado está indicado con un color diferente. El estado resultante de la combinación está representado con la mezcla de los colores de los estados que se combinan.

Los CRDTs basados en estado también son llamados CvRDTs (tipos de datos replicados convergentes).

En los CRDTs basados en estado las actualizaciones producen modificaciones únicamente sobre el estado de una de las réplicas. Eventualmente, las réplicas envían su estado a parte o a todas las demás réplicas. Cuando una réplica recibe el estado de otra réplica, es responsable de combinarlo con su propio estado. Al cabo de un tiempo todas las réplicas alcanzarían un estado consistente.

Sin embargo, para que las réplicas puedan alcanzar este estado consistente, el método de combinación debe cumplir ciertas propiedades. La primera de ellas es que la operación de combinación debe ser conmutativa, es decir, el estado resultante de combinar el estado de dos réplicas debe ser igual independientemente de cuál sea la réplica receptora y cuál sea la emisora. La segunda de ellas es que debe ser asociativa, es decir, el estado resultante de combinar el estado de tres réplicas debe ser igual independientemente del orden en el que se envíen los estados. Por último, debe ser idempotente, es decir, el estado resultante de combinar el estado de una réplica consigo mismo debe ser el propio estado. Una condición suficiente para que se cumplan estas tres propiedades es que la operación combinación se corresponda con la operación supremo del semirretículo superior formado por el conjunto de estados y una función de ordenación parcial entre ellos.[7]​

Una mejora de los CRDTs basados en estado son los basados en delta, en los que se envía solamente parte del estado cuando el cambio solo afecta a una parte de la réplica. El envío del estado completo es necesario solamente en la primera sincronización, de forma que se reduce la cantidad de información que es necesario enviar.[8]​

CRDTs basados en operación (CmRDTs)[editar]

Diagrama de aplicación de un CRDT basado en operación.

Los CRDTs basados en operación también son llamados CmRDTs (tipos de datos replicados conmutativos).

A diferencia de los CRDTs basados en estado, los CRDTs basados en operación no cuentan con una operación combinación. En su lugar, cada vez que se realiza una operación en una réplica se envía una función de actualización al resto con un mecanismo de envío con ordenación causal. Esta función de actualización es generada inmediatamente antes de ejecutar la actualización en la réplica originaria de la operación. Es muy importante que esto sea así para garantizar la dependencia causal de las actualizaciones. Cuando se tienen operaciones concurrentes en distintas réplicas, el orden de aplicación de las actualizaciones debería no importar. Por ello, la condición suficiente para que un tipo de dato sea un CRDT basado en operación es que cuente con una función “actualizar” que sea conmutativa para cualquier par de operaciones que puedan ser ejecutadas concurrentemente en distintas réplicas.[7]​

Existe también una variante de los CRDTs basados en operación que son los CRDTs basados en operaciones puras, que reducen el tamaño de la información enviada pues solamente se envían la operación y sus potenciales argumentos.[9]​

Implementaciones más conocidas de CRDTs[editar]

Hay 3 categorías principales:[8]​ contadores (cuya función es incrementar y decrementar un único valor), conjuntos (cuya función es añadir y eliminar elementos a un conjunto) y registros (almacenan un único valor que puede actualizarse).

Contadores[editar]

Los contadores son un tipo de CvRDT cuya función es permitir leer y modificar un valor de manera concurrente en diferentes máquinas.[10]​ Se basan en que el método de combinación es asociativo, conmutativo e idempotente.[11]​

Para implementar un contador es necesario mantener un estado interno y que todos los estados posibles puedan ser ordenados por alguna relación binaria.[12]​

G-Counter (Grow-Only-Counter)[editar]

Su característica principal es que el contador sólo se incrementa, no se decrementa.[8]​[11]​

La representación del estado interno es una matriz cuyo tamaño es el número total de nodos y cada nodo tiene una identificación entre 0 y número de nodos - 1.

El siguiente pseudocódigo muestra de una forma sencilla la lógica de este contador y las funciones necesarias para implementarlo:[8]​[11]​ 

Function Consulta ()
    suma <- matrizEstado[0] + matrizEstado[1] + ... + matrizEstado[n-1]
    return suma
End Consulta

Function Incrementar()
    matrizEstado[idNodo] <- matrizEstado[idNodo] + 1
End Incrementar

Function Combinar(matrizEstado_otroNodo)
    desde i=0 hasta n-1 hacer
        matrizEstado[i] = max(matrizEstado[i], matrizEstado_otroNodo[i])
End Combinar

La función Consulta devuelve la suma de todos los elementos de la matriz de estado.

La función Incrementar incrementa el valor del elemento de la matriz de estados en la posición correspondiente al identificador del nodo.

La función Combinar compara elemento a elemento dos matrices de estado, escogiendo en cada iteración el mayor de los dos.

PN-Counter (Positive Negative Counter)[editar]

A diferencia del anterior este contador también puede decrementarse.

La representación del estado interno se consigue a través de dos G-Counters, uno para representar los incrementos (comúnmente llamado p) y otro los decrementos (comúnmente llamado n).  De forma que p y n serán dos matrices de tamaño n, con n el número de nodos.[8]​[11]​

El siguiente pseudocódigo muestra de una forma sencilla la lógica de este contador y las funciones necesarias para implementarlo:[8]​[11]​ 

Function Consulta ()
    suma_p <- matrizEstado_p[0] + matrizEstado_p[1] + ... + matrizEstado_p[n-1]
    suma_n <- matrizEstado_n[0] + matrizEstado_n[1] + ... + matrizEstado_n[n-1]
    resultado <- suma_p - suma_n
    return resultado
End Consulta

Function Incrementar()
    matrizEstado_p[idNodo] <- matrizEstado_p[idNodo] + 1
End Incrementar

Function Decrementar()
    matrizEstado_n[idNodo] <- matrizEstado_n[idNodo] + 1
End Decrementar

Function Combinar(matrizEstado_p_otroNodo, matrizEstado_n_otroNodo)
    desde i=0 hasta n-1 hacer
        matrizEstado_p[i] = max(matrizEstado_p[i], matrizEstado_p_otroNodo[i])
        matrizEstado_n[i] = max(matrizEstado_n[i], matrizEstado_n_otroNodo[i])
End Combinar

La función Consulta devuelve la resta de las sumas de las dos matrices de estado.

La función Incrementar incrementa el valor del elemento de la matriz de estados p (matriz que representa los incrementos) en la posición correspondiente al identificador del nodo.

La función Decrementar incrementa el valor del elemento de la matriz de estados n (matriz que representa los decrementos) en la posición correspondiente al identificador del nodo.

La función Combinar compara elemento a elemento dos matrices de estado p, escogiendo en cada iteración el mayor de los dos. Realiza la misma operación con dos matrices de estado n.

Sets[editar]

Los conjuntos (sets) tienen dos operaciones características : añadir (add) y eliminar (remove).

G-Set (Grew Only Set)[editar]

La característica principal de este conjunto es que sólo se le añaden elementos, no se eliminan.[8]​[11]​

El estado interno está representado por un conjunto (set) inicialmente vacío.

El siguiente pseudocódigo muestra de una forma sencilla la lógica de este conjunto y las funciones necesarias para implementarlo:[8]​[11]​ 

Function Consulta()
    return set
End Consulta

Function Añadir(elemento)
    set <- añadir elemento a set
End Añadir

Function Combinar(set_otroNodo)
    set <- set U set_otroNodo
End Combinar

La función Consulta devuelve el conjunto.

La función Añadir añade un elemento al conjunto.

La función Combinar realiza la operación de unión sobre dos conjuntos, el resultado de esta operación sobrescribe el conjunto del nodo en el que se realiza.

2P-Set (2 Phase Set)[editar]

En un conjunto 2P-Set, a diferencia del caso anterior, sí se pueden eliminar elementos aunque no permite reinserciones.

En este caso el estado interno está representado por dos G-SET, uno para representar el conjunto de valores añadidos al 2P-SET (comúnmente llamado a (add)) y otro para representar el conjunto de valores eliminados del 2P-SET (comúnmente llamado r (remove) o tombstone).[8]​[11]​

El siguiente pseudocódigo muestra de una forma sencilla la lógica de este conjunto y las funciones necesarias para implementarlo:[8]​[11]​ 

Function Consulta()
    diferencia <- set_a - set_r
    return diferencia
End Consulta

Function Añadir(elemento)
    set_a <- añadir elemento a set_a
End Añadir

Function Eliminar(elemento)
    set_r <- añadir elemento a set_r

Function Combinar(set_a_otroNodo, set_r_otroNodo)
    set_a <- set_a U set_a_otroNodo
    set_r <- set_r U set_r_otroNodo
End Combinar

La función Consulta devuelve el resultado de aplicar la operación diferencia al conjunto a y al conjunto r.

La función Añadir añade un elemento al conjunto a (conjunto que representa los elementos añadidos al conjunto global del nodo 2P-SET).

La función Añadir añade un elemento al conjunto r (conjunto que representa los elementos eliminados del conjunto global del nodo 2P-SET).

La función Combinar realiza la operación de unión sobre dos conjuntos a, el resultado de esta operación sobrescribe el conjunto a del nodo en el que se realiza. Realiza la misma operación para dos conjuntos r.

LWW-element Set[editar]

Introduce un orden total en el conjunto, utilizando marcas de tiempo.

Al igual que el anterior, necesita 2 conjuntos, uno para representar los elementos añadidos y otro para representar los elementos eliminados del conjunto.[8]​[11]​

Las operaciones también son muy similares al 2P-SET, pero se ha de tener en cuenta que en LWW-element Set cuando se añade un elemento al conjunto también se añade su marca temporal.

Si un elemento está en el conjunto de añadidos y no se encuentra en el conjunto de eliminados, o si se encuentra tiene una marca temporal menos reciente que en el conjunto de añadidos, entonces ese elemento pertenece al conjunto.[8]​[11]​

A diferencia del 2P-SET el LWW-element Set sí permite reinserciones.

PN-Set[editar]

La lógica de este conjunto se basa en añadir un contador para cada elemento. Este contador se incrementa con la operación Añadir() y se decrementa con la operación Eliminar(). Si el contador del elemento es positivo entonces ese elemento pertenece al conjunto.[8]​

Observe-Remove Set, OR-Set, Add-Win Set[editar]

Los conjuntos de OR-Set son conjuntos LWW-element Set pero en lugar de marcas de tiempo utilizan etiquetas únicas.[8]​

Para cada elemento se mantienen dos listas de etiquetas, una que representa la acciones de añadir (lista de etiquetas añadidas) y otra que representa las acciones de eliminar(también llamada tombstone o lista de etiquetas eliminadas). La operación de añadir elemento al OR-Set genera un identificador único que es añadido a la lista de etiquetas añadidas. Los elementos se eliminan del OR-Set cuando todas las etiquetas que figuran en su lista de etiquetas añadidas también se encuentran en la lista de etiquetas eliminadas.[13]​

La operación de combinar dos OR-Set se basa en realizar la operación de unión sobre las dos listas de etiquetas añadidas y sobre las dos listas de etiquetas eliminadas de cada elemento.

Un elemento es miembro del conjunto si la diferencia entre la lista de etiquetas añadidas y vacías es no vacío, es decir, si no todas las etiquetas de la lista de etiquetas añadidas figuran en la lista de etiquetas eliminadas.[6]​

Se debe tener cuidado con el crecimiento de la lista de etiquetas eliminadas, una posible optimización es utilizar un vector de marcas de tiempo en cada réplica.[6]​

El nombre de Add-Win Set se debe a que, en el caso de quitar y añadir simultáneamente el mismo elemento, la acción de añadir tiene prioridad.[13]​

Remove-wins set (RWSet)[editar]

Es un conjunto OR-Set igual que el anterior, la diferencia: en el caso de quitar y añadir simultáneamente el mismo elemento, en este caso la acción de eliminar tiene prioridad.[13]​

Registros[editar]

Es un CRDT que únicamente guarda un valor.[6]​ Tiene dos operaciones: consultar y actualizar, la primera devuelve el valor y la segunda lo guarda; esta segunda operación no es conmutativa.[8]​ La solución a esto:

LWW-Registro (Last Write Wins Register)[editar]

Se asocia a cada nuevo valor una marca de tiempo. En la actualización, si la marca de tiempo del nuevo valor es más reciente (más mayor) que la marca de tiempo del actual valor de la réplica, entonces el valor se actualiza.

El siguiente pseudocódigo muestra de una forma sencilla la lógica de este registro y las funciones necesarias para implementarlo:[6]​[8]​ 

Function Consultar()
    return valor
End Consultar

Function Actualizar(valor_otro, marcaTemporal_otro)
    if (marcaTemporal_otro > marcaTemporal)
        valor <- valor_otro
        marcaTemporal <- marcaTemporal_otro
End Actualizar

La función Consultar devuelve el valor almacenado.

La función actualizar comprueba si la marca temporal del nuevo valor es más reciente que la que posee el valor actual, si es así el valor y la marca de tiempo se actualizan.

Usos en la industria[editar]

Los CRDTs son utilizados en numerosas aplicaciones:[14]​

  • Microsoft utiliza CRDTs en su base de datos Microsoft Azure CosmosDB para resolver conflictos entre distintos valores.[15]​
  • Redis Enterprise los utiliza para replicar la base de datos de distintos centros de datos en distintas localizaciones geográficas.[16]​
  • Netflix utiliza los CRDTs internamente en su sistema de almacenamiento Dynomite.[14]​
  • La base de datos interna de Facebook, Apollo database, soporta almacenamiento CRDT.[17]​
  • PayPal[18]​ y League of Legends[19]​ utilizan CRDTs de forma interna.
  • Los sistemas de navegación GPS TomTom utilizan CRDTs para sincronizar los datos de los usuarios entre múltiples dispositivos.[20]​
  • PeerPad es un editor de texto colaborativo basado en IPFS[21]​ y CRDTs.
  • La aplicación de Notas[22]​ de Apple para iOS utiliza CRDTs[23]​ para la sincronización entre diferentes dispositivos.
  • La aplicación de diseño gráfico Figma[24]​ utiliza CRDTs para hacer posible su funcionalidad colaborativa.[25]​

Referencias[editar]

  1. ↑ Shapiro, Marc; Preguiça, Nuno; Baquero, Carlos; Zawirski, Marek (2011). «Conflict-Free Replicated Data Types». En Défago, Xavier, ed. Stabilization, Safety, and Security of Distributed Systems. Lecture Notes in Computer Science (en inglés) (Springer): 386-400. ISBN 978-3-642-24550-3. doi:10.1007/978-3-642-24550-3_29. Consultado el 19 de mayo de 2021. 
  2. ↑ a b c Preguiça, Nuno; Baquero, Carlos; Shapiro, Marc (16 de mayo de 2018). «Conflict-free Replicated Data Types (CRDTs)». arXiv:1805.06358 [cs]. doi:10.1007/978-3-319-63962-8\_185-1. Consultado el 20 de mayo de 2021. 
  3. ↑ a b «About CRDTs • Conflict-free Replicated Data Types». Conflict-free Replicated Data Types (en inglés). Consultado el 20 de mayo de 2021. 
  4. ↑ Preguiça, Nuno; Manuel Marquès, Joan; Shapiro, Marc; Leția, Mihai (Jun 2009). «A commutative replicated data type for cooperative editing». 29th IEEE International Conference on Distributed Computing Systems (ICDCS 2009). 
  5. ↑ Letia, Mihai; Preguiça, Nuno; Shapiro, Marc (Junio 2019). «CRDTs: Consistency without concurrency control». Thème COM — Systèmes communicants Projet Regal. 
  6. ↑ a b c d e «ThinkMicroservices.com - Conflict-Free Replicated Data Types». thinkmicroservices.com. Consultado el 20 de mayo de 2021. 
  7. ↑ a b c Shapiro, Marc; Preguiça, Nuno; Baquero, Carlos; Zawirski, Marek (17 Jan 2014). «Conflict-free Replicated Data Types». SSS 2011 - 13th International Symposium Stabilization, Safety, and Security of Distributed Systems. 
  8. ↑ a b c d e f g h i j k l m n ñ o Zagorskii, Anton (5 de diciembre de 2018). «CRDT: Conflict-free Replicated Data Types». Medium (en inglés). Consultado el 20 de mayo de 2021. 
  9. ↑ Baquero, Carlos; Almeida, Paulo Sergio; Shoker, Ali (12 de octubre de 2017). Pure Operation-Based Replicated Data Types (en inglés). Consultado el 20 de mayo de 2021. 
  10. ↑ «An introduction to state-based CRDTs». Bartosz Sypytkowski (en inglés). 18 de diciembre de 2017. Consultado el 20 de mayo de 2021. 
  11. ↑ a b c d e f g h i j k «Consistency in Distributed Systems». mwhittaker.github.io. Consultado el 20 de mayo de 2021. 
  12. ↑ «A CRDT Primer Part II: Convergent CRDTs · An Abstract Plane». jtfmumm.com. Consultado el 20 de mayo de 2021. 
  13. ↑ a b c «CRDT Glossary • Conflict-free Replicated Data Types». Conflict-free Replicated Data Types (en inglés). Consultado el 20 de mayo de 2021. 
  14. ↑ a b «Code • Conflict-free Replicated Data Types». Conflict-free Replicated Data Types (en inglés). Consultado el 20 de mayo de 2021. 
  15. ↑ «Azure Cosmos DB: Pushing the frontier of globally distributed databases». azure.microsoft.com (en inglés). Consultado el 20 de mayo de 2021. 
  16. ↑ «Active-Active Geo-Distribution (CRDTs-Based)». Redis Labs (en inglés estadounidense). Consultado el 20 de mayo de 2021. 
  17. ↑ «Facebook Announces Apollo at QCon NY 2014 - DZone Java». dzone.com (en inglés). Consultado el 20 de mayo de 2021. 
  18. ↑ «CRDTs in Production». InfoQ (en inglés). Consultado el 20 de mayo de 2021. 
  19. ↑ «How League of Legends Scaled Chat to 70 million Players - It takes Lots of minions. - High Scalability -». highscalability.com (en inglés). Consultado el 20 de mayo de 2021. 
  20. ↑ «Practical Data Synchronization with CRDTs (StrangeLoop, 2016)». Speaker Deck (en inglés). Consultado el 20 de mayo de 2021. 
  21. ↑ Labs, Protocol. «IPFS Powers the Distributed Web». IPFS (en inglés estadounidense). Consultado el 20 de mayo de 2021. 
  22. ↑ «Usar Notas en el iPhone, el iPad o el iPod touch». Apple Support. Consultado el 20 de mayo de 2021. 
  23. ↑ «dunhamsteve/notesutils». GitHub (en inglés). Consultado el 20 de mayo de 2021. 
  24. ↑ «Figma». 
  25. ↑ Evan Wallace. «How Figma’s multiplayer technology works». 
Obtenido de «https://es.wikipedia.org/w/index.php?title=CRDT_(Tipos_de_datos_replicados_sin_conflicto)&oldid=154459064»