Modelos CAP y de Consistencia

Los modelos de consistencia definen las garantías que un sistema replicado ofrece sobre los valores que devuelven las lecturas, y el teorema CAP delimita cuáles de esas garantías pueden coexistir con la disponibilidad bajo particiones de red.

Definition

Un modelo de consistencia es un contrato entre un almacén de datos replicado y sus clientes que especifica los resultados permisibles de lecturas y escrituras concurrentes; el teorema CAP establece que, en presencia de una partición de red, un almacén de datos distribuido no puede proporcionar simultáneamente consistencia linealizable y disponibilidad.

Scope

Este tema abarca los modelos formales de consistencia —linealizabilidad, consistencia secuencial, consistencia causal y consistencia eventual— y su ordenación por fuerza; el teorema CAP, su enunciado preciso y su demostración; y refinamientos como PACELC que también consideran el equilibrio entre latencia y consistencia en ausencia de particiones. Proporciona el vocabulario para especificar y comparar las garantías de los sistemas replicados.

Core questions

• ¿Cómo difieren en fuerza la linealizabilidad, la consistencia secuencial, la causal y la eventual?
• ¿Qué prohíbe exactamente el teorema CAP y qué permite?
• ¿Cómo refinan las consideraciones de latencia el compromiso de consistencia cuando no hay partición?

Key theories

Linealizabilidad y consistencia secuencial

La linealizabilidad requiere que cada operación parezca tener efecto atómicamente en algún instante entre su invocación y respuesta, de forma consistente con el tiempo real; la consistencia secuencial elimina el requisito de tiempo real, exigiendo solo un único entrelazado legal que respete el orden de cada proceso.

El teorema CAP

Gilbert y Lynch demostraron que ningún almacén de datos replicado puede garantizar tanto la consistencia linealizable como la disponibilidad cuando la red puede perder mensajes entre réplicas, lo que obliga a una elección durante las particiones.

Refinamiento PACELC

PACELC extiende CAP al señalar que incluso sin una partición, un sistema intercambia latencia por consistencia, por lo que los diseños se caracterizan por su comportamiento tanto durante las particiones como en el funcionamiento normal.

Clinical relevance

Cada base de datos distribuida y servicio de almacenamiento debe declarar un modelo de consistencia, y los compromisos CAP y PACELC explican por qué algunos sistemas priorizan la disponibilidad mientras que otros priorizan la consistencia; comprenderlos es esencial para elegir y operar la infraestructura de datos.

History

Lamport definió la consistencia secuencial en 1979 y Herlihy y Wing formalizaron la linealizabilidad en 1990; Brewer conjeturó el compromiso CAP en 2000, Gilbert y Lynch lo demostraron en 2002, y el replanteamiento PACELC de Abadi en 2012 aclaró que la latencia, y no solo las particiones, impulsa las elecciones de consistencia.

Debates

¿Se malinterpreta a menudo el CAP?

El CAP se resume con frecuencia como 'elegir dos de tres', pero el resultado preciso solo fuerza una elección de consistencia-disponibilidad durante una partición; los críticos argumentan que esta simplificación excesiva oscurece el compromiso más relevante entre latencia y consistencia en el día a día, capturado por PACELC.

Key figures

• Eric Brewer
• Seth Gilbert
• Nancy Lynch
• Maurice Herlihy
• Jeannette Wing
• Leslie Lamport

Seminal works

• gilbert2002
• herlihy1990
• lamport1979

Frequently asked questions

¿Significa CAP que un sistema solo puede tener dos de consistencia, disponibilidad y tolerancia a particiones?

No del todo. Las particiones son un hecho de las redes, no una elección de diseño, por lo que la decisión real es qué hacer durante una partición: sacrificar la consistencia fuerte para mantenerse disponible, o sacrificar la disponibilidad para mantenerse consistente. Cuando no hay partición, un sistema puede ser tanto consistente como disponible.