My Solution for Designing a Simple URL Shortening Service: A TinyURL Approach

by blaze1302

System requirements


Functional:

  • User should be able to create a shortURL for a longURL
  • User should redirected to the longURL if he/she enters shortURL
  • User should be able to create a customized short URL
  • Assuming shortURL should have expiration of 5 years


Non-Functional:

  • System should be highly available
  • System should be able to redirect URL at a very low latency which is less than 10 milliseconds
  • System should be horizontally scalable. It should be able to serve 100 writes/sec and 10K reads per sec



Capacity estimation


Assuming write:read ratio as 1:100 and 100:10k request/sec


Storage estimation:

  • One entry in the URL mapping table should have:
    • 100 bytes of long URL
    • 10 bytes of short URL
    • 10 bytes of user id
    • 10 bytes of expiration time
    • This should approximately sum up to 150 bytes per database entry
  • Approx, 10k records per sec. Hence it would be 10^4*60*60*24*365*5 ~ 10^4*36*10^2*24*2*10^2 ~ 36*24 * 10^8 ~ 10^9 records over 5 years
  • This should sum up to 150 bytes * 10^9 ~ 15bytes * 10 ^10 ~ 15*10^7 KB ~ 15*10^5 MB ~ 1500 GB of data

Bandwidth Estimation:

  • Assuming 10k read requests per second and 1 request be of a size approx 150 bytes. We should support 150 * 10^4 ~ 15*10^5 ~ 1.5 MBPS traffic
  • Write bandwith should be 1/100 times the read B/W which should come around 15 KBPS


API design


POST: /shortUrl

  • This should take a long URL as input and returns shortURL as response and a http status code of 200


GET: /redirectUrl

  • This should return a long URL as a response and a http status code of 301


Analytics endpoints:


GET: /redirectionAnalytics

  • This should allow a query param as startDate and endDate
  • This should respond a report of most redirections of a short URL

GET: /userAnalytics

  • This should allow a query param of userId, startDate and endDate
  • This should respond with all the stats for shor urls created by a user


Database design

Database should consists of a primary datastore which consists of:

  • URL_Mapping table
    • short_url: string: primarykey
    • long_url: string: unique
    • owner_id: string
    • created_time
    • expiration_time: timestamp


This can be a nosql database with a key value pair like dynamoDB.

DynamoDB also has features like global secondary index help in faster reads


We should create a primary index on shortURL because it is going to be queried on most of the time

We can also have an index on long URL as it is a required read in a write path


A global secondary index on user_id should help incase listing by user is requried


Incase of database sharding, shortUrl sould be a candidate for partitioning key.


High-level design


  • System should have an API gateway as the first point of contact.
    • This should help in any kind of a DDoS attack and rate limiting
    • API gateway should also be able to distribute the load and act as a load balancer
  • Application Servers should comprise of 2 microsevices:
    • Redirection service: This service should be responsible to serve redirection to the long URL based on the short URL
    • Shortening Service: This service shoule be responsible to create short URL based on long URL as input and also ensure the uniqueness of short URLs in the system.
  • Database:
    • Database should have url_mapping datastore.
  • Cache at 2 places
    • There should be one cache at application later. The redirection service should first confirm if the short url is present in the cache. If not, it should check in the database. This should reduce the read calls to the database and contribute in achiving low latency.
    • One should be a CDN. This should have hot data based on the georaphical presence of the CDN. This should allow client to fetch the data from CDN which are geographically closer. THis sould also help in achiving lo


Ensuring uniqueness of identifiers:

Counters can be maintained in a unique way using a separate/central couter service. Once a shorted url request comes, the next available counter is requested from this service. These identifiers should be converted into the Base62 format. Base62 because the possible characters are [A-Z],[a-z],[0-9]

Incase of a collision(edge cases), shortening service should retry and get the next available counter value.




Request flows


Short URL creation flow:

  • Client calls the shortenUrl api with the long URL as input.
  • Api gateway recieves the request and sends it to the shortening service.
  • Shortening service validates if the long URL is valid. If not, http status code 400 is returned to the user.
  • If the long URL is valid, Shortening service checks if the long URL is already present in the database. If yes, it responds with the same short URL back without creating the new one.
  • Incase long URL is not present in the db, shortening service requests for the next available counter from the ID Generation service and creates a Base62 value for it. Which is your short URL.
  • If this shortURL is already present in the DB, next available counter is requested fromt the ID generation service until a unique short url is generated. The unique shortURL mapped to the longURL is then stored in the database.
  • Once a unique shortURL is generated and stored in the database, it is returned back to the user with a http status code of 201.


URL redirection flow: (what happes when user clicks on the short URL):

  • If the short URL is present in the CDN, same user is redirected to the long URL corresponding to it.
  • If not is CDN, request flows from api gateway and load balancer to the redirection service.
  • Redirection service checks if the short URL is present in the cache. If yes, long URL is returned back.
  • If it is not present in the cache, redirection service checks if the service is present in the database, if yes, its long URL first, stored in the cache and then returned back with http status code 301.
  • If short URL is not found in the database, an error response code 404 is sent back as a response.





Detailed component design


ID Generation:

  • To generate unique IDs a separate central service named ID Genaration service should be created.
  • This service maintains a counter which is supposed to be centralized.
  • Once a url shortening request comes to the shortening service, it requests for the next available counter to the OD Generation Service.
  • This counter is then converted to the Base62 format.
  • We discussed that 10^9 records are to be accumulated over 5 years, which can be incorporated in which shall be easily accomodated in 7 digit base 62 string. Hence we can create a short URL which is Base62 encoded into a 7 chars long URL.
  • If this short URL is present in the db, which is a case of collision, next available counter is requested. This can be retried until a unique shortURL is generated and effectively tackling collision case


Caching:

  • Caching is handled at 2 places.
    • CDN: These are geographically distributed caching servers which help to serve users which are geographically distributed. Users closer to the CDNs are most benifited.
    • Application layer cache: Redirection service, before checking in the database validates if the short URL is present in this cache. Incase present a database read query can be avoided decresing the database calls.
    • If the short URL is not present in this cache, a database call is made and the retrived entry from the db can be stored in the cache for further use.
    • Redis can be used as this cache.
    • As the short URL is valid for 5 years. we can have a TTL on 1 day in the cache.

Rate Limiting strategy:

  • We can enfore a rate limiting stategy per IP as we do not have any tokens in the read flow.
  • We can have around 100 requests from 1 IP address per minute.
  • We can have a exponentially back off strategy implemented in the api gateway to prevent abuse.



Trade offs/Tech choices

Short URL size

  • With increasing size of the ID, reads would become slower.
  • Also, the short URL should be as short as possible to optimize the data storage.
  • As discussed in previous points, the short URL is to be persisted for 5 years and hence 10^9 entries can be accumulated.
  • In Base62 vsersion, this can lead up to a short URL of 7 characters.
  • So we will have to have a short URL of size 7


Database:

  • As highly available key value datastore is required, dynamo DB would be a good choise as it also support fast reads and global secondary indexes

Consistency vs Availability:

  • Making the system as strictly consistent will increase the shortenUrl process as once the entry is created, it would also have to be replicated to all the replicas. This would increase the latency of the system.
  • We canmake the db as eventually consistent to make the shorten URL api as fast as possible.

Latency vs Cost:

  • Caches are expensive. Adding more cache increases the infrastructure cose.
  • But the non functional requirement is Low latency. We have introduced 2 caching layers.
    1. One as CDN and the other as Redis.
    2. we are evidently prioritizzing latency over cost



Failure scenarios/bottlenecks

Single point of failure:

  • There are few places which can be identified as single points of failure:
    1. API Gateway
    2. Redirection Service / Shortening Service
    3. Cache
    4. Databases
  • This single points of failure can be handled by having:
    1. an API Gateway which insures high availability
    2. Multiple instance of the application servers (redirection service / shortening service) can be unter the load balancers
    3. Redis should ensure high availability
    4. we can have replicas of the database so that there is no single point of failure. A master slave approach can be chosen with master serving all the write requests and slaves serving the read requests. Here the system would be eventually consistent to keep the latency to the lowest.

Horizontal Scaling:

  • As the load to the system increases, we can increase the redirection service and shortening service servers horizontally. Load balancers should make sure the load is distributed to the newly added servers to avoid increassed load on any one instance.


Disaster Recovery Preparedness:

  • Master and slave copies of the database should be geographically isolated.
  • Incase of any disater in the master's region, any of the slaves can be promoted to the new master.
  • Until the slave promotion is in progress, system can still run in a read only mode.
  • Instances of the application servers should be georaphiclaly isolated from each other to ensure application's availability in case of any disasters


Future improvements


Design custom URL support:

  • In the future, the system can be extended to support a custom short URL which is taken as input from the client.
  • Client passes the desired custom URL as part of the request to the system.
  • Short URL to be validated in the CDN, if it is present in the CDN, a 409 conflict http status code shall be thrown the user saying the custom URL is already occupied.
  • If not present in the CDN, shortURL can be validated in the cache, if it is present in the CDN, a 409 conflict http status code shall be thrown the user saying the custom URL is already occupied.
  • If not present in cache, the shortening service should validate if this custom short URL is already present the system. If yes, a 409 conflict http status code shall be thrown the user saying the custom URL is already occupied.
  • If the custom (short) URL is not present in the system, long URL is validated. If the long URL is already mapped to another short URL, the older entry is deleted from the database. This should help to keep long URL unique in the system.
  • Later, custom short URL and long URL is stored in the URL mapping datastore and an http status code of 201 is returned to the client.