Bancos de Dados Distribuídos - uniriotec.brConceito em busca de uma definição consensual, amplamente utilizadofernanda.baiao/BDDDW/Slides/03 - BDD - Visao... · 2006-10-7

1

Bancos de Dados Distribuídos

Fernanda Baiã[email protected]

Departamento de Informática AplicadaUNIRIO2006.2

Visão geral de BDD

© 2006 M. Tamer Özsu e Patrick Valduriez (tradução livre e adaptações Marta Mattoso e Fernanda Baião) 3

Bibliografia Utilizada

Özsu, M.T. Valduriez, P. "Principles of Distributed Database Systems", 2a edição, Prentice Hall, 1999 (versão em português lançada em 2001)Abiteboul, A., Buneman, P., and Suciu, D., “Data on the Web”, Morgan-Kaufman, 1999 Elmasri, R. Navathe, S. "Fundamentals of Database Systems", 2a edição, Benjamin/Cummings, 1994Ceri, S. Pelagatti, G. "Distributed Database Systems - Principles and Systems, McGraw Hill, 1984Kossmann, D., The State of the Art in Distributed Query Processing, ACM Computing Surveys 32(4), pp. 422-469, 2000


Conteúdo

1- Introdução2- Caracterização de SBDD3- Vantagens de SBDD4- Principais Desafios dos SGBDD5- As Novas Tecnologias e os SBDDs

Introdução


Histórico dos Sistemas de Bancos de Dados

Antes: Processamento de arquivos tradicional

Arquivo 3

Arquivo 2

Programa 1

Descrição de dados

Programa 2


Programa 3


Arquivo 1

Dad

os R

edun

dant

es

2


Histórico dos Sistemas de Bancos de Dados

Processamento de Banco de Dadosindependência de dadosindependência de dados

Programa 1


Programa 2Manipulação

de dados

Programa 3...

Banco de Dados


Motivação para os Sistemas de Bancosde Dados Distribuídos

Importância da tecnologia de Bancos de Dados DistribuídosProdutos no mercadoVantagens sobre os centralizadosPrevisões de substituição completa dos SGBDs centralizadosQuestões em aberto


Surgimento dos Sistemas de Bancosde Dados Distribuídos

Tecnologiade BD

Integração

DistribuiçãoCentralização

≠ CentralizaçãoCentralizaçãoIntegraçãoIntegração

Redes de Computadores

Sistemas de Bancos de Dados Distribuídos


Processamento Distribuído

Conceito em busca de uma definição consensual, amplamente utilizado

Computação distribuídaUm grupo de elementos de processamento

autônomos não necessariamente homogêneosinterconectados por uma rede de computadores cooperam na realização de tarefas


O que está sendo distribuído...

Lógica de processamento

Funções

Dados

Controle

Em um SBDD, todos são necessários e importantes...Em um SBDD, todos são necessários e importantes...

Caracterização de SBDD

3


O que ÉÉ um Sistema de Banco de Dados Distribuído

Base de Dados Distribuída (BDD)É uma coleção de diversas bases de dados, interligadasinterligadaslogicamentelogicamente através de uma rederede de de computadorescomputadores

Sistema de Gerência de Bases de dados Distribuídas (SGBDD)

É o sistemasistema de softwarede software que possibilita a gerência da BDD e lida com aspectos de transpartransparênciaência para o usuário

Sistema de Banco de Dados Distribuído (SBDD)SBDD = BDD + SGBDDSBDD = BDD + SGBDD


O que NÃO ÉNÃO É um Sistema de Banco de Dados Distribuído...

Sistemas de Tempo Compartilhado (Timesharing)Sistemas de Multiprocessamento

Memória Compartilhada (shared-memory, sharedeverything)Disco Compartilhado (shared-disk)Nada Compartilhado (shared-nothing, message-passing)Memória Compartilhada Distribuída (distributed shared-memory)

Sistema de Banco de Dados que reside em 1 nó da rede

= Sistema de Banco de Dados centralizado


SGBD centralizado em uma rede

Nó 1

Nó 2

Nó 3Nó 4

Nó 5Rede de

Comunicação


Um Ambiente de SGBDD

Nó 1

Nó 2

Nó 3Nó 4

Nó 5Rede de

Comunicação


Principais Características de um SBDD

Dados armazenados em diversosdiversos locaislocais (ou nós)cada nó é logicamente um processador≠ distância geográfica

Processadores interconectados através de rederedeA base de dados distribuída nãonão é é umauma coleçãocoleção de de arquivosarquivosO SGBDD possui todatoda a a funcionalidadefuncionalidade de um SGBDde um SGBDTecnologia atual

multiprocessadoresmemória compartilhada (shared-memory ou shared-everything)disco compartilhado (shared-disk)nada compartilhado ou memória distribuída (shared-nothing)

cliente-servidorclusters, GRIDs


Arquiteturas de Multiprocessadores

Memória Compartilhada

4



Disco Compartilhado



Memória Distribuída


Aplicações de SBDD

IntuitivasCompanhias aéreasRedes de lojasCadeias de hotéisControle militarSistemas de informações gerenciais corporativasQualquer organização que possua uma estrutura Qualquer organização que possua uma estrutura descentralizadadescentralizada

Nem tão intuitivas assim...Sistemas com grande volume de dados, mesmo que em organizações centralizadas, que demandam por aumento aumento de desempenhode desempenho


Arquiteturas de SGBDD


Arquiteturas de SGBDD

Distribuiçãodistribuição física dos componentes do sistema

Heterogeneidadevários níveis: hardware, comunicação, sistema operacionalpara o SGBD: modelo de dados, linguagem de consulta, algoritmos de gerência de transações

AutonomiaGrau de autonomia com que cada SGBD individual trabalha

existência de troca de informações entre os componentesVários conceitos...

de projeto: SGBD componente decide aspectos relacionados ao seupróprio projetode comunicação: SGBD componente decide se comunica ou não (e como se comunica) com outros SGBDde execução: SGBD componente executa operações locais da forma que deseja

Vantagens de SBDD

5


Vantagens de SBDDs

1. Transparência na Gerência dos Dados Distribuídos

2. Confiabilidade

3. Potencial Aumento de Desempenho

4. Expansão mais fácil e econômica


1. Transparência na Gerência dos Dados Distribuídos

Transparência é a separação entre a semântica de alto nível de um sistema e seus detalhes de implementaçãoA questão fundamental é prover

Independência de dadosIndependência de dadosno ambiente distribuído.

Desta forma, os usuários do banco de dados enxergariam umauma únicaúnica imagemimagem dada base de base de

dados dados logicamentelogicamente integradaintegrada, embora elaestivesse fisicamente distribuída.


Níveis de Transparência

Transparência da rede

Transparência da replicação

Transparência da fragmentaçãodiversas técnicas:

horizontal (seleções)

vertical (projeções)

combinações


Transparência - Exemplo

Qual a remuneração de cada empregado, em função das responsabilidades atribuídas a ele por mais de 1 ano em algum projeto?


Acesso transparente


Base de dados Distribuída – Visão do Usuário

6


SGBD Distribuído - Realidade


2. Confiabilidade

Componentes replicados

Eliminação de pontos únicos de falha

ProvêemProvêem maiormaior disponibilidadedisponibilidade e e confiabilidadeconfiabilidade


Confiabilidade

Requer suporte para transações distribuídasprotocolos distribuídos

de controle de concorrência e gerência de deadlocksde confiabilidadede controle de réplicas

Os aplicativos dos usuários não precisariam se preocuparcom com a coordenaçãocoordenação de de seusseus acessosacessos a a bancosbancos de de dados dados locaislocais individuaisindividuais, nem teriam que se preocupar

coma possibilidadepossibilidade de de falhasfalhas emem nósnós ouou links de links de comunicaçãocomunicação durante a transação


Confiabilidade - Exemplobegin_transaction ATUALIZAR_SALARIObeginEXEQ SQL UPDATE PAY

SET SAL = SAL*1.1end.

SELECT AVG(SAL)FROM EMP, PAYWHERE EMP.TITLE = PAY.TITLE


3. Potencial aumento de desempenho

Localização dos DadosCompartilhamento de recursos não é tão críticoReduz o tempo de acesso remoto aos dados

Requer suporte para fragmentação e replicaçãoParalelismo no Processamento de Consultas

Paralelismo entre consultas (Inter-query)Paralelismo dentro da consulta (Intra-query)Paralelismo dentro de operações


Paralelismo no Processamento de Consultas

Paralelismo entre consultas (Inter-query)Execução de diversas consultas em paralelo

Paralelismo dentro da consulta (Intra-query)Execução de operações de uma mesma consulta em paralelo

Paralelismo dentro de operaçõesExecução da mesma operação para fragmentos distintos da relação em paralelo

7


Para tirar proveito do paralelismo

Ter os dados distribuídos pelos processadores envolvidos no processamento paralelo

Replicação total?Replicação total?

E quanto às atualizações ?maior número de réplicas implica em maior tempo de processamento de uma atualização

controle de concorrência distribuído protocolos de finalização (commit)


Considerações sobre o aumento de desempenho em SBDD com paralelismo

Ganhos comprovados experimentalmenteMétricas

aceleração linear, crescimento linear

Balanceamento de cargadistribuição estática x dinâmicaAcelaração (Speed-up) chega a ser maior que o linear, em alguns casos

conferências DEXA, VECPAR, ...


4. Expansão Mais Fácil e Econômica

Crescimento da base de dados é um problema atual de muitas aplicaçõesEvolução da tecnologia

microprocessadores, workstations, clusters, GRIDs, ...modelo de computação cliente-servidor, múltiplascamadas, desenvolvimento baseado emcomponentes, ...

Principais Desafios dos SGBDDs



Projeto de Distribuição de Bases de Dados

Processamento Distribuído de Consultas

Controle de Concorrência Distribuído

Confiabilidade



Projeto de Distribuição de Bases de Dados“Particionamento dos dados”

Fragmentação Horizontal, Vertical ou combinaçõesválidasInformações não replicadas

Controle de concorrência simplificado> desempenho de operações de atualização

“Replicação”Total ou parcialFragmentos replicados em nós

+ disponibilidade> desempenho de operações de leitura

8


Exemplo de FragmentaçãoBase de Dados Centralizada

222-3333Cláudio Silva222-3333Gabriel Silva222-3333Maria Silva322-9999Jose Campos

TelefoneNome

Cláudio SilvaVarig 224Gabriel SilvaVarig 224Gabriel SilvaAir France 147Maria SilvaAir France 147José CamposAir France 147

PassageiroNome Vôo

Varig150500,00Varig 224Air France500750,00Air France 455Air France2501000,00Air France 147

CiaAssTarifaVôo

ParisEtoile10000KAir FrancePorto AlegrePampa20000KVarig

SedePresid.Faturam.Nome

Passageiros

Vôos

Cia_Aéreas

Reservas


Exemplo de FragmentaçãoFragmentação Horizontal - base AF


TelefoneNome

Gabriel SilvaAir France 147Maria SilvaAir France 147José CamposAir France 147

PassageiroNome Vôo

Air France500750,00Air France 455Air France2501000,00Air France 147

CiaAssTarifaVôo

ParisEtoile10000KAir FranceSedePresid.Faturam.Nome

Passageiros

Vôos

Cia_Aéreas

Reservas


Exemplo de FragmentaçãoFragmentação Horizontal - base RG


TelefoneNome

Cláudio SilvaVarig 224Gabriel SilvaVarig 224

PassageiroNome Vôo

Varig150500,00Varig 224CiaAssTarifaVôo

Porto AlegrePampa20000KVarigSedePresid.Faturam.Nome

Passageiros

Vôos

Cia_Aéreas

Reservas


Exemplo de FragmentaçãoFragmentação Vertical – base Voo-1


TelefoneNome

500,00Varig 224750,00Air France 455

1000,00Air France 147TarifaVôo

10000KAir France20000KVarigFaturam.Nome

Passageiros

Vôos

Cia_Aéreas


PassageiroNome Vôo

Reservas


Exemplo de FragmentaçãoFragmentação Vertical – base Voo-2


PassageiroNome Vôo

Varig150Varig 224Air France500Air France 455Air France250Air France 147

CiaAssVôo

ParisEtoileAir FrancePorto AlegrePampaVarig

SedePresid.Nome

Vôos

Reservas


TelefoneNome

Passageiros

Cia_Aéreas


ParisEtoile10000KAir France

SedePresid.Faturam.Nome

Cia Aérea - FH Primária

Air France500750,00Air France 455Air France2501000,00Air France 147

CiaAssTarifaVôo

Vôos - FH Derivada

Exemplo de FragmentaçãoFragmentação Horizontal Derivada

9


Requisitos de Informação para o PDBD

Info da base de DadosRelacionamentos, Cardinalidade

Nome Faturam. Presid. Sede

Vôo Tarifa Ass Cia Nome Telefone

PassageiroVôo

Cia_Aérea

Vôos Passageiros

Passagens

L1

L2 L3



Processamento Distribuído de Consultasconversão de transações do usuário em instruções de manipulação de dadosProblema de otimizaçãomin{custo = transmissão dados + process. local}formulação geral do problema é NP-difícil


Tradução automática das consultas em linguagemde alto nível

base distribuída é vista como única pelo usuárioA tradução deve ser correta.O plano gerado deve ser ótimo.

O processamento trabalha em quatro fases: a decomposição da consultaa localização dos dadosa otimização globala otimização local




Localização dos DadosTransforma consulta algébrica em consultaequivalente sobre uma base fragmentada.

Analisa predicado da consulta e função de fragmentaçãoAvalia geração de fragmentos vazios

A consulta pode ser reduzida


Processamento Distribuído de ConsultasFragmentação Horizontal na tabela Vôos

Vôo Tarifa Ass CiaAir France 147 1000,00 250 Air FranceAir France 455 750,00 500 Air France

Vôo Tarifa Ass CiaVarig 224 500,00 150 Varig

Nó 1

Nó 2

Nó 3Nó 4

Nó 5Rede de

Comunicação

Voo-RG

Voo-AF


Localização dos Dados

select Vôo, tarifa from vôos where Cia = “Air France”

select Vôo, tarifa from vôo-A where Cia = “Air France”UNIONselect Vôo, tarifa from vôo-V where Cia = “Air France”

select Vôo, tarifa from vôo-A where Cia = “Air France”

Transformação

Análise do predicado da consulta e da função de fragmentação

Avaliação da geração de fragmentos vazios

Redução da consulta

10


Localização dos Dadosselect Vôo, tarifa from vôos where tarifa <= 1000.00

select Vôo, tarifa from vôo-A where tarifa <= 1000.00UNIONselect Vôo, tarifa from vôo-V where tarifa <= 1000.00

NesteNeste casocaso nãonão hháá redureduççãoão, , masmas pode haverpode haver paralelismoparalelismo

Transformação





Otimização Global

Gera o plano de execução ótimo a partir daconsulta fragmentada

técnicas de otimização heurísticas e sistemáticas.cálculo do custo

Custo de Custo de E/SE/S(operações de acesso ao disco)(operações de acesso ao disco)

Custo de CPU Custo de CPU (operações de processamento)(operações de processamento)

Custo de comunicação Custo de comunicação ((movimentaçãomovimentação dos dados dos dados entreentre osos nósnós))


Processamento Distribuído de ConsultasFragmentação Vertical em Vôos

Vôo Ass CiaAir France 147 250 Air FranceAir France 455 500 Air FranceVarig 224 150 Varig

Vôo TarifaAir France 147 1000,00Air France 455 750,00Varig 224 500,00

Nó 1

Nó 2

Nó 3Nó 4

Nó 5Rede de

Comunicação

Voo-1

Voo-2


Localização dos Dados

select Vôo, tarifa from vôos where tarifa <= 1000.00

select Vôo, tarifa from vôo-1 where tarifa <= 1000.00JOINselect Vôo, tarifa from vôo-2 where tarifa <= 1000.00

Transformação




select Vôo, tarifa from vôo-1 where tarifa <= 1000.00


Questões no Processamento de Consultas Distribuído

Espaço de soluções pode ser muito grandeAvaliação “custo otimização” X “custo execução”Intervalo entre a otimização e re-otimizaçãoMudanças na distribuição dos dados

desbalanceamento de cargadistribuição dinâmica



Controle de Concorrência Distribuídosincronização de acessos concorrentesconsistência versus concorrênciaProblemas

Gerência de cópias múltiplasFalhas locais em nósFalha nas ligações de comunicaçãoFinalização (commit) distribuídaBloqueio perpétuo (deadlock) distribuído

ProblemasProblemas muitomuito complexoscomplexos e e aindaainda emem abertoaberto......

11


Controle de Concorrência Distribuído

Alternativas de Implementaçãotempos separados para leitura e modificação

2 cópias da base da dados distribuída 1 para consultas, 1 para atualização

atualizações periódicas na base de consultas



Confiabilidade

Como tornar o sistema tolerante a falhas

SGBDs componentes, rede de comunicação

Durabilidade e Atomicidade


Relações entre os Desafios


Questões Relacionadas aos SBDD

Suporte do Sistema OperacionalSGBDs não são uma aplicação como outraqualquer... suporte apropriado a operações de bancos de dados

Situação ainda mais crítica no caso dos SBDDsEx: suporte a transações distribuídas com controle de concorrência e reconstrução

requisitos de processamentopropósito geral + SBBDs


Questões Relacionadas aos SBDD

Processamento de Transações DistribuídoManter um estado consistente da base de dados com replicaçãoprotocolos sofisticados de controle de réplicas.

O método mais imediato é o ROWA (read one write many),

muito caro.Avaliar três tipos de replicação

replicação dos dadosreplicação do processamentoreplicação da comunicação


O que está disponível hoje no mercado?

Trabalho: Pesquisar produtos abaixo e elaborar um relatório técnico descrevendo as funcionalidades de distribuição

Oracle 10gSQL ServerIBM InformixPostgreSQL 8.1

12

As Novas Tecnologias e osSBDDs


As Novas Tecnologias e os SBDDs

Novas aplicaçõesInerentemente distribuídasRequisitos cada vez maiores por mais desempenhoTrabalho cooperativo, mineração de dados, ...Desenvolvimento baseado em componentes

Utilização combinada com recursos de paralelismo disponíveis nos produtos existentes

Oracle Real Application ClusterCompaq NonStop SQL


As Novas Tecnologias e os SBDDs

Gerência de dados na WebNecessidade de convergência entre 2 culturas distintas

Sistemas XML-nativos, conversores XML-bases relacionais, linguagens de consulta a dados XML (XQuery, XPath), máquinas de busca

InteroperabilidadeMudanças de tecnologia

Arquiteturas multi-camadas, serviços webclusters e GRIDs

Webcrescimento explosivo de dados semi/não estruturados, troca de

informações(HTML, XML, WSDL)

SGBDsserviços de gerência de dados

tradicionais(armazenamento, consulta, modelos de

dados, integridade e consistência)

Documents

Bancos de Dados Distribuídos - uniriotec.brConceito em busca de uma definição consensual, amplamente utilizadofernanda.baiao/BDDDW/Slides/03 - BDD - Visao... · 2006-10-7