Design - URL Shortener

 FUNCTIONAL REQUIREMENTS - 

  • Get short url
  • Redirect to long url

NON-FUNCTIONAL REQUIREMENTS - 

  • Low latency
  • High Availability

API ENDPOINTS -

  • POST v1/data/shorten
  • GET v1/{shortUrl}

How to shorten the URL?

Let us consider the shortened URL consists of character (a-z), (A-Z) and (0-9).
So, the number of characters present are 26+26+10 = 62.

Let's say our URL shortener can generate 11600 urls/second. So, it can generate 1160*3600*24 = 100 million url's per day. Let's say we want to store the URL's for 10 years. Therefore, 100 million * 365 * 10 = 365 billion records.

So, from this estimation we can infer the max length of the shortened URL - 
62^⒩ >= 365 billion. So n comes out to be 7.
Therefore, a url of length 7 is more than enough to store 365 billion records.

DESIGN - 

The main problem we face here is, how to generate ID's. One way is to use auto increment feature of RDBMS but that puts to much load on the system if the traffic is high. We also cannot generate ID's on server side because there can be multiple instances of a service and there is high chance of collision.

One solution is to have ticket server to generate ID's but we won't discuss that as it leads to a single point of failure. Another approach is to go with Twitter's snowflake unique Id generation algorithm that will generate numeric unique Id's (handling our use case) but we'll talk about this in some other article. 

A more go-to solution would be to use Redis for it's functionality of providing a unique no. in the range provided to it (let's say from 1-1 million), but now we face a problem that all these services will call this Redis and it will be under huge amount of load also it is a single point of failure.
One can argue to keep multiple Redis, but we may face collisions in it or even if we provide different ranges to each Redis, we'll face huge complication if we want to add a new Redis.




Zookeeper - Apache ZooKeeper is a distributed coordination service designed to manage and coordinate large clusters of distributed applications. ZooKeeper serves as a centralised service for maintaining configuration information, naming, synchronisation, and group services within a distributed system.

It will provide ranges to different servers (like 1-500, 501-1000..) it'll also reassign the range to a server once it reaches it's limit.

Cassandra - We are using a NoSql here because of high availability and easy scalability.

If a server goes down, what will happen to the Id's that were not assigned?

It's okay even if we loose couple of thousand tokens in the range, because Base62 of length 7 has enough numbers to handle our use case.

Comments

Post a Comment

Popular posts from this blog

Puzzle - 100 Doors

Problem Statement -  There are 100 doors in a row, all doors are initially closed. A person walks through all doors multiple times and toggle (if open then close, if close then open) them in the following way:  In the first walk, the person toggles every door  In the second walk, the person toggles every second door, i.e., 2 nd , 4 th , 6 th , 8 th , …  In the third walk, the person toggles every third door, i.e. 3 rd , 6 th , 9 th , …  Likewise, In the 100 th  walk, the person toggles the 100 th  door.  Which doors are open in the end?   Solution -  Approach - We'll try to solve this question mathematically First we understand that each door state will be changed, depending on its number of factors and to be closed at the end the number of factors of that particular number should be odd. For eg:- Door 1 will be open at end as its only factor is 1 (odd), Door 2 will be closed as it has factors 1&2 (even). Now, let us consider a numb...
Read more

Design - Booking System

Image
 We need to design a booking system like booking.com/airbnb. First we look at the requirements: FUNCTIONAL REQUIREMENTS: Hotel- Onboarding Updates See the booking details User- Search hotels Book rooms  Check bookings Analytics Dynamic pricing NON-FUNCTIONAL REQUIREMENTS: Moderate latency - It's ideal to have low latency when user makes a reservation, but it's acceptable if the system takes a few seconds to book the same room, High Availability High Consistency High Scalability API Signatures: We'll have basic CRUD service (Create, Read, Update, Delete) Hotel-related APIs: GET /v1/hotels/ID POST  /v1/hotels PUT  /v1/hotels/ID DELETE  /v1/hotels/ID  Room-related APIs: GET  /v1/hotels/ID/rooms/ID POST  /v1/hotels/ID/rooms PUT  /v1/hotels/ID/rooms/ID DELETE  /v1/hotels/ID /rooms/ID Reservation-related APIs: GET  /v1/reservations (get reservation history) GET  /v1/reservations/ID (detailed information about a reservation) POST...
Read more

Design - Notification System

Image
 To design a notification system we first understand the different third party services. How do these third-party services work? Third Party Services: A provider builds and sends notification request to the required third part service. The provider provides the third-party service with device token and the payload.   Gathering Contact Information:   To send notifications, we need to gather device tokens, phone numbers, or email addresses. To do this, when a user installs our application or signs up for the first time, API servers collect the user contact info and store them in the database. FUNCTIONAL REQUIREMENTS:   Should be able to send notifications. Pluggable: Should be extensible to send different types of notification. SaaS – Should be built as SaaS product with rate limiting even it is a internal tool. Because we should limit the number of requests from a service. Prioritization – We must send notifications on bases of priority, as OTP is high priority wherea...
Read more