Designing Data-Intensive Applications : Chapter 7.1

Encontrar el punto medio entre las 2 hipérboles:

• Las aplicaciones de verdad, que tienen datos valiosos, necesitan transaccionalidad para poder funcionar.
• Las transacciones son la antítesis de la escalabilidad, deben ser descartadas para poder obtener performance y alta disponibilidad.

ACID

Las transacciones nos brindan ACID pero las implementaciones de este acrónimo dependen mucho de cada base de datos, el termino es mas marketinero que descriptivo de las funcionalidades que asegura que tiene.

• Atomicity

  Nos referimos a que no se puede partir en partes más chicas, si dentro de una transacción atomica ocurre un error (de red, disco, proceso, etc) en alguna de las tareas y la transacción no puede ser completada, entonces se aborta y la base de datos descarta o revierte cualquier escritura que haya realizado la transacción.

  Esto permite que la aplicación no tenga que conocer ante un error, cuales escrituras fueron impactadas y cuales no. Sin esto además no podría reintentar por temor a que queden datos duplicados o incorrectos.

• Consistency

  En este contexto, significa que la base de datos esta en un estado correcto (desde el punto de vista de una aplicación).

  La idea es que haya ciertas sentencias sobre los datos que sean siempre verdaderas, por ejemplo que en un sistema contable, todos los ingresos y salida de dinero están balanceados. Si una transacción comienza con una base de datos valida según estas sentencias, y cada escritura de la transacción mantiene la validez, entonces podemos estar seguro que al final las sentencias seguirán siendo cumplidas.

  Cabe aclarar que esto no es una propiedad per se de la base de datos sino de la aplicación que la utiliza, es la base de datos la que permite mantener la consistencia a la aplicación a partir de la Atomicity e Isolation.

  Esta letra se agrego para que el acrónimo funcione y no tanto por su importancia.

• Isolation

  La concurrencia es inherente a las bases de datos, están pensadas para ser consumidas por multiples clientes, concurrentes o no a los mismos datos.

  

  Significa que transacciones que son ejecutadas concurrentemente son aisladas una de la otra, permitiendo que cada una corra como si fuera la unica transacción activa de la base de datos

• Durability

  El objetivo de una base de datos es brindar un lugar seguro donde guardar los datos sin miedo a que se pierdan. Durabilidad es el compromiso de que luego del OK de una transacción, todos los datos escritos seran preservados incluso ante caidas del proceso o problemas de hardware.

  En una base de datos de 1 solo nodo esto significa escribirlo a almacenamiento no volátil, como el disco duro o SSD (además de escribirse en el WAL).

  En un contexto de base de datos replicada, se necesita que al menos una cierta cantidad de nodos de por exitosa la operacion.

  Obviamente no hay durabilidad perfecta, si se borran los discos y los respaldos, no hay manera que la base de datos haga algo para evitarlo. Se usa como ejemplo el hecho que los SSD luego de cierta cantidad de semanas (variable según los materiales y la temperatura) van perdiendo datos (cabe aclarar que esto solo ocurre en dispositivos que ya han llegado casi al fin de su vida util).

La necesidad de transacciones multi objeto

Si bien muchas base de datos abandonaron las transacciones de multiples objetos por su dificultad para implementarlas a través de las particiones y sus problemas en escenarios de alta disponibilidad o carga, no hay ningún problema que impida que estas existan en bases de datos distribuidas, además de que hay muchos casos de uso donde escrituras de un solo objeto no son suficientes:

• En un modelo relacional la desnormalizacion de los datos lleva a que haya multiples tablas con claves foráneas que referencian entre ellas. Las transacciones de multiples objetos permiten mantener la validez de estas referencias y que no haya inconsistencias.
• En el modelo documental al no tener joins, es necesario desnormalizar los datos, por lo cual puede ser necesario actualizar varios documentos a la vez.
• Los indices secundarios tambien deben ser actualizados cada vez que cambia un valor, estos son objetos diferentes de los datos o el indice primario.

Serializacion

Se la conoce como el nivel máximo de nivel de aislamiento, garantiza que a pesar de que varias transacciones se ejecuten en paralelo, el resultado final sera el mismo que si hubieran ejecutado una a la vez, serialmente, sin ninguna concurrencia.

¿Porque no se usa siempre serialización si es tan genial? Para entender la razón es necesario ver las implementaciones disponibles y como performance:

• Literalmente ejecutando transacciones en orden serial
• Lockeo en 2 pasos
• Tecnicas de control de concurrencia optimistas como Serializable snapshot isolation

Ejecución Serial

La manera trivial es literalmente ejecutar una transacción a la vez, en orden, a través de un solo hilo como vimos en singular update queue. Automáticamente eliminamos todos los problemas de conflicto entre las transacciones. Si bien suena obvio, esta idea es muy reciente (2007), hasta entonces la concurrencia multi hilo era considerada esencial para una buena performance.

¿Que genero este cambio?

1. La memoria RAM se hizo tan barata que para muchos casos de uso se volvió posible tener todos los datos en memoria. Si toda la información esta en memoria para que la acceda una transacción, puede ejecutar mucho mas rapido que si tuviera que esperar que los datos se carguen desde disco.
2. El modelo OLTP usualmente utiliza transacciones cortas y con pocas operaciones mientras que las consultas analíticas son normalmente son operaciones solo de lectura por lo que pueden correr en un snapshot consistente por fuera del ciclo de ejecución serializado.

Asi es como funcionan HStore y Redis por ejemplo. Si bien un sistema diseñado para un solo hilo de ejecución puede ser a veces mas performante que uno que soporta concurrencia (por evitarse el overhead de coordinación de bloqueos) pero esta limitado a la carga que soporte un solo núcleo del CPU.

Encapsulando transacciones en Store Procedures

Las transacciones se pensaron para acompañar el flujo de actividad de un usuario. Debido a que estos flujos pueden tener duraciones muy largas, no se puede comenzar una transacción al inicio y finalizarla al terminar la sesión del usuario, puesto que esto generaría problemas en el sistema.

En un escenario interactivo, donde la aplicación hace una consulta, lee el resultado, tal vez hace otra consulta dependiendo del resultado de la primera, y asi sucesivamente. Mucho tiempo se gasta en comunicación entre la aplicación y la base de datos, si además forzamos a que no haya concurrencia, la base de datos va a pasar la mayor parte del tiempo esperando la siguiente consulta.

Por esta razón, los sistemas con transacciones seriales de un solo hilo no permiten transacciones interactivas de varias sentencias, sino que se obliga a que la aplicación envíe toda la transacción junta como un Store Procedure. Un ejemplo de como se ven estos 2 enfoques:

Problemas de los store procedures:

• Cada vendedor de base de datos tiene su lenguaje propio para estos, no se han mantenido actualizados en desarrollo de lenguajes de programación de uso general (lo que los hace verse arcaicos) y no tienen el ecosistema de librerias que tienen la mayoria de los lenguajes de programación.
• Es dificil manejar codigo que corre en la base de datos, cosas como debug o control de version se vuelven complejas.
• Las bases de datos son mas sensibles a la performance, una sentencia escrita no del todo bien puede causar muchos mas problemas que el codigo equivalente mal escrito en la aplicacion.

Particionado

Ejecutar todas las transacciones serialmente hace muy simple el control de concurrencia, pero limita el ancho de transacciones a procesar a la velocidad a un solo CPU en una sola maquina.

Para poder escalar a multiples CPU y multiples nodos, se puede particionar los datos, si se encuentra una manera de particionarlos que asegure que cada transacción solo lea y escriba datos en una sola partición, entonces cada particion puede tener su hilo de procesamiento de transacciones independiente del resto de las particiones, permitiendo escalar linealmente con la cantidad de CPU.

Si esto no es posible, entonces es necesaria coordinación de la transacción en multiples particiones, el store procedure deberá realizar bloqueos en todas las particiones para asegurar la serialibilidad de las operaciones. Esto genera una sobrecarga de coordinacion que lo hace extremadamente lento comparado con transacciones de una sola particion. VoltDB declaraba un máximo de 1000 escrituras por segundo en esta modalidad, varios ordenes por debajo de su capacidad en transacciones de una sola particion.

Cuando los datos son en el modelo key-value es fácil el particionado pero si hay multiples indices ya es dificil tener todo en una sola particion.

Resumen de ejecucion serial

• Necesitamos transacciones pequeñas y rápidas para no frenar todas las transacciones
• Estamos limitados a casos de uso donde entre el dataset en memoria (se puede utilizar anti-caching para suplir esto pero genera otros problemas)
• La carga tiene que ser suficientemente baja para que la soporte un solo CPU o sera necesario particionar la información para poder mejorar la performance.
• Transacciones en multiples particiones son posibles pero difíciles de llevar a la practica.

Lockeo en 2 pasos (2PL)

Fue el algoritmo más usado por 30 años en lo que a serializacion se refiere.

Varias transacciones pueden concurrentemente leer el mismo objeto mientras que nadie este escribiéndolo, por ejemplo:

• Si la transacción A ley un objeto y la transacción B quiere escribir en ese objeto, B queda frenada hasta que A haga un commit o aborte (esto asegura que B no cambie el valor del objeto a espaldas de A).
• Si la transacción A escribir en un objeto y la transacción B quiere leerlo, B queda frenada hasta que A haga un commit o aborte (evitando que se lea una version vieja del objeto).

Por lo tanto en 2PL las modificadores no solo bloquean a otros modificadores, sino que tambien bloquean a los lectores de un dato, y viceversa.

Implementación de 2PL

Cada objeto de la base de datos tiene un lock , el cual tiene 2 modos, compartido y exclusivo.

1. Si una transacción quiere leer un objeto, primero toma el lock en modo compartido. Multiples transacciones pueden tener el lock en modo compartido simultáneamente, salvo que una transacción ya lo tenga en modo exclusivo por lo cual deberían esperar.
2. Si una transacción quiere escribir en un objeto, necesita tomar el lock en modo exclusivo. Ninguna otra transacción podrá obtener el lock al mismo tiempo (en ningún modo), por lo cual si ya existe otro, la transacción deberá esperar.
3. Si la transacción hizo una lectura y ahora quiere escribir, debe mejorar su lock compartido a exclusivo. Esto funciona igual que para obtener el lock exclusivo directamente.
4. Luego de obtener el lock, una transacción lo tendrá hasta el final de la misma (commit o abort). Por esto se le llama "2 pasos", el primero para obtener los locks y el segundo para liberarlos.

Dado que hay varios locks en uso, es sencillo que ocurran deadlocks. La base de datos automaticamente los detecta y aborta una de ellas, permitiendo que la otra siga. La transacción abortada debe ser reintentada por la aplicación.

Performance

La razón por lo cual no fue usado después de los años 70, es que su performance es muy baja comparado con aislamiento débil.

Esto se debe a la sobrecarga de adquirir y liberar los locks, además de que se tiene menos concurrencia ya que se evitan situaciones donde pueda haber condiciones de carrera.

La latencia en estos sistemas puede ser bastante inestable, sobre todo si es común el escenario de deadlock, que fuerza a que esa transacción vuelva a realizar todos los pasos de vuelta.

Serializable Snapshot Isolation (SSI)

Si bien las técnicas anteriores no pintan un buen panorama, hay una alternativa bastante prometedora conocida como SSI. Provee serializacion total con minima penalidad de performance comparado con lo visto anteriormente. Es bastante nueva, fue descripta en el 2008 por uno de los fundadores de WiredTiger (el motor de storage de MongoDB).

Varias bases de datos han comenzado a usarlo, desde PostgreSQL en la version 9.1 hasta bases de datos distribuidas como FoundationDB.

Pesimista versus Optimista

El lock en 2 pasos visto anteriormente es un método de control de concurrencia pesimista, se basa en que si algo puede salir mal (por ejemplo con el lock de otro) entonces es mejor esperar hasta que la situación sea segura para continuar con la operación.

La ejecución serial es de una manera pesimista al extremo, es esencialmente equivalente a que cada transacción tenga un lock exclusivo en la bases de datos entera durante el transcurso de la transacción. En este caso se compensa esto con transacciones muy veloces para que solo mantengan el lock un breve periodo de tiempo.

La tecnica de SSI es en cambio optimista, en el sentido de que en vez de bloquear si algo potencialmente peligroso puede pasar, la transacción sigue con la esperanza de que todo salga bien al final. Cuando la transacción va a hacer el commit, si la base de datos detecta que algo malo paso (por ejemplo que se violo la aislacion) y en ese caso la transacción es abortada y debe ser reintentada.

La idea de control de concurrencia optimista no es nueva, sus ventajas y desventajas se han debatido multiples veces.

• Performan mal si hay mucha concurrencia en unos pocos objetos, puesto que esto genera un exceso de transacciones canceladas. Si ademas el sistema esta cerca del máximo de carga, la carga de reintentar las transacciones puede hacer que la performance se degrade.
• Si hay capacidad suficiente, y la distribución de accesos es buena, las técnicas de control de concurrencia optimistas suelen ser performar mejor.
• El problema de varios accesos al mismo objeto puede ser reducido, por ejemplo si varios quieren incrementar un contador, se pueden agrupar todos y aplicarlos juntos, siempre y cuando el contador no sea leído en la misma transacción.

Como el nombre lo sugiere SSI se basa en que las lecturas dentro de una transacción se ejecutan de un snapshot consistente de la base de datos. Sobre este snapshot SSI agrega un algoritmo para detectar conflictos de serializacion entre las escrituras y determinar cuales transacciones hay que abortar.

Decisiones basadas en premisas desactualizadas

Un patron recurrente que se ve a lo largo del capitulo es:

• Una transacción lee un dato de la base de datos
• Examina el resultado de la query
• Decide tomar una acción (escribir en la base de datos) en base al resultado que vio

Sin embargo con un snapshot, el resultado de la consulta original puede no estar actualizado con el momento en que se commite la transacción. Es decir, el hecho que hizo que tomáramos la decision de ejecutar la acción, puede ya no ser cierto al momento del commit.

Para que haya seguridad, la base de datos necesita asumir que cualquier cambio en el resultado de la consulta (la premisa) significa que las escrituras de esa transacción pueden ser invalidas. Esto significa que puede haber una dependencia causal entre las consultas y las escrituras dentro de la transacción. La base de datos debe detectar estas situaciones y abortar las transacciones.

¿Como hace la base de datos para detectar si una consulta puede haber cambiado?

• Detectando lecturas de un objeto de versionado MVCC (multi-version concurrency control) lo que significaría que leimos posteriormente a una escritura no commiteada.
• Detectando escrituras que afecten lecturas previas lo que significaría que hubo una escritura luego de la lectura.

Detectando lecturas a un MVCC

Cuando una transacción lee de un snapshot consistente en una base de datos MVCC, ignora escrituras que hayan ejecutado otras transacciones que no hayan commiteado al momento de generar el snapshot.

Por ejemplo, en la siguiente imagen, la transacción 43 ve Alice con on_call=true porque la transacción 42 (que modifica la marca de on_call) no esta commiteada. Sin embarco, cuando la transacción 43 quiere hacer el commit, la 42 ya hizo su commit. Esto significa que la escritura que fue ignorada cuando se leyó del snapshot, ahora tuvo efecto y genera que la premisa de la transacción 42 ya no es valida.

Para evitar esta anomalía, la base de datos necesita llevar registro cuando una transacción ignora las escrituras de otras transacciones debido a las reglas de visibilidad de MVCC. Cuando una transacciones quiere hacer un commit, la base de datos chequea de la lista de escrituras ignoradas, si alguna fue commiteada, la transacción se aborta.

¿Porque se espera hasta el momento de commit? Si la transacción 43 fuera de solo lectura, entonces no seria necesario abortarla porque no habría riesgos, y cuando la transacción 43 hace su lectura, la base de datos no sabe aun si la transacción va a hacer una escritura en el futuro. Además la transacción 42 puede ser aun abortada o seguir sin commitear cuando la 43 solicite el commit, lo que haría que el snapshot sea valido.

Detectando escrituras que afectan lecturas previas

En el contexto de lock en 2 pasos, se hablo de bloquear un rango de de indices, lo que permite que la base de datos bloque el acceso de todas las filas que cumplan cierto filtro de búsqueda, como por ejemplo WHERE shift_id = 1234. Podemos utilizar una técnica similar excepto que SSI al bloquear no bloquea otras transacciones.

En el ejemplo anterior, las 2 transacciones buscan por doctores de guardia en el turno 1234. Si hubiera un indice en shift_id, la base de datos puede usar el valor 1234 del indice para registrar que las transacciones 42 y 43 leyeron este dato. Esta información solo tiene que ser guardada durante la vida de la transacción.

Cuando una transacción escribe a la base de datos, debe buscar en el indice por cualquier transacción que haya leído recientemente la data afectada. Este proceso es similar a adquirir un lock de escritura en un rango de claves afectado, pero en vez de bloquear hasta que todos los lectores hayan hecho commit, el lock funciona como trampa, solo notifica a las transacciones que los datos que leyeron pueden ya no ser validos.

La transacciones 43 notifica a la 42 que su lectura anterior esta desactualizada, y viceversa. La transacción 42 es la primera en hacer commit y es exitosa, si bien la escritura de la transacción 43 afecta a la 42, la 43 no ha hecho commit aun, por lo cual su escriefectuar no ha tenido efecto. Sin embarco cuando la transacción 43 quiere hacer commit, la escritura de 42 que genero el conflicto ya esta commiteada, por lo cual 43 debe abortar.

Performance en SSI

Como siempre, el diablo esta en los detalles, y son estos los que afectan que tan bien funciona el algoritmo en la practica.

• Según la granularidad con la que llevamos el trackeo de escrituras y lecturas.
  • A mayor granularidad se puede ser mas preciso con que transacciones necesitamos abortar pero se genera una sobrecarga significativa por llevar el trackeo.
  • A menor granularidad se es mas rápido pero abortaremos mas transacciones que las estrictamente necesarias.
• En algunos casos, es valido para una transacción leer información que fue sobrescrito por otra transacción, dependiendo en que más haya sucedido, a veces es posible probar que el resultado de la ejecución es sin dudas serializable. PostgreSQL usa esta teoría para reducir la cantidad de transacciones abortadas innecesariamente.
• Para casos de uso con fuerte carga de lecturas, la posibilidad de que las consultas de lectura puedan correr en un snapshot consistente sin necesidad de lock es bastante util.
• Comparado con la ejecución serial, SSI no esta limitado a la capacidad de un solo CPU, FoundationDB por ejemplo distribuye la detección de conflictos de serializacion entre multiples maquinas, permitiendo escalar la capacidad fácilmente.
• Incluso con los datos participados en multiples maquinas, las transacciones pueden leer y escribir datos en multiples particiones mientras mantienen aislamiento serializable.