Loading...
List functional requirements for the system (Ask the chat bot for hints if stuck.)...
List non-functional requirements for the system...
Estimate the scale of the system you are going to design...
Traffic estimates: Assuming, we will have 500M new URL shortenings per month,
with 100:1 read/write ratio, we can expect 50B redirections during the same period:
100 * 500M => 50B
What would be Queries Per Second (QPS) for our system? New URLs shortenings
per second:
500 million / (30 days * 24 hours * 3600 seconds) = ~200 URLs/s
Considering 100:1 read/write ratio, URLs redirections per second will be:
100 * 200 URLs/s = 20K/s
14
Storage estimates: Let’s assume we store every URL shortening request (and
associated shortened link) for 5 years. Since we expect to have 500M new URLs
every month, the total number of objects we expect to store will be 30 billion:
500 million * 5 years * 12 months = 30 billion
Let’s assume that each stored object will be approximately 500 bytes (just a ballpark
estimate–we will dig into it later). We will need 15TB of total storage:
30 billion * 500 bytes = 15 TB
Bandwidth
Define what APIs are expected from the system...
We can have SOAP or REST APIs to expose the functionality of our service.
Following could be the definitions of the APIs for creating and deleting URLs:
Parameters:
api_dev_key (string): The API developer key of a registered account. This will be
used to, among other things, throttle users based on their allocated quota.
original_url (string): Original URL to be shortened.
custom_alias (string): Optional custom key for the URL.
user_name (string): Optional user name to be used in encoding.
expire_date (string): Optional expiration date for the shortened URL.
Returns: (string)
A successful insertion returns the shortened URL; otherwise, it returns an error
code.
Where “url_key” is a string representing the shortened URL to be retrieved. A
successful deletion returns ‘URL Removed’.
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...
We will use DynamoDB to essentially map shortened url to actual url
data is like this
key: TinyURL
Value: URL
TTL: 5 years (default)
CreationDate:
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...
We can compute a unique hash (e.g., MD5 or SHA256, etc.) of the given URL. The
hash can then be encoded for displaying. This encoding could be base36 ([a-z ,0-9])
or base62 ([A-Z, a-z, 0-9]) and if we add ‘-’ and ‘.’ we can use base64 encoding. A
reasonable question would be, what should be the length of the short key? 6, 8 or 10
characters.
Using base64 encoding, a 6 letter long key would result in 64^6 = ~68.7 billion
possible strings
18
Using base64 encoding, an 8 letter long key would result in 64^8 = ~281 trillion
possible strings
With 68.7B unique strings, let’s assume six letter keys would suffice for our system.
If we use the MD5 algorithm as our hash function, it’ll produce a 128-bit hash value.
After base64 encoding, we’ll get a string having more than 21 characters (since each
base64 character encodes 6 bits of the hash value). Since we only have space for 8
characters per short key, how will we choose our key then? We can take the first 6
(or 8) letters for the key. This could result in key duplication though, upon which we
can choose some other characters out of the encoding string or swap some
characters.
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...
Workflow is like this:
Client input a url and hits a create tinyUrl button.
the url will go thorugh a loadbalancer and api gateway.
It will then go to the createTinyURL service which will use sha256 hashing to generate a tinyurl.
it will then store the url in the dynamodb database using the tinyurl as a key.
When client searches the tinyurl in the browser, it will go throuhg the apigateway/loadbalancer, then it will hit the getTinyURL service. It will then retrieve the url from DynamoDB.
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...
We will add caching (most recently use strategy) and CDN to improve the speed . Most recently used shoud be good cause for the most part, when someone creates a tiny url, they want to use it right away.
Sha256 for hashing
Explain any trade offs you have made and why you made certain tech choices...
We use DynamoDb instead of relational database because it scales better. We also do not plan on doing queries on the data so sql is not really needed. We basically just need a mapping of key to value
Can also potentially use redis with a TTL
Try to discuss as many failure scenarios/bottlenecks as possible.
If multiple users use the same url. for every url request we can append a counter at the end to ensure each one is unique. Or if we have users, we append the user to the end to generate the url.
We will need to partion data since we will have lots.
We can partition data from consistent hashing.
To scale out our DB, we need to partition it so that it can store information about
billions of URLs. We need to come up with a partitioning scheme that would divide
and store our data to different DB servers.
a. Range Based Partitioning: We can store URLs in separate partitions based on
the first letter of the URL or the hash key. Hence we save all the URLs starting with
letter ‘A’ in one partition, save those that start with letter ‘B’ in another partition and
so on. This approach is called range-based partitioning. We can even combine
certain less frequently occurring letters into one database partition. We should come
up with a static partitioning scheme so that we can always store/find a file in a
predictable manner.
The main problem with this approach is that it can lead to unbalanced servers. For
example: we decide to put all URLs starting with letter ‘E’ into a DB partition, but
later we realize that we have too many URLs that start with letter ‘E’.
b. Hash-Based Partitioning: In this scheme, we take a hash of the object we are
storing. We then calculate which partition to use based upon the hash. In our case,
we can take the hash of the ‘key’ or the actual URL to determine the partition in
which we store the data object.
Our hashing function will randomly distribute URLs into different partitions (e.g.,
our hashing function can always map any key to a number between [1…256]), and
this number would represent the partition in which we store our object.
This approach can still lead to overloaded partitions, which can be solved by
using Consistent Hashing.
We can cache URLs that are frequently accessed. We can use some off-the-shelf
solution like Memcache, which can store full URLs with their respective hashes. The
application servers, before hitting backend storage, can quickly check if the cache
has the desired URL.
How much cache should we have? We can start with 20% of daily traffic and,
based on clients’ usage pattern, we can adjust how many cache servers we need. As
estimated above, we need 170GB memory to cache 20% of daily traffic. Since a
modern-day server can have 256GB memory, we can easily fit all the cache into one
24
machine. Alternatively, we can use a couple of smaller servers to store all these hot
URLs.
Which cache eviction policy would best fit our needs? When the cache is full,
and we want to replace a link with a newer/hotter URL, how would we choose? Least
Recently Used (LRU) can be a reasonable policy for our system. Under this policy,
we discard the least recently used URL first. We can use a Linked Hash Map or a
similar data structure to store our URLs and Hashes, which will also keep track of
the URLs that have been accessed recently.
To further increase the efficiency, we can replicate our caching servers to distribute
load between them.
We can add a Load balancing layer at three places in our system:
1. Between Clients and Application servers
2. Between Application Servers and database servers
3. Between Application Servers and Cache servers
Initially, we could use a simple Round Robin approach that distributes incoming
requests equally among backend servers. This LB is simple to implement and does
28
not introduce any overhead. Another benefit of this approach is that if a server is
dead, LB will take it out of the rotation and will stop sending any traffic to it.
A problem with Round Robin LB is that server load is not taken into consideration.
If a server is overloaded or slow, the LB will not stop sending new requests to that
server. To handle this, a more intelligent LB solution can be placed that periodically
queries the backend server about its load and adjusts traffic based on that.
Should entries stick around forever or should they be purged? If a user-specified
expiration time is reached, what should happen to the link?
If we chose to actively search for expired links to remove them, it would put a lot of
pressure on our database. Instead, we can slowly remove expired links and do a lazy
cleanup. Our service will make sure that only expired links will be deleted, although
some expired links can live longer but will never be returned to users.
Whenever a user tries to access an expired link, we can delete the link and
return an error to the user.
A separate Cleanup service can run periodically to remove expired links from
our storage and cache. This service should be very lightweight and can be
scheduled to run only when the user traffic is expected to be low.
We can have a default expiration time for each link (e.g., two years).
After removing an expired link, we can put the key back in the key-DB to be
reused.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?