Loading...
List non-functional requirements for the system...
Estimate the scale of the system you are going to design...
This system will be more read-heavy, more redirections than URL shortenings
100:1 ratio between read and write
We will need it to be highly scalable, therefore we can assume a large amount of URL shortening creations and a large amount of redirections.
We can do load testing to fine tune the system performance by gathering actual capacity requirements, and fine tune this for optimal scalability
/api/shortenPayload: {"originalUrl": "http://example.com/very/long/url"}{"shortUrl": "http://short.url/abcd1234"}/{shortUrlId}Where {shortUrlId} is the unique ID that represents the short URL./api/resolve/{shortUrlId}Response: {"originalUrl": "http://example.com/very/long/url"}/api/shorten/{shortUrlId}Response: {"message": "Short URL deleted successfully."}/api/stats/{shortUrlId}Response: {"clicks": 124, "created_at": "2021-01-01T00:00:00Z"}Other things to consider:
How will users authenticate with APIs either some sort of API token or session key
Rate limiting: Implement rate limiting for short URLs to prevent abuse
Validation and Error handling: Ensure input validation and return appropriate errors for failure scenarios like if a URL isn't valid or doesn't exist.
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...
URLs
PK | urlID: varchar
originalURL: varchar
CreationDate: datetime
ExpirationDate: datetime
UserID: int
User
PK | UserID: int
Name: varchar
Email: varchar
CreationDate: datetime
For higher scalability, we'd likely use a NoSQL database like DynamoDB, Cassandra because its easier to scale. Although the tradeoff will likely be eventual consistency, this should be ok cause we don't expect many redirects for a URL that is just created right away.
Additionally we don't really have many complex relationships that would benefit from SQL for complex joins.
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...
Redirect service --> This service will be used to redirect the request URL to the given original URL
Creation service --> This will write to the main database, which will then be written to the read-replicas
Cache --> Will be used in the Redirect Service for hot URLs, we can use a scheme read-through cache with a write-around strategy, something like Redis is a good candidate because of its strong performance, feature set and widespread use
We can use consistent hashing to efficiently replicate and partition the data
Database --> NoSQL Database will write to the replicas, and could be partitioned to distribute loads, we could also include indices on the replicas to decrease time to get data from replicas
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...
Redirect:
1) User hits the load balancer to determine where to redirect the use
2) Point to redirect service
3) Create a request in the RedirectService
4) Check cache for the short URL key: originalURL key value pair
5) If not in cache query DB for the long URL
6) If found reply was HTTP 301 and the long URL
7) Update the cache with key-value
Creation flow:
1) User hits load balancer
2) we get sent to the creationService
3) We generate a short URL for the long URL
4) We can do hash for the long URL
5) We can insert this into 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...
Lets dig deeper into the hashing component of the URL
For hashing if we use a base64 encoding, MD5 algo to produce a 128 bit hash value. But we might have problems with uniqueness
We could have a Key Generation Service (KGS) that generates random keys, and stores them in a DB. Whenever we want to shorten a URL we use one of these random generated keys
As soon as a key is used, it should be marked in the database so its not used again, the KGS can use two tables to store one for keys that are used, and one for used keys. KGS can also keep keys in memory so server can utilize them.
We could have a standby replica so that KGS isn't a single point of failure
Database:
We can store URLs in separate partitions based on the hash keys first letter, this is range-based but can lead to inequal DB partitions
Instead we can do a consistent ashing based parititoning. Where we take a hash of the stored object, and calculate which partition to use based on the hash.
We can randomly distribute the URLs into different partitions where the hashing function will map a key to a number between 1 and 256
Cache:
We can use off the shelf solutions like Redis or Memcached to store full URLs and the respective hashes.
When the cache is full, we want to replace a link with a new/hotter URL, we can use an LRU (linked list and hashmap) , we can also replicate caching servers to distribute load.
Cach replicas are updated whenever there is a cache miss, servers hit the backend database and update the entry for each cache replica.
Explain any trade offs you have made and why you made certain tech choices...
NoSQL vs MySQL
2) Sharding database, we can't do joins easily, but we don't have any complex joins so its a good juice
3) read-replicas. Need to keep in mind the delay in updating read-replicas. Since we have a cache that we update.
4) Since we have a few nodes we need good system management. We can use something like Kubernetes to ensure high availability and automatic scaling.
Try to discuss as many failure scenarios/bottlenecks as possible.
1) Load balancers could be a bottleneck, we could have active/passive strategy with the load balancers.
2) When a node in thee redis cluster fails, we could get a lot of misses. Since we use consistent hashing, we only get a minimal amount of keys used.
3) Some DB nodes might get too much traffic if sharding isn't done properly, we could have hot spots, we should evaluate our sharding strategy.
4) If a replica fails and the system doesn't handle it properly.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?
1) Distributed caches
2) Robust load balancing
3) Rate limiting for the DB
4) DB optimizations
5) Monitoring and alerts
6) Master-slave replication
7) Component redundancy