O gerenciador de buffer pool é um componente central do Adabas, um sistema de banco de dados escalável de alto desempenho para o processamento OLTP. Alta eficiência e escalabilidade do gerenciador de buffer pool é obrigatória para ADABAS em todas as plataformas suportadas. A fim de permitir que um máximo de paralelismo sem enfrentar o risco de bloqueios, um método de bloqueio de multi-versão é usada. Particionamento de estruturas de dados centrais é outra chave para o desempenho.
Tamanhos de página variáveis permitem ajuste flexível, mas fazer a lógica de buffer pool mais sofisticadas, em particular relativo em matéria de paralelismo.
1 - Introdução
O banco de dados Adabas da Software AG é um banco com uma história muito longa. É utilizado com sucesso em negócios críticos OLTP que dependem do robustez e o alto desempenho que são um sinônimo desse sistema de banco de dados, sistemas como reservas de voos, emergências médicas, entre outras. Ao longo dos anos, tem sido portado para todos os principais sistemas operacionais. Hoje, o banco de dados Adabas pode operar em máquinas UNIX que executam várias distribuições de UNIX, computadores com Windows, vários sistemas operacionais mainframes, como z/OS, MVS, VSE, e BS2000, e outras plataformas.
Para lidar com o mundo em ambientes em evolução, continua re-engenharia no Adabas foi necessário. Em particular, arquiteturas multi-processamento (simétrica multi-processamento) têm causado mudanças consideráveis no sistema como um todo. Um componente que tem sido recentemente redesenhado completamente durante este processo é o gerenciador do buffer pool do Adabas. A principal tarefa do gerenciador de buffer pool é armazenar em cache as páginas de banco de dados que foram lidas no disco, em ordem que essas páginas foram salvas o I/O são re-referenciados. Alterações das páginas de banco de dados são realizados apenas no buffer pool e não imediatamente gravados em disco. Claro, o registo adequado é necessária para garantir a persistência de operações cometidos, mas algoritmos logging estão além do escopo deste artigo. O pool de buffer também lida com informações temporárias que são gravados no disco somente se houver uma falta de espaço.
A seguir, vamos mencionar algumas características do Adabas que são importantes para o projeto do buffer pool.
1.1 Tipos de Dataset
No Adabas os dados do disco são organizados em dois arquivos de dataset chamados. O DATA onde são armazenados os dados de um banco de dados em um formato compactado, enquanto o ASSO armazena as informações de schema, o tabela de tradução do banco (chamada no Adabas de Address Converter), e os índices. Cada registro no dataset DATA tem um identificador exclusivo. O Address Converter mapeia o ID único para localização fisica do registro no DATA. Os índices tem a identificação lógica apenas. Há um terceiro arquivo de dataset chamado de WORK que é usado para armazenar dados temporários e registrar informações. Os arquivos dos dataset podem ser distribuídos ao longo de vários números de discos, usando raw device ou outro sistema de acesso (ou mistura de ambos). Um dataset consiste de páginas, que são numeradas em sequência ascendente. Estas páginas são a unidade de entrada e saída. O buffer pool armazena páginas de cada um dos três tipos de dataset.
1.2 Tamanhos Variados das Páginas
As páginas dentro de um dataset podem ter tamanho diferente. Dependendo do tamanho dos dados da tabela do banco de dados e o tipo de acesso padrão, o administrador do banco de dados (DBA) pode ajustar o tamanho da página (num intervalo de 1 a 32 kilobytes). Por exemplo, se uma tabela é normalmente acessado com consultas via um índice, o DBA pode escolher um tamanho de página para o data storage de tal forma que uma página contém apenas alguns registros de dados. O tamanho da página para o índice, e para o address converter, pode ser escolhida independentemente.
Em consequência, o gerenciador do buffer pool do Adabas deve lidar com páginas de vários tamanhos de todos os três tipos de dataset. Em particular, os diferentes tamanhos de página que afetam os algoritmos de substituição do buffer. Outros sistemas de banco de dados comerciais não têm essa liberdade na configuração, e, como conseqüência, não precisam lidar com tais problemas de substituição complexas. No buffer pool, uma lista livre é mantido separado da corrente LRU. Esta lista é então copiado e um dos buffers contidas na corrente LRU e são consecutivamente marcado como substituível. Quando uma área foi encontrado que é suficientemente grande para o novo buffer, o processo para. Este algoritmo, no entanto, não tem a flexibilidade do algoritmo Adabas descrito abaixo.
1.3 Acesso Paralelo
O gerenciador de buffer pool tem que cuidar de uma sincronização adequada dos acessos às páginas na área de buffer. Várias threads que executam em paralelo sobre múltiplas CPUs podem querer acessar a mesma página de banco de dados e, portanto, o mesmo buffer. Claro que, a sincronização tem de ser muito eficiente, não só para evitar bloqueios, mas também manter os tempos de espera mais curto possível.
As seções seguintes abordam a arquitetura e os algoritmos escolhidos para o novo gerenciador do buffer pool do Adabas.
2 Arquitetura do gerenciador de área de buffer
O buffer pool é alocado com um pedaço contíguo de memória. A fim de evitar duplas faltas página, ou seja, falhas de página na memória virtual do sistema operacional, todo o buffer pool pode ser fixado na memória física. Quando um bloco de disco é lido no buffer pool, uma estrutura de cabeçalho é atribuído a ele, que armazena todas as informações necessárias para a gestão do bloco, incluindo, naturalmente, a identificação das páginas de banco de dados deste bloco corresponde. Esses próprios cabeçalhos são alocados na área de buffer em áreas contíguas. Note-se que o tamanho variável principal no Adabas torna impossível de prever o número de cabeçalhos necessários (obviamente, o tamanho da página minimo possível determina um limite superior para o número de cabeçalhos, mas alocação que tanto cabeçalhos de antecedência podia perder uma grande quantidade de espaço).
O Adabas faz referência diretamente as páginas da área de buffer. Portanto, o endereço de uma página não deve ser alterado e não deve ser removido da área de buffer pool enquanto um comando ainda está trabalhando nele. Para garantir isso, sistemas de gerenciamento de banco de dados geralmente FIX e UNFIX nas páginas em um pool de buffer explicitamente. No gerenciador de buffer pool do Adabas, essa funcionalidade é combinada com a sincronização de acessos página pelos comandos Adabas. Para o efeito, cada cabeçalho contém um bloqueio readers/writer.
Os readers estão ligadas em sequência física (a chamada cadeia físico) e na sequência de LRU (corrente LRU). Além disso, para permitir uma pesquisa eficiente para uma página de banco de dados específica, uma estrutura de hash é alocado. Cada bucket de hash contém os ponteiros para os cabeçalhos correspondentes e está protegido pelo seu próprio latch (trinco). Assim, conflitos de bloqueio sobre a estrutura de hash são raros. O estouro de um bucket hash é organizado como árvore AVL. Assim, mesmo no caso em que um bucket tem uma grande quantidade de informações o estouro do acesso continua a ser rápido - outro pré-requisito para baixar a contenção de bloqueio sobre a estrutura hash. O buffer pool da arquitetura é mostrada na Figura 1 (LRU corrente não mostrada).
3 Sincronização de Acesso a Página
O acesso a uma página de banco de dados funciona da seguinte forma: A página é procurado na estrutura hash. O bucket hash é protegido por um (trinco) latch (um curto tempo mutuo de exclusão de bloqueio). Se ele não for encontrado, um cabeçalho para a página de banco de dados é alocado, exclusivamente bloqueado, e foi introduzido o hash na estrutura de tal forma que outras tarefas tem uma referência a ele. Em seguida, o I/O físico é iniciado. Quando ele for concluído, o bloqueio exclusivo pode ser rebaixado a um bloqueio compartilhado se o banco necessita para leitura apenas.
Se a página foi encontrada na estrutura de hash, o buffer pool tenta adquirir um bloqueio requisitada qualidade (lock compartilhado ou exclusivo) e, se bem sucedida, retorna um ponteiro para a localização correspondente na área de buffer. Bloqueios em páginas de banco em banco de dados são mantidos até que o comando tenha realizado as suas alterações para a página, ou seja, por apenas um tempo muito curto.
Quando as páginas de banco de dados estão logicamente ligados (por exemplo, nós em uma árvore de índices), e as atualizações que afetam esta ligação tem que ser realizada, mais do que uma página deve ser bloqueada exclusivamente por vez. Enquanto deadlock muitas vezes em tais situações pode ser evitada através da aplicação de uma determinada sequência de bloqueio, isto não é possível em todos os casos. Por exemplo, o posicionamento em um índice é feito de raiz para sair, enquanto as atualizações do índice ocorrer a partir da licença para a raiz. Assim, posicionamento e atualização simultaneamente poderia levar a um deadlock. Bloqueando o índice inteiro levaria a situações de espera inaceitáveis. Para lidar com esta situação, o gerenciador de buffer pool do Adabas usa um esquema de bloqueio multi-versão: quando um bloqueio exclusivo não for concedida, o buffer pool tenta adquirir um bloqueio compartilhado. Se este for concedido, uma cópia da página de banco de dados é gerado na área de buffer, e o ponteiro na estrutura hash é definido para essa cópia. Assim, as threads que, posteriormente, procuram esta página vão encontrar a cópia. O bloco que contém a página original permanece na área de buffer, mas é colocado no final da corrente LRU, sendo assim o principal candidato para a substituição, uma vez todos os bloqueios (compartilhados) sobre ele são liberados.
Uma consequência deste esquema de bloqueio é que bloqueios compartilhados não protegem uma ligação lógica entre as páginas contra as alterações. Portanto, as páginas encontradas através de um link sempre tem de estar se reavaliando antes de poderem ser usadas.
Exemplo 1 ilustra este efeito.
Note-se que em situações de alta carga, mais de um segmento poderia copiar a mesma página de banco de dados. Apenas uma destas duas cópias devem sobreviver. Para este efeito, o intercâmbio na estrutura hash para pesquisa deve ser atômica. Ela falhará se o endereço a ser substituído não é o esperado.
4 Salvando as Alterações para o Disco
O gerenciador de buffer pool do Adabas salva as páginas alteradas no disco de forma assíncrona. Quando um certo (configurável) porcentagem de todas as páginas foram modificadas, uma thread assíncrono (chamada de buffer flush thread) começa a gravar todas as páginas alteradas no disco. Claro, as páginas não devem ser modificadas, enquanto eles estão sendo gravados no disco.
Por outro lado, não é aceitável diferir modificações dessas páginas até que a gravação tenha sido feita. Se uma página que está bloqueada pelo buffer flush trhead é para ser modificada por uma outra thread, o mesmo bloqueio de multi-version como descrito acima é aplicada. As páginas envolvidos no buffer flush são bloqueados pelo segmento buffer flush thread usando um bloqueio de leitura privilegiada. Se uma página atual da gravação esta bloqueado, ela é inserido em uma lista de bloqueio recusado e ignorado. Depois que todas as outras páginas estão bloqueadas, os blocos buffer flush thread nas páginas na lista de bloqueio recusada se necessário. Normalmente, o comando de atualização que tinha realizado um bloqueio nessas páginas foram entretanto liberado do bloqueio
A gravação assíncrona de páginas alteradas tem algum consequências:
(*) Uma página que foi escolhido para a substituição não precisa ser gravada no disco antes de ser substituído, o que permite uma rápida substituição.
(*) As páginas não podem ser substituídos se elas tenham sido alterados após o último buffer flush. Portanto, um buffer flush deve ocorrer antes que muitas páginas estão sujas (dirty). Por outro lado, o flushing muito cedo destrói o efeito de cache para atualizações porque as páginas são gravadas no disco depois de poucas atualizações por página. Obviamente, encontrando um percentual razoável de páginas sujas para o início de um flush buffer não é trivial. A fim de aliviar o DBA a esta tarefa, o Adabas pode escolher uma percentagem útil e internamente adaptar à situação atual.
(*) Os algoritmos de recuperação de acidente estão fortemente acoplados à gravação assíncrona. O início e o fim do buffer flush são registrados. A partir desta informação registrando o algoritmo de recuperação de falhas pode-se deduzir que as alterações de banco de dados já estão incorporados no disco e que não são (possivelmente). Por isso, é essencial que todas as páginas alteradas sejam cobertas pelo buffer flush. Por outro lado, as páginas que são muito atualizados com freqüência pode diferir consideravelmente todo o buffer flush. Para lidar com tais situações, o buffer flush pode ser dividido em uma primeira parte que contém todas as páginas que podem ser bloqueadas sem bloquear o bloqueio, e uma segunda parte que descarregou todas as outras páginas (e geralmente lida com muito poucas páginas).
5 Buffer Replacement Handling
Como apontado anteriormente, o buffer flush do Adabas é bastante sofisticado. Se uma página de um determinado com um tamanho de página é para ser lida na área de buffer, e o buffer pool está cheio (que é o caso normal após uma fase inicial de enchimento), o espaço necessário deve ser fornecido ao selecionar outro buffer que pode ser gravado em cima. No entanto, por causa das diferentes de tamanhos de página em um banco de dados Adabas, pode ser necessário a substituição de várias outras páginas de tamanho menor. Nos bancos de dados com um tamanho fixo principal, a primeira página disponível durante a pesquisa a partir da extremidade da corrente LRU pode ser escolhido para a substituição. Isso não é verdade para o Adabas.
Considere o seguinte caso: uma página com tamanho de 4 KB tem de ser lido no buffer. No final da corrente LRU, apenas a pagina de 2 KB podem ser encontrado. A próxima página 4 KB é muito no início da corrente LRU, ou seja, é uma página muito nova. Neste caso, uma das páginas 2Kb e a sua vizinha física deve ser substituído. No entanto, o vizinho físico também pode ser uma página muito nova. Para encontrar bons candidatos de substituição, o seguinte tratamento é aplicado. A corrente LRU é pesquisada a partir do seu fim. Quando uma página é encontrada, que esteja disponível para a substituição (ou seja, não contém qualquer alteração, que não foi gravada e não esteja bloqueada), o Adabas procura o espaço necessário a partir desta página. Os vizinhos restantes são considerados, desde que possam ser substituído e o espaço necessário ainda não é recolhida. Então, os vizinhos certos são verificados. O espaço entre o mais à esquerda vizinho encontrou e o mais à direita geralmente deixa várias opções para os chamados conjuntos de sobreposição, ou seja, conjuntos de buffers que podem ser substituído para ganhar o espaço necessário (Figura 2). O conjunto de sobreposições com os menores custos é armazenada.
Então a busca LRU continua a busca, até um limite máximo das páginas encontradas for alcançado, ou até a uma página única for encontrada que é grande para tornar o espaço necessário. Esta página única é definida para substituição. O conjunto de substituição mais barato é escolhida para ser substituída.
O custo de um substituição é determinada pela aplicação de uma função para os time stamp de acesso das páginas no definidas. A escolha desta função influencia fortemente o algoritmo de substituição. Se a função for MIN (minimo), por exemplo, a primeiro definição de substituição encontrado seria selecionada. Se a função é SUM (soma), a probabilidade de uma substituição de multi-buffer diminui rapidamente com o número de páginas. No caso da função MAX (maximo), a definição de substituição é escolhida somente se todas as suas páginas são mais velhas do que os mais antigas páginas único substituível de tamanho suficiente.
Obviamente, busca por candidatos de substituição é uma operação que leva um tempo bem longo, devido à necessidade de lidar com diferentes tamanhos de página. Infelizmente, a corrente LRU não pode ser alterado enquanto tal pesquisa é realizada. Uma vez que cada acesso a uma página de banco de dados deve atualizar a corrente LRU (colocando a página acessada na frente da corrente LRU), há uma considerável gargalo. Para evitar contenção de bloqueio na corrente LRU, o Adabas divide a área de buffer em várias regiões físicas, onde cada região tem sua própria corrente LRU. O número de regiões depende do tamanho do conjunto de memória intermédia, o máximo paralelismo permitido pelo DBA, e outros critérios.
Estas regiões físicas são escolhidos para a substituição de uma maneira round-robin. Só a corrente LRU afetada está bloqueado. Além disso, as atualizações para a corrente LRU são diferidos. Obviamente, as atualizações não precisa ser feito antes de uma busca substituição é executada. Assim, o acesso a páginas é memorizado, mas é reflectida na corrente LRU apenas quando a fechadura para a pesquisa for necessária a substituição de qualquer maneira. Note-se, que, em contraste com o processo usado no ORACLE [Br97], os algoritmos Adabas reflecte a sequência correcta de acessos na cadeia LRU.
6 Prefetching
Operações seqüenciais que fazem scan dos dados de várias páginas de banco de dados adjacentes são bastante comuns. No Adabas, o DBA pode otimizar para tais operações, por exemplo, ao escolher tamanhos de página grandes. No entanto, tais optimizações são complexas e podem diminuir o desempenho dos comandos com diferentes padrões de acesso. Portanto, o Adabas reconhece o acesso sequencial, e pode ler várias páginas em uma IO em uma área de buffer pool contíguo. O algoritmo de substituição descrito acima, obviamente, cobre este caso sem adaptação. Apesar de ler com um I/O, todas as páginas têm o seu próprio cabeçalho e são gerenciados pelo gerenciador de buffer pool como se foi lido separadamente. O número de páginas a serem lidas de um IO é determinada dinamicamente, de acordo com os seguintes critérios:
(*) Número máximo de páginas necessários para o atual comando;
(*) Número de páginas que se encaixam em um único I/O físico. Isto depende da plataforma, mas também depende da distribuição dos arquivos de datasets sobre discos;
(*) Próxima página que já está na área de buffer. A fim de evitar inconsistências com atualizações nesta página, a página não deve ser relido no buffer;
(*) Espaço disponível na área de buffer pool;
7 Resumo
O gerenciador do buffer pool do Adabas foi completamente redesenhado para a mais recente versão paralela do Adabas. Em particular, o bloqueio da corrente LRU tinha sido um gargalo, em particular porque o algoritmo de substituição é muito complexo devido aos diferentes tamanhos de página utilizados em um banco de dados. Para evitar contenção de bloqueio na corrente LRU, tem sido dividido em diversas áreas. Além disso, a atualização da corrente LRU é feito preguiçosamente. A fim de aumentar o paralelismo e evitar impasses em particular em operações de índice, protocolos dedicado a multi-versão de bloqueio foram introduzidos. Várias otimizações dinâmicas para aliviar o DBA de ajuste muito sofisticado. O uso de mais algoritmos de auto-ajuste, como LRU-2 é constantemente investigada. Retirado - Clique Aqui
Tamanhos de página variáveis permitem ajuste flexível, mas fazer a lógica de buffer pool mais sofisticadas, em particular relativo em matéria de paralelismo.
1 - Introdução
O banco de dados Adabas da Software AG é um banco com uma história muito longa. É utilizado com sucesso em negócios críticos OLTP que dependem do robustez e o alto desempenho que são um sinônimo desse sistema de banco de dados, sistemas como reservas de voos, emergências médicas, entre outras. Ao longo dos anos, tem sido portado para todos os principais sistemas operacionais. Hoje, o banco de dados Adabas pode operar em máquinas UNIX que executam várias distribuições de UNIX, computadores com Windows, vários sistemas operacionais mainframes, como z/OS, MVS, VSE, e BS2000, e outras plataformas.
Para lidar com o mundo em ambientes em evolução, continua re-engenharia no Adabas foi necessário. Em particular, arquiteturas multi-processamento (simétrica multi-processamento) têm causado mudanças consideráveis no sistema como um todo. Um componente que tem sido recentemente redesenhado completamente durante este processo é o gerenciador do buffer pool do Adabas. A principal tarefa do gerenciador de buffer pool é armazenar em cache as páginas de banco de dados que foram lidas no disco, em ordem que essas páginas foram salvas o I/O são re-referenciados. Alterações das páginas de banco de dados são realizados apenas no buffer pool e não imediatamente gravados em disco. Claro, o registo adequado é necessária para garantir a persistência de operações cometidos, mas algoritmos logging estão além do escopo deste artigo. O pool de buffer também lida com informações temporárias que são gravados no disco somente se houver uma falta de espaço.
A seguir, vamos mencionar algumas características do Adabas que são importantes para o projeto do buffer pool.
1.1 Tipos de Dataset
No Adabas os dados do disco são organizados em dois arquivos de dataset chamados. O DATA onde são armazenados os dados de um banco de dados em um formato compactado, enquanto o ASSO armazena as informações de schema, o tabela de tradução do banco (chamada no Adabas de Address Converter), e os índices. Cada registro no dataset DATA tem um identificador exclusivo. O Address Converter mapeia o ID único para localização fisica do registro no DATA. Os índices tem a identificação lógica apenas. Há um terceiro arquivo de dataset chamado de WORK que é usado para armazenar dados temporários e registrar informações. Os arquivos dos dataset podem ser distribuídos ao longo de vários números de discos, usando raw device ou outro sistema de acesso (ou mistura de ambos). Um dataset consiste de páginas, que são numeradas em sequência ascendente. Estas páginas são a unidade de entrada e saída. O buffer pool armazena páginas de cada um dos três tipos de dataset.
1.2 Tamanhos Variados das Páginas
As páginas dentro de um dataset podem ter tamanho diferente. Dependendo do tamanho dos dados da tabela do banco de dados e o tipo de acesso padrão, o administrador do banco de dados (DBA) pode ajustar o tamanho da página (num intervalo de 1 a 32 kilobytes). Por exemplo, se uma tabela é normalmente acessado com consultas via um índice, o DBA pode escolher um tamanho de página para o data storage de tal forma que uma página contém apenas alguns registros de dados. O tamanho da página para o índice, e para o address converter, pode ser escolhida independentemente.
Em consequência, o gerenciador do buffer pool do Adabas deve lidar com páginas de vários tamanhos de todos os três tipos de dataset. Em particular, os diferentes tamanhos de página que afetam os algoritmos de substituição do buffer. Outros sistemas de banco de dados comerciais não têm essa liberdade na configuração, e, como conseqüência, não precisam lidar com tais problemas de substituição complexas. No buffer pool, uma lista livre é mantido separado da corrente LRU. Esta lista é então copiado e um dos buffers contidas na corrente LRU e são consecutivamente marcado como substituível. Quando uma área foi encontrado que é suficientemente grande para o novo buffer, o processo para. Este algoritmo, no entanto, não tem a flexibilidade do algoritmo Adabas descrito abaixo.
1.3 Acesso Paralelo
O gerenciador de buffer pool tem que cuidar de uma sincronização adequada dos acessos às páginas na área de buffer. Várias threads que executam em paralelo sobre múltiplas CPUs podem querer acessar a mesma página de banco de dados e, portanto, o mesmo buffer. Claro que, a sincronização tem de ser muito eficiente, não só para evitar bloqueios, mas também manter os tempos de espera mais curto possível.
As seções seguintes abordam a arquitetura e os algoritmos escolhidos para o novo gerenciador do buffer pool do Adabas.
2 Arquitetura do gerenciador de área de buffer
O buffer pool é alocado com um pedaço contíguo de memória. A fim de evitar duplas faltas página, ou seja, falhas de página na memória virtual do sistema operacional, todo o buffer pool pode ser fixado na memória física. Quando um bloco de disco é lido no buffer pool, uma estrutura de cabeçalho é atribuído a ele, que armazena todas as informações necessárias para a gestão do bloco, incluindo, naturalmente, a identificação das páginas de banco de dados deste bloco corresponde. Esses próprios cabeçalhos são alocados na área de buffer em áreas contíguas. Note-se que o tamanho variável principal no Adabas torna impossível de prever o número de cabeçalhos necessários (obviamente, o tamanho da página minimo possível determina um limite superior para o número de cabeçalhos, mas alocação que tanto cabeçalhos de antecedência podia perder uma grande quantidade de espaço).
O Adabas faz referência diretamente as páginas da área de buffer. Portanto, o endereço de uma página não deve ser alterado e não deve ser removido da área de buffer pool enquanto um comando ainda está trabalhando nele. Para garantir isso, sistemas de gerenciamento de banco de dados geralmente FIX e UNFIX nas páginas em um pool de buffer explicitamente. No gerenciador de buffer pool do Adabas, essa funcionalidade é combinada com a sincronização de acessos página pelos comandos Adabas. Para o efeito, cada cabeçalho contém um bloqueio readers/writer.
Os readers estão ligadas em sequência física (a chamada cadeia físico) e na sequência de LRU (corrente LRU). Além disso, para permitir uma pesquisa eficiente para uma página de banco de dados específica, uma estrutura de hash é alocado. Cada bucket de hash contém os ponteiros para os cabeçalhos correspondentes e está protegido pelo seu próprio latch (trinco). Assim, conflitos de bloqueio sobre a estrutura de hash são raros. O estouro de um bucket hash é organizado como árvore AVL. Assim, mesmo no caso em que um bucket tem uma grande quantidade de informações o estouro do acesso continua a ser rápido - outro pré-requisito para baixar a contenção de bloqueio sobre a estrutura hash. O buffer pool da arquitetura é mostrada na Figura 1 (LRU corrente não mostrada).
3 Sincronização de Acesso a Página
O acesso a uma página de banco de dados funciona da seguinte forma: A página é procurado na estrutura hash. O bucket hash é protegido por um (trinco) latch (um curto tempo mutuo de exclusão de bloqueio). Se ele não for encontrado, um cabeçalho para a página de banco de dados é alocado, exclusivamente bloqueado, e foi introduzido o hash na estrutura de tal forma que outras tarefas tem uma referência a ele. Em seguida, o I/O físico é iniciado. Quando ele for concluído, o bloqueio exclusivo pode ser rebaixado a um bloqueio compartilhado se o banco necessita para leitura apenas.
Se a página foi encontrada na estrutura de hash, o buffer pool tenta adquirir um bloqueio requisitada qualidade (lock compartilhado ou exclusivo) e, se bem sucedida, retorna um ponteiro para a localização correspondente na área de buffer. Bloqueios em páginas de banco em banco de dados são mantidos até que o comando tenha realizado as suas alterações para a página, ou seja, por apenas um tempo muito curto.
Quando as páginas de banco de dados estão logicamente ligados (por exemplo, nós em uma árvore de índices), e as atualizações que afetam esta ligação tem que ser realizada, mais do que uma página deve ser bloqueada exclusivamente por vez. Enquanto deadlock muitas vezes em tais situações pode ser evitada através da aplicação de uma determinada sequência de bloqueio, isto não é possível em todos os casos. Por exemplo, o posicionamento em um índice é feito de raiz para sair, enquanto as atualizações do índice ocorrer a partir da licença para a raiz. Assim, posicionamento e atualização simultaneamente poderia levar a um deadlock. Bloqueando o índice inteiro levaria a situações de espera inaceitáveis. Para lidar com esta situação, o gerenciador de buffer pool do Adabas usa um esquema de bloqueio multi-versão: quando um bloqueio exclusivo não for concedida, o buffer pool tenta adquirir um bloqueio compartilhado. Se este for concedido, uma cópia da página de banco de dados é gerado na área de buffer, e o ponteiro na estrutura hash é definido para essa cópia. Assim, as threads que, posteriormente, procuram esta página vão encontrar a cópia. O bloco que contém a página original permanece na área de buffer, mas é colocado no final da corrente LRU, sendo assim o principal candidato para a substituição, uma vez todos os bloqueios (compartilhados) sobre ele são liberados.
+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | Hash Structure
++-+--+--+--++-+--+--+--+--+--+--+--+
| | |
| | |
+----+ +------+ +--------+
+---------------|--------+ | |
| +-----|-------------|-----|--------------+ Physical chain
| | | | |+----|------------------+
^ ^ | | || | | ^
+-+--+----+-+--+--+-+----+-+--+-++-+--+-+----+----+--+-+-+--+
| | | | | | | | | | | | | Buffer Headers
| | | | | | | | | | | | |
+-+--+----+--+-+--+-+----+--+-+--+-+----+----+-+--+--+-+--+-+
| | | | | | |
| | | | | +----|--------------------------+
| | | | +--+ +-----------------+ |
| | | +----------|---------------------+ | |
| | +---------------|----------+ | | |
| +--------+ | | | | |
| | | | | | |
+-+-------+-----+---+---------+--+------+---+-----+----+----+----+----+---+-----+
| | | | | | | | |
| 17 | 19 | 1237 | 13 | 1567 | 34 | 99 | 65 |
| | | | | | | | |
+---------+---------+----+----+---------+---------+---------+---------+---------+
Esse acesso ao time stamp definido para zero.
Uma consequência deste esquema de bloqueio é que bloqueios compartilhados não protegem uma ligação lógica entre as páginas contra as alterações. Portanto, as páginas encontradas através de um link sempre tem de estar se reavaliando antes de poderem ser usadas.
Exemplo 1 ilustra este efeito.
Note-se que em situações de alta carga, mais de um segmento poderia copiar a mesma página de banco de dados. Apenas uma destas duas cópias devem sobreviver. Para este efeito, o intercâmbio na estrutura hash para pesquisa deve ser atômica. Ela falhará se o endereço a ser substituído não é o esperado.
4 Salvando as Alterações para o Disco
O gerenciador de buffer pool do Adabas salva as páginas alteradas no disco de forma assíncrona. Quando um certo (configurável) porcentagem de todas as páginas foram modificadas, uma thread assíncrono (chamada de buffer flush thread) começa a gravar todas as páginas alteradas no disco. Claro, as páginas não devem ser modificadas, enquanto eles estão sendo gravados no disco.
Por outro lado, não é aceitável diferir modificações dessas páginas até que a gravação tenha sido feita. Se uma página que está bloqueada pelo buffer flush trhead é para ser modificada por uma outra thread, o mesmo bloqueio de multi-version como descrito acima é aplicada. As páginas envolvidos no buffer flush são bloqueados pelo segmento buffer flush thread usando um bloqueio de leitura privilegiada. Se uma página atual da gravação esta bloqueado, ela é inserido em uma lista de bloqueio recusado e ignorado. Depois que todas as outras páginas estão bloqueadas, os blocos buffer flush thread nas páginas na lista de bloqueio recusada se necessário. Normalmente, o comando de atualização que tinha realizado um bloqueio nessas páginas foram entretanto liberado do bloqueio
A gravação assíncrona de páginas alteradas tem algum consequências:
(*) Uma página que foi escolhido para a substituição não precisa ser gravada no disco antes de ser substituído, o que permite uma rápida substituição.
(*) As páginas não podem ser substituídos se elas tenham sido alterados após o último buffer flush. Portanto, um buffer flush deve ocorrer antes que muitas páginas estão sujas (dirty). Por outro lado, o flushing muito cedo destrói o efeito de cache para atualizações porque as páginas são gravadas no disco depois de poucas atualizações por página. Obviamente, encontrando um percentual razoável de páginas sujas para o início de um flush buffer não é trivial. A fim de aliviar o DBA a esta tarefa, o Adabas pode escolher uma percentagem útil e internamente adaptar à situação atual.
(*) Os algoritmos de recuperação de acidente estão fortemente acoplados à gravação assíncrona. O início e o fim do buffer flush são registrados. A partir desta informação registrando o algoritmo de recuperação de falhas pode-se deduzir que as alterações de banco de dados já estão incorporados no disco e que não são (possivelmente). Por isso, é essencial que todas as páginas alteradas sejam cobertas pelo buffer flush. Por outro lado, as páginas que são muito atualizados com freqüência pode diferir consideravelmente todo o buffer flush. Para lidar com tais situações, o buffer flush pode ser dividido em uma primeira parte que contém todas as páginas que podem ser bloqueadas sem bloquear o bloqueio, e uma segunda parte que descarregou todas as outras páginas (e geralmente lida com muito poucas páginas).
5 Buffer Replacement Handling
Como apontado anteriormente, o buffer flush do Adabas é bastante sofisticado. Se uma página de um determinado com um tamanho de página é para ser lida na área de buffer, e o buffer pool está cheio (que é o caso normal após uma fase inicial de enchimento), o espaço necessário deve ser fornecido ao selecionar outro buffer que pode ser gravado em cima. No entanto, por causa das diferentes de tamanhos de página em um banco de dados Adabas, pode ser necessário a substituição de várias outras páginas de tamanho menor. Nos bancos de dados com um tamanho fixo principal, a primeira página disponível durante a pesquisa a partir da extremidade da corrente LRU pode ser escolhido para a substituição. Isso não é verdade para o Adabas.
Considere o seguinte caso: uma página com tamanho de 4 KB tem de ser lido no buffer. No final da corrente LRU, apenas a pagina de 2 KB podem ser encontrado. A próxima página 4 KB é muito no início da corrente LRU, ou seja, é uma página muito nova. Neste caso, uma das páginas 2Kb e a sua vizinha física deve ser substituído. No entanto, o vizinho físico também pode ser uma página muito nova. Para encontrar bons candidatos de substituição, o seguinte tratamento é aplicado. A corrente LRU é pesquisada a partir do seu fim. Quando uma página é encontrada, que esteja disponível para a substituição (ou seja, não contém qualquer alteração, que não foi gravada e não esteja bloqueada), o Adabas procura o espaço necessário a partir desta página. Os vizinhos restantes são considerados, desde que possam ser substituído e o espaço necessário ainda não é recolhida. Então, os vizinhos certos são verificados. O espaço entre o mais à esquerda vizinho encontrou e o mais à direita geralmente deixa várias opções para os chamados conjuntos de sobreposição, ou seja, conjuntos de buffers que podem ser substituído para ganhar o espaço necessário (Figura 2). O conjunto de sobreposições com os menores custos é armazenada.
+------------------------+ +-----------------------+
^ | ^ |
+----+----+----+----+----+-+--+--+-+----+----+----+--+-+----+
| | | | | | | |xxxx| | | | |
| | | | | | | |xxxx| | | | |
+-+--+----+--+-+--+-+----+--+-+--+-+----+----+-+--+--+-+--+-+
| | | | | | |
| | | | | +----|--------------------------+
| | | | +--+ +-----------------+ |
| | | +----------|---------------------+ | |
| | +---------------|----------+ | | |
| +--------+ | | | | |
| | | | | | |
+-+-------+-----+---+---------+--+------+---+-----+----+----+----+----+---+-----+
| | | | | | | | |
| 17 | 19 | 1237 | 13 | 1567 | 34 | 99 | 65 |
| | | | | | | | |
+---------+---------+----+----+---------+---------+---------+---------+---------+Então a busca LRU continua a busca, até um limite máximo das páginas encontradas for alcançado, ou até a uma página única for encontrada que é grande para tornar o espaço necessário. Esta página única é definida para substituição. O conjunto de substituição mais barato é escolhida para ser substituída.
O custo de um substituição é determinada pela aplicação de uma função para os time stamp de acesso das páginas no definidas. A escolha desta função influencia fortemente o algoritmo de substituição. Se a função for MIN (minimo), por exemplo, a primeiro definição de substituição encontrado seria selecionada. Se a função é SUM (soma), a probabilidade de uma substituição de multi-buffer diminui rapidamente com o número de páginas. No caso da função MAX (maximo), a definição de substituição é escolhida somente se todas as suas páginas são mais velhas do que os mais antigas páginas único substituível de tamanho suficiente.
Obviamente, busca por candidatos de substituição é uma operação que leva um tempo bem longo, devido à necessidade de lidar com diferentes tamanhos de página. Infelizmente, a corrente LRU não pode ser alterado enquanto tal pesquisa é realizada. Uma vez que cada acesso a uma página de banco de dados deve atualizar a corrente LRU (colocando a página acessada na frente da corrente LRU), há uma considerável gargalo. Para evitar contenção de bloqueio na corrente LRU, o Adabas divide a área de buffer em várias regiões físicas, onde cada região tem sua própria corrente LRU. O número de regiões depende do tamanho do conjunto de memória intermédia, o máximo paralelismo permitido pelo DBA, e outros critérios.
Estas regiões físicas são escolhidos para a substituição de uma maneira round-robin. Só a corrente LRU afetada está bloqueado. Além disso, as atualizações para a corrente LRU são diferidos. Obviamente, as atualizações não precisa ser feito antes de uma busca substituição é executada. Assim, o acesso a páginas é memorizado, mas é reflectida na corrente LRU apenas quando a fechadura para a pesquisa for necessária a substituição de qualquer maneira. Note-se, que, em contraste com o processo usado no ORACLE [Br97], os algoritmos Adabas reflecte a sequência correcta de acessos na cadeia LRU.
6 Prefetching
Operações seqüenciais que fazem scan dos dados de várias páginas de banco de dados adjacentes são bastante comuns. No Adabas, o DBA pode otimizar para tais operações, por exemplo, ao escolher tamanhos de página grandes. No entanto, tais optimizações são complexas e podem diminuir o desempenho dos comandos com diferentes padrões de acesso. Portanto, o Adabas reconhece o acesso sequencial, e pode ler várias páginas em uma IO em uma área de buffer pool contíguo. O algoritmo de substituição descrito acima, obviamente, cobre este caso sem adaptação. Apesar de ler com um I/O, todas as páginas têm o seu próprio cabeçalho e são gerenciados pelo gerenciador de buffer pool como se foi lido separadamente. O número de páginas a serem lidas de um IO é determinada dinamicamente, de acordo com os seguintes critérios:
(*) Número máximo de páginas necessários para o atual comando;
(*) Número de páginas que se encaixam em um único I/O físico. Isto depende da plataforma, mas também depende da distribuição dos arquivos de datasets sobre discos;
(*) Próxima página que já está na área de buffer. A fim de evitar inconsistências com atualizações nesta página, a página não deve ser relido no buffer;
(*) Espaço disponível na área de buffer pool;
7 Resumo
O gerenciador do buffer pool do Adabas foi completamente redesenhado para a mais recente versão paralela do Adabas. Em particular, o bloqueio da corrente LRU tinha sido um gargalo, em particular porque o algoritmo de substituição é muito complexo devido aos diferentes tamanhos de página utilizados em um banco de dados. Para evitar contenção de bloqueio na corrente LRU, tem sido dividido em diversas áreas. Além disso, a atualização da corrente LRU é feito preguiçosamente. A fim de aumentar o paralelismo e evitar impasses em particular em operações de índice, protocolos dedicado a multi-versão de bloqueio foram introduzidos. Várias otimizações dinâmicas para aliviar o DBA de ajuste muito sofisticado. O uso de mais algoritmos de auto-ajuste, como LRU-2 é constantemente investigada. Retirado - Clique Aqui
0 comentários:
Enviar um comentário