Web Caching with
Consistent Hashing
Problemas com a Web
Redes congestionadas
 Servidores atolados

Web Caching
Utilizar conteúdo de um servidor
intermediário ao invés de utilizar o
conteúdo do servidor original
 Implementações Tradicionais

Cache centralizado
 Cache centralizado cooperativo
 Cache hierárquico
 Diretório

Hashing





Mapeia endereços diretamente para
máquinas cache
Não há necessidade de dados duplicados
Não há necessidade de servidores
centralizados
Não há necessidade de comunicação
entre as máquinas cache
Porém a utilização de uma função hash
padrão não suporta servidores dinâmicos
Consistent Hashing





Utilização de uma função (f) hash normal
[0,M]
Divide-se o valor obtido pela função pelo
seu valor máximo (M) [0,1]
É formado o círculo unitário
Cada cache é associado a um ponto no
círculo unitário
Cada endereço é associado ao cache que
esteja localizado no círculo unitário mais
próximo dele caminhando no sentido
horário
Consistent Hashing
Consistent Hashing
Pode ser implementado utilizando
uma árvore binária
 Tempo médio de busca para n
caches é O(log(n))
 Lógica de busca fica no browser


Ou no DNS, que acabou sendo a
solução escolhida
Propriedades




Para m máquinas cache e c clientes (com
cada com a visão de metade das máquina
cache)
Balanço: Em qualquer visão, os
endereços estão distribuídos
uniformemente sobre as máquinas caches
Carga: Em todas as visões, nenhuma
máquina tem mais do que O(log(c)) vezes
em média o número de endereços
Espalhamento: Nenhum endereço é
armazenado em mais do que O(log(c))
caches
Consistent Hashing

Resultados para 26804 endereços
diferentes:
Caches
# médio de Desvio
endereços
padrão
por cache
Desvio
padrão
como % da
média
3
8934
246
2.5
5
5360
173
3.2
8
3350
112
3.4
10
2680
68
2.6
Implementação
Apesar de parecer bastente simples
implementar Consistent Hashing, os
browsers atuais não provêm bons
mecanismos de extensão
 Solução híbrida utilizando JavaScript
+ DNS (Cache Resolver)

Implementação

Parte JavaScript:


Realiza um hash padrão sobre o
endereço mapeando-o para um
intervalo de 1000 nomes de caches
virtuais
Parte DNS:

Mapeia uma cache virtual para um
endereço IP físico utilizando Consistent
Hashing
Implementação
Foi utilizado BIND 8.0 sem
modificações
 Em conjunto com BIND, um
processo chamado dnshelper
monitora os caches e envia sinais
para o BIND notificando-o sobre
novos endereços mapeados

Consistent × Central
Consistent × Cooperative
Consistent × Cooperative
Extensões

Localidade



Balanceamento de Carga Avançado



Mecanismo para clientes utilizarem caches
geograficamente mais próximos
Utiliza o serviço DNS em duas camadas
Identifica as Hot Pages
Utiliza DNS para referenciar Hot Pages para
vários caches diferentes
Tolerância a Falhas

A implementação de Consistent Hashing já é
bastante tolerante a falhas
Conclusão



Caching é uma solução para os problemas
de tráfego enfrentados pela Web
Consistent Hashing é uma alternativa
simples e eficiente para implementar
caching
O uso eficiente de caching e consistent
hashing pode aumentar
significativamente a eficiência da Web
Como vender isso?
Venda caching para os servidores,
não para os clientes
 www.akamai.com
