Qual é o algoritmo para itens expirados no armazenamento de valores-chave?

Eu estava pensando em como os armazenamentos atuais de valor-chave implementam a "data de vencimento" dos itens. Atualmente, tenho 2 variantes para isso em minha mente:

1. eles não fazem nada (mantêm os dados expirados) e só verificam quando você faz, por exemplo, GET por alguma chave. O problema aqui é que, se você tiver pouca memória, os itens expirados não serão excluídos.

2. eles mantêm estruturas de dados adicionais para conseguir "expirar o mais cedo possível". Vejo que isso pode ser feito com algo assim:

   storage_data = dict(key -> [value, expire_timestamp])
   expire_tree = SomeBinaryLikeTree(expire_timestamp -> [keys])
   

O problema de excluir entradas expiradas no cache é muito equivalente à coleta de lixo , menos toda a complexidade da contagem de referências.

As pessoas de Nasza-Klasa propuseram o algoritmo O (1) para Memcache da seguinte maneira:

Parece que muitas pessoas acreditam, por algum motivo, que a liberação de entradas expiradas não pode ser executada em O (1), ou mesmo que exija operações Omega (N). Usar uma pilha ou outras estruturas de dados de fila de prioridade pode obviamente fornecer O (log N), mas o patch abaixo visa O (1). Isso é conseguido com um depósito por cada segundo e colocando cada entrada em um depósito adequado, observando o tempo de expiração. A cada segundo, liberamos apenas elementos do próximo bloco. Isso obviamente é O (1) tempo amortizado, mas pode acontecer que você tenha muitos elementos que expiram no mesmo momento; portanto, o patch oferece um limite fixo para o número de operações que você deseja executar por uma solicitação, para tornar a coleta de lixo mais suave.

Veja toda a proposta com o código anexado .

Presumo que o armazenamento do valor-chave seja muito grande para percorrer todos os pares de kv para descobrir qual pode ser expirado. Suponho também que cada acesso de leitura atualize o carimbo de data / hora de expiração, portanto, apenas os itens que não foram acessados ​​por algum tempo expiraram.

O desafio é encontrar com eficiência todos os registros que podem expirar (sempre que a limpeza terminar), mas também atualizar com eficiência o carimbo de data / hora de expiração em todos os acessos de leitura (portanto, precisamos encontrar a chave na estrutura usada para a expiração).

Minha proposta: agrupar expiry_timestamps em buckets; por exemplo, se os itens durarem 8 horas, faça um balde por hora. Esses baldes são mantidos em uma lista vinculada; quando a expiração ocorre, o primeiro intervalo é esvaziado e a lista reduzida. O número de buckets é o tempo de vida útil / intervalo de limpeza. Cada bloco contém um hashSet de todas as chaves que devem expirar. A iteração sobre todas as chaves em um hashset é eficiente o suficiente.

Durante o acesso de leitura, o programa verifica em qual depósito a chave está atualmente e em qual depósito pertence agora. Na maioria dos casos, é o mesmo depósito, portanto, nenhuma ação adicional é necessária. Caso contrário, remova a chave do balde antigo (a remoção de um conjunto de hash é eficiente) e insira-a no novo balde.

   +--------------+   +--------------+   +--------------+
-->+ Expiry 08:00 +-->+ Expiry 09:00 +-->+ Expiry 10:00 +
   | KeySet       |   | KeySet       |   | KeySet       |
   +--------------+   +--------------+   +--------------+