Paralelismo em
Banco de Dados
Fernanda Baião
[email protected]
O Problema
Aplicações que requerem
alto desempenho
Grande volume de dados
Alto número de requisições ao banco de dados
e/ou
Requisições (consultas/atualizações) muito demoradas
aumento de disponibilidade / confiabilidade
replicação de dados
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
2
Processamento Paralelo
Tradicionalmente utilizado para obtenção de alto
desempenho em aplicações de bancos de dados
Opções arquiteturais
Servidores Paralelos + SGBDs paralelos
Clusters de PCs + SGBDs para clusters
Clusters de Bancos de Dados!
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
3
1
Cluster de Bancos de Dados
“Cluster de PCs executando, em cada nó,um
Sistema Gerenciador de Bancos de Dados
padrão.” (Akal, 2002)
SGBDs
Seqüenciais
Utilizados como componentes do tipo “caixa-preta”
Paralelismo
Implementado através de uma camada intermediária
de software (middleware)
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
4
Cluster de Bancos de Dados
Cluster de PCs
SGBD
SGBD
Clientes
Camada
Intermediária
SGBD
SGBD
SGBD
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
5
Processamento Paralelo e
Bancos de Dados
Propriedades de um sistema paralelo ideal
Aceleração linear
(linear speed-up)
Paralelismo em Bancos de Dados
Crescimento linear
(linear scale-up)
Equipe Pargres, Fernanda Baião
6
2
Paralelismo em Bancos de
Dados
Características de SBDP
Distribuição dos Dados
Fragmentação
Replicação
Processamento e otimização de consultas
Paralelismo inter-consultas
Paralelismo intra-consulta
Gerência de Transações
Balanceamento de Carga
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
7
Características de SBDP
Distribuição de dados
Fragmentação
Replicação
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
8
Fragmentação
☺ Alternativa bastante explorada na literatura
☺ Vários trabalhos apresentam bons resultados com o
emprego de tal técnica
Exige novo projeto físico para o banco de dados
Exige a implementação de middleware com funções
complexas para a execução de consultas
Pode exigir troca de grandes quantidades de dados
entre os nós durante o processamento de uma
consulta
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
9
3
Replicação
☺ Torna simples a migração do banco de dados
☺ Elimina a necessidade de um novo projeto físico
☺ Middleware pode ser mais simples do que na solução
que emprega fragmentação
Requer técnicas especiais para a manutenção da
consistência entre as réplicas
Atualização de cópias primárias x qualquer cópia
Eager replication x lazy replication
Aplicações com bases de dados muito grandes teriam
dificuldades em utilizar essa solução por restrições de
espaço de armazenamento
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
10
Características de SBDP
Processamento e otimização de consultas
Paralelismo inter-consultas
Execução concorrente de múltiplas consultas de diversos
usuários
Cada consulta é executada seqüencialmente
Aumento de vazão
Paralelismo intra-consulta
Decomposição de uma única consulta em sub-consultas
Execução paralela de múltiplas sub-consulta
Redução do tempo de execução da consulta
Paralelismo Inter-C e Intra-C combinados?!
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
11
Características de SBDP
Balanceamento de carga
Uniformizar o esforço de cada nó de processamento
Distribuindo as requisições ao BD
Distribuindo os dados
Objetivos
Evitar sobrecarga de um nó
Tirar proveito do multiprocessamento
Restrições
em que nós estão armazenados os dados acessados pela
requisição?
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
12
4
Solucões existentes de
paralelismo em clusters de BD
SGBDs para clusters
PGCluster
SmaQ
Comerciais
Clusgres
MySQL Cluster
Oracle 10g (Real Application Cluster)
DB2 ICE (Integrated Cluster Environment)
Clusters de Bancos de Dados
Paralelismo Inter-Consultas
Leg@Net
C-JDBC
Paralelismo Intra-Consulta
PowerDB
Inter + Intra
Pargres (!!!!)
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
13
Leg@Net
França
Lip6, Prologue Software,
ASPLine
Explora arquitetura de
clusters de bancos de dados
usando replicação
Propõe modelo para
balanceamento de carga e
garantia de consistência
entre as réplicas
Paralelismo inter-consultas
Código aberto, linux
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
14
PowerDB
Suíça
Instituto Federal de
Tecnologia de Zurique
Explora arquitetura de
clusters de bancos de dados
usando Fragmentação virtual
tamanho fixo dos fragmentos
Propõe técnicas de
roteamento de consultas
para balanceamento de
carga
Paralelismo intra-consulta
para aplicações OLAP
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
15
5
MySQL Cluster
Explora arquitetura de
clusters de bancos de
dados usando
replicação
Trabalha com os dados
em memória principal
Paralelismo inter
consultas
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
16
C-JDBC
Middleware com API padrão
para permitir a conexão de
aplicações Java com uma
grande variedade de SGBDs
relacionais
Explora arquitetura de
clusters de bancos de dados
fornecendo transparência à
aplicação
Possui recursos para
balanceamento de carga,
cache de consultas e
recuperação a falhas
Paralelismo inter-consultas
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
17
Postgres-R
Suíca
Modificação do código-fonte do
Postgres para ganhar
características de SGBD
paralelo
Explora arquitetura de clusters
de bancos de dados usando
replicação total
Propõe técnicas de controle de
concorrência e protocolo eager
replication para atualização de
réplicas
Arquitetura multi-master
Não trata balanceamento de
carga
Paralelismo inter consultas
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
18
6
Avaliação das soluções
existentes
Balanceamento de carga
Itens
Circular
Circular
Com
peso
Modelo de
replicação
Paralelismo de
consultas
Aplicação foco
Intra
OLTP
Benchmark
MRPP
Parcial
Total
Inter
OLAP
Leg@net
3
-
-
-
3
3
-
3
-
PowerDB
3
-
3
-
3
3
3
-
3
TPC-W
C-JDBC
3
3
3
3
3
3
-
3
-
TPC-W
TPC-R
PostgresR
3
-
-
-
3
3
-
3
-
Benchmark
próprio
MySQL
Cluster
3
-
-
3
-
3
N/A
3
-
Benchmark
próprio
SmaQ
-
-
3
-
3
3
3
-
3
TPC-H
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
19
ParGRES:
Alto desempenho em
Aplicações OLAP
Fernanda Baião
Departamento de Informática Aplicada
- UNIRIO
[email protected]
Cenário
Tomada de Decisões
Tomar a ação apropriada
considerando-se níveis de
risco e incerteza
assumidos
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
21
7
Realidade dos BD
corporativos
Sales
Marketing
Finance
Demographics
Customer
Service
Rates
MIS
General Ledger
Promotions
Product Planning
Contracts
Product Info
Market Data
Purchasing
Accounting
Competitive Info
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
22
O que queremos?
Informação!
Mas, de que forma?
Com :
Agilidade
Flexibilidade
Uma única versão da verdade
Sales
Paralelismo em Bancos de Dados
Marketing
Finance
Rates/
Regulatory
Customer
Service
MIS
Product Data
Customer Data
Sales Data
Market Data
G/L Data
Revenue Data
Equipe Pargres,
Fernanda
External
Data Baião
23
Data Warehouse
“Uma coleção de dados...
Orientados ao assunto
Integrados
Não voláteis
Variantes no tempo
... Para fornecer suporte ao processo de tomada de decisões
na organização” [Inmon, 92]
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
24
8
Ambiente de Data
Warehouse
BDs Operacionais
Integrar dados de múltiplas fontes
Facilitar o processo de análise sem
impacto para o ambiente de dados
operacionais
Obter informação de qualidade
DW
Atender diferentes tipos de usuários
finais
Flexibilidade e agilidade para
atender novas análises
Aplicação
SD
Paralelismo em Bancos de Dados
Ferramenta Aplicação
DBMKT
OLAP
Equipe Pargres, Fernanda Baião
25
Aplicações OLAP
(On-Line Analytical Processing)
Objetivo
Apoio à tomada de decisões
Características principais
Consultas de alto custo
Demandam muito tempo de processamento
Envolvem grande volume de dados
Ad-hoc (Gorla, 2003)
Operações de atualização “controladas”
Realizadas em períodos pré-definidos
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
26
Questões críticas no
ambiente de DW
Envolvimento dos usuários
Abordagem incremental e iterativa
Apresentação dos dados
simplicidade, clareza de semântica, níveis distintos
de detalhe
Esteja preparado para mudanças
Desempenho
Otimização de consultas OLAP!!!!!!!!!
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
27
9
Problema
Como obter alto desempenho no
processamento de consultas OLAP
de alto custo?
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
28
Desafio
Como obter alto desempenho no
processamento de consultas de alto
custo?
de maneira pouco dispendiosa?
dispendiosa
de maneira não intrusiva?
intrusiva
mantendo os programas de aplicação e os acessos
ao SGBD intactos
não mudando de SGBD
não alterando o esquema lógico do banco de dados
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
29
Processamento Paralelo
Opções Arquiteturais
Servidores Paralelos + SGBDs paralelos
Clusters de PCs + SGBDs para clusters
Clusters de Bancos de Dados!
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
30
10
Cluster de Bancos de Dados
(Relembrando…)
“Cluster de PCs executando, em cada nó,um
Sistema Gerenciador de Bancos de Dados
padrão.” (Akal, 2002)
SGBDs
Seqüenciais
Utilizados como componentes do tipo “caixa-preta”
Paralelismo
Implementado através de uma camada intermediária
de software (middleware)
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
31
Cluster de Bancos de Dados
Cluster de PCs
SGBD
SGBD
Clientes
Camada
Intermediária
SGBD
SGBD
SGBD
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
32
Paralelismo em Bancos de
Dados
Características de SBP
Distribuição dos Dados
Fragmentação
Replicação
Processamento e otimização de consultas
Paralelismo inter-consultas
Paralelismo intra-consulta
Gerência de Transações
Balanceamento de Carga
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
33
11
Distribuição de dados
Fragmentação
Horizontal
Vertical
Paralelismo em Bancos de Dados
Replicação
Total
Parcial
Equipe Pargres, Fernanda Baião
34
Fragmentação
Vantagens
Desvantagens
Alternativa bastante explorada
na literatura
Exige novo projeto físico para o
banco de dados
Vários trabalhos apresentam
bons resultados
Exige a implementação de
middleware com funções
complexas para a execução de
consultas
Pode exigir troca de grandes
quantidades de dados entre os nós
durante o processamento de uma
consulta
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
35
Replicação
Vantagens
Desvantagens
Torna simples a migração do
banco de dados
Middleware pode ser mais simples
Elimina a necessidade de um
novo projeto físico
Requer técnicas especiais para a
manutenção da consistência entre
as réplicas
Exigência de espaço de
armazenamento
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
36
12
Distribuição de dados
Fragmentação
Horizontal
Vertical
Replicação
Total
Parcial
Fragmentação + Replicação!
Fragmentação Virtual
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
37
Fragmentação Virtual
Objetivo: forçar cada SGBD a processar uma mesma
consulta sobre subconjuntos distintos de dados através da
adição de predicados definindo intervalos de dados
Sub -Query
1
PostgreSQL
DBMS
Sub -Query
2
PostgreSQL
DBMS
Sub -Query
3
PostgreSQL
DBMS
Sub -Query
4
PostgreSQL
DBMS
C1
C2
Original
Query
C
C3
C4
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
38
Fragmentação Virtual
Select sum(price) from ITEM
Select sum(price) from ITEM
where item_no >= 1
where item_no >= 250,001
and item_no < 250,001
and item_no < 500,001
Select sum(price) from ITEM
Select sum(price) from ITEM
Select sum(price) from ITEM
where item_no >= 500,001
where item_no >= 750,001
and item_no < 750,001
Paralelismo em Bancos de Dados
and item_no < 1,000,001
Equipe Pargres, Fernanda Baião
39
13
Fragmentação Virtual
Adaptativa
PostgreSQL
DBMS
PostgreSQL
DBMS
Original
C
Query
PostgreSQL
DBMS
PostgreSQL
DBMS
Paralelismo em Bancos de Dados
Subconsultas
Equipe Pargres, Fernanda Baião
40
Processamento e otimização
de consultas
Paralelismo inter-consultas
Execução concorrente de múltiplas consultas de diversos
usuários
Cada consulta é executada seqüencialmente
Aumento de vazão
Paralelismo intra-consulta
Decomposição de uma única consulta em sub-consultas
Execução paralela de múltiplas sub-consulta
Redução do tempo de execução da consulta
Paralelismo Inter-C e Intra-C combinados?!
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
41
Balanceamento de carga
Uniformizar o esforço de cada nó de processamento
Distribuindo as requisições ao BD
Distribuindo os dados
Objetivos
Evitar sobrecarga de um nó
Tirar proveito do multiprocessamento
Restrições
em que nós estão armazenados os dados acessados pela
requisição?
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
42
14
Paralelismo em clusters de BD
Soluções existentes
IntraInterBaixo
Atualiz.
Disp.
consulta consulta
custo
Pargres
■
Cluster de
SGBD
C-JDBC
PGReplicator
Slony-1
PowerDB/FAS
SGBD para
cluster
PowerDB/SVP
PGCluster
Oracle 10g/RAC
MySQL Cluster
Paralelismo em Bancos de Dados
■
■
■
Indep.
de
SGBD
Licença
■
■
■
■
■
LPGL
■
■
■
■
■
■
■
■
■
■
½
■
■
■
?
?
■
■
LGPL
½
■
■
■
■
■
■
■
■
GPL
BSD
■
■
?
?
BSD
Com.
GPL/Com.
Equipe Pargres, Fernanda Baião
43
Pargres
Middleware para clusters de bancos de dados
voltado para consultas de alto custo
típicas de aplicações OLAP
Implementa Paralelismo Inter & Intra-Consulta
Fragmentação Virtual Adaptativa
Utiliza o SGBD livre PostgreSQL
Sem adaptações para execução em clusters de Pcs
http://forge.objectweb.org/projects/pargres
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
44
Pargres
PC-Cluster
PostgreSQL
PostgreSQL
Clientes
PARGRES
PostgreSQL
PostgreSQL
PostgreSQL
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
45
15
Visão Geral solução
Pargres
Application
Server
PostgreSQL
JDBC driver
PostgreSQL
database
JVM
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
46
Visão Geral solução
Pargres
Application
Server
ParGRES
JDBC driver
JVM
Paralelismo em Bancos de Dados
ParGRES
Server
PostgreSQL
JDBC driver
PostgreSQL
database
JVM
Equipe Pargres, Fernanda Baião
47
Visão Geral solução Pargres
JDBC
Internet
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
48
16
Visão Geral solução Pargres
Cluster de PCs
JDBC
JDBC
Internet
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
49
Arquitetura do ParGRES
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
50
Arquitetura do ParGRES
CQP
Translator
CQP
Analisador sintático que
faz parser das consultas
Provê transparência no
paralelismo intra-C
Gramática SQL-99
Recursos não
suportados da linguagem
enviados diretamente ao
SGBD
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
51
17
Arquitetura do ParGRES
CQP
CQP
Componente principal da
arquitetura
Papel de coordenador
Decisão intra-C x inter-C
Composição de
resultados
Gerência das transações
distribuídas
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
52
Arquitetura do ParGRES
Gerência de transações Distribuídas
Time t1
Time t2
W1
R3
R1
R2
ParGRES
DBMS
DBMS
Paralelismo em Bancos de Dados
W1
Time t3
R3
ParGRES
Time t4
R3
ParGRES
ParGRES
R1
R2
W1
W1
R3
DBMS
DBMS
DBMS
DBMS
DBMS
DBMS
Equipe Pargres, Fernanda Baião
53
Pargres
Alto desempenho em consultas pesadas:
escalável, não centralizada
disponibilidade
não necessita modificar a aplicação cliente
independente de fabricante SBGD
uso de hardware commodity
Implementa Paralelismo Inter & Intra-Consulta
Replicação Total e Fragmentação Virtual
Adaptativa
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
54
18
Pargres
Compatível com SQL-ANSI/99
Usa o SGBD livre PostgreSQL versão 8.0.3
Sem adaptações para execução em clusters de Pcs
Desenvolvido em Java
JDBC versão 3.0
Console texto/web
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
55
Pargres Admin
Submissão de
consultas online
Adição/remocão
de NQPs
Atualização do
catálogo
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
56
Comparativo
IntraInterBaixo
Atualiz.
Disp.
consulta consulta
custo
Pargres
■
Cluster de
SGBD
C-JDBC
PGReplicator
Slony-1
PowerDB/FAS
SGBD para
cluster
PowerDB/SVP
PGCluster
Oracle 10g/RAC
MySQL Cluster
Paralelismo em Bancos de Dados
■
■
■
Indep.
de
SGBD
Licença
■
■
■
■
■
LPGL
■
■
■
■
■
■
■
■
■
■
½
■
■
■
?
?
■
■
LGPL
½
■
■
■
■
■
■
■
■
Equipe Pargres, Fernanda Baião
GPL
BSD
■
■
?
?
BSD
Com.
GPL/Com.
57
19
Validação Experimental
Benchmark TPC-H
Supplier
Partsupp
Part
PK: suppkey
50,000 tuplas
PK: partkey, suppkey
4,000,000 tuplas
PK: partkey
1,000,000 tuplas
Lineitem
Orders
Nation
PK: orderkey, linenumber
29,999,795 tuplas
PK: orderkey
7,500,000 tuplas
PK: nationkey
25 tuplas
Region
PK: regionkey
5 tuplas
Customer
PK: custkey
750,000 tuplas
Fator de escala = 5
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
58
Validação Experimental
Cluster de 32 nós no INRIA
Cada nó do cluster
Dois processadores 2.2 GHz Opteron, 2 GB RAM,
30 GB HD.
Nós interconectados em rede Gigabit Ethernet
Instância do PostgreSQL 8
Resultados mediram speed-up das consultas
variando o número de nós do cluster
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
59
Validação Experimental
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
60
20
Trabalhos relacionados e
futuros
Fragmentação física [Furtado e Mattoso - COPPE]
Reduzir o problema do espaço em disco
Projeto CG-OLAP [Tanaka, Baiao, Diniz – UNIRIO]
Aplicação no domínio de Geo-Processamento
Novas técnicas e protocolos de comunicação no cluster
Novas técnicas de distribuição dos dados
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
61
Mais Informações
http://pargres.nacad.ufrj.br
Mattoso et al., ParGRES: uma camada de
processamento paralelo de consultas sobre o
PostgreSQL, Workshop de Software Livre, FISL
2005
Mattoso et al., ParGRES: Middleware para
Processamento Paralelo de Consultas OLAP
em Clusters de Banco de Dados
SBBD-Demos 2005
http://www.objectweb.org/
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
62
Conclusão
Clusters de SGBDs e Processamento paralelo
Aumento de desempenho de aplicações com acesso
intensivo a SGBDs
Baixo custo
Pargres
Uma solução leve para alto desempenho de consultas OLAP
em clusters de BD
Pouco intrusiva
Componentes já consolidados
Cluster de PCs sem uso de hardware específico
Desenvolvimento sobre o PostgreSQL
Padrão SQL-99
Software livre
Paralelismo em Bancos de Dados
Equipe Pargres, Fernanda Baião
63
21
Paralelismo em
Banco de Dados
Fernanda Baião
Equipe Pargres
[email protected]
http://pargres.nacad.ufrj.br
22