System R
Recovery System
Vitor Silva
Tópicos


O System R
System R Recovery System






Shadows
Log
Protocolo Do, Undo, Redo
CheckPoints
Reinício do Sistema
Exemplo
O System R

“System R, an experimental database system, was
constructed to demonstrate that the usability
advantages of the relational data model can be
realized in a system with the complete function and
high performance required for everyday production
use.“ [A History and Evaluation of System R, 1981]
Arquitectura
Recovery System
Falha no Armazenamento (Discos)
1.

Imagens do estado da Base de Dados + Logs
das mudanças “antes” e “depois”
Falha no Sistema (Memória)
2.

Logs das mudanças + Shadow Pages
Falha na Transacção
3.

Logs das mudanças
Recuperação de Transacções não implica o reinício
do sistema
Shadow Files




Os ficheiros no sistema R contém um overhead de
recuperação e podem ser caracterizados como
shadowed ou nonshadowed
É da responsabilidade do utilizador a salvaguarda
dos Nonshadowed files
No caso dos shadowed files o RSS mantém duas
versões dos ficheiros: a versão actual e a versão
shadow.
Apenas a versão actual do ficheiro é actualizada por
operações RSS (excepto para salvar o ficheiro ou
restaurar o sistema)
Shadow Versions




Quando uma página shadow é actualizada pela
primeira vez no buffer pool é criada uma nova
página (versão actual)
De seguida, em cada actualização que envolva esta
página apenas a versão actual é alterada (a versão
shadow nunca é alterada)
Quando fôr altura de salvar o ficheiro a que
pertence a página, é salva a versão actual e
actualiza-se a tabela de páginas, libertando o
espaço ocupado pelas versões shadow
Restaurar um ficheiro significa descartar todas as
versões actuais das páginas e restaurar a tabela de
páginas anterior (da versão shadow)
Log’s


O log de transacções é implementado num
sistema de pilha push-down: escrever um
novo registo coloca-o na pilha, desfazer um
registo remove-o da pilha
Os registos de log de uma dada transacção
estão ligados por listas ligadas cujo factor
comum é o identificador de transacção
Registo de log









Nome do ficheiro
Identificador do atributo
Valor antigo do atributo
Novo valor do atributo
Alterações da
Transacção
Identificador de transacção
Informação de
Identificador de acção
controlo do
Carimbo Temporal
sistema de log
Dimensão do registo de log
Ponteiro para o registo de log anterior
desta transacção
Protocolo Do, Undo, Redo

As operações do RSS executadas sobre os
log’s são:




DO – executa a acção e escreve um registo no
log com a informação necessária
UNDO – com base num registo de log desfaz a
acção escrita pelo DO
REDO – com base num registo de log executa
novamente a acção escrita pelo DO
DISPLAY – opcional, traduz um registo de log para um formato
legível por uma pessoa
Acções do gestor de
recuperação do RSS






BEGIN – indica o início de uma transacção;
SAVE – designa um save point na transacção. Se uma
transacção incompleta for salvaguardada, o undo pode
parar nesse ponto em vez de desfazer toda a
transacção;
READ__SAVE – devolve os dados guardados no log
pela aplicação num dado save point;
UNDO – desfaz os efeitos de uma transacção até um
save point anterior;
ABORT – desfaz todos os efeitos de uma transacção;
COMMIT – assinala o término de uma transacção com
sucesso e faz com que as mudanças sejam guardadas
em disco;
Commit
Sistema R garante que as transacções que
fizeram commit podem ser refeitas e que as
transacções que falharam podem ser
desfeitas porque:

O log
das transacções
é escrito em
disco
antes
Uma
transacção
está concluída
com
sucesso
da “shadow database” ser substituída pela
quando
o registo de commit aparece no log em
“current database”;
disco
2. A acção commit escreve um registo de log de
1.
commit e depois força a escrita do log de
transacções em disco;
“Write ahead log protocol” [GRAY78]
UNDO


Undo – lê um registo de log, vê qual o
identificador de acção e invoca a operação
undo correspondente à acção tendo como
parâmetro os dados do registo de log
As alterações de uma transacção falhada
podem ser desfeitas lendo o log dessa
transacção desde o último registo até ao
primeiro e efectuando sucessivos undo, ou
até um save point prévio
Checkpoints (1/3)

Objectivo: limitar o trabalho (undo e redo)
necessário ao reiniciar o sistema

No Sistema R os checkpoints são imagens
do sistema num tempo em que não estão a
ser efectuadas acções RSS
Checkpoints (2/3)
Passos num checkpoint:

1.
2.
3.
4.

Lista de todas as transacções a decorrer, bem como
apontadores para o registo de log mais recente de cada uma
delas
Escrever no log do sistema o registo de checkpoint (contém
a lista de transacções a decorrer)
Todos os ficheiros são salvos em memória secundária (flush
buffer pool e directórios de shadow)
Endereço do registo de checkpoint é escrito na versão shadow
do estado, mais concretamente no directório
No reinício do sistema o ponteiro para o registo de
checkpoint poderá ser acedido directamente do
directório
Checkpoints (3/3)
Reinício do Sistema


Inicialmente o sistema de gestão de ficheiros
restaura os ficheiros às suas versões shadow
De seguida entra em acção o gestor de
recuperação que examina o registo de
checkpoint mais recente e detectar uma de
duas situações possíveis:


Se não existem transacções pendentes o sistema
já se encontra num estado consistente;
Se existirem transacções pendentes é necessário
restaurar o sistema a um estado consistente;
Exemplo
Identificação de transacções “winner” e “loser”;
Undo das “loser”, seguido de redo das “winner”;
Após o final do processo de reinício é efectuado um novo checkpoint;
Apenas após o final do processo de reinício é que o log e a versão
shadow da base de dados poderá começar a ser actualizada.
Bibliografia




“The Recovery Manager of the System R
Database Manager”- Jim Gray, Paul McJones,
Mike Blasgen, Bruce Lindsay, Raymond Lorie, Tom
Price, Franco Putzolu, Irving Traiger, 1981
“System R and the Relational Model” Anastassia Ailamaki , 2001
“A History and Evaluation of System R” - Donald
D. Chamberlin, Morton M. Astrahan, Michael W.
Blasgen, James N. Gray, W. Frank King, Bruce G.
Lindsay, Raymond Lorie, James W. Mehl, Thomas
G. Price, Franco Putzolu, Patricia Griffiths Selinger,
Mario Schkolnick, Donald R. Slutz, Irving L. Traiger,
Bradford W. Wade, Robert A. Yost, 1981
“Recovery Techniques For Database Systems” Joost S. M. Verhofstad, 1978