• Author / Uploaded
• Edinson Escobar

Citation preview

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

SISTEMAS DE BASES DE DATOS PARALELAS

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

•

Actualmente los Sistemas Paralelos se están comercializando con éxito por prácticamente todos los fabricantes de BD.

•

Este cambio lo han impulsado las siguientes tendencias: Los requisitos transaccionales de las empresas han aumentado, con el uso creciente de las computadoras. El crecimiento de la WWW y los datos recogidos por los visitantes han producido BD extremadamente grandes en muchas empresas. 

Las empresas utilizan volúmenes crecientes de datos para planificar sus actividades y sus tarifas.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

Las consultas utilizadas para estos fines se denominan consultas de Ayuda a la Toma de Decisiones y las necesidades de datos para las mismas pueden llegar a los terabytes. 

Los sistemas con un único procesador no son capaces de tratar volúmenes de datos tan grandes a la velocidad necesaria.



La naturaleza orientada a conjuntos de las consultas de BD se presta de manera natural a la paralelización.



Varios sistemas comerciales y de investigación han demostrado la potencia y dimensionalidad del procesamiento paralelo de consultas.



Con el abaratamiento de los microprocesadores, las máquinas paralelas se han vuelto comunes y relativamente baratas.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

•

El paralelismo se utiliza para proporcionar aceleración, y las consultas se ejecutan más rápido debido a que se proporcionan más recursos, como procesadores y discos.

•

El paralelismo también se utiliza para proporcionar ampliabilidad, y las cargas de trabajo crecientes se tratan sin aumentar el tiempo de respuesta mediante un aumento en el grado de paralelismo.

PARALELISMO DE E/S •

En su forma más sencilla, el paralelismo de E/S se refiere a la reducción del tiempo necesario para recuperar relaciones del disco dividiéndolas en varios discos.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

•

La forma más frecuente de división de datos en un entorno de BD Paralela es la División Horizontal.

•

En la división horizontal, las tuplas de las relaciones se dividen entre varios grupos, de modo que cada tupla resida en un disco.

TÉCNICAS DE DIVISIÓN •

Se presentan 3 estrategias básicas para la división de datos.

•

Se da por supuesto que hay n discos, D0, D1, …, Dn-1, entre los cuales se van dividir los datos.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

TÉCNICA 1.- TURNO ROTATORIO •

La relación se explora en cualquier orden y la i-ésima tupla se envía al disco numerado D i mod n.

•

El esquema de turno rotatorio asegura una distribución homogénea de las tuplas entre los discos.

•

Cada disco tiene aproximadamente el mismo número de tuplas que los demás.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

TÉCNICA 1.- TURNO ROTATORIO ACCESO • El esquema se adapta perfectamente a las aplicaciones que desean leer secuencialmente la relación completa para cada consulta. •

Con este esquema tanto las consultas concretas como las de rango son difíciles de procesar.

•

Dado que se debe emplear en la búsqueda cada uno de los n discos.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

TÉCNICA 2.- DIVISIÓN POR ASOCIACIÓN •

En esta estrategia de división uno o más atributos del esquema de la relación se designan como atributos de la división.

•

Se escoge una función de asociación cuyo rango sea [0, 1, …, n-1].

•

Cada tupla de la relación original se asocia en términos de los atributos de la división.

•

Si la función de asociación devuelve i, la tupla se ubica en el disco Di.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

TÉCNICA 2.- DIVISIÓN POR ASOCIACIÓN ACCESO •

•

Este esquema se adapta mejor a las consultas concretas basadas en el atributo de división. •

Por ejemplo si se divide una relación en términos del atributo No_Ctrl, se puede responder a la consulta: “Buscar el registro del alumno con número de control = 97120543”.

•

Aplicando la función de división por asociación a “97120543” y buscando luego en ese disco.

Dirigir la consulta a un solo disco ahorra el costo de iniciar una consulta en varios discos.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

TÉCNICA 2.- DIVISIÓN POR ASOCIACIÓN ACCESO •

Este esquema también es útil para las exploraciones secuenciales de la relación completa.

•

Si la función de asociación es una buena función aleatoria y los atributos de división forman una clave de la relación, el número de tuplas en cada uno de los discos será aproximadamente el mismo.

•

Por lo que el tiempo empleado para explorar la relación es aproximadamente 1/n del tiempo necesario para explorar la relación en un sistema de disco único.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

TÉCNICA 2.- DIVISIÓN POR ASOCIACIÓN ACCESO •

El esquema, sin embargo, no se adapta bien a las búsquedas concretas en términos de atributos que no sean de división.

•

Tampoco se adapta bien a las respuestas a consultas de rangos, dado que, generalmente, las funciones de asociación no conservan la proximidad dentro de los rangos.

•

Por lo tanto, hace falta explorar todos los discos para responder a las consultas por rango.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

TÉCNICA 3.- DIVISIÓN POR RANGOS •

Esta estrategia distribuye rangos contiguos de valores de los atributos a cada disco.

•

Se escoge un atributo de división, A, como vector de división.

•

Sea [v0, v1, …, vn-2] el vector de división, tal que, si i < j, entonces vi < vj.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

TÉCNICA 3.- DIVISIÓN POR RANGOS La relación se divide como sigue: •

Consideremos una tupla t tal que t[A] = x.

•

Si x < v0 entonces t se ubica en el disco D0.

•

Si x ≥ vn-2, entonces t se ubica en el disco Dn-1.

•

Si vi ≤ x < vi+1, entonces t se ubica en el disco Di+1. •

Por ejemplo, si tenemos los discos 0, 1, 2 se pueden asignar tuplas con valores menores de 5 al disco 0, entre 5 y 40 al disco 1, y con valores mayores de 40 al disco 2.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

TÉCNICA 3.- DIVISIÓN POR RANGOS ACCESO •

Este esquema se adapta bien a las consultas concretas y de rangos basados en el atributo de división.

•

Para las consultas concretas se puede consultar el vector de división para encontrar el disco en el que reside la tupla.

•

Para las consultas de rangos se consulta el vector de división para hallar el rango de discos en que pueden residir las tuplas.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

TÉCNICA 3.- DIVISIÓN POR RANGOS ACCESO •

En ambos casos la búsqueda se limita exactamente a aquellos discos que pudieran tener tuplas de interés.

•

Una ventaja de esta característica es que, si sólo hay unas pocas tuplas en el rango consultado, la consulta se suele enviar a un disco, en vez de hacerlo a todos.

•

Dado que se pueden utilizar otros discos para responder a otras consultas, la división por rangos da lugar a una mayor productividad de consultas a la vez que se mantiene un buen tiempo de respuesta.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

TÉCNICA 3.- DIVISIÓN POR RANGOS ACCESO •

Por otro lado, si hay muchas tuplas en el rango consultado, hay que recuperar muchas tuplas de pocos discos.

•

Lo que origina un cuello de botella de E/S (Punto Caliente) en esos discos.

•

Esto se le conoce como Sesgo de Ejecución, donde todo el procesamiento tiene lugar en una partición (o en sólo unas pocas).

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

CARACTERÍSTICAS DE LAS TÉCNICAS •

El tipo de división afecta a operaciones relacionales, como las reuniones.

•

La elección de la técnica de división también depende de las operaciones que haya que ejecutar.

•

En general, las divisiones por asociación y en rangos se prefieren al turno rotatorio.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

ALMACENAMIENTO •

Una vez que se ha dividido una relación entre varios discos, se puede recuperar en paralelo utilizándolos todos.

•

De modo parecido, cuando se está dividiendo una relación, se puede escribir en paralelo en varios discos.

•

De esta manera las velocidades de transferencia para la lectura o escritura de una relación completa son mucho mayores con paralelismo de E/S que sin él.

•

Sin embargo, la lectura de una relación completa, o Exploración de la Relación es sólo uno de los tipos de acceso a los datos. VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

El acceso a los datos puede clasificarse de la siguiente manera: 1. Explorar la relación completa. 2. Localizar una tupla de manera asociativa. Estas consultas denominadas Consultas Concretas, buscan tuplas que tengan un valor concreto para un atributo concreto. 3. Localizar todas las tuplas cuyo valor de un atributo dado se halle en un rango especificado. (p. e.: 5000 < Sueldo < 9000)

•

Las diferentes técnicas de división permiten estos tipos de acceso a diferentes niveles de eficacia. VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

•

BASES DE DATOS DISTRIBUIDAS

ISC

En un sistema con muchos discos, la forma de dividir una relación en un número determinado de discos, puede escogerse de la siguiente manera: o

Si una relación sólo contiene unas pocas tuplas que caben en un solo bloque de disco, es mejor asignar la relación a uno solo.

o

Las relaciones grandes se dividen preferiblemente entre todos los discos disponibles.

o

Si una relación consta de m bloques de disco y hay n discos disponibles en el sistema, se deberá ubicar la relación en min(m, n) discos.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

TRATAMIENTO DEL SESGO •

La distribución de las tuplas al dividir una relación (excepto para el Turno Rotatorio) puede estar sesgada, con un porcentaje alto de tuplas ubicado en algunas divisiones y menos en otros.

•

Por la manera en que puede aparecer el sesgo, se clasifica de la siguiente manera: o

Sesgo de los valores de los atributos

o

Sesgo de la división

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

•

El Sesgo de los Valores de los Atributos se refiere al hecho de que algunos valores pueden aparecer en los atributos de división de muchas tuplas.

•

Todas las tuplas con el mismo valor del atributo de división terminan en la misma partición, lo que da lugar al sesgo.

•

El Sesgo de la División se refiere al hecho de que puede haber un desequilibrio en la carga de la división, aunque no haya sesgo en los atributos.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

•

Un sesgo pequeño puede dar lugar a una disminución significativa del rendimiento.

•

El sesgo se transforma en un problema creciente al aumentar el grado de paralelismo. •

Por ejemplo: Si una relación de 1 000 tuplas se divide en 10 partes y la división está sesgada, puede haber algunas particiones de tamaño menor que 100 y otras de tamaño mayor que 100.

•

Incluso se puede dar la casualidad de que una partición tenga el tamaño de 200.

•

Teniendo una aceleración, al tener acceso en paralelo a las particiones, de sólo 5, en lugar del valor de 10 que se cabría esperar.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

•

Se esperaba una aceleración de 10 veces más rápido que haciéndolo en un solo disco; pero debido al sesgo (con 200 tuplas, se tiene 1000/200 = 5) sólo se obtiene una aceleración de 5.

•

Si la misma relación, con las 1 000 tuplas, tiene que dividirse en 100 partes, las particiones tendrán de media 10 tuplas.

•

Si una partición llega a tener hasta 40 tuplas (lo que es posible dado el gran número de particiones) la aceleración que se obtendría al tener acceso a ellas en paralelo sería de 25 (1000/40 = 25), en vez de 100.

•

Por lo tanto, se puede ver que la pérdida de aceleración debido al sesgo aumenta con el paralelismo.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

PARALELISMO ENTRE CONSULTAS •

Se ejecutan en paralelo entre sí diferentes consultas o transacciones.

•

La productividad de transacciones puede aumentarse con esta forma de paralelismo.

•

Sin embargo, el tiempo de respuesta de cada transacción no es menor que si éstas se ejecutaran aisladamente.

•

El uso principal del paralelismo entre consultas es ampliar los sistemas de procesamiento de transacciones para permitir un número mayor de transacciones por segundo.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

•

El paralelismo entre consultas es la forma más sencilla de paralelismo que se permite en los sistemas de BD, especialmente en los Sistemas Paralelos de Memoria Compartida.

•

Los SBD diseñados para sistemas con un único procesador pueden utilizarse en arquitecturas paralelas de memoria compartida con pocos o ningún cambio.

•

Esto dado que incluso los sistemas secuenciales de BD permiten el procesamiento concurrente.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

•

Las transacciones que se habrían realizado de manera concurrente en tiempo compartido en una máquina secuencial, se realizan en paralelo en la arquitectura paralela de memoria compartida.

•

Permitir el paralelismo entre consultas es más complicado en las arquitecturas de disco compartido y sin compartimiento.

•

Los procesadores tienen que realizar algunas tareas, como los bloqueos y el registro histórico, de forma coordinada, y eso exige que se intercambien mensajes.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

•

Los sistemas con arquitectura paralela también deben asegurar que dos procesadores no actualicen simultáneamente los mismos datos de manera independiente.

•

Cuando un procesador tiene acceso a los datos o los actualiza, el sistema de BD debe asegurar que el procesador tenga la última versión de éstos en memoria intermedia.

•

Esto último se conoce como el problema de Coherencia Caché.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

•

Se han desarrollado varios protocolos para garantizar la Coherencia Caché.

•

Generalmente los protocolos de la coherencia caché se integran con los de control de la concurrencia para reducir la sobrecarga.

•

Protocolo para asegurar la Coherencia Caché 1.

Antes de cualquier acceso de lectura o de escritura a un dato, una transacción lo bloquea en modo compartido o exclusivo. Inmediatamente después de obtener el bloqueo compartido o exclusivo del dato, lee también la copia más reciente del dato en el disco compartido.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

•

BASES DE DATOS DISTRIBUIDAS

ISC

Protocolo para asegurar la Coherencia Caché... 2.

Antes de que una transacción libere un bloqueo exclusivo de un dato, traslada éste al disco compartido; luego libera el bloqueo.

•

El protocolo asegura que cuando una transacción establezca un bloqueo compartido o exclusivo sobre un dato, obtenga la copia correcta del dato.

•

Se han desarrollado protocolos más complejos para evitar la lectura y escritura reiterada del disco.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

PARALELISMO EN CONSULTAS •

Se refiere a la ejecución en paralelo de una única consulta en varios procesadores y disco.

•

El uso de paralelismo en consultas es importante para acelerar las consultas de ejecución larga.

•

El paralelismo entre consultas no ayuda en esta labor, dado que cada consulta se ejecuta de manera secuencial.

•

Para valorar esta característica, considérese una consulta que exija que se ordene una relación:

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

PARALELISMO EN CONSULTAS •

Supóngase que la relación se ha dividido en varios discos mediante la división por rango, basado en algún atributo.

•

Y que se solicita la ordenación basado en el atributo de división.

•

La ordenación se puede realizar de la manera siguiente: •

Cada partición se ordena en paralelo

•

Y las particiones ordenadas se concatenan para obtener la relación ordenada final.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

•

Por lo que se puede hacer paralela una consulta haciendo paralelas las operaciones que la forman.

•

Existe otra fuente de paralelismo para la evaluación de las consultas: el Árbol de Operadores de una consulta puede contener varias operaciones.

•

Se puede hacer paralela la evaluación del árbol de operadores evaluando en paralelo algunas de las operaciones que no tengan ninguna dependencia entre sí.

•

Pueden ejecutarse en paralelo en procesadores separados, uno que genere el resultado que consuma el otro.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

•

BASES DE DATOS DISTRIBUIDAS

ISC

En resumen, la ejecución de una sola consulta puede hacerse en paralelo de dos maneras: •

Paralelismo en Operaciones. Se pude acelerar el procesamiento de consultas haciendo paralela la ejecución de cada una de las operaciones, como puede ser la ordenación, la selección, la proyección y la reunión.

•

Paralelismo entre Operaciones. Se puede acelerar el procesamiento de consultas ejecutando en paralelo las diferentes operaciones de las expresiones de las consultas.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

•

La operación reunión exige que se comparen pares de tuplas para ver si se satisfacen la condición de reunión.

•

Si cumplen, el par se añade al resultado reunido.

•

Los algoritmos de reunión paralela intentan repartir entre varios procesadores los pares que hay que comparar.

•

Cada procesador procesa localmente parte de la reunión.

•

Finalmente, hay que reunir los resultados de cada procesador para producir el resultado final.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

REUNIÓN POR DIVISIÓN •

Para ciertos tipos de reuniones, como las equirreuniones y las naturales, es posible dividir las dos relaciones de entrada entre los procesadores, y procesar localmente la reunión en cada uno de ellos.

•

Por ejemplo, supóngase que se utilizan N procesadores y que las relaciones que hay que reunir son R y S.

•

Cada una de las relaciones se divide en N particiones, denominadas r0, r1, …, rn-1, y s0, s1, …, sn-1.

•

Las particiones ri y si se envían al procesador Pi, donde la reunión se procesa localmente.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

BASES DE DATOS DISTRIBUIDAS

Inst. Tec. de Morelia

ISC

REUNIÓN POR DIVISIÓN •

Una vez divididas las relaciones se puede utilizar localmente cualquier técnica de reunión en cada procesador Pi para calcular la reunión de ri y si. r

s r0

P0

s0

r1

P1

s1

r2

P2

s2

r3

P3

s3

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

•

BASES DE DATOS DISTRIBUIDAS

ISC

Se puede optimizar el algoritmo de reunión utilizado localmente en cada procesador para reducir las E/S, no escribiendo en disco algunas de las tuplas sino guardándolas temporalmente en una memoria intermedia.

Reunión con Fragmentos y Réplicas • Funciona de la siguiente manera: 1.

Se divide una de las relaciones ( r ). Se puede utilizar en r cualquier técnica de división.

2.

La otra relación, digamos s, se replica entonces en todos los procesadores.

3.

El Procesador Pi procesa entonces localmente la reunión de ri con toda s, utilizando cualquier técnica de reunión.

VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

Procesamiento de Bases de Datos 8a. Ed. David M. Kroenke Pearson.  Introducción a los Sistemas de Bases de Datos 7a. Ed.

C. J. Date

ISC

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

Prentice Hall. VERANO DEL 2006

MC. Anastacio Antolino Hernández

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

http://www.cs.cinvestav.mx/BDChapa/Beto/Blanco.htm http://www.itlp.edu.mx/publica/tutoriales/basedat1/tema7. htm http://www.itlp.edu.mx/publica/revistas/revista_isc/anteriores/mzo99/b doo.html http://www.elrinconcito.com/articulos/BaseDatos/BasesDatos.htm http://es.wikipedia.org/wiki/CORBA

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

VERANO DEL 2006

ISC MC. Anastacio Antolino Hernández