Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.
• Each shortened URL represents one and only one unique long URL

Non-Functional Requirements:

• High availability over consistency (99.999% uptime)
  • Service uptime is more vital than consistency. It can be costly to users if a shortened URL doesn't work properly if our service is down. It is ok if a URL takes time to propagate over servers (eventual consistency is an acceptable trade-off).
• Durability should be 100%-> users should expect their shortened URLs to work at least as long as the original URL is valid
• Latency (when a user clicks a URL, there should be at most 1s of additional delay to navigate back to the original URL) -> users should expect the shortened URL to be almost as fast as clicking the original URL.
• Scalability (should handle about 100 million DAU, based on examples like bit.ly)

API Design

• POST /shorten-url
  • purpose: given a long URL -> return and get the shortened URL

• GET /url/${shortened-url}
  • purpose: return the original URL associated with the provided shortened URL

High-Level Design

Services needed:

• Basic web front-end
  • The front-end needs to interpret and handle redirections from GET /url/${shortened-url}
  • Previously navigated/generated responses can be cached on the client side.
• Load balancers
  • Mainly for increasing redundancy and resilience
  • Load distribution can be done using consistent hashing load balancing techniques to evenly distribute load across servers
• API Gateways -> Used to determine what services to trigger (i.e. if we are shortening a URL, or redirecting from a short url)
• Services:
  • URL shortening service -> corresponds to POST /shorten-url
  • URL redirect service -> corresponds to GET /url/${shortened-url}
  • Utilize consistent hashing to generate unique IDs for URLs, and to avoid collisions and detect duplicates
• SQL database (data is structured, and the only thing we really need to keep track of is a mapping between shortened and original URLs. We also can introduce constraints on preventing duplicates). We also need a place to persist the URL mappings by writing to disk instead of memory.
  • Database replication can also be useful to ensure data persistence
  • Storage:

• • I don't see sharding being necessary, because each DB row stores minimal information, and queries only need to check for existence of a key and and perform simple writes. In terms of scalability, just having one database instance should be enough.
• Use a distributed caching system (Redis) to serve most frequently requested URLs (hotspot problem) and implement rate limiting on the servers

Detailed Component Design

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

Generating Unique Short URLs

Let's assume a "short" URL is 8 characters long, base-62 encoded, for human readability. This means 62^8 ~= 2x10^14 (200 trillion) possible short URLs, which is more than enough for our user base.

One way to generate a unique URL is to simply try to generate one randomly, and see if the result collides with another entry. If it does -> we can simply retry.

There would be minimal downsides, as firstly, the odds of a collision happening in our encoding space is extremely low. The response time would be very fast, as generating a random number is a very quick operation, so even if by complete chance a collision occurs, we can quickly generate a new sequence.

In the event we SOMEHOW suffer performance hits due to too many collisions from occupied encoding spaces, we can simply increase the URL length by another place, exponentially increasing our encoding space.

To ensure only one source of truth for generating URLs -> We can centralize the URL shortener service, and handle multiple requests in sequence asynchronously using a message queue within the shortener service.

Handling Throughput

We can assume that URL accesses (reads) are a much more common operation than creations (writes).

One way to handle this throughput is through a Redis cache, where we cache the most frequently accessed URLs.

A cache is sufficient here, because a vast majority of URLs that get created only get accessed a handful of times, but a handful of URLs get accessed a vast majority of times (hotspot problem). Since the amount of the most frequently accessed URLs is much less, we can easily fit these mappings into memory, where we get the advantage of significantly faster reads vs another strategy like indexing a DB and reading from disk.

A Redis cache is also much more easy to scale vs another strategy like DB sharding, which is too complex for this application.

A LFU cache invalidation policy would be the ideal choice here. Upon a cache miss, the cache would evict the lowest frequency accessed entry, and replace with the new one. On a cache hit, we can increment the access frequency count for that short URL. A TTL policy is not needed because shortened URLs persist indefinitely and are not updated. Evictions only happen on a cache miss on the least frequently accessed entry. Lookups by short URL will always route to the same DB instance.