CS Fundamentals Trainer · Guides

Design a DOI resolver

A read-heavy redirect service that must outlive the sites it points to: the lookup path in Python and Go, a tested TTL cache and a Zipf hit-rate simulation, why sharding by prefix makes hot shards, versioned writes, tombstones, a safe link checker and content negotiation.

35 min read

When you click a DOI link such as https://doi.org/10.1145/362686.362692, something has to turn that name into the publisher's current address and send your browser there. That something is a resolver, and it is one of the simplest services you can design and one of the harder ones to run well: the logic is a dictionary lookup and a redirect, the load is enormous and read-heavy, the data changes slowly but must change correctly, and the whole point of the service is that it keeps working when the sites it points to do not. This guide designs one: the requirements, the numbers, the lookup path, caching (with a real browser test of what gets cached), sharding, the write path, failure modes, link checking and content negotiation. It builds on Persistent identifiers and link rot, which explains what a DOI is; read that first if the idea of a stable name is new. It also shares ideas with the URL shortener guide, with the difference that a shortener may lose links and this service must not.

1. What we are building

Functional requirements

• Resolve: given a name (10.1145/362686.362692, in any of its common spellings), redirect to the registered address.
• Return metadata instead of a redirect when the client asks for a machine-readable format (content negotiation).
• Register and update: authorised registrants create names and change where they point.
• Say "gone" properly: a removed item answers with a tombstone, not a generic error.

Non-functional requirements

• High availability. Millions of citations, articles and tools depend on it. It must work when any publisher is down; it depends only on its own data.
• Low latency. It sits in front of every click, so an extra 200 ms is paid by every reader.
• Correctness of updates. When a registrant fixes a target, readers must soon see the fix.
• Abuse resistance. Scrapers enumerate names, buggy clients retry in loops.
• Durability and history. A mapping is a promise; keep an audit trail of every change.

Resolving and registering are different services with different shapes: resolving is millions of reads that can be answered from a cache; registering is a trickle of authenticated writes that must be validated. Design them separately, joined by a stream of change events.

Back-of-the-envelope numbers

These are assumptions for a service of this kind, not figures for any real resolver; replace them with your own.

Three conclusions follow. The data is small: 75 GB fits on one large machine or a handful of small ones, so this is not a big-data problem. The load is easy per second but unforgiving: a few thousand lookups per second is nothing for a cache, and everything is about being available and fast for every one of them. Writes are rare, so we can afford to make each one careful (validated, audited, versioned) and to push the work to readers' caches.

2. The 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)

Notice what the public API does not do: it never fetches the target. The resolver's answer depends only on its own table, which is what makes it independent of the publishers' uptime.

3. The architecture

Diagram: The resolver: reads come from caches, writes go through a validated path

• Edge cache: answers popular names without reaching the resolver at all.
• Resolver instances: stateless; each holds an in-memory cache. Because they are stateless, any instance can answer, and a new one needs no warm-up beyond the cache filling.
• Prefix table: the small, slow-changing table mapping each prefix (10.1145) to its registrant or agency. It is small enough to keep in memory everywhere and is used for authorisation on writes and for routing (for example, to the metadata service of the right agency).
• Record store: the authoritative key-value data, sharded by a hash of the normalised name, with read replicas.
• Registration API: the only writer. It validates, writes to the store, and emits an event.
• Change log: an ordered stream of "this name now points here" events. Resolvers and the edge subscribe to it to drop stale entries (message queues and delivery guarantees).
• Link checker: a background crawler that visits registered addresses (section 9).

How this differs from the real DOI system

This is a teaching design with one operator and one store. The real DOI system is federated. It runs on the Handle System, in which a client first asks the Global Handle Registry for the service responsible for the name's prefix (the naming authority), then asks that Local Handle Service for the record, and clients and proxies can cache the service information so later lookups skip the global step (RFC 3650 describes this [5]). On top of that, registration agencies (Crossref, DataCite and others) register names under prefixes and keep the metadata, and the doi.org proxy gives ordinary web clients a plain HTTP way in. So in reality the records live with the agencies' services, not in one table. What carries over to the federated case is everything about caching, TTLs, invalidation, safe writes and failure handling; what changes is that the lookup gains a routing step (prefix to responsible service), and the resolver must also cope with the availability and consistency of those services, which it does not control. Treat the single-store version as the core you would put in front of, or inside, each service.

4. The lookup path

Every resolution does the same four things: normalise the name to one key, look it up (cache, then store), decide the status, and answer. I wrote the core and tested it; the code is below in Python and Go (pick a language; your choice is remembered). The files in the appendix are complete and runnable.

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
}

Normalisation comes first and is not optional: HTTPS://DOI.ORG/10.1145/ABC, doi:10.1145/abc and 10.1145/abc must all land on the same key, or each spelling gets its own cache entry and its own store read. The key function lives in one place and every layer (edge rules, resolver, registration API) uses it.

The two behaviours that matter most under load are in the code, not just described: request coalescing (when many requests miss on the same cold name at once, one of them reads the store and the rest wait for its answer) and stale-if-error (when the store is unreachable, an expired answer is better than none). What I checked with a test (with the clock replaced by a variable so that time can be moved on demand):

The table shows the shape of the trade-off in this design: the cache's TTL is the upper bound on how stale an answer can be, and an invalidation event shrinks the bound to the event's travel time.

5. Caching: where, how long, and how well it works

There are four places an answer can be cached, each with its own control:

Browsers: a permanent redirect would break updates

In the companion guide I measured, in a real Chromium, what happens after the target moves: a 301 or 308 is served from the browser's cache and the resolver never sees the second visit; a 302 or 307 goes back to the resolver and reaches the new target; a 302 with Cache-Control: max-age=60 stays wrong for up to a minute. The decision for a resolver follows directly: use 302 (or 307) and set max-age deliberately. A short max-age cuts repeat traffic from the same browser, and costs you that much staleness for people who visited just before an update.

How much does a cache help?

It depends on how skewed the popularity is, which I cannot know for your traffic. To see the range, I simulated an LRU cache with requests drawn from a Zipf distribution (a few names are asked for very often, most hardly ever) over 1 million names, 2 million requests, starting from an empty cache:

Read it this way: with real-world skew a small cache removes most of the load, and the first few thousand entries are worth far more than the last hundred thousand; with a flat distribution, caching helps little and the store must carry the traffic. The numbers include the cold start, so a warmed cache does a little better. What decides your design is a measurement, not this table: log which names are requested and fit the skew before choosing cache sizes.

Choosing the TTL

Because registrants rarely update, a minute is a comfortable default, and invalidation events let you raise the TTL without making updates feel slow. The negative TTL (how long "not found" is remembered) should be short, 10 s in my test, because a person who registers a name and tries it straight away expects it to work, and a long negative entry would make the new name look broken. The 404 response itself carries max-age equal to this negative TTL (the code sets it from the cache's setting), so browsers and the edge forget "not found" no later than the resolver does. Negative caching is still worth having: scrapers that enumerate non-existent names would otherwise hit the store on every request.

Two more cache problems appear at scale, and both are handled in the code of section 4. Stampede: when a very popular entry expires, thousands of requests miss at once and would hit the store together; the resolver lets one request read while the others wait for it (in the test, 50 simultaneous misses made one store read), the same idea as the leases in Facebook's memcache paper [3] and as the single-flight pattern in caching strategies. Stale on error: stale-if-error (RFC 5861) lets a cache keep serving an expired answer while the origin is down [4]; the resolver does the same for its own cache, which is exactly the behaviour a resolver wants. At the edge you get the same effect with the stale-if-error and stale-while-revalidate directives on the response.

6. Storage and sharding

The access pattern is a primary-key lookup, so any key-value store or a plain relational table works. A relational version I ran on 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()
);

The CHECK constraints keep bad rows out whatever the application does (a mixed-case key is rejected; I tried one). The version column is for an optimistic lock: UPDATE … WHERE doi_key = $1 AND version = $3 changes the row only if nobody else changed it since you read it. I tested it: with the record at version 2, an update that carries version = 2 changed 1 row; an update that carried the now-stale 2 a moment later changed 0 rows, which the API reports as 409.

Shard by the whole name, not by the prefix

Prefixes look like a natural shard key, since the prefix routes the name to its registrant. They are a poor one, because a few registrants own a very large share of all names. I modelled 2 million names over 2,000 prefixes with an assumed Zipf (s=1) popularity of prefixes, on 16 shards:

Hashing the whole name spreads names evenly, and costs nothing because lookups always have the full name. Use consistent hashing so adding a shard moves only a fraction of the keys. (The distribution of real prefixes is an assumption in this model; measure yours. The conclusion only needs a skew, not this exact one.)

Replication is asynchronous to read replicas. A replica that is a second behind answers with the previous target, which is no worse than a cache that is a second stale. For a resolver, serving a slightly old answer is the right side of the CAP trade-off: availability for reads, strong consistency only on the write path.

7. Writes: registration and updates

The write path is slow, careful and rare, so spend the checks here and keep the read path trivial.

1. Authenticate and authorise. The caller is a registrant or agency; the prefix table says which prefixes it owns; a request for a name under someone else's prefix gets 403.
2. Validate the name and the URL. Normalise the name; accept only http and https URLs; limit the length; reject credentials in the URL (https://user:pass@host).
3. Optimistic lock. The request carries the version it read; a mismatch is a 409, so two operators cannot silently overwrite each other.
4. One transaction: update the record, append to doi_history, and write an outbox row with the event. Committing all three together means the event exists if and only if the change does (the transactional outbox pattern; see message queues).
5. Publish the event from the outbox. Resolvers and the edge drop the entry; delivery is at least once, and dropping an entry twice is harmless.
6. Rate-limit per registrant (rate limiter) and log every change with who made it.

Never hard delete. A deletion request becomes state = 'tombstone', so the name keeps existing, resolves to a "this item was removed" page with status 410, and nobody else can ever register the same name.

8. Availability and failure modes

Put the instances behind a load balancer with health checks, run in at least two regions, and keep dependency-free reads as a rule: a resolver instance should be able to answer from its memory with the database off.

9. Link health and tombstones

A mapping that points to a dead page is still a broken link. A link checker finds them. It is a small crawler with the same politeness rules:

• Visit each registered address periodically with a HEAD request (falling back to GET), a short timeout and a redirect limit, at most one request at a time per host, and a descriptive User-Agent.
• Record the outcome with a timestamp; a single failure is noise, so act after several in a row over days.
• Do not rewrite the mapping automatically. Notify the registrant, show them the history, and let them fix it. After a long period of failure, an agency may decide to point the name at a tombstone or at an archived copy.
• SSRF: the checker fetches addresses that outsiders typed, so it must refuse private and internal addresses (loopback, link-local, internal ranges), limit redirects, and run in a network segment that cannot reach the internal services. A registrant who can make your server fetch http://169.254.169.254/ has found a hole.

10. Content negotiation and metadata

The same name must serve a browser (redirect) and a citation tool (metadata). The resolver looks at the Accept header: text/html gets the 302; the metadata types (CSL JSON, BibTeX, RIS and others, see the companion guide) are handled by a metadata service, which can be a separate deployment because its load and data are different. Two details matter for caches. Send Vary: Accept, so a shared cache keeps one entry per representation. And normalise Accept at the edge to a small set of values before it becomes part of the cache key, because clients send many near-identical Accept headers (different quality values, different orderings) and each distinct string would otherwise be a separate cache entry.

11. Observability and testing

Measure what tells you the design is working:

• Cache hit ratio at each layer, and store reads per second (the number that must stay flat when traffic grows).
• Latency percentiles (p50, p99) of the resolver itself, separate from the network.
• Rate of 404s (a spike means a scraper or a broken integration) and of 5xx.
• Staleness: the time from a committed update to the last cache dropping the old entry (invalidation lag).
• Link-check results: the share of registered addresses that fail, by registrant.

Test the pieces in isolation: the normaliser with a table of spellings (and a property test that normalising twice changes nothing), the cache with an injected clock (as above), the update path with two concurrent writers (exactly one succeeds), and the whole service with a fake store that goes down.

12. Common mistakes

• Answering with a 301. Browsers and proxies keep it, so updates never reach them (measured).
• Fetching the target to "check it" on every request. The resolver then fails when the publisher fails.
• Caching "not found" for long, so a new registration looks broken.
• Sharding by prefix, which creates hot shards (2.6× the average in my model).
• Skipping normalisation, which splits one name across several cache entries.
• Hard-deleting names, so they can be registered by someone else later.
• No history, so a wrong or malicious update cannot be traced or reversed.
• Letting the link checker fetch anything a registrant types (SSRF).
• Letting the cache grow without bound or forgetting Vary: Accept.

13. Questions interviewers like to add

"How do you keep it up when the database is down?"

Serve from the in-memory and edge caches, including expired entries (stale-if-error), and answer 503 with a short Retry-After only for names that have never been cached. Popular names are most of the traffic.

"How fast does an update become visible?"

At most the TTL (about a minute here) without invalidation; with an invalidation event, the time the event takes to reach the caches. The browser's own max-age adds to this for people who just visited.

"Why not make the mapping immutable and cache it for ever?"

Because the mapping is the whole product: registrants must be able to fix a moved or broken address. An immutable mapping is a URL shortener that can never repair a link.

"How would you shard it?"

By a hash of the whole normalised name with consistent hashing. Sharding by prefix creates hot shards because a few registrants own most names.

"How do you stop two operators overwriting each other?"

An optimistic lock: the update carries the version it read and succeeds only if it still matches; otherwise 409 and the operator reloads.

"How would you find dead links without hammering publishers?"

A polite background checker: per-host rate limits, HEAD requests, a long interval, backoff, and action only after repeated failures, with the registrant notified and nothing changed automatically.

"What would change at 100 times the traffic?"

More edge caching and a higher edge hit ratio (the cheapest lever), more resolver instances (stateless), more replicas, and possibly a second cache tier. The store barely changes because the cache absorbs the load.

14. Things to mention in an interview

• Read-heavy, small data, slow-changing: resolve and register are separate services.
• 302/307 with deliberate caching headers, because the mapping must be able to change.
• The cache TTL bounds staleness; invalidation events shrink it; negative entries need a short TTL.
• Never depend on the target; stale-if-error for the store.
• Shard by the hash of the whole name, with consistent hashing.
• Writes: authorise by prefix, validate, optimistic lock, history, outbox event, rate limit.
• Tombstones and 410, never hard deletes.
• Link checker: polite, SSRF-safe, never auto-rewrites.
• Content negotiation with Vary: Accept and a normalised Accept in the cache key.

Quick recap

• A resolver turns a stable name into the current address with a redirect. It must stay up when publishers do not, so it never contacts them on the read path.
• The load is read-heavy (about 600 reads per write in the example numbers) and the data is small (about 75 GB), so caches do most of the work.
• Use 302 or 307: a real browser kept a 301 or 308 after the target moved and kept sending readers to the old place.
• The TTL is the staleness bound; invalidation events shorten it; remember "not found" for only a few seconds.
• A small cache helps a lot under skewed traffic: with 1% of the names cached, the simulated hit rate was 23% for mild skew, 58% for moderate and 87% for strong skew, so measure your own skew before sizing it.
• Shard by a hash of the whole name: by prefix, the busiest shard carried 2.6 times the average load in the model.
• Writes are authorised by prefix, validated, versioned and audited; deletions become tombstones.
• A polite, SSRF-safe link checker finds dead targets and tells the registrant.

Appendix: the experiment code

Python 3 standard library. resolver.py runs its own assertions (python3 resolver.py), zipf.py and shard.py print the two tables, and the Go file runs with go run main.go. Timings and hit rates come from my run; the simulations use fixed seeds.

resolver.py: normalisation, TTL cache with negative entries, the resolver, and the tests of section 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: the same resolver in 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: the cache hit-rate simulation:

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: shard balance by prefix and by whole name:

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

Sources

1. IETF, RFC 9110: HTTP Semantics (redirect status codes) and RFC 9111: HTTP Caching.
2. Crossref, Content negotiation. Supported Accept values and the redirect through the DOI resolver.
3. Rajesh Nishtala and others, Scaling Memcache at Facebook, NSDI 2013. Section 3.2.1: leases against stale sets and 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. The Global Handle Registry and Local Handle Services; RFC 3651 and RFC 3652 are the namespace and protocol specifications.
6. David Karger and others, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, STOC 1997.
7. PostgreSQL documentation on generated columns and CHECK constraints, used in the table above (the SQL was run on PostgreSQL 16).

Practise this topic: System Design Networking

More guides