CONTROLE DISTRIBUÍDO DE CONCORRÊNCIADennis Williams e Wanderson de Lima

Roteiro Introdução Três problemas de concorrência Teoria da Serializabilidade Taxonomia dos mecanismos de controle de

concorrência Bloqueios Algoritmos baseados em TO Algoritmos otimistas Gerenciamento de impasses Controle de concorrência Relaxado Conclusão

Introdução Os SGBDs permitem que muitas

transações tenham acesso ao mesmo banco de dados ao mesmo tempo

Através da concorrência, é possível obter uma melhor vazão do SGBD

É necessário um mecanismo para garantir o isolamento das transações e a consistência do BD

Três problemas de concorrência Atualização perdida

T1 T2Read(X)X=X-M

Read(X)X=X+M

Write(X)Write(X)

Tem

po

O elemento X tem um valor incorreto porque sua atualização por T1 se perdeu

Três problemas de concorrência Leitura Suja

T1 T2Read(X)X=X-MWrite(X)

Read(X)X=X+MWrite(X)

Rollback

Tem

po

A transação T1 falha e deve voltar o valor de X ao seu valor antigo, porém T2 já leu o valor incorreto de X

Três problemas de concorrência Análise inconsistente

T1 T2Soma=0Read(A)Soma=Soma+A

Read(X)X=X-NWrite(X)

Read(X)Soma=Soma+XRead(Y)Soma=Soma+Y

Read(Y)Y=Y+NWrite(Y)

Tem

po

T1 lê X depois de subtrair de N e lê Y depois de somar N, portanto efetuou uma análise inconsistente

Teoria da Serializabilidade Um escalonamento S de n transações

T1,T2,..,TN é um ordenamento para as operações das transações sujeito a restrição de que, para cada transação Ti que participe em S, as operações de Ti em S devem aparecer na mesma ordem que ocorrem em em Ti. As operações de outras transações Tj podem se

intercalar com as operações de Ti em S Se, em um escalonamento S, as operações de

todas as transações não estão intercaladas, então o escalonamento é serial

Teoria da Serializabilidade Considere as três transações a seguir:

T1: T2: T3:Read(X) Write(X) Read(X)Write(X) Write(Y) Read(Y)Commit Read(Z) Read(Z)Commit Commit

O escalonamento S = {W2(X), W2(Y), R2(Z), C2, R1(X), W1(X), C1, R3(X), R3(Y), R3(Z), C3} é serial

Teoria da Serializabilidade Duas operações Oij(X) e Okl(X) estão em

conflito se tem acesso a mesma entidade de banco de dados X e se uma das operações é uma operação de gravação

Dois escalonamentos S1 e S2 definidos sobre o mesmo conjunto de transações são ditos equivalentes em conflito se, para cada par de operações conflitantes Oij(X) e Okl(X) (i≠k) sempre que Oij <1 Okl então Oij <2 Okl

Teoria da Serializabilidade Considere os dois escalonamentos a

seguir:

S = {W2(X), W2(Y), R2(Z), C2, R1(X), W1(X), C1, R3(X), R3(Y), R3(Z), C3}

S’ = {W2(X), R1(X), W1(X), C1, R3(X), W2(Y), R3(Y), R2(Z), C2, R3(Z), C3}

S e S’ são equivalentes em conflito

Teoria da Serializabilidade Um escalonamento é serializável se e

somente se ele é equivalente de conflitos com um escalonamento serial

A principal função de um controle de concorrência é gerar um escalonamento serializável para a execução de transações pendentes

Teoria da Serializabilidade O escalonamento da execução da transação

em cada site é chamando escalonamento local Em BDD não replicados, se cada

escalonamento local for serializável, sua união (chamada escalonamento global) é serializável, desde que as ordens de serialização local sejam idênticas

Se o BDD for replicado é possível que os escalonamentos locais sejam serializáveis, mas a consistência mútua do BD pode estar comprometida

Teoria da Serializabilidade Considere dois sites e um item de dado (X)

que é duplicado em ambos os sites. Além disso, considere as transações a seguir:

T1: T2:Read(X) Read(X)X = X + 5 X = X * 10Write(X) Write(X)Commit Commit

S1 = {R1(X), W1(X), C1, R2(X), W2(X), C2} S2 = {R2(X), W2(X), C2, R1(X), W1(X), C1}

Os dois escalonamentos são seriais. Se X=1, então S1 gera como saída 60 e S2 gera como saída 15 e a consistência mútua dos dois BDs é violada

Teoria da Serializabilidade Os escalonamentos que podem manter a

consistência mútua são chamados serializáveis de cópia única e atendem às seguintes condições: Cada escalonamento local deve ser

serializável Duas operações conflitantes devem estar

na mesma ordem relativa em todos os escalonamentos locais em que elas aparecem juntas

Taxonomia dos mecanismos de controle de concorrência

Taxonomia dos mecanismos de controle de concorrência Algoritmos pessimistas sincronizam a

execução concorrente mais cedo em seu ciclo de execução

A visão pessimista é a de que muitas transações entrarão em conflito entre si

Algoritmos otimistas atrasam a sincronização das transações até seu término

A visão otimista é a de que não haverá um número muito de transações que entram em conflito entre si

Bloqueios A ideia de bloqueio é que quando uma

transação necessita de uma garantia que um objeto no qual está interessada não mudará de algum modo enquanto a transação estiver ativa, então a transação adquire um bloqueio sobre o objeto

Bloqueios Bloqueio de modo múltiplo

Tipos de bloqueio Bloqueio de leitura(rl – read lock) Bloqueio de gravação(wl – write lock)

Operações read_lock(x) write_lock(x) unlock(x)

Bloqueios Regras:

Se uma transação A mantiver um bloqueio de gravação sobre uma unidade de bloqueio X, então uma solicitação de bloqueio de uma transação distinta B sobre X será negada

Se uma transação A mantiver um bloqueio de leitura sobre uma unidade de bloqueio X, então: Uma solicitação de uma transação distinta B de

bloqueio de gravação sobre X será negada Uma solicitação de uma transação distinta B de

bloqueio de leitura sobre X será concedida

Bloqueios As regras podem ser resumidas por meio

de uma matriz de compatibilidade de tipos de bloqueio Dois modos de bloqueios são compatíveis

se duas transações que acessam o mesmo item de dados podem obter esses bloqueios sobre esse item de dados ao mesmo tempo

RLi(X) WLi(X)RLi(X) COMPATÍVEL NÃO

COMPATÍVELWLi(X) NÃO

COMPATÍVELNÃO COMPATÍVEL

Bloqueios Protocolo de acesso a dados

Uma transação que deseja ler um item de bloqueio X tem de adquirir um bloqueio de leitura sobre X

Uma transação que deseja gravar um item de bloqueio X deve adquirir um bloqueio de gravação sobre X

Bloqueios O SGBD deve se encarregar de gerenciar

os bloqueios. Assim, o usuário não precisa especificar quando e como os dados devem ser bloqueados

Em sistemas baseados em bloqueio, o escalonador é um gerenciador de bloqueio e ele se comunica com o gerenciador de transação para estabelecer ou não o bloqueio e passar a operação ao processador de dados

Bloqueios Considere as duas transações e um

escalonamento gerado pelo bloqueio descrito anteriormente:T1:

T2:Read(X) Read(X)X=X+1 X=X*2Write(X)Write(X)Read(Y) Read(Y)Y=Y-1 Y=Y+2Write(Y)Write(Y)Commit CommitS = {wl1(X), R1(X), W1(X), lr1(X), wl2(X), R2(X), W2(X), lr2(X), wl2(Y), R2(Y), W2(Y), lr2(Y), C2, wl1(Y), R1(Y), W1(Y), lr1(Y), C1} S não é um escalonamento serializável

Se X=50 e Y=20, então S gera como saída X=102 e Y=38 se T1 for executada antes de T2 e X=101 e Y=39 se T2 for executada antes de T1

Bloqueios Como as operações de bloqueio e

liberação não são coordenadas, ele pode gerar escalonamentos não serializáveis

Para garantir a serializabilidade é necessário usar o bloqueio de duas fases ou 2PL(two-phase locking) A regra do bloqueio de duas fases é que

nenhum bloqueio deve ser adquirido pela transação após ela liberar um de seus bloqueios

Bloqueios As duas fases do 2PL são:

Fase de crescimento ou expansão Fase de contração ou encolhimento

Pode sofrer deadlock ou rollback em cascata

Bloqueios Bloqueio de duas fases com rollback em

cascata

Se T5 for abortada depois do passo read(A) da transação T7 ocasiona o rollback em cascata de T6 e T7

Bloqueios Bloqueio de duas fases sofrendo

deadlock

T3 já mantém um bloqueio de gravação sobre B e T4 solicita um bloqueio de leitura sobre B. Analogamente, T4 já mantém um um bloqueio de leitura sobre B e T3 está solicitando um bloqueio de gravação sobre A

Bloqueios Bloqueio de duas fases estrito

Libera todos os bloqueios juntos quando a transação termina(consolida ou aborta)

Evita rollbacks em cascata, mas pode sofrer deadlock

Bloqueios Refinamento no bloqueio de duas fases

Conversão de bloqueio de leitura para escrita Chamado de promoção ou upgrade Só pode ocorrer durante a fase de crescimento

Conversão de bloqueio de escrita para leitura Chamado de rebaixamento ou downgrade Só pode ocorrer durante a fase de contração

Bloqueios Considere o escalonamento abaixo:

S = {W1(X), R2(X), R3(Y), W1(Y)} S não é permitido pelo 2PL, pois T1

precisaria obter um bloqueio de gravação sobre Y depois de liberar seu bloqueio de gravação sobre X

Portanto, o 2PL ele não permite obter todos os escalonamentos que são serializáveis de conflito

Bloqueios 2PL centralizado

Um dos sites é designado como site primário é ele responsável pelo armazenamento das tabelas de bloqueio para todo o banco de dados, assim como concessão de bloqueios as transações

Os gerenciadores de transação dos outros sites se comunicam com o gerenciamento de bloqueio centralizado

Gargalo em torno do site central, menor confiabilidade devido a falha no site central

Bloqueios 2PL centralizado

Bloqueios 2PL de cópia primária

Uma das cópias(se houver várias) é escolhida como cópia primária e essa cópia tem de ser bloqueada para propósito de acessar essa unidade específica

Por exemplo, se a unidade de bloqueio X é replicada nos sites 1,2,3 e 1 é o site primário para X, a transação deve obter bloqueio em 1 para poder acessar uma cópia de x

Se x não tiver cópia, então a responsabilidade pelo gerenciamento de bloqueio fica entre diversos sites

Em relação ao 2PL centralizado, a única mudança é que os locais de cópias primárias têm de ser definidas para cada item de dados, antes de se enviar uma solicitação de bloqueio ou desbloqueio ao gerenciador de bloqueio

Bloqueios 2PL distribuído

A tarefa de gerenciamento de bloqueio é compartilhada por todos os sites de uma rede

Cada escalonador local é responsável pelas unidades de bloqueio locais a esse site

Em relação ao 2PL centralizado, a primeira mudança é que as solicitações de bloqueios são solicitadas aos gerenciadores de bloqueio de todos os sites participantes

A segunda mudança é que as operações são repassadas pelos gerenciadores de bloqueio participantes

Bloqueios 2PL distribuído

Algoritmos Baseados em TO Algoritmos que tentam não manter a

serializabilidade baseada em exclusão mútua.

Atribuição de um timbre de hora (timestamp) ts(Ti) a cada transação Ti.

Timbre de Hora: Identificador de cada transação de forma

exclusiva. Propriedades: exclusividade e caráter

monotônico.

Algoritmos Baseados em TO Atribuição de timbres de hora:

Uso de contadores globais. Uso de contadores locais.

Identificação por: <contador local, identificador de site>.

Clock do sistema. Regra de TO:

“Dada duas operações conflitantes Oij e Okl, que pertencem respectivamente às transações Ti e Tk, Oij só será executada antes de Okl se e somente se ts(Ti) < ts(Tk)”.

Algoritmos Baseados em TO Um escalonador que impõe a regra de TO

verifica cada nova operação que chega. Pode existir uma situação em que as

operações chegam ao escalonador numa sequência desordenada.

Atribuir a cada item de dados dois timbres de hora: Leitura (rts(x)) Gravação (wts(x))

Algoritmos Baseados em TO Algoritmo Básico de TO:

O gerenciador de transações fica no aguardo Se aparece uma operação do BD, verifica se:

Está no início de uma transação Atribui um timbre de hora à transação.

É leitura/escrita Envia a operação e seu timbre de hora ao escalonador do site.

É abort/commit Envia a operação ao escalonador.

Se a operação foi rejeitada pelo escalonador: Aborta a transação, reinicia e atribui um novo timbre de hora a

ele. Se a operação foi realizada com sucesso, informar ao

usuário.

Algoritmos Baseados em TO Algoritmo do Escalonador:

O escalonador fica no aguardo Armazena os valores de rts(x) e wts(x) iniciais. Se aparece uma operação, verifica se:

É leitura, verifica se ts(T) > rts(x): Envia ao processador de dados e atribui rts(x) <= ts(T).

É escrita, verifica se ts(T) > wts(x) e se ts(T) > wts(x): Envia ao processador de dados. Atribui rts(x) <= ts(T) e wts(x) <= ts(T).

É commit: Envia ao processador de dados.

É abort: Identifica os itens de dados acessados por T. Redefine os valores inicias de rts(x) e wts(x). Envia ao processador de dados.

Algoritmos Baseados em TO O escalonador garante que a transação

pode ser executada em outra oportunidade, caso tenha sido rejeitada anteriormente.

Isso pode ocorrer muitas vezes. Podem ocorrer em sites que estão

desativados há muito tempo. Pode-se usar contadores sincronizados

ou clocks como alternativas.

Algoritmos Baseados em TO Algoritmos de TO Conservadores:

Usados para reduzir essas probabilidades de reinicializações.

Atrasam as operações até que nenhuma das operações do escalonador tenham um timbre de hora menor do que o da transação.

Abordagem: Cada escalonador possui uma fila para cada

gerenciador de transações do sistema. O escalonador de um site i pode armazenar

operações que recebe do gerenciador de transações do site j.

Algoritmos Baseados em TO Algoritmos de TO Conservadores:

Algoritmos Baseados em TO Algoritmos de TO Conservadores:

Esse esquema reduz o número de reinicializações, mas não garante a eliminação delas.

Existem algoritmos extremamente conservadores que só admitem uma operação no processador de dados se em todas as filas de cada escalonador houvesse ao menos uma operação.

Algoritmos Baseados em TO Algoritmo de TO de várias versões:

Cada operação de gravação cria uma versão do item de dados.

Cada versão do item de dados é marcada pelo timbre de hora da transação que a cria.

Ele processa cada transação em um estado do banco de dados.

Algoritmos Otimistas Algoritmos pessimistas:

Algoritmos otimistas:

Algoritmos Otimistas Nos algoritmos otimistas, os timbres de

hora estão associados apenas as transações e não a itens de dados.

Os timbres de hora são atribuídos no início da validação.

O algoritmo que será discutido foi proposto em [Kung e Robinson, 1981] e estendido para SGBD's distribuídos [Ceri e Owicki, 1982].

Algoritmos Otimistas Cada transação é subdividida em várias subtransações.

Seja Tij uma subtransação de Ti executada no site j. A validação local de Tij é feita de acordo com as regras a

seguir, que são mutuamente exclusivas: Se todas as transações Tk tal que ts(Tk) < ts(Tij) tiverem

completado a fase de gravação antes de Tij iniciar sua fase leitura: A validação terá sucesso porque estarão em ordem sequencial.

Se houver qualquer transação Tk tal que ts(Tk) < ts(Tij) que complete a fase de gravação antes de Tij concluir sua fase leitura: A validação terá sucesso se ws(Tk)^rs(Tij) = 0.

Se houver qualquer transação Tk tal que ts(Tk) < ts(Tij) que complete a fase de leitura antes de Tij concluir sua fase leitura: A validação terá sucesso se ws(Tk)^rs(Tij) = 0 e ws(Tk)^ws(Tij) = 0

Algoritmos Otimistas

Algoritmos Otimistas É preciso assegurar a consistência

global, para garantir a regra de consistência mútua.

Não há um algoritmo otimista para isso. A transação é validada em termos globais

se todas as transações a precedem numa ordem terminam.

Algoritmos Otimistas Vantagens:

Quando os conflitos são raros, o algoritmo otimista comporta-se melhor que o algoritmo de bloqueio.

Possibilitam alto nível de concorrência. Desvantagens:

Alto custo de armazenamento. Uma transação pode falhar repetidamente

na validação.

Gerenciamento de Impasses Ocorrem em situações de exclusão mútua

ao acesso de recursos compartilhados. E as transações podem esperar em bloqueios.

É uma situação permanente. WFG (Wait for Graph).

Grafo orientado que representa o relacionamento entre as transações.

Os nós desse grafo representam as relações concorrentes do sistema.

Gerenciamento de Impasses Formação de um WFG é mais complicada

em sistemas distribuídos. LWFG e GWFG.

Gerenciamento de Impasses Métodos para tratamento de Impasses:

Prevenção Anulação Detecção e Resolução de Impasses

Gerenciamento de Impasses Prevenção:

O gerenciador de transações verifica da possibilidade de um impasse por uma transação.

Para executar essa verificação é preciso que os itens de dados sejam declarados previamente.

Vantagens: Redução de sobrecarga na avaliação de uma transação. Útil para sistemas que não desfazem processos.

Desvantagens: É difícil saber com exatidão quais itens de dados serão

acessados por uma transação.

Gerenciamento de Impasses Anulação:

São métodos mais adequados que a prevenção. Envolve técnicas de controle de concorrência ou

exigem que os escalonadores detectem a possibilidade do impasse.

A forma mais simples de resolver impasses: ordenar os recursos e insistir que cada processo solicite acesso aos recursos nessa ordem.

Unidades de bloqueio são ordenadas. Pode haver ordenação local ou global.

Gerenciamento de Impasses Anulação:

Uma abordagem é utilizar timbres de hora. Se a transação Ti é negada, então o

gerenciador de bloqueio não força Ti a esperar. Mas aplica um teste de prevenção na transação que solicita (Ti) e na transação que mantém bloqueio (Tj). Se aprovada Ti, espera por Tj, senão será

abortada.

Gerenciamento de Impasses Detecção e Resolução de Impasses:

É feita pela seleção de transações que serão abortadas para romper os ciclos GWFG.

É preciso avaliar alguns fatores: A quantidade de esforço investido na transação. O custo de abortar uma transação. A quantidade de esforço necessária para

concluir a execução da transação. O número de ciclos que contém a transação.

Gerenciamento de Impasses Detecção e Resolução de Impasses:

Detecção Centralizada: Um site é o responsável por detectar os impasses

para todo o sistema. Cada site envia seu LWFG ao detector de impasses,

que forma os GWFG e procura os ciclos nesse grafo. Comunicação x atraso.

Detecção Hierárquica: Os sites são dispostos em níveis. Cada site envia seu LWFG ao nível superior, até o nó

raiz.

Gerenciamento de Impasses Detecção e Resolução de Impasses:

Detecção Distribuída: Cada site será responsável por detectar os impasses.

No entanto, cada um deles comunica os WFG locais. Como cada site recebe os ciclos de impasses

potenciais de outros sites, as arestas responsáveis são adicionadas aos WFG locais.

As arestas representam que as transações locais estão esperando por transações remotas e vice-versa.

Ciclos envolvendo as arestas externas deverão ser comunicadas aos outros detectores de impasses.

Gerenciamento de Impasses Detecção e Resolução de Impasses:

Controle de Concorrência Relaxado Algoritmos que não usam da

serializabilidade como critério de correção. Escalonamento não serializável Transações Aninhadas

Controle de Concorrência Relaxado Escalonamento não serializável:

Utilizado em casos onde o escalonamento é restrito para certas aplicações.

Baseia-se no uso da observação intuitiva. Atomicidade Semântica Relativa:

Agrupar transações em classes, baseado em suas etapas.

As transações de mesma classe são compatíveis e podem ser intercaladas.

Controle de Concorrência Relaxado Transações Aninhadas:

Fechadas: O controle de concorrência de transações

aninhadas é muito similar a da baseada em bloqueios.

As transações aninhadas "relaxam" a durabilidade e o isolamento.

Abertas: Os bloqueios mantidos por uma subtransação

são liberados logo que ela se consolida ou aborta.

Conclusão O mecanismo distribuído do controle de

concorrência de um SGBD distribuído deve garantir a consistência do banco.

Os algoritmos de controle de concorrência visam tornar o SGBD distribuído em uma ferramenta confiável em um ambiente não confiável.

No geral, os algoritmos de controle de concorrência são de difícil implementação na prática.

O estudo de desempenho dos algoritmos estudados é algo que carece de maiores aprofundamentos.