My Solution for Designing a Simple URL Shortening Service: A TinyURL Approach with Score: 9/10

by xylo1913

System requirements


Functional:

  1. Be able to generate short URLs from long ones




Non-Functional:

  1. The system should be available




Capacity estimation

Estimate the scale of the system you are going to design...






API design

  1. POST : create_short(long_url) return 200 on successful creation, and write to our database along with the shortened URL,if the URL is already (we will look up the URL because we have indexed the long URL and return the short if it exists). Will return a 500 if we are unable to create the brief. We will use md5 since its faster and a 128 hash value fits our purposes.


  1. GET: get_long(short_url) it looks up our table and returns the long with either 301 or 302 status (Depending on the implementation), will send 400 if the short does not exist and 500 if there is a server side error


Database design

Since our service requires a high read/write throughput and the data does not follow a relational pattern, we will use a noSQL database like MongoDB. We will use a TTL mechanism to auto-delete old records to address scalability. To help with scalability and faster retrievals, we will use sharding based on the hash of the long URL. While this approach may introduce an uneven balance amongst the shards, we can potentially shard the uneven zones, further creating shards within shard. We will use a range based sharding strategy based on the hash range of long urls.


This ensures faster read/writes.

To address efficient distribution amongst the shard we will use consistent hashing to mitigate rebalances if nodes are added/removed/


Furthermore, to help with fault tolerance, we will use database replicas; the replicas will be updated as soon as possible based on the volume of change and a minimum amount of time.


To improve query time we will index our database on the long URL and have a second index on our short_url


1)key: long URL

2) value: short URL




High-level design

General Layout:

1)

Utilize a rate limiter (lower threshold for writes and higher for reads) based on IP address to ensure the system is not being abused.

Load balancer to distribute load amongst servers,we can use a consistent hashing protocol or give the requests to servers with the least load. We have multiple instances of the servers running to address scalability. We can use dynamic load distribution to direct the traffic.

Reads:

The client goes through the load balancer, the server directs the request and if its available in cache (We can use redis here) we return the long URL or the IP address. If not we query the database using the secondary short_url index. if the data is not present in the database we return 204. In case of a time out or invalid short URL we return a 500. Since each short URL has to be 8 chars or within a determined length we can return a 400 if the size is longer or shorter than the determined size.


Writes:

The client goes through the load balancer, the server directs the request to the server with the least amount of load as discussed above. We will use our index on the long URL to determine if the value is present, if it is we can just return the IP address and redirect the traffic. If it is not we will use a md5 hash to hash the long URL and take the first 8 chars, in case we have a hash collision (we will look up the short URL) we can append the time stamp to the long URL and hash again until we have found an empty spot.


Cache:

Since this is a heavy read service it would make sense to have a large cache. Since our operation is write around cache we will not be writing to the cache.The cache will be updated via async updates and we will use an LRU approach. Redis seems like a good choice.




Request flows



Client sends a request to LoadBalancer LoadBalancer distributes the request to Server1 Server1 checks the Cache for data (Read) Cache returns a Cache Hit to Server1 Server1 returns the data to Client (Cache Hit) If Cache Miss, Server1 reads data from Database Database returns the data to Server1 Server1 returns the data to Client Client sends a Write Request to LoadBalancer LoadBalancer distributes the Write Request to Server2 Server2 writes data to the Database (Write-Around) Database replicates the write operation to Replica1 Database replicates the write operation to Replica2



Detailed component design





Trade offs/Tech choices

1) MD5 because it is faster than sha256, and we don't need the extra crypto benefits of sha256

2) NOSQL: Since the data is not relational, we require heavy reads, writes, and fast look-up.

Also, we will have better scalability

3) Write around cache: since many of the writes may not be used frequently

4) Dynamic load balancer: distributing the load based on resource allocation.



Failure scenarios/bottlenecks

1) too many hash collisions: if the system gets big we may experience hash collisions.

2) Concurrent writes:





Future improvements

1) Adding analytics

2) Deploying to multiple regions to minimize latency