Computação Ubı́qua: Gestão e Disseminação de
Informação
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Mestrado em Engenharia Informática
Introdução
2010–2011
Desafios
Mobile Data Caching
Esquemas de Gestão
de Cache para
Sistemas Móveis
Vitor Beires Nogueira
Escola de Ciência e Tencologia
Universidade de Évora
1.1
Motivação
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Introdução
Caching de
Informação
Desafios
Obtenção de informação
Mobile Data Caching
A informação pode ser obtida de duas formas:
1 pushed (empurrada)
Esquemas de Gestão
de Cache para
Sistemas Móveis
I
I
2
por exemplo televisão, rádio, etc
modo ”publish subscribe”: podemos por exemplo subscrever informações sobre
a bolsa
pulled (puxada)
I
I
modo ”on demand”
o pedido é explicito e feito pelo receptor
1.2
Modo ”publish subscribe”
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Modo ”publish subscribe”
na computação móvel este modo é combinado com o broadcast existente
na comunicação sem fios
eficiente em termos de recursos
Introdução
Caching de
Informação
Desafios
Mobile Data Caching
escalável
Exemplos: serviços de informação financeira, de aeroportos, de
emergência, etc
Esquemas de Gestão
de Cache para
Sistemas Móveis
aconselhável quando o ”downlink”é consideravelmente superior ao
”uplink”
Questões que resultantes deste tipo de serviços
Que serviços publicar?
Com que frequência publicar os serviços?
Como adaptar a alocação da largura de banda entre os canais de uplink e
de downlink de modo a reflectir a carga numa célula?
Como tornar transparente o acesso a estes serviços?
1.3
Modo ”on demand”
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Introdução
Caching de
Informação
Desafios
Mobile Data Caching
os nós móveis necessitam de energia para fazer o pedido/pergunta
Esquemas de Gestão
de Cache para
Sistemas Móveis
alguns conteúdos são consultados mais frequentemente ⇒ hot items
não é escalável (número de clientes móveis)
1.4
Caching de Informação
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Caching
Na vida real é usual manter um pequeno stock de artigos ”essenciais”:
dinheiro na carteira, alimentos na dispensa, etc. Quais as vantagens?
Podemos reabastecer o stock de dois modos:
1
2
à medida que vamos precisando
fazendo ”previsões”
Introdução
Caching de
Informação
Desafios
Mobile Data Caching
Esquemas de Gestão
de Cache para
Sistemas Móveis
Hoarding
Quando sabemos que um determinado artigo vai escassear/esgotar.
Quando armazenar?
O que armazenar?
Caching/Hoarding na Computação Móvel
Consideramos a informação como um item que podemos fazer
caching/hoarding.
Acarreta muitos problemas: considere a situação em que duas pessoas
fazerem o caching do mesmo ficheiro, alteraram-nos e depois podemos
ter inconsistência
1.5
Desafios
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Nas redes sem fios as ligações tem menor largura de banda e estão mais
sujeitas a desconexões (weakly connected mobile clients)
As desconexões podem ser:
I
I
involuntárias
voluntárias
Como assegurar um acesso óptimo à informação num ambiente de
computação móvel onde entre os clientes e os servidores existe uma
ligação perecı́vel?
Introdução
Desafios
Disseminação de
Informação
Escalonamento do
broadcast
Mobile Data Caching
Esquemas de Gestão
de Cache para
Sistemas Móveis
Como minimizar o consumo de recursos na gestão de informação sem
deixar de ter um nı́vel aceitável de consistência?
Como explorar a assimetria da rede sem fios de modo a assegurar uma
baixa latência de acesso à informação assim como um baixo consumo de
recursos?
Como estender as técnicas de gestão de cache para informação
dependente do contexto (espacio/temporal)?
1.6
Disseminação de Informação
Modo ”on demand”
Neste modo o nó móvel
tem de competir pelo canal de uplink
tem de aguardar pela resposta
consome energia
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Introdução
Desafios
Disseminação de
Informação
Escalonamento do
broadcast
Mobile Data Caching
consome largura de banda
A situação agrava-se quando temos vários nós pedirem a mesma informação!
Esquemas de Gestão
de Cache para
Sistemas Móveis
Modo ”publish subscribe”
o servidor utiliza um canal de broadcast
envia informação
envia ı́ndice da informação: deste modo o cliente móvel pode determinar
quando estará disponı́vel a informação que lhe interessa
é poupada largura de banda
é um modo facilmente escalável
poupa energia aos clientes móveis
1.7
Ilustração do modo ”publish subscribe”
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Introdução
Desafios
Disseminação de
Informação
Escalonamento do
broadcast
Mobile Data Caching
Esquemas de Gestão
de Cache para
Sistemas Móveis
1.8
Estruturação da largura de banda de uma célula
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Divisão lógica da largura de banda de uma célula
Introdução
Desafios
Disseminação de
Informação
Escalonamento do
broadcast
Mobile Data Caching
Esquemas de Gestão
de Cache para
Sistemas Móveis
Divisão fı́sica da largura de banda de uma célula
on demand
broadcast: dividido em slots de modo a que cada item de informação
caiba em cada slot
1.9
Escalonamento do broadcast
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Introdução
Desafios
Disseminação de
Informação
Escalonamento do
broadcast
Determinar quando é que os diferentes itens de informação devem ser
transmitidos
Para facilitar a compreensão vamos considerar o canal de broadcast como
uma extensão da memória do nó móvel (semelhante a um disco no éter).
Mobile Data Caching
Esquemas de Gestão
de Cache para
Sistemas Móveis
1.10
Exemplo de um escalonamento do broadcast
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Introdução
Desafios
Disseminação de
Informação
Escalonamento do
broadcast
Mobile Data Caching
Esquemas de Gestão
de Cache para
Sistemas Móveis
1.11
Algoritmo para escalonar
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Introdução
Desafios
Disseminação de
Informação
Escalonamento do
broadcast
Mobile Data Caching
Esquemas de Gestão
de Cache para
Sistemas Móveis
1.12
Mobile Data Caching
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Introdução
Desafios
Mobile Data Caching
Uma cache é uma memória rápida e de menor dimensão com a função de
guardar informação utilizada frequentemente
Cache ⇒ Memória Principal ⇒ Disco
Tendo subjacente uma memória hierárquica, como podemos reduzir a
latência da leitura/escrita?
Estratégias de
Caching em Sistemas
Distruibuı́dos
Gestão da
Consistência da Cache
Questões de
Arquitectura e de
Performance
Esquemas de Gestão
de Cache para
Sistemas Móveis
Existem várias técnicas/algoritmos de gestão de cache.
1.13
Estratégias de Caching em Sistemas Distruibuı́dos
Considerações gerais
Nos SD (Sistemas Distruibuı́dos) assume-se que
I
I
I
existe uma grande largura de banda
a rede tem baixa latência
as falhas na rede são pouco frequentes
Por vezes fazem caching/prefetching de informação de modo a ocultar
possı́veis falhas na rede
Cenários
Os sistemas de gestão de cache dos SD tem de lidar com 2 cenários:
1
a informação existente na memória partilhada (servidor) pode ser
lida/escrita por diferentes clientes de um modo concorrente. Como por
exemplo nos sistemas de ficheiros distribuı́dos.
2
Os clientes só podem ler a informação. Como por exemplo na WWW.
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Introdução
Desafios
Mobile Data Caching
Estratégias de
Caching em Sistemas
Distruibuı́dos
Gestão da
Consistência da Cache
Questões de
Arquitectura e de
Performance
Esquemas de Gestão
de Cache para
Sistemas Móveis
Desafio
O desafio principal consiste em manter a consistência dos dados entre os
clientes e os servidores.
1.14
Gestão da Consistência da Cache
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Introdução
Desafios
Mobile Data Caching
A gestão da consistência da cache é necessária para garantir que sempre
que se utiliza informação da cache, esta satisfaz certos requisitos de
actualidade.
Existem vários modelos:
I
I
consistência de cache forte (como exemplo NFS)
consistência de cache fraca
A aplicabilidade dos modelos acima (para SD) ao caso móvel é limitada
uma vez que é necessário ter em conta o consumo de energia assim como
a maior ocorrência de falhas.
Estratégias de
Caching em Sistemas
Distruibuı́dos
Gestão da
Consistência da Cache
Questões de
Arquitectura e de
Performance
Esquemas de Gestão
de Cache para
Sistemas Móveis
1.15
Questões de Arquitectura e de Performance
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Introdução
Problemas que os sistemas de gestão de cache tem de lidar nos ambientes
móveis:
Como reduzir a latência no cliente?
Como manter a consistência da cache entre as várias caches e o servidor?
Como assegurar um acesso à informação aceitável na presença de
desconexões frequentes?
Como atingir alta eficiência energética e de largura de banda?
Desafios
Mobile Data Caching
Estratégias de
Caching em Sistemas
Distruibuı́dos
Gestão da
Consistência da Cache
Questões de
Arquitectura e de
Performance
Esquemas de Gestão
de Cache para
Sistemas Móveis
Como determinar o custo de uma falha na cache (cache miss) e como
incorporar este custo no sistema de gestão de cache?
Como gerir informação dependente do contexto (espaço, etc) na cache?
Como activar a cooperação entre múltiplas caches?
1.16
Organização das Caches
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Introdução
Desafios
Questões relativas à organização das caches:
Onde é que guardamos as caches?
Cache hierárquica?
O que guardamos na cache?
Como é que invalidamos o conteúdo da cache?
Quem é que invalida tal conteúdo?
Mobile Data Caching
Estratégias de
Caching em Sistemas
Distruibuı́dos
Gestão da
Consistência da Cache
Questões de
Arquitectura e de
Performance
Esquemas de Gestão
de Cache para
Sistemas Móveis
Que garantias de actualidade é que o sistema pode dar aos utilizadores?
Quais os custos envolvidos?
1.17
Esquemas de Gestão de Cache para Sistemas Móveis
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Introdução
Desafios
Mobile Data Caching
Particularidades
A gestão de cache em sistemas móveis tem algumas particularidades:
o protocolo de gestão de cache não deve sobrecarregar os recursos da
rede sem fios assim como o dispositivo móvel
Esquemas de Gestão
de Cache para
Sistemas Móveis
Uma taxonomia para
esquemas de gestão
de cache
Broadcast de
relatórios de
invalidação
estes protocolos devem ser eficientes em termos energéticos, tolerantes à
falha e adaptativos à variabilidade da QoS fornecida pela rede sem fios
1.18
Uma taxonomia para esquemas de gestão de cache
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Introdução
Estratégias para manter a consistência de cache
Desafios
Existem três estratégias:
Mobile Data Caching
”polling-every-time”
baseadas em TTL (time-to-leave)
baseadas em invalidar
I
sem estado: o servidor desconhece o conteúdo da cache dos clientes
• sı́ncrona: os relatórios da informação inválida são enviados periodicamente
• assı́ncrona: os relatórios da informação inválida são enviados sempre que a
informação é modificada.
I
Esquemas de Gestão
de Cache para
Sistemas Móveis
Uma taxonomia para
esquemas de gestão
de cache
Broadcast de
relatórios de
invalidação
com estado: o servidor sabe qual o conteúdo da cache dos seus clientes
O ”polling-every-time”é semelhante ao TTL com o campo do TTL igual a
zero.
Nas duas primeiras estratégias é o cliente o responsável por manter a
consistência e na última essa função fica a cargo do servidor.
1.19
Problemas do esquema de invalidação
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Introdução
Desafios
Mobile Data Caching
Esquemas de Gestão
de Cache para
Sistemas Móveis
Uma taxonomia para
esquemas de gestão
de cache
Broadcast de
relatórios de
invalidação
1.20
Broadcast de relatórios de invalidação
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Introdução
Desafios
Mobile Data Caching
No esquema de ”broadcasting timestamp”proposto por Barbara and Imieliński
temos:
um servidor faz o broadcast de relatórios de invalidação: todas as
invalidações numa janela das últimas ω unidades temporais
um invalidação é um par da forma (id, ts) em que id é o identificador do
dado e ts é um ”timestamp”que indica quando é que o mesmo foi
alterado, ou seja, t − ω ≤ ts < t, em que t é o tempo em que o relatório
de invalidação foi enviado
Esquemas de Gestão
de Cache para
Sistemas Móveis
Uma taxonomia para
esquemas de gestão
de cache
Broadcast de
relatórios de
invalidação
1.21
Bibliography I
Computação Ubı́qua:
Gestão e Disseminação
de Informação
V. Nogueira
Introdução
Desafios
Mobile Data Caching
Esquemas de Gestão
de Cache para
Sistemas Móveis
F. Adelstein, S. K. S. Gupta, G. G. Richard III, and L. Schwiebert.
Fundamentals of Mobile and Pervasive Computing.
McGraw-Hill, 2005.
Uma taxonomia para
esquemas de gestão
de cache
Broadcast de
relatórios de
invalidação
1.22