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.

Avalie esse artigo

Relevância
Estilo/Redação

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
Feedback geral
Bugs
Publicidade
Editorial
Marketing
InfoQ Brasil e todo o seu conteúdo: todos os direitos reservados. © 2006-2016 C4Media Inc.
Política de privacidade
BT

We notice you’re using an ad blocker

We understand why you use ad blockers. However to keep InfoQ free we need your support. InfoQ will not provide your data to third parties without individual opt-in consent. We only work with advertisers relevant to our readers. Please consider whitelisting us.