Embed Size (px)
Citation preview
1
Sistemas de Bancos de Dados Paralelos
Jorge de Abreu Soares
1. Introdução
À medida que maiores facilidades de hardware e software são oferecidas a desenvolvedores e
usuários, maiores se tornam suas necessidades, servindo assim como energia propulsora para o
avanço tecnológico. Podemos verificar isto na popularização do uso de computadores, seja no
ambiente doméstico, ou profissional, ou mesmo na computação de alto desempenho. Os
processadores e periféricos se tornam cada vez mais rápidos e menos caros, comparativamente aos
seus modelos predecessores.
Acompanhando as tendências, notamos que os softwares possuem e/ou adquirem um volume de
dados crescente. No início dos anos 90, a unidade de referência em armazenamento de dados em
memória primária e secundária, por exemplo, ficavam na ordem dos Kilobytes. Estas unidades
rapidamente migraram para valores em ordens de grandeza superiores. Hoje, avalia−se quantidade
de memória principal de computadores pessoais em Megabytes, e de memória secundária em
Gigabytes. E quando nos reportamos a servidores ou a sistemas de alto desempenho, não é difícil
encontrarmos memórias principais com Gigabytes, e discos rígidos com capacidade na ordem de
Terabytes.
Todavia, apesar da evolução tecnológica, a relação entre o volume de dados armazenados (tanto
em memória primária quanto em memória secundária) e a tecnologia atual que processa estes dados
não cresce proporcionalmente. E esta relação se torna mais crítica quando o assunto é memória
secundária. Por melhores que sejam os resultados obtidos na diminuição do tempo de resposta dos
discos rígidos (tomados aqui como referência), o fator mecânico lhes é intrínseco, o que limita em
muito a possibilidade de reduzir a enorme distância de seu desempenho, quando comparadas às
memórias principais.
Para resolvermos esta questão, devemos nos aproveitar do fato anteriormente mencionado: o
custo de computadores, principalmente os pessoais, permite-nos que os usemos em conjunto, para
que possamos resolver tarefas complexas de maneira fragmentada. Ou seja, se pudermos subdividir
um problema grande e trabalhoso, solúvel apenas por máquinas potentes, entre diversas “boas”
máquinas, de uso geral, estaremos ganhando tanto em desempenho quanto em flexibilidade. E este
foi um motivador para o advento das áreas da Ciência da Computação que estudam as arquiteturas
paralelas e os algoritmos distribuídos e paralelos. E esta vasta área de pesquisa produz diversos
2
resultados interessantes, tanto na paralelização e otimização de algoritmos antes seqüenciais, quanto
na solução de problemas complexos.
Ora, o processamento de grandes bases de dados é um problema complexo! Então, por que não
tentar unir a teoria de sistemas gerenciadores de bancos de dados (SGBDs), com seus algoritmos
sedimentados para processamento de consultas, recuperação de falhas, controle de concorrência,
entre outros, com as técnicas de processamento paralelo? Realmente, as duas linhas de pesquisa são
perfeitamente compatíveis. Por conseguinte, a linha de distribuição e paralelismo em banco de dados
surgiu para criar um novo conceito em processamento de bases de dados.
Em se tratando de SGBDs, o paradigma relacional se mostra perfeitamente compatível com
técnicas de distribuição e paralelismo. Contudo, ele nos deixa carentes quando tratamos com
aplicações do tipo CAD, CAM, CASE e Sistemas de Informações Geográficas, ditas aplicações
não convencionais, que são atendidas com novos paradigmas de processamento de dados: o
Orientado a Objetos [1] e o Relacional-Objeto, ou Relacional Estendido [2]. Estes sistemas de
gerência de dados, que trabalham com estas classes de aplicações, são os chamados Sistemas
Gerenciadores de Bancos de Dados Orientados a Objetos e os Sistemas Gerenciadores de
Bancos de Dados Relacionais-Objeto [1]. E esta maneira alternativa de tratar dados introduz
novos problemas.
A orientação a objetos, no contexto de gerência de dados, oferece-nos inúmeras soluções,
contudo apresentando diversos problemas [3]. Como exemplos, podemos citar a avaliação de
predicados de consultas, que deverão gerar planos de execução em paralelo; a alocação estática
e/ou dinâmica de objetos entre os nós integrantes do sistema multiprocessado, a gerência de
estruturas de dados mais complexas, tais como estruturas espaciais; entre outras. E, dentre estas
questões, temos disponíveis diversas arquiteturas de memória para sistemas de bancos de dados
paralelos. Precisamos de um indicador de qual seria a arquitetura mais indicada para certas
situações de processamento.
2. Paralelismo em Operações de Entrada e Saída em Disco
2.1 Discos RAID
Os discos RAID (Redundant Array of Inexpensive Disks) [4] buscam resolver o problema da
limitação evolutiva da capacidade de vazão dos discos magnéticos, da mesma forma que as
arquiteturas paralelas fazem: organizar diversos módulos simples de discos, construídos com
tecnologia padrão, e com preço acessível, pode oferecer um desempenho que, a princípio, seria igual
3
à soma dos desempenhos individuais dos componentes. Todavia, a solução não é tão simplória
quanto aparenta.
Nos discos RAID, a confiabilidade é um problema crítico. Considerando idênticos os
componentes utilizados na construção de um RAID, o tempo médio entre falhas (Medium Time
Between Failures − MTTF) do conjunto será igual ao MTTF de um disco, dividido pelo número de
discos. Com isso, mecanismos de tolerância a falhas tornam-se extremamente pertinentes.
Para implementar estes mecanismos, há diversas técnicas, que se valem do mesmo princípio: o
uso de informação redundante. Para isto, existem cinco soluções que implementam esta
redundância, desde o espelhamento total das informações de todos os discos (RAID Nível 1, que
necessita do dobro do número de discos), até implementações que geram bits de paridade de grupos
de informação (setores), espalhados pelos diversos discos do conjunto (RAID Nível 5).
Sistemas RAID são bem eficazes para acessos chamados "grandes", onde um volume
considerável é lido e/ou escrito. Leituras ditas "pequenas" têm bom desempenho em RAIDs dos
níveis 4 e 5. Entretanto, as escritas "pequenas" (de tamanho próximo a um setor por disco) deixam
muito a desejar, não tendo desempenho satisfatório em nenhuma alternativa. Logo, a sua utilização
ainda depende de melhoramentos. Além disso, discos RAID são inerentemente de difícil expansão,
pois há um número máximo de discos que podem ser ligados a uma máquina.
Em 1993, VALDURIEZ [5] menciona o fato de discos RAID serem uma promessa de alto
desempenho para sistemas de entrada e saída. Se utilizados com sistemas de bancos de dados
paralelos, poderiam resultar em uma interessante combinação de elementos, de forma a aumentar
consideravelmente a vazão e a diminuição do tempo de resposta em sistemas paralelos. Contudo, o
seu uso seria limitado a arquiteturas não distribuídas.
E podemos notar que esta previsão de fato se concretizou. Os discos RAID têm hoje uma
aceitação muito boa no mercado, pelo que eles oferecem em termos de desempenho. Isto se deve
muito ao fato de que a otimização do desempenho de um único disco ser difícil, pelos elementos
mecânicos envolvidos. Discos RAID oferecem alto desempenho com uma solução relativamente
simples, quando comparada a esta tarefa complicada de otimização. Cabe ressaltar, contudo, que
esta solução não foi tão aproveitada em sistemas gerenciadores de bancos de dados.
2.2 Sistemas de Arquivos Paralelos
Esta classe implementa o acesso paralelo a disco de uma forma diferente. Nos sistemas de
arquivos paralelos, os discos são distribuídos entre nós processadores interconectados, dedicados à
entrada e saída, e que se apresentam ao usuário como um único sistema de arquivos. Requerem
4
uma rede de interconexão de alta velocidade, pois o acesso a arquivos podem estar ocorrendo
concorrentemente por nós clientes. A Figura 1 exemplifica este esquema.
Figura 1 Arquitetura genérica de um sistema de arquivos paralelos
3. Desempenho de Sistemas de Bancos de Dados
Alguns fatores importantes são usados quando comparamos sistemas paralelos, e características
relacionadas a essas medições servem como um bom indicador no seu desempenho.
3.1 Medidas de desempenho
Cabe apresentar aqui duas formas de medidas fundamentais: a aceleração e a escalabilidade.
A aceleração (speedup) é a capacidade de o sistema desempenhar uma determinada tarefa em
um tempo tantas vezes menor quanto a quantidade de recursos adicionais no equipamento ou
sistema. Se esta relação for constante, ou seja, a razão entre o adicional de recursos e o tempo não
variar, diz-se que esta aceleração é linear. Seja T1 o tempo de execução serial de uma tarefa, e TN
o seu tempo de execução em uma versão paralela. Sendo assim:
NTT
oaaceleraç 1~ =
Já o conceito de escalabilidade (scale up) está relacionado ao fato de o sistema desempenhar
uma tarefa N vezes maior com N vezes mais hardware, e com um intervalo de tempo constante. A
relação pode ser explicitada como:
escalabilidadetempo do sistema de menor capacidadetempo do sistema de maior capacidade
=
Podemos classificar a escalabilidade em dois diferentes tipos [6]: transacional e de lote . Na
primeira, espera-se que um job com N pequenas tarefas seja N vezes mais rápido no acesso
compartilhado a um banco de dados N vezes maior, com N vezes mais clientes enviando requisições
5
ao banco. Este é a escalabilidade encontrada normalmente em sistemas de processamento e de
compartilhamento de recursos. O outro tipo de medida de escalabilidade é caracterizado pela
existência de uma única tarefa, N vezes maior, acessando uma base aumentada de um fator de N, e
que será resolvida por um sistema de computação N vezes maior. Esta última categoria é a que
melhor se aplica a consultas a bases de dados.
Estes conceitos servem como unidades de medida importantes para se avaliar sistemas paralelos,
e os de banco de dados incluem-se na regra. Um sistema de gerência de dados paralelo deve, à
medida que mais processadores são acrescentados à sua máquina hospedeira, ter um rendimento
próximo ao linear. Porém, a partir de um certo ponto, o sistema começa a ter seu desempenho
degradado, devido à alta taxa de comunicação entre os diversos nós.
Podemos enuimerar algumas barreiras genéricas à obtenção de escalabilidade e aceleração
linear [6]:
§ Tempo de inicialização: o tempo para tornar uma tarefa ativa. Se tivermos de inicializar
milhares delas, este tempo influirá no resultado final.
§ Interferência: uma nova tarefa que inicia causa uma redução na atividade das demais quando
do acesso ao recurso compartilhado.
§ Distorção (Skew): é caracterizado quando uma determinada tarefa mais lenta faz com que
todas as demais, que tiveram uma mesma média de tempo de execução, esperem por ela,
aumentando com isso o tempo de parede (elapsed time), o qual representa a variação de tempo
entre a submissão de um processo e sua resposta final.
3.2 Medidores de Desempenho (Benchmarks)
Benchmarks são conjuntos de programas, ou seções de programas-chave, os quais são
executados para obtenção de medidas de tempo [7].
Existem na literatura quatro tipos de programas usados para estas medidas, listados abaixo em
níveis decrescentes de acurácia na predição do desempenho.
• Programas Reais: Conjunto de programas que o usuário normalmente executa em sua
instalação. Como exemplo, temos os compiladores, processadores de texto, ferramentas de
projeto, entre outros.
• Kernels: Subconjunto dos programas−chave, que têm os códigos mais demorados. Entre os mais
famosos, encontramos o LINPACK, que consiste em um conjunto de rotinas usadas para resolver
sistemas de equações lineares. Os seus relatórios incluem máquinas que vão desde um IBM PC
6
compatível, até os mais poderosos super computadores. Kernels são melhores utilizados quando
queremos obter dados a respeito de particularidades de uma determinada máquina.
• Toy Benchmarks: Pequenos programas (normalmente de 10 até 100 linhas) que produzem um
resultado previamente conhecido. Quicksort é um exemplo de algoritmo desta categoria.
• Benchmarks Sintéticos: São programas que tentam simular a freqüência média de operações e
operandos de um grande conjunto de programas. Ao contrário dos Kernels, que são partes
representativas de programas importantes, os sintéticos jamais são executados em funcionamento
normal. Whetstone and Dhrystone são exemplos típicos.
VALDURIEZ [5] atenta para o fato de que sistemas de bancos de dados paralelos requererão
benchmarks específicos para sua avaliação, por serem a única maneira imparcial de averiguar a
relação preço/desempenho com uma determinada carga de trabalho. Como já existem diversos
benchmarks que testam sistemas centralizados, tanto em tarefas simples ou complexas, é
necessário que esta experiência seja útil na confecção de benchmarks para sistemas paralelos, de
forma a pressionar uma situação de aceleração e/ou escalabilidade lineares.
4. Sistemas de Bancos de Dados Paralelos
Os sistemas gerenciadores de bancos de dados são softwares com uma natureza muito
particular. Enquanto os aplicativos em geral têm um foco muito voltado ao uso intensivo da unidade
central de processamento, e no acesso a dados residentes em memória principal, os SGBDs têm
como maior responsabilidade o acesso a dados armazenados em discos magnéticos. E já é sabido e
constatado há bastante tempo que o custo de acesso a dados armazenados em memória secundária
é muitas ordens de grandeza maior que o mesmo acesso a dispositivos de memória primária. Isto
está intrinsecamente relacionado à natureza eletro-mecânica dos discos magnéticos rígidos. Todo
procedimento que envolva movimentação mecânica é dispendioso, e intrínseco no caso dos discos
rígidos, devido à sua própria arquitetura.
Os SGBDs mostraram-se indispensáveis no âmbito da gerência de dados ao longo destes últimos
30 anos, por oferecerem às outras aplicações a possibilidade de desempenhar tarefas
essencialmente funcionais. Com isso, a aplicação não mais se preocupa com questões inerentemente
ligadas aos dados, delegando aos SGBDs esta tarefa, e passando a focar essencialmente as regras
de negócio. Esta demanda foi crescendo de tal forma que, após algum tempo, as arquiteturas de
computadores disponíveis não eram capazes de executar com a mesma eficiência as requisições
submetidas aos SGBDs, por estes exigirem o máximo do poder de processamento daquelas
máquinas. Isto motivou a busca por desempenho na gerência de dados.
7
A primeira tentativa surgiu com as máquinas de bancos de dados. Estas consistiam em um
hardware e um sistema operacional especialmente dedicados a otimizar leituras e escritas em
discos magnéticos rígidos. Inclusive, esta é a filosofia utilizada nos videogames, onde o hardware é
projetado para dar o máximo desempenho nas operações de vídeo (resolução, número de cores,
freqüência horizontal e vertical, entre outros). Com isso, buscava−se atingir um elevado desempenho
no acesso e no tratamento de dados e transações (controle de concorrência, recuperação de falhas,
otimização de consultas, controle de segurança, entre outros). Sistemas como DBS3 [8], NonStop
SQL [9], BUBBA [10] e GAMMA [11] são exemplos de máquinas de bancos de dados, sendo que
as versões mais atuais dos dois últimos sistemas foram convertidas para trabalharem em
arquiteturas genéricas.
Contudo, esta solução não se mostrou tão boa para a gerência de dados quanto foi para os jogos
eletrônicos. O custo de uma máquina de banco de dados era proibitivo, além de possuir um uso
muito específico. Isto revelou que este não era o caminho para a obtenção de desempenho para
acesso a bases de dados. A resposta estaria em uma solução que oferecesse desempenho a um
custo mais baixo, e que permitisse um uso mais geral do hardware envolvido.
Com isso, as pesquisas na área voltaram−se para o uso da distribuição e o paralelismo na
gerência de dados. A fragmentação da base entre diversos nós de computação apresentou−se uma
solução mais econômica em termos de hardware. Contudo, estas soluções naturalmente trouxeram
agregadas outras questões e outros problemas.
No caso do paralelismo em gerência de dados, diversos trabalhos na literatura respondem a
várias destas indagações, e outros propõem novas soluções. Atacamos, neste trabalho, o problema
da avaliação de desempenho dos diversos modelos de memória de SBDP (Sistemas de Bancos de
Dados Paralelos). Contudo, introduziremos a seguir o assunto, apresentando esta nova classe de
gerentes de dados, e apresentando suas particularidades.
5. Caracterização de Sistemas de Bancos de Dados Paralelos
A grande maioria dos sistemas de bases de dados paralelos funciona na verdade como um
servidor a múltiplos clientes [12], dentro da conhecida arquitetura cliente-servidor. Fica então a
cargo do servidor realizar as operações mais custosas e que de fato necessitam ser paralelizadas,
almejando a melhoria de desempenho. Ao cliente, cabe a tarefa de servir de interface ao usuário
final, tendo todas as ferramentas de interface, linguagens de quarta geração, entre outros. Assim,
uma divisão de tarefas fica bem definida, deixando livre diversas características que não poderiam
ser menosprezadas no modo seqüencial de processamento, como a arquitetura do cliente. Este pode
variar de um computador pessoal até mesmo um computador de grande porte.
8
Então, espera-se de um Sistema Paralelo de Banco de Dados (SPBD) as seguintes qualidades:
s Alta confiabilidade : O SPBD deve, antes de tudo, ser capaz de garantir aos seus usuários que
o sistema será capaz de se recuperar de possíveis falhas ocasionais. A robustez é então uma
característica fundamental nesta classe de aplicativos. E isto é conseguido então com a
replicação de dados. Poder ter disponível uma cópia de reserva de parte do banco (ou mesmo
de todo ele) garante um caminho alternativo de acesso, não causando queda imediata no
funcionamento do sistema. Porém, este tipo de procedimento cria uma nova preocupação: a
consistência das cópias da base de dados. Mecanismos devem, portanto, ser implementados, de
forma que os dados reflitam o real estado do banco de dados.
s Expansibilidade : Capacidade de incrementar o poder de processamento e armazenamento da
máquina, com um mínimo de reorganização do banco de dados, e com aumento de aceleração e
escalabilidade mais próximo possível do linear, que a princípio seria o ideal.
Definidos os objetivos iniciais, como então desenvolver sistemas paralelos de gerência de dados
utilizando a tecnologia mais barata, acessível, e que seja de propósito geral, em nada se
assemelhando às máquinas de banco de dados? Fica então a cargo do software explorar técnicas de
paralelismo sobre a operação-mestre de qualquer SGBD: a consulta.
Logo, existem três possíveis formas de paralelismo que podemos adotar:
s Paralelismo entre consultas : associa-se a cada processador ou grupo deles executar uma ou
mais consultas, atendendo a uma demanda concorrente de transações
s Paralelismo dentro de consultas : uma mesma consulta é particionada entre os processadores,
de forma que cada um deles opera sobre um conjunto diferente de dados, executando contudo a
mesma operação
s Paralelismo dentro de operações: é a otimização de uma determinada consulta, através da
utilização de subrotinas, além da divisão dos dados.
5.1 Balanceamento de Carga
A idéia do balanceamento de carga baseia -se em designar a um processador (ou grupo de
processadores) um volume de tarefas suportável. Por exemplo, se temos um processador P1 com o
dobro do desempenho de outro P2, enviar-se-ia a princípio um número duas vezes maior de tarefas
para P1 do que se mandaria para P2. Situações onde um processador termina uma tarefa mais
rapidamente do que outro (por razões outras que não a sua velocidade de execução de consultas)
caracterizam a necessidade de balanceamento, na tentativa de manter aquele processador ocioso o
menor tempo possível.
9
O desempenho pode ser aumentado se o trabalho for distribuído de maneira uniforme. Se as
tarefas são de tamanhos diferentes, pode ser mais eficiente manter um pool de tarefas, que serão
divididas para cada processador, à medida que eles acabem o seu processamento.
O balanceamento pode ser mais importante em alguns ambientes do que em outros (ambientes
heterogêneos e carga definida pelo usuário; ou ambiente com processadores idênticos rodando um
job por processador).
Sistemas de bancos de dados paralelos devem implementar mecanismos eficientes de
balanceamento de carga, considerando as características físicas de cada um dos nós que integram o
sistema, a fim de obter o máximo de desempenho na execução de transações.
6. Modelos clássicos de arquiteturas paralelas
STONEBRAKER [13] classifica os modelos computacionais em três tipos: memória
compartilhada (shared memory), memória distribuída (shared nothing) e disco
compartilhado (shared disk), conforme descritos nas seções seguintes.
6.1 Memória Distribuída (Shared Nothing)
Aqui, a memória e as unidades de disco são fisicamente distribuídas entre os processadores, só
sendo acessadas diretamente pelo elemento processador correspondente. Com relação à
sincronização, ela é feita através da comunicação entre os processadores, e requisições de dados
não locais devem ser feitos através da rede de interconexão. A Figura 2 ilustra esta arquitetura de
memória.
Uma das maiores preocupações está em como se fazer a decomposição dos dados entre as
Unidades Cenrtais de Processamento (UCPs), de modo a minimizar a comunicação. Algumas
estratégias utilizadas são troca de mensagens, onde tarefas se comunicam pelo intercâmbio de
pacotes de dados; e memória fisicamente distribuída, parecendo, contudo, uma única memória
compartilhada (espaço de endereçamento único).
As vantagens deste modelo podem ser enumeradas como a seguir:
• Custo baixo com a rede de interconexão dos processadores (uso de tecnologia padrão)
• Extensibilidade, pela autonomia dos nós, que permite ao sistema crescer em algo como milhares
de processadores.
• A confiabilidade é outra característica deste tipo de arquitetura, pois uma boa política de
replicação dos dados aumenta a robustez do sistema.
10
Figura 2 Modelo de memória distribuída
Já as suas desvantagens podem ser enumeradas como a seguir:
• Alta complexidade de programação, dada pela necessidade de gerenciamento da base distribuída,
que aumenta com o crescimento do número de nós da máquina.
• Balanceamento de carga complicado, pois está intimamente relacionado com a maneira como os
dados foram particionados fisicamente na carga da base distribuída. A alocação estática de
objetos faz com que a inclusão de um novo nó no sistema exija um novo balanceamento, que
pode ser custoso.
Encontramos diversos exemplos [14] de sistemas de memória distribuída. Alguns dos comerciais
são o DBC da Teradata e NonStop SQL da Tandem. Além disso, diversos protótipos foram
implementados, dentre eles: BUBBA [10], EDS [15], GAMMA [11], GRACE [16], PRISMA [17],
além dos sistemas experimentais SHORE [18] e do ParGOA−MD [19].
6.2 Memória Compartilhada (Shared Everything)
Neste modelo, os processadores que integram o sistema trabalham com a memória e o disco
concorrentemente, onde todos têm acesso comum a estes dois recursos. Uma localização de
memória não pode ter seu valor alterado por uma tarefa, enquanto outra estiver acessando a mesma
localização. Além disso, o compartilhamento de dados entre tarefas é rápido (velocidade de acesso à
memória). A Figura 3 mostra o esquema mencionado.
Este tipo de arquitetura possui as seguintes vantagens:
• Simples de se programar, por o espaço de endereçamento, além de todos os demais controles de
informação, estarem disponíveis a todos os processadores de uma forma global.
• Balanceamento de carga pode ser relativamente fácil, devido à igualdade no acesso ao disco por
parte dos processadores, além de uma boa divisão de tarefas em tempo de execução.
11
• Baixo overhead na comunicação entre os processadores, por eles poderem cooperar
mutuamente via memória principal.
Figura 3 Modelo de memória compartilhada
Porém, encontramos neste modelo as seguintes desvantagens:
• Alto custo de hardware, principalmente no que se refere à interconexão dos processadores, o
que penaliza a expansibilidade da máquina.
• Geração de conflitos ao se acessar a memória (I/O bottleneck), limitando o aumento do número
de processadores.
• A confiabilidade do sistema é baixa, visto que a informação só estará disponível em um único
local, aumentando consideravelmente o risco de quebra do sistema em caso de falha eventual.
• A vazão da rede de interconexão entre os processadores deve ter a capacidade de pelo menos a
soma das vazões dos processadores e discos.
Para minimizar a latência e diminuir o tráfego na rede, cada processador pode ter associado um
cache local. Contudo, o custo de manutenção de coerência dos diversos caches degrada
consideravelmente o desempenho do sistema.
Outra técnica que também pode ser adotada é a de se dividir a memória em partições destinadas
a cada processador. Porém, problemas que existem no modelo de memória distribuída, a ser visto a
seguir, vêm junto com esta solução, não compensando, portanto, por não haver nenhuma
simplificação no hardware com esta medida.
Segundo ÖZSU e VALDURIEZ [14], o primeiro exemplo de sistema paralelo de banco de dados
que se valeu deste modelo apareceu com a implementação do DB2 em um computador IBM3090
com seis processadores [20]. Outros exemplos podem ser encontrados nos sistemas XPRS [21],
DBS3 [22] e VOLCANO [23].
12
6.3 Disco Compartilhado (Shared Disk)
Pode ser resumido como uma variação do modelo de memória distribuída. Cada processador
possui sua própria memória. Todavia, o disco passa a ser um recurso compartilhado por todos os
processadores. Um esquema simplificado pode ser observado na Figura 4.
São vantagens proporcionadas por esta arquitetura:
• Baixo custo, da mesma maneira que no caso de memória distribuída.
• O balanceamento de carga também é facilitado, pelas mesmas razões encontradas no modelo de
memória compartilhada.
• Aumento da confiabilidade do sistema, por os dados ficarem disponíveis em mais de um ponto do
sistema.
Figura 4 Modelo de disco compartilhado
As desvantagens encontradas neste modelo são:
• Aumento na complexidade de gerência de recursos.
• Como no caso da memória compartilhada, a expansibilidade é mais complicada.
• Problemas de desempenho pelo acesso concorrente ao disco.
• Adequado somente a bases de dados que sejam apenas de leitura.
Exemplos de sistemas de disco compartilhado são IMS/VS Data Sharing da IBM, o VAX
DBMS da DEC, a implementação do sistema ORACLE no computador VAXcluster da DEC e nos
computadores NCUBE, e o protótipo ParGOA−V [24].
13
6.4 Modelos híbridos de SGBDs paralelos
6.4.1 ARQUITETURAS HIERÁRQUICAS
Este modelo foi primeiramente proposto por BHIDE [25], depois por PIRAHESH [26], e por
BORAL [10]. Já VALDURIEZ [14,27] oferece duas opções de implementação: ou a de vários nós
(até 512) de memória compartilhada, cada qual com um número pequeno de processadores (quatro
no máximo), ou o inverso, com poucos nós ligados à rede de interconexão, porém com até 32
processadores no nó compartilhado. O autor declara então sua preferência pela primeira opção, já
que o custo de uma rede de interconexão rápida é bem menor que o de um nó compartilhado de
muitos processadores.
Segundo Valduriez, esta arquitetura amortiza os problemas de balanceamento de carga e
complexidade do particionamento do banco. Além disso, a expansibilidade e a simplicidade
encontradas no modelo compartilhado são incorporadas a esta opção. O sistema IDEA [28]
implementa este modelo híbrido.
GRAEFE e DAVISON [29] também propuseram um modelo híbrido chamado modelo de
hierarquias de memória , que possibilita, segundo os autores, um uso extremamente flexível, onde
bases de dados de tamanhos modestos tirariam proveito da arquitetura de um ou mais nós de
memória compartilhada, com o balanceamento de carga, mecanismos de travamento de recursos e
comunicação rápida; enquanto bases de tamanho relevante valer-se-iam dos recursos oferecidos
pelo modelo de memória distribuída, como a escalabilidade e processamento paralelo com um
mínimo de paradas do sistema, quando da ocorrência de saturações. Além disso, o desenvolvimento
de softwares para este modelo de arquitetura possibilitará sua execução nas máquinas de modelos
de memória distribuída e compartilhada (softwares independentes de arquitetura), flexibilizando mais
o seu uso.
O modelo de Graefe/Davison difere do de Valduriez apenas no que tange o acesso ao meio
secundário (disco). O último mostra o uso de um único disco sendo acessado pelos diversos clusters
de memória compartilhada, enquanto os primeiros indicam que cada nó de memória compartilhada
pode ter um ou mais discos. A Figura 5 exemplifica os modelos propostos por VALDURIEZ [14,27]
e por GRAEFE e DAVISON [29], nesta ordem.
Dentre os sistemas que estão evoluindo para esta arquitetura, podemos citar o NCR da Teradata
(que usa nós de memória compartilhada) e o sistema PowerCluster da Bull, com um cluster de nós
PowerPC [14].
14
Figura 5 Modelos híbridos de Valduriez e de Graefe/Davison
6.4.2 ARQUITETURAS NUMA
Também com o objetivo de combinar extensibilidade e flexibilidade, arquiteturas de memória
compartilhada evoluíram em arquiteturas NUMA [14]. O objetivo desta classe de arquitetura é
fornecer um ambiente de programação de memória compartilhada (juntamente com todos os seus
benefícios), em uma arquitetura paralela escalável.
Duas classes de arquitetura NUMA têm emergido: máquinas NUMA de cache coerente
(CC−NUMA: Cache Coherent NUMA) [30], que estaticamente divide a memória principal entre os
nós do sistema, e as arquiteturas de memória com cache único (COMA: Cache Only Memory
Architectures) [31], que converte a memória local de cada processador em um único cache
compartilhado. Com esta segunda solução, a localização de um dado é completamente desvinculada
de seu endereço físico real, e o dado é automaticamente migrado ou replicado na memória principal.
E como memórias compartilhadas e a coerência de caches são suportados por hardware, acessos
remotos à memória são bastante eficientes (apenas algumas vezes maior do que acessos locais)
[14]. A Figura 6 esquematiza uma arquitetura NUMA−COMA.
O que torna as arquiteturas NUMA uma boa opção é o fato de que ela não exige nenhuma
reescrita do programa de aplicação. Entretanto, algumas mudanças são necessárias no sistema
operacional e nos componentes de acesso à base de dados [32].
15
Figura 6 Arquitetura CC−NUMA
Alguns exemplos de computadores NUMA: o ORIGIN 2000, da Silicon Graphics [33], o
KSR1, da Kendal Square Research; o IBM NUMA-Q [34], da IBM; e o SPP1200, da Convex,
que consegue atingir centenas de processadores [14].
7. Sistemas de Bancos de Dados Paralelos Comerciais
Nesta seção, abordaremos alguns dos trabalhos relacionados à gerência paralela de objetos.
Encontraremos diversas implementações feitas usando os modelos de memória explicitados
anteriormente, além de alguns trabalhos que não constróem um modelo em particular, mas que
tentam otimizar o acesso e a fragmentação dos dados da base de objetos.
7.1.1 PRODUTOS COMERCIAIS
Alguns trabalhos [35] caracterizam sistemas paralelos de bancos de dados, inclusive
apresentando estudos de caso de alguns sistemas comerciais. Contudo, daquela época para cá,
diversas novas características apareceram nos sistemas comerciais de bancos de dados paralelos,
principalmente sobre plataformas de hardware do tipo NUMA. Dentre estes produtos, podemos
destacar:
3.2.5.1 DB2/PE [34]
Produto desenvolvido para ser executado sobre diversos modelos de arquiteturas paralelas e
sobre diversas versões de sistemas operacionais, o IBM DB2/PE já possui em seu cartel uma
versão para uma arquitetura CC-NUMA, a máquina NUMA-Q da IBM. Esta arquitetura paralela
16
implementa a idéia de quads, que são grupos (clusters) de processadores que possuem memória e
dispositivos de entrada e saída comuns (como no modelo de memória distribuída). Estes quads estão
interligados por uma via de alta velocidade, chamada IQ-Link.
A arquitetura do IBM NUMA-Q possui as seguintes características:
• Cada quad é um nó de memória compartilhada, contendo quatro processadores Intel IA-32, com
uma memória principal variando de 2 Gbytes até 8 Gbytes, e dois barramentos PCI
independentes para operações de entrada e saída locais.
• A migração de aplicações de memória distribuída para essa arquitetura se torna mais fácil.
• O uso da memória é otimizado, pois todas as aplicações que são executadas nesta arquitetura,
inclusive o sistema operacional, só necessitam de uma cópia carregada na memória.
• O IQ-Link fornece uma conexão de 1 Gbyte por segundo. Além de fazer com que cada quad
acesse a memória de outros quads, este switch permite um gerenciamento dinâmico do sistema.
• As operações de entrada e saída são sempre locais, graças ao mecanismo True Multi-path I/O,
que faz com que os recursos de entrada e saída sejam locais a um subconjunto de UCPs,
reduzindo a competição através do sistema. Além disso, pode-se aumentar a confiabilidade do
sistema, criando-se caminhos redundantes para o mesmo dispositivo de E/S.
• Oferece escalabilidade linear, permitindo um total de 252 processadores por sistema, e com um
máximo de 16 quads (64 processadores), atingindo um total de 64 Gbytes de memória principal,
192 Tbytes de capacidade de armazenamento secundário.
• Suporta tanto o particionamento estático quanto o dinâmico de dados (LPAR-like). Isto permite
que múltiplos bancos de dados sejam executados em um único sistema, sem contenção de
recursos.
O sistema gerenciador de banco de dados IBM DB2-PE se adapta perfeitamente à arquitetura
NUMA-Q. Os nós em um sistema de memória distribuída podem ser criados associando-se quads a
discos específicos, conforme representado na Figura 7.
17
Figura 7 A arquitetura do sistema DB2 com modelo de memória distribuída sobre a máquina
NUMA-Q da IBM [34]
O IBM DB2/PE suporta a distribuição total ou parcial dos fragmentos que são gerados
horizontalmente, através de função de hashing e utilizando o conceito de “grupos de nós”
(nodegroups). Possui também recursos especiais para data warehousing e data mining.
3.2.5.2 Oracle Parallel Server 8i [36,37]
Versão do sistema gerenciador de bancos de dados relacionais Oracle para a arquitetura IBM
NUMA-Q. As versões Oracle 8i [36] e Oracle 7 [37] possuem, dentre outras, as seguintes
características:
• Fornece transparência na fragmentação horizontal primária e derivada, por faixa de valores,
hashing e combinação (faixa de valores + hashing).
• Otimização dinâmica de consultas, baseada no predicado e nas estatísticas do banco.
• Redistribuição dinâmica dos dados.
• Os índices das tabelas fragmentadas também podem ser opcionalmente particionados, junto com
a tabela ou não, ou simplesmente não serem particionados.
• Os fragmentos podem ser independentemente carregados, exportados, importados, analisados,
realocados, truncados ou renomeados. A manutenção dos fragmentos de índices pode ser feita
independentemente dos outros fragmentos.
18
• A técnica partition-wise join aumenta o desempenho de junções em várias tabelas, dividindo
uma grande junção em equivalentes menores nas partições relativas. No caso de execução
paralela, cada subjunção pode ser processada em paralelo por um servidor de consultas
separado, minimizando a troca de dados entre processadores. Existem para esta técnica duas
variantes: a full partition-wise table join , que exige que todas as tabelas sejam particionadas
primariamente sobre o atributo-base da junção, e a very flexible partial partial partition-wise
join , que exige que apenas uma das tabelas fragmentada segundo o atributo de junção.
• Suporte a grandes bancos de dados (até 64 K partições por tabela).
3.2.5.3 Teradata [22]
Sistema gerenciador de bancos de dados relacional, desenvolvida para o paralelismo. Cada
unidade de paralelismo aje como uma unidade do sistema, inclusive ao ponto de possuir seu próprio
dado. As unidades de paralelismo também têm conhecimento de cada uma das outras unidades, e
trabalham cooperativamente.
A unidade básica de paralelismo é chamada Virtual Processor (VPROC), representada na
Figura 8, representa uma implementação lógica do modelo de memória distribuída. Na realidade,
múltiplos VPROCs irão existir simulataneamente em um nó de memória compartilhada, e seu
número irá depender da capacidade do nó compartilhado. Um VPROC simples é uma coleção de
processos UNIX que trabalham juntos em unidade. Cada VPROC controla e gerencia seus dados,
que estão armazenados em discos específicos.
Figura 8 A unidade de paralelismo (VPROC) gerencia todas as atividades do banco
relativas aos seus dados
19
As tuplas de cada tabela do banco são distribuídas aleatoriamente por todos os VPROCs do
sistema. O administrador de banco de dados não tem poder de escolher como esta distribuição será
feita. Este mecanismo garante, segundo os fabricantes, tanto um esforço computacional igualitário
quanto um bom balanceamento de dados de todo o sistema, não importando o quão rápido o banco
cresce ou que tipo de consulta ele sofre. Porém, alcançar este balanceamento depende do grau de
unicidade dos índices primários das tabelas.
3.2.5.4 Outros sistemas
(a) Informix Extended Parallel Server 8.3 [38]
• SGBD relacional que opera em arquiteturas NUMA, ou com memória compartilhada ou memória
distribuída que operem com o sistema operacional UNIX
• Operações específicas para data warehousing
• Além de fornecer diversas modalidades de fragmentação de relações, o sistema permite que o
usuário defina uma expressão de atribuição, envolvendo um atributo da relação
(b) Compaq NonStop SQL/MP [39]
• Máquina de banco de dados, que tira proveito da arquitetura paralela da Compaq
• Modelo de memória distribuída
• Fragmentação horizontal por faixa de valores
• Operações específicas para data warehousing
• Uso de padrões ANSI, ISO e ODBC
• A máquina pode chegar até 4080 processadores
• Tolerância à falhas via duplicação
8. Considerações Finais
Sistemas de Bancos de Dados Paralelos são, como tivemos a oportunidade de mostrar, realidade
de mercado. Aplicações como em atividades de descoberta de conhecimento em bancos de dados
(KDD – Knowledge Discovery in Databases), que exigem muito poder de processamento de
dados, beneficiam-se desta classe de gerentes de dados. Assim, o campo de estudo, apesar de
possuir diversos pontos ainda em aberto, merece especial atenção, dada a sua evidente importância.
20
9. Referências Bibliográficas
[1] CATTEL, R. G. G., Object data Management. Edição Revisada, Addison−Wesley
Publishing Company, Inc., 1994.
[2] DeWITT, D. J., Parallel Object−Relational Database Systems: Challenges &
Opportunities. Invited Talk: PDIS, 1996.
[3] DeWITT, D. J., GRAY, J., “Parallel Database Systems: The Future of High Performance
Database Systems”. Communications of the ACM, v. 35, n. 6, pp. 85-98, 1992.
[4] PATERSON, D. A., GIBSON, G., KATZ, R. H., “A Case for Redundant Array of
Inexpensive Disks (RAID)”. In: Proceedings of the 1988 ACM-SIGMOD International
Conference on Management of Data , Chicago, EUA, Maio 1988.
[5] VALDURIEZ, P., “Parallel Database Systems: open problems and new issues”.
International Journal on Distributed and Parallel Databases, v.1, n. 2, pp. 137-165,
1993.
[6] DeWITT, D. J., GRAY, J., “Parallel Database Systems: The Future of High Performance
Database Systems”. Communications of the ACM, v. 35, n. 6, pp. 85-98, 1992.
[7] CRUZ, A. J. O., Curso de Arquitetura de Computadores II, Apostila não editada,
Instituto de Matemática/UFRJ, Rio de Janeiro/RJ, Agosto 1994.
[8] BOUGANIM, L., DAGEVILLE, B., VALDURIEZ, P., “Adaptative Parallel Query
Execution in DBS3”. In: International Conference on EDBT, França, 1996.
[9] CHAMBERS, L., CRACKNELL, D., “Parallel Features of NonStop SQL”. In:
Proceedings of the 6th International Conference on Parallel and Distributed
Computing Systems (PDCS’93), 1993.
[10] BORAL, H., ALEXANDER, W., CLAY, L., et al., “Prototyping Bubba, A Highly Parallel
Database System”. IEEE Transactions on Knowledge and Data Engineering, v. 2, n. 1,
pp. 4-24, Março 1990.
[11] DeWITT, D. J., GHANDEHARIZADEH, S., SCHNEIDER, D. A., et al., “The Gamma
Database Machine Project”. IEEE Transactions on Knowledge and Data Engineering,
v. 2, n. 1, pp. 44-62, 1990.
[12] VALDURIEZ, P., “Parallel Database Systems: open problems and new issues”.
International Journal on Distributed and Parallel Databases, v.1, n. 2, pp. 137-165,
1993.
21
[13] STONEBRAKER, M., “The Case for Shared Nothing”, IEEE Q. Bull. Database
Engineering, v. 9, n. 1, pp. 4-9, Março 1986.
[14] ÖZSU, M. T., VALDURIEZ, P., Principles of Distributed Database Systems . 2a edição,
Capítulo 13, New Jersey, EUA, Prentice Hall, 1999.
[15] EUROPEAN DECLARATIVE SYSTEM (EDS) DATABASE GROUP,
“EDS−Collaborating for a High Performance Parallel Relational Database”. In:
Proceedings of the ESPIRIT Conference, pp. 274-295, Novembro 1990.
[16] FUSHIMI, S., KITSUREGAWA, M., TANAKA, H., “An Overview of the System
Software of a Parallel Relational Database Machine GRACE”. In: Proceedings of the 12th
International Conference on Very Large Databases, pp. 209-219, Agosto 1986.
[17] APERS, P. M. G., VAN DEN BERG, C., FLOKSTRA, J., et al., “Prisma/BD: a Parallel
Main−Memory Relational DBMS”. IEEE Transactions on Data and Knowledge
Engineering, v. 4, pp. 541-554, 1992.
[18] DeWITT, D. J., NAUGHTON, J. F., SHAFER, J. C., et al., “Parallelizing OODBMS
Traversals: a performance evaluation”. The VLDB Journal, v.5, n.1, pp.3-18, 1996.
[19] MEYER, L. A. V., MATTOSO, M. L. Q., “Parallel query processing in a shared-nothing
object database server ”. In: Proceedings of the 3rd International Meeting on Vector
and Parallel Processing (VECPAR' 98), pp. 1007-1020, Porto/PT, Junho 1998.
[20] CHENG, J. M., et al., “IBM Database 2 Performance: Design, Implementation and Tuning”,
IBM Systems Journal (MOIS 1984), v. 23, n. 2, pp. 189−210, 1984.
[21] STONEBRAKER, M., KATZ, R., PATTERSON, D., et al., “The design of XPRS”. In:
Proceedings of the 14th VLDB Conference, pp. 318-330, Los Angeles/CA, EUA, Agosto
1988.
[22] NCR CORPORATION, Born To Be Parallel: Why Parallel Origins Give Teradata and
Enduring Performance Edge; White Paper obtido em
http://www.big.tuwien.ac.at/teaching/offer/ss04/usi1/usi1adwArtikelParallel.pdf
(obtido em 21/08/2004); Agosto 1996.
[23] GRAEFE, G., “Encapsulation of Parallelism in the Volcano Query Processing Systems”. In:
Proceedings of the ACM SIGMOD International Conference on Management of Data ,
pp. 102-111, Maio 1990.
22
[24] SOARES, J. A., TAVARES, F. O., “Paralelismo em Bancos de Dados Orientados a
Objetos”. In: Anais da XVII Jornada de Iniciação Científica, Universidade Federal do
Rio de Janeiro, Rio de Janeiro/RJ, Novembro 1995.
[25] BHIDE, A., “An Analysis of Three Transaction Processing Architectures”, In:
Proceedings of the ACM SIGMOD International Conference on Management of Data ,
pp. 339−350, Junho 1988.
[26] PIRAHESH, H., MOHAN, C., CHENG, J. M., et al., “Parallelism in RDBMS:
Architectural Issues and Design”, In: Proceedings of the 2nd International Symposium on
Databases in Distributed and Parallel Systems , pp. 4−29, Julho 1990.
[27] VALDURIEZ, P., “Parallel Database Systems: the case for shared-something”. In:
Proceedings of the 9th International Conference on Data Engineering, pp.460-465,
1993.
[28] BOUGANIM, L., Data Placement for Parallel and Distributed Queries.
IDEA.DD.24B.002, INRIA, França, 1996.
[29] GRAEFE, G., DAVISON, D. L., “Encapsulation of Parallelism and Architecture-
Independence in Extensible Database Query Execution”. IEEE Transactions on Software
Engineering, v. 19, n. 8, pp. 749-763, 1993.
[30] LENOSKI, D., LAUDON, L., GHARACHORLOO, K., et al., “The Stanford Dash
Multiprocessor”, Computer, n. 25, v. 3, pp. 63-79, Março 1992.
[31] HAGERSTEN, E., LANDIN, E., HARIDI, S., “Ddm − a Cache-Only Memory
Architecture”, Computer, n. 25, v. 9, pp. 44-54, Setembro 1992.
[32] BOUGAMIN, L., FLORESCU, D., VALDURIEZ, P., “Multi−Join Query Execution with
Skew in NUMA Multiprocessors”, Distributed and Parallel Databases, n. 7, v. 1, 1999.
[33] SILICON GRAPHICS, Origin 2000 Deskside Owner's Guide. Califórnia, EUA, Julho
1998.
[34] IBM CORPORATION, IBM DB2 Universal Database Enterprise-Extended Edition
(EEE) on IBM NUMA-Q Hardware Platforms; White Paper obtido em
http://www-306.ibm.com/software/data/db2/udb/numa-q/wp.pdf (obtido em 21/08/2004);
Fevereiro 2000.
23
[35] MEYER, L. A. V. C., MATTOSO, M. L. Q., “Parallelism in database management
systems”. In: Anais do XII Simpósio Brasileiro de Banco de Dados, Tutorial publicado
como separata com 38 págs., Fortaleza/CE, Outubro 1997.
[36] SEQUENT COMPUTER SYSTEMS, Oracle 8i for NUMA-Q: NUMA Enhancements
Introduced in Oracle 8i Yield Substantial Improvements in OLTP Throughput and
Scalability; White Paper obtido em
http://www.sequent.com/products/software/dbms/oracle8i_wp.html (obtido em
28/03/2000); Fevereiro 1999.
[37] SEQUENT COMPUTER SYSTEMS, A Performance Study of the Oracle 7 Server on
Sequent’s NUMA-Q Architecture; White Paper obtido em
http://www.sequent.com/products/software/dbms/oracle7_wp1.html (obtido em
28/03/2000); 1996.
[38] INFORMIX CORPORATION, Informix Extended Parallel Server 8.3; White Paper
obtido em http://www.ewertdotcom.com/portfolio/docs/21924_701.pdf (obtido em
21/08/2004); 1999.
[39] COMPAQ CORPORATION, NonStop SQL/MP; White Paper obtido em
http://h71033.www7.hp.com/attach/7954 (obtido em 21/08/2004); Abril 1999.
