System Design Interview 1: URL shortener like TinyURL
By Tomasz Kuczma
A URL shortener is one of the most famous system design interview questions. In my opinion, it is also the most essential one from a scalability perspective and that is why global companies like the famous FAANG ask about it. Let’s go through it like during an interview to show you how you can structure this discussion.
There is no perfect system
Remember, there is no silver bullet to design the perfect system. There are also no good or bad answers to the question. It’s all about trade-offs and all you have to show is that you are aware of those trade-offs.
During the interview when you design at least part of your system, an interviewer will try to break something to simulate real-life (changing traffic, unexpected events, failures). It’s all planned and natural part of an interview. Interviewers do that to check how you would react in the real world where things change and break unexpectedly - that is a key skill where true seniority shows up. My advice is to do not get demotivated e.g. do not think that you designed something incorrectly. It’s all part of the interview and if you get that questions it means that you did a great job so far! Just answer the question of what you would do in case of an unexpected event.
Note that an interviewer might want you to skip part of the stuff I describe here or dive deeper into some of them. It’s ok as you have usually only 1 hour so it’s impossible to cover everything in detail. Also, thanks to that trick, an interviewer can reuse the same question multiple times but focus on a different part every time.
Requirements
Collect requirements first! Usually, the question sounds very simple and generic. That’s intentional! It’s just not possible to design a working complex scalable system in 1 hour. Interviewers want to listen to how the candidate goes through the question, discovers challenges, potential pitfalls, and corner cases. It also tests your communications. Always talk with your interviewer and ask clarifying questions. Do it especially in the begging to collect initial requirements about the system.
In the case of a URL shortener system, the initial question will only sound like this:
Do you know TinyURL or goo.gl URL shortener? Design such URL shortening system.
That’s your time to collect functional requirements:
- Who can create links?
- Can a link expire?
and non-functional one:
- How many reads and writes per second do we expect? (estimates scale, CPU, and storage capacity and defines if service is read or write-heavy)
- How long are the links in bytes? (estimates storage capacity)
- When link should become available after creation? (clarifies SLA requirements)
- What is our availability and durability guaranty? (clarifies replication policy)
Also, try to think about usability and additional features of the system:
- Do we need to support links with custom names?
- Do we want to have links available only during a certain time window? (e.g. marketing campaign like Christmas sale)
Generally, ask about features that you should keep in mind to simplify the future evolution of a system. It’s 100 times easier to plan them now (without implementing them yet) than change the entire architecture later.
Planning is a key to success.
Capacity planning
Based on the answer to questions from the previous section, you can do capacity planning. It’s just simply answering a question:
How many nodes do I need to handle storage and traffic?
Assuming the answers are:
- read-write ratio: 200:1 (for every URL written/shortened there will be 50 reads of that shortened URL)
- expected number of writes: 1B/week (1 billion new URLs will be shortened per week)
- average URL length: 700 bytes (note that sometimes distribution and percentiles like p50, p90 might be more important than average)
- data needs to be highly available and durable (generic requirement without specific number)
Our capacity planning looks like this:
- Writes per second:
10^9 / week = 10^9/7/24/3600/s ≈ 1650/s - Reads per second:
200 * WPS = 330k/s(all read and write requests give332k RPS), it’s read-heavy system - Storage capacity:
10^9 * 700 bytes / week = 10^9 * 700 * 52 bytes / year = 3.64 * 10^13 bytes / year = 36.4 TB / year(52B new objects yearly) - Bandwith capacity:
332k/s * 700 = 232 MB/s - RAM estimation for caching (4h period): (let’s say you will cache only 20% of links causing 80% of traffic according to 80:20 Pareto’s principle)
4h * 20% * 332k/s * 700b = 4 * 3600 * 0.2 * 332k/s ≈ 669 GB /4h(you need almost 700GB of RAM to cache 20% of traffic within 4h window)
Why 4h window?
It’s just an educated guess. Systems usually have some peak hours (in some regions of the world) which comes from the fact of how our work is organized. 8h window could be good too but I wanted to be frugal. Frugality is one of Amazon’s leadership principles. This way you can show that you understand company culture and principles.
Based on that simple math, it’s quite visible that a single application host + SQL server is not a solution here. In real life, you should revisit capacity planning after building a prototype (do performance tests), then again before lanch (re-execute performance tests), and then again based on real data coming from monitoring and metering systems (repeat that regularly). Note that, synthetic performance tests can give incorrect results e.g. because your cache can be much more efficient (99% instead of 80%) which can build not realistic expectations and trust.
API design
Just write down the basic APIs your system needs. You can use the REST API principles to design them. It will be also your checklist if you implemented all requirements so it’s good to have them listed clearly.
E.g:
1. Create short URL
Request to api.example.com:
POST /rest/api/short
{
url: "https://kuczma.dev/articles/linux/modern-commands/"
}
Response:
200 OK
{
location: "https://example.com/ac34lkju"
}
where "ac34lkju" is link id
2. Read short URL
Request to example.com:
GET /ac34lkju
Response (http redirect):
301 Moved Permanently
Location: https://kuczma.dev/articles/linux/modern-commands/
Here you could double-check with an interviewer if you are on the same page.
For simplicity, I skipped here user authentication and creation of custom URLs. Also, consider yourself if HTTP 302 or HTTP 303 is better for your use-case.
General design
Now it’s time to draw something. Let’s create a general architecture diagram:
All services run on multiple hosts for availability and to support our scale. First, user’s requests will be sent to load balancer which will dispatch it to the first service - API Gateway. This service will authenticate the request (if needed) and forward it accordingly to the proper backend service - Links or Users. Users service is used to manage users - supports basic CRUD operations, changing password, etc. Let’s say, it’s also responsible for user authentication in APIs that require that (e.g. creating a new link with a custom name that could be available only for registered or premium users).
Links service is more interesting. This is where requests to create and read a short URL go. For reads, Links service queries cache cluster first and then (if there is a cache miss) DB and propagate this information to cache. For writes, Links service stores the information in DB and then writes it back to the cache. Technically, we could use the CQRS pattern here to design Links service, but that’s a topic for a separate article.
Of course, Links service needs to contact the proper DB shard to be able to serve user requests.
But how exactly are short links generated (link_id)?
That is a good question and there are few solutions for that:
- generate random number (e.g. 64 bit) and format it using user and URL friendly characters like
[AZaz0-9]set (like Base64 without+and/characters) - generate a hash of the original link and current timestamp
- create a separate service that will precompute a list of available
link_ids (generate random ids) and store them in a separate DB. Then you can just read-and-delete first availablelink_idto create a new short URL
All have pros and cons which you will have to explain that the interviewer e.g. what will happen in case of hash/random number collision?
Database design
The key problem in this system is a database design (mostly links database). You need a database where you can add 36TB of data yearly and support 332k read-heavy requests per second (1.6k writes and 330k reads). You can, of course, reduce the number of read requests by using an efficient cache policy (mentioned in the next section). For the purpose of this article, let’s assume that you need at least 12 DB nodes to store all the data (1 copy). Each node stores 3TB and handles 30k RPS (technically you can expect less RPS because of caching policy - let’s say there will be 10k RPS).
Since you need data to be highly available and durable you need replication. Usually, storing 3 copies in 3 different zones (AWS availability zones) is a good choice. So you need to have 12 nodes in each AZ (add 36 nodes every year in total).
How to shard the data?
You can notice that data can be queried using a single value - link id.
Thanks to that key-value storage will be a good choice here and link_id will be the key.
Surprisingly, many problems require only key-value storage.
Data can be easily sharded based on key using some range policy or hashing algorithm e.g.
- keys with prefix “a” goes to node 1. With prefix “b” to node 2 etc.
- or
hash(key) % number_of_nodes == node_id
You just need to store these rules somewhere (e.g. in a config file or other DB) which should be easy as it’s quite small data. In other systems, you might need to design a more sophisticated sharding algorithm.
Simple sharding base on modulo algorithm:
Note that each node stores independent data in the above example and nodes do not need to communicate with each other to read or store data. All thanks to a routing algorithm. At this point, you can imagine that you can store the data in any SQL DB (e.g. PostgreSQL, MySQL) or in document DB like Mongo DB (all you need is storage with item atomicity and durability guaranty).
Important questions to ask:
What will happen after a year when you need to double capacity? What will happen in yet another year?
The routing algorithm might stop working or can become inefficient when we will add a new node.
E.g. because hash(key) % old_number_of_nodes != hash(key) % new_number_of_nodes.
How would you mitigate that?
You can e.g:
- Create a special node adding procedure that will mitigate that (take care of data redistribution without losing availability)
- Our routing algorithm can support that case e.g. take a look into Chord DHT (distributed hash table) algorithm.
How to achieve replication?
You can have a distinguished master node that will handle replication to additional 2 peers. You can store information on which node is master together with shard rules.
Note that you need to have tools/procedures in case of failures e.g. to restore initial 3 copies of data in case 1 node went down.
Caching
To reduce DB load you can use caching. Proper caching is the base of distributed systems scalability along with DB schema and sharding. As mention before, you will cache only 20% of requests as according to 80:20 Pareto’s principle only 20% of links (objects) will generate 80% of traffic.
Redis or Memcached are good candidates for this role. You cannot store all data in one node (from RAM capacity and load point of view) so you will create the entire cluster and distribute the load based on the key (hash of it).
Some of the caching design decisions are similar to DB design e.g. need for data sharding. Some might be simplified as data is not persistent here.
Caching introduces also inconsistency risk which might be (or might be not) a problem in some systems which you need to work around somehow. Few other questions which you might want to ask yourself are:
- What is your cache eviction policy? Just LRU?
- How many replicas do you need? 1, 2, 3, or more? Where to put those replicas? In the same rack or in different AZs? (btw, you should ask the same question in DB replication)
- How to avoid cold cache problem (cache without any entry after a system restart)? What problem can cold cache cause?
I left those questions as an exercise for thorough readers. BTW, it’s my favorite scientific paper/thesis sentence the proof is left as an exercise to the reader where the author wants to say I'm too lazy to explain that ;) .
Conclusions
We’ve just bearly touch on the topic of system design interviews. I wasn’t able to cover every detail because there are too many of them and I intentionally skip a few too to keep it simple (I hope). I shown you one example of how this interview could go but remember there is no the perfect design and this is just a simple example. Similar questions to this one are key-value store design and in some sense also S3 design (but you store files that have different nature). If you think about it, many problems you can solve in a similar way I show you above. Eventually, you will have to duplicate the data which is fine in NoSQL world
One more time, I want to highlight that it’s not possible to cover everything in 45 min interview. Don’t be surprised if your interview will go in a different direction and you only focus on deployment strategies and how would you ensure that rollback is safe. Listen to your interviewer what he wants to talk about. System design interview, as the other interview parts, concentrets on understending the subject and problem solving, not on memorizing things.
I plan to present 2-3 more different system designs in separate articles.
Software engineer with a passion. Interested in computer networks and large-scale distributed computing. He loves to optimize and simplify software on various levels of abstraction starting from memory ordering through non-blocking algorithms up to system design and end-user experience. Geek. Linux user.