--- title: "Cache LRU em Zig: HashMap e Lista Duplamente Encadeada" url: "https://ziglang.com.br/artigos/zig-lru-cache-hashmap-lista-duplamente-encadeada/" markdown_url: "https://ziglang.com.br/artigos/zig-lru-cache-hashmap-lista-duplamente-encadeada.MD" description: "Implemente um cache LRU em Zig com HashMap, lista duplamente encadeada, capacidade fixa, eviction O(1), ownership explícito, testes e métricas de produção." date: "2026-09-09" author: "" --- # Cache LRU em Zig: HashMap e Lista Duplamente Encadeada Implemente um cache LRU em Zig com HashMap, lista duplamente encadeada, capacidade fixa, eviction O(1), ownership explícito, testes e métricas de produção. 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](/artigos/zig-redis-cache-rate-limit-lock/). 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 | Componente | Responsabilidade | Custo esperado | |---|---|---:| | `AutoHashMap(K, *Node)` | Encontrar o nó pela chave | O(1) médio | | Lista duplamente encadeada | Manter a ordem de recência | O(1) | | `head` | Entrada mais recentemente usada | O(1) | | `tail` | Entrada candidata à próxima eviction | O(1) | | Allocator | Criar e destruir nós | Depende do allocator | 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. ```zig 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: ```zig 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: | Política | Vantagem | Responsabilidade | |---|---|---| | Cache recebe valores emprestados | Simples e sem cópia | Dados devem viver mais que a entrada | | Cache duplica chave e valor | Ownership local claro | Liberar ambos em replace, remove, eviction e deinit | | Chamador fornece callbacks | Genérico para recursos complexos | API e tratamento de erro ficam maiores | 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](/artigos/zig-alocacao-memoria-estrategias/) 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**: ```zig 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](/artigos/zig-mutex-vs-atomic-quando-usar/) 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](/artigos/zig-profiling-perf-flamegraph/) 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? | Política | Expulsa | Boa escolha quando | Limitação | |---|---|---|---| | LRU | Menos recente | Recência prevê reutilização | Todo hit altera metadados | | FIFO | Mais antigo inserido | Simplicidade e baixo overhead | Ignora acessos recentes | | TTL | Item expirado | Validade tem prazo objetivo | Pode manter itens frios até expirar | | LFU | Menos frequente | Popularidade de longo prazo importa | Contadores e aging são mais complexos | | Random | Item aleatório | Overhead mínimo e cache grande | Menor previsibilidade | 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: | Métrica | Interpretação | |---|---| | `cache_get_total` | Volume de consultas | | `cache_hit_total` | Consultas servidas pelo cache | | `cache_miss_total` | Trabalho que precisou ser refeito | | `cache_eviction_total` | Pressão sobre a capacidade | | `cache_entries` | Ocupação atual | | `cache_weight_bytes` | Memória lógica, se houver pesos | | latência de `get` e carregamento | Benefício real e contenção | 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.