Modos de Desconexão
para BD’s Móveis
Sandberg Marcel Santos
Baseado no artigo “Disconnection Modes for Mobile
Databases”, de Holliday, Agrawal e El Abbadi
Índice






Sistema Considerado
Cenários
Modelo do BD
Tipos de Desconexão
Implementação
Implementação (Sistema Assíncrono)
Sistema Considerado





Banco de dados distribuído
Pequena equipe (laptops)
Replicação do BD nos laptops: sim/não
Redes ad hoc com/sem fio
Capacidade de atualização do BD


Não-necessidade de conexão com um computador
fixo
Desconexões planejadas/não-planejadas
Cenários

Formas de interação com o BD



Basic sign-off
Check-out
Relaxed check-out
Basic Sign-off


Desconexão por longos períodos de tempo
(ex.: viagem)
Deve-se informar aos demais membros da
equipe


Continuação do processamento de atualizações no
BD
Ausência do processador


Não por falha
Desconexão voluntária
Basic Sign-off

Membro em viagem


Cópia (de parte) do BD (laptop)
Processamento de transações read-only
Check-out


“Desmarcação” de parte do BD
Demais membros


Membro desconectado



Completamente inacessível
Acesso total
Outras partes: read-only
Retorno

Sincronização e integração automáticas
Relaxed Check-out

Relaxamento

Parte do BD que sofreu a “desmarcação”: readonly (demais membros)
Modelo do BD

Sistema distribuído



BD completamente replicado
Interação dos usuários: invocação de
transações em qualquer site


n sites: S1, S2, ..., Sn
Transparência: múltiplas cópias físicas  uma
única cópia lógica
Transações: atomicidade
Modelo do BD


Controle de concorrência (two-phase locking)
Equipe





Número fixo de membros
Desconexão freqüente
Rede ad hoc
Ausência de alguns membros: possibilidade
de atualizações
Participantes com mesmo “peso”
Tipos de Desconexão

Não-planejada


Considera-se o site desconectado como uma falha
Basic sign-off
Tipos de Desconexão

Check-out





Partição do BD
Check-out com leitura móvel
Check-out com leitura do sistema
Check-out relaxado
Check-out otimista
Partição do BD
Check-out com Leitura Móvel
Check-out com Leitura do Sistema
Check-out Relaxado
Check-out Otimista
Check-out Otimista

Assume-se, de maneira otimista


Não-ocorrência de atualizações conflitantes
Integração das atualizações conflitantes (na
reconexão dos sites desconectados)

Regras pré-definidas
Implementação – Basic Sign-off
- Desconexão de um site Si 
Si: seleção de um proxy



Passagem do poder de voto
Poder de votar em nome de outro membro
Proxy de Si


Direito de votar (atualizações do BD)
Conhecimento da situação de Si (atualizações
processadas/não-processadas)
Implementação – Basic Sign-off
- Reconexão de Si 
Contatar o proxy



Proxy desconectado: determinação do novo proxy
(mensagens em broadcast)
Determinar as atualizações necessárias
Retirar o poder de voto do proxy
Implementação – Basic Sign-off

Correção

Garantida trivialmente
Implementação – Check-out
- Desconexão 

Si: seleção de um proxy
Ao mesmo tempo: realização de uma pseudotransação (obtenção dos write locks em um
certo conjunto de itens)


Write locks: bloqueio de itens do BD
Pseudo-transação: transação para a obtenção de
write locks
Implementação – Check-out
- Reconexão 
Idêntica à do basic sign-off, exceto


Transmissão dos novos valores dos itens
Liberação dos write locks
Implementação – Check-out


Regras (desconexão/reconexão) válidas para
todas as variações
Correção da partição do BD

Garantida trivialmente
Implementação
Check-out com Leitura Móvel (ex.)

Correção: garantida pela serialização das
transações (t1, t2, t3, t4) (desconexão)
Implementação
Check-out com Leitura do Sistema (ex.)

Correção: garantida pela serialização das
transações (t2, t1, t3, t4) (reconexão)
Implementação
Check-out Relaxado


Check-out com leitura móvel + acesso em
browse mode
Browse mode



Sites conectados
Itens “desmarcados”
Não garante leitura consistente
Implementação
Check-out Relaxado (ex.)

Correção: não-garantida (dependência cíclica:
t1 e t5)
Implementação
Check-out Otimista

Problema



Atualizações conflitantes (necessidade de
integração)
Roll back (reconexão)
Sugestão: regras baseadas em check-out




Site que está desconectando (Si)
Ajuda no processo de integração
Desmarcação de algumas partes do BD
Concordância dos outros sites
Implementação
Check-out Otimista
Quando Si desmarca um certo conjunto de
itens:
1) - Transação em Si que acessar somente itens
desmarcados (desconexão)  commit
- Reconexão de Si: prioridade de Si (das
atualizações feitas por Si) > prioridade dos
outros

Implementação
Check-out Otimista
2) - Transação em Si que acessar somente itens
não-desmarcados  commit
- Reconexão de Si: prioridade dos outros >
prioridade de Si
3) Transação em Si que acessar ambos conjuntos
de itens


Commit condicional
Possibilidade: roll back e redo
Implementação
Check-out Otimista

Correção: dependência


Da integração (atualizações)
Da realização dos roll backs e dos redos
Implementação (Sistema Assíncrono)



Redes distribuídas com congestionamento e
atrasos
Execução local das transações 
incorporação assíncrona dos efeitos em cópias
remotas do BD
Não-necessidade de todos os sites estarem
conectados (simultaneamente, em algum
momento)
Implementação (Sistema Assíncrono)

Comunicação epidêmica


Periodicamente: contato entre membros e troca de
informações
Comunicação par-a-par: disseminação das
atualizações por todo o sistema
Implementação (Sistema Assíncrono)
SGBD distribuído epidemic-based




Controle de concorrência (two phase locking)
Transação t (momento do commit): escreve-se
um registro de pré-commit em um log de
eventos
Propagação do registro (comunicação
epidêmica)
Outros membros: sincronização
Implementação (Sistema Assíncrono)
SGBD distribuído epidemic-based

Cada membro


Vector clock: ordem causal dos eventos (précommits)
2D timetable (matrix clock): conhecimento mais
recente sobre os eventos (de todos os membros)

Inclusa em todas mensagens epidêmicas
Implementação (Sistema Assíncrono)
Basic Sign-off (Desconexão)



Si solicita um proxy (Sj)
Si não aceita mais mensagens epidêmicas
(exceção: as de Sj) e vice-versa
Sj não realiza mais pré-commits (transações
locais)
Implementação (Sistema Assíncrono)
Basic Sign-off (Desconexão)

Sj envia a Si: todos os registros de précommits (que acredita que Si não viu) +
respectiva informação temporal


Si sabe de tudo que Sj sabe (antes da desconexão)
Si envia a Sj: seus registros de pré-commits +
informação temporal

Sj conhece o estado de Si (atualização de Si na
reconexão)  desconexão de Si
Implementação (Sistema Assíncrono)
Basic Sign-off (Desconexão)


Sj: marcação do log de eventos (identificador
para Si)  não descartar registros 
atualização de Si (reconexão)
Sj: (retorno) envio e recebimento de
mensagens epidêmicas / proxy de Si
Implementação (Sistema Assíncrono)
Basic Sign-off (Reconexão)



Si: quem está agindo como Si?
Sj: parar envio/recebimento mensagens
epidêmicas / fornecer log de eventos +
timetable para Si  (retorno) operações
normais
Si: log de eventos e timetable = aos de Sj 
(retorno) operações normais
Implementação (Sistema Assíncrono)
Check-out

Variações de check-out: implementações
similares


Ex.: check-out com leitura móvel
Desconexão


Por definição: tentativa de atualização de um item
(se há uma transação concorrente conflitante) 
abort de todos os registros de pré-commits
Si (antes da desconexão): envio de todos os itens
com um timestamp ∞
Implementação (Sistema Assíncrono)
Check-out

Desconexão (cont.)


∞ incomparável com qualquer timestamp: abort
de todas as transações de leitura ou atualização de
itens de Si
Reconexão


Si: envio de mensagem epidêmica com todos os
itens e com um timestamp normal
Site é o mesmo (registro conflitante com o valor
∞)  sobrescrição do log  atualização dos itens