No artigo anterior desta série, vimos como um sistema pode entrar em colapso quando o banco de dados recebe mais requisições do que consegue processar, e como o cache foi a intervenção que restaurou a estabilidade operacional. O cache foi apresentado como uma camada que guarda resultados de operações custosas para evitar repeti-las. Mas essa descrição, ainda que correta, omite algo importante. Por que o cache funciona? Por que guardar um dado em outro lugar acelera o sistema? E por que esse princípio aparece em praticamente todo nível da computação moderna, do transistor dentro do processador até os servidores de borda distribuídos pelos continentes?
A resposta começa num problema que os engenheiros de hardware enfrentaram há mais de sessenta anos e que nunca deixou de ser relevante.
O problema que nunca foi resolvido, apenas gerenciado
Desde o início da computação moderna, velocidade e capacidade de armazenamento caminham em direções opostas. Memória rápida é cara e pequena. Memória barata é grande e lenta. Esse antagonismo tem raízes físicas e econômicas que não se alteraram desde os anos 1960.
Na prática, isso significa que um processador moderno consegue executar bilhões de operações por segundo, mas o acesso à memória principal pode ser centenas de vezes mais lento do que a velocidade de execução das instruções. Quando o processador precisa de um dado que não está disponível imediatamente, ele para e espera. Esse tempo de espera é chamado de latência de memória, e ela é o gargalo que define o desempenho real de boa parte dos programas que existem.
As ordens de grandeza que governam esse problema foram catalogadas por Jeff Dean e depois atualizadas por Peter Norvig em sua página pessoal, e são referência na literatura de sistemas distribuídos. No artigo anterior desta série já citamos alguns desses números no contexto do banco de dados. Aqui o que importa é a proporção dentro do próprio hardware. Um acesso à memória principal leva cerca de 100 nanossegundos, enquanto um acesso ao cache L1 do processador leva cerca de 0,5 nanossegundo, duzentas vezes mais rápido. Esses números variam com as gerações de hardware, mas as proporções se mantêm estáveis há décadas.
graph LR
A["Registradores
~0.3 ns"] --> B["Cache L1
~1 ns"]
B --> C["Cache L2
~4 ns"]
C --> D["Cache L3
~10 ns"]
D --> E["Memória RAM
~100 ns"]
E --> F["SSD NVMe
~100 µs"]
F --> G["Disco magnético
~10 ms"]
G --> H["Rede / CDN
~50-150 ms"]
style A fill:#1a472a,color:#fff
style B fill:#1e5631,color:#fff
style C fill:#2d7a3e,color:#fff
style D fill:#3a9e52,color:#fff
style E fill:#f0a500,color:#000
style F fill:#e05c00,color:#fff
style G fill:#c0392b,color:#fff
style H fill:#922b21,color:#fffA resposta que a engenharia encontrou foi criar camadas intermediárias. Em vez de escolher entre memória rápida ou memória grande, os sistemas modernos usam ambas ao mesmo tempo, em hierarquia. Os dados mais usados ficam nos níveis mais rápidos. Os dados menos usados ficam nos níveis mais lentos. E a movimentação entre níveis acontece automaticamente, guiada por um princípio observado empiricamente nos programas de computador.
O princípio que tornou tudo possível
Em 1966, Les Belady, da IBM, publicou no IBM Systems Journal um estudo sobre algoritmos de substituição de páginas em sistemas com memória virtual. O problema central que Belady investigava era decidir qual página descartar quando o cache está cheio e uma nova página precisa entrar. Para resolvê-lo, ele propôs o que ficou conhecido como algoritmo de Belady, que descarta sempre a página que será referenciada mais distante no futuro. Esse algoritmo é teoricamente ótimo, mas pressupõe conhecimento do futuro, o que o torna impraticável. Seu valor está em estabelecer o teto de desempenho que qualquer algoritmo real pode aspirar.
O que o trabalho de Belady deixou implícito, Peter Denning formalizou dois anos depois. Denning percebeu que o problema dos algoritmos de substituição só existia porque os programas não acessavam a memória de forma aleatória. Se o acesso fosse aleatório, qualquer dado no cache teria a mesma probabilidade de ser pedido novamente, e a questão de qual descartar seria irrelevante. O fato de que os algoritmos de substituição fazem diferença na prática é evidência de que o acesso à memória segue um padrão estruturado, que ficou conhecido como localidade de referência.
Em 1968, Denning publicou na Communications of the ACM seu trabalho sobre o modelo de working set, que recebeu o ACM Best Paper Award de sistemas naquele ano. Ali, ele mostrou que todo programa em execução, em qualquer intervalo de tempo razoável, usa ativamente apenas uma fração pequena de todas as páginas de memória que possui. A esse conjunto ativo ele chamou de working set.
"A localidade foi adotada como ideia quase imediatamente por arquitetos de sistemas operacionais, bancos de dados e hardware."
— Peter Denning, The Locality Principle, Communications of the ACM, 2005
A localidade de referência tem duas dimensões. A primeira é a localidade temporal. Um dado que foi acessado recentemente tem alta probabilidade de ser acessado novamente em breve. Quando um programa lê o valor de uma variável, há boa chance de que precise desse valor de novo alguns ciclos depois. A segunda é a localidade espacial. Quando um dado em determinado endereço de memória é acessado, os dados em endereços próximos têm alta probabilidade de serem acessados em seguida. Isso acontece porque programas processam arrays, listas e estruturas de dados que são armazenados em blocos contíguos na memória.
Essas duas propriedades são o que torna o cache eficaz. Se os dados seguissem uma distribuição aleatória de acesso, guardar alguns deles num lugar mais rápido não ajudaria muito, porque a chance de acertar seria baixa. Mas como o acesso é concentrado e previsível em termos de padrão, mesmo um cache relativamente pequeno consegue absorver uma grande fração dos acessos.
O conceito de working set não é específico de memória de processador. Em um sistema web com Redis, o working set é o conjunto de dados que os usuários ativos estão acessando naquele momento. Isso inclui os produtos mais visitados, os perfis dos usuários com sessão aberta e as configurações carregadas por cada instância da aplicação. Esse conjunto tende a ser uma fração pequena do banco de dados total, mas concentra a grande maioria do tráfego de leitura. É por isso que um Redis com alguns gigabytes consegue absorver a maior parte das queries de um banco de dados com terabytes.
Como o processador implementa cache em hardware
Maurice Wilkes, cientista britânico da Universidade de Cambridge, foi o primeiro a propor formalmente a ideia de uma memória intermediária entre o processador e a memória principal. Em seu artigo de 1965, publicado no IEEE Transactions on Electronic Computers, ele descreveu o conceito em termos que ainda servem como referência.
"Discute-se o uso de uma memória central rápida de, digamos, 32.000 palavras como auxiliar de uma memória central mais lenta de, digamos, um milhão de palavras, de forma que, em casos práticos, o tempo de acesso efetivo seja mais próximo do da memória rápida do que da memória lenta."
— Maurice Wilkes, Slave Memories and Dynamic Storage Allocation, IEEE Transactions on Electronic Computers, 1965
A primeira implementação comercial apareceu no IBM System/360 Model 85, em 1969, com 16 KB de cache. Era uma quantidade minúscula de memória rápida, mas suficiente para demonstrar que o princípio funcionava na prática.
Hoje, um processador moderno de uso geral tem três ou quatro níveis de cache integrados ao chip. O cache L1 é o mais próximo dos núcleos de processamento, menor e mais rápido, tipicamente entre 32 KB e 64 KB por núcleo. O cache L2 é maior e um pouco mais lento, na faixa de 256 KB a alguns MB por núcleo. O cache L3 é compartilhado entre os núcleos, com dezenas de MB, e serve como última linha antes de precisar ir à memória principal.
Quando o processador precisa de um dado, ele percorre essa hierarquia em ordem crescente de latência. Se o dado estiver no L1, o acesso leva cerca de 4 ciclos de clock. Se não estiver, vai ao L2, que leva cerca de 12 ciclos. Se não estiver no L2, vai ao L3, com cerca de 30 a 40 ciclos. Se não estiver no L3, vai à memória principal, com latência de 200 a 300 ciclos. A diferença entre encontrar o dado no L1 e precisar ir à memória principal é de 50 a 75 vezes em termos de latência.
sequenceDiagram
participant CPU as Núcleo
participant L1 as Cache L1
(~4 ciclos)
participant L2 as Cache L2
(~12 ciclos)
participant L3 as Cache L3
(~35 ciclos)
participant RAM as Memória RAM
(~250 ciclos)
CPU->>L1: Solicita dado
alt Hit no L1
L1-->>CPU: Retorna dado
else Miss no L1
L1->>L2: Busca dado
alt Hit no L2
L2-->>L1: Retorna dado
L1-->>CPU: Retorna dado
else Miss no L2
L2->>L3: Busca dado
alt Hit no L3
L3-->>L2: Retorna dado
L2-->>L1: Retorna dado
L1-->>CPU: Retorna dado
else Miss no L3
L3->>RAM: Busca dado
RAM-->>L3: Retorna dado
L3-->>L2: Retorna dado
L2-->>L1: Retorna dado
L1-->>CPU: Retorna dado
end
end
endQuando ocorre um miss no L1, não é o L1 que vai buscar o dado no L2 de forma autônoma. Quem detecta o miss e dispara a requisição é o cache controller, um circuito de hardware embutido no processador. O núcleo fica bloqueado esperando. O dado sobe a hierarquia pelo caminho inverso. Se estava na RAM, passa pelo L3, depois pelo L2, e finalmente chega ao L1, preenchendo cada nível pelo qual passa. Isso significa que, após um miss completo até a RAM, todos os níveis intermediários ficam com uma cópia do dado, o que acelera acessos futuros ao mesmo conteúdo por outros núcleos ou pela mesma sequência de código.
Quando o L1 está cheio e precisa acomodar um cache line recém-chegado, ele precisa descartar outro. Essa decisão é tomada pela política de substituição. É aqui que o algoritmo de Belady entra, não como mecanismo real, mas como referência teórica. Belady provou que o algoritmo ótimo é descartar a linha que será referenciada mais distante no futuro, mas isso exige conhecimento do futuro, o que o torna impraticável. O que os processadores reais usam é o LRU (Least Recently Used), que descarta o dado que não foi acessado há mais tempo. LRU é uma aproximação do ótimo de Belady usando apenas informação do passado. Se um dado não foi pedido recentemente, a probabilidade de ser pedido em breve é baixa.
Na prática, L1 e L2 usam variações de pseudo-LRU, porque implementar LRU puro em hardware na velocidade desses níveis seria muito custoso em área de silício. Todo esse processo é transparente para o programador. O hardware toma as decisões de busca e evicção automaticamente, sem que nenhuma linha de código precise se preocupar com qual nível da hierarquia está sendo acessado.
O que torna um workload cacheável
A eficácia do cache depende de uma métrica chamada hit ratio, que é a proporção de acessos que encontram o dado no cache sem precisar buscá-lo na origem. Um hit ratio de 90% significa que apenas 10% dos acessos precisam ir ao nível mais lento. Um hit ratio de 50% significa que metade dos acessos ainda paga o custo completo.
O hit ratio de um sistema é determinado principalmente pela distribuição dos seus acessos. Sistemas cujo tráfego segue uma distribuição de lei de potência, onde poucos itens concentram a maioria dos acessos, são naturalmente favoráveis ao cache. Um conjunto pequeno de dados cobre uma fração grande do tráfego total, então um cache pequeno consegue um hit ratio alto.
Sistemas com distribuição uniforme, onde todos os dados têm a mesma probabilidade de serem acessados, são desfavoráveis ao cache. Para manter um hit ratio alto nesse tipo de workload, o cache precisaria ter capacidade próxima ao tamanho total dos dados, o que elimina a vantagem econômica da hierarquia.
Na prática, a maioria dos workloads de aplicações web e de banco de dados se aproxima mais da distribuição de lei de potência do que da distribuição uniforme. Produtos populares, artigos recentes, perfis de usuários ativos e configurações do sistema tendem a ser acessados com frequência desproporcional em relação ao conjunto total. Isso é o que torna o cache eficaz na maioria dos cenários onde ele é aplicado.
Há também uma dimensão temporal além da distribuição de frequência. O hit ratio depende de quanto tempo os dados permanecem válidos no cache em relação ao ritmo de atualização na origem. Dados que mudam raramente, como configurações do sistema ou listas de categorias de produtos, podem ficar no cache por longos períodos sem risco de desatualização. Dados que mudam frequentemente, como saldos de conta ou estoque em tempo real, exigem tempos de expiração curtos (TTL) ou estratégias de invalidação ativa, o que reduz o hit ratio efetivo.
A hierarquia além do hardware
O mesmo princípio que justifica o cache L1 dentro do processador justifica cada camada de cache ao longo do caminho entre um servidor e um usuário. A lógica é idêntica em todos os casos. Dados que precisam ser acessados frequentemente devem ser mantidos o mais perto possível de quem os usa, para minimizar a latência e o custo de acesso.
No nível do sistema operacional, existe o page cache, que mantém em memória RAM as páginas de arquivos recentemente lidas do disco. Quando um programa lê um arquivo, o sistema operacional guarda o conteúdo em memória. Na próxima leitura do mesmo arquivo, o dado já está disponível sem nova leitura de disco. O Linux, por exemplo, usa toda a memória RAM disponível que não está sendo usada por processos para page cache, e a libera automaticamente quando um processo precisa de mais memória.
No nível da aplicação, o cache de queries ao banco de dados funciona da mesma forma. O resultado de uma consulta é guardado em memória, e as próximas requisições pelo mesmo resultado são atendidas diretamente, sem executar a query novamente. É exatamente o que descrevemos no artigo anterior com o Redis.
No nível da rede, as CDNs, Content Delivery Networks, aplicam o mesmo princípio em escala global. A Akamai, fundada em 1998 por Tom Leighton e Daniel Lewin a partir de uma pesquisa no MIT, foi a primeira empresa a comercializar esse conceito em larga escala. A percepção central de Leighton e Lewin era que conteúdo armazenado próximo ao usuário final pode ser acessado sem percorrer uma longa distância pela internet. Em vez de servir todos os usuários do mundo a partir de um único servidor de origem, o conteúdo é replicado em centenas ou milhares de servidores distribuídos geograficamente. Quando um usuário no Brasil acessa um vídeo hospedado por uma empresa americana, o vídeo é servido por um servidor localizado no Brasil ou na América do Sul, não pela origem nos Estados Unidos.
A diferença de latência entre buscar um dado de um servidor a 20 km de distância versus buscar do outro lado do planeta é medida em milissegundos, mas esse valor é perceptível para o usuário e significativo para sistemas que fazem muitas requisições encadeadas. Uma página web moderna pode fazer dezenas de requisições a recursos diferentes para ser carregada. Se cada uma dessas requisições adiciona 100 ms de latência intercontinental, o tempo total de carregamento cresce de forma rápida.
A relação entre latência, throughput e contenção
Esses três conceitos descrevem aspectos distintos do comportamento de um sistema sob carga, e entendê-los separadamente ajuda a diagnosticar problemas com mais precisão.
Latência é o tempo que leva para uma operação individual ser concluída, medida do ponto de vista de quem a requisitou. Throughput é o número de operações que um sistema consegue completar por unidade de tempo. Contenção, o fenômeno que percorreu o artigo anterior desta série, é a competição entre múltiplos processos pelo mesmo recurso limitado.
A relação entre os três é capturada pela Lei de Little, formulada por John Little em 1961 e publicada na Operations Research. A lei estabelece que o número médio de elementos num sistema é igual ao throughput multiplicado pela latência média. Em outras palavras, se a latência aumenta e o throughput se mantém constante, o número de requisições acumuladas dentro do sistema cresce proporcionalmente.
Isso explica o padrão de degradação progressiva descrito no artigo anterior. Quando a latência das queries ao banco de dados aumentou devido ao aumento de volume, as conexões ficaram abertas por mais tempo. Mais conexões abertas ao mesmo tempo significa mais contenção pelo pool de conexões. Mais contenção aumenta ainda mais a latência. O ciclo se retroalimenta.
O cache quebra esse ciclo ao reduzir a latência de uma fração das requisições. Quando 80% das requisições passam a ser atendidas em menos de 1 milissegundo pelo Redis, em vez de 100 a 200 milissegundos pelo banco de dados, o número médio de requisições em processamento simultâneo cai drasticamente. A contenção diminui. O pool de conexões se libera. O sistema recupera a capacidade de absorver o volume de entrada.
"O número médio de elementos num sistema é igual à taxa média de chegada multiplicada pelo tempo médio que um elemento permanece no sistema."
— John D. C. Little, A Proof for the Queuing Formula: L = λW, Operations Research, 1961
Por que o cache existe em cada camada
A hierarquia de cache que descrevemos até aqui, do L1 no processador ao servidor de borda na CDN, não é uma coincidência de design. É a aplicação do mesmo princípio em contextos com diferentes ordens de grandeza de latência e diferentes unidades de dado.
No processador, a unidade é uma cache line de 64 bytes, e a latência que se tenta evitar é da ordem de centenas de nanossegundos. Na aplicação web, a unidade é o resultado de uma query ou uma sessão de usuário, e a latência que se tenta evitar é da ordem de dezenas de milissegundos. Na CDN, a unidade é um arquivo de imagem, um script JavaScript ou um segmento de vídeo, e a latência que se tenta evitar é intercontinental, da ordem de centenas de milissegundos.
Em todos os casos, a estrutura é a mesma. Existe uma origem que tem todos os dados mas é lenta ou distante. Existe um cache que tem um subconjunto dos dados mas é rápido e próximo. O sistema tenta servir as requisições pelo cache quando possível, e vai à origem apenas quando necessário. E a eficácia desse arranjo depende de quanto o padrão de acesso aos dados exibe localidade temporal, espacial, ou ambas.
O que muda entre os níveis é a proporção entre o tamanho do cache e o tamanho total dos dados. No processador, o cache L1 tem dezenas de kilobytes para cobrir um espaço de endereçamento de gigabytes, uma proporção de um para milhões. Em uma aplicação web, um Redis com dezenas de gigabytes cobre um banco de dados com terabytes, uma proporção de um para centenas. Em uma CDN, os servidores de borda armazenam terabytes para cobrir um volume de origem que pode ser muito maior. Em todos os níveis, o cache precisa de uma fração pequena da origem para ser eficaz. Isso só é possível porque o padrão de acesso não é uniforme. O working set, em qualquer escala, é sempre menor do que o conjunto total.
Denning capturou essa universalidade em um artigo posterior, revisitando décadas de aplicação do princípio que ele havia formalizado.
"A localidade não é específica de programas. Ela aparece em sistemas de arquivos, em bancos de dados, em redes e em comportamento humano. É um princípio da natureza."
— Peter Denning, The Locality Principle, Communications of the ACM, 2005
O que esse princípio significa para o design de sistemas
Entender a hierarquia de memória e o princípio da localidade muda a forma como se pensa sobre design de sistemas. Um sistema que ignora esses princípios vai acabar pagando custos que poderiam ser evitados. Um sistema que os explora de forma consciente consegue desempenho muito superior com os mesmos recursos de hardware.
Um exemplo concreto é um sistema que serializa o objeto completo de um usuário em uma única chave no Redis, incluindo histórico, preferências e dados de perfil. Esse design ignora a localidade espacial. Se a aplicação precisa frequentemente apenas do nome e do avatar para renderizar um cabeçalho, ela carrega e deserializa o blob inteiro a cada requisição. O cache está em uso, mas o design dos dados trabalha contra o princípio que o cache explora. O custo aparece na latência de deserialização e no consumo de memória, não no banco de dados, o que torna o diagnóstico mais difícil do que no cenário de cache ausente.
Na prática, isso se traduz em algumas perguntas que valem a pena fazer ao desenhar qualquer sistema que manipula dados. Qual é o padrão de acesso esperado? Os dados têm distribuição concentrada ou uniforme? Com que frequência os mesmos dados são pedidos em sequência? Quando um dado é pedido, quais outros dados tendem a ser pedidos junto?
Essas perguntas não têm respostas universais. Dependem do domínio do problema, do volume de usuários, e do comportamento específico da aplicação. Sem essas perguntas, qualquer implementação de cache é uma aposta, não uma decisão arquitetural.
No próximo artigo desta série, o foco se desloca da teoria para os padrões arquiteturais concretos que determinam como o cache se integra ao resto do sistema. Cache-aside, read-through, write-through e write-behind são padrões com trade-offs distintos, mais ou menos adequados dependendo dos requisitos de consistência e disponibilidade do sistema. Entender por que o cache funciona, como vimos aqui, é o que torna possível escolher o padrão certo para cada contexto.
