Análise de Paralelismo em Diferentes Arquiteturas

Regina Mitsue Azuma

razuma@hotmail.com

Resumo

Paralelismo é necessário para se obter tempos de resposta aceitáveis para operações complexas e que envolvam grande volume de dados, como em sistemas de suporte a decisão ( DSS), data warehousing systems, sistemas de informações geográficas ( GIS) e sistemas de banco de dados multimídia. Desde que esses sistemas não são mono-usuário, devem suportar processamento paralelo de consultas múltiplas e concorrentes, possivelmente em paralelo a transações OLTP.

Há diferentes formas de paralelismo que podem ser suportadas pelos sistemas paralelos de banco de dados: paralelismo inter-query (habilita execução paralela de múltiplas consultas geradas por transações concorrentes) bem como diferentes formas de paralelismo intra-query, ou seja, paralelismo inter-operator (habilita execução paralela de operações múltiplas e independentes possivelmente dentro da mesma query) e paralelismo intra-operator (a mesma operação pode ser executada como várias sub-operações usando particionamento de função em adição ao particionamento de dados).

Se por um lado paralelismo provê potencial para execução mais eficiente de consultas, por outro aumenta a sua complexidade. Questões peculiares a execução paralela precisam ser consideradas.

Desde que execução paralela requer comunicação de dados entre processadores, a otimização de consultas deve levar em consideração o trade-off entre o benefício do paralelismo e o custo da comunicação.

Um importante componente da otimização de consultas em sistemas de banco de dados paralelos é o schedule dos planos de execução de consultas. Este problema é particularmente complexo em ambiente shared-nothing onde cada processador tem acesso exclusivo a sua memória principal e unidades de disco.

Neste artigo pretendemos detalhar a relação entre as formas de paralelismo, as diversas categorias de sistemas de banco de dados ( OLTP, DSS, ...) e os tipos de arquitetura de máquinas paralelas (shared-nothing, shared-everything, shared-disk, ...), destacando como é explorado o paralelismo em vários sistemas comerciais e projetos de banco de dados.

1 Introdução

Alta performance é provavelmente o objetivo mais importante dos SGBDs paralelos. Nestes sistemas, o aumento de performance pode ser obtido através de várias soluções complementares e inter-relacionadas: paralelismo, otimização e balanceamento de carga (distribuição uniforme de processamento de consultas entre processadores). O uso de paralelismo pode aumentar o throughput (usando paralelismo inter-query) e decrementar o tempo de resposta das transações (usando paralelismo intra-query).

Os problemas presentes na utilização dos diferentes tipos de paralelismo dependem da arquitetura do sistema paralelo em questão. Os tipos clássicos de arquitetura são: shared-nothing, shared-disk e shared-everything. Cada arquitetura apresenta características diferentes e, consequentemente, maior ou menor complexidade no que se refere ao balanceamento de carga, particionamento de dados, processamento simultâneo de transações com diferentes perfis e controle de concorrência no acesso a dados.

As seções 2 e 3 contêm uma revisão sobre as arquiteturas de sistemas paralelos e as formas de paralelismo. É apresentada também uma explanação sobre tópicos que estão diretamente relacionados com o aumento de performance através da exploração do potencial das diversas formas de paralelismo (seções 4 e 5) e uma análise correlacionando todos os tópicos apresentados (seção 6). Na seção 7 são referenciados vários sistemas paralelos de banco de dados e os tipos de paralelismo explorados. Na seção 8 algumas conclusões são apresentadas.

2 Arquiteturas de Sistemas Paralelos

Tradicionalmente as arquiteturas de sistemas paralelos são categorizadas de acordo com o modo como os processadores compartilham recursos de hardware como discos e memória principal [10] [12]. As configurações típicas são a shared-nothing (SN), shared-disk (SD) e shared-everything (SE).

Na arquitetura shared-nothing, cada processador tem acesso exclusivo a sua memória principal e unidades de disco. Apresenta como vantagem baixo custo e alta escalabilidade, pois reduz interferência entre processadores. No entanto, a existência de data skew [2] (distribuição não uniforme das tuplas de uma relação entre os processadores) pode causar sérios problemas de balanceamento. Outra desvantagem é a baixa disponibilidade, pois no caso de um processador falhar, os dados no disco correspondente se tornam indisponíveis. Na prática, sistemas SN usam discos multiplamente conectados e mecanismos de replicação de dados para garantir disponibilidade do sistema, resultando no problema de se manter múltiplas cópias de um dado consistentes.

Na arquitetura shared-disk qualquer processador tem acesso a qualquer unidade de disco através da rede de interconexão, mas acesso exclusivo a suas memórias principais. Cada processador pode acessar páginas do disco compartilhado ou copiá-las em seu próprio cache. Para evitar conflito no acesso às mesmas páginas, mecanismos de bloqueio global e protocolos para manutenção de coerência de cache são necessários. Essa arquitetura pode apresentar problemas de gargalo no acesso a disco.

Na arquitetura shared-everything, qualquer processador tem acesso a qualquer módulo de memória e unidade de disco. A comunicação entre processos é rápida e pode ser feita via memória principal, no entanto conflitos de acesso à memória podem degradar a performance. Após um certo número de processadores o acesso à memória principal pode representar um gargalo que limita a velocidade de processamento do sistema. Outro problema é que um memory fault pode afetar muitos processos, já que o espaço de memória é compartilhado por todos processadores.

3 Tipos de Paralelismo

Existem diversas formas de paralelismo a serem exploradas na implementação de sistemas de banco de dados paralelos [7]:

  • Paralelismo inter-query: múltiplas consultas (transações) podem ser executadas concorrentemente pelo mesmo sistema gerenciador de banco de dados, aumentando o throughput do sistema.

  • Paralelismo intra-query: é baseado na paralelização de operações algébricas sobre conjuntos para processamento de consultas a banco de dados, diminuindo o tempo de resposta. Divide-se em:

  • Paralelismo inter-operator: execução paralela de diferentes operações de uma única query. Esse tipo de paralelismo pode ser usado de duas formas:

  • para executar produtores e consumidores em pipelines, conhecido por paralelismo inter-operator vertical.

  • para executar concorrentemente sub-árvores independentes em um plano complexo de avaliação bushy-query, conhecido por paralelismo inter-operator vertical ou paralelismo bushy.

  • Paralelismo intra-operator: uma única operação em um plano de consulta é executada em múltiplos processos, tipicamente em partes separadas do problema e subconjuntos separados de dados. Essa forma de paralelismo é também chamada de paralelismo baseado em fragmentação ou particionamento.

    Árvores de processamento de consultas é a representação mais usada para modelar o processamento de consultas relacionais [2]. As folhas da árvore representam as relações base que participam da consulta. Os nós intermediários modelam operações e recebem suas relações de entrada via arcos de entrada e enviam o resultado através das arcos de saída para a próxima operação. A raiz da árvore produz o resultado da consulta inteira.

    Essa representação permite expressar os diferentes tipos de paralelismo já mencionados:

  • paralelismo inter-operator bushy: operações em diferentes caminhos podem ser executadas concorrentemente

  • paralelismo intra-operator: cada operação relacional pode ser decomposta em várias sub-operações a serem executadas em diferentes partições da mesma relação.

  • paralelismo inter-operator pipelined: dois nós relativos ao mesmo arco podem ser executados concorrentemente.

    As árvores, de acordo com sua forma, podem ser classificadas em linear ( left linear tree ou right linear tree) ou bushy tree.

    4 Particionamento de Relações

    Particionar uma relação significa distribuir as tuplas entre vários discos de acordo com algum critério [3] [4]. A razão para se usar particionamento em sistemas de banco de dados paralelos é a possibilidade de se explorar a vazão dos discos, lendo e atualizando múltiplos discos em paralelo. Há vários critérios para particionamento:

  • round-robin: mapeia a i-ésima tupla para o disco (i mod n), onde n é o número de discos

  • hash: função de hash é aplicada sobre o atributo chave para distribuir as tuplas entre os discos. Permite operação de match exato no atributo do particionamento, direcionando as tuplas com mesmo atributo chave para um único disco e evitando a sobrecarga de iniciar consultas em múltiplos discos. No entanto, consultas de range no atributo de particionamento devem ser enviados para todos os discos em que a relação foi particionada.

  • range: mapeia tuplas contíguas da tabela no mesmo disco. A vantagem é que isola a execução de consultas de match exato e range para um pequeno número de processadores. E também resolve melhor a distribuição não uniforme de valores do atributo de particionamento.

    Particionamento horizontal foi proposto inicialmente para sistemas shared-nothing, mas tem sido útil para sistemas shared-memory, reduzindo conflitos de acesso à memória. O particionamento completo (cada relação é particionada por todos os nós) causa problemas para pequenas relações ou sistemas com grande quantidade de nós. Uma solução melhor é o particionamento variável (cada relação é armazenada em um certo número de nós em função do tamanho da relação e freqüência de acesso).

    Alguns SGBDs paralelos provêem vários critérios de particionamento. É necessário prover aos DBAs ferramentas que auxiliem a seleção da melhor combinação de estratégias. Tais ferramentas poderiam ter como entrada uma descrição dos tipos de consultas, freqüência e informações estatísticas, gerando como resultado qual estratégia de particionamento usar em cada relação. Essas ferramentas poderiam ser integradas ao otimizador para que este pudesse fazer uso das informações.

    Outra área de pesquisa são algoritmos de particionamento multi-atributo. Todos os algoritmos de particionamento usam o valor de um único atributo para realizar a distribuição das tuplas. No entanto seria interessante poder efetuar a seleção por outro atributo que não seja a chave, sem que seja necessário envolver nesta operação todos os nós pelos quais a relação foi particionada.

    5 Processamento Conjunto de Transações OLTP e de Suporte à Decisão

    Processar uma mistura de transações curtas OLTP (Online Transaction Processing) e transações longas e complexas de suporte a decisão requer mecanismos especiais de controle de concorrência e escalonamento de recurso. Geralmente não há muitos benefícios em paralelizar uma única transação devido ao seu pequeno tamanho. No entanto, pode-se melhorar o throughput do sistema executando muitas transações independentes em paralelo. Em consultas longas e complexas, o uso de paralelismo intra-query pode melhorar significativamente o tempo de resposta.

    Para garantir a consistência do banco de dados, bloqueios no acesso a dados são adquiridos durante a execução de uma transação e são mantidos até o fim da transação. Se uma transação curta precisa dados bloqueados por uma transação longa de suporte a decisão, o tempo de resposta para a transação curta poderia degradar de modo inaceitável.

    Em muitas situações o maior gargalo é a contenção de bloqueios entre transações, sendo que adicionar processadores para aumentar o paralelismo inter-query pode não melhorar o throughput das transações.

    Uma das soluções é a execução em modo browse, que permite às consultas complexas obter respostas aproximadas lendo dados inconsistentes. Mas esta solução não é suficiente para todas as aplicações.

    Outra opção é o gerenciamento de transações multi-level, onde uma transação de alto nível pode ser vista como mini-transações (sub-transações). Bloqueios de baixo nível são mantidos somente durante a execução de uma sub-transação ao invés da transação inteira. Essa redução da duração do bloqueio permite maior concorrência de transação, e maior OLTP scaleup (aumento de throughput obtido pela adição de processadores, discos e memória).

    6 Análise Comparativa dos Tipos de Paralelismo em Diferentes Arquiteturas e Aplicações

    6.1 Paralelismo Inter-query

    Essa forma de paralelismo é suportada por diversos sistemas comerciais de banco de dados, em várias arquiteturas.

    Nos sistemas SD e SE o próprio nó onde foi iniciada a transação ou outro nó com menor carga pode processar a consulta, pois todos tem acesso a dados em qualquer disco. Em sistemas SN, o processamento da consulta no nó que contém a maior parte dos dados de entrada pode reduzir a sobrecarga de comunicação.

    6.2 Paralelismo Inter-operator

    Não há grandes diferenças entre as arquiteturas SN, SD e SE em relação ao paralelismo inter-operator. O maior volume de dados processados são dados provenientes do nó anterior que são dinamicamente distribuídos para os nós adjacentes, considerando a representação da consulta via uma árvore de processamento de consultas.

    6.3 Paralelismo Intra-operator

    Particionamento de Dados

    Paralelismo intra-operator requer paralelismo de E/S e de processamento. Paralelismo de E/S significa que os dados a serem processados por uma operação de banco de dados estão particionados entre vários discos, de modo que o tempo de E/S não seja limitado pela vazão de um único disco. Paralelismo de processamento requer que os dados de entrada de uma operação de banco de dados possa ser processada por múltiplas CPUs para evitar que o tempo de execução seja limitado pela capacidade de um único processador [13].

    Para os três tipos de arquitetura em análise (SN, SD, SE) a alocação de dados aos discos determina o grau máximo de paralelismo de E/S. E, como a realocação (re-particionamento) é um processo caro, pode-se dizer que o paralelismo de E/S é um parâmetro estático. No entanto, é realizada reorganização dinâmica quando o critério usado para o particionamento muda ou são detectados problemas sérios de data skew, com o objetivo de evitar o desbalancemento de carga.

    Para sistemas SN o paralelismo de processamento é dependente da alocação estática de dados ao disco, pois cada disco é acessado exclusivamente por um nó. Isto reduz a flexibilidade de variar dinamicamente o grau de paralelismo de processamento se comparado às demais arquiteturas onde todo nó tem acesso a qualquer disco, logo a alocação de dados não é fator limitante do paralelismo de processamento.

    Para sistemas SD e SE, não só o grau de paralelismo de processamento pode ser escolhido, como também quais processadores devem ser alocados, de modo que é possível alocar processadores com menor utilização de CPU.

    Para sistemas SN, a determinação de uma alocação de banco de dados apropriada significa encontrar um compromisso em relação a objetivos contraditórios: suportar alto grau de paralelismo intra-query, baixa sobrecarga de comunicação e balanceamento de carga uniforme. Por exemplo, um alto grau de fragmentação favorece o paralelismo intra-transaction e balanceamento de carga, mas às custas de uma sobrecarga alta de comunicação. Um pequeno grau de fragmentação pode ser suficiente para se obter tempos de resposta adequadas para pequenas relações.

    A sobrecarga de comunicação para sistemas SE e SD é reduzida, pois é possível trocar resultados intermediários longos via memória e discos compartilhados, correspondentemente, e não pela rede.

    Objetos Complexos e Dados Multimídia.

    Para aplicações de engenharia onde é necessário armazenar objetos complexos compostos por muitas tuplas interconectadas, particionar os objetos por múltiplos nós é uma tarefa difícil pois um sub-objeto pode ser compartilhado por muitos objetos complexos. Esses objetos complexos, assim como objetos multimídia, imagens raster de Sistemas de Informações Geográficas poderiam ser armazenados em uma única tupla, evitando a sobrecarga de comunicação ou múltiplos acessos a diferentes discos. No entanto isso impediria a paralelização das operações de scan. Por outro lado, para sistemas SD e SE o objeto poderia ser particionado por vários discos de modo que poderia usar pelo menos paralelismo de E/S para reduzir o tempo de resposta.

    Processamento Conjunto de Transações Online e Consultas Complexas

    SN não suporta eficientemente os dois tipos de transações, pois requer alocação do banco de dados de acordo com um perfil médio de transação. As consultas complexas ficam restritas a menos nós do que o desejável, impedindo maior paralelismo, e as transações OLTP não podem ficar restritas a um nó apenas, causando sobrecarga de comunicação.

    Em sistemas SD, transações OLTP são executadas em um só nó para evitar a sobrecarga de comunicação e commit distribuído. O grau de processamento paralelo para consultas complexas pode ser determinado dinamicamente de acordo com a situação corrente de carga do sistema. A concorrência por CPU e memória entre OLTP e consultas complexas pode ser evitada atribuindo diferentes tipos de consultas a conjuntos separados de processadores.

    Bloqueio de Dados

    Paralelismo intra-transaction implica na decomposição de transações em múltiplas sub-transações rodando em nós diferentes. Em sistemas SN essa separação é determinada pelo particionamento do banco de dados, assegurando que cada sub-transação opera em dados pertencentes ao respectivo nó. Controle de concorrência é uma função local ao nó. Para SD, sub-transações em diferentes nós podem referenciar e modificar os mesmos dados. Logo, é necessário controle de concorrência entre sub-transações paralelas. Controle de coerência também é necessário para evitar acesso a dados obsoletos e para propagar objetos atualizados entre as sub-transações. Requisições de bloqueio precisam ser enviadas para um gerenciador de bloqueio global, gerando sobrecarga de comun! icação e atrasos.

    Recuperação à queda

    Atualizações resultantes de uma única transação, usando paralelismo intra-operator, podem ser realizadas por múltiplos nós, de forma que o log de transação pode estar espalhado por vários nós. Sistemas SN tem a vantagem que cada arquivo de log local contém informações de log da partição do banco de dados armazenada no disco local, sem ter a necessidade de um arquivo de log global, como acontece aos sistemas SD e SE.

    7 Paralelismo em Sistemas Comerciais e Projetos de Sistemas de Banco de Dados

    Existem alguns SGBDs que implementam os conceitos discutidos. A maior parte dos produtos comerciais shared-memory (INGRES e ORACLE) e shared-disk (IBM´s IMS/VS Data Sharing, DEC´s DBMS e Rdb, ORACLE on DEC´s VAX cluster) exploram somente paralelismo inter-query. Nesta seção apresentamos as características básicas de sistemas que exploram os demais tipos de paralelismo.

    DB2 Parallel Edition

    É baseado em uma arquitetura shared-nothing. As relações são particionadas usando estratégia hash-partitioning e todas as operações são capazes de explorar paralelismo intra-operator. Nesse sistema, um plano de consulta é dividido em múltiplas subseções que correspondem a diferentes sub-árvores no plano de consulta. Cada subseção é associada a um agente paralelo (processo) que executa concorrentemente, suportando paralelismo intra-query. Os dados são pipelined entre operadores consecutivos de um plano, suportando paralelismo pipelined.

    Informix eXtended Parallel Server (XPS)

    Apresenta arquitetura shared-memory e explora paralelismo vertical (pipelined) e horizontal (hash partitioned)

    XPRS

    A arquitetura é shared-memory e o particionamento de dados usa os critérios: round-robin, page partitioning, range partitioning. O sistema implementa paralelismo intra-operator e inter-operator em planos bushy tree.

    NonStop SQL/MP

    É um sistema de BD paralelo da Tandem Computers e pode ser visto como um sistema clássico shared-nothing. As relações são particionadas usando hashing e range partitioning. Explora paralelismo intra-operation para executar joins, groupings e scans em paralelo, usando replicação e particionamento. E não implementa paralelismo inter-operator.

    8 Conclusão

    A estratégia de particionamento de relações, o mecanismo de controle de concorrência a dados, os algoritmos paralelos das operações, os tipos de paralelismo explorados e a estratégia de otimização são decisões muito importantes no projeto de um SGBD paralelo. O tipo de arquitetura é um fator determinante na maioria das decisões.

    Enquanto o "particionamento ideal" de dados é o maior objetivo de sistemas SN para equilibrar o balanceamento de carga e reduzir comunicação sobre a rede, nos sistemas SE e SD o particionamento não tem impacto muito grande, mas apresentam o problema de concorrência e bloqueio dos recursos que compartilham. Se, por um lado o compartilhamento de recursos favorece o balanceamento de carga, por outro pode se tornar o gargalo do sistema.

    Atualmente há uma tendência nas pesquisas ao uso da arquitetura SN. Outras linhas de pesquisa são as arquiteturas híbridas, que combinam as características de duas ou mais das arquiteturas clássicas, tipicamente em dois níveis. Talvez essas arquiteturas híbridas possam resolver de forma melhor as limitações de cada abordagem.

    O paralelismo inter-query é explorado por grande parte dos SGBDs paralelos em diferentes arquiteturas. Paralelismo inter-operator não apresenta grandes vantagens de uma arquitetura para outra. A forma de paralelismo que apresenta maior complexidade e é mais dependente da arquitetura do sistema é o paralelismo intra-operator. São poucos os sistemas que exploram esse tipo de paralelismo.

    Seria interessante que os SGBDs paralelos provessem várias formas de paralelismo, estratégias de particionamento de dados e algoritmos diferentes de operações, de modo que o tipo de consulta, a freqüência e o tipo de dado manipulado pudessem ser levados em consideração para a definição do melhor conjunto de estratégias para execução das consultas. No entanto, é importante considerar também o compromisso entre o tempo de otimização e o tempo de execução das consultas.

    Referência Bibliográfica

    [1] Baru, C. and Fecteau G. "An Overview of DB2 Parallel Edition". ACM SIGMOD'95, 6/95, pp. 460-462

    [2] Brunie, L. and Kosch H. "Control strategies for complex relational query processing in shared nothing systems". SIGMOD Record (September 1996), 25(3), pp. 34-39.

    [3] DeWitt D. J. and Gray, J. "Parallel Database Systems: The Future of Database Processing or a Passing Fad?", SIGMOD Record (December 1990), 19(4), pp. 104-112.

    [4] DeWitt D. and Gray J. "Parallel Database Systems: The Future of High Performance Database Systems", Communications of The ACM (June 1993), 35(6), pp. 85-98.

    [5] Englert, S, Glasstone, R. and Hasan W. "Parallelism and its Price: A Case Study of NonStop SQL/MP", SIGMOD Record (December 1995), 24(4), pp. 61-71.

    [6] Gerber, B. "Informix Online XPS", ACM SIGMOD´95, 6/95, pp. 463-463.

    [7] Graefe, G. "Query Evaluation Techniques for Large Databases". ACM Computing Surveys (June 1993), 26(2), pp. 73-170.

    [8] Hasan, W., Florescu, D. Valduriez, P. "Open Issues in Parallel Query Optimization". SIGMOD Record (September 1996), 25(3), pp. 28-33.

    [9] Hong, W. "Exploiting Inter-Operation Parallelism in XPRS". ACM SIGMOD' 92, 6/92 pp. 19-28.

    [10] Norman, M. G., Zurek T. and Thanisch P. "Much Ado About Shared-Nothing". SIGMOD Record (September 1996), 25(3), pp. 16-21.

    [11] O' Connell, et. al. "A Teradata Content-Based Multimedia Object Manager for Massively Parallel Architectures", ACM SIGMOD' 96, 6/96, pp. 68-78.

    [12] Özsu, M. T. and Valduriez, P. "Distributed and Parallel Database Systems", Handbook of Computer Science and Engineering, CRC Press, 1996 (in press).

    [13] Rahm, E. "Parallel Query Processing in Shared Disk Database Systems". SIGMOD Record (December 1993), 22(4), pp. 32-37.

    [14] Tseng, E. and Reiner, D. "Parallel Database Processing on the KSR1 Computer", ACM SIGMOD' 93, 5/93, pp. 453- 455

    [15] Wolf, J and Chen M. "A Hierarchical Approach to Parallel Multiquery Scheduling". IEEE Trans. on Parallel and Distributed Systems (June 1995), 6(6), pp. 578-589.