![]() ![]() If requests spike, our counter host may not be able to handle it.Whenever the application servers receive a request, they will talk to the counter, which returns a unique number and increments the counter. Let’s see how we will use the counter - we will use a single server that will be responsible for maintaining a counter. One of the solutions to this problem is to use a counter, which keeps track of a count (0–3.5 Trillion) so that in each case if we encode the counter value, there is a guarantee of no duplicates/collisions. This could (however unlikely) result in duplication or collisions in the Database. MD5(Long URL) -> base62encode(128-bit hash value) -> FE66AB71IT… We can take the first 7 characters for the key. After base62 encoding, we’ll get a string having more than seven characters. If we use the MD5 algorithm as our hash function, it’ll produce a 128-bit hash value. To generate a unique short URL, we can compute it using the Unique Hash(MD5, SHA256, etc.) of the original URL and then encode using base62. Let’s stick with 7 because even if we consumed 1000 keys a second, it would take 111 years to run out. However, the point of this system is to keep our URL as short as possible. The longer our key, the more URLs we have, and the less we have to worry about our system ever running out. Now, the questions arise, what should be the length of the short URL generated to cater to 60 billion requests. What is the minimum length of the shortened URL to represent 60Billion URLs? We will use (a-z, A-Z, 0–9) to encode our URLs which leads us to use base62 encoding. Total storage requirement = 60 billion * 200 bytes = 12TB Encoding URL Now, we assume the URL's length to be 120 characters (120 bytes) on average and then add 80 more bytes to store the information about the URL. Storage Estimation: Let us assume that we are willing to store our data (short URL + long URL) for ten years then, the number of URLs we will be storing would be = 500 million * 10 * 12 = 60 billion URLs ![]() Considering the 100:1 read/write ratio, URLs redirections per second will be = 100 * 200 URLs/s = 20K/s.If we calculate this value for each second, i.e., queries per second (QPS) = 500 million / (30 days * 24 hours * 3600 seconds) = ~200 URLs/s.Traffic Estimation: We can assume that we will have 500 million new URL shortening requests per month with a 100:1 read/write ratio, we can expect 50 billion redirections during the same period (100 * 500 million= 50 billion). Database- It will be used to store the mapping of long URLs to short URLs.Web Servers- Multiple instances of web servers will be deployed for horizontal scaling.Load Balancer- To distribute the load evenly among the backend servers.It will communicate with the backend servers via HTTP protocol. Here, we will assume that our read/write = 100 : 1 key componentsįollowing will be the key components in the URL shortening application: The most important thing to keep in mind here is that our system will be read-heavy, i.e., the number of reading requests per second can be up to 1000 times more than the writing request. This section will look at the estimate of the number of monthly requests, storage, etc. Users should be able to specify the expiration time of the URL.Analytics: How many times the URL is visited?.The service should be REST API accessible.Shortened links should not be predictable in any manner.URL redirection should happen in real-time with minimal latency.Therefore, our system should be highly available. If the system fails, it will imply that all the short links will not function.Users should have the option to give a custom short link for their URL.The short link should redirect users to the original link.Users should be able to generate a shortened URL from the original URL.The URL shortening service like Tiny-URL should have the following features: Functional Requirements This brings us to a discussion around the requirements and features of the system. Whenever the user visits the short URL, he/she will be redirected to the original URL.īefore jumping to the solution, as an interviewee, we should always discuss with the interviewer what he/she wants. Tiny-URL is a URL-shortening web service that creates shorter aliases for long URLs. The goal is to design a highly scalable service that could allow users to create shorter URLs, given long URLs, and have read and write functionality. Asked in: Google, Facebook, Amazon, Adobe Let’s understand the problemĭesign a URL Shortening service like Tiny URL.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |