Loading...
List functional requirements for the system (Ask the chat bot for hints if stuck.)...
convert full url to short ones.
when user try to access short URL, the system will access full URL which short url represents.
cold database to Handle of expired URLs.
What happens when a user attempts to create a short URL for a URL that's already shortened.
User authentication and ownership of shortened URLs.
Managed URL deletions.
Analytic features such as click tracking.
List non-functional requirements for the system...
scalability: need support this feature all over the world and serve 1b users.
availability: high availability to make sure
performance/latency: need get short ulr in 100ms and convert short to regular url in 10ms?
accuracy: make sure user to get right regular url from short
consistence: we dont need it?
Estimate the scale of the system you are going to design...
assuming:
short: 8B
long: 128B
ownerID: 32B
createTime: 8B
expired Time: 8B
192B ~ 256B
200 /s: five years: 200*60*60*24*365*5*256=8TB
Define what APIs are expected from the system...
shortenURL(str long_url, user_ID, expiration_time=None): Takes a long URL and returns a short URL.
redirectURL(str short_url): Takes a long URL and returns the associated long URL.
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...
key-value database
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...
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...
shortenURL() API:
Client sends the request. API Gateway forwards it to Shortening Service. It creates the short URL -> long URL mapping and store it in the database.
redirectURL() API:
Client sends the request. If the mapping is found in a regional, nearby CDN, it is returned from the CDN. Otherwise, the request reaches API Gateway and the Mapping Service. It checks if the mapping exists in Redis Cache. If it does, the mapping is returned. If not, it reads the Database.
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...
[Mid-level deep dive topic]
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.
[Mid-level deep dive topic]
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...
[Junior-level deep dive topic]
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.
Caching improves scalability on reads significantly. As the number of reads increases and pressures Shortening Service, we can increate caching capacity on both CDN and in the data center to serve more requests from caching.
[Mid-level deep dive topic]
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?