Loading...
List functional requirements for the system (Ask the chat bot for hints if stuck.)...
User input the long URL and system need to return short url.
Whenever user enter short url. Redirect the user to original long url without any intermediate response
Not in scope
URL eviction policy is 1 year after that short URL should be deleted.
Option to user to manage expiry, customize URL, edit URL
Validate URL
User authentication
Short URL length should be less then 100 char
List non-functional requirements for the system...
Response time for redirect URL should be less than 10ms. For create URL response time should be more then 10ms
high availability: We expect redirect service to be highly available.
High scalability. Current estimation is 1k request/second for redirect and 100 request/sec for create URL. Next 5 years can expect 20k request for redirect URL. And 1k request for create URL
Estimate the scale of the system you are going to design...
1000 request/sec is what we are expecting
Given the response time of 300ms.
1 request will take 300ms. then in 1 sec we can complete 10/3 ~= 3.33 request
means 3 requests will get complete by 1 thread in 1 sec.
so 1k request will need 1000/3 ~= 333 threads
Since our system is I/O bound. we can consider it will reduce wait time by 20%. i.e. 240ms for 1 request.
so, 1 sec it will complete 1000/240 ~= 4 request.
means 1k request will need 240 threads.
if 1 instance has 60 core. so we need 4 instance of application.
Database: We need to have total 240 db connection.
we are considering this as high read system.
database capacity:
databases consist of key value
key would be short URL, and value object consist of long URL, create time, expiry time.
key (50 char) (50 bytes)
expiry time (8 byte)
create time (8 byte)
long URL (100 char) (100bytes)
total 1 item size is around 166 bytes
round of 200 bytes.
or we can say for 200 request/sec. it will be around
200*200*60*60*24*365*5 ~= 6TB considering data growth and some buffer we consider 10TB.
Define what APIs are expected from the system...
For Communication use HTTPS Protocol, expected request-response format is JSON.
create short URL
Http Post Method:
createURL(longURL: String)
input: longUrl
output: shortUrl: String
Validate the URL pattern. If does not match return Custom error message.
If short URL collision happen. It can have 2 scenarios. 1st URL already exists, or short URL Collision happen. Check If URL exist return. If short URL does not exit retry.
Already created short URL will return error.
RedirectUrl
Http Get method
redirectURL()
input=None
output= redirecturl: String
Failure scenario: URL has expired and deleted from database, or wrong URL entered. Return Error message URL does not exits, it may have expired or URL is not correct.
Defining the system data model early on will clarify how data will flow among different components of the system. Also, you could draw an ER diagram using the diagramming tool to enhance your design...
we will use NoSQL database. Because we do not have high ACID characteristic requirements.
we use nosql database with key-value store. we can use Dynamo DB as database which meet our high availability and scalability scenario.
structure name: ShortURL
Fields:
longActualUrl: String
ShortUrl- primary key, String
createAtTime: Long
expiry time: Long
As system scale, we can gradually implement Sharding. Sharding on hash of short URL.
As our reads are high, we can also think of implementing separate read-write database.
We can implement cache. Redis.
Eviction policy: Least recently used
Cache policy: Read through cache
You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...
Client makes request.
If redirect request. Web address is resolved by DNS and the request is routed to regional CDN node.
If data is found it will return immediately. Otherwise, forward request to API gateway.
For URL shortening service. we direct client request to API gateway.
API gateways is responsible for load-balancing and routing to respective microservice. To find active instance we use service discovery. Load balancing can be done in round robin manner.
redirect url service query the cache if found return else get data from database and update the cache.
Failure:
Do not find short URL.
High cache miss
URL shortener service generate unique id of length 10 character for each long URL. And update the entry in database.
Failure.
Long URL already exits.
Unique ID collision
under heavy load we can consider using sharding of database.
we can include observability service to track the health metric of each component of the system.
Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...
Users submit the long URL. Https request goes to regional CDN. If found return the redirect url. Else forward to API gateway. API gateway forward request to redirect service for redirect to original. For creating short URL api gateway forward request to create url shortener service.
if create url shortener generate short url and update database with new entry.
redirect url read from cache if not found query database. we update cache with data from database. we return data to api gateway. update the CDN and return to user.
Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...
API Gateway: Will be responsible for routing as well as load balancing. We have service discovery where each instance on start register itself with service discovery.
API gateway will query service discovery to find the active instance ip address and port.
Each service periodically send heartbeat to service discovery and API gateway will will query and cache data of active srevice from service discovery.
Redirect Service: Query the cache if found return. Else get from database update the cache and return.
Cache we are using key-value store cache. Cache eviction policy can be Least recently used.
create URL shortener service: will create entry into the database with corresponding short and long URL
Database: We have selected NoSQL database. SQL database is not selected because we do not have high ACID requirement.
We can use database with key-value store.
Explain any trade offs you have made and why you made certain tech choices...
SQL vs NOSQL: We choose NoSQL database. since we do not want very high atomicity, Isolation, consistency and durability. we need high availability and scalability. we can think of Dynamo DB.
Cache: we choose Redis cache instead of normal collection data structure.
Try to discuss as many failure scenarios/bottlenecks as possible.
Availability: we can have redundant/replica database in to manage failure of database node.
Keeping high availability for redirect service we can have more instances to handle failure.
API gateway can be single point of failure and potential bottle neck.
Regional CDN could be down.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?
Scalability: We can have multiple instances of each service Redirect service and URL shortener service.
URL customization. User authentication.