TRANSAÇÕES E CONTROLE DE CONCORRÊNCIA Sistemas Distribuídos
Vinícius Pádua
Transações •  Garan0r que todos os objetos gerenciados no servidos permaneçam consistente mesmo na presença de falhas do servidor •  Objetos gerenciáveis –  Até mesmo os que estão na memória volá0l •  Servidor deve garan0r que a transação seja executada e os resultados gravados em armazenamento permanente Vinícius Pádua 2 Transações •  Sincronização Simples – sem transações Vinícius Pádua 3 Sincronização Simples •  Sem u0lização de transações •  Imagine dois clientes transferindo valores • 
• 
Quais os valores corretos esperados para os saldos dos clientes A e B Como após roesolver? término da execução dos processos? Quais os valores finais dos saldos dos clientes se a sequência temporal de execução das operações for: 1a, 2a, 1b, 2b, 1c, 2c, 1d, 2d, 1e, 2e, 1f, 2f? Vinícius Pádua 4 Sincronização Simples •  Como resolver? •  Operações atômicas –  Executa tudo ou nada –  Comunicação Inter processos •  Semáforos, mutex, monitores –  Java •  public synchonized void deposito ... Vinícius Pádua 5 Sincronização Simples •  “public synchonized void ...” solução dos problemas? •  Problema do Produtos X Consumidor •  Pode surgir alguma dificuldade? Qual? –  Produtor deseja inserir novo item, mas está cheio –  Consumidor deseja re0rar item, mas esta seco •  Como proceder? Vinícius Pádua 6 Sincronização Simples •  Como resolver? –  Variáveis condicionais –  Java •  Wait e no0fy Vinícius Pádua 7 Modelo de falha para transações •  Proposto por Lampson [1981] •  Algoritmos funcionam corretamente na presença de falhas previsíveis –  Escritas em armazenamento permanente podem falhar –  Servidores podem falhar –  Atraso na chegada da mensagem Vinícius Pádua 8 Modelo de falha para transações •  Escritas em armazenamento permanente podem falhar –  Grava correto ou permanece estado anterior –  Soma de verificação –  Modelo de Armazenamento Estável •  Manter o disco consistente –  Proteger a inserção de dados corrompidos –  Evitar que os dados sejam perdidos •  Dois discos idên0cos –  Gravação: Menos vantajosa –  Leitura: Mais vantajosa Vinícius Pádua 9 Modelo de falha para transações •  Escritas em armazenamento permanente podem falhar Vinícius Pádua 10 Modelo de falha para transações •  Servidores podem falhar –  Servidor danificado é subs0tuído •  Atraso na chegada da mensagem –  Perdida, duplicada ou corrompida Vinícius Pádua 11 Transações •  Sequencia de requisições separadas que devem ser atômicas •  Livres da interferência •  Concluídas com êxito ou sem efeitos Vinícius Pádua Operação I A Sacar R$ 100 B Depositar R$ 100 C Sacar R$ 200 D Depositar R$ 200 Operação I D Sacar R$ 150 B Depositar R$ 150 C Sacar R$ 240 A Depositar R$ 240 Operação III D Sacar R$ 300 C Depositar R$ 300 B Sacar R$ 400 A Depositar R$ 400 12 Transações •  Originárias do SGBD •  Corba – Serviço de transação de objetos •  Propriedades ACID –  Atomicidade •  Tudo ou nada •  Atomicidade da falha –  Consistência •  Estado consistente para estado consistente –  Isolamento •  Transação não podem afetar outras –  Durabilidade •  Armazenamento permanente mas após falhas Vinícius Pádua 13 Transações •  Gerenciada pelo coordenador •  Operações –  TID = OpenTransac0on() –  RET = CloseTransac0on() –  AbortTransac0on() •  Cancelamento de transações –  Execução –  Conflitos com outras transações –  Fala de processo/computador Vinícius Pádua 14 Transações •  Situações Possíveis Bem Sucedida Cancelada pelo Cliente Cancelada pelo Servidor OpenTransac0on() OpenTransac0on() OpenTransac0on() Comando 10 Comando 20 Comando 30 Comando 11 Comando 21 Comando 31 Comando 12 Comando 22 Servidor Cancela Comando 13 Comando 23 Comando 14 Comando 24 ERRO da operação relatado ao cliente Comando 15 Comando 25 CloseTransac0on() AbortTransac0on() Vinícius Pádua 15 Transações •  Ações do serviço relacionadas a falha de processo –  Processo falhar inesperadamente •  Novo processo cancela transação não confirmadas –  Cliente falha •  Timeout •  Ações de cliente relacionadas a falhas do servidor –  Excep0on –  No0ficar o usuário da aplicação Vinícius Pádua 16 Transações •  Como executar 2+ transações garan0ndo o isolamento? –  Execução em série •  Uma a uma –  Como maximizar a concorrência? •  Transações equivalentes ou serializáveis •  Controle de concorrência Vinícius Pádua 17 Controle de Concorrência •  Maximizar a performance do servidor Transação T saldo = B.getSaldo() B.setSaldo(saldo*1.1) A.saque(saldo/10); Transação U
saldo = B.getSaldo() B.setSaldo(saldo*1.1) C.saque(saldo/10); saldo = B.getSaldo() B.setSaldo(saldo*1.1) A.saque(saldo/10); saldo = B.getSaldo() B.setSaldo(saldo*1.1) C.saque(saldo/10); Vinícius Pádua Saldo Inicial A = 100 B = 200 C = 300 18 Controle de Concorrência Transação V A.saque(100); B.deposita(100) A.saque(100); B.deposita(100) Transação W
getSaldoTodasContas()
total = A.saldo() total = total + B.saldo() total = total + C.saldo() Vinícius Pádua Saldo Inicial A = 100 B = 200 C = 300 19 Controle de Concorrência •  Equivalência Serial –  Transações executadas simultaneamente mesmo efeito executadas sequencialmente –  Evitar problemas citados Transação T saldo = B.getSaldo() B.setSaldo(saldo*1.1) A.saque(saldo/10); Transação U
saldo = B.getSaldo() B.setSaldo(saldo*1.1) C.saque(saldo/10); saldo = B.getSaldo() B.setSaldo(saldo*1.1) A.saque(saldo/10); saldo = B.getSaldo() B.setSaldo(saldo*1.1) C.saque(saldo/10); Vinícius Pádua Saldo Inicial A = 100 B = 200 C = 300 20 Controle de Concorrência •  Equivalência Serial Transação V A.saque(100); B.deposita(100) A.saque(100); B.deposita(100) Transação W
getSaldoTodasContas()
total = A.saldo() total = total + B.saldo() total = total + C.saldo() Vinícius Pádua Saldo Inicial A = 100 B = 200 C = 300 21 Controle de Concorrência •  Operações Conflitantes –  Efeitos combinados depende da ordem de execução Regras de conflito para operações de Leitura e Escrita Operações Leitura Leitura Leitura Escrita Escrita Escrita MoIvo Conflito Não Efeito de duas operações de leitura não depende da ordem Sim Efeito de uma operação de leitura e escrita depende da ordem de execução Sim Efeito de duas operações de escrita depende da ordem de execução Vinícius Pádua 22 Controle de Concorrência •  Operações Conflitantes –  Transações Serialmente Equivalentes •  Necessário que todos os pares de operações conflitantes das duas transações sejam executados na mesma ordem •  T acessa i antes de U e T acessa j antes de U ou •  U acessa i antes de T e U acessa j antes de T Transação T X = read(i) Write(i,10) Write(j,20) Transação W Y = read(j) write(j,30) Z = read(i) T e W são não serialmente equivalente, pois W acessa j antes de T Vinícius Pádua 23 Controle de Concorrência •  Operações Conflitantes –  Transações Serialmente Equivalentes –  Como tornar serialmente equivalentes? Transação T saldo = B.getSaldo() B.setSaldo(saldo*1.1) A.saque(saldo/10); Transação U
saldo = B.getSaldo() B.setSaldo(saldo*1.1) C.saque(saldo/10); Vinícius Pádua 24 Controle de Concorrência •  Exercício de Fixação –  Um servidor gerencia os objetos a1, .. Na. O servidor fornece duas operações para seus clientes: Leitura(i) – retorna valor de Ai Escrita(i, valor) – Atribui valor a Ai As transações T e U são definidas: T | x = leitura(J) ; y = leitura (I) ; escrita (J,44) ; escrita(I,33); U | x = leitura(K) ; escrita(I,55) ; y = leitura(J) ; escrita(K,66); De uma interposições serialmente equivalentes das transações T e U Vinícius Pádua 25 Controle de Concorrência •  Operações Conflitantes –  Pode ser ob0do pela transações esperando umas às outras, pelo reinicio da transação após conflito ou pro combinação dos métodos –  Equivalência Serial •  Travamento •  Controle de concorrência o0mista •  Ordenação de carimbo de tempo Vinícius Pádua 26 Controle de Concorrência •  Recuperação de Cancelamentos –  Abort Transac0on –  Não deve persis0r nenhuma informação –  Podem afetar outras transações Vinícius Pádua 27 Controle de Concorrência Recuperação de Cancelamentos Transação T saldo = A.getSaldo() A.setSaldo(saldo+10) OpenTransac0on() saldo = A.getSaldo() A.setSaldo(saldo+10) AbortTransac0no() Transação U saldo = A.getSaldo() A.setSaldo(saldo+20) OpenTransac0on() saldo = A.getSaldo() A.setSaldo(saldo+20) CloseTransac0on() Vinícius Pádua Saldo de A = 100 U0lizou valor errado 28 Controle de Concorrência Recuperação de Cancelamentos •  Leitura Sujas –  Transações serialmente equivalentes –  Causa •  Confirmação de uma transação que u0lizou valor alterado por outra transação que foi cancelada –  Evitar •  Capacidade de recuperação das transações –  Retardar a confirmação até que todas as transações confirmem –  Transação será cancelada a transação concorrente seja •  Cancelamento em Cascata –  Cancelamento causa mais cancelamentos Vinícius Pádua 29 Controle de Concorrência Recuperação de Cancelamentos Transação T A.setSaldo(105) OpenTransac0on() A.setSaldo(105) AbortTransac0no() Transação U A.setSaldo(110)
OpenTransac0on() A.setSaldo(110) CloseTransac0on() Vinícius Pádua Saldo de A = 100 30 Controle de Concorrência Recuperação de Cancelamentos •  Escritas Prematuras –  Duas operações de leitura no mesmo objeto e uma é cancelada •  Execução restrita de transações –  Transações retardem as operações de leitura e escrita •  Versões de tenta0va –  Cada transação possui versões privadas Vinícius Pádua 31 Transações Aninhadas •  Uma transação pode ser composta por outras –  Transação de nível superior –  Subtransações Transação de Nível Superior Subtransação T1 Subtransação T11 Subtransação T2 Subtransação T12 Vinícius Pádua Subtransação T21 Subtransação T22 32 Transações Aninhadas •  Vantagens –  Subtransações de mesmo nível podem ser executadas concorrentes –  Subtransações podem ser confirmadas ou canceladas independente •  Transação ascendente decide o que fazer quando uma subtransação cancelar Vinícius Pádua 33 Transações Aninhadas •  Regras para confirmação de transações –  Todas as subtransações dever ter sido confirmadas ou canceladas –  Subtransação é confirmada provisoriamente –  Transação ascendente é cancelada, todas as subtransações são canceladas –  Subtransação é cancelada, transação ascendente decide oque fazer –  Transação de nível superior é confirmada, todas as subtransações confirmada provisoriamente são confirmadas Vinícius Pádua 34 Travas Exclusivas •  Servidor trava o objeto u0lizado por uma transação •  Liberação apenas ao final Transação T saldo = B.getSaldo() B.setSaldo(saldo*1.1) A.saque(saldo/10); Transação U
saldo = B.getSaldo() B.setSaldo(saldo*1.1) C.saque(saldo/10); OpenTransac0on() saldo = B.getSaldo() TRAVA B B.setSaldo(saldo*1.1) A.saque(saldo/10); TRAVA A CloseTransac0on() DESTRAVA A,B OpenTransanc0on() saldo = B.getSaldo() ESPERA TRAVA B B.setSaldo(saldo*1.1) TRAVA B C.saque(saldo/10); TRAVA C CloteTransac0on() DESTRAVA B,C Vinícius Pádua Saldo Inicial A = 100 B = 200 C = 300 35 Travas Exclusivas •  Parte do objeto onde o acesso é em série, deve ser a menor possível –  Evitar bloquear todos os objetos •  Cenário: Muitas leituras e poucas escritas –  Como será o desempenho? –  Primeira leitura ira bloquear o sistema –  Travas Compar0lhadas •  Trava de leitura e de escrita Vinícius Pádua 36 Travas Compar0lhadas •  Trava de leitura e de escrita –  Travas de leitura não entram em conflito •  Compa0bilidade de travas Trava Solicitada Leitura Escrita Trava já Alocada Nenhum OK OK Leitura OK Espera Escrita Vinícius Pádua Espera Espera 37 Travas Compar0lhadas Transação T OpenTransac0on() A.deposito(100); TRAVA ESCRITA A B.saque(200); ESPERA TRAVA B Transação U
OpenTransanc0on() B.deposito(200) TRAVA ESCRITA B A.saque(200); ESPERA TRAVA A •  E Agora? •  Impasses Vinícius Pádua 38 Impasses •  Cada membro de um grupo de transações esta esperando por outro membro Espera Espera Vinícius Pádua 39 Impasses •  Cenário –  T, U, V trava de leitura em C –  W trava de escrita em B –  V esperando por B –  T, W trava de escrita em C, que acontece? –  Quem espera por quem? –  Onde esta o impasse? C B Vinícius Pádua 40 Impasses •  Detecção de impasses –  Descoberta dos ciclos •  Prevenção –  Solicitar as travas de todos os objetos no início da transação •  Algoritmo do banqueiro •  Retêm recursos que outros processos podem estar usando –  Tempos Limites (0meout) •  Muito comum •  Cada trava tem um tempo limite •  Após certo tempo, as travas são vulneráveis Vinícius Pádua 41 Impasses Tempos Limites Transação T OpenTransac0on() A.deposito(100); TRAVA ESCRITA A B.saque(200); ESPERA TRAVA B ... ... Trava A se torna vulnerável, DESTRAVA A e CANCELA T Transação U
OpenTransanc0on() B.deposito(200) TRAVA ESCRITA B A.saque(200); ESPERA TRAVA A A.saque(200); TRAVA A CloseTransac0on() DESTRAVA A B Vinícius Pádua 42 Impasses Tempos Limites •  Nem sempre o tempo limite é solução, PQ? –  Transações canceladas por trava vulnerável mesmo sem impasse, Quando ocorre? •  Sistema sobrecarregado •  Dificuldade em definir o tempo limite Vinícius Pádua 43 Travamento de Duas Versões •  Permite mais concorrência que as travas de leitura e escrita –  Gravar versões de tenta0va dos objetos –  Leitura feita em versões confirmadas Trava Solicitada Leitura Escrita Confirmação Trava já Alocada Nenhum OK OK Ok Leitura OK OK Espera Escrita OK Espera -­‐ Confirmação Espera Espera -­‐ Vinícius Pádua 44 Travas Hierárquicas •  Caso necessite saber o saldo de todas as contas bancárias? –  Trava em todas as contas? –  Travas de granularidade mista Trava Solicitada Leitura Escrita Confirmação I-­‐Leitura I-­‐Escrita Trava já Alocada Nenhum OK OK Ok Ok Ok Leitura OK Espera Ok Ok Espera Espera Espera Espera Espera Ok Ok Ok I-­‐Escrita Espera Espera Ok Ok Ok Escrita I-­‐Leitura Espera Espera Ok Vinícius Pádua 45 Controle de Concorrência O0mista •  Baseado na observação que a probabilidade de duas transações acessarem o mesmo objeto é baixa –  As verificações serão feitas apenas no CloseTransac0on –  Fase de trabalho, de validação e de atualização Vinícius Pádua 46 Controle de Concorrência O0mista •  Fase de Trabalho –  U0lizam versão de tenta0va •  Todas leituras feita nessas versões •  Podem exis0r várias versões de leituras diferente em várias transações •  Fase de Validação –  Inicia com a CloseTransac0on –  Verifica se ocorreu conflito com as outras transações •  Fase de Atualização –  Caso a transação seja válida –  Todas as versões de tenta0va são tornadas permanentes Vinícius Pádua 47 Controle de Concorrência O0mista •  Validação de Transações –  Transações – Ti e Tj, sendo i<j –  Pelo menos uma deve ser sa0sfeita •  Ti termina todas as fases antes de Tj iniciar •  Ti termina antes de Tj iniciar fase de atualização e Ti não modifica objeto lido por Tj •  Ti termina fase de trabalho antes que Tj termine fase de trabalho e Ti não modifique objeto que é lido ou modificado por Tj Vinícius Pádua 48 Controle de Concorrência O0mista •  Validação para trás (backward) –  Conjunto de leituras que esta sendo validade é comparado com os conjuntos de escritas já confirmadas •  Validação para frente (forward) –  Comparado com o conjunto de leitura de todas as transações a0vas que estão na fase de trabalho •  Inanição –  É cancelada, mesmo após reinício –  Raras Vinícius Pádua 49 Ordenação por carimbo de Tempo •  Cada transação recebe um carimbo quando inicia •  Os objetos são carimbados com carimbo de leitura e/ou escrita cada transação que u0lize •  Os carimbos são únicos e ordenados •  A transações são processadas em ordem Vinícius Pádua 50