Quem mexe com bancos de dados há vários anos conhece um "fantasminha" nada camarada: a contenção entre clientes, às vezes mencionada incorretamente como deadlock. A causa é igualmente conhecida: vários clientes atualizando os mesmos dados ao mesmo tempo, forçando-os a formar uma fila e causando lentidão. Não chega a ser um deadlock pois as atualizações acabam acontecendo; num deadlock legítimo, o tempo de espera é realmente infinito.
A ocorrência de contenção é mitigada ou exacerbada pelo mecanismo de travamento (locking) adotado pelo banco de dados. A existência deste mecanismo é essencial para garantir a integridade dos dados -- deixar duas atualizações se misturarem seria rápido, mas acabaria dando resultados análogos ao filme "A Mosca".
Nos meus bons tempos de Clippeiro, a contenção costumava acontecer em torno dos índices, não dos arquivos em si. O Clipper trava apenas um registro por vez durante a atualização, o que é rápido e gera pouca contenção, muito embora não garanta nem de longe uma transação ACID. Já os índices, por serem estruturas mais complexas (árvores B-Tree) exigiam travamento do arquivo inteiro na atualização. Algumas software houses usavam drivers de índices de outros fornecedores, na tentativa de melhorar a escalabilidade.
Surpreendentemente, inúmeros outros produtos bem mais pretensiosos que o Clipper apresentavam problemas graves de contenção. Entre os que vi pessoalmente, estão o ZIM e o banco de dados MS SQL (versões mais antigas baseadas no Sybase). Chegavam a apresentar problemas piores que o Clipper por não travarem os dados por registro, mas sim por página de dados, causando contenção mesmo quando os clientes estavam apenas atualizando dados "próximos" mas não-relacionados.
O primeiro banco de dados que conheci que resolvia o problema de forma efetiva era o Borland Interbase, hoje conhecido como Firebird e bastante popular entre desenvolvedores Delphi. Embora não seja incrivelmente rápido, funciona bem e evita contenções e deadlocks de forma muito transparente.
Um detalhe histórico: muita gente migrou do Clipper para o Delphi, e o Interbase/Firebird ajudou na migração pois desobrigou os clippeiros de aprender a difícil arte de lidar com contenções em bancos como MS SQL/Sybase, muito popular na mesma época.
Bem, o Interbase evitava contenções, deadlocks e ainda garantia transações ACID usando um único mecanismo: multigerações (MVCC). A idéia é: nunca atualize ou apague um registro (ou melhor, uma "linha"). Se for necessário atualizar, adicione um novo registro ao fim do arquivo. Se for necessário apagar, adicione um novo registro marcando-o como apagado. Dados "velhos" nunca são atualizados, portanto nunca precisam ser travados, e não existe mais possibilidade de contenção.
Parece até idiota de tão simples, mas funciona maravilhosamente bem. O esquema tem dois defeitos relativamente pequenos: gasta mais disco e pode ser mais lento que um esquema baseado em páginas. Cada registro precisa ter mais duas colunas, normalmente ocultas ao usuário: um "timestamp" que indica quando o registro foi criado; e algum flag "apagado" que indica se aquela versão do registro foi apagada.
Uma vantagem decisiva deste esquema é que o arquivo de banco de dados pode ser copiado "a quente", ou seja, com o banco funcionando. Na pior das hipóteses, a cópia pode pegar o último registro pela metade, mas o arquivo lido até ali estará consistente. Um banco de dados normal nunca pode ser copiado "a quente", pois o arquivo pode estar sendo modificado aleatoriamente, e a cópia pode misturar partes "velhas" com partes "novas" do mesmo arquivo.
Parece que todos os bancos de dados recentes têm multigerações (MVCC). No caso do MySQL, os drivers InnoDB e Falcon têm este recurso (embora no InnoDB haja contenção em torno de UPDATEs, por razões de design).
Um outro recurso facilmente implementável num banco de dados com MVCC, é a criação de "snapshots" -- a possibilidade de fotografar e consultar o banco de dados como ele estava num momento do passado. É de certa forma uma mancada do Interbase/Firebird não ter oferecido este recurso desde as primeiras versões, já que estava prontamente disponível.
Snapshots são bem mais úteis do que parece a princípio. Já esqueci quantas e quantas vezes recebi reclamações de usuários, porque, por exemplo, alguém mexeu erradamente no cadastro de um cliente. Muitos sistemas comerciais mantém os registros antigos, de forma explícita, criando tabelas de "arquivo morto" etc.
Por "hacking value", vamos ver como seria implementar MVCC sobre um banco de dados que não oferece tais recursos nativamente. Assim como foi dito antes, criamos a tabela com dois campos extras:
CREATE TABLE t ( codigo INT NOT NULL, nome VARCHAR, _timestamp TIMESTAMP NOT NULL, _deleted INT NOT NULL DEFAULT 0, PRIMARY KEY (codigo, _timestamp) );
A chave primária normal seria o campo "código", mas teremos diversas versões do mesmo registro na tabela, logo ele não pode ser, isoladamente, uma chave primária. Já o par código + momento da criação do registro é garantidamente único (se o timestamp tiver precisão suficiente).
Para adicionar dados nesta tabela, não precisamos especificar as colunas "especiais", pois pelo menos no MySQL, um timestamp é automaticamente preenchido com a hora da máquina se não for informado um valor a ele. Talvez um timestamp artificial (um simples contador) fosse mais apropriado... mas estamos apenas fazendo uma brincadeira, ora!
Podemos adicionar quantas versões quisermos do mesmo código. Para "apagar" um registro, basta adicionar um registro novo com a coluna _deleted igual a 1. Agora, na hora de recuperar os dados, provavelmente queremos só as versões mais recentes. Isso se consegue com:
select * from t t1 where t1._timestamp = (select max(_timestamp) from t where t.codigo = t1.codigo) and _deleted = 0;
Não muito eficiente... mas funciona! Honestamente, não consegui "desenrolar" esta consulta de forma a não usar subconsultas, que costumam trazer problemas de desempenho.
De qualquer forma, o comando acima traz todos os registros mais recentes e omite os que têm o último registro marcado como apagado. Se quiséssemos espiar como o banco de dados estava no dia 1/maio/07, às quatro e meia da tarde, basta fazer:
select * from t t1 where t1._timestamp = (select max(_timestamp) from t where t.codigo = t1.codigo and t._timestamp <= "2007-05-01 16:30" ) and _deleted = 0;
Vamos supor que nosso banco de dados SQL acima não tivesse suporte a transações. Uma das características de uma transação é a isolação: ela não deve enxergar dados "novos", que foram adicionados depois que a transação começou. Foi o que a gente acabou de fazer com o comando SQL anterior: basta colocar a data-limite como sendo o momento que a transação iniciou. A garantia "I" do ACID está na mão.
As garantias "A" (atomicidade) e "D" (durabilidade) não dependem apenas do MVCC, mas também de interação com o sistema de arquivos, portanto ficam fora do escopo da nossa brincadeira. A garantia "C" (consistente) também é uma questão de criar chaves estrangeiras nos lugares certos.
Uma garantia, fora do ACID, mas que todo sistema MVCC oferece, é impedir que duas transações concorrentes atualizem o mesmo dado. Num nível mais baixo isso nunca acontece, mas no nível da aplicação, pode acontecer, digamos, de o mesmo cliente 1234 ser atualizado por 2 transações simultâneas. Qual das versões vai ficar como a mais atual? Vai depender da sorte -- o que é inaceitável no contexto de bancos de dados.
Sistemas MVCC de verdade detectam tais conflitos, deixam a primeira transação finalizar, e abortam as demais. Não sei se as aplicações tratam isso corretamente na prática; já vi muitos programas simplesmente tentarem novamente a mesma transação, ignorando as alterações feitas pelo outro usuário.
Mas assumindo que a aplicação faz a coisa certa, como poderíamos simular a detecção de conflitos com nosso MVCC caseiro? Até onde consegui imaginar, o único jeito seria armazenar todas as alterações em memória, e verificar se houve mudanças nesses registros antes de gravá-los.
Parece uma solução pela metade, mas é a estratégia que o novo backend do MySQL, o Falcon, adota. O desenvolvedor do Falcon foi o grande "cérebro" por trás do Interbase. O Interbase é mais cuidadoso e armazena os dados das transações em andamento no disco, de forma que podem ser recuperados após uma queda do banco. É um recurso muito reconfortante, mas na prática ele causa lentidão e provavelmente nenhuma aplicação lida com essa situação -- a transação pela metade é simplesmente descartada.
Uma coisa interessante dos bancos relacionais atuais é que eles tratam snapshots como recursos avançados, quase sagrados, de uso exclusivo do administrador do banco de dados. Talvez estejamos subutilizando o MVCC dos nossos bancos de dados. Explico.
Imagine a emissão de uma nota fiscal. Um dos motivos que o Fisco nos obriga a manter blocos de nota em papel, é que os dados ali impressos são eternos, ou seja, são um "snapshot" do momento da emissão da nota.
Se, digamos, a razão social (nome comercial) do cliente for alterado após a emissão da nota, isso causa problemas numa eventual reemissão da nota, pois os dados sairiam diferente da primeira. A solução mais comum para este embaraço é armazenar todos os dados impressos na própria tabela de notas fiscais, gerando um grande volume de dados duplicados pois na prática poucos clientes mudam de nome ou endereço.
Se o banco de dados oferecesse os recursos de versionamento e snapshotting de forma mais acessível às aplicações, poderíamos fazer melhor. Bastaria obter o registro do cliente correspondente ao momento da emissão da nota (timestamp). Mesmo que o cliente mude de nome mil vezes, cada nota fiscal emitida para ele obteria o nome correto para a sua "época".
Certamente tal esquema usaria muitíssimo menos espaço em disco que gravar todos os dados da nota. Enquanto os bancos de dados não oferecem snapshots de uso tão fácil quanto o descrito acima, fica a sugestão para que você use o "MVCC de pobre" descrito mais acima, ao menos em tabelas-chave como cadastros de clientes, fornecedores etc.
Agora, divertido mesmo seria implementar um banco de dados MVCC "do zero". Na verdade, nem é tão difícil assim; como dito bem no início do artigo, o bicho pega mesmo é na hora de implementar os índices, pois estes têm estrutura em árvore, e precisam sofrer atualizações em trechos preexistentes.
O banco de dados ZODB do produto Zope é exatamente isso, uma implementação começada do zero, e ainda por cima baseada em Python. O ZODB tem todas as características que desejamos: multigerações, snapshots, transações ACID e concorrência sem contenção.
Como o ZODB foi feito para ser usado por um Zope rodando na mesma máquina, o acesso via rede exige um segundo serviço denominado ZEO, que atende as requisições de rede e repassa localmente ao ZODB. A solução ZODB para os índices é bastante curiosa: eles ficam fora do banco de dados propriamente dito, cortando pela raiz o problema de contenção em torno do índice.
A aplicação pode usar o mecanismo de índice que quiser, se quiser. É responsabilidade desse mecanismo manter a árvore de índice. Para sítios de pequeno porte, manter o índice em memória é a estratégia mais robusta. Mesmo tabelas com centenas de milhares de registros são indexadas em poucos segundos num computador moderno. (Naturalmente, não é uma estratégia válida para bancos com terabytes de tamanho...).
Outra vantagem do ZODB é o fato dele ser um banco de objetos, não um simples banco de dados. Através de alguns truques Python, pode-se lidar com uma tabela como se ela fosse uma lista Python em memória. Se a tabela não tiver um "schema", pode-se armazenar qualquer objeto nela -- completamente diferente da visão "quadrada" do SQL com suas linhas e colunas. Às vezes a caretice do SQL garante a integridade dos dados, o que é importante em certas aplicações caretas porém vitais. (Isso não desqualifica um banco de objetos para aplicativos críticos -- basta impor um "schema").
Mas enfim, nada como reinventar a roda.
Para começo de conversa, é preciso definir o layout dos dados no arquivo. O layout mais simples de tratar, que por nova coincidência era o utilizado no dBase/Clipper, é o registro de tamanho fixo, com algum cabeçalho "mágico" em cada registro para achar os registros em caso do arquivo ficar corrompido:
preâmbulo (apenas uma vez no início do arquivo) {
tamanho do registro
último timestamp gravado
checksum ou MAC
}
registro (repetido várias vezes ao longo do arquivo) {
número mágico
campo/coluna 1
campo/coluna 2
...
campo/coluna n
hora de criação (_timestamp)
apagado? (_deleted)
checksum ou MAC
}
Uma coisa que o dBase não tinha era o campo final de checksum. Ele é útil tanto para verificar se cada registro está íntegro, como para detectar transações feitas pela metade.
Quando o banco de dados for iniciado, basta recalcular o checksum do último registro do arquivo; se ele estiver errado, ou pior, o comprimento do último registro estiver menor que o esperado, ele está corrompido e deve ser descartado. Este truque nós já usamos em outro artigo sobre transações ACID usando arquivos comuns.
Um checksum comum protege contra corrupção acidental, mas não contra alteração maliciosa dos dados. Uma opção ainda melhor de checksum é um algoritmo MAC (message authentication code). É basicamente um checksum com qualidade criptográfica, baseado numa chave secreta. Ele também permite verificar se o registro foi adulterado por alguém que não conhecia a chave secreta.
Uma transação geralmente vai envolver mais de uma tabela, portanto mais de um arquivo. Os dados gravados numa única tabela são insuficientes para determinar se a transação como um todo foi inteiramente gravada. É necessário ter um "arquivo mestre", que contém apenas a seguinte estrutura, semelhante ao preâmbulo de um arquivo comum:
transação (apenas uma vez) {
último timestamp de transação
checksum ou MAC
}
Ao gravar uma transação, este arquivo-mestre deve ser o *último* a ser atualizado. Isso garante que, se houver um registro com timestamp mais novo que o arquivo-mestre, esse registro deve ser descartado pois é resíduo de uma transação gravada pela metade.
Na verdade, ainda segundo o nosso outro artigo, o arquivo-mestre deve ser gravado em duas ou mais cópias, pois este arquivo é regravado inúmeras vezes e a chance de corrupção é muito grande; ter mais cópias garante que podemos sempre ter acesso a uma cópia boa.
O nosso arquivo-mestre proposto acima é sobrescrito inteiramente a cada final de transação. Se, por um motivo qualquer, gostaríamos de ter uma lista de transações para consulta posterior, basta ir adicionando o registro de transação ao final dos arquivos-mestre sem sobrescrever a transação anterior.
Com esta estrutura simplíssima, nossas transações serão quase ACID e nosso banco será MVCC. Do ACID, ainda falta a letra D - durabilidade - que é alcançada fazendo todas as gravações de arquivos em modo síncrono, o que garante que os dados estarão no disco, e não num suspeito buffer de memória.
Já que estamos criando algo do zero por capricho, vamos caprichar nos detalhes. O timestamp que utilizei nos comandos SQL de exemplo lá em cima é muito ruim, pois (pelo menos no MySQL) ele tem resolução de 1 segundo; um monte de registros vai acabar com o mesmo timestamp, o que pode gerar ambiguidades.
O timestamp ideal é 100% descartável, ou seja, é utilizado no máximo apenas uma vez. Um compromisso aceitável é usar um contador monotonamente crescente (zero, 1, 2, 3...) que é incrementado apenas a cada transação. Desde que impeçamos uma mesma transação de gravar duas atualizações do mesmo registro (basta descartar as redundâncias ainda em memória), isso bastará para os fins do MVCC, e o próprio arquivo-mestre conterá o último timestamp.
Faltou tratar um pequeno e grande problema: os índices. Não podemos ignorá-los porque, conforme mostrado nos testes com SQL, os índices são cruciais para encontrar rapidamente as versões mais recentes de cada registro. Sem falar que chaves primárias dependem de índices para funcionar etc.
O problema dos índices é tornado pior pelas inúmeras opções: manter a tabela em ordem; índices em bitmap; árvores B+, hashes... As árvores B+ são as mais comumente usadas, são o burro de carga dos bancos de dados.
Para quem nunca implementou uma árvore B+, vai uma breve introdução. A estrutura básica gravada em disco, para uma árvore de ordem 4, é a seguinte:
nó da árvore {
registro 1
registro 2
registro 3
numero de registros ocupados
galho 0
galho 1
galho 2
galho 3
}
Essa estrutura é idealmente de tamanho fixo, tal qual nosso registro de dados MVCC. Normalmente, não se coloca o registro inteiro numa árvore B+; o índice é gravado num arquivo em separado dos dados. Grava-se no índice apenas o valor do índice e um apontador qualquer para onde está o registro de dados (pode ser por exemplo o número sequencial do registro dentro do arquivo MVCC).
Na medida que o arquivo de índice cresce, podemos adicionar novos nós ao arquivo de forma parecida ao arquivo MVCC (implementações eficientes nunca removem blocos velhos dos índices). O problema é que neste caso não podemos "gravar e esquecer"; será necessário voltar atrás e atualizar o nó de vez em quando.
Supondo um índice vazio, com apenas um nó em disco. Para as três primeiras inserções de novos registros, basta ir ocupando as "casinhas" do nó. Como nosso exemplo é de ordem 4, cabem até 3 registros. Detalhe: os registros são mantidos na ordem do índice dentro desse nó. Portanto, cada inserção reescreve praticamente todo o nó no disco.
+----+----+-----+ |João|José|Maria| +----+----+-----+
Se, neste ponto, alguém precisar fazer uma busca pela chave do índice, bastará fazer uma busca seqüencial na estrutura para achar o que deseja. Árvores B+ de verdade podem ter ordens muito maiores, em torno de 100, portanto para até 100 registros a busca é seqüencial ordenada.
Quando formos incluir o quarto registro... más notícias, acabou o espaço. Supondo que temos os valores "João", "José" e "Maria" no índice, e queremos inserir "Jonas" (que fica alfabeticamente entre "João" e "José").
O registro do meio da lista (José) vai ser "promovido" para um nó mais alto que o atual. Como este nó não existe, ele é criado, e José é movido para lá. Os demais registros são divididos em 2 grupos; os menores que José ficam no nó atual. Os maiores são realocados para um novo nó. No caso, apenas Maria será movida para o novo nó. Neste ponto, já temos 3 nós, e cada "santo" está alojado num deles.
+------+--------+--------+ | José | *vazio | *vazio | +------+--------+--------+ +----+-+-+ +-----+-+-+ |João|*|*| |Maria|*|*| +----+-+-+ +-----+-+-+
Falta inserir Jonas; ele será colocado no mesmo nó que João, pois alfabeticamente, ele é menor que José.
+------+--------+--------+ | José | *vazio | *vazio | +------+--------+--------+ +----+-----+-+ +-----+-+-+ |João|Jonas|*| |Maria|*|*| +----+-----+-+ +-----+-+-+
O problema é que os nós estão "soltos no espaço"; não há uma relação formal entre eles. Nós sabemos que essa relação existe, mas um computador não saberia. Aí entram em cena os "galhos".
O nó "José", que dissemos ser de nível mais alto, é quem tem de se ligar aos demais. O galho 0 é apontado para o nó de "João/Jonas", e o galho 1 é apontado para o nó de "Maria". Por que?
Pois os galhos do nó têm uma relação com os registros. O galho zero aponta para elementos "menores" que o registro 1 (no caso, Jonas é menor que José). O galho 1 aponta para elementos maiores que o registro 1, porém *menores* que o registro 2. E assim por diante.
+------+--------+--------+
| José | *vazio | *vazio |
+------+--------+--------+
| |
| |
| |
| |
| |
| |
| |
+----+-----+-+ +-----+-+-+
|João|Jonas|*| |Maria|*|*|
+----+-----+-+ +-----+-+-+
| | | | | | | |
x x x x x x x x
Se viéssemos a inserir Joni e Jofre, eles cairiam no mesmo nó que João e Jonas. No momento de inserir Jofre, o nó estaria lotado. O registro mediano de João/Jonas/Joni é, obviamente, Jonas, que é promovido e movido para junto de José na raiz da árvore. Um novo nó é criado, e Joni é movido para lá. Jofre é finalmente inserido junto de João.
O nó-raiz consiste agora de Jonas e José. Precisamos rearrumar os galhos. O nó João/Jofre continua no galho 0, pois são menores que Jonas. O nó Joni é ligado ao galho 1, pois é maior que Jonas e menor que José. O nó Maria é reconectado ao galho 2, pois José está agora no registro 2. O arranjo final da árvore seria:
+-------+------+--------+
| Jonas | José | *vazio |
+-------+------+--------+
| | | |
| | | x
| | |
| | |
| | |
| | |
| | |
+----+-----+-+ +----+-+-+ +-----+-+-+
|João|Jofre|*| |Joni|*|*| |Maria|*|*|
+----+-----+-+ +----+-+-+ +-----+-+-+
| | | | | | | | | | | |
x x x x x x x x x x x x
A manutenção de índices num sistema MVCC radical como o nosso tem uma vantagem: registros nunca são atualizados ou removidos; são apenas adicionados. Parece que é possível que várias threads atualizem a mesma árvore B+ mediante locking por nó. Tiramos proveito dos fatos: a busca por um dado sempre corre de cima para baixo, enquanto a inserção sempre mexe na árvore de baixo para cima.
Se tivéssemos apenas threads de consulta ou apenas threads de inserção, elas poderiam conviver trivialmente. No caso das inserções, o nó que estiver sendo alterado por uma thread tem de ser travado. e as outras threads de atualização que vêm em seguida esperam pelo destravamento em fila. O travamento pode ser implementado por mutex em memória, de forma nenhuma precisa ser feito no nível de sistema de arquivos (a não ser que haja vários processos ou computadores manipulando o mesmo arquivo).
Tanto a inserção quanto a consulta devem travar o nó em foco, para gravação e também para *leitura*, pois o conteúdo do nó vai parecer bem bagunçado se alguém tentar consultá-lo enquanto estiver sendo atualizado -- ou pior, for atualizado enquanto estiver sendo lido! (Como a leitura é via de regra muito rápida e atômica, e se o nó for feito pequeno, talvez seja possível elidir travamento nas threads de consulta).
Se uma thread de consulta já "cruzou" com a de inserção e está lendo os nós mais abaixo, não há mais risco de interferência... a não ser que a consulta trombar com a próxima thread de inserção :)
Se a thread de consulta parar porque um nó está travado para atualização, ela não pode ingenuamente seguir adiante quando o nó destravar, pois pode ser que o dado em que a consulta está interessada tenha sido movido para o nó imediatamente acima -- que a consulta já leu e não tinha achado nada.
A thread de consulta tem de "observar" a inserção, e agir conforme. Se o nó travado tinha espaço vago a inserção terminou seu trabalho ali mesmo, e a consulta pode simplesmente seguir adiante. Se o nó estava cheio, ele foi dividido em dois, e o nó superior (já lido) vai ganhar um novo elemento. A consulta deve recuar ao nó superior aguardar o destravamento, e reler os dados.
Como o nó superior pode também estar cheio, ser dividido em dois etc. pode acontecer de a thread de consulta ser "empurrada" de volta até o topo da árvore, e ser obrigada a reler tudo de novo. Se o índice tiver uma taxa muito alta de inserções, há o risco das consultas ficarem todas socadas no topo da árvore e nunca conseguirem completar. Um simples controle de deadline pode ser implementado para brecar as inserções, se houver consultas esperando tempo demais.