Distribuição de Mídia Contínua
Replicacao de Conteudo
Jussara M. Almeida
Abril 2005
Onde Fazer Replicacao de Conteudo?
Rede
“Local”
Rede
“Local”
Servidor
Proxy
Servidor
Proxy
Servidor
Origem
Rede Remota
Servidor
Proxy
Rede
“Local”
Nos clientes: reduz jitter
Nos proxies: reduz latencia e demanda
por banda na rede e servidor
No servidor: reduz atraso e demanda por
banda do disco
Politica de Replicacao
•
Politica de insercao
–
•
Criterio para determinar se um novo conteudo
deve ser inserido no cache
Politica de remocao
–
Criterio para determinar qual objeto,
armazenado no cache, deve ser removido para
liberar espaco para novo conteudo
Politicas de Replicacao Tradicionais (Web)
•
Politicas de Insercao: tipicamente nao sao
explicitamente definidas, isto e, sempre insere
conteudo requisitado no cache.
–
•
Desastre em potencial para Midia Continua
Politicas de remocao
–
Least Recently Used (LRU):
•
–
Least Frequently Used (LFU):
•
–
Remove do cache conteudo menos recentemente
acessado para liberar espaco para novo arquivo
Remove do cache conteudo menos frequentemente
acessado para liberar espaco para novo arquivo
Variacoes (Greedy-Dual)
•
Leva em consideracao recencia, tamanho, custo, etc
Acessos a Objetos Pouco Populares
Numero de arquivos novos acessados
Somente 1 vez em cada hora:
tempo ate proximo acesso:
New Files
New Files Accessed Once
30
100%
Cumulative %
Number of Files
Unique Files
20
10
New Files Accessed Once
80%
60%
40%
20%
0%
0
7AM 11AM 3PM 7PM 11PM 3AM
Hour
1 2 4 8 16 32 64 128
Time Until Next Access (Hours)
Arquivo novo = arquivo nao acessado nas ultimas h horas
• Resultados similares para:
h  1,2,4,8, multiplos dias, ambos servidores, e segmentos no eTeach
• Armazenar todo arquivo que nao e encontrado no cache nao e boa ideia
Midia Continua: O Que Replicar?
• Arquivos inteiros
– Arquivos grandes, restricao de espaco
• Espaco e barato
– Interatividade
• Alguns trechos de um video sao mais populares
• Segmentos
– Qual o tamanho do segmento
• Camadas
– Codificacao em camadas
• Intervalos
– Entidade dinamica, refletem a recencia dos acessos
Intervalo
• Buffer circular com conteudo dinamico
S1
0

S2
T
S1
0
Tempo

T
S2
0
S1
Arquivo
f
T
i
S2
0
S1
i
T
Intervalo
• Tamanho do intervalo reflete recencia dos
acessos
– Menores intervalos, acessos mais proximos,
arquivo mais popular
• Demanda por banda de disco:
– Um fluxo escritor (preceding stream) e um
fluxo leitor (following stream)
• Demanda por espaco:
– Tempo entre acessos X bitrate do arquivo
Interval Caching (IC)
• Armazena os “menores” intervalos
– Objetivo: max # fluxos servidos do cache
– Se arquivos com bitrate diferentes
• Armazena intervalos com menor demanda por espaco
– Cada intervalo economiza um fluxo do disco (leitor)
– Se arquivos com bitrates iguais
• Armazena no cache blocos que serao utilizados de
novo no futuro mais proximo (LRU)
• Adaptacao dinamica a variacoes na carga
• Pouco efetiva se arquivo pequeno /interatividade
– Pequena prob. de multiplos acessos por playback
Generalized Interval Caching
(GIC)
• Extensao de IC para cargas heterogeneas
– Acessos a arquivos longos
– Acessos a pequenos clips / interatividade
• Arquivos longos:
– Multiplos acessos ao mesmo arquivo durante
playback
• Arquivos pequenos:
– Tipicamente, somente um acesso em andamento,
em um dado momento
GIC: Conceitos
• Intervalos: entre dois fluxos simultaneos
(arquivos longos)
– Tamanho do intervalo: tempo entre dois acessos
– Demanda por espaco:
tempo entre dois acessos X bitrate do arquivo
• Intervalos antecipados: tempo entre dois acessos
consecutivos
(fluxos nao simultaneos, arquivos pequenos)
– Tamanho do intervalo: tempo entre dois acessos
(estimado com base nos dois ultimos acessos)
– Demanda por espaco: tamanho do arquivo
(se decidir cachear, arquivo inteiro e armazenado)
Politica GIC
Politica GIC
• Ordena intervalos (reais ou antecipados) em
ordem de tamanho do intervalo
– Mesmo principio da LRU
• Armazena o maior numero de intervalos,
dado o espaco existente
Politica GIC
• Detalhes de implementacao (Figs 2 e 3 )
Politica GIC
• Detalhes de implementacao (Figs 2 e 3 )
– Mudancas na lista de intervalos ocorrem somente quando
da chegada ou termino de um novo fluxo: simplicidade
• E com operacoes de VCR?
Avaliacao da Politica GIC
• Simulacao (modelos analiticos sao dificeis)
• Carga: duas classes de objetos
– Arquivos longos (92 arquivos)
• Distribuicao de popularidade: Zipf (0.271)
• Tamanho: 90 mins ou 1 GB
– Clips (interactive workload)
• Popularidade: 80% acessos para 20% dos clips
• Tamanho do arquivo: uniforme (1-30 segs)
• Tempo de visualizacao: exponencial
media =30 segs (banners) e min= 5segs
• Duracao da sessao: 30 mins
Avaliacao da Politica GIC
• Interactive probability: prob de sessao de cliente
ser para clips
• Processo de chegada de clientes: Poisson
• Servidor:
– Memoria: sequencia de blocos
– Se nao faz caching: 2 blocos alocados para cada fluxo
• Resultados
Replicacao em Discos
• Replicacao em servidores proxy localizados mais
proximo dos clientes
– Rede entre proxies e servidor origem passa a ser o
gargalo (antes era disco)
• Arquivos grandes com demanda por espaco e
largura de banda
• Restricao de largura de banda ignorada por:
– Politicas de caching de blocos /arquivos em memoria
principal
– Politicas de caching de objetos Web em disco
Replicacao em Discos
• Politicas de caching tradicionais
– Algoritmos baseados na frequência (ex: LFU).
• Se comportam melhor para cargas que mantem um padrão
mais constante de acesso.
• Funcionam bem para mídia contínua.
• Não reagem bem a mudanças na carga.
– Algoritmos baseados na Recência (ex: LRU).
• Exploram a localidade de referência de um arquivo. Muito
sensível a mudanças temporárias na carga.
– Métodos Híbridos (LRFU, LRU-k):
• Algoritmos que exploram a recencia e freqüência.
Replicacao em Discos
• Interval Caching: boa ideia?
Desperdicio de 50% da banda do disco do
proxy:
Um escritor para cada leitor
Resource-Based Caching para
Midia Continua
• Objetivos:
– Tentar manter a utilização de banda e espaço
equivalentes. (“andar na diagonal do gráfico”)
Resource-Based Caching para
Midia Continua
• Objetivos:
– Replicar o conteúdo requisitado num futuro mais
próximo (recência).
– Ser um algoritmo de “replicação flexível”
(distribuindo diversos tipos de mídia) decidindo
em tempo real “o que replicar” de um determinado
arquivo.
– Permite a replicação de diferentes tipos de entidade
RBC – Entidade
• Uma entidade é uma unidade atômica de um
objeto que será armazenada na cache.
• Tipos de Entidade:
– Objetos estáticos: arquivos inteiros.
– Objetos dinâmicos:
• Armazenados em Intervalos (como no IC).
• Armazenados em Runs:
• Somente arquivos MC são armazenados desta
forma. Objetos não-MC são armazenados
inteiros e distribuidos com melhor-esforço.
Runs
Runs
• Run pode ser vista como a extensão do
intervalo em uma entidade única.
• Quando mais de dois usuários acessam o
mesmo arquivo concorrentemente pode ser
interessante compartilhar o escritor(wi)
• Cada run possui um escritor (wi) e diversos
leitores (ri) concorrentes.
RBC – Entidade
• Cada entidade possui demanda por recursos:
• Arquivo Inteiro:
–
–
= Tamanho do Arquivo.
= número estimado de requisições durante o playback.
• Intervalo:
–
–
• Run:
–
–
= di*bi, onde d = intervalo o acesso corrente e o último.
= (ri + wi)*bi => 2*bi.
= di*bi.
= (ri + wi)*bi.
RBC – Atributos da Entidade
• Caching Gain:
– BHR (Byte Hit Ratio): razão entre a
quantidade de bytes servidos pelo cache e
número total de bytes requisitados
– O HR (Hit Ratio): razão entre a quantidade de
acessos para arquivos presentes na cache pelo
número total de acessos.
RBC – Atributos da Entidade
• Goodness: usado para escolher qual
entidade sera retirada do cache
• Bw_goodness = gi/bi
• Space_goodness = gi/si
RBC – Seleção da Entidade
para entrar na Cache
• Seja Us = utilização de espaço e Ub = utilização
de banda
Se Ub > Us + e:
Escolher entidade com o
menor “overhead de escrita”
=> min(wi/(wi + ri))
Se Us > Ub + e:
Escolher a entidade com
menor tamanho => min(si)
Se |Us -Ub| < e:
Escolher entidade max
RBC – Seleção da Entidade
para entrar na Cache
• Seja Us = utilização de espaço e Ub = utilização
de banda
Se Ub > Us + e:
Escolher entidade com o menor “overhead de
escrita” => min(wi/(wi + ri))
Se Us > Ub + e:
Escolher a entidade com menor tamanho =>
min(si)
Se |Us -Ub| < e:
Escolher entidade max
RBC – Seleção da Entidade
para entrar na Cache
RBC – Algoritmo de Inserção
de Entidades na Cache
• Estados da Cache:
– Sem Restrição: banda e espaço excedem os requisitos
para a entidade sendo alocada. Neste caso a entidade
é colocada na cache.
– Restrição de Espaço: cache tem banda para alocar a
entidade mas não tem espaço livre suficiente.
– Restrição de banda: cache tem espaço para alocar a
entidade mas não tem banda livre suficiente.
– Restrição de banda de espaço: cache não tem espaço
nem banda livres para alocar a entidade.
RBC – Algoritmo de Inserção
de Entidades no Cache
If (
&&
If (
&&
)
If (
&&
)
If (
&&
)
– insert_in_cache(Ei);
– space_constrained-policy(Ei);
)
– bandwidth_constraint_policy(Ei);
– Bw_space_constrained_policy(Ei);
RBC – Algoritmo de Substituição
de Entidades no Cache
RBC – Algoritmo de Substituição
de Entidades no Cache
RBC - Detalhes de Implementação
• Estimativa do número de leitores:
– ri = (duração do arquivo)/(TTR)
• Calculando o Inter-arrival Time (TTR = 1/l*pi):
– Análise Estatística.
– Contador de Referência: Método baseado em frequência
(LFU). Pouco sensível a mudanças.
– Tempo de Acesso: Método baseado em Recência (LRU-k).
Sensível a mudanças. (LRU < LRU-k < LFU)
– Método utilizado: MTTR (híbrido).
– MTTR(t0) = (1 – a)(t0 – t1) + a*MTTR(t1)
» Aumenta a (recência)
» Diminui a (freqüência)
Experimentos: Carga
Utilizada
• Caracterização de carga utilizada:
– Baseado nos logs da NLANR, NCSA e NASA
– Distribuição dos Dados: Predominância de arquivos de
texto e imagens. (1% dos acessos para CM)
– Popularidade: Modelado com Zipf
– Tamanho dos objetos: Uniformemente distribuidos
com os objetos de não-CM sendo algumas ordens de
magnitude menor que os objetos do tipo CM.
Resultados dos Experimentos
• Comparação do RBC com diferentes tipos
de Entidade
– Teste com intervalo e arquivo inteiro:
• Banda restrita:
– Armazena mais arquivo inteiro
• Espaço Restrito:
– Armazena mais intervalo
– Testes utilizando runs, intervalos e arquivo
inteiro
• RBC utilizando runs foi melhor.
Resultados dos Experimentos
• Comparação do RBC com outros algoritmos.
– Quanto a BHR:
• RBC superior a LRU-2 (arquivos inteiros) e WLRU-n
(arquivos inteiros).
– Quanto a HR:
• RBC superior a LRU-2, WLRU-n e LRU-min.
• Comparação do RBC com variedade de
cargas:
– Foi comparado com o LRU-2, LRU-min e o WLRU-n.
– 80% de cargas não-CM e 20% de carga CM.
– O RBC foi superior.
Comentários Finais
• Observações sobre os gráficos:
– Gráficos e parâmetros não foram explicados.
– Valores muito fora da realidade para banda
e espaço.
– Inconsistência de dados.
• Complexidade do Algoritmo:
– Em nenhum momento do texto a
complexidade do algoritmo é discutida.
Caching Cooperativo
• Múltiplos proxies cooperam para atender
requisições de clientes
• Questões importantes:
– Protocolo de comunicação entre proxies
– Replicação independente ou não
• Múltiplas cópias de um mesmo objeto
• Uma única cópia do objeto
– Consistência entre cópias
– Balanceamento de cargas
Middleman : A Video Caching
Proxy Server
• Arquitetura distribuída com múltiplos
servidores proxy
– Rápida comunicação entre servidores
– LAN ou campus network
• Avaliação de diferentes políticas de
caching
• Projeto baseado no estudo de cargas
reais de video sob demanda na Internet
Observações em Cargas de
Vídeo Reais
• Tamanhos de vídeos variados
– Tamanhos de vídeos na Web em torno de 1MB,
mas tendência a crescimento
– Tamanho em rede de banda larga (Suécia) era
em torno de 96MB
– Sistema de cache tem que ser flexível
• Vídeos are WORM – write once read many
– Consistência do cache não é um problema
Observações em Cargas de
Vídeo Reais
• Padrões de acesso:
– 61% dos acessos foram para arquivos inteiros
– 39% pararam logo no início do vídeo
– Cache tem que permitir armazenamento parcial
de arquivos
• Alta localidade temporal nos acessos
– Caching é uma boa estratégia
Middleman:
Principais Componentes
• Dois componentes principais
– Coordenadores
– Servidores proxy
• Servidores proxy locais
• Servidores proxy de armazenamento
• Coordenador:
– Tipicamente um por sistema
– Mantém registro do que está armazenado em
cada proxy
– Toma as decisões de subsituição de conteúdo
do cache para o sistema inteiro
Middleman:
Principais Componentes
• Servidores proxy locais
– Responsáveis por atender requisições de clientes
– Podem rodar na mesma máquina do cliente
(browser plug-in)
– Alternativamente, podem rodar em máquinas
específicas do sistema, responsáveis por um conjunto
de usuários
• Servidores proxy de armazenamento
– Armazenam dados
– Não respondem a requisições de clientes
Middleman: Principais Componentes
• Proxy cluster: coleção de servidores proxy (locais
e de armazenamento) rodando em uma LAN e
organizados por um único coordenador
Vantagens:
• Redução da latência
• Grande quantidade de espaço
• Redução da carga
(servidor e proxies)
• Escalabilidade
Desvantagens:
• O Coordenador é um possível
gargalo e ponto único de falha
Middleman: Política de Caching
• Caching de blocos de arquivos
– Cada arquivo é segmentado em uma sequência de blocos
– Blocos são armazenados de forma independente,
possivelmente em servidores diferentes
– Possível atraso na troca de servidores para blocos
diferentes
– Blocos são armazenados à medida que forem
requisitados pelos usuários
– Blocos não requisitados não são armazenados
Middleman: Política de Caching
• Não tem política explícita para inserção de
conteúdo : sempre insere
– Problema em potencial
• Remoção de blocos de arquivos
– Aplica política para escolher qual arquivo deve ser
removido (ex: arquivo menos popular)
– Remove bloco por bloco, à medida que for necessário,
a partir do último bloco
(inspirado na caracterização de carga anterior)
Middleman:
Exemplo de Funcionamento
Funcionamento: Cache Miss
Cliente B1
requisita arquivo M
e a requisição é
interceptada pelo
servidor local LP1
Overhead de
comunicação entre
servidores proxy e
coordenador
Cancelamento de Requisição
• Cliente interrompe fluxo durante visualização de bloco M2
• Browser interrompe conexão com servidor proxy local (LP)
• Se requisição era cache hit, LP interrompe demais conexões
e informa coordenador
• Se requisição era cache miss: LP notifica coordenador
– Se este é o único usuário acessando o arquivo no sistema:
• Coordenador informa LP que ele pode interromper
demais conexões
• Todas referências a M2 são apagadas. M1 permanece
armazenado no sistema
– Se há outros usuários acessando o arquivo:
• Coordenador pede LP para continuar a baixar M2 e
salvá-lo em algum servidor proxy de armazenamento
Avaliação
• Simulação com traces de acesso a um servidor
educacional/entretenimento na Univ. Lulea
(Suécia)
– Traces cobrem 2 anos e 2 meses
– Carga muito baixa
• Cache size agregado, normalizado pela
quantidade total de dados
Políticas de Remoção de Conteúdo
• LRU, LFU, FIFO
• LRU-K
– Mantém um histórico dos últimos k acessos de cada
objeto no cache
– Remove o último bloco do arquivo com a maior kdistance
– A k-distance de um arquivo em um dado instante é a
diferença entre o tempo corrente e o instante em que
o k-esimo acesso foi realizado
• HistLRUpick:
– Roda LRU-k e desempata escolhendo bloco do servidor
menos carregado
– Balanceamento de carga
Políticas de Remoção de Conteúdo
• LRU, LFU, FIFO
• LRU-K
– Mantém um histórico dos últimos k acessos de cada
objeto no cache
– Remove o último bloco do arquivo com a maior kdistance
– A k-distance de um arquivo em um dado instante é a
diferença entre o tempo corrente e o instante em que
o k-esimo acesso foi realizado
• HistLRUpick:
– Roda LRU-k e desempata escolhendo bloco do servidor
menos carregado
– Balanceamento de carga
Byte Hit Ratio
Balanceamento de Carga entre
Proxies
Codificação em Camadas
Hierárquica
• Hierarchical Layered Encoding
– Fluxo dividido em n camadas
– Camada básica fornece um mínimo de qualidade
– Camadas superiores provêm melhorias de qualidade
– Camada i só é útil na presença de camadas 0,1, …, i-1
• Útil para clientes heterogêneos
– Cliente com banda larga deseja receber fluxo
de alta qualidade
Protocolo Cliente-Servidor para
Adaptação de Qualidade
• Fluxos codificados em camadas
• Servidor e cliente realizam controle de
congestionamento
– Protocolo RAP
– Taxa de transmissão muda dinamicamente em função da
banda disponível
– Número de camadas adaptado dinamicamente
Adicionando Proxy Cache
• Proxy realiza controle de congestionamento com
servidor e com clientes
– Qualidade de um fluxo armazenado no cache depende
da banda disponível entre servidor e primeiro cliente
– Ajuste de qualidade de grão fino
• Camadas divididas em segmentos de tamanho fixo
– Camadas superiores são gradualmente armazenadas no
cache para melhorar a qualidade
Política de Caching
• Baseada em prefetching de segmentos sob demanda
– Explora variações na popularidade dos arquivos e
limitações de banda dos clientes interessados
• Política de substituição apenas (sempre insere)
– Substituição na granularidade de segmentos
• Suporta interatividade (parcialmente)
• Minimiza latência inicial
• Qualidade de um fluxo transmitido a um cliente não
é limitada à banda disponível no servidor origem
– Proxy “esconde” gargalos no caminho entre proxy e origem
Cache Miss
• Proxy intercepta requisição e repassa ao servidor
• Conteúdo é enviado do servidor ao cliente pelo proxy
– Proxy armazena conteúdo localmente
– Como servidor realiza adaptação de qualidade, conteúdo
armazenado tem qualidade variada
Cache Hit
• Proxy deve realizar controle de congestionamento e
adaptação de qualidade
– Se banda com cliente maior que qualidade do fluxo
armazenado, proxy deve enviar segmentos que não
existem no cache
– Prefetching sob demanda, em resposta a novas requisições
pelo mesmo conteúdo : explora popularidade do arquivo
– Proxy realiza prefetching de segmentos faltantes de
camadas parcialmente armazenadas e também de camadas
superiores (adição de novas camadas)
Prefetching
Prefetching
• Quando realizar o prefetching de um segmento
faltante?
– Quanto antes, maior a chance de recebê-lo a tempo, mas
menos precisa é a estimativa da qualidade
• Janela de prefetching
– No instante tp de visualização, proxy examina o intervalo
[tp+T, tp+T+] e identifica os segmentos faltantes das
camadas no cache bem como novas camadas
– Proxy envia UMA requisição de prefetching ao servidor
com todos os segmentos faltantes
– Servidor envia segmentos em ordem de prioridade
– Novas requisições de prefetching preemptam requisições
em tratamento
Prefetching
Política de Substituição de
Conteúdo do Cache
• Objetivo: convergir para estado eficiente do cache
• Estado do cache é eficiente se:
– Qualidade média de qualquer fluxo no cache é
diretamente proporcional à sua popularidade.
• Qualidade média de um fluxo deve convergir para banda média dos
últimas transmissões para clientes interessados
– Variação na qualidade de qualquer fluxo no cache é
inversamente proporcional à sua popularidade
• À medida que a popularidade de um fluxo
correntemente no cache diminui, sua qualidade e seu
tamanho (no cache) são reduzidos, até ser
completamente removido do cache
Padrões de Remoção de Conteúdo
• Escolhe a camada mais superior como vítima da remoção
– Utiliza função de popularidade
• Remove segmentos da camada vítima, do último para o
primeiro
– Evitar fragmentação
– Manter prefixo para redução de latência inicial
• Se necessário, escolhe nova camada e repete processo
• Primeiros segmentos da camada básica são mantidos no
cache: esconder latência inicial de requisições futuras
Prioridade para Remoção
dentro de um Fluxo
Função de Popularidade
• Weighted hit: mantido para cada camada de cada
fluxo
– Whit = PlaybackTime / StreamLength
– 0  whit  1
• Whit de uma sessão calculado ao final da mesma
• Índice de popularidade de um arquivo: valor
acumulado do whit durante uma janela recente
• Interatividade capturada de forma restrita
Função de Popularidade: exemplo
Mecanismo de travamento
• Enquanto um fluxo está sendo transmitido para um
cliente, suas camadas no cache são travadas
(locked), não podendo ser removidas
• Evita remoção de segmentos finais da camada i para
inserção de segmentos iniciais da camada i+1
Avaliação
• Simulação para mostrar correção do mecanismo
– Cache atinge estado eficiente
• Não avalia desempenho da política
– Experimentos simples
• Métricas
– Completeza: % dos fluxos residindo no cache
– Continuidade: tamanho médio das sequências de
segmentos consecutivos no cache
• variação dos fluxos no cache
Resultados
• Mecanismo de prefetching
– Cache size = infinito (sem substituição)
– BW servidor-proxy = 56 Kbps
– BW proxy-cliente = 1.5 MBs
– Figura 9
• Convergência mais rápida para camadas mais básicas
Resultados
• Política de substituição de conteúdo
– Cache size = 50% dos dados
– BW servidor-proxy = 56 Kbps
– 2 clientes : cliente 1 = 1.5 MBps e cliente 2 = 56 Kbps
– Cenário 1: 95% requisições de cliente 1
• Figuras 10 e 11
– Objetos mais populares têm mais camadas no
cache, e estas camadas têm melhor qualidade
(completeza e continuidade)
– Cenário 2: 95% requisições de cliente 2
(banda do cliente limitada)
• Figuras 12 e 13