Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.
• Let's make a simplifying assumption that these URLs are for web pages. HTTP redirect to long URL when sent a request for the short URL. We won't support arbitrary operations like POST etc.
• Each short url maps to exactly one long url. No two users can reserve the same short url.

Non-Functional Requirements:

• low latency redirect
• high service availability

API Design

// Using the short URL

Request: GET /{short}

Response: HTTP redirect to long URL

Request: POST /create

Body: {long url}

Response:

Returns the short url. If already mapped for the given {long url}, it simply returns existing short url. Could increase latency on this method.

High-Level Design

URLs are stored as a simple mapping from short -> long. A no-sql database will due (very fast lookup by key, ), using some function on the long URL to generate the keys, we'll call it hash().

There could be different approaches to implementing this function.

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

Let's talk about some different ways to generate the short urls. One way, would be to swap our DB for a relational database which typically come with auto-increment primary keys, and just use this integer as the url. So what's wrong with that?

• Does not scale well under high write volume. ID generation is a bottleneck to ensure atomicity.
• Since ID generation is handled by the DB, it's not in our control. Being central part of this product's functionality, we may want the ability to evolve and customize ID gen over time.

We can generate the ID using a hashing function on the original long URL. To prevent all the keys from a single domain being close together creating hotspots, we may reverse the URL string (foobar.com.www instead of www.com.foobar). Hash collisions are rare if we use a sufficiently large key space, and can be detected using database atomic insert-if-not-exists features.