Loading...
Generate a short URL from a long URL
Retrieve a long URL given a short URL
Persist the URLs for X period of time
Out of scope:
User account management
Updating and deleting existing URLs
High availability for reading URLs
Strong consistency -> should be able to read URL immediately after writing
Low latency for reading URLs -> fast redirects
Scalability to support many new URLs and users per second
1000 reads / sec
10 writes / sec
36,000 writes/hr -> 720,000 URLs a day
URL takes 1kb to store
Define what APIs are expected from the system...
POST /generate -> short URL string once generated
Headers: Bearer token / JWT token
Body: {
longUrl: "...."
}
Returns Error if URL already exists for this long URL
GET
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...
1:1 short URL to long URL
URL(long URL, URL hash (Short URL), user ID, timestamp_created, time_to)
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...
Use partitioning (sharding) to allocate
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...
A POST request will travel to a Load Balancer and on to URL Service which will try to generate a hash of the long URL. It will first check to see if this long URL exists in the URL DB, and if so return error.
If it doesn't exist, it will forward the write request to a DB coordinator (routing tier) and send it on to the relevant shard.
A GET Request will similarly be forwarded to the URL service which will query the DB via the matching short URL.
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...
The coordinator routing tier will maintain a registry of which key ranges belong to which shard, in something like an in-memory cache or low latency data store. A technology for this is something like ZooKeeper, which can guarantee to keep this information synchronised to track which nodes have which partitions.
Explain any trade offs you have made and why you made certain tech choices...
By going with a relational approach, I have to manually manage the horizontal scaling of the DB via sharding and potentially read replicas to support scale as load increases. On the other hand , I could have used a NoSQL database on account of the low schema complexity, which would more organically scale as a managed service in something like DynamoDB, and continue to guarantee the same low latency. It's also more fault tolerant if a single node goes down. However, it's more difficult to provide strong consistency which was identified as a non-functional requirement. In this way I have traded maintenance and fault tolerance for strong consistency and a more consistent user experience.
Try to discuss as many failure scenarios/bottlenecks as possible.
If a shard goes down, users will be unable to access URLs in that space of keys. I can mitigate this by implementing read replicas with automatic failover, so that the read replica can be promoted to primary instance if the writer instance fails. This should only account for a very short drop in availability. If the Coordinator goes down, the whole service will fail to function. It's therefore ideal to make this a distributed coordinator service across multiple nodes, so there's no single point of failure. Finally, a ton of reads to a particular URL could generate a "hot key" problem. This could be mitigated with a CDN in front of the load balancer, so that repeat requests are cached at the edge and significantly reducing load off the backend servers, at the same time as lowering end user latency by reducing geographical distance. This is extra ideal because the structure of read request and responses are not user-specific, so single cache entries for one URL can serve many users without PII or user-specific qualities in the response.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?
I would probably migrate to a distributed NoSQL design and implement a read-after-write consistency guarantee through techniques like time-stamping the requests and two-phase write commits for transactions. This would support the higher scalability requirement, continue to have consistency for the users writing the URL, and generally reduce maintenance and risk of faults interrupting the availability of the system.