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

Requisitos não funcionais

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.

GrandezaCálculoResultado
Resoluções por diasuposto100 milhões
Taxa média100 000 000 ÷ 86 400 scerca de 1 160 por segundo
Pico (3× a média, uma razão suposta)1 160 × 3cerca de 3 500 por segundo
Nomes armazenadossuposto250 milhões
Tamanho de um registrosuposto ~300 bytes (chave, URL, estado, um pouco de metadados)cerca de 75 GB no total
Registros e atualizaçõessupostos 5 milhões por mês ÷ (30 × 86 400 s)cerca de 2 escritas por segundo
Razão leitura/escrita1 160 ÷ 1,9cerca 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

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):

TesteResultado
Três grafias de um nomea mesma chave e o mesmo redirecionamento
1 000 consultas repetidas de um nome0 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 depoiso destino novo
O mesmo, com um evento de invalidação explícitoo destino novo imediatamente
Um nome pedido antes de ser registrado, depois registrado, depois pedido de novoainda 404 até o TTL negativo de 10 s acabar, depois 302
Entrada inválida e um nome desconhecido400 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 caiua resposta expirada ainda é servida (stale-if-error)
O armazenamento está fora do ar e o nome nunca esteve em cache503 com Retry-After, não uma resposta errada
50 requisições simultâneas por um nome frio, a leitura no armazenamento leva 0,2 s1 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:

CamadaControlada porVida típicaCompartilhada por
NavegadorCache-Control no 302segundos a minutosum usuário
Borda / CDNCache-Control, s-maxagesegundos a minutostodos os usuários de uma região
Memória do resolvedoro TTL no códigodezenas de segundostodas as requisições àquela instância
Armazenamento (page cache, réplicas)o banco de dadosautomáticatudo atrás dele

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

TTLLeituras do armazenamento poupadasObsolescência depois de uma atualização sem invalidação
10 smodestasno máximo 10 s
60 sgrandesno máximo 1 minuto
1 horaquase todas as repetiçõesno 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 shardShard mais ocupado, como múltiplo da médiaMais quieto
Hash do prefixo2,60×0,36×
Hash do nome normalizado inteiro1,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.

  1. 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.
  2. Valide o nome e a URL. Normalize o nome; aceite apenas URLs http e https; limite o comprimento; rejeite credenciais na URL (https://user:pass@host).
  3. Lock otimista. A requisição leva a version que leu; uma divergência é um 409, de modo que dois operadores não possam se sobrescrever em silêncio.
  4. Uma transação: atualize o registro, acrescente a doi_history e 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).
  5. 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.
  6. 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

FalhaO que acontecePor que é seguro
O site de uma editora está fora do arA resolução não é afetada: o resolvedor redireciona sem contatá-lo. O leitor vê o erro da editoraO resolvedor nunca depende dos destinos
O armazenamento de registros está inalcançávelOs resolvedores continuam respondendo do cache, inclusive com entradas expiradas (stale-if-error); nomes sem cache recebem 503 com um Retry-After curtoA maior parte do tráfego é de nomes populares
Uma instância do resolvedor morreO balanceador de carga a retira; as outras atendem o tráfegoSem estado; o cache se reabastece
O fluxo de eventos atrasaAs entradas envelhecem até o TTL em vez de serem invalidadasO TTL limita a obsolescência
Uma região é perdidaO DNS ou o anycast envia o tráfego a outra região com suas próprias réplicas e cachesAs leituras são servidas localmente
Um scraper percorre o espaço de nomesCache negativo e um limite de taxa por cliente; os 404 são baratosAs respostas de não encontrado também ficam em cache
A chave de um registrante vazaO histórico mostra cada mudança; reverta a partir de doi_history; revogue a chaveTrilha 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.

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:

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:

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

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.

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

Resumo rápido

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

  1. IETF, RFC 9110: HTTP Semantics (códigos de status de redirecionamento) e RFC 9111: HTTP Caching.
  2. Crossref, Content negotiation. Valores de Accept suportados e o redirecionamento pelo resolvedor de DOI.
  3. Rajesh Nishtala e outros, Scaling Memcache at Facebook, NSDI 2013. Seção 3.2.1: leases contra sets obsoletos e thundering herds.
  4. M. Nottingham, RFC 5861: HTTP Cache-Control Extensions for Stale Content (stale-while-revalidate, stale-if-error).
  5. 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.
  6. David Karger e outros, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, STOC 1997.
  7. 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

Mais guias