System requirements

Functional:

• Require a URL and generate a shortened URL using its unique identifier;
• The unique identifier should be consisted of alphanumeric characters, with length between 6 to 8 characters;
• I will generate the ids using a sequential identifier and then cypher it using the base62 algorithm. It will already handle collisions;
• In future we can add expiration dates, access control, region restrictions, auditing and other features;

Non-Functional:

Capacity estimation

• The initial demand would be 200 requests per second for writing, with potential to achieve 1000. For reading, the higher expectation is 20,000 requests per second, but it can also be a lot higher on spikes;

API design

It will be composed of the following routes:

• GET /:unique_id - This will check if the provided unique_id exists and return the proper response (HTTP 302 if it exists or HTTP 404 if it doesn’t);
• POST /newurl - This will receive the full URL as a JSON property sent in the body, generate the unique_id based on the next sequential value available, and return the shortened url;

Database design

• We will use a key-value database for this first version thinking on how performant it is and that the data fits this model

High-level design

• An REST API replicated according to the demand connected to a cache;
• The cache is connected to a Key-Value Database;
• This REST API will be executed on a Kubernetes cluster with autoscale and HPA enabled to allow horizontal scaling;
• The range identifiers will be provided to each instance of the API when it goes online. The control of this will be held on a Zookeeper clusterl

Request flows

• For creating a new shortened URL:
  • The client will make a POST request to the API passing the full URL as a property in a JSON body;
  • The API will check if the URL is valid. If it isn’t, return a HTTP 400 as a signal of bad request;
  • Once the URL is valid, the API will then get the next identifier, cypher it using base62, and save the identifier as the key and the URL as the value in the database;
  • Once the data is saved, the API will return the shortened URL and the full length URL in a JSON body as the response;
• For accessing the shortened URL:
  • First the API will check if the provided id exists in the cache;
  • If it exists, return a HTTP 302 to redirect to the destination URL;
  • If it doesn’t, the API will check if the provided id exists in the database;
  • If the id doesn’t exists, it will return a HTTP 404 not found error;
  • If it does, it will save the data in the cache and return an HTTP 302 to redirect the client to the destination URL;

Detailed component design

• For the id generation we are using an 8 characters generated using a base62 algorithm. This will handle collisions well and give us some time to evaluate into something better;
• For the API we can use some rate limit technique to avoid some hacking attempt or data stealing;

Trade offs/Tech choices

• As we are aiming for maximum availability, consistency maybe affected but it doesn’t seem to be a great issue;
• Also the horizontal scaling may add some high costs as we reach some high demands;
• If we choose a long data retaining period, the database may be huge;
• As we don’t have access control, all the data is public;
• We don’t offer any kind of content control, so a malicious user can add something dangerous;
• The Kubernetes was used to handle horizontal scaling;
• The cache will help to give faster answers on trending URLs;
• The Zookeeper is just a way to control which nodes are online and control the id range that each will handle;
• The key value database seems to be a good solution to store data with this initial requirements since it acts like a hash table;

Failure scenarios/bottlenecks

• If on instance of the API crashes, Kubernetes will provide a new one;
• If cache crashes, it will make some access a little slower for some time;
• If the key-value database crashes, we can only reply based on the cached data;
• If Zookeeper crash, then we can’t start any new instances;

Future improvements

• Probable the cache may have some disk persistence to allow a faster recovery;
• All other parts of the system works in a cluster way, with several replicas to handle most of the failure scenarios.