Estimate Memory for a URL Cache

Problem

You are building the read path for a URL shortener: a short code like x7Kp2Qa maps to a long destination URL. Reads vastly outnumber writes, so you want an in-memory cache in front of the database. Estimate how much memory the cache needs to hold the hot set of mappings, and decide whether it fits on a single machine.

Then extend the estimate to the related question a crawler team faces: how much memory does it take to remember every URL you have already seen, and what changes if you only need an approximate answer?

• Give the per-entry size with its components, then the total.
• Account for data-structure overhead, not just the payload bytes.
• Say whether the answer fits on one commodity server (assume 64-256 GB RAM).

Examples

Working assumptions; ask for any of them and you will usually get a number close to these:

• Corpus: a few billion short URLs have been created over the product's lifetime; 10^9 stored mappings is a fair round figure.
• Read traffic: ~10,000 redirects per second on average, so ~10^9 reads per day.
• Skew: URL popularity follows a power law. The 80/20 rule is acceptable: 20% of URLs get 80% of the reads. In practice for shortened links it is even more skewed, since a link is hot the day it is shared and cold a week later.
• Distinct URLs read per day: far fewer than total reads, because hot links are read many times. Accepting 10^8 distinct URLs read per day is fine.
• Long URL length: average around 100 bytes; the interviewer may say 200 if the product is used for tracking links with long query strings.
• Short code: 7 characters from a 62-character alphabet (62^7 ≈ 3.5 × 10^12 codes, plenty for 10^9 URLs).
• Cache implementation: Redis or Memcached, or an in-process hash map. Per-entry overhead of ~50-100 bytes beyond the payload is realistic for any of them.

Hints

1. The cache does not hold every URL ever created. Decide what "hot set" means before you count anything.
2. Per-entry memory is key + value + overhead. The overhead of a hash-table entry (pointers, length fields, allocator rounding) is often larger than a 7-byte key.
3. For the crawler question, ask whether an occasional false "already seen" is acceptable. That single question changes the answer by two orders of magnitude.