CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 5 of 7 · 2 min read

The two flows

Shorten with an ID, redirect with a cache.

Shortening flow.

  1. The input is the long URL.
  2. Look up the long URL in the database. If it is there, it was shortened before, so return the stored short URL.
  3. If not, get a new unique ID from the ID generator.
  4. Convert the ID to the short code with base 62.
  5. Save a new row: the ID, the short URL and the long URL.
  6. Return the short URL.

Because step 2 returns the earlier code, the same long URL always gets the same short URL. This needs an index on the long URL column, or a separate lookup table, or the check becomes a full scan.

Redirect flow. Reads are ten times writes, so a cache sits in front of the database.

  1. A user opens https://tinyurl.com/zn9edcu.
  2. A load balancer sends the request to a web server.
  3. The web server looks in the cache. If the pair is there, it replies with the redirect at once.
  4. If not, it reads the database, puts the pair in the cache, and replies.
  5. If the code is not in the database either, the user typed a wrong link, so the server replies "not found".

Sizing the cache (made up). Keep one day of new links in memory: 100 million pairs. Each entry holds a 7-byte code and a 100-byte long URL, about 107 bytes. That is 100,000,000 × 107 bytes = 10.7 GB, which fits on a few cache nodes. With a least-recently-used rule, popular links stay and rarely used ones drop out. Most clicks hit links that are new or popular, so the hit rate can be high.

Sizing the database. About 36.5 TB over ten years. A key lookup by code is all that is needed, so the table can be split by hash of the code across shards (Level 4). Each shard has replicas. Nothing needs joins or transactions across rows, so the load spreads easily.

Full picture.

client --> load balancer --> web servers (stateless)
                                |-- cache (code -> long URL)
                                |-- ID generator (shorten only)
                                '-- database, sharded by code, with replicas

Check yourself: 1. Why does the shorten flow first look up the long URL? 2. What happens on a cache miss in the redirect flow? 3. Why can the database be sharded easily?