PDF de programación - Tema 7. Almacenamiento físico

Sistemas de Información II
Tema 7. Almacenamiento
físico

Bibliografía:
Elmasri y Navathe: “Fundamentos de Sistemas de Bases de

Garcia-Molina, Ullman y Widom: “Database systems: the

complete book”. Prentice-Hall (Capítulos 11-13).

Datos”

3ª edición, 2002 (Capítulos 5-6).

Carlos Castillo

UPF – 2008

1

Almacenamiento físico

Objetivo DBMS = almacenar datos
Implementación

Requiere conocer en detalle el
almacenamiento de datos en un computador

2

Medios de almacenamiento

Primario

Registros de CPU
Caché de CPU
Memoria volátil

Secundario

Discos magnéticos
Discos ópticos

Terciario

Cinta y bancos de cinta

3

Jerarquía de memoria

Cinta

Disco óptico

Disco magnético

Memoria RAM

Memoria caché

Más barato (por byte)
Más lento
Persistente

Más costoso (por byte)
Más rápido
Volátil

4

En el caso de una BD

Cinta

Disco óptico

Disco magnético

Memoria RAM

Memoria caché

Respaldos de los datos

Log de transacciones
Datos de las tablas

Optimización de consultas
Copia del esquema

5

Disco y memoria

Disco magnético

Memoria virtual – Sistema de Archivos

Memoria RAM

6

Buffers

Tamaño de página = 4Kb

Páginas de disco

Buffers en memoria

Desde memoria secundaria es imposible leer

físicamente 1 bit

7

Discos magnéticos

8

Disco magnético

(platter)

Metal

Cara del disco

Plástico

9

Velocidad de rotación

Velocidad rotacional es constante
(7k-10k rpm)

La aguja va más rápido en el borde del disco
La densidad de información es menor en el
borde
La tasa de transferencia es igual para todas
las pistas

10

Paquete de discos (ej.: 5-10)

Pista
Track
Cilindro=
Pista en
todos los
discos

Gira completo al mismo tiempo

11

Cabezal lectura/escritura

12

Sectores y clusters

Sectores incluyen gaps, alrededor del 10% del disco
que no está magnetizado y ayuda a encontrar los sectores.
13

http://www.ixora.com.au/notes/io_service_times.htm

14

Tiempo lectura

Latencia

15-45 mseg
Tiempo de búsqueda (mover cabezal)
10-40ms
Tiempo de rotación (esperar disco) 5ms

Transferencia

1-2 mseg por bloque

Tiempo escritura = Tiempo lectura
Tiempo modificación = 2 x Tiempo lectura

15

Fragmentación

Bloques definidos durante el formateo
Se busca localizar contiguamente los
bloques en disco

Estrategia en memoria secundaria:

evitar acceso aleatorio

16

Ejemplo: ordenar en disco

Supuesto: registros en disco

Fichero 'datos.dat'
10.000.000 de registros, cada registro de
1Kb, total 10 Gb de datos
Tenemos solo 1Gb de memoria

¿Qué hacer?

Usar quicksort => acceso aleatorio a disco

17

Ordenar fragmentos

Idea: leer 1Gb de datos a la vez a
memoria

Leer 1.000.000 de registros a la vez
Ordenarlos en memoria usando quicksort
Generar archivos temporales
independientes

sort01.dat ... sort10.dat

¿Y ahora?

No podemos leer sort01.dat y
sort02.dat a la vez y mezclarlos ... cada
uno pesa 1Gb

18

Mezclar fragmentos

Memoria

Disco

01 02 03 04

10

Los primeros 100Kb de cada fichero
elegir mayor valor y grabar a disco

19

Costo en tiempo

Leer cada bloque desde disco, secuencial =
1
Ordenar en memoria = 0

El tiempo que demora eso es mucho menor

Grabar cada bloque a disco, secuencial = 1
Leer la parte superior de cada bloque = 1

No es exactamente secuencial

Escribir a disco, secuencial = 1
Costo tiempo aprox. 4 veces lo que tarda

leer el fichero original

20

Costo en espacio

Espacio original: no se cuenta
Espacio para archivos temporales

1 vez tamaño del original

Espacio para archivo de salida

1 vez tamaño del original
Costo espacio aprox. 2 veces el

tamaño del fichero original
¡20Gb libres para ordenar 10Gb!

Podríamos ahorrar (ej.: borrar el original
una vez que tenemos los temporales) –
aunque es un poco arriesgado

21

Resumen (uso disco)

Leer y escribir en disco es lo más lento

Evitar acceso aleatorio
Usar acceso secuencial

22

Principios de diseño

Utilizar bloques de disco

Unidad mínima de lectura es un bloque

Evitar acceso aleatorio
Leer bloques contiguos

No siempre están presentes ambos
principios

23

Registros

24

Registro (tupla, fila)

Secuencia de campos de distinto tipo
Preguntas

¿Cómo se representa cada campo en disco?
¿Cómo se almacenan varios registros en
bloques?
¿Qué pasa si los registros tienen distinto
tamaño?

Operaciones

Búsqueda – Borrado – Actualización -
Inserción

25

Representación de elementos

de datos

Cada valor de un campo físicamente
será una secuencia de bytes
Strings (cadenas) de ancho fijo
Strings de ancho variable
Fechas
Booleanos
Jerga informal

“Ancho” normalmente se refiere a un campo
“Largo” normalmente se refiere a un registro

26

Strings de tamaño fijo

Tipo en SQL

CHAR(3)
Ejemplo

Códigos de aeropuerto

Codificación, siempre 3 bytes, ni menos
ni más, se usa un símbolo especial
NULL (#, \000)

“CDG”
“MIA”
“LL”
“X”

C D G
M I A
L L #
X # #

27

Strings de tamaño variable

Tipo en SQL

VARCHAR(30)

Ejemplo

Nombres de personas
Codificación 1: Largo

“Joan”

L J O A N

L = log2(largo máximo) bytes representando el
largo. Por eso se usa tanto VARCHAR(255)
Codificación 2: Terminar con símbolo

“Joan”

J O A N #

28

Números

Enteros

Siempre un número fijo de bytes
Utilizar mínimo posible
Con signo/sin signo aumenta rango

Misma representación para enums
Flotantes

Representación independiente del
procesador

29

Fecha y hora

Tipo en SQL
TIMESTAMP

Codificación 1: CHAR(14) YMDhms

“4 de Marzo del 2005”
“10 de Enero del 1988 13:25”
Se utilizan 14 caracteres => 14 bytes

20050304120000

19880110132500

Codificación 2: Unix Time

Número de segundos transcurridos desde
1/1/1970 GMT
Se utiliza 1 entero => 4 bytes
19 de Enero del 2038 a las 3:14 AM

30

Bit

Tipo en SQL

BOOLEAN, BIT

Ejemplo
Género
Estado (activo/inactivo, ocupado/desocupado,
etc.)

Consejo: reservar espacio para más estados
siempre = usar shortint/smallint

Representación
1 byte completo

31

Registros

Esquema físico

Forma de leer el registro de disco

32

Registros de largo fijo

CREATE TABLE persona (
nombre CHAR(30),
dirección CHAR(100),
sexo BOOLEAN,
fnacimiento TIMESTAMP
);

Tamaño mínimo del registro =

30+100+1+4 = 135 bytes

33

Offsets

nombre +0
dirección +30
sexo +130
fnacimiento +131

Problema:

Campos deben comenzar en múltiplo de 4 (u

8), especialmente los numéricos

Registro debe comenzar en múltiplo de 4 (u

8)

34

Offsets alineados

nombre +0 [2 bytes extra]
dirección +32
sexo +132 [3 bytes extra]
fnacimiento +136

Los bytes extra normalmente no son

usados, pues pueden aparecer-
desaparecer al modificar el orden de
los campos

35

Encabezado de registro

Esquema usado (dirección)

Ej.: 2 bytes => 64k tablas distintas

Largo del registro

Ej.: 4 bytes => registros de hasta 2G

Fecha de último acceso
Bloqueo

Ej.: 1 byte (RW, R, Libre)

OID

Campo extra que agregan algunas BD

36

Ejercicio 1

Registro con:

char(15), short int (2 bytes), timestamp,
integer

¿Cuánto espacio ocupa?

Registros comienzan en cualquier posición
Alinear a múltiplos de 4
Alinear a múltiplos de 8

37

Ejercicio 2

Registro con:

double, varchar(17),byte, timestamp

¿Cuánto espacio ocupa?

Registros comienzan en cualquier posición
Alinear a múltiplos de 4
Alinear a múltiplos de 8

38

Ejercicio 3

Registro con:

double, varchar(17),byte, timestamp

Registro requiere encabezado con dos
punteros de 4 bytes y un byte
¿Cuánto espacio ocupa?

Registros comienzan en cualquier posición
Alinear a múltiplos de 4
Alinear a múltiplos de 8

39

Bloques de Registros

Tamaño fijo (ej.: 4Kb)
Varios registros, dependiendo del
tamaño
Encabezado de bloque
Identificador del bloque
Directorio de offsets de los registros en el
bloque

Con espacio extra para crecer

Fechas de último acceso/modificación

40

Bloques ordenados

Cada bloque un conjunto de registros
Si los bloques tienen algún orden:

Reservar espacio en cada bloque
Bloques para overflow
Dividir el bloque y encadenarlos

41

Direccionamiento de bloques
Necesitamos asignar un ID a cada
bloque

Referencias entre bloques (ej.: “bloque
siguiente”)
Mantener tabla de bloques en caché
Indexar por bloques

Opciones

ID con significado => representa una
posición física del registro => “dirección
física”
ID correlativo => simplemente numera
bloques => “dirección lógica”

42

Ejemplos de direccionamiento

físico

Hostname (4 bytes en Ipv4)
Superficie
Cilindro
Pista
Sector
Bloque
Pueden cambiar en el tiempo

=> tabla de direccionamiento lógico a
físico

43

Registros de largo variable

Encabezado de registro contiene largos
Ejemplo

persona(nombre,género,dirección,fnacimient
o)
Encabezado del registro

Largo del registro
Offset de fnacimiento (¡no es necesario!)
Offset de nombre
Offset de dirección

Mejor orden:

Género – Fnacimiento – Nombre - Dirección

44

Registros de largo variable:

ideas para optimizar

Se ponen los campos de ancho fijo
primero
Campos que admiten NULL pueden ser
tratados como un caso especial

En vez del offset, se guarda un NULL

45

Registros grandes

Ejemplo: campo de tipo TEXT
Idea:

Usar varios bloques
En el encabezado del bloque, se guarda un
puntero al siguiente bloque
En el siguiente bloque, se indica que es un
bloque de continuación

46

Registros muy grandes

Ejemplo: campo de tipo BLOB

Imagen
Sonido

Se recupera normalmente completo
Normalmente no se buscan por
contenido
Almacenamiento: en espacio aparte

47

Registros muy grandes:
administración externa

Guardar una URL

Se ahorra transmitir el BLOB a través del
socket usado para la BD
Se ahorra cargar el BLOB en memoria

Requiere: borrado, modificación,
inserción aparte
Podemos hacer más: dividir el BLOB en
varios discos para mejor velocidad
El eterno dilema

Es más eficiente, pero es más difícil de
mantener

48

Modificaciones

Inserción

Registros ordenados => cada registro va a
un bloque específico

Borrado

Lista de espacios libres en el bloque
Marcar registros como no usados =>
fragmentación
Políticas de asignación: first-fit, best-fit

Actualización