Protocolo com Base em Timestamp

Figura 1: Protocolo com Base em Timestamp

Em uma situação onde o acesso a um determinado item do Banco de Dados é realizado apenas um por vez, ou seja, existe apenas uma única transação utilizando aquele item de dado, é bem simples entender o funcionamento do SGBD sobre essa operação. A dificuldade começa a ocorrer quando temos mais de uma operação tentando fazer uso do mesmo item de dado, pois será necessário que de alguma forma isso seja organizado de maneira justa e coerente.

Vamos ilustrar o evento através do exemplo de uma agência bancária onde existe apenas uma pessoa para o atendimento gerencial. Supondo que chegue apenas um cliente por vez na agência querendo falar com o gerente, não teremos problemas, afinal, será um único cliente exclusivo para que ele precise atender. Pensemos, na comum cena onde há vários clientes para serem atendidos pelo mesmo gerente. Precisaremos de um controle de concorrência, pois são várias pessoas tentando ter acesso a uma única pessoa. Usualmente, as agências bancárias adotam um controle através de senhas, sendo que a entrega é feita conforme a ordem de chegada a agência.

Podemos considerar isso como sendo um controle de concorrência, se a solução para este controle é a entrega de senhas. Se a ordem de entrega das senhas é feita conforme a chegada do cliente a agência, podemos supor então que cada cliente tem um tempo X, que determina o horário da sua chegada na agência. Se tivermos dois clientes A e B, sendo que, o cliente A chegou no tempo 1 e o cliente B chegou no tempo 2, logo, o cliente A será atendido primeiro que o cliente B, pois seu horário de chegada é mais antigo. Temos então, um controle de concorrência baseado no Registro de Tempo.

De forma similar, é preciso que o sistema de banco de dados faça o controle da execução quando existem transações que estão concorrendo entre si, para garantir a consistência do banco de dados. Consistência esta que, quando na transação concorrente, precisa estar assegurada para garantir que qualquer escala executada tenha o mesmo efeito de uma outra qualquer que fosse executada sem nenhuma concorrência, para tanto, a escala de execução deve, de alguma forma, ser equivalente a uma escala sequencial.

Para cada transação iniciada, é associado um timestamp fixo exclusivo, ou seja, antes que uma transação tenha início, o sistema de banco de dados fornecerá um rótulo de tempo (lembrando que este é um identificador exclusivo criado pelo SGBD para identificar uma transação).

Supondo que temos duas transações A e B, a transação A se iniciou no tempo 1 e a transação B teve início no tempo 2, logo, a transação A será executada primeiro que a transação B, pois seu tempo de início é mais antigo.

Para implementar este esquema de rótulo de tempo, temos duas possibilidades:

  • Usar a hora do relógio do sistema (clock) sendo esse o timestamp, então, o horário de início da transação será igual à hora em que a transação entra no sistema.
  • Usar um contador lógico que é incrementado sempre que se usa um novo timestamp, isto é, o timestamp da transação é igual ao valor do contador no momento em que a transação entra no sistema. Os rótulos de tempo da transação são numerados com 1, 2, 3 e assim consecutivamente (o computador tem uma valor máximo finito, de modo que o sistema precisa reiniciar o contador periodicamente para zero quando nenhuma transação estiver sendo executada por algum período curto de tempo).

O algoritmo precisa garantir que a ordem em que o item está sendo acessado não está violando a ordem do rótulo de tempo, e para isso o algoritmo associa a cada item X do banco de dados dois valores de rótulo de tempo(TS), sendo:

  • read_TS(X) - rótulo de tempo de leitura;
  • write_TS(X) - rótulo de tempo de gravação;

Esses timestamps são atualizados sempre que uma nova instrução read_TS(X) ou write_TS(X) é executada. Sempre que uma transação read e write é desfeita pelo esquema de controle de concorrência, esta transação recebe um novo timestamp e é reiniciada. O rótulo de tempo (TO) compara o rótulo de tempo de T com read_TS(X) e write_TS(X) para garantir que o rótulo da transação de tempo não seja violada, ou seja, o protocolo de ordenação de timestamp irá garantir que qualquer operação read ou write que esteja em conflito sejam executadas por ordem de timestamp.

O protocolo de ordenação de timestamp pode prevenir o deadlock (ou impasse). Existem dois esquemas que impedem o deadlock, eles são chamados de:

  • Wait-die (esperar-morrer) - uma transação A que iniciou no instante 1 e uma transação B que iniciou no instante 2, logo, o timestamp de A B, então, a transação A será abortada (morre) e será reiniciada posteriormente com o mesmo rótulo de tempo.
  • Wound-wait (ferir-esperar) - uma transação A que iniciou no instante 1 e uma transação B que iniciou no instante 2, logo, o timestamp de A B, então, a transação A tem permissão para esperar.

Em ambos os esquemas, a transação mais nova (que entrou depois) acaba sendo abortada pela transação que é mais velha (que entrou primeiro), se elas estiverem envolvidas em um deadlock.

Nesta técnica existe a possibilidade de paralisação de transações longas, caso uma série repetitiva de transações curtas causar o reinício da transação longa. Caso isso ocorra, é necessário que as transações que estão em conflito sejam suspensas temporariamente para permitir que a transação seja concluída.

Há também a possibilidade que algumas escalas não recuperáveis sejam geradas. Para a solução podemos optar entre uma dessas 3 opções:

  • Gravar todas as escritas juntas ao final da transação, ou seja, enquanto as transações de escritas estão em andamento, nenhuma transação tem permissão para acessar qualquer um dos itens de dados que estão foram escritos.
  • Limitar o bloqueio, ou seja, são adiadas todas as transações de leituras de itens não confirmados, até que a transação que fez a atualização do item de dados seja confirmada.
  • Acompanhar as escritas não confirmadas, ou seja, dar permissão a uma transação apenas depois do commit de qualquer transação que tenha escrito um valor onde esta transação tenha lido.

E por aqui eu finalizo este artigo, no qual vimos o protocolo com Base em Timestamp (Registro de Tempo), utilizado no controle de concorrência. Vejo você nos próximos artigos.

Até breve. Um grande abraço.