System requirements

Functional:

1. Given a long URL, the system returns a alphanumeric string for a shortened URL.
2. Given a shortened URL, the system redirects them to the long URL.
3. Support authentication.
4. The user can edit the shortURL.
5. The system provides analytics on the usage of short URLs like number of clicks.
6. Implement rate limiting.
7. What happens when URLs are malformed.
8. Each of the shortened URL has an expiry. The users can specify the expiration date for the URLs. If not provided, the expiration date is infinite and never gets deleted.

Non-Functional:

1. Should be able to support 1000s of requests per second.
2. We probably do not need strong consistency, eventual consistency should be OK.
3. We need high availability and low latency.
4. We need to be able to scale up our database and servers whenever needed.

Capacity estimation

• Assume we have 1,000,000 users per day, writing 100 URLs per day.
• We will have 100,000,000 entries per day for a large scale service. We can assume a hash of 10 bytes is used.
• If a URL is 150 characters at max, and date takes up 8*8 bytes = 64 bytes, we have a total of 150 (long URL) + 64 (expiration date) + 10 (short URL) bytes ~= 230 bytes per URL.
• With 100,000,000 entries, we have 23 * 10*9 bytes = 23GB per day. This will certainly not fit in a single DB instance, so we will need to start the Database.
• From the web servers point of view, we can easily process 1000 requests per second, but we will have atleast a few 100s of web servers to handle traffic spike and failing servers.

API design

• GET /v1/api/<shortURL>
  • Response:
    • Code: 301
    • redirectUrl: longUrl associated with the short URL.
• POST /v1/api/shortenURL
  • Request parameters: longURL, expiration time (optional)
  • Response:
    • Code: 200 upon Success
    • Payload: shortUrl
• PUT /v1/api/<shortURL>
  • Request parameters: shortURL, longURL, expiration time (optional)
  • Response:
    • Code: 200 upon Success
    • Payload: shortUrl

Database design

We can choose either relational DB or NoSQL. We will have a simple schema in a relational DB. Since we do not need strong consistency, we can adopt NoSQL databases.

The database values are fairly simple:

• Primary Key: shortUrl
• Other values: longUrl, expiration key

We will partition the DB based on the hash values range. We will use the hashing to reduce the possibility of hot keys. To further improve even distribution, we can do consistent hashing with virtual nodes. Consistent hashing also helps with addition and removal of database nodes.

We expect equal number of reads and writes per second. So we can go ahead with leaderless replication and need to ensure quorum of reads and writes is achieved. We could have used single-leader replication, but in the light of the fact that it is not a read-intensive system but a equally read and write intensive system, leaderless replication is probably better.

High-level design

• We need a load balancer at the very beginning to handle requests and distribute them to the web server evenly in a round-robin fashion.
  • The load balancer can also implement rate limiting if required.
• We need a bunch of stateless web-servers to handle read and write requests.
• We need a database to store the short URLs, longURLs and expiration time.
• We need a cache in front of the database to improve reads.
  • It can be a write-through cache, or a write back cache.
  • To improve the write performance, we can choose the write back cache, so that the cache takes care of copying the data to the database upon eviction.

Request flows

POST flow:

The client sends a long URL for shortening.

The long URL is hashed to create a potential shortURL. If the shortURL is already present in the DB, check to see if the longURL matches. If it matches, return to the user an success with payload stating that the URL has already been shortened. This can be shown at the client. If hash is present, but long URL does not match, then add 1 to the hash (linear probing) to check if that hash is taken or not. Continue till a available hash is found.

Once a valid hash is found, add that to the database.

PUT Flow:

In case that this is a PUT request, check if the shortURL is already taken with another long URL, and if so, return an error.

Otherwise, delete the old shortURL, longURL entry and add this new entry. Return Success to the user.

GET flow:

The client receives a short URL.

The client checks if the short URL is present in the cache or database.

If so, the long URL is returned with status code 301

Otherwise an appropriate response with 404 code it given to the client to say that the short URL does not exist in the system

Detailed component design

There are a few interesing parts here: The database partitioning and the hash calculation.

Database paritioning:

• We can use consistent hashing for partitioning.
• We can place the replicas in subsequent database servers on the consistent hashing ring.
• The long URL is hashed to see which partition it needs to be stored at.

Hash calculation:

• Once the partition is decided, the short URL is calculated.
• We calculate the MD5 hash of the long URL. However, the MD5 hash is too long. So we strip it down to a smaller value, and check if the shortened URL of 10 bytes is present in the system already or not.
• If the shortURL is not present, then we add it to the database.
• If the shortURL is present in the system, then we increase the truncated MD5 hash and use check again, until we find a value that is not taken yet.

Trade offs/Tech choices

• We are doing a leaderless replication here, since we are looking at roughly equal number of reads and writes. This comes with the problem of eventual consistency. If we want strong consistency, then we will need to adopt single-leader replication with synchronous replication.
• Additionally, we are using a non-relational database. This is also because we want eventual consistency. If we want strong consistency, we can use relational DB like MySQL.

Failure scenarios/bottlenecks

• Hot shards is still a problem.

Future improvements

• We can choose a better partitioning scheme if we want to avoid hot shards