Consistência de Dados em
Computação Móvel
José Maria Monteiro
Departamento de Informática – PUC-Rio
[email protected]
Disciplina: Introdução à Computação Móvel
Prof.: Markus Endler
1
Agenda





Motivação
Ambientes de Computação Móvel
Uma Taxonomia para Consistência de Dados em CM
Estudo de Caso: O Sistema Bayou
Conclusões
2
Motivação



Evolução e disseminação dos dispositivos portáteis
Avanços nas tecnologias de comunicação sem fio
Um Novo Paradigma: Computação Móvel

Possibilita que os usuários de DP’s mantenham a
conexão com a rede enquanto se movimentam
livremente


Tendo acesso a recursos, serviços e informações
compartilhadas
Novas Aplicações

Sistemas de Contole de Tráfego, Aplicações Baseadas em
Localização, Sistemas de Informações Sobre Tempo e Clima, ...
3
Motivação


As aplicações necessitam recuperar dados atuais e
consistentes
Os mecanismos tradicionais de controle de
concorrência não são adequados para CM

Devido às limitações inerentes aos ambientes móveis





Conectividade intermitente
Recursos limitados (energia, memória, processamento)
Mobilidade
Baixa largura de banda
Protocolos tradicionais
 Baseados em bloqueios, exigem excessiva comunicação,...
4
Motivação

São necessárias novas abordagens



Para garantir a consistência dos dados em ambientes
de CM
Diversos mecanismos têm sido propostos
Torna-se necessário investigar, analisar, comparar
e classificar as abordagens propostas
5
Ambientes de Computação Móvel
6
Propondo uma Taxonomia

Özsu e Valduriez (1991)


Propuseram uma classificação para sistemas de bancos
de dados distribuídos baseada nas características de
autonomia, distribuição e heterogeneidade
Dunham et al. (1997)

Observaram
 Um sistema de banco de dados móvel pode ser visto como uma
extensão de um sistema distribuído
 Ou seja, como um sistema distribuído dinâmico, onde os canais
de comunicação entre os computadores mudam dinamicamente

Estenderam a classificação de Özsu e Valduriez
 Adicionando um ponto no eixo da distribuição
7
Propondo uma Taxonomia

Dunham et al. (1997)
8
Propondo uma Taxonomia

Propomos uma taxonomia para sistemas de
bancos de dados móveis


Baseada na arquitetura e no funcionamento das
soluções encontradas
Classificação proposta






Replicação/Caching de Dados no Cliente
Servidores Replicados
Replicação em Redes Ad Hoc
SBD’s Múltiplos em CM
Comunidades de Bancos de Dados
Ambientes de Broadcast
9
Propondo uma Taxonomia

Replicação/Caching de Dados no Cliente
10
Propondo uma Taxonomia

Replicação/Caching de Dados no Cliente

Motivação




Objetivos


Canais de comunicação instáveis
Custo da infra-estrutura de comunicação sem fio
Dispositivos desconectados por longos períodos de tempo
Suporte à desconexão
 Possibilitar que os dispositivos continuem a execução de
suas operações sobre os dados mesmo na ausência de
conexão
Funcionamento


Uma cópia dos dados (ou de parte) é armazenada nos clientes
Em caso de desconexão, utiliza-se a cópia
11
Propondo uma Taxonomia

Replicação/Caching de Dados no Cliente

Vantagens



Desvantagens


Manter a consistência entre os dados armazenados nos clientes
e no servidor central
Arquitetura


Maior disponibilidade dos dados
Melhor desempenho (acesso local)
Redes móveis infra-estruturadas
Abordagens


Replicação e Reconciliação
Caching de Dados
12
Propondo uma Taxonomia

Servidores Replicados
13
Propondo uma Taxonomia

Servidores Replicados
14
Propondo uma Taxonomia

Servidores Replicados

Motivação



Objetivos


Canais de comunicação instáveis
Nem sempre o servidor está disponível ou alcançável
Possibilitar que as aplicações utilizem o servidor disponível que
estiver mais próximo
Funcionamento


Distribuir múltiplas cópias dos dados em diversos servidores
O cliente utiliza a cópia disponível mais próxima
15
Propondo uma Taxonomia

Servidores Replicados

Vantagens




Desvantagens


Necessidade de atualizar todas as cópias quando um item for
alterado
Arquitetura


Maior disponibilidade dos dados
Melhor desempenho (acessa a cópia mais próxima)
Maior Throughput
Ambientes computacionais parcialmente (fracamente)
conectados (onde a desconexão é a regra)
Exemplos

Bayou, Votação Ponderada, Deno
16
Propondo uma Taxonomia

Replicação em Redes Ad Hoc
17
Propondo uma Taxonomia

Replicação em Redes Ad Hoc

Motivação




Objetivos


Alto dinamismo das redes ad hoc
Freqüentes desconexões dos dispositivos móveis
Freqüente divisão (partição) da rede
 Dispositivo em uma partição não consegue acessar dados
armazenados por dispositivos que estejam em outra partição
Possibilitar que um cliente móvel acesse dados de um servidor
que não está na sua área de cobertura, através de hosts
intermediários
Funcionamento


Distribuir múltiplas cópias dos dados em diversos servidores
O cliente utiliza a cópia disponível mais próxima
18
Propondo uma Taxonomia

Replicação em Redes Ad Hoc

Vantagens



Desvantagens


Manter a consistência das diversas cópias
Arquitetura


Maior disponibilidade dos dados
Melhor desempenho (acessa a cópia mais próxima)
Redes Ad Hoc
Exemplos


Métodos para Alocação de Réplicas
Método PAN
19
Propondo uma Taxonomia

SBD’s Múltiplos em CM
20
Propondo uma Taxonomia

SBD’s Múltiplos em CM

Motivação





Freqüentes fusões e aquisições de diferentes companhias
Necessidade de gerenciar uma variedade de BD’s pré-existentes,
heterogêneos, autônomos e distribuídos geograficamente
(Bancos de Dados Múltiplos – Multidatabase)
Nec. de interoperabilidade  Multidatabase Systems - MDBSs
Nec. de estender os serviços dos MDBSs a usuários móveis 
Mobile Multidatabase Systems - MMDBSs
Objetivos

Possibilitar que usuários de dispositivos portáteis utilizem bancos
de dados múltiplos
21
Propondo uma Taxonomia

SBD’s Múltiplos em CM

Arquitetura


Redes móveis infra-estruturadas
Exemplos



Kangaroo
PSTM
V-Lock
22
Propondo uma Taxonomia

Comunidades de Bancos de Dados Móveis
23
Propondo uma Taxonomia

Comunidades de Bancos de Dados Móveis

Motivação


As redes ad hoc possibilita que os dispositivos se comuniquem
sem a participação de qualquer componente da rede fixa
Possibilita a formação de estruturas altamente dinâmicas que se
formam de maneira espontânea
 O compartilhamento de dados pode ser realizado através da
criação de federações dinâmicas de BD’s
 As quais são denominadas comunidades de bancos de dados
móveis (Mobile Database Communities – MDbC’s)
 Uma MDbC pode ser vista como um MMDBS no qual os
servidores podem estar em dispositivos móveis
24
Propondo uma Taxonomia

Comunidades de Bancos de Dados Móveis

Objetivos


Arquitetura


Possibilitar que um cliente móvel acesse os dados dos demais
membros da comunidade (de forma “integrada”)
Redes ad hoc
Exemplos

SESAMO
25
Propondo uma Taxonomia

Ambientes de Broadcast
26
Propondo uma Taxonomia

Ambientes de Broadcast

Motivação


Objetivos


O link de comunicação entre o cliente e o servidor nem sempre
está disponível (existe), ou pode apresentar custos elevados
Possibilitar que os clientes acessem os dados sem necessitar
enviar requisições ao servidor
Funcionamento


O servidor de broadcast periodicamente difunde os dados
Os clientes monitoram o canal de broadcast e filtram os dados
de seu interesse
27
Propondo uma Taxonomia

Ambientes de Broadcast

Vantagens




Desvantagens



O acesso aos dados é estritamente seqüencial
Aumenta a latência de acesso à informação
Arquitetura


O servidor não fica sobrecarregado com requisições
O servidor não precisa enviar mensagens individuais
Os dados podem ser acessados concorrentemente por qualquer
número de clientes sem nenhuma degradação de performance
Redes infra-estruturadas com broadcast
Exemplos

Relatórios de Invalidação, Múltiplas Versões, TGST, ...
28
Estudo de Caso: O Sistema Bayou

Características




Sistema de armazenamento replicado
Utiliza um nível fraco de consistência
Projetado para ambientes de CM parcialmente
(fracamente) conectados
Provê uma infra-estrutura


Para o desenvolvimento de aplicações colaborativas, sem
requisitos de tempo real
Ex: Edição cooperativa de documentos, agendas, e-mails
29
Estudo de Caso: O Sistema Bayou

Arquitetura


Cada BD é inteiramente replicado em um
conjunto de servidores
As aplicações (clientes) interagem com os
servidores através de uma API específica



Bayou Application Programming Interface
Suporta duas operações básicas: leitura e escrita
Os clientes podem executar tanto leituras quanto
escritas em qualquer um dos servidores, com os
quais possa se comunicar (read-any/write-any)

Por exemplo, o servidor mais próximo
30
Estudo de Caso: O Sistema Bayou

Arquitetura

O cliente e o servidor




Podem co-existir em um mesmo host, ou podem executar de
forma isolada
Podem executar nos hosts fixos ou móveis
Apresentam conexão intermitente
As aplicações


Têm conhecimento de que podem ler dados inconsistentes
Sabem que suas escritas são inicialmente apenas uma tentativa
31
Estudo de Caso: O Sistema Bayou

Arquitetura

No servidor



A informação de que escritas foram consolidadas em em que
ordem são propagadas para os demais servidores durante o
processo de anti-entropia
Cada servidor mantém duas visões do BD: consolidada e corrente
Detecção e resolução automática de conflitos




Detecção  Método baseado em validação de dependências
(consulta + resultado esperado)
Resolução  Utiliza procedimentos escritos em uma linguagem
interpretada de alto nível
As dependências e os procedimentos são incluídos juntos a cada
operação de escrita
A validação é feita antes da operação de escrita se executada
32
Estudo de Caso: O Sistema Bayou

Garantias de Sessão

O Bayou utiliza



Essa abordagem proporciona


Alta disponibilidade, boa escalabilidade e simplicidade de projeto
Problema:


Esquema de replicação read-any/write-any
Mecanismo de consistência fraca
É possível que os clientes obtenham valores inconsistentes
quando lêem dados de diferentes réplicas
Solução:

Para reduzir as inconsistências observadas pelos clientes, Bayou
provê garantias de sessão (sesion garantees)
33
Estudo de Caso: O Sistema Bayou

Garantias de Sessão

Definição




É uma abstração para uma seqüência de operações de leitura e
escrita que são submetidas durante a execução de uma aplicação
Não se tem a intenção de que as sessão sejam correspondentes
ao conceito de transação atômica (serializabilidade)
O objetivo é proporcionar às aplicações individualmente uma
visão do BD que seja consistente com as suas próprias ações
Características


O sistema tenta assegurar as garantias, caso não consiga,
informa à aplicação que a garantia não pôde ser alcançada, e
esta tenta executar a operação em outro servidor
Proporcionam um meio de adaptabilidade. O grau de consistência
pode ser adaptado aos níveis de conectividade.
34
Estudo de Caso: O Sistema Bayou

Garantias de Sessão

Read Your Writes (RYW)


Monotonic Reads (MR)


Leituras sucessivas refletem o resultado de um conjunto de
escritas não decrescente
Writes Follow Reads (WFR)


As operações de leitura devem refletir as escritas executadas
anteriormente (pela mesma sessão)
As operações de escrita são propagadas após as operações de
leitura das quais dependem
Monotonic Writes (MW)

As operações de escrita são propagadas após as escritas que as
precedem logicamente
35
Estudo de Caso: O Sistema Bayou

Garantias de Sessão

Implementação


Vetores de versão (semelhantes aos vectors timestamps)
Operações Desconectadas

Não inclui a noção de operação desconectada


Uma vez que vários níveis de conectividade são possíveis
É necessário apenas que ocasionalmente a comunicação entre
pares de servidores aconteça
 Grupos de servidores podem se desconectar do restante do
sistema e ainda continuarem conectados entre si
36
Conclusões




Existem um número razoável de abordagens para
garantir a consistência e a disponibilidade de
dados em CM
A taxonomia proposta pode ajudar a compreensão
dos diversos mecanismos existentes
O sistema Bayou apresenta alta disponibilidade de
dados em ambientes de conexão intermitente,
podendo ser utilizado em diversas aplicações
colaborativas
As idéias do sistema Bayou podem influenciar na
elaboração de novos mecanismos de consistência
37
Dúvidas????
38