Gerência de Transações em Gerência de Transações em MDSMDS

Consistência de dados em Consistência de dados em conectividade intermitenteconectividade intermitente

Francisco de AssisUFCG/COPINPós-graduação - Banco de Dados - 2007.1

Gerência de Gerência de Transações em MDSTransações em MDSo Como manter a consistência de dados se a conectividade é intermitente?o Como fazer o controle de concorrência em MDS?

CONSISTÊNCIA DE CONSISTÊNCIA DE DADOS EM DADOS EM CONECTIVIDADE CONECTIVIDADE INTERMITENTEINTERMITENTE

Tópico1

13/04/2007 3

Agenda – Consistência de Agenda – Consistência de dadosdados

MotivaçãoO modelo de consistênciaOperando em conectividade

fracaRestaurando a consistência

13/04/2007 4

Motivação – Consistência de Motivação – Consistência de dadosdados

Variação na conectividade◦De alta velocidade até alta latência

Clientes móveis devem operar desconectados

Clientes móveis podem operar em conectividade fraca

A conexão será, eventualmente, restaurada

13/04/2007 5

Conceitos - ClusterConceitos - Cluster

Dados nos “sítios” fortemente conectados possuem alta consistência – formam um cluster.

13/04/2007 6

Cluster

Site

Um certo grau de inconsistência é admitido para cópias dos dados em clusters diferentes.

BD Distribuído Fraca conectivida

de

Conceitos - LeituraConceitos - Leitura

Leitura fraca◦Weak Read (WR)◦Lê cópias (possivelmente)

inconsistentesLeitura estrita (explícita,

rígida, ...)◦Strict Read (SR)◦Lê cópias consistentes

13/04/2007 7

Conceitos - EscritaConceitos - Escrita

Escrita fraca◦Weak Write (WW)◦Faz “atualização condicional”

Escrita estrita (explícita)◦Strict Write (SW)◦Grava dados de forma permanente

13/04/2007 8

Conceitos - VantagensConceitos - Vantagens

O grau de inconsistência pode ser adaptado as condições de uso.◦Usando Weak e Strict de forma

balanceadaProvê adaptabilidade variável:

◦A aplicação sempre decide o grau de inconsistência; ou

◦O BD sempre decide o grau de inconsistência.13/04/2007 9

O modelo de consistênciaO modelo de consistência

13/04/2007 10

p-cluster

p-cluster = physical cluster

Definido se: Há baixa latência; A banda é muito

larga;

- Objetivo: reduzir comunicação inter-cluster (entre p-clusters).

- Usar WR e WW para acesso direto aos dados do mesmo p-cluster (maximizar processamento local).

- Temos dois tipos de cópia:

core: valor permanente.

quasi: valor sob validação condicional.(são “reconciliados” no restabelecimento da comunicação)

Modelo “extendido”Modelo “extendido”

Weak Read (WR)

Lê cópias locais e retorna o valor mais atual

Melhor esforçoLê cópia local mais atual (core ou quasi)

ConservadoraLê cópia local mais atual (apenas quasi)

Strict Read (SR)Lê apenas cópias core e retorna o valor mais atual

Weak Write (WW) Escreve em cópias quasi

Strict Write (SW)

EventualEscreve apenas em cópias core

ImediataEscreve em cópias core e quasi, num mesmo p-cluster

13/04/2007 11

Extensões

Exemplo práticoExemplo práticoAmbiente cooperativoAmbiente cooperativo

13/04/2007 12

p-clusterGrupo B

Notebook

PDA

Servidor

p-clusterGrupo A

Cópia core para Grupo ACópia quasi para Grupo B

O modelo de consistênciaO modelo de consistênciaPara realizar uma transação, o

DMS (Database Management System) consulta várias cópias do dado◦Traduz o resultado num único valor

13/04/2007 13

O modelo de consistênciaO modelo de consistência

13/04/2007 14

A transação pode ser: ◦Strict (não inclui operações Weak)

São ACID!

◦Weak (não inclui operações Strict) São executadas em cópias locais de um p-

cluster São visíveis apenas em operações weak

◦Weak + Strict Difíceis de definir! São separadas em sub-transações

“sub-weak + sub-strict”

Exatidão dos dadosExatidão dos dados

13/04/2007 15

Restrições de integridade são “relaxadas”◦Não há como garantir “corretude

total” em conexão intermitente

Exatidão dos dadosExatidão dos dados

13/04/2007 16

O problema!

Restrição

IF X > 0 THEN Y > 0

Core Quasi

X = -1

Y = 2

X = -1

Y = -4Transaçã

o

X = 10;IF Y < 0 Y = 10;

Realização da

transação(Strict-

Imediata)

SW (x)SR (y)

Inconsistência

Core Quasi

X = 10Y = 2

X = 10Y = -4

A cópia quasi de X foi alterada sem se preocupar com a restrição!

Exatidão dos dadosExatidão dos dados

A solução!

1.Ao fazer SW imediata, as cópias quasi devem verificar a consistência

2.Ao fazer SW imediata, as operações de leitura devem ser feitas nas cópias quasi

3.Adiar a atualização das cópias quasi

13/04/2007 17

Exatidão dos dadosExatidão dos dados

13/04/2007 18

Conceito de l-cluster (logical cluster)◦É o conjunto de cópias quasi de um p-

cluster◦As restrições são aplicadas nesses l-

clusters◦Restrições intra-cluster definem se o

estado do banco é ou não consistente ◦Deve haver uma medida de

divergências (d) entre restrições inter-cluster

Operando em conectividade Operando em conectividade fracafraca

13/04/2007 19

Como fazer o agendamento correto da transação (scheduling)?

Como garantir a corretude da transação?

Como serializar a transação?

Agendamento completo Agendamento completo intra-clusterintra-cluster

13/04/2007 20

Intra-cluster é:◦Num mesmo p-cluster◦Entre as cópias quasi

Agendamento completo Agendamento completo intra-clusterintra-cluster

13/04/2007 21

IAS = IntrA-cluster Schedule◦Operações sobre um dado são

traduzidas em operações nas cópias;◦A ordem das transações é respeitada;◦Operações conflitantes são gravadas;◦A transação deve operar sempre na

mesma cópia de um dado;◦Transações weak não podem ver

resultados parciais de transações strict;

Critério de corretudeCritério de corretude

13/04/2007 22

Corretude fraca de um IAS◦A execução concorrente pode manter

inconsistência Limiarizada!

◦As transações weak devem ler dados consistentes

◦As transações strict devem ser equivalentes a transações em cópia única

Não garante corretude em clusters diferentes

Critério de corretudeCritério de corretude

13/04/2007 23

Corretude forte de um IAS◦Há divergências entre l-clusters

diferentes◦Tenta fazer a correspondência entre:

IAS de transações strict E agendamento serial.

◦Ainda pode existir inconsistência

SerializandoSerializando

13/04/2007 24

Atestar a corretude de um IAS◦ Usando um grafo de serialização

modificadoIncluir no grafo:◦ Todas as transações strict◦ Adicionar arestas que representem

operações em cópias◦ Incluir transações weak◦ Incluir arestas: dependência, precedênciaSe uma IAS têm um grafo acíclico, então

a corretude é forte

SerializandoSerializando

13/04/2007 25

Controle de coerência◦Todas as cópias têm o mesmo valor◦Vale globalmente para cópias core◦Vale localmente para cópias quasi

Controle de concorrência◦Mantém as outras restrições de

integridade

Limitando a divergênciaLimitando a divergência

13/04/2007 26

Em cada p-cluster, “d” é o grau de divergência entre cópias quasi e core, podendo ser:◦Número máximo de cópias

divergentes;◦Faixa de valores aceitável para o

dado;◦Número máximo de transações que

podem agir numa cópia quasi;◦...

Outras vantagens do Outras vantagens do modelomodelo

13/04/2007 27

Leituras weak = dados “imprecisos”◦Mais flexibilidade para o usuário◦Oferece bons resultados se a

aplicação tratar com dados estatísticos

MECANISMO DE MECANISMO DE CONTROLE DE CONTROLE DE CONCORRÊNCIACONCORRÊNCIA

Tópico1I

13/04/2007 28

Agenda – Controle de Agenda – Controle de concorrênciaconcorrência

MotivaçãoModelos disponíveisAdaptando modelos

13/04/2007 29

Motivação – Controle de Motivação – Controle de concorrênciaconcorrência

Adaptar mecanismos existentes◦Ou não!

Analisar o overhead◦Deve ser mínimo para MDS!

13/04/2007 30

Modelos disponíveisModelos disponíveis

Baseado em travamento◦2 fases, centralizado

Um nó é responsável pelo travamento

◦2 fases, com cópia primária Vários nós são responsáveis pelo

travamento

◦2 fases, distribuída Qualquer nó é responsável pelo

travamento

Nenhum resolve o problema da comunicação intermitente!13/04/2007 31

Adaptando modelosAdaptando modelos

Poucas alternativas foram pensadas!◦Distributed HP-PPL CCM

Resolve conflitos usando: Prioridade Status (bloqueado, gravando) Acrescenta timeout para MDS

13/04/2007 32

Adaptando modelosAdaptando modelos

Epsilon Serializability◦Coloca limites para inconsistência◦Uma transação importa

inconsistência Lendo dados não validados

◦Uma transação exporta inconsistência Permitindo a leitura de dados não

validados

◦Melhor alternativa, segundo Kumar13/04/2007 33

Então...Então...o Como manter a consistência de dados se a conectividade é intermitente?•R: Relaxando...o Como fazer o controle de concorrência em MDS?•R: Usando “Epsilon Serializability”

BibliografiaBibliografia

http://citeseer.ist.psu.edu/ramamritham94formal.html

http://www.cs.uoi.gr/~pitoura/distribution/Mobile/icdcs95-slides.ps

http://ieeexplore.ieee.org/iel5/69/17849/00824602.pdf?arnumber=824602

http://doi.ieeecomputersociety.org/10.1109/69.824602

13/04/2007 35