Motivação
Os sistemas cada vez mais têm a necessidade de efectuar consultas
complexas sobre volumes gigantescos de dados, em tempo útil
A velocidade dos processadores tem aumentado significativamente,
mas, a velocidade dos discos tem tido um crescimento baixo sendo
muitas vezes o estrangulamento no acesso aos dados
Objectivo
Melhoria do desempenho
Incremento da disponibilidade dos dados
Acesso distribuído aos dados
Uma base de dados paralela garante o primeiro ponto, e
uma base de dados distribuída garante predominantemente
os dois últimos
O que permitiu o sucesso dos sistemas paralelos e
distribuídos
Aparecimento e implementação massiva dos sistemas relacionais,
onde as consultas de operações uniformes aplicadas a um conjunto
uniforme de dados, permitem a exploração de diversas formas de
paralelismo
Incapacidade dos fabricantes em conceber máquinas de grande
porte com capacidade suficiente para responder ás solicitações de
múltiplos utilizadores tendo acesso simultâneo a bases de dados
com volume da ordem dos terabytes
Aparecimento de máquinas baratas com múltiplos processadores
rápidos. Oferecem poder de computação aproximado às máquinas
de grande porte, são economicamente mais viáveis, e apresentam
arquitecturas modulares que permitem configurações de acordo
com as necessidades de processamento
Métricas
Um sistema paralelo ideal deve apresentar duas propriedades
Aceleração linear (linear speedup)
Crescimento linear (linear scaleup)
Aceleração linear
Não toma em consideração o tamanho do problema, mas sim o tamanho
do sistema
Para uma determinada tarefa, se o hardware for dobrado, a tarefa deverá
ser executada em metade do tempo
Mede-se definindo a razão entre o tempo de execução de um sistema
considerado de dimensão (1) e um sistema de dimensão (N)
tempo _ sistema _ 1
Speedup =
tempo _ sistema _ N
Speedup
A aceleração é linear se o quociente for igual a N
Crescimento linear
Mede a habilidade de crescimento do sistema e do problema
Se o hardware for duplicado, o sistema deverá ser capaz de
executar uma tarefa duas vezes maior, no mesmo intervalo de
tempo
Mede-se definindo a razão entre o tempo de execução de uma
tarefa de dimensão (1) num sistema de dimensão (1), e o tempo de
execução de uma tarefa de dimensão (N) num sistema de dimensão
(N)
tempo _ tarefa _ 1 _ sistema _ 1
Speedup =
tempo _ tarefa _ N _ sistema _ N
Scaleup
O crescimento é linear se o quociente for igual a 1
Factores limitativos da aceleração e crescimento lineares
O Speed-Up e Scale-Up são muitas vezes sublineares derivado a:
Custo de Arranque: O custo de iniciar múltiplos processos pode dominar o
tempo de computação, se o grau de paralelismo for elevado.
Interferência: Os processos ao acederem a recursos partilhados (ex: Bus do
sistema, discos, locks) competem entre si, despendendo tempo à espera dos
recursos, em vez de executarem trabalho útil.
Skew: Aumentando o grau de paralelismo aumenta-se a variação nos tempos de
execução das tarefas paralelas. O tempo global de execução é condicionado pela
mais demorada das tarefas paralelas.
No entanto, ganhos sobrelineares também podem ser alcançados,
em particular nas aplicações de bases de dados, quando se
consegue tirar proveito de um bom balanceamento de carga e da
disponibilização dos dados em memória e cache.
!
Arquitectura de comunicações para sistemas paralelos
"
Arquitectura de comunicações
Bus: Os nós do sistema enviam e recebem dados por um único bus de
comunicação;
Dificuldades de escalabilidade com o aumento do número de nós no
barramento.
Mesh: Os nós são configurados como nós numa matriz, e cada
componente é ligada a todas as componentes adjacentes;
As ligações aumentam com o número de nós adicionados, e por isso tem
melhor escalabilidade.
Mas pode requerer percorrer 2 (sqrt(n)-1) ligações para enviar uma
mensagem para alguns nós mais distantes na matriz.
Hipercubo: Os nós são numerados em binário; são ligados uns aos
outros se as suas representações binárias diferirem exactamente em
apenas um bit.
N nós estão ligadas a outros log(n) nós e podem chegar a qualquer outro
percorrendo no máximo log(n) ligações; reduz os tempos de comunicação
Arquitectura das bases de dados paralelas
Usam mais do que um CPU/disco/memória.
A organização da memória (principal e secundária) é um dos parâmetros
que tem maior influência num sistema paralelo
Formas de partilha
Shared memory
Todos os processadores partilham a mesma memória, e os dados podem ser movidos
entre a memória e qualquer disco
Shared disk
Cada processador tem a sua memória mas pode ler ou escrever em qualquer dos
discos
Shared nothing
Os discos/cpu/memória individuais são interligados
Hybrid
Combinação das arquitecturas anteriores
Permite:
Resolver mais rapidamente as consultas
O carregamento de dados, a construção de índices e a avaliação das
consultas podes ser efectuados em paralelo
Shared memory
Neste tipo de arquitectura, todos os processadores têm acesso a
qualquer módulo de memória ou disco através de um BUS ou rede
de comunicação
Bastante usada em baixos níveis de paralelismo (4 a 8 nós)
Vantagens
Simplicidade
Balanceamento de carga
Desvantagens
Custo
Expansibilidade limitada
Baixa disponibilidade
Simplicidade
Os dados em memória podem ser acedidos por qualquer dos processadores permitindo o acesso ao
catálogo e informações de controlo. Dessa forma a gestão do SGBD é similar a um sistema em
mono processamento
Balanceamento de carga
O sistema associa as tarefas aos processadores em tempo real baseando-se na carga actual dos
mesmos
Custo
Derivado da complexidade da rede de comunicação, já que é necessário ligar cada processador a
cada memória e disco do sistema
Expansibilidade limitada
Acessos conflituantes à memória partilhada podem causar interferência entre os processadores
limitando o crescimento do sistema
A rede de comunicação deve ter a largura de banda (quantidade de mensagens que a rede pode
suportar) correspondente à soma dos processadores e dos discos. É complicado construir tais redes
o que implica uma grande dificuldade em garantir um crescimento linear
Baixa disponibilidade
O espaço de memória é partilhado por todos os processadores, e uma falha nesse componente pode
afectar todos os processadores
Shared disk
Neste tipo de arquitectura, cada processador possui memória
principal exclusiva e tem acesso a qualquer disco através de um
BUS ou rede de comunicação
Adequado a aplicações “read-only”
Vantagens
Custo
Expansibilidade
Balanceamento de carga
Disponibilidade
Facilidade de migração de sistemas mono processamento
Desvantagens
Complexidade
Desempenho
Custo
O custo da rede de comunicação é inferior à arquitectura de memória partilhada já que pode ser
utilizada tecnologia de BUS padrão
Expansibilidade
Cada processador tem a si associado um módulo de memória, logo, o problema da interferência
não se coloca, permitindo uma muito maior expansibilidade (centenas de processadores)
Balanceamento de carga
É tão bom como o sistema de memória partilhada porque a atribuição de tarefas aos processadores
pode continuar a ser feita baseada na carga actual dos memos
Disponibilidade
As falhas dos módulos de memória são isoladas de outros nós possibilitando uma muito maior
disponibilidade do sistema
Facilidade de migração de sistemas mono processamento
Um sistema de discos partilhados pode ser visto como um conjunto de sistemas mono
processamento que partilham memória secundária
Complexidade
Não existe memória principal global para o controlo de bloqueios pelo que a gestão de transacções
se torna um processo mais complexo, aumentando a troca de mensagens entre processadores e
originando interferência e atrasos
Desempenho
O acesso aos discos torna-se o gargalo do sistema
Shared nothing
Neste tipo de arquitectura (memória distribuída), cada processador
possui memória principal e secundária exclusivas. Cada nó pode
ser visto como um SGBD local (tal como um SGBD distribuído)
Devido a esta similaridade muitas das soluções projectadas para
SGBD distribuídos tais como, fragmentação, gestão distribuída de
transacções e processamento de consultas distribuído podem ser
reutilizadas neste modelo
Vantagens
Baixo custo
Expansibilidade
Disponibilidade
Crescimento incremental
Desvantagens
Balanceamento de carga
As principais vantagens da memória distribuída são o baixo custo aliado a uma
alta expansibilidade e disponibilidade
Os dados acedidos da memória local (primária e secundária) não passam pela
rede de comunicação, minimizando a interferência na partilha dos recursos
Permitindo um crescimento incremental, consegue suportar um número enorme
de processadores sem causar interferência entre si, obtendo aceleração e
crescimento lineares.
A replicação de dados entre os nós permite que seja obtido um alto grau de
disponibilidade do sistema
O custo de comunicação e acesso a discos remotos é alto. O envio de dados
envolve software nos dois extremos da comunicação ponto a ponto
Outro problema desta arquitectura é o balanceamento de carga que pode
degradar consideravelmente o desempenho do sistema. Isto pode ocorrer porque
diferentemente das arquitecturas citadas anteriormente, o balanceamento de
carga é decidido baseado na localização dos dados e não na carga corrente do
sistema
O acréscimo de novos nós ao sistema requer uma reorganização dos dados
Hybrid
Arquitectura hierárquica
Este modelo híbrido consiste de uma arquitectura shared nothing onde cada nó
é formado no nível interno como uma arquitectura shared memory
Arquitectura shared something
Outra alternativa é um sistema shared disk tendo em cada nó um sistema
shared memory
Arquitectura shared something
Arquitectura hierárquica
!
"
Um sistema de Bases de Dados Distribuídas consiste num
conjunto de sites, ligados por uma rede convencional, que não
partilham nenhum componente físico
Os dados estão fisicamente armazenados por várias máquinas
(também referidos por sites ou nós), e cada site é normalmente
gerido por um SGBD (Sistema de Gestão de Base de Dados) e é
capaz de correr independentemente dos outros sites
Os dados são partilhados pelos
utilizadores nas várias máquinas.
A rede interliga as máquinas, pelo que
comunicação entre sites é efectuada
através da rede
As transacções podem aceder a dados
num ou mais sites, de uma vez
Cada nó pode ser um “query site”, um
“data site” ou ambos
Clientes e Servidores
O servidor (SGBD) é o software
que gere a base de dados
O cliente é a aplicação que
requisita informação da base de
dados
Um nó num sistema distribuído
pode actuar como cliente, como
servidor ou ambos
Um cliente pode ligar-se directa
ou indirectamente à base de
dados num nó
Para ligar cada nó num sistema
distribuído é necessário uma rede
de comunicação. Os comandos
são enviados do cliente para o
servidor usando protocolos de
comunicação
Cada base de dados num sistema
distribuído é distinta de todas as
outras bases de dados e tem o seu
global database name
A distribuição dos dados é gerida por
factores como administração local e
aumenta a disponibilidade e o
desempenho
O sistema deve tratar o impacto da
distribuição de dados de forma
transparente. Em particular, as
seguintes propriedades são
desejáveis
Distribuição de dados independente
Atomicidade na distribuição de dados
Existe facilidade de expansão quer
pela adição de novos nós quer pelo
melhoramento de características do
hardware (discos, processadores,
etc.)
Bases de dados Homogéneas
Todos os nós correm o mesmo SGBD
Os servidores têm conhecimento uns dos outros (database links) e
existe uma efectiva distribuição dos pedidos efectuados pelos
utilizadores
Bases de dados Heterogéneas
Os nós têm SGBD diferentes
Os nós podem não ter conhecimento uns dos outros, podendo
fornecer capacidades limitadas para cooperação no
processamento de transacções distribuídas
A ligação entre os diferentes SGBD é feita através de software
específico (Heterogeneous Services Agent)
São usados protocolos de rede para a simplificação de
transacções (ODBJ, JDBC, etc.)
Normalmente usam-se quando se pretende integrar sistemas de
bases de dados já existentes, para fornecer novas funcionalidades
Formas de armazenamento de dados distribuídos
Replicação
Existem várias cópias dos dados, armazenadas em nós
diversos
Grande tolerância a falhas
Fragmentação
Determinação de conjuntos de fragmentos distintos que
constituem unidades lógicas de alocação
Cada unidade lógica é armazenada num determinado nó
(possivelmente distintos, mas não obrigatoriamente)
Os dados existentes na relação global são mapeados pelos
fragmentos sem nenhuma perda
Replicação e fragmentação
As relações são divididas em fragmentos distintos, e existem
várias cópias desses fragmentos replicadas por diferentes nós
Replicação
Vantagens
Disponibilidade
Existindo réplicas, a falha num nó não implica indisponibilidade
Paralelismo
As consultas podem ser efectuadas em vários nós simultaneamente
Redução do volume de dados a transferir
Uma relação está disponível em cada nó que tenha uma réplica
Desvantagens
Actualizações das réplicas
Cada réplica tem de ser actualizada
Falhas nas actualizações ou actualizações concorrentes podem implicar
inconsistência dos dados
Replicação síncrona: Todas as réplicas são actualizadas antes das
transacções serem submetidas
Aumento do tempo de resposta
Replicação assíncrona: As réplicas são actualizadas periodicamente
Inconsistência temporária dos dados
Fragmentação
Vantagens
Menores relações
Menor volume de dados implica melhor tempo de resposta (depende da consulta)
Paralelismo
As consultas podem ser efectuadas em vários nós simultaneamente
Desvantagens
Divisão das consultas por vários nós
Estando as relações fragmentadas, pode ser necessário efectuar operações de junção
e união (depende da consulta)
Comparativamente com a replicação pode gerar tempos de resposta superiores quando
os dados pretendidos se encontram em nós distintos
Fragmentação horizontal
Cada fragmento é um conjunto de tuplos da relação original
Os fragmentos devem ser disjuntos
Técnicas utilizadas
Fragmentação por faixa de valores
Os fragmentos são obtidos em função dos valores dos atributos da relação, levando-se
em consideração os predicados existentes nas aplicações
Fragmentação por função de Hashing
A relação global é fragmentada de acordo com o valor de uma função de hashing
aplicada sobre um dos atributos, de forma a relacionar cada tuplo a um fragmento
Fragmentação circular
Consiste da associação sequencial de cada tuplo da relação global a um fragmento
sem levar em consideração o valor de nenhum atributo.
Desta forma, se a relação contiver n tuplos e o número de fragmentos a serem gerados
for m, cada fragmento receberá n/m tuplos.
Fragmentação derivada
A fragmentação derivada de uma relação global não é baseada nas propriedades dos
seus próprios atributos mas em função da fragmentação de outra relação. É usada para
facilitar a operação de junção entre fragmentos
Fragmentação vertical
Cada fragmento é um conjunto de atributos da relação original
Cada fragmento tem um esquema mais pequeno do que o esquema da
relação original
Cada fragmento de uma relação tem de ter um atributo comum para permitir
mapear a relação original sem perdas, ou seja, é replicado em cada fragmento
a chave primária da relação global de forma a permitir a sua reconstrução a
partir da junção dos fragmentos
O seu objectivo é identificar fragmentos de tal forma que várias aplicações
possam ser executadas com acesso à somente uma partição da relação
global.
Caso uma aplicação necessite de acesso à dados presentes em mais de um
fragmento, a fragmentação vertical não é benéfica visto que será necessária a
realização de junções entre os fragmentos para a obtenção do resultado
!
Fragmentação híbrida
Combinação da fragmentação horizontal e vertical
Pode ser feita de duas formas: fragmentando-se horizontalmente a
relação e em seguida para cada fragmento obtido fragmentá-lo
verticalmente, ou o inverso
Embora estas operações possam ser recursivamente repetidas, o que
ocorre na prática é a interrupção do processo depois da segunda iteração.
A ordem em que as fragmentações são aplicadas afectam o resultado
final.
"