System requirements

Functional:

• Provide endpoints for creating shortened urls from long URLs
• Shortened urls must not be longer than 10 characters
• Users should be able to provide shortened URLs and be redirected to the long URL
• Statistics should be generated on the URLs being used
• Users should be able to delete shortened URLs
• User authentication mechanism is beyond scope

Non-Functional:

• System should support large loads, 10k shortening requests per day, 1 millions requests to shortened URLs per day
• System should be highly available, seeking 99.9999% availability
• System should make best effort to minimize latency (i.e. two requests to shorten URL sent at large intervals should return the same shortened URL), with 50ms response time
• Duplicating shortened URLs for different long URLS should never happen. Thus, we may need some sort of strong consistency
• System should have ability to scale horizontally as the load on system increases

Capacity estimation

• We estimate around 10k shortening requests per day. We assume about 80 bytes for the long URLs and 20 bytes for the corresponding to about 1 mb of data per day for storing new URL mapping
• We assume 1 million redirect requests per day. And thus per second requests is roughly 11.57 (1 million / 24 * 60 * 60). And we plan for two orders of magnitude higher (i.e. around 1000 requests per second)
• A single server can handle load but we will plan for 3 servers to ensure we have redundancy / availability

API design

• shorten_url(long_url, short_url, expiry_time) returns short_url:
  • API is for shortening a 'long_url' parameter and returning a 'short_url'.
  • User may optionally provide a 'short_url' and the service shall return same 'short_url' if this is a valid url
  • Optional expiry_time allows user to set a time whereby the URL will expire.
• redirect(short_url) returns long_url
  • When DNS server generates the short_url, this will be forwarded to this service, and internally a server will generate the redirect
• get_stats(short_url) returns several statistics on access of short_url, creation date, creation user

Database design

• The amount of data and request rate is sufficiently small we can use an SQL database
• We can shard the database using the short_url as the key, since we will do writes using the short_url and most lookups. For look ups by long_url (a one time read) we will need to search all shards)
• We will use leader/follower DB design with synchronous writes to ensure full consistency and no duplicate short_url for different long URL
• We will store the short_url to long_url in a table in this SQL DB. We will also add the expiry time. Some URLs may be short lived and we want to make sure these get expired as required. We will have a userId, creationTime too.
• We will cache using a LRU Redis distributed cache
• We will index on long_url field for quick search on those values if we need to search cross shard. And we will introduce bloom filters so that we can first check those if a long_url already appears there
• We will have another DB for storing statistics. This will be noSQL, since we don't care as much about consistency and want more flexiblity on the schema. Lets let this be a document store.

High-level design

Here we will place load balancers for receiving all requests. They will route to frontend service which will be in change of validating users (i.e. will use redirection to IDP, validate the JWTs generated by the IDPs), routing shortening requests to shortening service. A separate set of load balancers will handle the actual traffic of the short_url endpoints. These will route to redirect services. All of these services will be stateless and use kubernetes horizontal pod autoscaling based on load (i.e. configured at CPU / memory thresholds).

The redirect services shall query Redis cache to see if caches contain the URL mapping. If not, these we get directed to the DB for lookup. If not in cache, the application will search the correct shard and then cache the mapping after it finds it. It can read from read replicas here. It's ok not to use the leader (i.e. write replicat). These services will handle much more traffic than the shortening service and thus number of servers should be sized higher.

The shortening service will first lookup the long_url and see if it exists. It firsts looks at the bloom filter if it is found and if found, checks whether it's a false positive by looking in the appropriate DB. If so, then it looks up the short_url and returns that. If not found, then it generates a random short URL and looks it up for ensuring it doesn't already exists. We can generate these in advance if necessary, but don't expect to get too many conflicts. Next, it will update the cache with the mapping (assumes that users will want to test and we want to maximize speed for enhanced performance initially).

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?