Controle de Concorrência Eficiente para Ambientes de Broadcast



Baixar 96.08 Kb.
Encontro16.04.2019
Tamanho96.08 Kb.



Consistência de Dados em Computação Móvel

José Maria Monteiro


Departamento de Informática, PUC-Rio

monteiro@inf.puc-rio.br



Resumo


As recentes evoluções ocorridas nos computadores portáteis em conjunto com os avanços nas tecnologias de comunicação sem fio estão possibilitando que os usuários de dispositivos móveis mantenham a conexão com a rede enquanto se movimentam livremente, tendo acesso a recursos, serviços e informações compartilhadas. Este paradigma computacional é denominado de computação móvel. A computação móvel possibilita o desenvolvimento de novas e sofisticadas aplicações em banco de dados. Tais aplicações necessitam recuperar dados atuais e consistentes. Entretanto, devido às limitações inerentes aos ambientes móveis, como reduzida largura de banda e freqüentes desconexão dos dispositivos portáteis, torna-se necessário que mudanças no gerenciamento e nos mecanismos de garantia de consistência dos dados sejam implementadas. Este trabalho investiga, descreve e classifica as principais abordagens para manter a consistência dos dados em ambientes de computação móvel.


  1. Introdução

A integração dos computadores portáteis com as recentes tecnologias de comunicação celular, redes de comunicação sem fio e serviços via satélite está possibilitando que os usuários de dispositivos móveis mantenham a conexão com a rede enquanto se movimentam livremente, tendo acesso a recursos, serviços e informações compartilhadas. Este paradigma computacional é denominado de computação móvel. Neste ambiente, os usuários têm acesso a informações e recursos compartilhados independente de onde estejam localizados e de sua mudança de localização (mobilidade). A computação móvel possibilita o desenvolvimento de novas e sofisticadas aplicações em banco de dados. Entretanto, para que estas aplicações possam executar de forma efetiva, torna-se necessário que mudanças no gerenciamento e nos mecanismos de garantia de consistência dos dados sejam implementadas. Essa necessidade surge das restrições impostas pelos ambientes de comunicação sem fio, tais como: Limitação na largura de banda dos canais de comunicação sem fio, mobilidade e freqüentes desconexões dos dispositivos móveis, mobilidade dos dados e grande número de usuários.

O gerenciamento de dados e o controle de concorrência em ambientes de computação móvel tem sido objeto de uma variedade de pesquisas e produtos comerciais. Novos modelos computacionais, arquiteturas, modelos transacionais, protocolos e algoritmos têm sido propostos. Neste trabalho, fazemos uma revisão bibliográfica das principais abordagens propostas para garantir a consistência dos dados em ambientes de computação móvel e propomos uma taxonomia a fim de classificar e organizar estes trabalhos. Além disso, apresentamos em detalhes como o sistema Bayou [40, 41, 42, 43] pode ser utilizado para garantir a consistência dos dados em redes móveis fracamente (parcialmente) conectadas, garantindo alta disponibilidade de dados.



Este trabalho está organizado da seguinte forma: a seção 2 discute os ambientes de computação móvel; na seção 3 apresentamos uma taxonomia para as abordagens de controle da consistência dos dados; a seção 4 descreve em detalhes o sistema Bayou; e a seção 5 conclui este trabalho.

2. Ambientes de Computação Móvel
Devido aos recentes avanços da computação e das tecnologias de comunicação sem fio podemos afirmar que a informática está entrando em uma nova revolução, tão profunda quanto as que ocorreram com o surgimento dos computadores pessoais e das redes de computadores [50]. A massificação dos dispositivos computacionais portáteis e sua integração com as redes de comunicação sem fio estão possibilitando o acesso à informação em qualquer lugar e a qualquer momento. Este cenário, denominado de computação móvel, está alterando profundamente a maneira como as pessoas trabalham, estudam e usam seu tempo, além de mudar a forma como as empresas oferecem seus produtos e serviços e interagem com seus clientes.

Nesta seção, descrevemos e analisamos as principais propriedades e características de um ambiente de computação móvel. A seção está organizada como descrito a seguir: a subseção 2.1 apresenta uma arquitetura de referência para um ambiente de computação móvel e a subseção 2.2 discute as características, limitações e problemas referentes a estes ambientes.
2.1. Arquitetura Clássica para um Ambiente de Computação Móvel
O termo “móvel” implica na capacidade que um computador possui de mover-se enquanto mantém uma conexão com uma infra-estrutura fixa de comunicação. Assim, de maneira semelhante aos ambientes de computação distribuída, um dispositivo computacional tem acesso a serviços, recursos e dados distribuídos; e, adicionalmente, pode mover-se livremente. Desta forma, a computação móvel amplia o conceito tradicional de computação distribuída. Um modelo abstrato de uma arquitetura para um ambiente de computação móvel é mostrada na figura 1. Esta arquitetura consiste de um conjunto de computadores móveis (MH - Mobile Host) e uma rede de alta velocidade que interconecta fisicamente computadores fixos (FH - Fixed Host) e estações de suporte à mobilidade (MSS - Mobile Support Station). Um computador móvel é um dispositivo de computação inteligente que pode movimentar-se livremente ao mesmo tempo em que mantém sua conexão com a rede fixa através de um link (conexão) sem fio. As estações de suporte à mobilidade fornecem uma interface sem fio que permite aos computadores móveis interagir com a rede fixa, tendo acesso a informações e recursos compartilhados. Cada MSS é responsável por uma determinada região geográfica, chamada de célula, tendo como uma de suas tarefas o endereçamento dos computadores móveis localizados nesta célula. Uma MSS somente pode se comunicar com as unidades móveis que estiverem fisicamente localizadas em sua célula. Um computador fixo é um computador de propósito geral, que pode disponibilizar serviços para os computadores móveis, mas que não é capaz de comunicar-se diretamente com estes [50].

Em uma plataforma de computação móvel, podemos nos referir aos computadores móveis como clientes ou usuários, os quais requisitam serviços disponibilizados por servidores (computadores fixos) localizados na rede fixa. Clientes móveis e estações de suporte à mobilidade se comunicam através de canais de comunicação sem fio. Este canal, em geral, consiste de dois links; o uplink, utilizado para mover dados dos clientes para os as MSS’s, e o downlink, usado para transportar dados das MSS’s para os clientes.




Figura 1. Arquitetura Clássica para um Ambiente de Computação Móvel

2.2. Características de um Ambiente de Computação Móvel
Nesta subseção iremos apresentar e discutir as principais características de uma plataforma computacional baseada no paradigma de computação móvel.

Como afirmado anteriormente, um ambiente de computação móvel apresenta características bastante particulares. Dentre elas, destacam-se:



Limitação de Energia nos Computadores Móveis. Os computadores móveis dependem de baterias para funcionar. Atualmente, as baterias disponíveis no mercado são relativamente pesadas e só conseguem armazenar energia para algumas horas de uso. Este problema é visto como o maior empecilho no uso de computadores móveis. Infelizmente, a tecnologia de construção de baterias não tem acompanhado o crescimento de outros segmentos da informática e a evolução prevista não muda esse cenário [53]. Logo, o gerenciamento de energia é um problema importante e deve ser tratado tanto pelo hardware quanto pelo software. Portanto, energia é um recurso limitado em computadores móveis, e o seu consumo deve ser minimizado. A fim de conservar energia e estender o tempo de vida da bateria, o cliente entra no modo doze (stand by mode), no qual o cliente não está ativamente escutando o canal de comunicação com o servidor. Os clientes gastam uma quantidade de energia significativamente menor no modo doze que no modo ativo, logo uma das principais metas em computação móvel é minimizar o tempo que o cliente deve gastar no modo ativo para recuperar os itens de dados do seu interesse.

Longa Desconexão dos Clientes. Um computador móvel pode passar longos períodos de tempo desconectado, devido às limitações de energia da bateria e da própria mobilidade da máquina, pois pode mover-se para uma área não coberta pelo sistema de comunicação.

Transações de Longa Duração. A eventual e freqüente desconexão dos clientes pode fazer com que as transações móveis que acessam dados dos servidores sejam de longa duração.

Deve ser Escalonável. O número de clientes nas aplicações em ambientes móveis tende a crescer rapidamente. Desta forma, uma plataforma de computação móvel deve estar apta a suportar um grande número de clientes.

Comunicação Assíncrona entre Clientes e Servidores. Em uma rede de comunicação sem fio o custo para manter um servidor statefull chega a ser proibitivo. Por isso, nestes ambientes, os servidores têm uma largura de banda relativamente alta para disseminar informações (dowlink), enquanto os clientes não podem transmitir dados ou, se o fazem, é sobre um link com baixa largura de banda (uplink).



3. Uma Taxonomia para as Abordagens de Consistência de Dados em Computação Móvel
Nesta seção, investigamos e descrevemos as diversas abordagens que têm sido propostas para garantir a consistência dos dados em ambientes de computação móvel. Além disso, propomos uma taxonomia a fim classificar e organizar as soluções encontradas. A taxonomia proposta difere da classificação apresentada por Dunham et al. [26] no sentido em que tenta levar em consideração a arquitetura e o funcionamento das soluções estudadas.
3.1. Classificação

Um sistema de bancos de dados móvel é um ambiente computacional que pode ser visto como a extensão de um sistema distribuído. Özsu e Valduriez propuseram uma excelente classificação para sistemas de bancos de dados distribuídos. Esta taxonomia baseia-se nas características de autonomia, distribuição, e heterogeneidade. Dunham et al. [26] estendem esta classificação adicionando um ponto no eixo da distribuição. Eles observaram que um sistema de computação móvel pode ser visualizado como um sistema distribuído dinâmico, onde os canais de comunicação entre os computadores da rede mudam dinamicamente.

Nesta subseção, propomos uma taxonomia para os sistemas de bancos de dados móveis, a qual baseia-se na arquitetura e no funcionamento destes ambientes.
3.1.1. Replicação/Caching de Dados no Cliente

Devido à freqüente desconexão das unidades móveis, causada pelas limitações das baterias e pela própria mobilidade do dispositivo, a comunicação entre os clientes móveis e o servidor fixo se torna bastante instável. Além disso, o custo de se utilizar uma infra-estrutura de comunicação sem fio pode ser bastante elevado, uma vez que a velocidade de transmissão nestes links é baixa e a taxação pode ser feita com base no tempo de conexão. Portanto, há um incentivo sensato para que os computadores móveis estejam desconectados por longos períodos de tempo. Desta maneira, torna-se necessária uma forma de possibilitar aos usuários de dispositivos portáteis continuarem a execução de suas operações (leitura e escrita) sobre os itens do banco de dados, mesmo na ausência de uma conexão com o restante do sistema de comunicação, em particular, com o servidor de banco de dados. Chamamos esta característica de suporte à desconexão. A fim de se alcançar este objetivo, uma cópia dos dados (ou de parte deles) é armazenada localmente nos clientes. Em caso de desconexão, as transações locais irão executar suas operações de leitura e escrita sobre sua cópia local, o que proporciona uma maior disponibilidade dos dados e um melhor desempenho na execução das transações. Entretanto, um mecanismo adicional para manter a consistência entre os dados armazenados em cada cliente e no servidor central torna-se necessário.

Duas abordagens principais para manter a consistência de dados nestes ambientes podem ser encontradas na literatura. A primeira abordagem trata a cópia local dos clientes como sendo uma réplica total ou parcial do banco de dados central (armazenado na rede fixa) [2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 19, 24, 39]. Já a segunda, considera a cópia local como um cache [1, 13, 15, 16, 17, 20, 21, 22, 23, 38].
3.1.2. Servidores Replicados

Um banco de dados replicado é um banco de dados distribuído no qual múltiplas cópias de parte dos itens de dados são armazenadas em diversos servidores. A replicação de dados traz as seguintes vantagens:



Melhor Disponibilidade de Dados: Os dados continuam disponíveis, ou seja, as aplicações podem continuar sua execução, mesmo que alguns dos servidores falhem.

Ganhos de Performance: Uma vez que existem várias cópias de cada item de dado, as aplicações podem usar as cópias que estiverem fisicamente mais próximas, permitindo um acesso mais rápido aos dados e reduzindo o tráfego no meio de comunicação.

Maior Throughput: Como existem várias cópias de cada item de dado em diferentes locais, a contenção no acesso aos itens de dados tende a ser menor, o grau de concorrência tende a ser maior e assim o número de transações concluídas por unidade de tempo será maior.

Entretanto, estes benefícios trazem a necessidade de atualizar todas as cópias de um item quando este for alterado. Assim, as leituras tendem a ser mais rápidas e as escritas mais lentas. Além disso, o SGBD deve garantir que a execução concorrente de um conjunto de transações sobre um banco de dados replicado será equivalente a uma execução serial sobre o mesmo banco de dados não replicado (one-copy database), o que é denominado de one-copy serializability (1SR) pela literatura. Nos tradicionais SGBD’s replicados isto é realizado através de um protocolo de controle de réplica (replica control protocol), os quais podem ser classificados em três grupos: Primary-Copy Method, Quorum-Consensus Method e Available-Copies Method.

Infelizmente, estes algoritmos não são adequados para ambientes de computação móvel, onde tipicamente há uma grande limitação para a comunicação entre os dispositivos móveis e a rede fixa, além da freqüente e muitas vezes prolongada desconexão destes dispositivos. Por este motivo, várias abordagens têm sido propostas, como por exemplo, o sistema Bayou [40, 41, 42, 43], a Votação Ponderada [44] e o sistema Deno [45].
3.1.3. Replicação em Redes Ad Hoc

Os recentes avanços ocorridos nas tecnologias de comunicação sem fio têm levado a um grande interesse pelas redes ad hoc, as quais são compostas exclusivamente por dispositivos móveis. Em uma rede ad hoc, cada dispositivo móvel funciona como um roteador, e se interliga com outros computadores móveis. Assim, a comunicação entre dois hosts é possível mesmo que o host origem e o destino não estejam na área de cobertura um do outro, neste caso, os pacotes de dados são encaminhados através de outros hosts que estejam no caminho até que cheguem ao destino.

Em redes ad hoc, uma vez que os hosts se movem livremente e que as desconexões ocorrem com freqüência, o que causa a freqüente divisão (partição) da rede, as diferenças tecnológicas com as redes fixas e redes móveis estruturadas são grandes.

Quando acontece a divisão da rede, o que ocorre com freqüência em redes ad hoc, um dispositivo que está em uma das partições não consegue acessar os itens de dados mantidos por dispositivos que estejam em outra partição. Assim, a disponibilidade de dados é bem menor que em redes móveis infra-estruturadas. Com a finalidade de reduzir a deteriorização da disponibilidade de dados uma das estratégias possíveis é a replicação de dados. Porém, os métodos tradicionais são impraticáveis devido ao alto dinamismo das redes ad hoc. Além disso, outra diferença fundamental é que em redes ad hoc, mesmo que um cliente móvel não possa acessar um servidor (provedor) de dados diretamente, (ou seja, mesmo que não esteja na mesma área de cobertura do servidor), ele poderá fazê-lo através de hosts intermediários.

Desta forma, novos mecanismos para gerência de dados replicados foram propostos especificamente para redes ad hoc, tentando tirar proveito e se adequar às suas características particulares, dentre eles destacamos: os métodos para alocação de réplicas [34] e o método PAN [37].
3.1.4. SBD’s Múltiplos em Computação Móvel

Durante muitos anos a utilização dos bancos de dados centralizados foi a abordagem dominante para o gerenciamento dos dados corporativos. Entretanto, as freqüentes fusões e aquisições de diferentes companhias tem levado as organizações à uma nova realidade, trazendo a necessidade de gerenciar uma variedade de sistemas de bancos de dados, os quais são muitas vezes heterogêneos, autônomos e distribuídos geograficamente. Com a finalidade de tornar estes diferentes bancos de dados inter-operáveis a abordagem de bancos de dados múltiplos tem sido exaustivamente estudada. Um banco de dados múltiplo consiste em uma coleção de bancos de dados pré-existentes e autônomos, os quais são chamados de bancos de dados locais (local databases – LDBs). Os sistemas concebidos para gerenciar os bancos de dados múltiplos são denominados sistemas de bancos de dados múltiplos (Multidatabase Systems – MDBSs).

Com o rápido avanço nas tecnologias de comunicação sem fio surge a necessidade de estender os serviços dos MDBSs a usuários de dispositivos portáteis (móveis). Este novo cenário é denominado de sistemas de bancos de dados múltiplos móveis (Mobile Multidatabase Systems – MMDBSs).

O processamento de transações em sistemas de bancos de dados múltiplos tem sido foco de diversas pesquisas [46] e muitos protocolos para controle de concorrência foram propostos. Entretanto, estas técnicas não são adequadas para sistemas de bancos de dados múltiplos com suporte a usuários móveis. Isto porque o conceito de mobilidade, onde os usuários acessam os dados através de uma conexão sem fio, introduz complexidades e restrições adicionais, as quais discutimos na seção 2.

Desta forma, novas abordagens foram propostas, entre elas destacamos: o sistema Kangaroo [26], o PSTM [25] e o V-Lock [31].

3.1.5. Comunidades de Bancos de Dados

Como mostramos anteriormente, a evolução na performance e na capacidade de comunicação dos dispositivos portáteis possibilitou que alguns destes dispositivos adquirissem a capacidade de se comunicar sem a participação de qualquer componente da rede fixa, podendo formar estruturas altamente dinâmicas que se formam de maneira espontânea. Estas estruturas são chamadas redes ad hoc [55]. Em contraste com os ambientes tradicionais de computação móvel, onde a localização dos servidores de dados e as conexões de rede são relativamente estáveis. Nas redes ad hoc a migração dos hosts e a instabilidade das conexões são a regra.

Naturalmente, os usuários destes ambientes desejam compartilhar informações entre si. Este compartilhamento pode ser realizado através da criação de federações dinâmicas de bancos de dados. Tais federações são denominadas comunidades de bancos de dados móveis (Mobile Database Communities - MDbC’s). Uma MDbC é um ambiente dinamicamente configurável composto de múltiplos bancos de dados heterogêneos, autônomos, distribuídos e móveis, no qual cada usuário pode acessar o banco de dados dos demais usuários através de uma infra-estrutura de comunicação sem fio. Cada banco de dados neste ambiente é chamado de membro ou participante da comunidade. Assim, uma MDbC é um sistema de bancos de dados múltiplos onde os computadores que armazenam bancos de dados locais podem mover-se livremente, e assim, apresentam uma conexão intermitente. Desta forma, os mecanismos propostos para o controle de concorrência em sistemas de bancos de dados múltiplos e móveis (MMDBSs) não são adequados para MDbC’s. Logo, novas abordagens estão sendo estudadas. O SESAMO, proposto em [35] é a principal abordagem encontrada na literatura.


3.1.6. Ambientes de Broadcast

A computação móvel está proporcionando o surgimento de novas e sofisticadas aplicações em banco de dados. Muitas delas apresentam como características um grande número de clientes móveis, um pequeno número de servidores e um banco de dados relativamente pequeno. Como exemplo podemos citar as aplicações de comércio eletrônico, tais como leilões e propostas eletrônicas, sistemas de controle de tráfego e sistemas baseados em localização [52]. Enquanto tradicionalmente os dados são enviados dos servidores para os clientes sob demanda (pull-based), estas aplicações se beneficiam do modo de disseminação de dados baseado em difusão (push-based). Nele, o servidor repetidamente difunde (broadcast) os itens de dados para uma população de clientes sem que haja uma requisição específica por partes dos clientes. Os clientes monitoram o canal de broadcast e retiram os itens de dados que necessitam [51]. Enquanto estes itens são enviados por broadcast, as transações que estão sendo executadas no servidor podem atualizar os valores dos itens de dados. Desta forma, distinguimos dois tipos de transações: as transações do servidor e as transações dos clientes, as quais chamamos de transações móveis.

Os ambientes de broadcast apresenta diversas vantagens. O servidor na rede fixa não fica sobrecarregado com pedidos de requisições e não envia várias mensagens individuais que teriam que ser transmitidas em sistemas pull-based. Além disso, os dados podem ser acessados concorrentemente por qualquer número de clientes sem nenhuma degradação de performance. Entretanto, o acesso aos dados é estritamente seqüencial, ou seja, os clientes necessitam esperar que os dados de seu interesse apareçam no canal. Isto aumenta a latência de acesso à informação, a qual é proporcional à quantidade de informações a serem transmitidas em cada ciclo.

O conceito de disseminação de dados por broadcast não é novo. Trabalhos anteriores incluem o projeto datacycle e o sistema de informações da comunidade de Boston (BCIS) [58]. Entretanto, novas abordagens têm sido propostas para garantir a consistência de dados em ambientes de computação móvel com disseminação de dados por broadcast. Dentre elas destacamos: o Relatório de Invalidação [51], a Invalidação Baseada em Versões [51], Múltiplas Versões [51], Consistência de Atualização [52] e TGST [49].



4. Estudo de Caso: O Sistema Bayou

Bayou [40, 41, 42, 43] é um sistema de armazenamento replicado, que utiliza um nível fraco de consistência e que foi projetado para ambientes de computação móvel que inclui dispositivos portáteis fracamente conectados. O sistema Bayou provê uma infra-estrutura para o desenvolvimento de uma variedade de aplicações colaborativas, que não tenham requisitos de tempo real, tais como calendários, e-mail e edição de documentos para grupos desconectados.



4.1 Arquitetura do Sistema

No sistema Bayou, cada banco de dados é inteiramente replicado em um conjunto de servidores. As aplicações executam como clientes e interagem com os servidores através de uma API específica, denominada Bayou Application Programming Interface, a qual 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. O cliente e o servidor podem co-existir em um determinado host, ou podem executar de forma isolada. Assim, em contraste com o sistema Coda que faz uma distinção clara entre unidades móveis executando como clientes e hosts fixos fortemente conectados a redes fixas executando como servidores, a arquitetura Bayou trata os dispositivos móveis como um ponto em um modelo ponto a ponto (peer-to-peer) onde os servidores estão conectados de forma intermitente uns com os outros.

O sistema Bayou não provê suporte à replicação transparente para as aplicações que executam na camada superior. As aplicações têm o conhecimento de que podem ler dados inconsistentes, e que suas escritas são uma tentativa. Entretanto, o conhecimento específico do domínio da aplicação é explorado com a finalidade de detectar e solucionar conflitos de forma automática.
4.3 Conectividade Fraca

O sistema Bayou suporta um esquema de replicação read-any/write-any. Quando um cliente submete uma operação de escrita a um determinado servidor, este executa a escrita imediatamente em sua réplica, sem qualquer processo de detecção de conflitos. As escritas que foram aceitas localmente são chamadas de tentativas (tentative). O valor resultante de uma tentativa de escrita (tentative write) é imediatamente disponibilizado para leitura. Os servidores propagam as escritas entre si através de um processo baseado na comunicação entre pares denominado sessão de anti-entropia (anti-entropy). Durante uma sessão, os dois servidores envolvidos trocam suas escritas, e então, ao final do processo, os servidores entram em um consenso sobre que escritas devem executar e em que ordem. O sistema garante que todos os servidores irão eventualmente receber todas as escritas e que dois servidores que receberam o mesmo conjunto de escritas irão apresentar o mesmo estado (conteúdo) do banco de dados. Para alcançar este objetivo, é necessário que as escritas sejam executadas na mesma ordem global em todos os servidores e que os procedimentos para detecção e resolução de conflitos sejam determinísticos.

Uma vez que os servidores podem receber as operações de escrita dos clientes e dos outros servidores em uma ordem diferente da ordem global, os servidores podem necessitar desfazer os efeitos de uma tentativa de escrita (tentative write) previamente executada e executá-la novamente em uma outra ordem. Assim, uma dada escrita pode ser executada diversas vezes em um mesmo servidor. Uma escrita se torna estável quando o servidor recebe e executa todas as escritas que a precedem. A fim de aumentar a taxa com que as escritas se tornam estáveis, Bayou usa um esquema denominado primary-commit: um servidor designado como primário tem a responsabilidade de executar o commit das atualizações, ou seja, torná-las permanente. As escritas já consolidadas (committed writes) são ordenadas de acordo com o momento em que elas são consolidadas no servidor primário, sendo ordenadas antes das tentativas de escrita. A informação de que escritas foram consolidadas e em que ordem são propagadas para os demais servidores durante o processo de anti-entropia. Cada servidor mantém duas visões do banco de dados: uma cópia que reflete somente os dados consolidados (committed) e outra cópia que reflete as tentativas de escrita conhecidas até o momento pelo servidor.

O sistema Bayou provê um método automático baseado em validação de dependências para detectar conflitos e procedimentos para a resolução automática de conflitos. As validações de dependências e os procedimentos para resolução de conflitos são incluídos juntos a cada operação de escrita. A validação de dependência consiste de uma consulta e o resultado esperado. Antes da operação de escrita ser executada no servidor, a consulta que compõe a validação de dependência é executada sobre a cópia corrente do banco de dados. Um conflito é detectado se a consulta não recupera o resultado esperado. Neste caso, a atualização requisitada não é executada e o servidor invoca o procedimento para resolver o conflito detectado. Este procedimento é um programa escrito em uma linguagem interpretada de alto nível, o qual é responsável por solucionar conflitos e produzir uma atualização modificada que será executada. Quando a resolução automática não é possível, o procedimento de resolução de conflito deve armazenar esta informação em um log, o qual será utilizado para a resolução manual de conflitos. Bayou permite que as réplicas permaneçam acessíveis mesmo quando conflitos são detectados e ainda não resolvidos. Isto permite que os clientes continuem suas operações, mas pode levar a criação de conflitos em cascata.


4.4 Mobilidade e Garantias de Sessão

As aplicações no sistema Bayou não necessitam se restringir a utilizar um único servidor, mas podem interagir com qualquer servidor com o qual consigam se comunicar. Para isso, é utilizado um esquema de replicação read-any/write-any. Além disso, o Bayou utiliza um mecanismo de consistência fraca, os quais são interessantes, pois proporcionam alta disponibilidade, boa escalabilidade, e simplicidade de projeto. Entretanto, é possível que os clientes obtenham valores inconsistentes quando lêem dados de diferentes réplicas. Por exemplo, um usuário pode ler o valor de um determinado item de dado e posteriormente ao executar esta operação novamente pode obter um valor anterior ao valor lido inicialmente. Um problema sério ocorre nos sistemas com consistência fraca mesmo quando um único usuário ou aplicação está atualizando os dados. Suponha que um usuário móvel executou uma operação de escrita em um determinado servidor, e mais tarde tentou ler o mesmo item de um outro servidor, mas como os servidores ainda não se sincronizaram, o cliente irá obter um valor inconsistente. Para reduzir as inconsistências observadas pelos clientes quando acessam diferentes servidores, Bayou provê garantias de sessão (session guarantees). Uma garantia de sessã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ões sejam correspondentes ao conceito de transação atômica, que garante atomicidade e serializabilidade. Ao contrário, a intenção é proporcionar às aplicações individualmente uma visão do banco de dados que seja consistente com as suas próprias ações, mesmo que estas leiam e escrevam a partir de vários servidores, potencialmente inconsistentes. Quatro garantias são propostas. Estas garantias podem ser aplicadas independentemente nas diversas operações que pertencem à sessão. A seguir, descrevemos estas garantias:



Read Your Writes: As operações de leitura devem refletir as escritas executas anteriormente (pela mesma sessão).

Monotonic Reads: Leituras sucessivas refletem o resultado de um conjunto de escritas não decrescente.

Writes Follow Reads: As operações de escrita são propagadas após as operações de leitura das quais dependem.

Monotonic Writes: As operações de escrita são propagadas após as escritas que as precedem logicamente.

Essas propriedades são garantias no sentido que o sistema de armazenamento as assegura para cada leitura ou escrita pertencente a uma sessão, ou caso não consiga assegurá-las informa para a aplicação que a garantia não pode ser alcançada. As garantias de sessão proporcionam um meio de adaptabilidade. O grau de consistência pode ser adaptado aos vários níveis de conectividade, selecionando-se individualmente que garantias de sessão deseja-se utilizar.


4.5 Operações Desconectadas

O projeto Bayou não inclui a noção de operação desconectada, uma vez que vários níveis de conectividade são possíveis. Sendo necessário apenas que ocasionalmente a comunicação entre pares de servidores aconteça. Assim, o sistema trata a arbitrária conectividade da rede. Por exemplo, grupos de servidores podem se desconectar do restante do sistema e ainda continuarem conectados entre si.


5. Conclusões

A importância deste estudo se dá em razão de um número razoável de abordagens existentes para garantir a consistência e a disponibilidade de dados em ambientes de computação móvel. Assim, procuramos fazer uma revisão do estado da arte a fim de oferecer um guia de referência para os interessados em desenvolver aplicações e pesquisas que envolvam a manipulação de dados em ambientes móveis.

Logicamente, não temos a pretensão de esgotar a discussão sobre a consistência de dados em computação móvel, ao contrário, desejamos despertar a atenção dos interessados no assunto, procurando abordar os pontos que julgamos importantes. Além disso, oferecemos uma relação bibliográfica bastante vasta, que inclui diversas soluções para as mais variadas arquiteturas encontradas em computação móvel.

Outras contribuições importantes deste trabalho foram: a elaboração de uma taxonomia que classifica e organiza as principais propostas para a consistência de dados em ambientes de computação móvel, e a descrição detalhada do sistema Bayou.



Referências


[1]

Walborn G., e Chrysanthis P. Supporting Semantics-Based Transaction Processing in Mobile Database Applications. 1995.

[2]

Gray J., Helland P., O’Neil P., e Shasha D. The Dangers of Replication and a Solution. 1996.

[3]

Barbará-Millá D., e Garcia-Molina H. Replicated Data Management in Mobile Environments: Anything new under the sun? 1994.

[4]

Ionitou C., e Andersen B. Replicated Objects with Lazy Consistency. 1995.

[5]

Lu Q., e Satyanaranyanan M. Isolation-Only Transactions for Mobile Computing. 1994.

[6]

Huang Y., Sistla P., e Wolfson O. Data Replication for Mobile Computers. 1994.

[7]

Kanitkar V., e Delis A. Two-Stage Transaction Processing in Client-Server DBMSs. 1998.

[8]

Yee W., Donahoo M., Omiecinski E., e Navathe S. Scaling Replica Maintenance in Intermittently Synchronized Mobile Database. 2001.

[9]

B. R. Badrinath and T. Imielinski. Replication and Mobility. 1992.

[10]

Lu Q., e Satyanaranyanan M. Improving Data Consistency in Mobile Computing Using Isolation-Only transaction.

[11]

Pitoura E., e Bhargava B. Data Consistency in Intermittently Connected Distributed Systems. 1999.

[12]

Loh y., Hara T., Tsukamoto M, e Nishio S. A Hybrid Method for Concurrent Updates on Disconnected Databases in Mobile Computing Environments. 2000.

[13]

Cao H. Adaptive Power-Aware Cache Management for Mobile Computing Systems. 2002.

[14]

Lin H., Chen C., e Zhou B. A Probability-Based Approach of Transaction Consistency in Mobile Environments. 2001.

[15]

Barbará D., e Imielínski T. Sleepers and Workaholics: caching Strategies in Mobile Environments. 1994.

[16]

Su C., e Tassiulas L. Joint Broadcast Scheduling and User’s Cache Management for Efficient Information Delivery. 1998.

[17]

Jing J., e Elmargarmid A. Bit-Sequences: An Adaptive Cache Invalidation Method in Mobile Client/Server Environments. 1997.

[18]

Franklin M., Carey M., e Livny M. Transactional Client-Server Cache Consistency: Alternatives and Performance. 1997.

[19]

Mazumdar S., Pietrzyk M., e Chrysanthis P. Caching Constrained Mobile Data. 2001

[20]

Machado J. Um Mecanismo de Gerência de Cache para um Servidor de Dados Móveis em Redes Ad Hoc. 2004.

[21]

Lee S., Hwang C., e Yu H. Supporting Transactional Cache Consistency in Mobile Database Systems. 1999.

[22]

Yuen J., Chan E., Lam K., e Leung H. Cache Invalidation Scheme for Mobile Computing Systems with Real-Time Data. 2000.

[23]

Berkenbrok C., Dantas M., Berkenbrok G. e Filho P. Caching Strategies Using Propagation and Invalidation Update in Mobile Computing Environments.

[24]

Phatak S., e Badrinath. Transaction-Centric Reconciliation in Disconnected Database. 2004.

[25]

Dirckze R., e Gruenwald L. A Pré-Serialization Transaction Management Techniques for Mobile Multidatabases. 2000.

[26]

Dunham M., Helal A., e Balakrishnan S. A Mobile Transaction Model that Captures Both the Data and Movement Behavior. 1997.

[27]

Weijun X., Zhengding L., Bing L. e Sarem M. Transaction Management in Mobile Multidatabase Systems. 2001.

[28]

Dirckze P., e Gruenwald L. A Toggle Transaction Management Technique for Mobile Multidatabase. 1998.

[29]

Pitoura E., e Bhargava B. A Framework for Providing Consistency and Recoverable Agent-Based Access to Heterogeneous Mobile Databases. 1995.

[30]

Faiz M., e Zaslavsky A. Database Replica Management Strategies in Multidatabase Systems with Mobile Hosts. 1995.

[31]

Lim J., e Hurson A. Transaction Processing in Mobile, Heterogeneous Database System. 2002.

[32]

Holliday J., Agrawal D., e Abbadi A. Planned Disconnections for Mobile Databases. 2000.

[33]

Holliday J., Agrawal D., e Abbadi A. Disconnected Modes for Mobile Database. 2002.

[34]

Hara T. Replica Allocation Methods in Ad Hoc Networks with Data Update. 2003.

[35]

Frank S., e Brayner A. SESAMO: Uma Estratégia de Controle de Concorrência em Sistemas Múltiplos de Bancos de Dados. 2004.

[36]

Alonso R., Bárbara D., e Garcia-Molina H. Data Caching Issues in a Information Retrieval System. 1990.

[37]

Luo J., Hubaux J., e Eugster P. PAN: Providing Reliable Storage in Móbile Ad Hoc Networks with Probabilistic Quorum Systems. 2003.

[38]

Hou W., Su M., Zhang H., e Wang H. An Optimal Construction of Invalidation Reports for Móbile Databases. 2001.

[39]

Barbará D. Mobile Computing and Databases – A Survey. 1998.

[40]

Terry D., Demers A., Petersen K., Spreitzer M., Theimer M. e Welch B. Session Guarantees for Weakly Consistent Replicated Data. 1994.

[41]

Terry D., Demers A., Petersen K., Spreitzer M., Theimer M., Welch B. e Hauser C. Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System. 1995.

[42]

Terry D., Demers A., Petersen K., Spreitzer M., Theimer M. e Welch B. The Bayou Architecture: Support for Data Sharing among Mobile Users. 1994.

[43]

Terry D., Demers A., Petersen K., Spreitzer M. e Theimer M. Flexible Update Propagation for Weakly Consistent Replication. 1997.

[44]

Rodrig M. e Lamarca A. Decentralized Weighted Voting for P2P Data Management. 2003.

[45]

Cetintemel U., Keleher P. e Franklin M. Support for Speculative Update Propagation and Mobility in Deno. 1999.

[46]

Brayner A. Transaction Management in Multidatabase System. 1999.

[47]

Brayner A. e Häder T. Global Semantic Serializability: Na Approach to Increase Concurrency Control in Multidatabase Systems. 2001

[48]

Brayner A., Häder T. e Ritter N. Semantic Serializability: A Correctness Criterion for Processing Transactions in Advanced Database Applications. 1999.

[49]

Brayner A. e Monteiro J. Temporal Serialization Graph Testing: An Approach to Control Concurrency in Broadcast Environments. 2000.

[50]

Mateus G. e Loureiro A. Introdução à Computação Móvel. 1998.

[51]

Pitoura E. e Chrysanthis P. Scalable Processing of Read-Only Transactions in Broadcast Push. 1999.

[52]

Shanmugasundaram J., Nithrakashyap A., Sivasankaran R. e Ramamritham K. Efficient Concurrent Control for Broadcast Environments. 1999.

[53]

Sheng S., Chandrasekaran A. e Broderson R. A Portable Multimedia Terminal for Personal Communications. 1992

[54]

J. Jing, A. Helal and A. Elmagarmid. Client-Server Computing in Mobile Environments. 1999.

[55]

J. P. Macker and M. S. Corson. Mobile Ad Hoc Networking and the IETF”, Internet Engineering Task Force MANET Working Group. Available online at http://www.ietf.org/html.charter/manet-charter.html.

[56]

Brayner A. e Aguiar L. Increasing Mobile Transaction Concurrency in Móbile Database Communities. 2003.

[57]

Brayner A. e Aguiar J. Sharing Mobile Database in Dynamically Configurable Environments. 2003.

[58]

Herman G. The Datacycle Architecture for Very Hight Throughput Database Systems. 1987.

[59]

S. Acharya, R. Alonso, M. Franklin, e S. Zdonik. Broadcast Disks: Data Management for Asymmetric Communications Environments. 1995.

[60]

S. Acharya, M. Franklin, e S. Zdonik. Disseminating Updates on Broadcast Disks. 1996.

[61]

M. A. Casanova. The Concurrency Problem of Database Systems. 1981.

[62]

A. Datta, D. E. Vandermeer, A. Celik, e V. Kumar. Broadcast Protocols to Support Eficcient Retrieval from Databases by Mobile Users. 1999.

[63]

T. Imielinski and B. R. Badrinath. Mobile Wireless Computing: Challenges in Data Management. 1994.

[64]

B. Oki. The Information Bus – A Architecture for Extensible Distributed Systems. 1993.

[65]

S. Shekar and D. Liu. Genesis and Advanced Traler Informations Systems (ATIS): Killer Applications for Mobile Computing. 1994.







©aneste.org 2017
enviar mensagem

    Página principal