Lendo dados temporais
de forma consistente em
Broadcast Disks
José Flávio M. V. Júnior
Baseado no artigo: Reading Temporally Consistent
Data in Broadcast Disks, Victor C. S. Lee, Joseph K.
Ng, Jo Y. P. Chong, Kwork-Wa Lam
Sumário








Introdução
Conceitos relacionados
Protocolos de controle de concorrência
Protocolo BCC-TI
Variações do Protocolo BCC-TI
Experimentos
Resultados
Conclusões
Introdução

Muitas aplicações para dispositivos móveis
possuem restrições de tempo para transações e
dados





Informações sobre bolsa de valores
Condições do tempo
Tráfego nas estradas
Os dados podem se tornar inválidos com o passar
do tempo;
Para refletir o estado atual do mundo real, os dados
devem ser periodicamente atualizados.
Introdução



Transações devem ler dados temporais
consistentes a fim de produzir resultados
corretos;
Os dados devem estar suficientemente
atualizados;
As transações devem ser completadas em
tempo hábil;
Introdução

Em ambiente de broadcast é mais difícil
manter a consistência dos dados;


pode levar tempo para as versões mais recentes
dos dados alcançarem os clientes;
dificulta a confirmação das transações


a validade dos dados expiram;
Protocolos especias foram desenvolvidos;
Conceitos relacionados

Broadcast Disks




Uma abordagem cliente-servidor para ambientes
móveis;
Explora a vantagem de largura de banda do
servidor para transmitir dados para múltiplos
clientes através de difusão;
Continuamente e repetidamente transmite dados
para os clientes;
O canal utilizado para broadcast se torna um
disco em que os clientes podem recuperar dados
enquanto se movem;
Conceitos relacionados

Broadcast Disks
Conceitos relacionados

Dado temporal

Dado temporal possui informação temporal
associada a cada nova versão


É atualizado periodicamente para refletir o estado
atual do mundo real
Dado não temporal não existe nenhuma restrição
sobre o tempo

Pode ser escrito aperiodicamente
Conceitos relacionados

Consistência Temporal


O valor atual de um item de dado do ambiente deve ser
próximo o bastante do valor armazenado no banco de
dados;
Mecanismos para verificação de consistência temporal
baseados em:
 rótulo de tempo (timestamp): indica o tempo


quando o valor do dado foi gravado;
controle de versão (versioning): a idade e
dispersão da idade dos dados;
intervalo de validade absoluta (avi): por quanto
tempo o valor do dado é válido;
Protocolos de controle de
concorrência


A consistência do banco de dados pode ser
violada quando ele é acessado
concorrentemente;
Abordagem comum baseada em locking é
impraticável


Requer comunicação bi-direcional;
Sobrecarga de requisições de lock.
Protocolos de controle de
concorrência

Optimistic concurrency control (OCC)




Evita o reinicio das transações pelo atraso na
resolução de conflitos;
Transações podem executar até o ponto de
commit;
Elevado consumo de largura de banda dos
clientes;
Possui variantes (OCC-BC, OCC-FC, OCC-TI,
entre outras).
Protocolos de controle de
concorrência

Optimistic concurrency control with broadcast commit
(OCC-BC);
 As transações podem ser processadas sem espera
na fase de leitura;
 Somente o conjunto de operações de escrita é
verificado;
 Quando uma transação é confirmada, uma verificação
é executada frente as outras transações ativas para
determinar se houve conflitos;
Protocolos de controle de
concorrência

OCC-BC
 Se uma transação Ti ativa leu dados escritos pela
transação em validação, Ti é reiniciada;
 As transações de somente leitura (ROT) não
precisam ser verificadas;
 As ROTs podem fazer commit de forma
independente;
 Sofre com o reinicio tardio das ROT;
Protocolos de controle de
concorrência

Datacycle



Ler todos os dados em um único ciclo;
Durante a execução das transações de leitura o
stream é escaneado;
É muito caro em termos de conexão.
Protocolo BCC-TI




Broadcast concurrency control using
timestamp interval (BCC-TI);
Oferecer autonomia entre clientes móveis e
servidores;
Leitura de dados consistentes sem contatar o
servidor;
Reduzir o número de reinícios
desnecessários das transações.
Protocolo BCC-TI

A idéia básica:



Ajustar dinâmicamente a posição (ordem de
serialização) das ROTs;
Intervalo de tempo (timestamp) é associado a
cada ROT;
O conflito de dados é verificado pelo fechamento
do intervalo;
Protocolo BCC-TI

Do lado do servidor:




Armazena informações das transações de
atualização;
Possui uma estrutura de dados chamada control
information table (CIT);
A CIT é transmitida periodicamente pelo servidor,
junto com os dados;
O tamanho das informações de controle é
proporcional ao número de itens de dado
atualizados no último ciclo.
Protocolo BCC-TI

Do lado do servidor:



Para todo objeto de dado d o servidor armazena
junto o último timestamp de gravação WTS(d);
Registra na CIT o timestamp TS(U) quando a
transação é confirmada;
As operações de escrita WS(U) também são
armazenadas na CIT;
Protocolo BCC-TI

Do lado do cliente:




Quando ele inicia uma ROT um intervalo de
tempo é associado;
Limite inferior (LB) e limite superior (UB);
O intervalo é ajustado para induzir a ordem serial
das transações de leitura (ROT) e de atualização
(WT).
A CIT e o WTS(d) são utilizados;
Protocolo BCC-TI

Ajustando o intervalo de tempo de uma transação ROT
 O cliente lê a tabela de controle (CIT)
1.
2.

UB(Q) = mini ( TS(Ui), UB(Q) )
Se LB(Q) >= UB(Q) a transação é reiniciada;
Quando a transação Q ler o objeto de dado d os seguintes
passos são executados:
1.
2.
LB(Q) = max( LB(Q), WTS(d) )
Se LB(Q) >= UB(Q) a transação é reiniciada;
Protocolo BCC-TI

Primeiro ciclo de transmissão
WTS(z) = 3
Z
WTS(y) = 3 WTS(x) = 3
Y
WS(U) = {}
X
RS(Q) = {x, y, z}
Protocolo BCC-TI

Segundo ciclo de transmissão
WTS(y) = 3
X
Y
WTS(x) = 5
WTS(z) = 5
Z
WS(U) = {x, z} RS(Q) = {x, y, z}
Protocolo BCC-TI

Apenas um tipo de conflito pode acontecer
entre ROT e WT
WS(U) ∩ RS(Q) != {}

A ordem de serialização deve ser Q → U
Protocolo BCC-TI

O custo desses benefícios


manter e fazer broadcast da CIT;
gerenciamento de intervalo de tempo;

pode ser feito através de uma tabela de transações
nos clientes
Variações do Protocolo BCC-TI

BCC-TI com controle de versão
(Versioning)



Objetos de dados temporais são tratados de
forma diferente;
Um número de versão é associado ao objeto de
dado temporal;
Utiliza limiar absoluto e relativo para definir a
consistência temporal dos dados;
Variações do Protocolo BCC-TI

BCC-TI com controle de versão
(Versioning)

Consistência absoluta:
at(x) <= A (A >= 0), onde A é o limiar absoluto

Consistência relativa:

Dada sobre a dispersão temporal dos dados:
dt(x, y) = | at (x) - at (y) |
dt(x, y) <= R (R >= 0) , onde R é o limiar relativo
Variações do Protocolo BCC-TI

BCC-TI com intervalo de tempo válido
(TVI)



objetos de dados temporais são tratados de
forma diferente;
um intervalo de tempo é associado ao objeto de
dado temporal (data deadline);
se o deadline do dado for perdido uma
inconsistência temporal é detectada e a
transação é reiniciada;
Experimentos

Os seguintes protocolos foram
analisados






Datacycle
Puro BCC-TI
BCC-TI Versioning 0
BCC-TI Versioning 1
BCC-TI Versioning 2
BCC-TI TVI
Experimentos
Experimentos


300 objetos de dados sendo 30 dados
temporais
Cada objeto de dado possui igual chance de ser
acessado;
Experimentos

Avaliação do desempenho

Os principais números avaliados:



miss rate: % de transações que perderam seus
deadlines
restart rate: número médio reinicio de transações
transaction response time: tempo decorrido do início
até o final da transação
Resultados
D
TVI
V0
D
TVI
V0
P
P
V1
V1
V2
Gráfico 1: Taxa de perda de
transações
V2
Gráfico 2: Média de reinício
de transações
Resultados
TVI
P
V0
P
D
V1
V2
V1
V2
V0
TVI
Gráfico 3: Tempo de resposta
Gráfico 4: Taxa de reinício por
inconsistência nos dados
Resultados
TVI
V0
V1
V2
Gráfico 5: Taxa de reinício por
inconsistência temporal
Conclusões



O ajuste dinâmico reduz significativamente o
número de reinícios das transações;
Em particular, o desempenho desses
protocolos melhoram quanto menos severa é
a restrição temporal;
Os requisitos de consistência temporal e a
semântica dos dados podem melhorar o
desempenho do sistema;
Bibliografia

Victor C. S. Lee, Joseph K. Ng, Jo Y. P. Chong, Kwork-Wa Lam:
“Reading temporally consistent data in broadcast disks”,
2004.

Victor C. S. Lee, Kwok-Wa Lam, and Sang H. Son.
“Concurrency control using timestamp ordering in
broadcast environments”. The Computer Journal, 2002.

Sanjay Kumar Madria and Mukesh Mohania. “Mobile data and
transaction management”. Inf. Sci. Inf. Comput. Sci., 2002.

Swarup Acharya, Rafael Alonso, Michael Franklin, and Stanley
Zdonik. "Broadcast Disks : Data Management for
Asymmetric Communication Environments"