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 take a unique machine ID, and a sequence counter. Each time a particular machine generates a URL, we can increment the counter. We concatenate these two pieces of information to create a unique URL. This approach is a good way to prevent collisions, and significantly reduce concurrency concerns.

To avoid outages, we can use a distributed approach where multiple nodes can generate IDs independently. We can utilize a consensus algorithm to ensure uniqueness across nodes.

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. We can also input a specific TTL (say, 2 minutes) when a cache entry is first entered, and extend the TTL (2 sec) each time that link is accessed. This means that links that are "hot" for a while eventually die out and this design better reflects expected usage. Lookups by short URL will always route to the same DB instance. When a TTL expires, we can refetch from the DB to update the entry, or simply allow another entry to be cached by self evicting.

When a link is updated, the cache should immediately purge or update the corresponding cache entries associated with those URLs. DEL and SET Redis commands can be used for this.

Rate Limiting

We can implement a per-IP throttling approach. This way, we can prevent greedy clients from making requests whilst not adversely affecting legitimate users.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10