In this chapter, we will tackle an interesting and classic system design interview question: designing a URL shortening service like tinyurl.
- 08.01Design a URL shortenerIn this chapter, we will tackle an interesting and classic system design interview question: designing a URL shortening service like tinyurl.
- 08.02Step 1 - Understand the problem and establish design scopeSystem design interview questions are intentionally left open-ended. To design a well-crafted system, it is critical to ask clarification questions. Candidate: Can you give an…
- 08.03Back of the envelope estimationWrite operation: 100 million URLs are generated per day.Write operation per second: 100 million / 24 /3600 = 1160Read operation: Assuming ratio of read operation to write…
- 08.04Step 2 - Propose high-level design and get buy-inIn this section, we discuss the API endpoints, URL redirecting, and URL shortening flows.
- 08.05API EndpointsAPI endpoints facilitate the communication between clients and servers. We will design the APIs REST-style. If you are unfamiliar with restful API, you can consult external…
- 08.06URL redirectingFigure 8-1 shows what happens when you enter a tinyurl onto the browser. Once the server receives a tinyurl request, it changes the short URL to the long URL with 301 redirect.…
- 08.07URL shorteningLet us assume the short URL looks like this: www.tinyurl.com/{hashValue}. To support the URL shortening use case, we must find a hash function fx that maps a long URL to the…
- 08.08Step 3 - Design deep diveUp until now, we have discussed the high-level design of URL shortening and URL redirecting. In this section, we dive deep into the following: data model, hash function, URL…
- 08.09Data modelIn the high-level design, everything is stored in a hash table. This is a good starting point; however, this approach is not feasible for real-world systems as memory resources…
- 08.10Hash functionHash function is used to hash a long URL to a short URL, also known as hashValue. Hash value length The hashValue consists of characters from [0-9, a-z, A-Z], containing 10 +…
- 08.11URL shortening deep diveAs one of the core pieces of the system, we want the URL shortening flow to be logically simple and functional. Base 62 conversion is used in our design. We build the following…
- 08.12URL redirecting deep diveFigure 8-8 shows the detailed design of the URL redirecting. As there are more reads than writes, <shortURL, longURL> mapping is stored in a cache to improve performance.…
- 08.13Step 4 - Wrap upIn this chapter, we talked about the API design, data model, hash function, URL shortening, and URL redirecting. If there is extra time at the end of the interview, here are a…
References
Step 4 - Wrap up
- A RESTful Tutorial: https://www.restapitutorial.com/index.html
- Bloom filter: https://en.wikipedia.org/wiki/Bloom_filter