DEV Community: Pablo Arango Ramirez

Capítulo 3 - Almacenamiento y Acceso a Datos

Pablo Arango Ramirez — Mon, 18 Nov 2024 01:11:16 +0000

En su nivel más fundamental, una base de datos hace dos cosas

Permite almacenar datos
Permite consultar esos datos

Desde las perspectiva de la BD, ¿Cómo podemos almacenar los datos? y, cuando nos consulten, cómo podemos devolver esos datos?

Probablemente usted no va a implementar su propio motor de almacenamiento, pero si va a escoger uno. Por eso debe saber que hace un motor de almacenamiento por debajo
Hay diferencias muy marcadas entre los motores de almacenamiento optimizados para cargas transaccionales vs los optimizados para cargas analíticas

Motores de Almacenamiento - Dos familias (Para sistemas transaccionales)

Estructurados por logs
Orientado a paginación

Las estructuras de datos que soportan las bases de datos modernas

Ejemplo: Funciones db_get() y db_set() que implementan una base de datos muy sencilla

!/bin/bash
db_set () {
echo "$1,$2" >> database
}
db_get () {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Exploratorium"]}

De la misma forma como funciona esta BD, muchas BDs de datos modernas utilizan un log
- log: archivo tipo append-only que es una secuencia de records añadidos al final de una estructura de datos
Escribir datos → Buen desempeño. Insertar datos al final de un archivo es muy eficiente
Consultar datos → Mal desempeño. El costo de consulta es O(n). Si se duplica la cantidad de records en la BD, el tiempo de consulta se duplica también. La solución a esto son los índices.

Índice: estructura de datos adicional derivada de los datos primarios para obtener acceso rápido a los datos.
- Aceleran las consultas de lectura
- Pero, hacen que las escrituras sean más lentas. Esto porque al escribir se debe actualizar el índice.

Trade-off en sistemas de almacenamiento: Índices aceleran las consultas, pero afectan negativamente las escrituras

Por eso es que las BDs no indexan todo de forma predeterminada, eso lo debe hacer el desarrollador porque es el que conoce los patrones de acceso a los datos

Índices

def. Estructura de datos adicional que se deriva de los datos primarios y sirve para facilitar la búsqueda de información en la BD.

Trade-off en los sistemas de almacenamiento
- índices aumentan desempeño de lectura pero
- reducen desempeño de escritura

Tipos de Índices → Las estructuras de datos que soportan las bases de datos modernas

Índices hash → “Hasheé” llaves a valores
Tablas SST → Tablas de cadenas de caracteres ordenadas (sorted string tables). Almacena los datos en disco de forma ordenada
Árboles LSM → Log-structured merge tree
Árboles-B → Divida la BD en bloques de tamaño fijo

Índices Hash
def. Estructura adicional tipo llave-valor donde la llave es el identificador del dato en la estructura primaria y el valor es la ubicación del dato en la tabla

Se basa en la estructura HashMap (*tipo de dato *diccionario** en múltiples lenguajes de programación)
Log + Hash map

Crédito de la imagen: Martin Kleppmann, Designing Data-Intensive Applications, O'Reilly Media, 2017, Capítulo 3.

Cada vez que añade un nuevo dato al log de la BD, también actualiza el Hash Map
Para no quedarse sin espacio en disco, se realiza un proceso de compactación y agrupamiento(merging) para solo almacenar el valor más actualizado de una llave y reducir el espacio en disco
- compactación → Eliminar llaves duplicadas en el log y solo almacenar la última copia
- Agrupamiento (merging) → Juntar varios segmentos en uno solo Crédito de la imagen: Martin Kleppmann, Designing Data-Intensive Applications, O'Reilly Media, 2017, Capítulo 3.

Limitaciones de una tabla Hash

Debe estar en memoria principal → En disco es muy complicado tener un hash map porque es lento. Debe hacer muchas operaciones aleatorias de entrada y salida y es costoso hacer que escale eficientemente.

Tablas SST

def. Tablas de cadenas de caracteres ordenados (sorted string tables)
Formato de almacenamiento en disco donde la secuencia de parejas llave-valor está ordenado con base en la llave.
Características:

Las parejas llave-valor se almacenan en forma ordenada en disco
Cada llave solo puede aparecer una vez, con el valor actualizado Crédito de la imagen: Martin Kleppmann, Designing Data-Intensive Applications, O'Reilly Media, 2017, Capítulo 3.
El proceso de agrupamiento (merging) se encarga de eliminar los valores no actualizados de las llaves

Árboles LSM (Log-structured merge tree):

Usada en Bases de datos NoSQL
Son una cascada de Tablas SST que se integran en segundo plano
“Data is initially written to a memory component (memtable) and then periodically flushed to disk-based components (SSTables).”

Datos ordenados → consultas basadas en rangos eficientes
Escrituras secuenciales a disco → Buen throughput de escritura

Crédito de la imagen: Martin Kleppmann, Designing Data-Intensive Applications, O'Reilly Media, 2017, Capítulo 3.

Usuario hace una operación de escritura
Las escrituras es escriben en memoria principal
1. memtable → Estructura de datos en memoria para almacenar datos recientes
Cuando memtable se llena, se ordenan y se envian a disco (sort and flush)
Al estar en disco después de un tiempo, ocurre un algoritmo de agrupamiento y compactación.
1. merge y compact → Agrupar las SSTables y eliminar valores actualizados o borrados

Básicamente, se tiene una estructura tipo árbol en RAM que recibe las escrituras (Memtable). Cuando la memtable se llena, los datos se envían al disco. En el disco se hace un proceso de segundo plano que agrupa y compacta los segmentos para eliminar valores eliminados y desactualizados.

Nota. DynamoDB, Cassandra, BigTable y RocksDB usan Árboles LSM

Google BigTable fue la tecnología pionera que introdujo los términos SSTable y Memtable

Árboles-B (B-Trees )
El tipo de indice más utilizado y el estándar para las bases de datos relacionales (Y muchas no relacionales). Tipo update-in-place

Filosofía: Dividen la base datos en bloques de tamaño fijo (páginas), tradicionalmente de 4 KB y leen/escriben una página a la vez.

Es un diseño que encaja más con el hardware subyacente porque los discos también se dividen en bloques de tamaño fijo
Cada página se puede identificar utilizando una dirección (como un apuntador en disco, no en memoria). Se utiliza las referencias de disco para construir un árbol de páginas
Cada llave en las “hojas” del B-tree tiene una apuntador a la dirección en disco donde está el bloque que contiene el valor de la llave

Crédito de la imagen: Martin Kleppmann, Designing Data-Intensive Applications, O'Reilly Media, 2017, Capítulo 3.

Son el tipo de estructura de índice más utilizado en bases de datos relacionales. MySQL, Postgres, Oracle y muchas más usan árboles-b para sus indices.

El árbol siempre está balanceado y tiene una profundidad de O(log n)

Casi todas las BDs pueden estar en un B-tree que sea de 3 a 4 niveles de profundidad. Un árbol de 3 niveles, páginas de 4KB y un factor de branching de 500 puede almacenar hasta 265 TB

Explicación Árboles-B

Procesamiento Transaccional vs Analítico

Originalmente, una escritura a una BD representaba una transacción comercial.

Cliente comprando algo
pagarle a un empleado

OLTP → Online transaction processing

Patrones de acceso similares a los de una transacción comercial
- App normalmente consulta un pequeño número de filas con base en un índice (llave)

OLAP → Online analytical processing

Patrones de acceso para el análisis de datos
- Consulta sobre cantidades masivas de filas pero a pocas columnas. Calcula valores agregados (SUM, AVG, COUNT)

Procesamiento transaccional vs analitico

Propiedad	OLTP	OLAP
Patrón de lectura	Pocas filas por consulta, utilizando una llave para acceder al dato.	Valores agregados sobre muchas filas
Patrón de escritura	Acceso aleatorio. Baja latencia de escritura para el input del usuario	Importar datos en lote (ETL) o eventos de stream
Usado por	Usuario final, via app web	Analista interno para Inteligencia de negocios
Que representan los datos	El estado actual de los datos	Historial de eventos que han ocurrido con el tiempo
Tamaño de los datos	GB a TB	TB a PB
En resumen	muchas consultas pequeñas con baja latencia	Pocas consultas grandes

¿El mismo sistema que utilizo para que mis clientes reserven un asiento en el avión es el mismo sistema que utiliza el analista para detectar patrones de compra en los vuelos? NO!
Por eso se crearon dos aproximaciones distintas. Dos tipos de motores de almacenamiento
OLTP → BD que soporta que los clientes reserven un puesto en el avión

Optimizado para procesamiento transaccional
Son sistemas “user facing”. Manejan un volumen masivo de consultas

OLAP → BD que soporta las operaciones de analitica e inteligencia de negocios. Por ejemplo, averiguar cuantos puestos se han vendido en un mes

Optimizado para analítica
Son sistemas “Business-analyst facing”. Manejan poco volumen de consultas pero las consultas son mucho más grandes
Cuando sus consultas necesitan escanear una gran cantidad de filas, los índices de las BDs OLTPs pierden relevancia. Acá es más importante codificar los datos de una forma compacta.

Al principio de los sistemas computacionales, las BDs se utilizaban tanto para procesamiento transaccional como analítico. SQL es flexible en ese aspecto. No obstante, la década de 1980 las compañías dejaron de usar sus sistemas OLTP para analítica y empezaron a hacer consultas de análisis en BDs separadas → Esas bases de datos se conocen como Bodegas de Datos (Data warehouses)

Data Warehousing (Bodegas de datos)

Capítulo 2 - Modelos de Datos y Lenguajes de Consulta

Pablo Arango Ramirez — Tue, 22 Oct 2024 02:50:52 +0000

Crédito de la imagen: Martin Kleppmann, Designing Data-Intensive Applications, O'Reilly Media, 2017, Capítulo 2.

Tipos de modelos de datos

Jerárquico (El modelo inicial) → Desarrollado en los 1950s por IBM. No se adaptaba bien a las relaciones many-to-many. Modelo Jerárquico
Relacional (SQL) → Solución al modelo jerárquico. Poco flexible
Documental → Datos que vienen en documentos autocontenidos (JSON). Poco soporte de relación entre documentos
Modelo de grafos → Nodos y ejes

El Modelo Relacional

Propuesto por Edgar Codd en 1970
Los datos se organizan en relaciones (tablas) donde cada relación es una colección no ordenada de tuplas (filas)
Casos de uso originales
- Procesamiento transaccional → operaciones de movimiento de dinero en un banco, reservas de aerolineas
- Procesamiento analítico en lotes → reportes, payroll, analítica
Sigue el paradigma de schema-on-write (Esquema al escribir)
- El esquema de los datos es explicito y el motor de BD se asegura que todos los datos escritos a la BD sean consistentes con el esquema predefinido.

NoSQL

Surgió con un hashtag de Twitter en el 2009
def. Not ONLY SQL
Sigue el paradigma de schema-on-read (Esquema al leer)
Surgió debido a estos factores:
- Necesidad de mayor escalabilidad que las BDs relacionales.
- Preferencia por software open-source gratis envés de productos de BDs relacionales empresariales.
- Operaciones de consultas especializadas que no están bien soportadas por el modelo relacional.
- Frustración con las restricciones de los esquemas relacionales.
- Necesidad de un modelo más dinámico y expresivo

Problema: Objetos vs Relaciones → Desajuste por Impedancia (Impedance mismatch)

Impedance Mismatch: Problema de incongruencia entre el modelo relacional y los objetos en el código de la aplicación. Es el conjunto de dificultades técnicas y conceptuales que surgen cuando se almacenan objetos de programación en bases de datos con modelos relacionales
- Si los objetos en la app se almacenan en una BD con modelo relacional (SQL), se necesita una capa de traducción entre el código de la app y la modelo de la BD
Solución → Mapeo Objeto-Relacional (ORM: Object-relational mapping)
- Frameworks de ORM
- Reducen el código boilerplate requerido para esa capa de transición
Ejemplos: Apache OpenJPA, SQLAlchemy, TypeORM

Expresiones en distintos Modelos

Perfil de Linkedin
- Modelo Relacional

Martin Kleppmann, Designing Data-Intensive Applications, O'Reilly Media, 2017.

Modelo Documental NoSQL (JSON)

        {
            "user_id": 251,
            "first_name": "pedro",
            "positions": [
                {"job_title": "founder", "organization": "EmpresaA"},
                {"job_title": "ceo", "organization": "EmpresaB"}
            ],
        ...
        }

Con el modelo JSON, la estructura de árbol implícita en el perfil de Linkedin, se vuelve explícita en el modelo de datos

Versiones iniciales de una aplicación pueden encajar bien en un modelo documental JOIN-Free, pero los datos tienen una tendencia a volverse más interconectados a medida que surgen nuevas funcionalidades

En algún punto va a necesitar many-to-many y por ende utilizar joins
Ejemplo Linkedin → Representar la organización donde trabaja la persona como una entidad.

Crédito de la imagen: Martin Kleppmann, Designing Data-Intensive Applications, O'Reilly Media, 2017, Capítulo 2.

Debate: ¿Cómo representar de mejor forma las relaciones de las entidades en una base de datos?

Es una discusión más vieja que los esquemas NoSQL. Viene desde los primeros sistemas de bases de datos computacionales.

Caso: La IMS de IBM utilizaba el modelo jerárquico. Este modelo no soportaba JOINs. En los 60s, los desarrolladores tenían que decidir entre duplicar datos (Normalizar) o resolver manualmente las referencias de un record a otro. IMS de IBM. Este es el mismo problema que tienen los desarrolladores hoy en día con las BDs documentales.

La solución a esto en su entonces fue el modelo relacional de SQL. El modelo relacional permite poner todos los datos al descubierto con una lista de tuplas (tabla). El optimizador de consultas en una BD relacional automáticamente decide que partes de la consulta ejecutar y en qué orden hacerlo.

Estas decisiones ya no las toma un desarrollador
- “Solo se construye un optimizador de consultas una vez. Todas las apps que utilicen la BD se benefician de el”

Las BDs documentales se devolvieron al modelo jerárquico → almacena records embebidos (many-to-one) en el mismo record, no en otra tabla

Cuando se trata de relaciones many-to-many, el modelo documental y el modelo relacional no son muy distintos. En ambos casos, el ítem relacionado se referencia mediante un identificador único. Este identificador se utiliza como llave foránea en el otro ítem en el modelo relacional. En el modelo documental se usa como referencia a otro documento.

Modelo Relacional vs Modelo Documental

Documental
- Flexibilidad de esquema
- Mejor localidad de datos → Capacidad para mover computo (objetos) a datos almacenados
- Poco soporte de JOINS
Relacional
- Buen soporte de joins
- Buen soporte de relaciones many-to-one y many-to-many
- Poca flexibilidad de esquema

¿Convergencia entre el modelo relacional y documental?

Postgres ya soporta documentos JSON como tipo de datos desde la versión 9. Documentación Postgres
Hay drivers de Mongo que automáticamente resuelven las referencias externas de documentos. Resuelve el problema desde el lado del cliente.

Parece ser que las BDs relacionales y documentales se están volviendo cada vez más parecidas. Esto es algo bueno porque los modelos de datos se complementan entre sí. Si una BD soporta datos que son document-like y también soporta consultas relacionales, las aplicaciones pueden utilizar la combinación de ambas funcionalidades que mejor se ajuste a sus necesidades.

Regla de pulgar:
Use documentales cuando

Tiene datos con relaciones one-to-many.
Necesita que un árbol de datos embebidos se cargue en la aplicación desde el inicio.
Estructura de datos tipo documento.

Use relacionales cuando

Necesita muy buen soporte de joins
Tiene relaciones many-to-many

Lenguajes de Consulta

Dos tipos de lenguajes: Declarativo e Imperativo

Declarativo → SQL
- Le digo a la máquina que datos y transformaciones quiero realizar frente a los datos, pero no le digo como realizar la consulta
```
SELECT * FROM animals WHERE family = "sharks"
```

Imperativo → Lenguajes de programación (Java, python, JS)

Le digo a la máquina, como ejecutar la consulta

function getSharks(){
    var sharks = [];
    for (var i=0; i<animals.length; i++){
        if(animals[i].family === "sharks"){
            sharks.push(animals[i]);
        }
    }
return sharks;
}

La misma consulta se puede expresar de forma genérica con algebra relacional: sharks = σ_family="Sharks" (animals)

SQL Provee mejor soporte para algunos tipos de consultas

Consultas tipo Map Reduce (Documentales) → Ej: Obtener número de tiburones por mes
SQL

SELECT date_trunc('month', observation_timestamp) AS observation_month, 1
                   sum(num_animals) AS total_animals
            FROM observations
            WHERE family = 'Sharks'
            GROUP BY observation_month;

Documental (Mongo)

db.observations.mapReduce(
                function map() { 2
                    var year  = this.observationTimestamp.getFullYear();
                    var month = this.observationTimestamp.getMonth() + 1;
                    emit(year + "-" + month, this.numAnimals); 3
                },
                function reduce(key, values) { 4
                    return Array.sum(values); 5
                },
                {
                    query: { family: "Sharks" }, 1
                    out: "monthlySharkReport" 6
                }
            );

Modelo de Grafos

def. Base de datos que almacena los datos como relaciones entre nodos conectados por ejes

Imagen: https://www.larkinfolab.nl/partners/neo4j/

Ejemplo: Representar el matrimonio de dos personas

Estructura→ ejemplo Neo4J

Cada vertice (Nodo) consiste de
- ID
- Ejes hacia afuera
- Ejes hacia adentro
- propiedades llave-valor
Cada eje consiste de
- Id
- Vertice origen
- Vertice destino
- etiqueta
- Propiedades llave - valor

Los grafos son muy buenos para la evolucionabilidad del sistema. Un grafo se puede extender fácilmente para acomodar cambios en las estructuras de datos de la app.

Ejemplo de lenguaje para BDs de grafos → Cypher (Lenguaje de consultas utilizado en Neo4J)
Ejemplo: Insertar el hecho que Idaho queda en USA y que USA queda en América del norte. Insertar que Lucy nació en Idaho

        CREATE
        (NAmerica:Location {name: 'north america', type: 'continent'}),
        (USA:Location {name:'united states', type: 'country'}),
        (Idaho:Location {name: 'idaho', type 'state'}),
        (Lucy: Person {name:'Lucy'}),
        (Idaho) -[:WITHIN] -> (USA) -[:WITHIN] -> (NAmerica)
        (Lucy) -[:BORN_IN] -> (Idaho)

Este modelo permite realizar consultas muy complejas con una sintaxis sencilla.
Ejemplo: Encuentre los nombres de las personas que emigraron de USA a Europa

MATCH
  (person) -[:BORN_IN]->  () -[:WITHIN*0..]-> (us:Location {name:'United States'}),
  (person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (eu:Location {name:'Europe'})
RETURN person.name
    //[:WITHIN*0..] -> follow a within edge, zero or more times

Encuentra todos los vertices (personas) que

Tengan un born_in eje a un vertice. Desde ese vértice siga una cadena ejes WITHINs hasta que llegue a una ubicación que sea USA.
Ese mismo vertice (persona) tenga un eje lives_in que lleve a un vertices que pertenezca a Europa.

Si fuera a hacer la misma consulta en SQL, sería algo asi

-- in_usa es el set de vértices de todas las ubicaciones en USA
in_usa(vertex_id) AS (
                      SELECT vertex_id FROM vertices WHERE properties->>'name' = 'United States' 1
                    UNION
                      SELECT edges.tail_vertex FROM edges 2
                        JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
                        WHERE edges.label = 'within'
                  ),

-- in_europe es el set de vèrtices de todas las ubicaciones en Europa
                  in_europe(vertex_id) AS (
                      SELECT vertex_id FROM vertices WHERE properties->>'name' = 'Europe' 3
                    UNION
                      SELECT edges.tail_vertex FROM edges
                        JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
                        WHERE edges.label = 'within'
                  ),

-- born_in_usa es el set de vértices de todas las personas que nacieron en USA
                  born_in_usa(vertex_id) AS ( 4
                    SELECT edges.tail_vertex FROM edges
                      JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
                      WHERE edges.label = 'born_in'
                  ),

 -- lives_in_europe es el set de todas las personas que viven en Europa
                  lives_in_europe(vertex_id) AS ( 5
                    SELECT edges.tail_vertex FROM edges
                      JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
                      WHERE edges.label = 'lives_in'
                  )

SELECT vertices.properties->>'name'
                FROM vertices
                -- join para encontrar a las personas que nacieron en USA y viven en Europa
                JOIN born_in_usa     ON vertices.vertex_id = born_in_usa.vertex_id 6
                JOIN lives_in_europe ON vertices.vertex_id = lives_in_europe.vertex_id;

Triple store & SPARQL → Almacenar toda la información en forma de sentencias de tres partes

Sujeto
Predicato
Objeto
ejemplo: Juan Gustan bananos

Modelo “Lucy vive en Londres”

_:lucy     a       :Person.
_:lucy     :name   "Lucy".
_:lucy     :bornIn _:idaho.
_:idaho    a       :Location.
_:idaho    :name   "Idaho".
_:idaho    :type   "state".
_:idaho    :within _:usa.
_:usa      a       :Location.
_:usa      :name   "United States".
_:usa      :type   "country".
_:usa      :within _:namerica.
_:namerica a       :Location.
_:namerica :name   "North America".
_:namerica :type   "continent".

Nota. → La web3 (web semantica) se basa en ese modelo
https://www.programstrategyhq.com/post/web3-meaning-explained

Capítulo 9 - Consistencia y Consenso

Pablo Arango Ramirez — Tue, 15 Oct 2024 01:54:37 +0000

Capítulo 9 - Consistencia y Consenso

“Is it better to be alive and wrong or right and dead” Jay Kreps

Consistencia y consenso → Algoritmos y protocolos para construir sistema distribudios tolerantes a fallas

Se asume que todos los problemas que pueden ocurrir en un sistema distirbuido van a ocurrir
- Paquetes perdidos, reordenados o duplicados
- Demoras arbitrarias en la red
- Relojes desincronizados
- Puasas de nodos
- Nodos que se caen
La mejor forma para construir sistemas distribuidos tolerantes a fallas es mediante abstracciones de proposito general con garantias utiles.
Consenso
- def. Garantía de que todos los nodos del sistema van a estar de acuerdo en algo

Garantías de Consistencia

Aislamiento de transacciones
- Serializabilidad → prevenir condiciones de carrera
Consistencia distribuida
- Linealizabilidad → Coordinar el estado de las replicas en entornos donde hay demoras de red y fallos de nodos

Linealizabilidad (Consistencia atómica)

La garantía de consistencia más fuerte utlizada comunmente por los sistemas de datos
def. Dar la ilusión de que en el sistema solo hay “Una copia de los datos”
- En un sistema linealizable, todas las operaciones leen la versión más reciente de los datos. Se abstrae el hecho de que los datos están distribuidos, dandole la ilusión a los clientes de que los datos están todos almacenados en el mismo sitio.
- Es una garantía de actualidad
  - El sistema se comporta como si solo existiera una copia de los datos, donde cada operación es atómica. Esto significa que por cada dos operaciones, siempre se puede señalar cual ocurrrió primero.
- https://stackoverflow.com/questions/9762101/what-is-linearizability
Contra-Ejemplo → Sistema No Linealizable
- Bob leé datos de una nodo que no ha sido actualizado. El sistema no se comporta como si solo hubiera una copia de los datos.
Ejemplo - Sistema Linealizable
- Después de que alguna operación de escritura leé el valor actualizado x=1, todas las operaciones que le siguen deben leer el mismo valor.
Linealizabilidad ≠ Serializabilidad
- Serializabilidad es una propiedad de aislamiento de las transacciones → Garantiza que las transacciones se van a comportar como si se hubieran ejecutado serialmente, una detrás de otra
- Linealizabilidad es una propiedad de actualidad en las operaciones de escritura y lectura de un registro de datos. No agrupa las operaciones en transacciones, por eso no previene problemas como las lecturas o escrituras sesgadas.
Casos de uso para usar Linealizabilidad
- Candados distribuidos → escoger un nodo para que sea el lider
  - Todos los nodos deben estar de acuerdo en quien es el lider
- Restricciones y univocidad → Requerimiento para tener un valor único y actualizado donde todos los nodos deben estar de acuerdo
  - Nombres de usuarios unicos
  - No balances negativos
  - No personas reservando el mismo asiento
Implementación de sistemas linealizables
- Replicación un solo lider → Linealizable
- Replicación multilider → No linealizable
  - Varios lideres se deben sincronizar de forma asíncrona
- Sin lider (Leaderless) → No linealizale
  - La penalidad de linealizarlo es muy alta

El Costo de Linealizar → Teorema CAP

Caso: Cuando hay una interrupción de red, se debe escoger entre linealizabilidad (consistencia) o disponibilidad. Si los nodos de un sistema no se pueden comunicar y usted quiere que el sistema siga sirviendo tráfico, entonces el sistema no va a ser consistente, pero sí va a estar disponible. Por otro lado, si usted quiere preservar la consistencia, el sistema no va a estar disponible por un tiempo.
- Cuando se construyen sistemas distribuidos en los que los componentes se conectan mediante una red que no es fiable (IP, Ethernet, etc.), se van a tener problemas de red. Trade-off entre disponibilidad y consistencia → Teorema CAP
Teorema CAP → Consistency (Linearizability), Availability, Partition tolerance
- Si una aplicación requiere ser linealizable (consistente) y las réplicas (nodos) se desconectan, se debe esperar a que el error de red se resuelva para poder mantener la consistencia del sistema. Durante ese tiempo, los nodos que no tengan comunicación con el líder no estarán disponibles. Consistencia (Linealizablidad) pero no disponibilidad
- Si una aplicación NO requiere linealizabilidad y las replicas se desconectan del lider, cada nodo puede seguir procesando datos de forma independiente. Durante ese tiempo, el sistema no va a ser consistente entre sus nodos. No consistencia pero si disponibilidad
CAP
- Consistencia → No hay datos desactualizados (desincronizados) entre las replicas del sistema. NUNCA
- Disponibilidad → Los clientes siguen recibiendo respuestas, inclusive si un nodo está fallando
- Tolerancia a particiones (partition tolerance) → Sistema se mantiene funcional asi ocurran errores de red
Nota. El término CAP es un poco engañoso. Las particiones (errores) de red no son algo que usted pueda escoger. Si o si van a ocurrir. La forma indicada de plantear el teorema CAP es asi:

Consistente o disponible **cuando* ocurran particiones de red*

Cuando hayan particiones de red, usted puede escoger entre mantener disponibilidad del sistema o ser consistente. NO AMBOS
Nota. Si bien la linealizabilidad es una garantía util, pocos sistemas en la práctica son 100% linealizables. Esto se debe a que la linealizabilidad es costosa en terminos de desempeño. Soportar linealizabilidad hace que el sistema sea más lento.

Garantías de Orden

Ordenamiento y causalidad → El orden ayuda a preservar la causalidad en un sistema
La causalidad impone un ordenamiento de eventos
- Causa viene antes del efecto
- Ejemplos → Dependencias causales
  - Mensaje se envía antes de que el mensaje se reciba
  - La pregunta viene antes de la respuesta
  - Un nodo lee datos y escribe algo como resultado de la lectura de esos datos
Si un sistema obedece el ordenamiento impuesto por la causalidad de eventos es causalmente consistente
- Ej: Aislamiento con snapshot es causalmente consistente
La linealizabilidad implica causalidad
- Todo sistema linealizable preserva la causalidad de eventos correctamente
Para que un sistema sea causalmente consistente, no necesita ser linealizable. Hay formas de lograrlo que no tienen efectos tan negativos en el desempeño como la linealizabilidad pura.
- Para preservar causalidad, se debe saber que operacion ocurrió antes de cualquier otra operación → orden parcial
- Las operaciones concurrentes se procesan en cualquier orden, pero si una operación ocurre antes de otra, entonces se debe mantener el orden de procesamiento en el resto de replicas. Para lograr esto, se necesita un mecanismo para describir el conocimiento de un nodo en el sistema.

Formas de capturar dependencias causales

Ordenamiento secuencial → numeros secuenciales o timestamps para ordenar eventos
- Estampilla Lamport (Lamport timestamp) → Cada nodo almacena una pareja de (contador, Id Nodo) donde
  - Contador: Número de operaciones que ha procesado
  - Id Nodo: Identificador del nodo que actualizó el objeto
  - Las estampillas de tiempo lamport proveen un ordenamiento consistente con causalidad
    - Si tiene dos timestamps, la que tiene el valor de contador más alto es el timestamp más reciente. Si ambas tienen el mismo valor en el contador, la que tiene el NodeId mayor es la más reciente.
  - IMPORTANTE. Las garantía de ordenamiento no son suficientes para satisfacer todos los requerimientos de consistencia en un sistema distribuido, como asegurarse que solo existan usernames ú*nicos en el sistema. Cuando dos usuarios tratan de crear el mismo *username, escoger la operación con menor timestamp solo funciona en retrospectiva. Un nodo no puede decidir inmediatamente si la petición de un username debe ser aceptada, sin antes saber si otro nodo está procesando la misma petición por otro usuario. Verificar que ningun nodo esté procesando la misma operación no es eficiente. Por eso, **el sistema también debe conocer cuando una operación finaliza para asegurarse que ningun otro nodo pueda realizar la misma operación. Esto se conoce como **broadcast de orden total
    - Broadcast de orden total (total order broadcast)

Broadcast de Orden Total (Total Order Broadcast)

def. Protocolo de comunicación entre nodos de un sistema distribuido para intercambiar mensajes
También se conoce como broadcast atómico
El protocolo dicta que estas propiedades siempre se deben satisfacer para la comunicación entre partes del sistema
- Entrega fiable (reliable delivery) → No hay mensajes perdidos
  - Si un mensaje se entrega a un nodo, se le entrega a todos los nodos
- Entrega de orden total (totally ordered delivery) → Los mensajes se entregan a cada nodo en el mismo orden
Nota. El broadcast de orden total es la forma más adecuada de implementar replicación en una base de datos

Total order broadcast

Broadcast de orden total ≠ Linealizabilidad

	Broadcast atómico	Linealizabilidad
¿Qué es?	Protocolo de comunicación	Modelo de consistencia
Enfoque	La entrega y ordenamiento de mensajes	Apariencia y orden de operaciones
Objetivo	Asegurarse que los mensajes se entreguen de cierta forma	Asegurarse que el sistema entero se comporte como si solo existiera una copia de los datos
Aplicaciones	Mecanismo de bajo nivel para implementar modelos de consistencia como linealizabilidad	Propiedad del sistema como tal

Transacciones Distribuidas y Consenso

Consenso (definición informal) → Hacer que varios nodos estén de acuerdo en algo
- No es algo fácil de implementar
Situaciones donde los nodos de un sistema deben estar de acuerdo
- Escoger un lider → Todos los nodos deben estar de acuerdo en quien es el lider
- commit atómico → Todos los nodos deben estar de acuerdo en el resultado de una transacción
  - Problema: Una transacción puede abortarse en un nodo pero ser exitosa en otro nodo
  - Solución: Commit de dos fases (two-phase commit)

Commit de dos fases (two-phase commit - 2PC)

def. algoritmo para lograr transacciones atómicas que involucran multiples nodos
- Es la forma para implementar commits atómicos en un sistema distribuido
- Sistema de un solo nodo → Un solo dispositivo controla el exito de un commit. El unico requisito es que la operación se efectue en el log en disco
- Sistema de multiples nodos → La operación puede abortarse en un nodo pero ser exitosa en otro nodo
  - Un nodo solo puede hacer commit si está seguro que el resto de nodos también puedne hacer commit
Commit de dos fases → Implementación

Coordinador → Componente adicional que se encarga de administrar las transacciones
Pasos
1. App cliente realiza operación de escritura en varios nodos → Le avisa al coordinador
2. Coordinador empieza la fase 1 → Enviar petición de prepare a los nodos
  1. Petición de prepare: “Eres capaz de hacer commit?”
  2. Coordinador recibe respuesta de los nodos
3. Coordinador empieza la fase 2 → commit o rollback
  1. Si todos los nodos respindieron SI en la fase 1 → commit
  2. Si algun nodo respondió NO en la fase 1 → rollback
Nota. Si un nodo retorna SI en la petición de preparación, debe hacer commit si el coordinador lo solicita en la segunda fase. Si por alguna razón el nodo se cae, el coordinador va a reintentar la operación hasta que se haga commit.
2 promesas aseguran la atomicidad del 2PC
- Si un nodo promete hacer commit en la fase 1, debe si o si hacerlo si el coordinador lo solicita en la fase 2
- Una vez el coordinador toma una decision, es irrevocable

Transacciones Distirbuidas en la Práctica

Dos notas importantes sobre las transacciones distribuidas
1. Ofrecen la garantía de seguridad con el commit de dos fases
2. Causan problemas operacionales e impactan el desempeño
  1. Ej. Las transacciones distribuidas en MySQL son 10 veces más lentas que las transacciones en un solo nodo
  2. Muchos servicios en la nube deciden no implementar transacciones distribuidas debido a sus implicaciones en desempeño
2 tipos de transacciones dsitribudas
- Internas → Mismo sistema de almacenamiento
  - DBs que usan replicación y particionamiento en su configuración estandar soportan transacciones internas entre los nodos de la BD
- Heterogeneas → Multiples sistemas de almacenamiento
  - Dos BDs de vendors distintos (MySQL replication)
  - Brokers de mensajería (Kafka)
Procesameinto de mensajers - Garantía de “Exactly once”
- Las transacciones distribuidas heterogenas permiten que sistemas diversos se integren de formas muy poderosas
  - Ejemplo: Un mensaje de un broker (Kafka, pubsub) pueder ser reconocido como procesado si y solo si la transacción en la BD transaccional fue commited
- Protocolo atómico que soporta las transacciones distribuidas en sistemas heterogeneos → Transacciones XA

Transacciones XA

def. Open XA Transacciones → eXtended Architecture Transactions
- ¿Qué es? Estandar para implementar 2PC en tecnologías heterogeneas, soportado por muchas BDs relacionales y brokers de mensajería
- Basicamente es un API para interactuar con un coordinador de transacciones, permitiendo que multiples recursos transaccionales interactuen entre si para participar en una transacción global intersistemas

MySQL :: MySQL 8.4 Reference Manual :: 15.3.8 XA Transactions

Coordinador → Libreria que se incluye en algun proceso como una aplicación
- Hace seguimiento de los participantes en las transacciones
- Recolecta las respuestas de los participantes despues del prepare
- Utiliza un log en su disco local para llevar registro de los commits y rollbacks
Las transacciones XA resuelven el problema de mantener varios sistemas de datos consistentes entre si, pero también tienen limitantes
- Los coordinadores no replicados son puntos únicos de fallo que pueden causar bloqueos a nivel de sistema
- Muchos coordinadores no soportan alta disponibilidad
- aplicaciones sin estado pueden escalar facilmente, pero añadir un coordinador las hace stateful
- Las transacciones XA no puden detectar deadlocks entre varios sistemas

Consenso Tolerante a Fallas

Consenso → Hacer que multiples nodos estén de acuerdo en algo
- Si muchas personas tratan de reservar el último puesto en un avión, el algoritmo de consenso debe determinar cuál de estas operaciones mutualmente incompatibles es la ganadora.
“The Consensus Problem” → Uno o más nodos puede proponer valores, y el algoritmo de consenso decide alguno de esos valores.
Un algoritmo de consenso debe satisfacer las siguiente propiedades
- Acuerdo uniforme (Uniform agreement ) → Ningún nodo decide de manera diferente al resto de los nodos
- Integridad → Ningún nodo decide dos veces
- Validez → Si un nodo decide el valor V, entonces V fue propuesto por algún otro nodo
- Terminación → Cada nodo que no se bloquea, eventualmente decide algún valor.
Broadcast de orden total y consenso: El broadcast de orden total es lo mismo que rondas repetidas de consenso
- Debido a la propiedad de acuerdo del consenso, todos los nodos deciden entregar los mismos mensajes en el mismo orden
- Debido a la propiedad de integridad, los mensajes no se duplican
- Debido a la propiedad de validez, los mensajes no se corrompen ni se crean de la nada
- Debido a la propiedad de terminación, los mensajes no se pierden
Algunos algoritmos de consenso
- Viewstamped Replication → https://medium.com/@polyglot_factotum/understand-viewstamped-replication-with-rust-automerge-and-tla-7a94e9e4d553
- Raft → https://www.geeksforgeeks.org/raft-consensus-algorithm/
- Zab → https://medium.com/@adityashete009/the-zab-algorithm-502781c54498

Apache Zookeeper

https://zookeeper.apache.org/
def. Herramienta de codigo abierto que provee
- algoritmo de Consenso
- Detección de fallos
- Servicio de membresía
Herramientas como ZooKeeper: Proporcionan consenso y detección de fallos, evitando la necesidad de desarrollar algoritmos propios.

Para implementar sistemas dsitribuidos
- Muchos sistemas comunes utilizan Zookeeper por debajo
  - Apache Kafka
  - HBase
  - Hadoop Yarn
  - Redis

Resumen

Linealizabilidad → modelo de consistencia con el objetivo de dar la ilusión de que los datos replicados se comporten como si solo existiera una copia de los datos
Causalidad: Ordena eventos según causa y efecto, permite concurrencia y reduce la sobrecarga de coordinación.
Consenso → Hacer que todos los nodos de un sistema estén de acuerdo en algo
- Muchos en la práctica de los sistemas distribuidos se pueden reducir al problema de lograr consenso
- Commit atómico
  - Una BD debe decidir si le hace commit o abort a una transacción distribuida
- Broadcast de orden total
  - Un sistema debe deciri en que orden entregar los mensajes a los nodos
- Restricción de univocidad
  - Cuando varias transacciones concurrentes intentan crear records conflictivos con la misma llave, se debe decidir cuales operaciones permitir y cuales rechazar
- Registros linealizables
Base de datos con un solo líder: Proporciona linealizabilidad pero falla si el líder es inaccesible.
- Opciones para manejar fallos:
  - Esperar la recuperación del líder
  - Conmutación manual por fallos
  - Algoritmo de consenso automático

DEV Community: Pablo Arango Ramirez

Capítulo 3 - Almacenamiento y Acceso a Datos

Las estructuras de datos que soportan las bases de datos modernas

Índices

Procesamiento Transaccional vs Analítico

Data Warehousing (Bodegas de datos)

Capítulo 2 - Modelos de Datos y Lenguajes de Consulta

Lenguajes de Consulta

Modelo de Grafos

Capítulo 9 - Consistencia y Consenso

Capítulo 9 - Consistencia y Consenso

Linealizabilidad (Consistencia atómica)

El Costo de Linealizar → Teorema CAP

Garantías de Orden

Broadcast de Orden Total (Total Order Broadcast)

Transacciones Distribuidas y Consenso

Commit de dos fases (two-phase commit - 2PC*)*

Transacciones Distirbuidas en la Práctica

Transacciones XA

Consenso Tolerante a Fallas

Apache Zookeeper

Resumen

Commit de dos fases (two-phase commit - 2PC)