URL shortener: short codes, fast redirects

"Design a service that turns a long URL into a short one and redirects, at the scale of a large consumer site."

functional

Shorten a URL. Redirect a code. Custom alias. Expiry. Clicks per day.

latency

Redirect p99 under 50 ms at the server; create p99 under 300 ms.

availability

Redirect 99.99%: a broken redirect breaks every page that links to it. Create 99.9%.

durability

A created link is never lost or changed.

I assume 100 million new links a day, 100 redirects per link, links kept 10 years, and redirects in under 50 ms at p99.

500 B per link row and per redirect response, and the 3× peak, are assumptions; say them out loud. 551 B is Redis memory for one cached link with a 500 B URL, measured in the lab. The method is on the R2 sheet.

Writes peak at about 3,500 a second; redirects at about 350,000. Ten years of links is 183 TB, so the data needs about 19 shards.

• The redirect lives at the root path, so the short URL stays short. Reserve the paths the site itself uses.
• Without an Idempotency-Key, a create retried after a timeout makes a second code. With it, the unique index returns the first.
• A deleted code is not reused. Old pages may still link to it, so it answers 404 or 410 for ever.

Create is a POST with an Idempotency-Key. The redirect is a GET on the short path that answers 302, 404 or 410.

-- One row per short link. The primary key refuses a duplicate code.
CREATE TABLE links (
  code       text        PRIMARY KEY1,
  long_url   text        NOT NULL,
  owner_id   bigint,
  custom     boolean     NOT NULL DEFAULT false,
  created_at timestamptz NOT NULL DEFAULT now(),
  expires_at timestamptz,
  idem_key   text        UNIQUE2,
  CHECK (length(code) BETWEEN 4 AND 30)
);

-- Expired links leave in batches; this index finds them.
CREATE INDEX links_expires_at ON links (expires_at)
  WHERE expires_at IS NOT NULL3;

-- One counter per generator. A server claims a block with one UPDATE.
CREATE TABLE key_ranges (
  name       text   PRIMARY KEY,
  next_start bigint NOT NULL4
);

-- Clicks per link per day, written in batches.
CREATE TABLE clicks_daily (
  code   text   NOT NULL,
  day    date   NOT NULL,
  clicks bigint NOT NULL,
  PRIMARY KEY (code, day)5
);

One table keyed by code. A redirect is one primary-key read, so the table shards by a hash of the code.

Creates go to Postgres. Redirects read Redis first and Postgres on a miss. Clicks and expiry run in the background.

Postgres gives me a primary key that refuses duplicate codes and a counter row I can claim blocks from. Redis gives me a cache with expiry.

shorten(url, idem_key):
  FOR attempt IN 0 .. 4:
    code = source.next(url, attempt)       // hash + salt, random, or a range1
    IF insert(code, url, idem_key) adds 1 row2:
      RETURN code
    IF idem_key is stored: RETURN its code   // a retried request3
    IF the row at code has this url:
      RETURN code                            // same URL, same hash4
  FAIL "no free code"

next_from_range():                         // key ranges
  IF this block is used up:
    start = UPDATE counter row: next += 1000, RETURNING old value5
    block = [start, start + 1000)          // nobody else gets it
  RETURN scramble(next value of block)6     // 7 characters

// Shorten stores l under a code from src. It retries with the next candidate when the code is
// taken. A retried request with the same idempotency key gets the first code back. A hashed URL
// that is already stored under its code also returns that code.
func (s *Service) Shorten(ctx context.Context, src Source, l Link) (string, int, error) {
  for attempt := range MaxAttempts {
    code, err := src.Candidate(ctx, l.LongURL, attempt)
    if err != nil {
      return "", attempt + 1, err
    }
    l.Code = code
    ok, err := s.Store.insert(ctx, l)
    if err != nil {
      return "", attempt + 1, err
    }
    if ok {
      s.forget(ctx, code)
      return code, attempt + 1, nil
    }
    if l.IdemKey != "" {
      first, found, err := s.Store.codeForIdemKey(ctx, l.IdemKey)
      if err != nil {
        return "", attempt + 1, err
      }
      if found {
        return first, attempt + 1, nil
      }
    }
    stored, _, err := s.Store.Find(ctx, code)
    if err != nil && !errors.Is(err, ErrNotFound) {
      return "", attempt + 1, err
    }
    if stored == l.LongURL {
      return code, attempt + 1, nil
    }
  }
  return "", MaxAttempts, ErrNoFreeCode
}

// Candidate implements Source. Only the first code of each block costs a database call.
func (r *RangeSource) Candidate(ctx context.Context, _ string, _ int) (string, error) {
  r.mu.Lock()
  defer r.mu.Unlock()
  if r.next == r.end {
    var start int64
    if err := r.store.db.QueryRow(ctx, sqls["claim_range"], r.name, int64(r.block)).Scan(&start); err != nil {
      return "", fmt.Errorf("claim a block of %d from %s: %w", r.block, r.name, err)
    }
    r.next, r.end = uint64(start), uint64(start)+r.block
    r.claims++
  }
  n := r.next
  r.next++
  return Scramble(n, r.length)
}

UPDATE key_ranges
SET next_start = next_start + $2
WHERE name = $1
RETURNING next_start - $2;

// Scramble maps counter value n to a code that does not look sequential. It is a bijection on
// [0, 62^length), so it never creates a collision. It hides the order; it is not encryption.
func Scramble(n uint64, length int) (string, error) {
  space := Space(length)
  if n >= space {
    return "", fmt.Errorf("counter %d does not fit in %d characters (%d codes)", n, length, space)
  }
  return Base62(mulMod(n, scrambleFactor%space, space), length), nil
}

// HashValue is the first 8 bytes of SHA-256(url + "#" + salt). The salt changes the code when two
// different URLs land on the same one.
func HashValue(url string, salt int) uint64 {
  sum := sha256.Sum256([]byte(url + "#" + strconv.Itoa(salt)))
  return binary.BigEndian.Uint64(sum[:8])
}

// HashCode truncates the hash to length base62 characters.
func HashCode(url string, salt, length int) string {
  return Base62(HashValue(url, salt)%Space(length), length)
}

I take codes from a block of counter values that each server claims from Postgres. Random codes with a retry also work at 7 characters.

redirect(code):
  url = Redis GET "link:" + code
  IF url == "": RETURN 404                // a cached miss1
  IF url is missing:
    row = Postgres: SELECT by primary key2
    IF no row: cache "" for 60 s; RETURN 404
    IF row expired: RETURN 4103
    cache url for min(24 h, time to expiry)4
  count the click in memory
  RETURN 302, Location: url, Cache-Control: no-store5

// Resolve returns the long URL for code: from Redis when cached, else from Postgres, and then
// caches the answer. A Redis error falls back to Postgres; the cache is never the only copy.
func (s *Service) Resolve(ctx context.Context, code string) (string, error) {
  v, err := s.Cache.Get(ctx, CacheKey(code)).Result()
  switch {
  case err == nil && v == missing:
    return "", ErrNotFound
  case err == nil:
    return v, nil
  case !errors.Is(err, redis.Nil):
    s.Log.Warn("link cache unavailable; reading Postgres", "code", code, "err", err)
  }
  s.DBReads.Add(1)
  url, exp, err := s.Store.Find(ctx, code)
  if errors.Is(err, ErrNotFound) {
    s.cache(ctx, code, missing, s.MissTTL)
    return "", ErrNotFound
  }
  if err != nil {
    return "", err
  }
  ttl := s.CacheTTL
  if exp != nil {
    left := exp.Sub(s.Now())
    if left <= 0 {
      return "", ErrExpired
    }
    ttl = min(ttl, left)
  }
  s.cache(ctx, code, url, ttl)
  return url, nil
}

func (h *Handler) redirect(w http.ResponseWriter, r *http.Request) {
  code := strings.TrimPrefix(r.URL.Path, "/")
  long, err := h.Svc.Resolve(r.Context(), code)
  switch {
  case errors.Is(err, ErrNotFound):
    http.NotFound(w, r)
    return
  case errors.Is(err, ErrExpired):
    http.Error(w, "this link has expired", http.StatusGone)
    return
  case err != nil:
    h.Svc.Log.Error("resolve failed", "code", code, "err", err)
    http.Error(w, "try again", http.StatusServiceUnavailable)
    return
  }
  status := http.StatusFound
  w.Header().Set("Cache-Control", "private, no-store")
  if h.Permanent {
    status = http.StatusMovedPermanently
    w.Header().Set("Cache-Control", "public, max-age=86400")
  }
  if h.OnClick != nil {
    h.OnClick(code)
  }
  http.Redirect(w, r, long, status)
}

I answer 302 with no-store, so every click reaches me and I can count it. Redis answers most redirects; Postgres answers the misses by primary key.

on redirect:
  buffer[code, today] += 1                 // memory only1

every 5 s:
  batch = swap buffer with an empty one2
  upsert batch: clicks = clicks + n3        // one statement
  IF it fails: add batch back to buffer4

// Flush writes every buffered count as one statement: one row per link and day, added to the
// stored total. A background loop calls it every few seconds.
func (b *ClickBuffer) Flush(ctx context.Context) error {
  b.mu.Lock()
  batch := b.counts
  b.counts = map[clickKey]int64{}
  b.mu.Unlock()
  if len(batch) == 0 {
    return nil
  }
  codes := make([]string, 0, len(batch))
  days := make([]time.Time, 0, len(batch))
  clicks := make([]int64, 0, len(batch))
  for k, n := range batch {
    codes, days, clicks = append(codes, k.code), append(days, k.day), append(clicks, n)
  }
  if _, err := b.store.db.Exec(ctx, sqls["add_clicks"], codes, days, clicks); err != nil {
    b.restore(batch)
    return fmt.Errorf("flush %d click rows: %w", len(batch), err)
  }
  b.mu.Lock()
  b.flushes++
  b.rowsWritten += len(batch)
  b.mu.Unlock()
  return nil
}

INSERT INTO clicks_daily (code, day, clicks)
SELECT * FROM unnest($1::text[], $2::date[], $3::bigint[])
ON CONFLICT (code, day) DO UPDATE SET clicks = clicks_daily.clicks + excluded.clicks;

Tested: 8 servers clicked 10,000 times each on 100 links while a flusher ran. Every link got exactly 800, written in batches.

Each redirect server counts clicks in memory and writes one upsert every 5 seconds. At larger scale, I log clicks to a stream and aggregate there.

create_alias(alias, url):
  refuse unless 4 to 30 chars of [0-9A-Za-z-_]
  refuse reserved paths: admin, login, static
  refuse 7 plain base62 chars1              // a generated shape
  insert; 0 rows: RETURN 409 taken2

expire():                                   // a job, every minute
  REPEAT: delete 1000 rows3 WHERE expires_at < now
  UNTIL a pass deletes nothing

// CheckAlias applies the alias rules: 4 to 30 characters from base62 plus - and _, not a reserved
// path, and not shaped like a generated code.
func CheckAlias(alias string) error {
  if len(alias) < 4 || len(alias) > 30 {
    return fmt.Errorf("%w: %q must have 4 to 30 characters", ErrBadAlias, alias)
  }
  plain := true
  for _, c := range alias {
    if c == '-' || c == '_' {
      plain = false
      continue
    }
    if !strings.ContainsRune(Alphabet, c) {
      return fmt.Errorf("%w: %q has the character %q", ErrBadAlias, alias, c)
    }
  }
  if reserved[strings.ToLower(alias)] {
    return fmt.Errorf("%w: %q is a reserved path", ErrBadAlias, alias)
  }
  if plain && len(alias) == GeneratedLength {
    return fmt.Errorf("%w: %q looks like a generated code; add - or _, or change the length", ErrBadAlias, alias)
  }
  return nil
}

DELETE FROM links
WHERE code IN (
  SELECT code FROM links
  WHERE expires_at < $1
  LIMIT $2
);

An alias goes through the same primary key as generated codes, so a taken alias is a 409. A rate limit and a block list stop most abuse at create time.

At 7 characters, 1 million random codes did not collide once. After 10 years at 100 million a day, a random code collides about 1 time in 10, and the retry handles it.

Demand as in panel B. 10 TB per node is the planning ceiling from R2: 50 GB a day reaches it in 200 days. Lab capacity comes from one laptop; read it as orders of magnitude.

I start with one Postgres and a stateless service. I add Redis when reads near one node, and shards when storage passes about 10 TB.