Post on 11-Jun-2015
description
Universidad Nacional de TrujilloEscuela de Informática
Bases de Datos Paralelas
◦ Introducción◦ Diseño
Se comercializan con éxito Tendencias:
◦ Mayores requisitos transaccionales, y bases de datos de mayor tamaño
◦ Consultas de ayuda a la toma de decisiones, volúmenes de datos mayores a los soportados por un procesador
◦ Procesamiento paralelo de consultas brinda mayor potencia y dimensionabilidad
◦ Microprocesadores a menor precio hacen más común el uso de máquinas paralelas
Existen diferentes arquitecturas de Sistemas Paralelos◦ De memoria compartida◦ De discos compartidos◦ Arquitectura jerárquica
Mejoran la velocidad de procesamiento de E/S Bases de Datos del orden de los Terabytes (10^12 bytes) Tipos de máquinas paralelas
◦ De grano fino: utilizan una gran cantidad de procesadores de capacidad relativamente baja
◦ De grano grueso: utilizan pocos procesadores de gran capacidad
Medidas de rendimiento◦ Productividad: N° de tareas completadas en un determinado
tiempo◦ Tiempo de respuesta: Cantidad de tiempo necesaria para
completarse una única tarea(*) La productividad se puede mejorar realizando un gran numero de pequeñas transacciones en paralelo
Actualmente, máquinas paralelas de grano grueso son más comunes en el mercado (2 – 4 procesadores)
Paralelismo enfocado a:◦ Almacenamiento de datos◦ Procesamiento de consultas
Requisito importante: carga de datos en paralelo SBDP debe considerar, también:
◦ Recuperación en caso de falla en algunos procesadores y discos◦ Reorganización interactiva de datos y cambios de esquemas
Un SBDP mal diseñado dejará de funcionar si cualquier componente falla (disco o procesador)
Máquinas paralelas se diseñan para afrontar fallas de dispositivos◦ Se distribuye carga de trabajo sólo entre los procesadores
funcionales◦ Datos son guardados sólo en réplicas funcionales
SBDP no están disponibles durante la creación de índices, y cambios de esquemas (excepto en Himalaya, Compaq)
Objetivo: Reducir el tiempo necesario para recuperar relaciones del disco
División de información: División horizontal
Estrategias de División◦ Turno Rotario:
i-ésima tupla se envía al Di mod n , donde n: cantidad de discos Provee una distribución homogéneo
◦ División por Asociación: Cada tupla se asocia en términos de los atributos de asociación Función de asociación: fx(tupla) = i, donde i: índice del disco al que será
enviado◦ División por Rangos
Distribuye rangos contiguos de valores Se escoge atributo de la relación como vector de división
Tipos de acceso a datos◦ Exploración de la relación: devuelve la relación completa◦ Consultas concretas: devuelve tuplas con un valor concreto en un
atributo◦ Consultas de rango: devuelve tuplas cuyo valor de atributo se
encuentre dentro de un rango especificado Comparación de técnicas de división
◦ (*) Si el atributo consultado es parte de la función de asociación◦ (**) Si el atributo consultado es parte del atributo de rango
Exploración C. Concreta C. De Rango
Turno Rotatorio Fácil Difícil Difícil
División por Asociación
Fácil Fácil (*) Difícil
División por Rango Fácil Fácil (**) Fácil (**)
Ejecutar paralelamente diferentes consultas o transacciones Tiempo de respuesta de cada transacción no disminuye Mejora: Ejecutar mayor número de transacciones en paralelo
Tiempo de respuesta global disminuye Implementación:
◦ FÁCIL en sistemas paralelos de memoria compartida◦ DIFÍCIL en sistemas paralelos de discos compartidos o sin
compartimiento Necesario: Asegurar que dos procesadores no actualicen
simultáneamente los mismos datos, y que recuperen la información más actual
Problema de Coherencia de Caché◦ Se integra al control de concurrencia◦ Protocolo
Tx bloquean página de disco antes de leer o escribir Tx envía página modificada al disco compartido antes de desbloquear
Ejecución paralela de una consultas en diferentes discos y procesadores
Objetivo: acelerar consultas de ejecución larga Paralelizar consulta Paralelizar operaciones (internas) Árbol de operadores: para evaluar en paralelo las
operaciones sin dependencias entre sí Posibilidades:
◦ Paralelismo en operaciones: haciendo paralela la ejecución de cada una de las operaciones.
◦ Paralelismo entre operaciones: ejecutando en paralelo las diferentes operaciones
Las dos opciones de paralelismo son complementarias La elección de algoritmos para evaluar en paralelo las
consultas depende de la arquitectura de la máquina
Paralelismo de Encauzamiento◦ Encauzamiento: Resultados de operación A son procesadas por
operación B antes de que A termine y devuelva el resultado completo.
◦ Paralelismo + Encauzamiento: ejecución paralela de A y B en procesadores diferentes
◦ Adecuado para un n° pequeño de procesadores, no es fácilmente extensible.
Paralelismo Independiente◦ Expresiones de consultas independientes se ejecutan en
paralelo◦ Tampoco proporciona una alto grado de paralelismo
Ordenación en paralelo◦ Ordenación con división por rangos
Redistribuir la relación como si fuese una división por rangos (sobre carga de E/S de discos y comuniaciones)
Cada procesador ordena localmente las tuplas (paralelismo de datos)
◦ Merge Sort externo paralelo Cada procesador ordena localmente las tuplas Las partes ordenadas de cada procesador se mezclan
Partes ordenadas de cada procesador se dividen en rangos Cada procesador recibe las tuplas de manera ordenada y las mezcla
para obtener una sola parte ordenada Las partes odenadas de cada procesador se concatenan
Reunión paralela◦ Reunión por división
Se muestra la división utilizada en una reunión por división paralela.
Reunión paralela◦ Reunión con fragmentos y réplicas