L i s s a n d r a

El mundo comenzó y terminará en el File System.

Agenda

  • ¿Qué es el TP? ¿Qué no es el TP?
  • Arquitectura del trabajo práctico
  • LFS
  • Memoria
  • Pool de Memorias
  • Kernel

Quienes leyeron el enunciado?

¿Qué es el TP?

¿Qué no es el TP?

  • Una base de datos académica
  • Simularemos características de algunas bases de datos del mercado actual

  • Cassandra
  • Una base de datos productiva
  • Saber/aprender SQL

Arquitectura del TP

Arquitectura del TP

Kernel

Memoria

LFS

REQUEST

Lissandra File System

Persistencia

Cada proceso se construye sobre el anterior

UNIX Epoch (Timestamp)

  • Es el tiempo en milisegundos desde 01/01/1970

Lissandra File System

UNIX Epoch (Timestamp)

¡¡Es más fácil comparar números que fechas!!

Lissandra File System

06/06/2019 00:09:30

06-06-2019 00:09:30.000

06062019000930000

vs

1554503145

Dato

  • ¿Qué es un dato?
  • ¿De qué forma son?

Ejemplos:

TIMESTAMP;KEY;VALUE

126;1;Jinx

679;90;Corki

380;345;Pantheon

150;1;Morgana

Lissandra File System

Tablas

  • Encargado de persistir los datos con los que vamos a trabajar
  • Los datos se organizan en tablas
  • Las tablas tienen metadata

Lissandra File System

Archivos

  • Las tablas estarán guardadas en archivos

Lissandra File System

Problema

¿Qué pasa si queremos consultar una Key sobre la que tenemos muchos Values?

¿Y si en vez de una Key son muchas Key?

Lissandra File System

6;1;F

7;1;G

8;1;H

4;1;D

5;1;E

1;1;A

2;1;B

3;1;C

Particionamiento

  • Como los archivos son muy grandes y pueden haber Keys múltiples veces mejoramos los selects con particionamiento

Lissandra File System

Ejemplo de particionamiento

Suponiendo una tabla con 3 particiones

Lissandra File System

Lissandra

  • Encargado de administrar la API
  • Listado de la API
    • CREATE
    • DROP
    • DESCRIBE
    • SELECT
    • INSERT

Lissandra File System

CREATE

Lissandra File System

LFS

FS

Lissandra

Ayudantes

CREATE TABLE Ayudantes
SC 4 3000

INSERT

Lissandra File System

LFS

FS

Lissandra

764;1;Nay

Ayudantes

INSERT
Ayudantes
1 Nay 764

Lissandra

  • Memtable

¡¡Datos temporales que aún no están persistidos!!

Lissandra File System

Pequeña cache. Para no tener que estar tocando el archivo fisico

Lissandra

  • Dumps

Lissandra File System

Compactación

  • Nos permite eliminar los archivos temporales

  • Comparamos los archivos de las particiones contra todos los temporales

  • Nos quedamos siempre con el último timestamp para cada Key

Lissandra File System

Ejemplo de Compactación

Lissandra File System

SELECT

Lissandra File System

LFS

FS

Lissandra

764;1;Nay

Ayudantes

SELECT Ayudantes 1

Nay

SELECT

Lissandra File System

  • Vamos a tener que comparar las Keys de:
  • Memtable
  • Particiones originales (.bin)
  • Archivos temporales (.tmp)

Problema

Lissandra File System

SELECTs muy lentos, INSERTs rápidos

¿Cómo podemos mejorar los SELECT para que sean más performantes?

Memoria

Cache

Memoria

  • Mejor la performance del sistema (SELECTs)

  • Permite devolver resultados más rápidamente al tenerlos cacheados

Memoria

Memoria

Memoria

SELECT Ayudantes 4

SELECT Ayudantes 4

Resultado: Nay

Resultado: Nay

Resultado: Nay

SELECT Ayudantes 4

Segmentos y páginas

  • Cada tabla será un segmento

  • Cada registro será una página dentro del segmento de la tabla

¡¡TABLA EN FILE SYSTEM -> SEGMENTO EN MEMORIA

REGISTRO EN FILE SYSTEM -> PÁGINA EN MEMORIA!!

Memoria

Memoria (Teoría)

Memoria

Tabla de Páginas

Memoria

API

  • Listado de la API
    • DESCRIBE
    • CREATE
    • DROP
    • INSERT
    • SELECT
    • JOURNAL

Memoria

SELECT

Memoria

INSERT

Ejemplo de Flag de Modificado

Memoria

Problema

¿Qué pasa si realizamos un INSERT sobre Memoria y luego un SELECT sobre File System?

Inconsistencias

Inconsistencias

Inconsistencias

Inconsistencias

Memoria

Consistencia Eventual

LFS

Memoria

SELECT TABLA_A 9

Mochila

Cartuchera

60;9;Lápiz
724;9;Mochila

341;9;Cartuchera

Memoria

Carpeta

110;9;Carpeta

Memoria

¡¡Aquellas páginas cuyo Flag de Modificado esta activado, no pueden ser reemplazadas!!

Memoria

Reemplazos

Memoria

  • ¿Qué es memoria FULL?

  • ¿Cómo lo resolvemos?

  • ¿Cómo se entera el File System de los cambios?

Journaling

Memoria

Pool de memorias

  • Una sola memoria puede resultar en un cuello de botella y el sistema perdería performance

  • Decidimos agregar múltiples memorias

Pool de Memorias

Atención de Request en el LFS

Pool de Memorias

¡¡En paralelo!!

Pool de memorias

  • Cada memoria funciona independientemente

  • Las mismas tablas podrían estar abiertas en distintas memorias

  • Se autoreconocen mediante Gossiping

Pool de Memorias

Ejemplo de gossiping

A

B
C

Seeds

B

C

Seeds

Pool de Memorias

Ejemplo de gossiping

A

B
C

Seeds

B

A

C

Seeds

Pool de Memorias

Ejemplo de gossiping

A

B
C

B

A

C

C

Seeds

Seeds

Seeds

Pool de Memorias

Ejemplo de gossiping

A

B
C

B

A

C

C

A
B

Seeds

Seeds

Seeds

Pool de Memorias

Ejemplo de gossiping

A

B
C

B

A

C

C

A

B

Seeds

Seeds

Seeds

Pool de Memorias

Kernel

Planificación y multiprocesamiento

Kernel

  • Principal punto de entrada al sistema

  • Permite planificar Scripts LQL y enviar requests a las memorias

Kernel

API

  • Listado de la API
    • DESCRIBE
    • CREATE
    • DROP
    • JOURNAL
    • INSERT
    • SELECT
    • RUN
    • ADD

Kernel

Planificador

  • Planificará mediante algoritmo Round Robin
  • Multiprocesamiento

¡¡N estados Exec!!

Kernel

Atención de Request en la Memoria

Kernel

OPCIÓN 1: EN PARALELO

OPCIÓN 2: EN SERIE

Criterios

  • Cada INSERT/SELECT está asociado a una tabla

  • Cada tabla tiene asociada un criterio en su metadata

  • El tipo de consistencia determina el criterio:
    • Strong consistency
    • Strong-Hash consistency
    • Eventual consistency

Kernel

Ejemplo elección de Memoria

Kernel

Metadata de las tablas

  • Hacemos un DESCRIBE global a una memoria y lo guardamos por un tiempo

Kernel

Strong Consistency

SC

LFS

Memoria

Kernel

Strong Hash Consistency

Hash

SHC

LFS

Memoria

(MOD 0)

Memoria

(MOD N)

. . .

Kernel

Eventual Consistency

. . .

EC

LFS

Memoria

Memoria

Random

Kernel

Métricas

  • Cada criterio mantiene métricas

Ejemplos:

  • Write Latency / 30s : 45ms (en los últimos 30s tardó en promedio 456ms en resolver un INSERT)

  • Reads / 30s: 9786 (realizó 9786 SELECT en los últimos 30s)

  • Memory Load(Memoria 1): 30% (el 30% de las operaciones totales las realizó la Memoria 1)

Kernel

Dudas?

Presentacion TP: Lissandra - Google Slides