Hay un patrón común que resuelve bastante bien este problema.
Use conjuntos ordenados y use una marca de tiempo como puntaje. Entonces es trivial eliminar elementos por rango de puntaje, lo que podría hacerse periódicamente, o solo en cada escritura, con lecturas que siempre ignoran los elementos fuera del rango, leyendo solo un rango de puntajes.
Más aquí:https://groups.google.com/forum/#!topic/redis-db/rXXMCLNkNSs