base de datos paralelas

Inst. Tec. de Morelia

BASES DE DATOS DISTRIBUIDAS

ISC

SISTEMAS DE BASES DE DATOS PARALELAS

VERANO DEL 2006

MC. Anastacio Antolino Hernndez



ISC

Actualmente los Sistemas Paralelos se estn comercializando con xito por prcticamente 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 volmenes crecientes de datos para planificar sus actividades y sus tarifas.

VERANO DEL 2006




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 volmenes 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 paralelizacin. Varios sistemas comerciales y de investigacin han demostrado la potencia y dimensionalidad del procesamiento paralelo de consultas. Con el abaratamiento de los microprocesadores, las mquinas paralelas se han vuelto comunes y relativamente baratas.

VERANO DEL 2006




ISC

El paralelismo se utiliza para proporcionar aceleracin, y las consultas se ejecutan ms rpido debido a que se proporcionan ms recursos, como procesadores y discos. El paralelismo tambin 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 ms sencilla, el paralelismo de E/S se refiere a la reduccin del tiempo necesario para recuperar relaciones del disco dividindolas en varios discos.

VERANO DEL 2006




ISC

La forma ms frecuente de divisin de datos en un entorno de BD Paralela es la Divisin Horizontal. En la divisin horizontal, las tuplas de las relaciones se dividen entre varios grupos, de modo que cada tupla resida en un disco.

TCNICAS DE DIVISIN Se presentan 3 estrategias bsicas para la divisin 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




ISC

TCNICA 1.- TURNO ROTATORIO La relacin se explora en cualquier orden y la i-sima tupla se enva al disco numerado D i mod n. El esquema de turno rotatorio asegura una distribucin homognea de las tuplas entre los discos. Cada disco tiene aproximadamente el mismo nmero de tuplas que los dems.

VERANO DEL 2006




ISC

TCNICA 1.- TURNO ROTATORIO ACCESO El esquema se adapta perfectamente a las aplicaciones que desean leer secuencialmente la relacin completa para cada consulta. Con este esquema tanto las consultas concretas como las de rango son difciles de procesar. Dado que se debe emplear en la bsqueda cada uno de los n discos.

VERANO DEL 2006




ISC

TCNICA 2.- DIVISIN POR ASOCIACIN En esta estrategia de divisin uno o ms atributos del esquema de la relacin se designan como atributos de la divisin. Se escoge una funcin de asociacin cuyo rango sea [0, 1, , n-1]. Cada tupla de la relacin original se asocia en trminos de los atributos de la divisin. Si la funcin de asociacin devuelve i, la tupla se ubica en el disco Di.

VERANO DEL 2006




ISC

TCNICA 2.- DIVISIN POR ASOCIACIN ACCESO Este esquema se adapta mejor a las consultas concretas basadas en el atributo de divisin. Por ejemplo si se divide una relacin en trminos del atributo No_Ctrl, se puede responder a la consulta: Buscar el registro del alumno con nmero de control = 97120543. Aplicando la funcin de divisin por asociacin 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 2006MC. Anastacio Antolino Hernndez



ISC

TCNICA 2.- DIVISIN POR ASOCIACIN ACCESO Este esquema tambin es til para las exploraciones secuenciales de la relacin completa. Si la funcin de asociacin es una buena funcin aleatoria y los atributos de divisin forman una clave de la relacin, el nmero de tuplas en cada uno de los discos ser aproximadamente el mismo. Por lo que el tiempo empleado para explorar la relacin es aproximadamente 1/n del tiempo necesario para explorar la relacin en un sistema de disco nico.VERANO DEL 2006MC. Anastacio Antolino Hernndez



ISC

TCNICA 2.- DIVISIN POR ASOCIACIN ACCESO El esquema, sin embargo, no se adapta bien a las bsquedas concretas en trminos de atributos que no sean de divisin. Tampoco se adapta bien a las respuestas a consultas de rangos, dado que, generalmente, las funciones de asociacin 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 2006MC. Anastacio Antolino Hernndez



ISC

TCNICA 3.- DIVISIN POR RANGOS Esta estrategia distribuye rangos contiguos de valores de los atributos a cada disco. Se escoge un atributo de divisin, A, como vector de divisin. Sea [v0, v1, , vn-2] el vector de divisin, tal que, si i < j, entonces vi < vj.

VERANO DEL 2006




ISC

TCNICA 3.- DIVISIN POR RANGOS La relacin 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




ISC

TCNICA 3.- DIVISIN POR RANGOS ACCESO Este esquema se adapta bien a las consultas concretas y de rangos basados en el atributo de divisin. Para las consultas concretas se puede consultar el vector de divisin para encontrar el disco en el que reside la tupla. Para las consultas de rangos se consulta el vector de divisin para hallar el rango de discos en que pueden residir las tuplas.

VERANO DEL 2006




ISC

TCNICA 3.- DIVISIN POR RANGOS ACCESO En ambos casos la bsqueda se limita exactamente a aquellos discos que pudieran tener tuplas de inters. Una ventaja de esta caracterstica es que, si slo 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 divisin por rangos da lugar a una mayor productividad de consultas a la vez que se mantiene un buen tiempo de respuesta.VERANO DEL 2006MC. Anastacio Antolino Hernndez



ISC

TCNICA 3.- DIVISIN 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 Ejecucin, donde todo el procesamiento tiene lugar en una particin (o en slo unas pocas).

VERANO DEL 2006




ISC

CARACTERSTICAS DE LAS TCNICAS El tipo de divisin afecta a operaciones relacionales, como las reuniones. La eleccin de la tcnica de divisin tambin depende de las operaciones que haya que ejecutar. En general, las divisiones por asociacin y en rangos se prefieren al turno rotatorio.

VERANO DEL 2006




ISC

ALMACENAMIENTO Una vez que se ha dividido una relacin entre varios discos, se puede recuperar en paralelo utilizndolos todos. todos. De modo parecido, cuando se est dividiendo una relacin, se puede escribir en paralelo en varios discos. discos. De esta manera las velocidades de transferencia para la lectura o escritura de una relacin completa son mucho mayores con paralelismo de E/S que sin l. l. Sin embargo, la lectura de una relacin completa, o Exploracin de la Relacin es slo uno de los tipos de acceso a los datos. datos.VERANO DEL 2006MC. Anastacio Antolino Hernndez



ISC

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

Las diferentes tcnicas de divisin permiten estos tipos de acceso a diferentes niveles de eficacia. eficacia.VERANO DEL 2006MC. Anastacio Antolino Hernndez



ISC

En un sistema con muchos discos, la forma de dividir una relacin en un nmero determinado de discos, puede escogerse de la siguiente manera: manera:o Si una relacin slo contiene unas pocas tuplas que caben en un solo bloque de disco, es mejor asignar la relacin a uno solo. solo. Las relaciones grandes se dividen preferiblemente entre todos los discos disponibles. disponibles. Si una relacin consta de m bloques de disco y hay n discos disponibles en el sistema, se deber ubicar la relacin en min(m, min( n) discos. discos.

o

o

VERANO DEL 2006




ISC

TRATAMIENTO DEL SESGO La distribucin de las tuplas al dividir una relacin (excepto para el Turno Rotatorio) puede estar sesgada, Rotatorio) sesgada, con un porcentaje alto de tuplas ubicado en algunas divisiones y menos en otros. otros. Por la manera en que puede aparecer el sesgo, se clasifica de la siguiente manera: manera:o o Sesgo de los valores de los atributos Sesgo de la divisin

VERANO DEL 2006




ISC

El Sesgo de los Valores de los Atributos se refiere al hecho de que algunos valores pueden aparecer en los atributos de divisin de muchas tuplas. tuplas. Todas las tuplas con el mismo valor del atributo de divisin terminan en la misma particin, lo que da lugar al sesgo. sesgo. El Sesgo de la Divisin se refiere al hecho de que puede haber un desequilibrio en la carga de la divisin, aunque no haya sesgo en los atributos. atributos.

VERANO DEL 2006




ISC

Un sesgo pequeo puede dar lugar a una disminucin significativa del rendimiento. rendimiento. El sesgo se transforma en un problema creciente al aumentar el grado de paralelismo. paralelismo. Por ejemplo: Si una relacin de 1 000 tuplas se divide en 10 ejemplo: partes y la divisin est sesgada, puede haber algunas particiones de tamao menor que 100 y otras de tamao mayor que 100. 100. Incluso se puede dar la casualidad de que una particin tenga el tamao de 200. 200. Teniendo una aceleracin, al tener acceso en paralelo a las particiones, de slo 5, en lugar del valor de 10 que se cabra esperar. esperar.

VERANO DEL 2006




ISC

Se esperaba una aceleracin de 10 veces ms rpido que hacindolo en un solo disco; pero debido al sesgo (con 200 disco; tuplas, se tiene 1000/200 = 5) slo se obtiene una aceleracin de 1000/ 5. Si la misma relacin, con las 1 000 tuplas, tiene que dividirse en 100 partes, las particiones tendrn de media 10 tuplas. tuplas. Si una particin llega a tener hasta 40 tuplas (lo que es posible dado el gran nmero de particiones) la aceleracin que se obtendra al tener acceso a ellas en paralelo sera de 25 (1000/40 1000/ = 25), en vez de 100. 25), 100. Por lo tanto, se puede ver que la prdida de aceleracin debido al sesgo aumenta con el paralelismo. paralelismo.

VERANO DEL 2006




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. paralelismo. Sin embargo, el tiempo de respuesta de cada transaccin no es menor que si stas se ejecutaran aisladamente. aisladamente. El uso principal del paralelismo entre consultas es ampliar los sistemas de procesamiento de transacciones para permitir un nmero mayor de transacciones por segundo. segundo.

VERANO DEL 2006




ISC

El paralelismo entre consultas es la forma ms sencilla de paralelismo que se permite en los sistemas de BD, especialmente en los Sistemas Paralelos de Memoria Compartida. Compartida. Los SBD diseados para sistemas con un nico procesador pueden utilizarse en arquitecturas paralelas de memoria compartida con pocos o ningn cambio. cambio. Esto dado que incluso los sistemas secuenciales de BD permiten el procesamiento concurrente. concurrente.

VERANO DEL 2006




ISC

Las transacciones que se habran realizado de manera concurrente en tiempo compartido en una mquina secuencial, se realizan en paralelo en la arquitectura paralela de memoria compartida. compartida. Permitir el paralelismo entre consultas es ms complicado en las arquitecturas de disco compartido y sin compartimiento. compartimiento. Los procesadores tienen que realizar algunas tareas, como los bloqueos y el registro histrico, de forma coordinada, y eso exige que se intercambien mensajes. mensajes.

VERANO DEL 2006




ISC

Los sistemas con arquitectura paralela tambin deben asegurar que dos procesadores no actualicen simultneamente los mismos datos de manera independiente. independiente. Cuando un procesador tiene acceso a los datos o los actualiza, el sistema de BD debe asegurar que el procesador tenga la ltima versin de stos en memoria intermedia. intermedia. Esto ltimo se conoce como el problema de Coherencia Cach. Cach.

VERANO DEL 2006




ISC

Se han desarrollado varios protocolos para garantizar la Coherencia Cach. Cach. Generalmente los protocolos de la coherencia cach se integran con los de control de la concurrencia para reducir la sobrecarga. sobrecarga. Protocolo para asegurar la Coherencia Cach1. Antes de cualquier acceso de lectura o de escritura a un dato, una transaccin lo bloquea en modo compartido o exclusivo. exclusivo. Inmediatamente despus de obtener el bloqueo compartido o exclusivo del dato, lee tambin la copia ms reciente del dato en el disco compartido. compartido.

VERANO DEL 2006




ISC

Protocolo para asegurar la Coherencia Cach... Cach...2. Antes de que una transaccin libere un bloqueo exclusivo de un dato, traslada ste al disco compartido; luego libera el bloqueo. compartido; bloqueo.

El protocolo asegura que cuando una transaccin establezca un bloqueo compartido o exclusivo sobre un dato, obtenga la copia correcta del dato. dato. Se han desarrollado protocolos ms complejos para evitar la lectura y escritura reiterada del disco. disco.

VERANO DEL 2006




ISC

PARALELISMO EN CONSULTAS Se refiere a la ejecucin en paralelo de una nica consulta en varios procesadores y disco. disco. El uso de paralelismo en consultas es importante para acelerar las consultas de ejecucin larga. larga. El paralelismo entre consultas no ayuda en esta labor, dado que cada consulta se ejecuta de manera secuencial. secuencial. Para valorar esta caracterstica, considrese una consulta que exija que se ordene una relacin: relacin:

VERANO DEL 2006




ISC

PARALELISMO EN CONSULTAS Supngase que la relacin se ha dividido en varios discos mediante la divisin por rango, basado en algn atributo. atributo. Y que se solicita la ordenacin basado en el atributo de divisin. divisin. La ordenacin se puede realizar de la manera siguiente: siguiente: Cada particin se ordena en paralelo Y las particiones ordenadas se concatenan para obtener la relacin ordenada final. final.

VERANO DEL 2006




ISC

Por lo que se puede hacer paralela una consulta haciendo paralelas las operaciones que la forman. forman. Existe otra fuente de paralelismo para la evaluacin de las consultas: consultas: el rbol de Operadores de una consulta puede contener varias operaciones. operaciones. Se puede hacer paralela la evaluacin del rbol de operadores evaluando en paralelo algunas de las operaciones que no tengan ninguna dependencia entre s. s. Pueden ejecutarse en paralelo en procesadores separados, uno que genere el resultado que consuma el otro. otro.

VERANO DEL 2006




ISC

En resumen, la ejecucin de una sola consulta puede hacerse en paralelo de dos maneras: maneras: Paralelismo en Operaciones. Se pude acelerar el Operaciones. procesamiento de consultas haciendo paralela la ejecucin de cada una de las operaciones, como puede ser la ordenacin, la seleccin, la proyeccin y la reunin. reunin. Paralelismo entre Operaciones. Se puede acelerar el Operaciones. procesamiento de consultas ejecutando en paralelo las diferentes operaciones de las expresiones de las consultas. consultas.

VERANO DEL 2006




ISC

REUNIN PARALELA La operacin reunin exige que se comparen pares de tuplas para ver si se satisfacen la condicin de reunin. Si cumplen, el par se aade al resultado reunido. Los algoritmos de reunin paralela intentan repartir entre varios procesadores los pares que hay que comparar. Cada procesador procesa localmente parte de la reunin. Finalmente, hay que reunir los resultados de cada procesador para producir el resultado final.

VERANO DEL 2006




ISC

REUNIN POR DIVISIN 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 reunin en cada uno de ellos. Por ejemplo, supngase 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 envan al procesador Pi, donde la reunin se procesa localmente.VERANO DEL 2006MC. Anastacio Antolino Hernndez



ISC

REUNIN POR DIVISIN Una vez divididas las relaciones se puede utilizar localmente cualquier tcnica de reunin en cada procesador Pi para calcular la reunin de ri y si.rr0 P0 s0

s

r1

P1

s1

r2

P2

s2

r3

P3

s3

VERANO DEL 2006




ISC

Se puede optimizar el algoritmo de reunin utilizado localmente en cada procesador para reducir las E/S, no escribiendo en disco algunas de las tuplas sino guardndolas temporalmente en una memoria intermedia.

Reunin con Fragmentos y Rplicas Funciona de la siguiente manera:1. Se divide una de las relaciones ( r ). Se puede utilizar en r cualquier tcnica de divisin. La otra relacin, digamos s, se replica entonces en todos los procesadores. El Procesador Pi procesa entonces localmente la reunin de ri con toda s, utilizando cualquier tcnica de reunin.

2.

3.

VERANO DEL 2006




ISC

Principles Of Distributed Database Systems 2. Ed. Ed. M. Tamer Ozsu y Patrick Valduriez Prentice Hall Fundamentos de Bases de Datos 4a. Edicin Silberschatz, Korth y Sudarshan Mc Graw Hill Procesamiento de Bases de Datos 8a. Ed. Ed. David M. Kroenke Pearson. Pearson. Introduccin a los Sistemas de Bases de Datos 7a. Ed. Ed. C. J. Date Prentice Hall. Hall.VERANO DEL 2006MC. Anastacio Antolino Hernndez



ISC

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

VERANO DEL 2006


base de datos paralelas

Documents