Distributed Databases: Basic Concepts II

En el anterior articulo se describían una serie de conceptos básicos sobre las bases de datos distribuidas necesarios para comprender las futuras entregas planeadas en las que desgranar las peculiaridades de cada una de ellas.

Pero antes de meterse en harina, es necesario ahondar un poco mas en estos fundamentos con una segunda entrega dedicada en exclusiva a ello.

CAP Theorem

El teorema CAP define que para cualquier sistema de datos distribuidos en red existe una compensación fundamental entre la consistencia, disponibilidad y tolerancia a la partición. Es decir, no es posible garantizar las tres propiedades de forma simultánea y dado que en los sistemas distribuidos la tolerancia a la partición es inevitable, se debe escoger entre sacrificar la disponibilidad o la consistencia.

Consistency

Propiedad que define que cada lectura debe devolver la escritura más reciente o un error, es decir, garantiza que cada nodo del clúster devuelve la misma escritura más reciente y exitosa.

Aunque existen varios tipos de modelos de consistencia, el teorema de CAP hace referencia a la consistencia secuencial, una modelo fuerte de consistencia.

Este modelo define que el resultado de cualquier ejecución es el mismo que si las operaciones de todos los procesadores se ejecutaran en algún orden secuencial, y las operaciones de cada procesador individual aparecen en esta secuencia en el orden especificado por su programa.

Es decir, si la operación B comenzó después de que la operación A se completase con éxito, entonces la operación B debe ver el sistema en el mismo estado en que se encontraba al finalizar la operación A o un estado más nuevo (pero nunca un estado más antiguo).

Availability

Propiedad que define que cada petición debe recibir una respuesta (sin error), sin la garantía de que contenga la escritura más reciente.

Es decir, todos los nodos disponibles devuelven una respuesta para todas las solicitudes de lectura y escritura en un período de tiempo razonable. La palabra clave aquí es “todos”, ya que no basta con que un conjunto de ellos responda.

Partition tolerance

Propiedad que define que el sistema continúa funcionando a pesar de un número arbitrario de mensajes se pierdan o se retrasen por la red.

Es decir, un sistema tolerante a particiones debe soportar cualquier cantidad de fallos de red siempre y cuando no resulte en un fallo que afecte a toda ella. Para ello, los datos se replican a lo largo de los distintos nodos del cluster de tal forma que permitan afrontar fallos o interrupciones intermitentes en la red.

CAP categories

El teorema de CAP clasifica los sistemas en tres categorías, pero dado que en los sistemas distribuidos la tolerancia de partición no es una opción, los productos deben escoger entre una consistencia o una disponibilidad perfecta:

  • Optar por la consistencia implica no poder siempre responder a la consulta de un cliente, ya que el sistema no puede garantizar la devolución de la escritura más reciente.
  • Optar por la disponibilidad en cambio, implica que, aunque todas las peticiones vayan a ser respondidas, no se garantiza la devolución de la escritura mas reciente para todas ellas.

Dicho esto, los sistemas se clasifican en las siguientes categorías.

CP – Consistent and Partition Tolerant

Sistema consistente y tolerante a la partición en el que la disponibilidad es sacrificada en caso de fallos en la red. Ideal para aquellos casos de uso en los que se requiere una consistencia estricta, como, por ejemplo, cuando en un sistema bancario un cliente realiza un ingreso, debe ser capaz de verlo reflejado de forma instantánea.

AP – Available and Partition Tolerant

Sistema disponible y tolerante a la partición en el no se garantiza una consistencia. Ideal para aquellos casos de uso en los que la consistencia eventual es una opción, como, por ejemplo, un sistema de recomendaciones de un comercio online.

Muchos de los productos que serán analizados en posteriores artículos permiten configurar a que propiedad se le quiere dar mayor importancia, pero siempre sacrificando uno en favor del otro.

Una vez descrito el teorema de CAP, es hora de saldar la deuda contraída en el primer articulo sobre conceptos básicos de las bases distribuida y profundizar en las transacciones ACID.

ACID

ACID es el acrónimo de Atomicity, Consistency, Isolation y Durability, propiedades que garantizan la validez de las transacciones en los sistemas de gestión de bases de datos relacionarles.

Atomicy

Propiedad que garantiza que en caso de que una transacción este compuesta por mas de una operación, se ejecutan todas o ninguna. Es decir, en caso de que alguna de las operaciones falle, el resto también deberán fallar y la base de datos no sufrirá cambio alguno.

Consistency

Propiedad que garantiza que cualquier transacción llevará a la base de datos desde un estado válido a otro también válido, respetando los constraints, cascades, triggers y cualquier combinación de estos.

Comentar que, aunque el concepto de la consistencia hace acto de presencia tanto aquí como en el teorema dé CAP, el significado es totalmente diferente. Puestos a enfrentarlos, lo lógico es comparar la consistencia de CAP con los niveles de aislamiento de ACID, ya que ambos tratan con los valores que las operaciones de lectura pueden ver.

Isolation

Propiedad que garantiza que en caso de que varias transacciones afecten a la misma información de forma concurrente, se ejecuten de forma aislada, independiente y sin generar ningún tipo de error. Dicho de otra forma, determina cómo y cuándo los cambios realizados por una transacción se vuelven visibles para el resto.

En este punto es interesante describir las dos principales estrategias de aislamiento estricto empleadas en los sistemas de gestión de bases de datos:

Serializable ISOLATION

Nivel de aislamiento que permite que las transacciones se ejecuten de manera equivalente a una programación en serie o de forma secuencial.

Para ello, cuando dos transacciones tratan de actualizar lo mismos datos utiliza bloqueos para garantizar que no lo hagan, de tal forma que una transacción debe esperar a que la otra se complete, pudiendo producirse deadlocks.

SNAPSHOT ISOLATION

Nivel de aislamiento que permite que multiples transacciones accedan a los mismos datos sin bloqueos y con la máxima concurrencia.

Para ello, todas las lecturas realizadas en una transacción verán una instantánea (snapshot) coherente de la base de datos y la transacción en sí misma se confirmará con éxito solo si ninguna actualización entra en conflicto con las actualizaciones simultáneas realizadas por las transacciones que se confirmaron desde esa instantánea. De lo contrario, deberá fallar y revertir la transaccion.

Durability

Propiedad que garantiza que una vez realizada una transacción (commit) esta persistirá, aunque el sistema falle.

En resumen, un sistema de gestión de base de datos que opere bajo transacciones ACID garantiza la integridad y seguridad absoluta de los datos evitando lost updates, dirty reads o stale reads. De igual manera, simplifica la gestión de la concurrencia, permitiendo a los desarrolladores tratar cada transacción como si se ejecutara de forma secuencia, incluso en escenarios de concurrencia.

Ahora bien, operar con transacciones ACID sobre sistemas distruibuidos en los que los datos que afectan a una transacción pueden estar desperdigados en distintos nodos no es empresa fácil. Es por ello que las bases de datos SQL distribuidas más modernas se apoyan en el MVCC, entre otros conceptos, para darle solución.

MVCC

Multi-Version Concurrency Control (MVCC) es un mecanismo de control de concurrencia comúnmente utilizado por los sistemas de administración de bases de datos, para proporcionar operaciones concurrentes dentro de la base de datos, sin bloqueos.

Su principal premisa es que, en lugar de actualizar directamente los datos existentes en base de datos, cada actualización crea una nueva versión de estos, de modo que aquellas peticiones de lectura concurrentes aún puedan ver la versión anterior mientras se procesa la transacción de actualización. Como no podía ser de otra forma, esta premisa se ajusta como un guante a una base de datos distribuida en la que las transacciones deben operar sobre datos alojados en distintos nodos del cluster.

En otras palabras, este mecanismo garantiza que:

  • Las escrituras no bloquean las lecturas.
  • Las lecturas no bloquean las escrituras.
  • Las transacciones de solo lectura pueden leer datos confirmados sin adquirir bloqueos.

Dicho esto, no hay una definición o implementación estándar del protocolo MVCC, ya que existen diversas opciones de diseño que impactan directamente en su comportamiento y rendimiento.

A continuación, se describen muy brevemente estas decisiones de diseño, dado que hacerlo en detalle requeriría un articulo en exclusiva y no es el ámbito del presente escrito.

Concurrency Control Protocol

El protocolo es el encargado de determinar si una transacción puede acceder o modificar una versión de fila en particular de la base de datos en tiempo de ejecución, así como de permitir que una transacción confirme (commit) sus modificaciones.

Las principales estrategias son: Timestamp Ordering (MVTO), Optimistic Concurrency Control (MVOCC) y Two-phase Locking (MV2PL).

Version Storage

El almacenamiento de versiones es el encargado de determinar cómo el sistema almacena versiones físicas de los datos y qué información contiene cada una, lo que tiene implicaciones para el “Garbage Collection”. Dado que cada actualización crea una nueva versión de los datos en el sistema, es fundamental determinar dónde y cómo se van a organizar estos datos.

Las principales estrategias son: Append-only Storage, Delta Storage y Time-Travel Storage.

Garbage Collection

El garbage collector es el encargado de realizar una poda periódica de las versiones antiguas de los datos para gestionar el uso y el rendimiento de la memoria.

El proceso de recolección de basura se divide en tres pasos:

  1. Detectar versiones expiradas. Por ejemplo, aquellas creadas por una transacción cancelada o que ya no están visibles para ninguna transacción activa.
  2. Desvincula dichas versiones de las cadenas e índices asociados.
  3. Liberar el espacio de almacenamiento.

Las principales estrategias son: Tuple-level Garbage Collection y Transaction-level Garbage Collection.

Conclusiones

En conclusión, esta segunda entrega acerca de los conceptos básicos de las bases de datos distribuidas ha estado enfocada en describir el ACID, el teorema de CAP así como el MVCC, los cuales resultaran fundamentales para comprender las entregas venideras.

Referencias

Se recomienda encarecidamente leer los siguientes artículos que han servido de base para el escrito:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s