Loading...
List functional requirements for the system (Ask the chat bot for hints if stuck.)...
short url
get original url
redirecting url
List non-functional requirements for the system...
high availablity
large amount of users
Estimate the scale of the system you are going to design...
each user shorts 5 urls
200,000 users will be 1 million urls
each url is 5kb
total storage will be 5GB
Define what APIs are expected from the system...
String shortUrl(String originalUrl, String userId, Date expireDate)
String getOriUrl(String shortUrl)
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...
will use NOSQL to store shorten url and original url
original url {
short url,
urlid
}
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...
loadBalance is used to distribute traffic to the right server
API Service is used to manage user login or profile update
shorten service is used to generate shorten service and return to user and store to database, it will pregenerate some shorten url and store to cache in case of high volumn requests
DynamoDB is used to store the shorten url data
cache is used to keep the pregenerate url, it will keep update with database to keep data consistent.
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...
shorten url: user send request to loadbalancer, after API service valid user identity it will send request to shorten service. shorten service will first check cache if there is any pregenerate url can use. If not it will generate a shorten url. Finally it will store the shorten url and original url and user information into DynamoDB
redirect url: user first check CDN to get original url, if not find send request to loadbalancer, loadbalancer send request to redirect service, it will check in cache first and if not find, check database of the original url and return it back to client.
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...
There will be replic of database in case of single point failure. we can set master-slave, master db will only for write and slave for read.
The url can generate by random string to avoid duplication.
redirect service, shorten service and api service also have replic to avoid failure.
Performance and scalability of redirectURL() API is extremely important for this system. As such, we employ two levels of caching. Requests will naturally have locality of access, so caching will be effective.
At the closest location from the clients, we will have CDN storing short -> long mappings for the most frequently requested URLs. For example, if a celebrity posts a short URL link in their Social Network post, this mapping should be in CDN. CDN can be hosted at Internet Exchange Points (IXPs), making the response time from client quite short. It has limited storage space, so it should store a small set of the most frequently accessed mappings. High volume of requests are handled by CDN, without even reaching the API Gateway. It is quite beneficial from scalability & fault tolerance perspective.
In the data center, we will employ a caching node, e.g., Redis. As we can install multiple Redis nodes with 100s of GBs of memory, it can store larger set of mappings. It is still faster than accessing the database, so this would provide performance and scalability gain.
Both CDN and Redis Cache can employ Least Recently Used eviction algorithm to ensure currently popular mappings stay in cache.
Database and Cache should be partitioned for improved scalability.
Short URL is a good choice for a partitioning key because:
Other partitioning keys (long URL, user ID) would have disadvantages about these points.
Explain any trade offs you have made and why you made certain tech choices...
There are two ways to create a short URL:
There is a tradeoff:
Pro of Hash approach is that you don't have to generate random numbers. Con is that the created hashes might collide. In particular, since our random string (8 characters) will be shorter than what the hash algorithms generate (20 bytes or larger), the risk of collision would increase.
Pro of random generation is the possibility of collision is lower. If a newly created random string collides with an already existing one, we can simply generate one more random string. Con is that it would require computational power to generate random numbers. However, since Linux and other OSes support fast random number generation with /dev/urandom, we assume the cost is manageable.
We will pick random generation in this exercise.
Try to discuss as many failure scenarios/bottlenecks as possible.
All the components - Load Balancers, Web Servers, Cache and Database should have multiple instances for improved availability. There should be robust monitoring and alerting systems on them.
All nodes can fail. Let's look at important failure cases.
If Mapping Service fails (hardware failure, crash, software bug, network partition, slowness ...), it would directly impact the most time sensitive operation of this system, i.e., redirectURL(). To mitigate this, we should always run multiple Mapping Service nodes. It is s stateless service, so we can multiple nodes of the same service. We can use a coordination service, e.g., ZooKeeper, to track which nodes are alive (i.e. sending regular heartbeat to ZooKeeper), which are likely dead (i.e. not sending heartbeats for some time), which nodes should be taking requests.
Losing cache would also impact redirectURL() functionality. For example, let's say Redis Cache that is holding 10% of short URL -> long URL mappings goes does due to a faulty memory. Mapping Service will now have to access the database for each of these mappings. This makes requests much slower. Increased load on the database may even have cascading impact - database gets slower and slower, Mapping Services retry, making the database even busier - ultimately resulting in the database crash.
We have multiple mitigations.
a. Create read replicas for Redis Cache. Let's say for 1 leader, we put 2 read-only replicas. Writes are handled by the leader, and propagated to read replicas by transmitting a write log. Reads can be handled by all three. If the leader goes down for some reason, one of the read replicas can become the leader (after a leader selection process) and take over the responsibility as the leader. This would avoid the aforementioned scenario.
b. Mapping Service should have a mitigation strategy to avoid overloading the database. For example, exponential backoff before retrying, rate-limiting, and circuit-breaking.
Caching improves scalability on reads significantly. As the number of reads increases and pressures Shortening Service, we can increase caching capacity on both CDN and in the data center to serve more requests from caching.
As the number of write requests to shortenURL() increases, it might put too much pressure on the database, causing slowness, errors, or even crashes.
To avoid this, we can introduce a message queue to buffer the requests. Shortening Service would push a message in Message Queue, representing the request. Queue Worker would pull from the queue, creates the mapping in DB, and notifies the client the mapping is ready. The system can inform the client with long polling.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?