Cache LRU em Zig: HashMap e Lista Duplamente Encadeada

Para implementar um cache LRU em Zig, use um HashMap para encontrar entradas e uma lista duplamente encadeada para registrar a ordem de uso. O item acessado mais recentemente fica na frente; o menos recente fica no fim. Quando a capacidade acaba, remova o nó do fim e apague a mesma chave do mapa.

Essa combinação mantém get, put e eviction em tempo médio O(1). Ela é útil para metadados, arquivos pequenos, resultados de parsing, respostas calculadas e objetos cuja reconstrução custa mais que mantê-los temporariamente em memória. Para cache compartilhado entre processos ou com persistência, compare antes com Redis em Zig.

O exemplo deste guia tem capacidade fixa por quantidade de entradas, ownership explícito e nenhuma dependência externa. Ele também mostra os pontos que mais causam bugs: atualizar um valor existente, manter mapa e lista consistentes, liberar nós e sincronizar get em cenários concorrentes.

Resposta rápida: anatomia do LRU

As operações seguem regras pequenas:

• get(key): encontra o nó, move-o para head e retorna o valor;
• put(key, value): atualiza e promove se a chave já existe;
• put de chave nova: cria o nó na frente;
• se len > capacity: remove tail da lista e do mapa;
• deinit: destrói todos os nós e depois desaloca o mapa.

O detalhe importante é que ler também modifica o cache. Um get bem-sucedido muda a ordem LRU, então não pode ser tratado como operação somente leitura em um desenho multithread.

Por que não usar apenas um HashMap

Um mapa responde rapidamente “onde está a chave?”, mas não sabe qual entrada foi usada por último. Seria possível guardar um contador ou timestamp em cada item e percorrer o mapa na eviction, porém a remoção passaria a custar O(n).

Também não basta usar apenas uma lista: mover um nó conhecido para a frente é barato, mas encontrar esse nó pela chave exigiria percorrer todas as entradas.

A composição resolve os dois problemas:

1. o mapa aponta diretamente para o nó;
2. o nó conhece prev e next;
3. qualquer nó pode ser desconectado em O(1);
4. o fim da lista identifica imediatamente a vítima.

Esse é um padrão frequente em sistemas: uma estrutura oferece indexação e outra oferece ordenação. A correção depende de atualizá-las como uma única unidade lógica.

Implementação genérica em Zig

A implementação abaixo armazena chaves e valores por valor. Ela destrói os nós, mas não chama free em memória apontada por slices ou ponteiros dentro de K e V. Esse contrato será detalhado na seção de ownership.

const std = @import("std");

pub fn LruCache(comptime K: type, comptime V: type) type {
    return struct {
        const Self = @This();

        const Node = struct {
            key: K,
            value: V,
            prev: ?*Node = null,
            next: ?*Node = null,
        };

        allocator: std.mem.Allocator,
        map: std.AutoHashMap(K, *Node),
        capacity: usize,
        head: ?*Node = null,
        tail: ?*Node = null,

        pub fn init(
            allocator: std.mem.Allocator,
            capacity: usize,
        ) !Self {
            if (capacity == 0) return error.InvalidCapacity;

            return .{
                .allocator = allocator,
                .map = std.AutoHashMap(K, *Node).init(allocator),
                .capacity = capacity,
            };
        }

        pub fn deinit(self: *Self) void {
            var current = self.head;
            while (current) |node| {
                const next = node.next;
                self.allocator.destroy(node);
                current = next;
            }

            self.map.deinit();
            self.* = undefined;
        }

        pub fn len(self: *const Self) usize {
            return self.map.count();
        }

        pub fn get(self: *Self, key: K) ?*V {
            const node = self.map.get(key) orelse return null;
            self.moveToFront(node);
            return &node.value;
        }

        pub fn peek(self: *const Self, key: K) ?*const V {
            const node = self.map.get(key) orelse return null;
            return &node.value;
        }

        pub fn put(self: *Self, key: K, value: V) !void {
            if (self.map.get(key)) |node| {
                node.value = value;
                self.moveToFront(node);
                return;
            }

            const node = try self.allocator.create(Node);
            errdefer self.allocator.destroy(node);

            node.* = .{
                .key = key,
                .value = value,
            };

            try self.map.put(key, node);
            self.attachFront(node);

            if (self.map.count() > self.capacity) {
                self.evictLeastRecent();
            }
        }

        pub fn remove(self: *Self, key: K) bool {
            const node = self.map.get(key) orelse return false;
            _ = self.map.remove(key);
            self.detach(node);
            self.allocator.destroy(node);
            return true;
        }

        fn moveToFront(self: *Self, node: *Node) void {
            if (self.head == node) return;
            self.detach(node);
            self.attachFront(node);
        }

        fn attachFront(self: *Self, node: *Node) void {
            node.prev = null;
            node.next = self.head;

            if (self.head) |old_head| {
                old_head.prev = node;
            } else {
                self.tail = node;
            }

            self.head = node;
        }

        fn detach(self: *Self, node: *Node) void {
            if (node.prev) |prev| {
                prev.next = node.next;
            } else {
                self.head = node.next;
            }

            if (node.next) |next| {
                next.prev = node.prev;
            } else {
                self.tail = node.prev;
            }

            node.prev = null;
            node.next = null;
        }

        fn evictLeastRecent(self: *Self) void {
            const victim = self.tail orelse return;
            _ = self.map.remove(victim.key);
            self.detach(victim);
            self.allocator.destroy(victim);
        }
    };
}

Os nomes exatos de APIs da biblioteca padrão podem variar entre versões de Zig. Fixe a versão usada pelo projeto e trate erros de compilação como uma migração explícita, não como motivo para remover checagens de allocator ou consistência.

Como mapa e lista permanecem consistentes

Uma entrada existe em dois lugares lógicos: o mapa contém key -> *Node, e o nó participa da lista. Se uma operação atualizar apenas um lado, o próximo acesso pode encontrar um ponteiro destruído, contar uma entrada fantasma ou perder parte da lista.

No put de chave nova, a sequência é:

1. alocar o nó;
2. preencher chave e valor;
3. inserir o ponteiro no mapa;
4. anexar o nó à frente;
5. se necessário, remover a vítima dos dois índices.

O errdefer destrói o nó caso map.put falhe por falta de memória. A lista só é alterada depois da inserção bem-sucedida no mapa, então esse erro não exige rollback estrutural.

Na eviction, o código remove a chave do mapa antes de destruir o nó. Nunca deixe um ponteiro para memória liberada dentro do HashMap.

Atualização, get e peek

Quando put recebe uma chave existente, não deve criar outro nó. Ele substitui o valor e move o nó atual para a frente. Duplicar nós para a mesma chave quebraria a contagem e deixaria uma entrada antiga inacessível pelo mapa.

O exemplo oferece duas formas de leitura:

• get: retorna ?*V e atualiza a recência;
• peek: retorna ?*const V sem alterar a ordem.

Use peek apenas quando a leitura não deve contar como uso, por exemplo em diagnóstico. Em uma política LRU normal, servir o valor ao consumidor deve promover a entrada.

O ponteiro retornado por get é emprestado. Ele deixa de ser válido depois de remove, deinit ou qualquer operação que possa expulsar aquela entrada. Não guarde esse ponteiro fora do escopo controlado pelo cache.

Testando a política de eviction

O teste principal deve provar comportamento, não detalhes internos da lista:

test "LRU removes the least recently used entry" {
    var cache = try LruCache(u32, []const u8).init(
        std.testing.allocator,
        2,
    );
    defer cache.deinit();

    try cache.put(1, "um");
    try cache.put(2, "dois");

    // A chave 1 vira a mais recente; 2 passa a ser a vítima.
    try std.testing.expectEqualStrings("um", cache.get(1).?.*);

    try cache.put(3, "tres");

    try std.testing.expect(cache.get(2) == null);
    try std.testing.expectEqualStrings("um", cache.get(1).?.*);
    try std.testing.expectEqualStrings("tres", cache.get(3).?.*);
    try std.testing.expectEqual(@as(usize, 2), cache.len());
}

Adicione também testes para:

• capacidade 1;
• capacidade 0 rejeitada;
• atualização de chave sem aumentar len;
• remoção de head, tail e nó intermediário;
• get de chave ausente sem alterar a ordem;
• deinit sem vazamentos usando std.testing.allocator;
• sequência longa comparada com uma implementação de referência simples.

Para encontrar casos difíceis, gere operações aleatórias (put, get, remove) e compare o resultado com um modelo lento baseado em array. Esse tipo de teste diferencial costuma revelar erros nos ponteiros prev e next.

Ownership de chaves e valores

Zig obriga o projeto a responder: quem é dono da memória armazenada?

Na versão acima, K e V são copiados para o nó. Isso é suficiente para inteiros, enums e structs compostas apenas por valores. Para []const u8, somente o descritor do slice é copiado; os bytes continuam pertencendo a outro lugar.

Há três políticas comuns:

Para chaves de texto, StringHashMap ou um contexto de hash apropriado costuma ser mais adequado que AutoHashMap([]const u8, ...). Se o cache duplicar strings, armazene a cópia no nó e use exatamente essa slice como chave do mapa. Na eviction, remova do mapa antes de liberar seus bytes.

A escolha de allocator também importa. Leia estratégias de alocação de memória em Zig antes de usar uma arena: uma arena facilita desalocação em lote, mas não recupera memória de cada eviction. Em um cache de processo longo, um allocator que suporte destroy por nó costuma controlar melhor o uso real.

Tornando o LRU seguro entre threads

O cache mostrado não é thread-safe. Tanto put quanto remove escrevem, e um get bem-sucedido também altera quatro ligações possíveis da lista.

A solução inicial mais auditável é um único mutex protegendo mapa e lista juntos:

mutex.lock();
defer mutex.unlock();

const value = cache.get(key);

Não use um lock para o mapa e outro para a lista sem uma ordem global rigorosa. As duas estruturas representam o mesmo estado e devem mudar atomicamente aos olhos das outras threads. O guia Mutex vs Atomic em Zig ajuda a escolher a primitiva sem transformar uma estrutura simples em um algoritmo lock-free arriscado.

Se o mutex aparecer no perfil, alternativas incluem:

• um cache independente por thread;
• sharding por hash, com um mutex e um LRU por shard;
• política aproximada que não promove em todo hit;
• fila de acessos para uma thread proprietária aplicar a recência;
• cache somente leitura substituído por snapshots.

Faça a medição com perf e flamegraphs em Zig antes de aumentar a complexidade. Hit rate alto não compensa contenção extrema nem crescimento de memória.

Capacidade por itens ou por bytes

Limitar a quantidade de entradas funciona quando os valores têm tamanhos parecidos. Se uma resposta ocupa 500 bytes e outra 50 MiB, capacity = 1000 não representa um orçamento útil.

Para limitar por bytes, adicione:

• weight em cada nó;
• current_weight no cache;
• uma função que calcula o peso de K e V;
• eviction em loop enquanto current_weight > max_weight;
• rejeição de uma entrada individual maior que max_weight.

A inserção passa a expulsar zero, uma ou várias entradas. Atualizar um valor existente precisa subtrair o peso antigo e somar o novo antes de verificar o limite.

Não use apenas RSS do processo como controle: allocator, fragmentação, stacks, bibliotecas e buffers externos também ocupam memória. O peso do cache é uma métrica do subsistema, não a memória total do serviço.

LRU, FIFO, TTL ou LFU: qual escolher?

TTL e LRU podem coexistir: primeiro rejeite entradas expiradas; depois use LRU para respeitar o orçamento. Evite verificar todos os TTLs a cada operação. Uma heap de expiração, timing wheel ou limpeza amostrada pode ser melhor, dependendo da escala.

Métricas mínimas em produção

Instrumente o cache desde o início:

Calcule hit_rate = hits / (hits + misses), mas interprete junto com latência e custo do miss. Um cache com 95% de hits pode ser inútil se os 5% restantes são baratos; outro com 40% pode valer muito se evita leituras de disco ou parsing pesado.

Não registre cada chave perdida em logs de produção. Isso aumenta I/O, pode expor dados e cria uma carga justamente durante uma tempestade de misses. Prefira contadores, amostragem e categorias de chave.

Evitando cache stampede

Quando uma chave popular expira ou sofre eviction, várias threads podem calcular o mesmo valor simultaneamente. O LRU sozinho não evita essa avalanche.

Opções práticas:

1. single-flight por chave: uma thread carrega, as outras aguardam;
2. stale-while-revalidate: servir valor antigo por uma janela enquanto uma thread atualiza;
3. jitter no TTL: evitar que milhares de entradas expirem no mesmo instante;
4. limite de concorrência: proteger a origem contra misses simultâneos;
5. negative caching curto: guardar “não encontrado” quando isso é seguro.

Tenha cuidado para não executar I/O lento segurando o mutex global do LRU. Um padrão comum é consultar sob lock, registrar o carregamento em andamento, liberar o lock, buscar o valor e voltar para publicar o resultado.

Checklist de code review

Antes de colocar o cache em produção, confirme:

• capacidade zero é rejeitada;
• cada chave tem exatamente um nó;
• mapa e lista são atualizados na mesma operação lógica;
• eviction remove do mapa antes de destruir o nó;
• atualização não aumenta a contagem;
• get promove a entrada e peek não promove;
• ownership de chaves e valores está documentado;
• ponteiros retornados têm lifetime limitado;
• deinit, remove, replace e eviction não vazam recursos;
• acesso concorrente protege também get;
• capacidade representa um orçamento realista;
• hit, miss, eviction e ocupação têm métricas;
• a política foi comparada com FIFO, TTL ou cache externo.

Conclusão

Um cache LRU em Zig é uma aplicação direta de duas estruturas complementares: HashMap para localização e lista duplamente encadeada para recência. O algoritmo cabe em pouco código, mas só é confiável quando ownership, rollback de alocação, lifetime dos ponteiros e consistência entre mapa e lista estão explícitos.

Comece com capacidade pequena, um único mutex se houver concorrência e métricas de hit/miss. Só adicione sharding, limite por bytes, TTL ou single-flight depois que a carga mostrar a necessidade. Em sistemas, o melhor cache não é o mais sofisticado: é aquele cujo consumo de memória, política de eviction e comportamento sob miss a equipe consegue explicar e testar.