BT

Caches LRU de Alto Desempenho: a experiência do eBay, em detalhes

Postado por Reinaldo Braga em 11 Out 2011 |

Seguindo a atual tendência de criar soluções simples, sem a utilização de técnicas ou frameworks complexos, para conseguir o suporte a grandes volumes de transações, a equipe do eBay criou uma solução de cache LRU, em Java, e a descreveu detalhadamente em seu blog de tecnologia.

O eBay é hoje o maior "mercado" digital da internet, com centenas de milhões de listas ativas a qualquer hora do dia. Para manter esse mercado funcionando a empresa enfrenta desafios técnicos nada convencionais. A utilização de cache nesse ambiente de milhares de transações por dia tem especial relevância.

O uso de cache é uma ferramenta útil para diminuir gargalos e garantir bom desempenho, até mesmo para casos de falha, e o modelo de cache definido pelo eBay traz a vantagem de que, mesmo com grande volume não foi necessário implementar semáforos ou objetos e métodos synchronized.

A solução de cache do eBay

A estrutura descrita por Mathias Spycher, engenheiro do eBay, consiste em um ConcurrentHashMap, no qual as entradas encapsulam o valor juntamente com uma referência. Esta refrerência aponta para uma lista duplamente ligada (em que cada nó tem uma referência para o nó anterior e o posterior), que armazena o cache LRU (LRU=Menos Recentemente Usado). O início da lista contém os itens menos frequentemente utilizados e o final, os mais utilizados. A imagem abaixo extraída do blog do eBay, resume a estrutura.

 

Estas são as operações que podem ser feitas no cache:

  • get : Pesquisa o item através da chave fornecida
  • load: Carrega o valor no cache a partir de uma fonte de dados
  • put: Cria uma nova entrada e coloca a chave no ConcurrentHashMap
  • offer: Adiciona um novo nó ao final da lista de cache LRU (least recently used, ou usado mais recentemente) onde ficam as entradas acessadas recentemente
  • evict: Remove nós do topo (head) da lista LRU e as entradas associadas ao ConcurrentHashMap (somente quando a lista LRU atinja um determinado tamanho)
  • purge: Apaga os nós marcados para exclusão da lista LRU; são os menos acessados recentemente e que, no algoritmo, vão sendo adicionados para uma lista ligada paralela à lista LRU, para facilitar esse processo de exclusão. Esta última lista foi chamada de hole (furo).

No processo de pesquisa de um valor pela chave, o cache primeiro verifica o ConcurrentHashMap (chamado de "mapa" adiante), e caso o valor não esteja presente, dispara a função load() e coloca o valor no mapa através do método putIfAbsent(). O objetivo principal é manter o cache LRU consistente, pois o processo de adicionar ao mapa é mais controlado e extensível, por ser particionado.

A lista LRU usada para cache, porém, não pode ser particionada, pois isso causaria problemas de inconsistência. Para conseguir o desempenho necessário foi introduzida uma segunda lista para manter os itens que vão ser excluídos quando o purge é chamado. A segunda lista é chamada hole, e tem esse nome pois as entradas dos nós que são adicionados nessa lista são limpas (atribuídas um valor nulo), dando a impressão de "buracos" dentro da lista LRU.

A operação evict() é sempre feita em bloco para garantir o desempenho. É chamada pelo purge, o que é feito por uma única thread, evitando a necessidade de semáforos e locks. O pseudocódigo abaixo, no post do eBay ilustra o funcionamento da operação get():

get(kChave) -> vValor

pesquisamos a entrada pela chave kChave
se existir, então temos a entrada ent
  chamamos o offer() com a entrada ent
  chamamos o purge() para eliminar entradas na lista hole, caso seja necessário,
senão
  carregamos o valor vValor para a chave kChave
  criamos a entrada ent <- (kChave,vValor)
  chamamos o put() para a entrada ent
fim
retorna valor ent.val

Na operação get(), se a chave existir, a operação offer() é chamada, incluindo um novo nó no fim da lista do cache. Note, porém, que por estarmos em um ambiente de concorrência só podemos garantir que o nó que acabou de ser inserido é um dos mais recentes; mas não exatamente o mais recente, pois a operação não é atômica e não faz o lock da lista.

Veja o pseudocódigo para a operação put(ent):

put(ent) -> ent

existindo a entrada xEntrada <- map.putIfAbsent(entrada.key, ent)
se não encontrada
  chamar offer() com a entrada ent;
  se o tamanho atingir o limite para remoção
     chamar evict() para algumas entradas
  fim
  retorna entrada ent
senão, temos uma entrada existente xEntrada
  retorna entrada xEntrada
fim

Uma ou mais threads podem competir ao chamar a operação put(), mas apenas uma irá chamar a operação offer(). E após a inclusão do novo nó no fim da lista cache LRU é verificado se é necessário chamar a operação evict(), para liberar os nós já separados para remoção.

offer(ent)

se o último nó não se refere à entrada ent
  atribui o nó corrente cNo <- ent.node
  cria um novo nó nNo(ent), o novo nó se refere à entrada ent
  se a operação atômica compare-e-atribua do nó ent.node, esperado cNo, atribuindo nNo
    adiciona o nó nNo para o fim da lista cache LRU
    se nó cNo não for nulo
      atribua à entrada cNo.entry nulo, e cNo agora tem uma entrada vazia
      adiciona o nó cNo para a fila hole
    fim
  fim
fim

Observe que primeiro é verificado se a entrada que está sendo adicionada não é exatamente a que acabou de ser incluida. Este é um caso raro de acontecer, a não ser que os valores sejam os mesmos acessados por várias threads. O segundo passo é executar uma operação atômica de "compare-e-atribua", que evita que as várias threads façam o mesmo processo ao mesmo tempo.

A thread verifica se a entrada foi anteriormente associada a outro nó. Caso positivo, o nó é marcado com a entrada vazia, e incluso na lista de nós a serem apagados. Esse mecanismo é utilizado para permitir a exclusão posterior por uma thread separada.

 

Desempenho

Em experimentos executados numa máquina com 4 núcleos e 16 threads, o desempenho chegou a 1 milhão de pesquisas por segundo. (Mas o desempenho pode variar muito de acordo com o número de threads, e também com o limite para remoção de nós antigos e o tempo de carregamento de itens no cache.)

Após alguns experimentos, foi notado que aumentando o número de threads faz com o que o desempenho diminua, ao contrário do que se poderia imaginar, pois as threads não acompanham o processo de purge(), causando gargalos.

Além disso, para operações com chaves e valores pequenos, o gerenciamento de memória do Java pode gerar um overhead que não ocorreria em C/C++. Assim, vale a tentativa de implementar esse tipo de algoritmo em outras linguagens para medir o desempenho do modelo apresentado.

Soluções criativas como a utilizada pelo eBay mostram que estamos deixando uma era em que somente o conhecimento de frameworks seria suficiente. Hoje a criatividade e o conhecimento de algoritmos estão fazendo a diferença em ambientes que exigem altos desempenho e escalabilidade.

Olá visitante

Você precisa cadastrar-se no InfoQ Brasil ou para enviar comentários. Há muitas vantagens em se cadastrar.

Obtenha o máximo da experiência do InfoQ Brasil.

Dê sua opinião

HTML é permitido: a,b,br,blockquote,i,li,pre,u,ul,p

Receber mensagens dessa discussão
Comentários da comunidade

HTML é permitido: a,b,br,blockquote,i,li,pre,u,ul,p

Receber mensagens dessa discussão

HTML é permitido: a,b,br,blockquote,i,li,pre,u,ul,p

Receber mensagens dessa discussão

Dê sua opinião

Conteúdo educacional

Feedback geral
Bugs
Publicidade
Editorial
InfoQ Brasil e todo o seu conteúdo: todos os direitos reservados. © 2006-2014 C4Media Inc.
Política de privacidade
BT