En la computación distribuida , un tipo de datos replicados sin conflictos ( CRDT ) es una estructura de datos que se puede replicar en múltiples computadoras en una red , donde las réplicas se pueden actualizar de forma independiente y simultánea sin coordinación entre las réplicas, y donde siempre es matemáticamente posible resolver las inconsistencias que puedan surgir. [1] [2] [3] [4] [5] [6] [7] [8]
El concepto CRDT fue definido formalmente en 2011 por Marc Shapiro, Nuno Preguiça, Carlos Baquero y Marek Zawirski. El desarrollo estuvo motivado inicialmente por la edición colaborativa de texto y la informática móvil . Los CRDT también se han utilizado en sistemas de chat en línea , juegos de azar en línea y en la plataforma de distribución de audio SoundCloud . Las bases de datos distribuidas NoSQL Redis , Riak y Cosmos DB tienen tipos de datos CRDT.
Fondo
Las actualizaciones simultáneas de múltiples réplicas de los mismos datos, sin coordinación entre las computadoras que albergan las réplicas, pueden resultar en inconsistencias entre las réplicas, que en el caso general pueden no resolverse. Restaurar la coherencia y la integridad de los datos cuando hay conflictos entre las actualizaciones puede requerir que algunas o todas las actualizaciones se eliminen total o parcialmente.
En consecuencia, gran parte de la informática distribuida se centra en el problema de cómo evitar actualizaciones simultáneas de los datos replicados. Pero otro enfoque posible es la replicación optimista , donde se permite que se realicen todas las actualizaciones simultáneas, con posibles inconsistencias creadas, y los resultados se fusionan o "resuelven" más tarde. En este enfoque, la coherencia entre las réplicas se restablece finalmente mediante "fusiones" de réplicas diferentes. Si bien la replicación optimista podría no funcionar en el caso general, resulta que existe una clase significativa y prácticamente útil de estructuras de datos, los CRDT, donde funciona, donde matemáticamente siempre es posible fusionar o resolver actualizaciones simultáneas en diferentes réplicas de la estructura de datos sin conflictos. Esto hace que los CRDT sean ideales para una replicación optimista.
Como ejemplo, un indicador de evento booleano unidireccional es un CRDT trivial: un bit, con un valor de verdadero o falso. Verdadero significa que algún evento en particular ha ocurrido al menos una vez. Falso significa que el evento no ha ocurrido. Una vez que se establece en verdadero, la bandera no se puede volver a establecer en falso. (Un evento, habiendo ocurrido, no puede dejar de ocurrir). El método de resolución es "true gana": cuando se fusiona una réplica donde la bandera es verdadera (esa réplica ha observado el evento), y otra donde la bandera es falsa (que réplica no ha observado el evento), el resultado resuelto es verdadero: el evento ha sido observado.
Tipos de CRDT
Hay dos enfoques para los CRDT, los cuales pueden proporcionar una gran consistencia eventual : los CRDT basados en operaciones [9] [10] y los CRDT basados en el estado. [11] [12]
Las dos alternativas son teóricamente equivalentes, ya que una puede emular a la otra. [1] Sin embargo, existen diferencias prácticas. Los CRDT basados en el estado a menudo son más simples de diseñar e implementar; su único requisito del sustrato de comunicación es algún tipo de protocolo de chismes . Su inconveniente es que el estado completo de cada CRDT debe transmitirse eventualmente a todas las demás réplicas, lo que puede resultar costoso. Por el contrario, los CRDT basados en operaciones solo transmiten las operaciones de actualización, que normalmente son pequeñas. Sin embargo, los CRDT basados en operaciones requieren garantías del middleware de comunicaciones ; que las operaciones no se descarten ni se dupliquen cuando se transmitan a las otras réplicas y que se entreguen en orden causal . [1]
CRDT basados en operaciones
Los CRDT basados en operaciones también se denominan tipos de datos replicados conmutativos o CmRDT . Las réplicas de CmRDT propagan el estado transmitiendo solo la operación de actualización. Por ejemplo, un CmRDT de un solo entero podría transmitir las operaciones (+10) o (−20). Las réplicas reciben las actualizaciones y las aplican localmente. Las operaciones son conmutativas . Sin embargo, no son necesariamente idempotentes . Por lo tanto, la infraestructura de comunicaciones debe garantizar que todas las operaciones de una réplica se entreguen a las otras réplicas, sin duplicaciones, pero en cualquier orden.
Los CRDT puramente basados en operaciones [10] son una variante de los CRDT basados en operaciones que reducen el tamaño de los metadatos.
CRDT basados en el estado
Los CRDT basados en estado se denominan tipos de datos replicados convergentes o CvRDT . A diferencia de los CmRDT, los CvRDT envían su estado local completo a otras réplicas, donde los estados se fusionan mediante una función que debe ser conmutativa , asociativa e idempotente . La función de combinación proporciona una combinación para cualquier par de estados de réplica, por lo que el conjunto de todos los estados forma una semirrejilla . La función de actualización debe aumentar monótonamente el estado interno, de acuerdo con las mismas reglas de orden parcial que la semirrejilla.
Los CRDT del estado delta [12] [13] (o simplemente los CRDT delta) son CRDT optimizados basados en el estado en los que solo se difunden los cambios aplicados recientemente a un estado en lugar de todo el estado.
Comparación
Si bien los CmRDT imponen más requisitos al protocolo para transmitir operaciones entre réplicas, usan menos ancho de banda que los CvRDT cuando el número de transacciones es pequeño en comparación con el tamaño del estado interno. Sin embargo, dado que la función de combinación CvRDT es asociativa, la combinación con el estado de algunas réplicas produce todas las actualizaciones anteriores de esa réplica. Los protocolos de chismes funcionan bien para propagar el estado de CvRDT a otras réplicas al tiempo que reducen el uso de la red y manejan los cambios de topología.
Se conocen algunos límites inferiores [14] sobre la complejidad del almacenamiento de los CRDT basados en estados.
CRDT conocidos
G-Counter (contador solo para cultivo)
entero de carga útil [n] P inicial [0,0, ..., 0]incremento de
actualización () deje g = myId () P [g]: = P [g] + 1valor de
consulta (): entero v sea v = Σ i P [i]comparar (X, Y): booleano b sea b = (∀i ∈ [0, n - 1]: XP [i] ≤ YP [i])fusionar (X, Y): carga útil Z sea ∀i ∈ [0, n - 1]: ZP [i] = max (XP [i], YP [i])
Este CvRDT implementa un contador para un grupo de n nodos. A cada nodo del clúster se le asigna un ID de 0 a n - 1, que se recupera con una llamada a myId (). Por lo tanto, a cada nodo se le asigna su propia ranura en la matriz P , que incrementa localmente. Las actualizaciones se propagan en el fondo, y se fusionaron tomando el máximo () de todos los elementos de P . La función de comparación se incluye para ilustrar un orden parcial de los estados. La función de fusión es conmutativa, asociativa e idempotente. La función de actualización aumenta monótonamente el estado interno de acuerdo con la función de comparación. Por lo tanto, este es un CvRDT correctamente definido y proporcionará una gran consistencia eventual. El equivalente de CmRDT difunde las operaciones de incremento a medida que se reciben. [2]
PN-Counter (contador positivo-negativo)
payload entero [n] P, entero [n] N inicial [0,0, ..., 0], [0,0, ..., 0]incremento de actualización () deje g = myId () P [g]: = P [g] + 1actualizar decremento () deje g = myId () N [g]: = N [g] + 1valor de consulta (): entero v sea v = Σ i P [i] - Σ i N [i]comparar (X, Y): booleano b sea b = (∀i ∈ [0, n - 1]: XP [i] ≤ YP [i] ∧ ∀i ∈ [0, n - 1]: XN [i] ≤ YN [i])fusionar (X, Y): carga útil Z sea ∀i ∈ [0, n - 1]: ZP [i] = max (XP [i], YP [i]) sea ∀i ∈ [0, n - 1]: ZN [i] = max (XN [i], YN [i])
Una estrategia común en el desarrollo de CRDT es combinar varios CRDT para hacer un CRDT más complejo. En este caso, se combinan dos contadores G para crear un tipo de datos que admita operaciones de incremento y decremento. El contador G "P" cuenta los incrementos; y el contador G "N" disminuye. El valor del PN-Counter es el valor del contador P menos el valor del contador N. La combinación se maneja dejando que el contador P combinado sea la combinación de los dos contadores P G, y de manera similar para los contadores N. Tenga en cuenta que el estado interno del CRDT debe aumentar de forma monótona, aunque su estado externo, tal como se expone a través de la consulta, puede volver a los valores anteriores. [2]
G-Set (conjunto solo para cultivo)
conjunto de carga útil A inicial ∅actualizar agregar (elemento e) A: = A ∪ {e}búsqueda de consulta (elemento e): booleano b sea b = (e ∈ A)comparar (S, T): booleano b sea b = (SA ⊆ TA)fusionar (S, T): carga útil U sea UA = SA ∪ TA
El G-Set (conjunto de solo crecimiento) es un conjunto que solo permite adiciones. Un elemento, una vez agregado, no se puede eliminar. La fusión de dos G-Sets es su unión. [2]
Conjunto 2P (conjunto bifásico)
conjunto de carga útil A, conjunto R inicial ∅, ∅búsqueda de consulta (elemento e): booleano b sea b = (e ∈ A ∧ e ∉ R)actualizar agregar (elemento e) A: = A ∪ {e}actualizar eliminar (elemento e) búsqueda previa (e) R: = R ∪ {e}comparar (S, T): booleano b sea b = (SA ⊆ TA ∧ SR ⊆ TR)fusionar (S, T): carga útil U sea UA = SA ∪ TA sea UR = SR ∪ TR
Se combinan dos conjuntos G (conjuntos de solo crecimiento) para crear el conjunto 2P. Con la adición de un conjunto de eliminación (llamado conjunto de "lápida"), se pueden agregar y eliminar elementos. Una vez eliminado, un elemento no se puede volver a agregar; es decir, una vez que un elemento e está en el conjunto de lápidas, la consulta nunca volverá a devolver True para ese elemento. El conjunto 2P usa la semántica "remove-wins", por lo que remove ( e ) tiene prioridad sobre add ( e ). [2]
Conjunto de elementos LWW (Conjunto de elementos de última escritura ganada)
LWW-Element-Set es similar a 2P-Set en que consta de un "conjunto de adición" y un "conjunto de eliminación", con una marca de tiempo para cada elemento. Los elementos se agregan a un LWW-Element-Set insertando el elemento en el conjunto de complementos, con una marca de tiempo. Los elementos se eliminan del LWW-Element-Set al agregarlos al conjunto de eliminación, nuevamente con una marca de tiempo. Un elemento es miembro del LWW-Element-Set si está en el conjunto de complementos, y no en el conjunto de eliminación, o en el conjunto de eliminación, pero con una marca de tiempo anterior a la última marca de tiempo en el conjunto de adición. Fusionar dos réplicas del LWW-Element-Set consiste en tomar la unión de los conjuntos de adición y la unión de los conjuntos de eliminación. Cuando las marcas de tiempo son iguales, entra en juego el "sesgo" del LWW-Element-Set. Un conjunto de elementos LWW puede estar sesgado hacia adiciones o eliminaciones. La ventaja de LWW-Element-Set sobre 2P-Set es que, a diferencia de 2P-Set, LWW-Element-Set permite reinsertar un elemento después de haber sido eliminado. [2]
OR-Set (Observado-Eliminar conjunto)
OR-Set se parece a LWW-Element-Set, pero usa etiquetas únicas en lugar de marcas de tiempo. Para cada elemento del conjunto, se mantiene una lista de etiquetas de adición y una lista de etiquetas de eliminación. Un elemento se inserta en el OR-Set al generar una nueva etiqueta única y agregarla a la lista de agregar etiquetas para el elemento. Los elementos se eliminan del OR-Set al agregar todas las etiquetas en la lista de agregar etiquetas del elemento a la lista de eliminar etiquetas (lápida) del elemento. Para fusionar dos OR-Sets, para cada elemento, deje que su lista de agregar etiquetas sea la unión de las dos listas de agregar etiquetas, y de la misma manera para las dos listas de quitar etiquetas. Un elemento es miembro del conjunto si y solo si la lista de agregar etiquetas menos la lista de quitar etiquetas no está vacía. [2] Es posible una optimización que elimina la necesidad de mantener un conjunto de lápidas; esto evita el crecimiento potencialmente ilimitado del conjunto de lápidas. La optimización se logra manteniendo un vector de marcas de tiempo para cada réplica. [15]
CRDT de secuencia
Se puede utilizar un CRDT de secuencia, lista o conjunto ordenado para crear un editor colaborativo en tiempo real , como alternativa a la transformación operativa (OT).
Algunas CRDT de secuencia conocidas son Treedoc, [5] RGA, [16] Woot, [4] Logoot, [17] y LSEQ. [18] CRATE [19] es un editor descentralizado en tiempo real construido sobre LSEQSplit (una extensión de LSEQ) y ejecutable en una red de navegadores usando WebRTC . LogootSplit [20] se propuso como una extensión de Logoot con el fin de reducir los metadatos para las secuencias CRDT. MUTE [21] [22] es un editor colaborativo en tiempo real peer-to-peer basado en la web que se basa en el algoritmo LogootSplit.
Uso industrial
Nimbus Note es una aplicación colaborativa para tomar notas que utiliza Yjs CRDT para la edición colaborativa. [23]
Redis es una base de datos en memoria distribuida, altamente disponible y escalable que utiliza CRDT para implementar bases de datos distribuidas globalmente basadas y totalmente compatibles con el código abierto de Redis.
SoundCloud de código abierto Roshi , un CRDT de conjunto de elementos LWW para la transmisión de SoundCloud implementado sobre Redis . [24]
Riak es un almacén de datos de valor-clave NoSQL distribuido basado en CRDT. [25] League of Legends usa la implementación de Riak CRDT para su sistema de chat en el juego, que maneja 7.5 millones de usuarios concurrentes y 11,000 mensajes por segundo. [26] Bet365 , almacena cientos de megabytes de datos en la implementación de Riak de OR-Set. [27]
TomTom emplea CRDT para sincronizar los datos de navegación entre los dispositivos de un usuario. [28]
Phoenix , un marco web escrito en Elixir , utiliza CRDT para admitir el intercambio de información de múltiples nodos en tiempo real en la versión 1.2. [29]
Facebook implementa CRDT en su base de datos de "consistencia a escala" de baja latencia de Apollo. [30]
Teletype for Atom emplea CRDT para permitir a los desarrolladores compartir su espacio de trabajo con los miembros del equipo y colaborar en el código en tiempo real. [31]
OrbitDB de Haja Networks utiliza CRDT basados en operaciones en su estructura de datos principal, IPFS-Log. [32]
Apple implementa CRDT en la aplicación Notes para sincronizar ediciones sin conexión entre varios dispositivos. [33]
Referencias
- ^ a b c Shapiro, Marc; Preguiça, Nuno; Baquero, Carlos; Zawirski, Marek (2011). "Tipos de datos replicados sin conflictos". Estabilización, seguridad y protección de sistemas distribuidos (PDF) . Apuntes de conferencias en Ciencias de la Computación. 6976 . Grenoble, Francia: Springer Berlin Heidelberg. págs. 386–400. doi : 10.1007 / 978-3-642-24550-3_29 . ISBN 978-3-642-24549-7.
- ^ a b c d e f g Shapiro, Marc; Preguiça, Nuno; Baquero, Carlos; Zawirski, Marek (13 de enero de 2011). "Un estudio completo de tipos de datos replicados convergentes y conmutativos". Rr-7506 .
- ^ Shapiro, Marc; Preguiça, Nuno (2007). "Diseño de un tipo de datos replicado conmutativo". Repositorio de Investigación en Computación (CoRR) . abs / 0710.1784. arXiv : 0710.1784 . Código Bibliográfico : 2007arXiv0710.1784S .
- ^ a b Oster, Gérald; Urso, Pascal; Molli, Pascal; Imine, Abdessamad (2006). Actas de la conferencia del vigésimo aniversario de 2006 sobre trabajo cooperativo apoyado por computadora - CSCW '06 . pag. 259. CiteSeerX 10.1.1.554.3168 . doi : 10.1145 / 1180875.1180916 . ISBN 978-1595932495.
- ^ a b Letia, Mihai; Preguiça, Nuno; Shapiro, Marc (2009). "CRDT: coherencia sin control de simultaneidad". Repositorio de Investigación en Computación (CoRR) . abs / 0907.0929. arXiv : 0907.0929 . Código Bibliográfico : 2009arXiv0907.0929L .
- ^ Preguiça, Nuno; Marques, Joan Manuel; Shapiro, Marc; Letia, Mihai (junio de 2009), "A Commutative Replicated Data Type for Cooperative Editing", Proc 29th IEEE International Conference on Distributed Computing Systems (PDF) , Montreal, Quebec, Canadá: IEEE Computer Society, págs. 395–403, doi : 10.1109 / ICDCS.2009.20 , ISBN 978-0-7695-3659-0
- ^ Baquero, Carlos; Moura, Francisco (1997), Especificación de tipos de datos abstractos convergentes para la informática móvil autónoma , Universidade do Minho
- ^ Schneider, Fred (diciembre de 1990). "Implementación de servicios tolerantes a fallas utilizando el enfoque de máquina de estado: un tutorial". Encuestas de computación ACM . 22 (4).
- ^ Letia, Mihai; Preguiça, Nuno; Shapiro, Marc (1 de abril de 2010). "Consistencia sin control de simultaneidad en grandes sistemas dinámicos" (PDF) . SIGOPS Oper. Syst. Rev . 44 (2): 29–34. doi : 10.1145 / 1773912.1773921 .
- ^ a b Baquero, Carlos; Almeida, Paulo Sérgio; Shoker, Ali (3 de junio de 2014). Magoutis, Kostas; Pietzuch, Peter (eds.). Hacer CRDT basados en operaciones basados en operaciones . Apuntes de conferencias en Ciencias de la Computación. Springer Berlín Heidelberg. págs. 126–140. CiteSeerX 10.1.1.492.8742 . doi : 10.1007 / 978-3-662-43352-2_11 . ISBN 9783662433515.
- ^ Baquero, Carlos; Moura, Francisco (1 de octubre de 1999). "Utilización de características estructurales para funcionamiento autónomo". SIGOPS Oper. Syst. Rev .: 90–96.
- ^ a b Almeida, Paulo Sérgio; Shoker, Ali; Baquero, Carlos (13 de mayo de 2015). Bouajjani, Ahmed; Fauconnier, Hugues (eds.). CRDT basados en estado eficientes por mutación delta . Apuntes de conferencias en Ciencias de la Computación. Springer International Publishing. págs. 62–76. arXiv : 1410.2803 . doi : 10.1007 / 978-3-319-26850-7_5 . ISBN 9783319268491.
- ^ Almeida, Paulo Sérgio; Shoker, Ali; Baquero, Carlos (4 de marzo de 2016). "Tipos de datos replicados del estado delta". Revista de Computación Paralela y Distribuida . 111 : 162-173. arXiv : 1603.01529 . Código bibliográfico : 2016arXiv160301529S . doi : 10.1016 / j.jpdc.2017.08.003 .
- ^ Burckhardt, Sebastian; Gotsman, Alexey; Yang, Hongseok; Zawirski, Marek (23 de enero de 2014). "Tipos de datos replicados: especificación, verificación, optimización". Actas del 41º Simposio ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación . págs. 271-284. doi : 10.1145 / 2535838.2535848 . ISBN 9781450325448.
- ^ Annette Bieniusa, Marek Zawirski, Nuno Preguiça, Marc Shapiro, Carlos Baquero, Valter Balegas, Sérgio Duarte, "An Optimized Conflict-Free Replicated Set" (2012) arXiv : 1210.3368
- ^ Roh, Huyn-Gul; Jeon, Myeongjae; Kim, Jin-Soo; Lee, Joonwon (2011). "Tipos de datos abstractos replicados: bloques de construcción para aplicaciones colaborativas". Revista de Computación Paralela y Distribuida . 71 (2): 354–368. doi : 10.1016 / j.jpdc.2010.12.006 .
- ^ Weiss, Stephane; Urso, Pascal; Molli, Pascal (2010). "Logoot-Undo: Sistema de edición colaborativo distribuido en redes P2P". Transacciones IEEE en sistemas paralelos y distribuidos . 21 (8): 1162-1174. doi : 10.1109 / TPDS.2009.173 . ISSN 1045-9219 .
- ^ Nédelec, Brice; Molli, Pascal; Mostefaoui, Achour; Desmontils, Emmanuel (2013). "LSEQ". LSEQ una estructura adaptativa para secuencias en edición colaborativa distribuida . pag. 37. doi : 10.1145 / 2494266.2494278 . ISBN 9781450317894.
- ^ Nédelec, Brice; Molli, Pascal; Mostefaoui, Achour (2016). "CRATE: escribiendo historias junto con nuestros navegadores". Actas del 25th International Conference Companion en World Wide Web . pag. 231. doi : 10.1145 / 2872518.2890539 . Archivado desde el original el 1 de enero de 2020 . Consultado el 1 de enero de 2020 .
- ^ André, Luc; Martin, Stéphane; Oster, Gérald; Ignat, Claudia-Lavinia (2013). "Apoyo a la granularidad adaptable de los cambios para la edición colaborativa a gran escala". Actas de la Conferencia Internacional sobre Computación Colaborativa: Redes, Aplicaciones y Uso Compartido - CollaborateCom 2013 . págs. 50–59. doi : 10.4108 / icst.collaboratecom.2013.254123 .
- ^ "MUTE" . Equipo de la Costa. 24 de marzo de 2016.
- ^ Nicolás, Matthieu; Elvinger, Victorien; Oster, Gérald; Ignat, Claudia-Lavinia; Charoy, François (2017). "MUTE: un editor colaborativo en tiempo real basado en web de igual a igual". Actas de ECSCW Panels, Demos and Posters 2017 . doi : 10.18420 / ecscw2017_p5 .
- ^ "Acerca de los CRDT" . Consultado el 18 de junio de 2020 .
- ^ Bourgon, Peter (9 de mayo de 2014). "Roshi: un sistema CRDT para eventos con marca de tiempo" . SoundCloud.
- ^ "Presentación de Riak 2.0: tipos de datos, coherencia sólida, búsqueda de texto completo y mucho más" . Basho Technologies, Inc. 29 de octubre de 2013.
- ^ Hoff, Todd (13 de octubre de 2014). "Cómo League of Legends amplió el chat a 70 millones de jugadores: se necesitan muchos esbirros" . Alta escalabilidad .
- ^ Macklin, Dan. "bet365: Por qué bet365 eligió a Riak" . Basho.
- ^ Ivanov, Dmitry. "Desmitificación práctica de CRDT" .
- ^ McCord, Chris. "Lo que hace especial a Phoenix Presence" .
- ^ Mak, Sander. "Facebook anuncia Apollo en QCon NY 2014" .
- ^ "Codifique juntos en tiempo real con Teletype for Atom" . Atom.io. 15 de noviembre de 2017.
- ^ "OrbitDB / ipfs-log en Github" . Consultado el 7 de septiembre de 2018 .
- ^ "Encabezados IOS Objective-C derivados de la introspección en tiempo de ejecución: NST / IOS-Runtime-Headers" . 2019-07-25.
enlaces externos
- Una colección de recursos y artículos sobre CRDT
- "Fuerte coherencia eventual y tipos de datos replicados sin conflictos" (una charla sobre los CRDT) por Marc Shapiro
- Lecturas en tipos de datos replicados sin conflictos por Christopher Meiklejohn
- Teorema de CAP y CRDT: CAP 12 años después. Cómo han cambiado las reglas por Eric Brewer