Loading...
Should turn long urls into short urls for the user to copy and share.
Should persist these urls for about 10 years.
Should provide basic analytics for the urls, in near real time.
Should convert a url into a short set of characters
List functional requirements for the system (Ask the chat bot for hints if stuck.)...
Should optimize for reads over writes.
Should redirect within 100ms.
Should guarantee a write or throw an error when the user has submitted.
Should be durable, data should not be lost if a component crashes.
List non-functional requirements for the system...
Writes:
1B users x 10 links per user / year x 10 years = 100B links per 10 years
1 link = 256 bytes = 25 GB per 10 years
How many characters would we need?
Using 0-9, a-z, A-Z gives us 62 chars. 7 chars would give us 3.5 trillion links, which seems sufficient.
Reads:
Hot links - millions of clicks per link
90% of the links would be around 100 clicks
Basic CRUD API exposed to the client. REST would be appropriate. GRAPHQL would be overkill because it's unlikely that additional related data would need to be fetched by the client.
Our analytic service would need a basic read and write endpoint, and would likely be internal. So we could use an RPC protocol like protobuf.
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...
Consistency is prioritized because the user will immediately need their link after submission. Additionally, because we will be hashing the urls there is a possibility of collisions. If we used an eventually consistent storage solution, we'd have to resolve write conflicts. An RDBMS provides unique indexes to prevent hash collisions, and we can use stored procedures to implement hash probing when one occurs.
Our RDBMS will contain the following tables:
User:
Link:
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...
To start simple, we will have an app server connected to a database.
We've established that we will need 10B rows per year, so we will need to partition the data. Since our hashing function should be uniformly distributed, we can use the short_url as the partition key.
We also identified the problem of hot links. To reduce the load on the database, we will introduce a cache. While the data size can fit in the cache, if we wanted to reduce cost, we could implement an LRU eviction policy so that the hottest links are likely to be in the cache. The cache will be populated using write around. Write back runs the risk of a consistency problem during a hash collision. Write through could be acceptable if we are willing to sacrifice write times. Write around feels like a good compromise.
Using RDBMS to process analytics would add heavy write loads on the DB. It's better to use other components for this. To process the events, we would use a Kafka queue, since it is durable and can be partitioned. Apache Spark can process the events and use mini batching to update the database periodically to reduce the load. It too can be partitioned in the same structure as Kafka. Spark would aggregate the events and update the database with the view count periodically.
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...
Write path:
Read path:
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...
DB scaling and partitioning
The db and caches will be partitioned based off the short url key. Consistent hashing would be used to minimize the movement of data when more partitions are added or removed.
Explain any trade offs you have made and why you made certain tech choices...
Try to discuss as many failure scenarios/bottlenecks as possible.
Cache failure could lead to a cache stampede, causing too much load on the DB. We could add rate limiting to the DB while we repair the cache. We can speed up repair by periodically storing most accessed links in S3, which can be used to warm up the cache on restart.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?