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.