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).