CS Fundamentals Trainer · Guias
Projetando um resolvedor de DOI
Um serviço de redirecionamento de leitura intensiva que precisa sobreviver aos sites para os quais aponta: o caminho de consulta em Python e Go, um cache com TTL testado e uma simulação de taxa de acerto Zipf, por que fazer sharding por prefixo cria shards quentes, escritas versionadas, tombstones, um verificador de links seguro e negociação de conteúdo.
37 min de leitura
Quando você clica em um link DOI como https://doi.org/10.1145/362686.362692, algo precisa transformar esse nome no endereço atual da editora e enviar o seu navegador para lá. Esse algo é um resolvedor, e é um dos serviços mais simples de projetar e um dos mais difíceis de operar bem: a lógica é uma consulta a um dicionário e um redirecionamento, a carga é enorme e de leitura intensiva, os dados mudam devagar mas precisam mudar corretamente, e todo o sentido do serviço é continuar funcionando quando os sites para os quais ele aponta não funcionam. Este guia projeta um: os requisitos, os números, o caminho de consulta, o cache (com um teste em navegador real do que fica em cache), o sharding, o caminho de escrita, os modos de falha, a verificação de links e a negociação de conteúdo. Ele se apoia em Identificadores persistentes e link rot, que explica o que é um DOI; leia esse primeiro se a ideia de um nome estável for nova. Também compartilha ideias com o guia do encurtador de URL, com a diferença de que um encurtador pode perder links e este serviço não pode.
1. O que estamos construindo
Requisitos funcionais
- Resolver: dado um nome (
10.1145/362686.362692, em qualquer uma de suas grafias comuns), redirecionar para o endereço registrado. - Devolver metadados em vez de um redirecionamento quando o cliente pede um formato legível por máquina (negociação de conteúdo).
- Registrar e atualizar: registrantes autorizados criam nomes e mudam para onde apontam.
- Dizer "removido" do jeito certo: um item removido responde com um tombstone, não com um erro genérico.
Requisitos não funcionais
- Alta disponibilidade. Milhões de citações, artigos e ferramentas dependem dele. Precisa funcionar quando qualquer editora está fora do ar; depende apenas dos seus próprios dados.
- Baixa latência. Fica na frente de cada clique, então 200 ms a mais são pagos por todo leitor.
- Correção das atualizações. Quando um registrante corrige um destino, os leitores precisam ver a correção logo.
- Resistência a abusos. Scrapers enumeram nomes, clientes com bugs fazem retry em laços.
- Durabilidade e histórico. Um mapeamento é uma promessa; mantenha uma trilha de auditoria de cada mudança.
Resolver e registrar são serviços diferentes, com formas diferentes: resolver são milhões de leituras que podem ser respondidas por um cache; registrar é um fio de escritas autenticadas que precisam ser validadas. Projete-os separadamente, ligados por um fluxo de eventos de mudança.
Números de guardanapo
Estas são suposições para um serviço deste tipo, não números de nenhum resolvedor real; substitua-as pelas suas.
| Grandeza | Cálculo | Resultado |
|---|---|---|
| Resoluções por dia | suposto | 100 milhões |
| Taxa média | 100 000 000 ÷ 86 400 s | cerca de 1 160 por segundo |
| Pico (3× a média, uma razão suposta) | 1 160 × 3 | cerca de 3 500 por segundo |
| Nomes armazenados | suposto | 250 milhões |
| Tamanho de um registro | suposto ~300 bytes (chave, URL, estado, um pouco de metadados) | cerca de 75 GB no total |
| Registros e atualizações | supostos 5 milhões por mês ÷ (30 × 86 400 s) | cerca de 2 escritas por segundo |
| Razão leitura/escrita | 1 160 ÷ 1,9 | cerca de 600 para 1 |
Três conclusões decorrem. Os dados são pequenos: 75 GB cabem em uma máquina grande ou em um punhado de pequenas, então isso não é um problema de big data. A carga é fácil por segundo, mas implacável: alguns milhares de consultas por segundo não são nada para um cache, e tudo se resume a estar disponível e rápido para cada uma delas. As escritas são raras, então podemos nos dar ao luxo de fazer cada uma com cuidado (validada, auditada, versionada) e de empurrar o trabalho para os caches dos leitores.
2. A API
GET /{doi} resolve (any spelling of the name)
Accept: text/html -> 302 Found, Location: the registered address
Accept: application/vnd.citationstyles.csl+json (or BibTeX, RIS…) -> 200 with metadata
unknown name -> 404 (a human page, short cache)
removed item -> 410 Gone (a tombstone page)
not a DOI -> 400
HEAD /{doi} same status and headers, no body
PUT /admin/dois/{doi} create or update { "url": "...", "version": 7, "metadata": {...} }
authenticated; the caller must own the prefix; 409 if "version" is stale
DELETE /admin/dois/{doi} turn it into a tombstone (never a hard delete)
Note o que a API pública não faz: ela nunca busca o destino. A resposta do resolvedor depende apenas da sua própria tabela, o que o torna independente da disponibilidade das editoras.
3. A arquitetura
Diagram: The resolver: reads come from caches, writes go through a validated path
- Cache de borda: responde nomes populares sem chegar ao resolvedor.
- Instâncias do resolvedor: sem estado; cada uma tem um cache em memória. Como não têm estado, qualquer instância pode responder, e uma nova não precisa de aquecimento além de o cache se encher.
- Tabela de prefixos: a tabela pequena, de mudança lenta, que mapeia cada prefixo (
10.1145) para o seu registrante ou agência. É pequena o bastante para ficar em memória em todo lugar e é usada para a autorização das escritas e para o roteamento (por exemplo, para o serviço de metadados da agência certa). - Armazenamento de registros: os dados chave-valor autoritativos, com sharding por um hash do nome normalizado, com réplicas de leitura.
- API de registro: o único escritor. Valida, escreve no armazenamento e emite um evento.
- Log de mudanças: um fluxo ordenado de eventos "este nome agora aponta para cá". Os resolvedores e a borda o assinam para descartar entradas obsoletas (filas de mensagens e garantias de entrega).
- Verificador de links: um crawler em segundo plano que visita os endereços registrados (seção 9).
Como isto difere do sistema DOI real
Este é um projeto didático com um operador e um armazenamento. O sistema DOI real é federado. Roda sobre o Handle System, em que um cliente primeiro pergunta ao Global Handle Registry qual serviço é responsável pelo prefixo do nome (a autoridade de nomes), depois pergunta a esse Local Handle Service pelo registro, e clientes e proxies podem guardar em cache as informações do serviço para que as consultas seguintes pulem o passo global (a RFC 3650 descreve isso [5]). Além disso, as agências de registro (Crossref, DataCite e outras) registram nomes sob prefixos e guardam os metadados, e o proxy doi.org dá aos clientes web comuns uma entrada HTTP simples. Então, na realidade, os registros vivem nos serviços das agências, não em uma única tabela. O que se transfere para o caso federado é tudo sobre cache, TTLs, invalidação, escritas seguras e tratamento de falhas; o que muda é que a consulta ganha um passo de roteamento (prefixo para o serviço responsável), e o resolvedor também precisa lidar com a disponibilidade e a consistência desses serviços, que ele não controla. Trate a versão de armazenamento único como o núcleo que você poria na frente de cada serviço, ou dentro dele.
4. O caminho de consulta
Toda resolução faz as mesmas quatro coisas: normaliza o nome em uma chave, consulta (cache, depois armazenamento), decide o status e responde. Escrevi o núcleo e o testei; o código está abaixo em Python e Go (escolha uma linguagem; sua escolha é lembrada). Os arquivos do apêndice são completos e executáveis.
def key_of(raw):
"""The one key every layer uses: no scheme or host, decoded, lower case (DOIs ignore case)."""
s = re.sub(r"^(?:https?://(?:dx\.)?doi\.org/|doi:\s*)", "", raw.strip(), flags=re.I)
s = unquote(s).lower()
return s if DOI.match(s) else None
class StoreDown(Exception):
pass
# ... TTLCache: an LRU where each entry expires (ttl), misses are remembered briefly (neg_ttl),
# and get_stale() can still return an expired entry ...
class Resolver:
def __init__(self, store, cache):
self.store, self.cache, self.store_reads = store, cache, 0
self.lock = threading.Lock() # guards the cache and the in-flight table
self.inflight = {} # key -> Event, for a store read already under way
def _fresh(self, key):
with self.lock: return self.cache.get(key)
def _stale_or_fail(self, key): # stale-if-error: an old answer beats no answer
with self.lock: hit, rec = self.cache.get_stale(key)
if hit: return rec
raise StoreDown(key)
def lookup(self, key):
hit, rec = self._fresh(key)
if hit: return rec
with self.lock:
ev = self.inflight.get(key)
leader = ev is None
if leader: ev = self.inflight[key] = threading.Event()
if not leader: # request coalescing: wait for the read that is already running
ev.wait()
hit, rec = self._fresh(key)
return rec if hit else self._stale_or_fail(key)
try:
with self.lock: self.store_reads += 1
rec = self.store.get(key) # the slow, authoritative read; may raise StoreDown
rec = dict(rec) if rec else None # a real database hands back a copy, not its own object
with self.lock: self.cache.put(key, rec)
return rec
except StoreDown:
return self._stale_or_fail(key)
finally:
with self.lock: self.inflight.pop(key, None)
ev.set()
def handle(self, raw_doi, accept="text/html"):
key = key_of(raw_doi)
if key is None:
return 400, {}, b"not a DOI"
try:
rec = self.lookup(key)
except StoreDown:
return 503, {"Retry-After": "5"}, b"temporarily unavailable"
if rec is None: # the browser and the edge may remember a 404 for exactly as long as we do
return 404, {"Cache-Control": f"max-age={self.cache.neg_ttl}"}, b"DOI not found"
if "citationstyles.csl+json" in accept: # same name, different representation
return 200, {"Content-Type": "application/vnd.citationstyles.csl+json", "Vary": "Accept"}, json.dumps(
{"DOI": key, "title": rec["title"], "URL": "https://doi.org/" + key}).encode()
return 302, {"Location": rec["url"], "Vary": "Accept", "Cache-Control": f"max-age={self.cache.ttl}"}, b""
// keyOf is the one key every layer uses: no scheme or host, decoded, lower case.
func keyOf(raw string) (string, bool) {
s := prefixRe.ReplaceAllString(strings.TrimSpace(raw), "")
if d, err := url.PathUnescape(s); err == nil {
s = d
}
s = strings.ToLower(s)
return s, doiRe.MatchString(s)
}
// ... Cache: an LRU where each entry expires (ttl), misses are remembered briefly (neg),
// and GetStale can still return an expired entry ...
type Store interface {
Get(key string) (string, error)
}
type call struct{ done chan struct{} } // a store read that is already under way
type Resolver struct {
store Store
cache *Cache
mu sync.Mutex
inflight map[string]*call
storeReads int
}
func NewResolver(s Store, c *Cache) *Resolver {
return &Resolver{store: s, cache: c, inflight: map[string]*call{}}
}
func (r *Resolver) staleOrFail(k string) (string, error) { // stale-if-error: an old answer beats no answer
r.mu.Lock()
defer r.mu.Unlock()
if u, ok := r.cache.GetStale(k); ok {
return u, nil
}
return "", ErrStoreDown
}
func (r *Resolver) lookup(k string) (string, error) {
r.mu.Lock()
if u, ok := r.cache.Get(k); ok {
r.mu.Unlock()
return u, nil
}
if c, running := r.inflight[k]; running { // request coalescing: wait for the read that is already running
r.mu.Unlock()
<-c.done
r.mu.Lock()
u, ok := r.cache.Get(k)
r.mu.Unlock()
if ok {
return u, nil
}
return r.staleOrFail(k)
}
c := &call{done: make(chan struct{})}
r.inflight[k] = c
r.storeReads++
r.mu.Unlock()
u, err := r.store.Get(k) // the slow, authoritative read, outside the lock
r.mu.Lock()
if err == nil {
r.cache.Put(k, u)
}
delete(r.inflight, k)
r.mu.Unlock()
close(c.done)
if err != nil {
return r.staleOrFail(k)
}
return u, nil
}
// Handle returns the HTTP status and the Location header (302 means "go there").
func (r *Resolver) Handle(raw string) (int, string) {
k, ok := keyOf(raw)
if !ok {
return 400, ""
}
u, err := r.lookup(k)
switch {
case err != nil:
return 503, ""
case u == "":
return 404, ""
}
return 302, u
}
A normalização vem primeiro e não é opcional: HTTPS://DOI.ORG/10.1145/ABC, doi:10.1145/abc e 10.1145/abc precisam cair na mesma chave, ou cada grafia ganha a sua própria entrada de cache e a sua própria leitura no armazenamento. A função de chave mora em um só lugar e toda camada (regras de borda, resolvedor, API de registro) a usa.
Os dois comportamentos que mais importam sob carga estão no código, não só descritos: a coalescência de requisições (quando muitas requisições dão miss ao mesmo tempo no mesmo nome frio, uma lê o armazenamento e as demais esperam pela sua resposta) e o stale-if-error (quando o armazenamento está inalcançável, uma resposta expirada é melhor que nenhuma). O que verifiquei com um teste (com o relógio substituído por uma variável para que o tempo possa ser avançado sob demanda):
| Teste | Resultado |
|---|---|
| Três grafias de um nome | a mesma chave e o mesmo redirecionamento |
| 1 000 consultas repetidas de um nome | 0 leituras extras no armazenamento |
| A editora muda o destino, 30 s depois (TTL 60 s) | o resolvedor ainda responde com o destino antigo |
| O mesmo, 61 s depois | o destino novo |
| O mesmo, com um evento de invalidação explícito | o destino novo imediatamente |
| Um nome pedido antes de ser registrado, depois registrado, depois pedido de novo | ainda 404 até o TTL negativo de 10 s acabar, depois 302 |
| Entrada inválida e um nome desconhecido | 400 e 404; o 404 leva Cache-Control: max-age=10, igual ao TTL negativo, de modo que um navegador ou cache de borda não pode guardá-lo por mais tempo que o resolvedor |
| O TTL passou e o armazenamento caiu | a resposta expirada ainda é servida (stale-if-error) |
| O armazenamento está fora do ar e o nome nunca esteve em cache | 503 com Retry-After, não uma resposta errada |
| 50 requisições simultâneas por um nome frio, a leitura no armazenamento leva 0,2 s | 1 leitura no armazenamento, 50 redirecionamentos corretos (coalescência) |
A tabela mostra a forma da troca neste projeto: o TTL do cache é o limite superior de quão obsoleta uma resposta pode ser, e um evento de invalidação reduz esse limite ao tempo de viagem do evento.
5. Cache: onde, por quanto tempo e quão bem funciona
Há quatro lugares em que uma resposta pode ficar em cache, cada um com o seu controle:
| Camada | Controlada por | Vida típica | Compartilhada por |
|---|---|---|---|
| Navegador | Cache-Control no 302 | segundos a minutos | um usuário |
| Borda / CDN | Cache-Control, s-maxage | segundos a minutos | todos os usuários de uma região |
| Memória do resolvedor | o TTL no código | dezenas de segundos | todas as requisições àquela instância |
| Armazenamento (page cache, réplicas) | o banco de dados | automática | tudo atrás dele |
Navegadores: um redirecionamento permanente quebraria as atualizações
No guia complementar medi, em um Chromium real, o que acontece depois que o destino muda: um 301 ou 308 é servido do cache do navegador e o resolvedor nunca vê a segunda visita; um 302 ou 307 volta ao resolvedor e chega ao novo destino; um 302 com Cache-Control: max-age=60 continua errado por até um minuto. A decisão para um resolvedor decorre diretamente: use 302 (ou 307) e defina o max-age de propósito. Um max-age curto reduz o tráfego repetido do mesmo navegador, e custa essa mesma quantidade de obsolescência para quem visitou logo antes de uma atualização.
Quanto um cache ajuda?
Depende de quão assimétrica é a popularidade, o que não posso saber para o seu tráfego. Para ver a faixa, simulei um cache LRU com requisições tiradas de uma distribuição Zipf (poucos nomes são pedidos com muita frequência, a maioria quase nunca) sobre 1 milhão de nomes, 2 milhões de requisições, começando com o cache vazio:
| Tamanho do cache (parcela de todos os nomes) | Taxa de acerto, assimetria leve (s=0,8) | Moderada (s=1,0) | Forte (s=1,2) |
|---|---|---|---|
| 0,1% (1 000 entradas) | 10,0% | 40,3% | 76,0% |
| 1% (10 000) | 23,1% | 58,4% | 87,4% |
| 5% (50 000) | 38,7% | 71,4% | 92,4% |
| 20% (200 000) | 58,2% | 81,2% | 93,6% |
Leia assim: com a assimetria do mundo real, um cache pequeno remove a maior parte da carga, e as primeiras milhares de entradas valem muito mais que as últimas centenas de milhares; com uma distribuição plana, o cache ajuda pouco e o armazenamento precisa carregar o tráfego. Os números incluem a partida a frio, então um cache aquecido se sai um pouco melhor. O que decide o seu projeto é uma medição, não esta tabela: registre quais nomes são pedidos e ajuste a assimetria antes de escolher os tamanhos de cache.
Escolhendo o TTL
| TTL | Leituras do armazenamento poupadas | Obsolescência depois de uma atualização sem invalidação |
|---|---|---|
| 10 s | modestas | no máximo 10 s |
| 60 s | grandes | no máximo 1 minuto |
| 1 hora | quase todas as repetições | no máximo 1 hora |
Como os registrantes raramente atualizam, um minuto é um padrão confortável, e os eventos de invalidação deixam você aumentar o TTL sem fazer as atualizações parecerem lentas. O TTL negativo (por quanto tempo "não encontrado" é lembrado) deve ser curto, 10 s no meu teste, porque uma pessoa que registra um nome e o tenta logo em seguida espera que funcione, e uma entrada negativa longa faria o nome novo parecer quebrado. A própria resposta 404 leva max-age igual a esse TTL negativo (o código o define a partir da configuração do cache), de modo que navegadores e a borda esquecem o "não encontrado" no máximo quando o resolvedor esquece. O cache negativo ainda vale a pena: os scrapers que enumeram nomes inexistentes, de outro modo, bateriam no armazenamento a cada requisição.
Mais dois problemas de cache aparecem em escala, e os dois são tratados no código da seção 4. Stampede: quando uma entrada muito popular expira, milhares de requisições dão miss ao mesmo tempo e bateriam juntas no armazenamento; o resolvedor deixa uma requisição ler enquanto as outras esperam por ela (no teste, 50 misses simultâneos fizeram uma leitura no armazenamento), a mesma ideia dos leases do artigo do memcache do Facebook [3] e do padrão single-flight em estratégias de cache. Obsoleto em caso de erro: o stale-if-error (RFC 5861) deixa um cache continuar servindo uma resposta expirada enquanto a origem está fora do ar [4]; o resolvedor faz o mesmo com o seu próprio cache, que é exatamente o comportamento que um resolvedor quer. Na borda você obtém o mesmo efeito com as diretivas stale-if-error e stale-while-revalidate na resposta.
6. Armazenamento e sharding
O padrão de acesso é uma consulta por chave primária, então qualquer armazenamento chave-valor ou uma tabela relacional simples serve. Uma versão relacional que executei no PostgreSQL:
CREATE TABLE doi_records (
doi_key text PRIMARY KEY CHECK (doi_key = lower(doi_key) AND doi_key ~ '^10\.[0-9]{4,9}/\S+$'),
prefix text GENERATED ALWAYS AS (split_part(doi_key, '/', 1)) STORED,
url text NOT NULL CHECK (url ~ '^https?://'),
state text NOT NULL DEFAULT 'active' CHECK (state IN ('active', 'tombstone')),
metadata jsonb NOT NULL DEFAULT '{}',
version int NOT NULL DEFAULT 1,
updated_at timestamptz NOT NULL DEFAULT now()
);
CREATE INDEX ON doi_records (prefix);
-- append-only history: who pointed what where, and when (for disputes and rollbacks)
CREATE TABLE doi_history (
id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
doi_key text NOT NULL,
url text NOT NULL,
state text NOT NULL,
changed_by text NOT NULL,
changed_at timestamptz NOT NULL DEFAULT now()
);
As restrições CHECK mantêm linhas ruins fora seja o que for que a aplicação faça (uma chave com maiúsculas e minúsculas misturadas é rejeitada; tentei uma). A coluna version serve a um lock otimista: UPDATE … WHERE doi_key = $1 AND version = $3 altera a linha apenas se ninguém a alterou desde que você a leu. Testei: com o registro na versão 2, uma atualização que carrega version = 2 alterou 1 linha; uma atualização que carregava o agora obsoleto 2 um instante depois alterou 0 linhas, o que a API relata como 409.
Faça sharding pelo nome inteiro, não pelo prefixo
Os prefixos parecem uma chave de shard natural, já que o prefixo encaminha o nome ao seu registrante. São uma má escolha, porque alguns registrantes são donos de uma parcela muito grande de todos os nomes. Modelei 2 milhões de nomes em 2 000 prefixos com uma popularidade Zipf (s=1) suposta dos prefixos, em 16 shards:
| Chave de shard | Shard mais ocupado, como múltiplo da média | Mais quieto |
|---|---|---|
| Hash do prefixo | 2,60× | 0,36× |
| Hash do nome normalizado inteiro | 1,01× | 1,00× |
Fazer o hash do nome inteiro espalha os nomes uniformemente e não custa nada, porque as consultas sempre têm o nome completo. Use consistent hashing para que adicionar um shard mova apenas uma fração das chaves. (A distribuição dos prefixos reais é uma suposição neste modelo; meça a sua. A conclusão só precisa de uma assimetria, não desta exata.)
A replicação é assíncrona para réplicas de leitura. Uma réplica atrasada em um segundo responde com o destino anterior, o que não é pior que um cache obsoleto em um segundo. Para um resolvedor, servir uma resposta ligeiramente antiga é o lado certo da troca do CAP: disponibilidade para leituras, consistência forte apenas no caminho de escrita.
7. Escritas: registro e atualizações
O caminho de escrita é lento, cuidadoso e raro, então gaste as verificações aqui e mantenha o caminho de leitura trivial.
- Autentique e autorize. Quem chama é um registrante ou agência; a tabela de prefixos diz quais prefixos ele possui; um pedido por um nome sob o prefixo de outro recebe 403.
- Valide o nome e a URL. Normalize o nome; aceite apenas URLs
httpehttps; limite o comprimento; rejeite credenciais na URL (https://user:pass@host). - Lock otimista. A requisição leva a
versionque leu; uma divergência é um 409, de modo que dois operadores não possam se sobrescrever em silêncio. - Uma transação: atualize o registro, acrescente a
doi_historye escreva uma linha de outbox com o evento. Confirmar as três juntas significa que o evento existe se e somente se a mudança existe (o padrão transactional outbox; veja filas de mensagens). - Publique o evento a partir do outbox. Os resolvedores e a borda descartam a entrada; a entrega é at-least-once, e descartar uma entrada duas vezes é inofensivo.
- Limite a taxa por registrante (rate limiter) e registre em log toda mudança com quem a fez.
Nunca faça hard delete. Um pedido de exclusão vira state = 'tombstone', de modo que o nome continua existindo, resolve para uma página "este item foi removido" com status 410, e ninguém mais poderá registrar o mesmo nome.
8. Disponibilidade e modos de falha
| Falha | O que acontece | Por que é seguro |
|---|---|---|
| O site de uma editora está fora do ar | A resolução não é afetada: o resolvedor redireciona sem contatá-lo. O leitor vê o erro da editora | O resolvedor nunca depende dos destinos |
| O armazenamento de registros está inalcançável | Os resolvedores continuam respondendo do cache, inclusive com entradas expiradas (stale-if-error); nomes sem cache recebem 503 com um Retry-After curto | A maior parte do tráfego é de nomes populares |
| Uma instância do resolvedor morre | O balanceador de carga a retira; as outras atendem o tráfego | Sem estado; o cache se reabastece |
| O fluxo de eventos atrasa | As entradas envelhecem até o TTL em vez de serem invalidadas | O TTL limita a obsolescência |
| Uma região é perdida | O DNS ou o anycast envia o tráfego a outra região com suas próprias réplicas e caches | As leituras são servidas localmente |
| Um scraper percorre o espaço de nomes | Cache negativo e um limite de taxa por cliente; os 404 são baratos | As respostas de não encontrado também ficam em cache |
| A chave de um registrante vaza | O histórico mostra cada mudança; reverta a partir de doi_history; revogue a chave | Trilha de auditoria somente de acréscimo |
Ponha as instâncias atrás de um balanceador de carga com health checks, rode em pelo menos duas regiões e mantenha leituras sem dependências como regra: uma instância do resolvedor deve conseguir responder da sua memória com o banco de dados desligado.
9. Saúde dos links e tombstones
Um mapeamento que aponta para uma página morta ainda é um link quebrado. Um verificador de links os encontra. É um pequeno crawler com as mesmas regras de polidez:
- Visite cada endereço registrado periodicamente com uma requisição
HEAD(recuando paraGET), um timeout curto e um limite de redirecionamentos, no máximo uma requisição por vez por host e umUser-Agentdescritivo. - Registre o resultado com um timestamp; uma única falha é ruído, então aja depois de várias seguidas ao longo de dias.
- Não reescreva o mapeamento automaticamente. Avise o registrante, mostre-lhe o histórico e deixe-o consertar. Depois de um longo período de falha, uma agência pode decidir apontar o nome para um tombstone ou para uma cópia arquivada.
- SSRF: o verificador busca endereços que estranhos digitaram, então precisa recusar endereços privados e internos (loopback, link-local, faixas internas), limitar redirecionamentos e rodar em um segmento de rede que não alcance os serviços internos. Um registrante que consegue fazer o seu servidor buscar
http://169.254.169.254/encontrou uma brecha.
10. Negociação de conteúdo e metadados
O mesmo nome precisa atender um navegador (redirecionamento) e uma ferramenta de citação (metadados). O resolvedor olha o cabeçalho Accept: text/html recebe o 302; os tipos de metadados (CSL JSON, BibTeX, RIS e outros, veja o guia complementar) são tratados por um serviço de metadados, que pode ser um deployment separado porque sua carga e seus dados são diferentes. Dois detalhes importam para os caches. Envie Vary: Accept, para que um cache compartilhado guarde uma entrada por representação. E normalize o Accept na borda para um pequeno conjunto de valores antes que ele entre na chave de cache, porque os clientes enviam muitos cabeçalhos Accept quase idênticos (valores de qualidade diferentes, ordens diferentes) e cada string distinta seria, de outro modo, uma entrada de cache separada.
11. Observabilidade e testes
Meça o que lhe diz que o projeto está funcionando:
- Taxa de acerto do cache em cada camada e leituras do armazenamento por segundo (o número que deve ficar plano quando o tráfego cresce).
- Percentis de latência (p50, p99) do próprio resolvedor, separados da rede.
- Taxa de 404 (um pico significa um scraper ou uma integração quebrada) e de 5xx.
- Obsolescência: o tempo de uma atualização confirmada até o último cache descartar a entrada antiga (lag de invalidação).
- Resultados da verificação de links: a parcela de endereços registrados que falham, por registrante.
Teste as peças isoladamente: o normalizador com uma tabela de grafias (e um teste de propriedade de que normalizar duas vezes não muda nada), o cache com um relógio injetado (como acima), o caminho de atualização com dois escritores concorrentes (exatamente um tem sucesso) e o serviço inteiro com um armazenamento falso que cai.
12. Erros comuns
- Responder com um 301. Navegadores e proxies o guardam, então as atualizações nunca chegam a eles (medido).
- Buscar o destino para "conferi-lo" a cada requisição. O resolvedor então falha quando a editora falha.
- Guardar "não encontrado" em cache por muito tempo, de modo que um registro novo pareça quebrado.
- Fazer sharding por prefixo, o que cria shards quentes (2,6× a média no meu modelo).
- Pular a normalização, o que divide um nome entre várias entradas de cache.
- Apagar nomes de verdade (hard delete), de modo que possam ser registrados por outra pessoa depois.
- Nenhum histórico, de modo que uma atualização errada ou maliciosa não pode ser rastreada nem revertida.
- Deixar o verificador de links buscar qualquer coisa que um registrante digite (SSRF).
- Deixar o cache crescer sem limite ou esquecer o
Vary: Accept.
13. Perguntas que os entrevistadores gostam de acrescentar
"Como você o mantém no ar quando o banco de dados está fora?"
Sirva dos caches em memória e de borda, inclusive entradas expiradas (stale-if-error), e responda 503 com um Retry-After curto apenas para nomes que nunca estiveram em cache. Os nomes populares são a maior parte do tráfego.
"Com que rapidez uma atualização se torna visível?"
No máximo o TTL (cerca de um minuto aqui) sem invalidação; com um evento de invalidação, o tempo que o evento leva para chegar aos caches. O próprio max-age do navegador soma a isso para quem acabou de visitar.
"Por que não tornar o mapeamento imutável e guardá-lo em cache para sempre?"
Porque o mapeamento é o produto inteiro: os registrantes precisam poder corrigir um endereço movido ou quebrado. Um mapeamento imutável é um encurtador de URL que nunca pode consertar um link.
"Como você faria o sharding?"
Por um hash do nome normalizado inteiro, com consistent hashing. O sharding por prefixo cria shards quentes porque poucos registrantes são donos da maioria dos nomes.
"Como você impede dois operadores de se sobrescreverem?"
Um lock otimista: a atualização leva a versão que leu e só tem sucesso se ainda coincidir; caso contrário, 409 e o operador recarrega.
"Como você encontraria links mortos sem martelar as editoras?"
Um verificador educado em segundo plano: limites de taxa por host, requisições HEAD, um intervalo longo, backoff e ação apenas depois de falhas repetidas, com o registrante avisado e nada alterado automaticamente.
"O que mudaria com 100 vezes o tráfego?"
Mais cache de borda e uma taxa de acerto de borda maior (a alavanca mais barata), mais instâncias do resolvedor (sem estado), mais réplicas e possivelmente uma segunda camada de cache. O armazenamento quase não muda porque o cache absorve a carga.
14. Coisas a mencionar em uma entrevista
- Leitura intensiva, dados pequenos, mudança lenta: resolver e registrar são serviços separados.
- 302/307 com cabeçalhos de cache deliberados, porque o mapeamento precisa poder mudar.
- O TTL do cache limita a obsolescência; os eventos de invalidação a reduzem; as entradas negativas precisam de um TTL curto.
- Nunca depender do destino; stale-if-error para o armazenamento.
- Sharding por hash do nome inteiro, com consistent hashing.
- Escritas: autorizar por prefixo, validar, lock otimista, histórico, evento de outbox, limite de taxa.
- Tombstones e 410, nunca hard deletes.
- Verificador de links: educado, seguro contra SSRF, nunca reescreve automaticamente.
- Negociação de conteúdo com
Vary: Accepte umAcceptnormalizado na chave de cache.
Resumo rápido
- Um resolvedor transforma um nome estável no endereço atual com um redirecionamento. Precisa continuar no ar quando as editoras não estão, então nunca as contata no caminho de leitura.
- A carga é de leitura intensiva (cerca de 600 leituras por escrita nos números de exemplo) e os dados são pequenos (cerca de 75 GB), então os caches fazem a maior parte do trabalho.
- Use 302 ou 307: um navegador real manteve um 301 ou 308 depois de o destino mudar e continuou enviando os leitores ao lugar antigo.
- O TTL é o limite de obsolescência; os eventos de invalidação o encurtam; lembre "não encontrado" por apenas alguns segundos.
- Um cache pequeno ajuda muito sob tráfego assimétrico: com 1% dos nomes em cache, a taxa de acerto simulada foi de 23% para assimetria leve, 58% para moderada e 87% para forte, então meça a sua assimetria antes de dimensioná-lo.
- Faça sharding por um hash do nome inteiro: por prefixo, o shard mais ocupado carregou 2,6 vezes a carga média no modelo.
- As escritas são autorizadas por prefixo, validadas, versionadas e auditadas; as exclusões viram tombstones.
- Um verificador de links educado e seguro contra SSRF encontra destinos mortos e avisa o registrante.
Apêndice: o código dos experimentos
Biblioteca padrão do Python 3. O resolver.py executa as suas próprias asserções (python3 resolver.py), o zipf.py e o shard.py imprimem as duas tabelas, e o arquivo Go roda com go run main.go. Tempos e taxas de acerto vêm da minha execução; as simulações usam sementes fixas.
resolver.py: normalização, cache com TTL e entradas negativas, o resolvedor e os testes da seção 4:
import re, time, json, threading, collections
from urllib.parse import unquote
DOI = re.compile(r"^10\.\d{4,9}/\S+$")
def key_of(raw):
"""The one key every layer uses: no scheme or host, decoded, lower case (DOIs ignore case)."""
s = re.sub(r"^(?:https?://(?:dx\.)?doi\.org/|doi:\s*)", "", raw.strip(), flags=re.I)
s = unquote(s).lower()
return s if DOI.match(s) else None
class StoreDown(Exception):
pass
class TTLCache:
"""LRU with a time-to-live per entry; a miss can be remembered too (negative caching).
Expired entries stay until evicted, so they can still be served when the store is down."""
def __init__(self, capacity, ttl, neg_ttl, clock=time.monotonic):
self.cap, self.ttl, self.neg_ttl, self.clock = capacity, ttl, neg_ttl, clock
self.d = collections.OrderedDict() # key -> (expires_at, value or None)
def get(self, key): # fresh entries only
item = self.d.get(key)
if item is None or item[0] <= self.clock():
return False, None
self.d.move_to_end(key); return True, item[1]
def get_stale(self, key): # any entry, even an expired one
item = self.d.get(key)
return (False, None) if item is None else (True, item[1])
def put(self, key, value):
self.d[key] = (self.clock() + (self.ttl if value is not None else self.neg_ttl), value)
self.d.move_to_end(key)
while len(self.d) > self.cap: self.d.popitem(last=False)
def invalidate(self, key): self.d.pop(key, None)
class Resolver:
def __init__(self, store, cache):
self.store, self.cache, self.store_reads = store, cache, 0
self.lock = threading.Lock() # guards the cache and the in-flight table
self.inflight = {} # key -> Event, for a store read already under way
def _fresh(self, key):
with self.lock: return self.cache.get(key)
def _stale_or_fail(self, key): # stale-if-error: an old answer beats no answer
with self.lock: hit, rec = self.cache.get_stale(key)
if hit: return rec
raise StoreDown(key)
def lookup(self, key):
hit, rec = self._fresh(key)
if hit: return rec
with self.lock:
ev = self.inflight.get(key)
leader = ev is None
if leader: ev = self.inflight[key] = threading.Event()
if not leader: # request coalescing: wait for the read that is already running
ev.wait()
hit, rec = self._fresh(key)
return rec if hit else self._stale_or_fail(key)
try:
with self.lock: self.store_reads += 1
rec = self.store.get(key) # the slow, authoritative read; may raise StoreDown
rec = dict(rec) if rec else None # a real database hands back a copy, not its own object
with self.lock: self.cache.put(key, rec)
return rec
except StoreDown:
return self._stale_or_fail(key)
finally:
with self.lock: self.inflight.pop(key, None)
ev.set()
def handle(self, raw_doi, accept="text/html"):
key = key_of(raw_doi)
if key is None:
return 400, {}, b"not a DOI"
try:
rec = self.lookup(key)
except StoreDown:
return 503, {"Retry-After": "5"}, b"temporarily unavailable"
if rec is None: # the browser and the edge may remember a 404 for exactly as long as we do
return 404, {"Cache-Control": f"max-age={self.cache.neg_ttl}"}, b"DOI not found"
if "citationstyles.csl+json" in accept: # same name, different representation
return 200, {"Content-Type": "application/vnd.citationstyles.csl+json", "Vary": "Accept"}, json.dumps(
{"DOI": key, "title": rec["title"], "URL": "https://doi.org/" + key}).encode()
return 302, {"Location": rec["url"], "Vary": "Accept", "Cache-Control": f"max-age={self.cache.ttl}"}, b""
class FakeStore:
"""A stand-in for the database: counts reads, can be slow, can be switched off."""
def __init__(self, data): self.data, self.calls, self.delay, self.down = data, 0, 0.0, False
def get(self, key):
self.calls += 1
if self.delay: time.sleep(self.delay)
if self.down: raise StoreDown("store unreachable")
return self.data.get(key)
if __name__ == "__main__":
now = [0.0]; clock = lambda: now[0]
D = "10.1145/362686.362692"
store = FakeStore({D: {"url": "https://publisher-a.example/bloom", "title": "Space/time trade-offs in hash coding"}})
r = Resolver(store, TTLCache(capacity=1000, ttl=60, neg_ttl=10, clock=clock))
assert key_of("HTTPS://DOI.ORG/10.1145/362686.362692") == D
assert r.handle("doi:" + D)[:2] == (302, {"Location": "https://publisher-a.example/bloom", "Vary": "Accept", "Cache-Control": "max-age=60"})
assert r.handle(D, accept="application/vnd.citationstyles.csl+json")[0] == 200
assert r.handle("nonsense")[0] == 400
status, headers, _ = r.handle("10.1145/nope")
assert (status, headers["Cache-Control"]) == (404, "max-age=10"), "the 404 may be cached downstream for exactly the negative TTL"
reads = store.calls
for _ in range(1000): r.handle(D)
assert store.calls == reads, "1000 repeats must not touch the store" # caching works
store.data[D]["url"] = "https://publisher-b.example/bloom" # the publisher moves the paper
now[0] += 30; assert r.handle(D)[1]["Location"].endswith("publisher-a.example/bloom") # stale inside the TTL
now[0] += 31; assert r.handle(D)[1]["Location"].endswith("publisher-b.example/bloom") # fresh after it
store.data[D]["url"] = "https://publisher-c.example/bloom"
r.cache.invalidate(D) # an update event drops the entry at once
assert r.handle(D)[1]["Location"].endswith("publisher-c.example/bloom")
assert r.handle("10.1145/new")[0] == 404 # asked before it exists: the miss is cached
store.data["10.1145/new"] = {"url": "https://x.example/n", "title": "n"} # then it is registered
assert r.handle("10.1145/new")[0] == 404; now[0] += 11; assert r.handle("10.1145/new")[0] == 302 # visible after the short negative TTL
# stale-if-error: the store goes down after the TTL has passed
now[0] += 61; store.down = True
assert r.handle(D)[:2][0] == 302, "an expired answer is served while the store is down"
assert r.handle("10.1145/never-seen")[0] == 503, "a name that was never cached gets a 503, not a wrong answer"
store.down = False
# request coalescing: 50 simultaneous misses for one cold name make ONE store read
store.data["10.1145/popular"] = {"url": "https://x.example/popular", "title": "p"}; store.delay = 0.2
before = store.calls; results = []
ts = [threading.Thread(target=lambda: results.append(r.handle("10.1145/popular")[0])) for _ in range(50)]
[t.start() for t in ts]; [t.join() for t in ts]
assert results.count(302) == 50 and store.calls - before == 1, (results.count(302), store.calls - before)
print("all resolver checks passed")
main.go: o mesmo resolvedor em Go:
package main
import (
"container/list"
"errors"
"fmt"
"net/url"
"regexp"
"strings"
"sync"
"time"
)
var doiRe = regexp.MustCompile(`^10\.\d{4,9}/\S+$`)
var prefixRe = regexp.MustCompile(`(?i)^(?:https?://(?:dx\.)?doi\.org/|doi:\s*)`)
// keyOf is the one key every layer uses: no scheme or host, decoded, lower case.
func keyOf(raw string) (string, bool) {
s := prefixRe.ReplaceAllString(strings.TrimSpace(raw), "")
if d, err := url.PathUnescape(s); err == nil {
s = d
}
s = strings.ToLower(s)
return s, doiRe.MatchString(s)
}
var ErrStoreDown = errors.New("store unreachable")
type entry struct {
key string
expires time.Time
url string // empty means "known not to exist" (negative entry)
}
// Cache is an LRU whose entries expire. Expired entries stay until evicted so GetStale can still serve them.
// It is not safe for concurrent use; the Resolver guards it with its mutex.
type Cache struct {
cap int
ttl, neg time.Duration
now func() time.Time
ll *list.List
m map[string]*list.Element
}
func NewCache(cap int, ttl, neg time.Duration, now func() time.Time) *Cache {
return &Cache{cap: cap, ttl: ttl, neg: neg, now: now, ll: list.New(), m: map[string]*list.Element{}}
}
func (c *Cache) Get(k string) (string, bool) { // fresh entries only
el, ok := c.m[k]
if !ok || !el.Value.(*entry).expires.After(c.now()) {
return "", false
}
c.ll.MoveToFront(el)
return el.Value.(*entry).url, true
}
func (c *Cache) GetStale(k string) (string, bool) { // any entry, even an expired one
if el, ok := c.m[k]; ok {
return el.Value.(*entry).url, true
}
return "", false
}
func (c *Cache) Put(k, u string) {
ttl := c.ttl
if u == "" {
ttl = c.neg
}
if el, ok := c.m[k]; ok {
c.ll.Remove(el)
}
c.m[k] = c.ll.PushFront(&entry{k, c.now().Add(ttl), u})
for c.ll.Len() > c.cap {
last := c.ll.Back()
c.ll.Remove(last)
delete(c.m, last.Value.(*entry).key)
}
}
func (c *Cache) Invalidate(k string) {
if el, ok := c.m[k]; ok {
c.ll.Remove(el)
delete(c.m, k)
}
}
type Store interface {
Get(key string) (string, error)
}
type call struct{ done chan struct{} } // a store read that is already under way
type Resolver struct {
store Store
cache *Cache
mu sync.Mutex
inflight map[string]*call
storeReads int
}
func NewResolver(s Store, c *Cache) *Resolver {
return &Resolver{store: s, cache: c, inflight: map[string]*call{}}
}
func (r *Resolver) staleOrFail(k string) (string, error) { // stale-if-error: an old answer beats no answer
r.mu.Lock()
defer r.mu.Unlock()
if u, ok := r.cache.GetStale(k); ok {
return u, nil
}
return "", ErrStoreDown
}
func (r *Resolver) lookup(k string) (string, error) {
r.mu.Lock()
if u, ok := r.cache.Get(k); ok {
r.mu.Unlock()
return u, nil
}
if c, running := r.inflight[k]; running { // request coalescing: wait for the read that is already running
r.mu.Unlock()
<-c.done
r.mu.Lock()
u, ok := r.cache.Get(k)
r.mu.Unlock()
if ok {
return u, nil
}
return r.staleOrFail(k)
}
c := &call{done: make(chan struct{})}
r.inflight[k] = c
r.storeReads++
r.mu.Unlock()
u, err := r.store.Get(k) // the slow, authoritative read, outside the lock
r.mu.Lock()
if err == nil {
r.cache.Put(k, u)
}
delete(r.inflight, k)
r.mu.Unlock()
close(c.done)
if err != nil {
return r.staleOrFail(k)
}
return u, nil
}
// Handle returns the HTTP status and the Location header (302 means "go there").
func (r *Resolver) Handle(raw string) (int, string) {
k, ok := keyOf(raw)
if !ok {
return 400, ""
}
u, err := r.lookup(k)
switch {
case err != nil:
return 503, ""
case u == "":
return 404, ""
}
return 302, u
}
type fakeStore struct {
mu sync.Mutex
data map[string]string
calls int
delay time.Duration
down bool
}
func (f *fakeStore) Get(k string) (string, error) {
f.mu.Lock()
f.calls++
d, down, v := f.delay, f.down, f.data[k]
f.mu.Unlock()
time.Sleep(d)
if down {
return "", ErrStoreDown
}
return v, nil
}
func must(ok bool, msg string) {
if !ok {
panic(msg)
}
}
func main() {
t0 := time.Unix(0, 0)
now := t0
clock := func() time.Time { return now }
const D = "10.1145/362686.362692"
st := &fakeStore{data: map[string]string{D: "https://publisher-a.example/bloom"}}
r := NewResolver(st, NewCache(1000, 60*time.Second, 10*time.Second, clock))
s, l := r.Handle("HTTPS://DOI.ORG/10.1145/362686.362692")
must(s == 302 && l == "https://publisher-a.example/bloom", "redirect")
reads := st.calls
for i := 0; i < 1000; i++ {
r.Handle(D)
}
must(st.calls == reads, "cache absorbs repeats")
st.data[D] = "https://publisher-b.example/bloom"
now = t0.Add(30 * time.Second)
_, l = r.Handle(D)
must(strings.Contains(l, "publisher-a"), "stale inside the TTL")
now = t0.Add(61 * time.Second)
_, l = r.Handle(D)
must(strings.Contains(l, "publisher-b"), "fresh after the TTL")
must(func() bool { s, _ := r.Handle("nonsense"); return s == 400 }(), "bad input")
// stale-if-error: the store goes down after the TTL has passed
now = t0.Add(200 * time.Second)
st.down = true
s, _ = r.Handle(D)
must(s == 302, "an expired answer is served while the store is down")
s, _ = r.Handle("10.1145/never-seen")
must(s == 503, "a name that was never cached gets a 503")
st.down = false
// request coalescing: 50 simultaneous misses for one cold name make ONE store read
st.data["10.1145/popular"] = "https://x.example/popular"
st.delay = 200 * time.Millisecond
before := st.calls
var wg sync.WaitGroup
var okc int32
var cm sync.Mutex
for i := 0; i < 50; i++ {
wg.Add(1)
go func() {
defer wg.Done()
if s, _ := r.Handle("10.1145/popular"); s == 302 {
cm.Lock()
okc++
cm.Unlock()
}
}()
}
wg.Wait()
must(okc == 50 && st.calls-before == 1, fmt.Sprintf("coalescing: %d ok, %d store reads", okc, st.calls-before))
fmt.Println("all Go resolver checks passed")
}
zipf.py: a simulação de taxa de acerto do cache:
import random, bisect, collections, itertools
rnd=random.Random(3)
K=1_000_000 # distinct DOIs that get resolved in the window
def zipf_sampler(n,s):
cum=list(itertools.accumulate(1/(i**s) for i in range(1,n+1))); tot=cum[-1]
return lambda: bisect.bisect_left(cum, rnd.random()*tot)
class LRU:
def __init__(s,cap): s.cap=cap; s.d=collections.OrderedDict()
def get(s,k):
if k in s.d: s.d.move_to_end(k); return True
s.d[k]=1
if len(s.d)>s.cap: s.d.popitem(last=False)
return False
print("Zipf popularity over %d DOIs, 2,000,000 resolutions, LRU cache sized as a share of the DOIs"%K)
print("cache size (share of DOIs) | s=0.8 | s=1.0 | s=1.2")
res={}
for s in (0.8,1.0,1.2):
draw=zipf_sampler(K,s); seq=[draw() for _ in range(2_000_000)]
for share in (0.001,0.01,0.05,0.2):
c=LRU(int(K*share)); hits=sum(c.get(k) for k in seq); res[(s,share)]=hits/len(seq)
for share in (0.001,0.01,0.05,0.2):
print(f"{share*100:>6.1f}% ({int(K*share):>7} entries) | {100*res[(0.8,share)]:5.1f}% | {100*res[(1.0,share)]:5.1f}% | {100*res[(1.2,share)]:5.1f}%")
shard.py: equilíbrio dos shards por prefixo e por nome inteiro:
import random, hashlib, itertools, bisect, collections
rnd=random.Random(5)
P=2000; N=2_000_000; SHARDS=16
w=[1/(i**1.0) for i in range(1,P+1)]; cum=list(itertools.accumulate(w))
prefix=lambda: bisect.bisect_left(cum, rnd.random()*cum[-1])
h=lambda s:int(hashlib.md5(s.encode()).hexdigest(),16)
by_prefix=collections.Counter(); by_doi=collections.Counter()
for n in range(N):
p=prefix(); doi=f"10.{1000+p}/item{n}"
by_prefix[h(f"10.{1000+p}")%SHARDS]+=1; by_doi[h(doi)%SHARDS]+=1
mean=N/SHARDS
print(f"{N} DOIs over {P} prefixes (Zipf s=1 assumed), {SHARDS} shards; busiest shard as a multiple of the average:")
print(f" sharded by prefix: {max(by_prefix.values())/mean:.2f}x (quietest {min(by_prefix.values())/mean:.2f}x)")
print(f" sharded by hash of the whole DOI: {max(by_doi.values())/mean:.2f}x (quietest {min(by_doi.values())/mean:.2f}x)")
Fontes
- IETF, RFC 9110: HTTP Semantics (códigos de status de redirecionamento) e RFC 9111: HTTP Caching.
- Crossref, Content negotiation. Valores de
Acceptsuportados e o redirecionamento pelo resolvedor de DOI. - Rajesh Nishtala e outros, Scaling Memcache at Facebook, NSDI 2013. Seção 3.2.1: leases contra sets obsoletos e thundering herds.
- M. Nottingham, RFC 5861: HTTP Cache-Control Extensions for Stale Content (
stale-while-revalidate,stale-if-error). - IETF, RFC 3650: Handle System Overview. O Global Handle Registry e os Local Handle Services; a RFC 3651 e a RFC 3652 são as especificações de espaço de nomes e de protocolo.
- David Karger e outros, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, STOC 1997.
- Documentação do PostgreSQL sobre generated columns e restrições
CHECK, usadas na tabela acima (o SQL foi executado no PostgreSQL 16).
Pratique este tema: System Design System Design › Case studies