AFAIK, não é possível configurar o Redis para remover consistentemente os dados mais antigos primeiro.

Quando as opções *-ttl ou *-lru são escolhidas em maxmemory-policy, o Redis não usa um algoritmo exato para escolher as chaves a serem removidas. Um algoritmo exato exigiria uma lista extra (para *-lru) ou um heap extra (para *-ttl) na memória e a referência cruzada com a estrutura de dados normal do dicionário Redis. Seria caro em termos de consumo de memória.

Com o mecanismo atual, os despejos ocorrem no loop de eventos principal (ou seja, os despejos em potencial são verificados em cada iteração do loop antes de cada comando ser executado). Até que a memória volte ao limite máximo de memória, o Redis escolhe aleatoriamente uma amostra de n chaves e seleciona para expiração a mais ociosa (para *-lru) ou a que estiver mais próxima de seu limite de expiração (para *-ttl). Por padrão, apenas 3 amostras são consideradas. O resultado não é determinístico.

Uma forma de aumentar a precisão deste algoritmo e mitigar o problema é aumentar o número de amostras consideradas (parâmetro maxmemory-samples no arquivo de configuração). Não deixe muito alto, pois consumirá alguma CPU. É uma compensação entre a precisão do despejo e o consumo de CPU.

Agora, se você realmente precisa de um comportamento consistente, uma solução é implementar seu próprio mecanismo de despejo no Redis. Por exemplo, você pode adicionar uma lista (para chaves não atualizáveis) ou um conjunto classificado (para chaves atualizáveis) para rastrear as chaves que devem ser despejadas primeiro. Em seguida, você adiciona um daemon cuja finalidade é verificar periodicamente (usando INFO) o consumo de memória e consultar os itens da lista/conjunto ordenado para remover as chaves relevantes.

Observe que outros sistemas de cache têm sua própria maneira de lidar com esse problema. Por exemplo, com o memcached, há uma estrutura LRU por slab (que depende do tamanho do objeto), portanto, a ordem de despejo também não é precisa (embora mais determinística do que com o Redis na prática).