Um framework para a gerência de cache de
Banco de Dados Móvel: Design and
Avaliação
Yuri A. Lacerda
Cronograma






Introdução
Mecanismo de Caching
Caching Convencional
Caching Móvel
Conclusão
Referências
Introdução


Em um ambiente móvel os servidores de
banco de dados enviam informações via
wireless para diversos clientes.
Clientes móveis podem possuir perfis
variados: notebooks, palmtops, celulares,
etc.
Introdução
Database Server
Mobile Client
Mobile Client
Mobile Client
Rede Wireless
Introdução

Canal de transmissão wireless:
–
–

Baixa largura de banda;
Instabilidade na conexão;
Motivam:
–
Armazenar itens mais acessados do banco de
dados em um cache no cliente móvel:


Aumentar o desempenho ao realizar consultas
Prover disponibilidade mesmo desconectado
Mecanismo de Caching



Granularidade
Estratégia de Coerência
Políticas de Substituição
Mecanismo de Caching

Granularidade:
–
Unidade que será armazenada no cache:



Página
Objeto
Atributo
Ex: Mobile Client
Cache:
Cliente c_a;
Cliente c_c;
Mecanismo de Caching

Estratégia de Coerência
–
–
Invalidar os itens que estão incoerentes no cache
Atualizar os itens inválidos
Mecanismo de Caching

Estratégia de Coerência
Client A
Database Server:
Query q1
Client B
Database:
Cliente = {
c1 ( ‘João’, ‘Rua a’);
c2 ( ‘Maria’, ‘Rua b’); }
Mecanismo de Caching

Estratégia de Coerência
Client A
Database Server:
Cache:
c_c1 ( ‘João’,
‘Rua a’);
Client B
return q1;
Database:
Cliente = {
c1 ( ‘João’, ‘Rua a’);
c2 ( ‘Maria’, ‘Rua b’); }
Mecanismo de Caching

Estratégia de Coerência
Client A
Database Server:
Cache:
c_c1 ( ‘João’,
‘Rua a’);
Client B
Update c1
Database:
Cliente = {
c1 ( ‘João’, ‘Rua C’);
c2 ( ‘Maria’, ‘Rua b’); }
Mecanismo de Caching

Estratégia de Coerência
INCOERENTE!
Client A
Database Server:
Cache:
c_c1 ( ‘João’,
‘Rua a’);
Client B
Database:
Cliente = {
c1 ( ‘João’, ‘Rua C’);
c2 ( ‘Maria’, ‘Rua b’); }
- Que estratégia usar para corrigir este problema?
Mecanismo de Caching

Políticas de Substituição
–
O tamanho do cache é limitado
Client A
Database Server:
Cache:
c_c1 ( ‘João’, ‘Rua a’);
c_c3 ( ‘Maria’, ‘Rua m’);
c_c4 ( ‘José’, ‘Rua j’);
Query q
Mecanismo de Caching

Políticas de Substituição
–
O tamanho do cache é limitado
Client A
Database Server:
Cache:
c5 ( ‘Francisco’, ‘Rua f’);
c_c1 ( ‘João’, ‘Rua a’);
c_c3 ( ‘Maria’, ‘Rua m’);
c_c4 ( ‘José’, ‘Rua j’);
ESTÁ CHEIO!
Mecanismo de Caching

Políticas de Substituição
–
O tamanho do cache é limitado
Client A
Database Server:
Cache:
c5 ( ‘Francisco’, ‘Rua f’);
c_c1 ( ‘João’, ‘Rua a’);
c_c3 ( ‘Maria’, ‘Rua m’);
c_c4 ( ‘José’, ‘Rua j’);
ESTÁ CHEIO!
- Qual item substituir?
Caching Convencional

Banco de Dados Cliente / Servidor
–
–

Tráfego é comparado ao acesso ao disco
Diminuir latência da rede
Granularidade
–
–
–
Mecanismo de cache é baseado em Páginas
Servidor também é baseado em Páginas
Princípio da Localidade

–
Vizinhos serão acessados num futuro próximo
Overhead compensa se vizinhos forem
acessados num futuro próximo
Caching Convencional

Por que não aplicar a MDS?
–
–
–
Alta perda de energia (Baterias)
Overhead devido a pequena largura banda
Espaço de armazenamento pequeno
Caching Convencional

Estratégia de Coerência
–
–
O servidor possui conhecimento do cache de
cada cliente e envia mensagem quando um item
base é atualizado
Atualização do cache em cada cliente
Caching Convencional

Estratégia de Coerência
Local
Network
Client A
Database Server:
Cache:
c_c1 ( ‘João’,
‘Rua C’);
Database:
Cliente = {
c1 ( ‘João’, ‘Rua C’);
c2 ( ‘Maria’, ‘Rua b’); }
Client B
Update c1
Caching Convencional

Estratégia de Coerência
Local
Network
Client A
Database Server:
Cache:
c_c1 ( ‘João’,
‘Rua C’);
Client B
Refresh
Database:
Cliente = {
c1 ( ‘João’, ‘Rua C’);
c2 ( ‘Maria’, ‘Rua b’); }
Caching Convencional

Por que não aplicar a MDS?
–
–
Clientes trafegam livremente
Servidor pode não estar capaz de enviar
mensagem para todos
Database Server:
MC 2
Cache:
c_c1 ( ‘João’,
‘Rua a’);
Database:
Cliente = {
c1 ( ‘João’, ‘Rua C’);
c2 ( ‘Maria’, ‘Rua b’); }
wireless
Cache:
c_c1 ( ‘João’,
‘Rua a’);
Caching Convencional

Estratégia de Coerência
–
Solução Leases [2]



Cada item no cache possui um refresh-time préestabelecido
Ao expirar o item é atualizado
Que valor utilizar?
–
Muito Alto: Pode ter itens desatualizados
– Muito Baixo: Atualizações e muito tráfego desnecessários

Deveria ser adaptado automaticamente.
Caching Convencional

Políticas de Substituição
–
Algumas soluções existentes

Least Recently Used (LRU);
–





LRU-k
Least Reference Density (LRD);
Optimal;
CLOCK;
WORST;
Entre outras
Caching Móvel - Modelo

Sequência
Database
server (S)
Identificados todos os
itens qualificados (I)
Avaliação da
Query
Envio de Q
para o servidor
Mobile
client (S)
Envio de i
para o servidor
(I – i)
Itens
qualificados
para serem
enviados para o
cliente
Avaliação da
Query
Início da
Query (Q)
Identificados
itens locais
qualificados
(i)
Identificados
todos os itens
qualificados
Políticas de Substituição
Caching Móvel - Modelo


Paradigma ponto-a-ponto
Banco de Dados Orientado a Objetos
–
Não impede que se use para Relacional
Caching Móvel - Modelo

Cache Table
–
É um mini banco de dados que pode ser manipulado pelo
servidor.
– Estrutura:
Database server
X
attribute a
attribute b
attribute c
Mobile client
Remote
(R_oid,R_host)
Cache
X
C_X
attribute c_a
method a()
method b()
method c()
attribute c_b
attribute c_c
substituto x
Caching Móvel - Modelo

Granularidade
–
–
–
Caching de Atributo
Caching de Objeto
Caching Híbrido
Caching Móvel - Modelo

Caching de Atributo
–
–
O servidor só retorna para o cliente aqueles
atributos que foram requisitados
Exemplo:
Select x.name, x.city
from x in Places to Stay
where x.vacancy > 0
Consulta retorna dois objetos: x e y
Caching Móvel - Modelo
CACHE
c_vacancy
Places To Stay
Substituto x
Caching Móvel - Modelo
Server
CACHE
c_vacancy
Places To Stay
Substituto x
x.name
x.city
y.name
y.city
y.vacancy
Caching Móvel - Modelo
Server
CACHE
c_vacancy
Places To Stay
Substituto x
x.name
x.city
y.name
y.city
y.vacancy
Caching Móvel - Modelo
Server
CACHE
c_name
c_city
c_vacancy
Places To Stay
Substituto x
Substituto y
Caching Móvel - Modelo

Caching de Objeto
–
–
Clientes móveis tendem a ter os objetos
acessados mais frequentemente
Possuir todo o objeto pode evitar futuros acessos
no servidor
Caching Móvel - Modelo

Caching Híbrido
–
–
Armazena apenas os atributos de um objeto
qualificado com uma grande probabilidade de ser
acessado futuramente;
Probabilidade de Acesso Futuro ao Objeto >
Threshold E
Caching Móvel

Coerência de Cache
–
–
–
Cada cliente é responsável por se invalidar
Mesma estratégia de Leases, Refresh Time (RT),
unido a heurísticas
Cada item tem seu RT baseado na probabilidade
de ser atualizado:


Caching de Atributo e Caching Híbrido: Atributos com
RT.
Caching de Objeto: Objeto com R.T.
Caching Móvel

Estimativa do RT
–
–
–
–
–
X: item do cache
dx: duração da inter-chegada entre escritas
dx: média de Dx
Sx: desvio padrão
βx: frequência de atualização de x
RT = dx + βx.Sx
W(x)
W(x)
W(x)
W(x)
W(x)
t
0
5
10
15
20
25
30
35
W(X) = Write (X)
Caching Móvel

Erro
W(x)
Servidor
t
Refresh(x)
t
Cliente

False Alarm
t
Servidor
Refresh(x)
Cliente
Não houve escrita!
Refresh(x)
t
Caching Móvel

Políticas de Substituição
–
Mean


Armazena a média de acesso de cada item
Problema: Não descobre a mudança rapidamente
A(x)
A(x)
A(x)
A(x)
A(x)
t
0
5
10
15
20
25
30
35
A(X) =Acessa (X)
Média de todos os acesso de cada item
Caching Móvel
–
Window


Armazena uma janela dos valores inter-operações
Problema: Necessita armazenar uma janela para cada
objeto ou atributo
A(x)
A(x)
A(x)
A(x)
A(x)
t
0
5
Janela:
10
15
10 5
10 5
20
25
30
35
A(X) =Acessa (X)
Média dos últimos acessos
Caching Móvel
–
Exponentially Weighted Moving Average


Resolve o problema da janela
Adiciona pesos aos valores inter-operações
Simulações


Não foram exaustivos
Perfil do comportamento:
–
Granularidade

Caching Híbrido possuiu desempenho superior:
–
Alta taxa de acertos
– Baixo tempo de resposta
– Baixa taxa de erros
– Baixo taxa de alarmes falsos
Caching Móvel
–
Políticas de Substituição


EWMA-0.5 desempenho bastante estável em
diversos cenários;
LRU, LRU-3 e LRD também possuíram um
desempenho satisfatório para alguns cenários.
Conclusões




Proposto um mecanismo para prover
desempenho
Caching baseado em paginas não é
adequado
Foi proposto um caching baseado em
atributos, objetos ou híbrido.
Estratégias de coerências e políticas de
substituição que se adaptam a forma de
acesso
Referências
[1] B. Y. Chan, A. Si, H. V. Leong, “A Framework for Cache
Management for Mobile Databases: Design and Evaluation.
2001.
[2] C.G. Gray and D.R. Cheriton, “Leases: An efficient fault-tolerant
mechanism for distributed file cache consistency,” in
Proceedings of SOSP, 1989, pp. 202–210.