6

Como parte de um teste foi pedido que eu desenvolvesse uma aplicação para gerir dados de high scores em ambientes com alta concorrência. Essa aplicação não deve persistir nada em disco ou utilizar bibliotecas e frameworks externos. Basicamente os requisitos dizem que:

  • otimizar o uso de memória e CPU é importantíssimo
  • o serviço receberá um número estelar de requests simultâneos
  • para a parte de http devemos utilizar a classe HttpServer.

A aplicação é basicamente um conjunto de serviços rest para o usuário:

  • logar (deve retornar um token e manter o user autenticado por 10 minutos)
  • postar um high score para determinado nível
  • obter uma lista de high scores para determinado nível (em ordem)

O sistema só deve retornar 15 high scores para cada nível, os high scores são únicos para cada par Usuário / Nível (ou seja, para a fase x o user y só deve possuir um high score).

Considerando os requisitos funcionais e não funcionais pensei na seguinte estrutura de dados para armazenar high scores (com o mínimo de retenção):

// Mapa que liga um nivel a uma lista ordenada de High Scores
private static final Map<Integer, ConcurrentSkipListSet<HighScore>> scores = 
   new ConcurrentHashMap<>();
// Conjunto de usuários autenticados
private static final Set<AuthToken> authorized = 
   Collections.newSetFromMap(new ConcurrentHashMap<AuthToken, Boolean>());

Enquanto essa estrutura de dados me parece eficiente no sentido de reduzir a retenção não sei o quanto ela acaba desperdiçando memória internamente.

Da mesma maneira, os ConcurrentSkipListSet permitem inserção ordenada em log(n) e tornam a implementação do método que retorna high scores trivial. Por outro lado, para limitar o Set aos top 15 high scores por nível (para evitar desperdício de memória e crashes), fiz uma verdadeira ginástica incluindo o uso de AtomicInteger para contar a quantidade de high scores por nível (o método size da ConcurrentSkipListSet é custoso) e a necessidade de sincronizar vários pontos com locks.

Em suma, não estou convencido de que estou usando a estratégia mais eficiente para resolver o problema e nem estou acostumado a pensar em tão baixo nível...

No mundo "real" resolveria esse problema de maneira trivial com o uso de um container Jetty, um Servlet para o login armazendo a autenticação na sessão e, provavelmente, um banco de dados embedded como o H2. Infelizmente não estou autorizado a usar nada disso.

Dessa maneira, como vocês abordariam um problema desse tipo dadas as constraints artificias de tecnologia? Usariam quais estruturas de dados (ou desenvolveriam suas próprias?)? A minha estratégia é "boa o suficiente" para o problema ou viajei na solução?


P.S. Esse problema submetido à Code Review se parece muito com o que estou resolvendo (e a solução foi parecida com a minha também).

2
  • Suponho que esteja fora do seu escopo um caso em que o mesmo usuário submeta um high score menor que um outro submetido anteriormente, certo? (mesmo porque isso não faria sentido...) Da mesma forma, um score submetido não pode ser removido, certo? (pergunto pra saber se você pode mesmo seguramente descartar o 16º resultado pra frente)
    – mgibsonbr
    23/12/2013 às 14:23
  • @mgibsonbr, exatamente. Um único score por usuário / nível (o maior) e não existe nenhum front para apagar um high-score. Podemos seguramente descartar resultados além do décimo quinto. 23/12/2013 às 20:25

1 Resposta 1

2

Não tenho muita experiência com programação concorrente - em particular envolvendo Java - então não posso te sugerir uma estrutura de dados eficiente, mas posso te dar alguns parâmetros para te ajudar a decidir:

  1. Não se preocupe com a ordem de complexidade da estrutura, mas sim com seu fator constante.

    Você diz que o "ConcurrentSkipListSet permite inserção ordenada em log(n)", mas isso é mesmo relevante em uma lista com apenas 15 elementos? Imagina quantos nós essa lista vai criar? (lembre-se que um objeto Java tem um overhead fixo de uns 24 bytes se me lembro bem, mais uma referência pro HighScore no mínimo e outras referências internas para os demais nós) E as falhas na predição de desvio? (branch prediction) Não que eu ache isso relevante, uma vez que o gargalo dos processadores modernos não é o CPU, mas a cache...

    Um simples array (ou o equivalente thread-safe disponível) com referências para os HighScores ocuparia menos espaço (overhead de 24 bytes + 4 ou 8 bytes por cada uma das 15 referências). E o desempenho para percorrê-lo seria bom, ainda que ele estivesse desordenado (basta percorrê-lo todo lembrando do menor índice, depois acrescentar ou substituir o menor conforme o total seja menor ou igual a 15) - principalmente porque as referências ocuparão uma posição contígua na memória (o que evita cache miss). Se a solução envolver uma seção crítica (synchronize), então pouco importa o algoritmo, pois o lock sozinho vai ser responsável por 90% do tempo de execução. Por falar nisso...

  2. O synchronize é seu pior inimigo.

    De novo, não tenho familiaridade com os recursos que Java oferece para acesso concorrente, mas se for o caso que esse ConcurrentSkipListSet consegue operar sem usar synchronize então é melhor utilizá-lo do que fazer qualquer "gambiarra" para poder acessar o size em tempo constante. Esse método só é "custoso" se o seu conjunto é grande, mas log(n) numa lista de 15 elementos é quase o mesmo que O(1).

    Estabelecer uma seção crítica sempre envolve o acesso ao disco (uns 10.000 ciclos de CPU da última vez que eu chequei), por isso evite o uso de synchronize sempre que isso for possível. A propósito...

  3. Não é necessário esperar que uma operação esteja pronta antes de terminar o request.

    Quando o usuário submete seu high score, sugiro "enfileirá-lo" para processamento e seguir em frente. Dê uma olhada em ConcurrentLinkedQueue por exemplo. Se você tiver um thread dedicado em reunir todos os high scores submetidos (i.e. cada request produz algo, um thread à parte consome) fica mais fácil escolher estruturas de dados que ofereçam bom desempenho sem precisar usar um lock.

    Se logo depois de submeter um high score o usuário pedir a lista para um determinado nível, você sempre pode pegar uma cópia daquela lista (é recomendável que o thread apenas a atualize de forma atômica), se necessário atualizá-la com os últimos scores ainda não processados (ConcurrentLinkQueye.toArray(T[] a)) e retornar. Se quiser evitar esse retrabalho - e não houver problema em ocasionalmente se obter uma lista desatualizada (inevitável) que não inclua o último score que o próprio usuário postou (evitável, mas traz mais complexidade) - apenas retorne a lista no seu estado atual.

No mais, creio que sua solução proposta está adequada. Na prática eu sugeriria que em vez de um conjunto de tokens de acesso, você mapeasse um token para um usuário (para evitar que um usuário atualizasse o high score de outro), mas se você estivesse preocupado com trapaça nada que você fizesse seria 100% garantido... (uma vez que os dados vêm do lado cliente)

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .