I swear this channel is such a hidden gem.

I've gone through a lot of videos on this subject and this is by far the best. Not just regurgitating what they've read elsewhere, but actually coming from a place of proper understanding.

Great content! Probably the most in-depth TinyURL design I've seen. Most others don't actually get into write conflicts/locking.

I appreciate the new 2.0 video style and how in depth it is. I found the older videos too brief considering the complexity of the systems they covered.

Thank you very much, I’ve been reading DIDA and Understanding Distributed Systems so it’s great to see how those concepts apply to the use cases you are showing. This is the first video of yours that I’ve seen yet, planning to watch all the series when I can because you highlight the questions that we should be asking when designing and assert the tradeoffs of different solutions, it’s amazing. I don’t know if you have done for the other videos but if I could ask for anything would be for you to change the pencil color when reviewing the flows of data, it makes it easier to find where you are pointing to in the drawing board. Again, thank you very much, these videos are really helpful.

You are so underrated brother... this is the best content on the internet regarding System Design interviews 100%... who cares about an interviewer saying 'yes' to every question that the interviewee asks, or an interviewee coming up with the same 10 boxes every single System Design question when you explain stuff like this... keep it up, you are saving lifes!!

You are very good, the best even, at driving the solution of a design problem by applying logical reasons rather than throwing something at my face i wouldn't understand. Thanks for existing!

I really like the format for these types of videos of starting with a naive solution and then iterating on each component as we discover performance problems. That way the initial db schema and the overall graph of how requests / responses implement the features can be clearly presented to the viewer + the viewer gets a conceptual framework to start evaluating the ways in which the simple picture needed to become more sophisticated.

Hey, first of all thank you for the videos. They've been really helpful for me prepping for an upcoming interview! I watched a separate video on tinyURL/pastebin link generation, and the main point of the video was that instead of hashing, which can lead collisions when we truncate the MD5/whatever hash, like you mentioned in the video. Their suggestion was that we could have a cluster of key generations/ID generators, and each one would have a range of URLs to distribute when a write request is made. They could be coordinated by ZooKeeper and would allocate only from their own chunks, and would refresh their URLs as needed. The only concern is that we lose that range of URLs (say 1 million) if a specific generator goes down, but since we have 2 trillion combinations if we use base 36 with 8 characters and even more if we use base 62, this isn't a major concern. This would also speed up writes in the case there is a collision. What are your thoughts on this?

I fucking love how you can explain complex shit and be funny at the same time. Keep up the good work!

Brief Outline 00:01:15 Problem Requirements 00:02:04 Performance Considerations 00:03:23 Link Generation 00:05:45 Assigning URLs - Replication 00:08:07 Assigning URLs - Caching 00:08:51 Assigning URLs - Partitioning 00:10:34 Assigning URLs - Single Node 00:11:29 Assigning URLs - Predicate Locks 00:14:12 Assigning URLs - Engine Implementation? 00:15:42 Assigning URLs - Database Choice 00:16:17 Maximizing Read Speeds 00:17:35 Maximizing Read Speeds - Hot Links 00:18:50 Maximizing Read Speeds - Populating the Cache 00:21:02 Analytics - Naive Solution 00:22:22 Analytics - Stream Processing 00:23:49 Analytics - Click Consumer 00:26:00 Analytics - Exactly Once? 00:29:16 Analytics - One Publisher Per Row 00:30:17 Deleting Expired Links 00:31:21 PasteBin - Huge Pastes 00:34:23 Final Diagram Thanks, Jordan!

Awesome video! Couple thoughts: - For storage, it may be useful to talk about content addressable storage. Many pastes may be the same and that will save space - I’m not sure what the CDN buys us here. Reading from s3 isn’t crazy slow but the big issue is that the object space is huge and my hunch is that most of the time, you’d get CDN misses in most regions. That is assuming you’re not storing every paste to your CDN, which feels expensive. This is more a not that a cdn feels like a premature optimization - I really like your count approach. Another couple be using a counter CRDT and increment server side while serving the link. That being said, yours is more general purpose and scales for other types of analyitics

At 12:34 -> You do not have to do any predicate query. Relational databases use B-trees and are not append-only like databases that use LSM trees. So an "INSERT" will fail if another INSERT beat it to the race because the 2nd insert will notice the primary key in the B-tree. This sort of "INSERT and fail if primary key exists" is very hard to accomplish in LSM based DBs as they are append-only. In fact to accomplish this in an LSM based database, you usually have to do a special slow instruction that involves multiple phases and uses something like Paxos or raft or 2PC. So with a database like postgres, one solution to this TinyURL is to actually just have different application servers INSERT new rows. If there was a race on the exact same primary key, the 2nd application server will get a "duplicate key exists" error and will know to retry or send the error to the client.

Once again, learned a lot and read and write scaling techniques were helpful in my system design interview. Another write scaling technique you can talk about is Log structured merge trees for o(1) write and O(logn) reads.

Thank you for all the system design content! I’ve been binging through the 2.0 playlist and this video does a great job putting all the pieces together. I don’t have any experience with system design interviews so I have two questions in particular: 1. If in an interview, someone were able to deliver a design with the same level of depth + complexity that you’ve described here, what level would they be placed at? Alternatively, what sort of depth would interviewers be looking for in say an L4 interview? 2. Many of the system design interview guides recommend to lay out a basic architecture first and then go into a deep dive at the end but in your videos, you weave both parts together. How would you recommend to split these parts up? For example, is database schema + choosing a type of database part of the deep dive or should it be part of the basic architecture? And how about for replication/partitioning?

6:40 never thought I'd laugh out loud during a system design video. Thanks for making my studying somewhat tolerable

Using PH as your example URL makes you a legend

Hey Jordan, awesome video as usual! I really appreciate the way you break down tradeoffs. I checked out the TinyURL/Pastebin design from grokking's course, but it felt a bit sloppy to me, your version is so much better :) thank you!

I'd love it if you could make content regarding what level of depth is expected from a Mid level SD interview vs Senior vs Staff! It would be cool to take the same problem and do a mock at each level so we can understand the differences! Would love to see a mock series between you and Gaurav tackling this. I've interviewed with companies where they haven't picked a level for me yet and they say we will determine it based on your performance. But I don't know what the expectation is exactly in the context of a system design interview.

Appreciate. It is a very serious description/implementation for such easy task.

FK , this man contents has its own system design . Love you buddy

Hi Jordan. You were talking about 16 TB of potential data, partitioning, single leader replication. Sounds like Mongo fits better than relational solution. Thank you for great content!

Wonder why key-value DB wouldn’t be the db choice. It doesn’t require data relation and we can quickly check if tiny url has been used and also supports fast retrieval

Hi Jordan, great video! I'm not sure that we have to have uderId in the table, because the same long URL can be used by different users, and the eventual short URL (hash) will be the same.

I'm here for your eyes

Hi Jordan, this is the best in-depth design video about tinyurl in any book or on any website. Thanks a lot! I do have two questions: 1. I am confused by the discussion around the concurrent writes part. In the video you first ruled out the multi-leader and leaderless replication designs. Then you discussed how to handle the concurrent writes to a single row. But if we are choosing single-leader replication, would this still happen? Shouldn't the leader handle the concurrent writes with locking or queuing, and determine the "one with later timestamp" to be unsuccessful (any maybe then assign a different unused shortURL to it)? 2. In many other sources, there is the other way to assign the tinyURL, which is through distributing sequentially increasing numbers in base-36/62 via a ticketing server. The ticketing server can scale itself by preallocating different ID ranges. I am curious what kind of partitioning could this design have to handle large read and write traffic? Like if we use hash range partition, clearly all the writes will concentrate on one partition which is BAD. Of course we could do another hash on the shortURL and partition on that to make it evenly distributed, but hashing itself is not free, and adds to complexity. What's your point of view on that? Thanks in advance!

Great video, especially the discussion on single leader vs multi leader databases here. A couple notes: I don’t think write through for the CDN is a good idea. If you wrote a 10 GB file there, it would be at the expense of other files that may be getting accessed frequently. We shouldn’t give priority to a large unknown file over something that has been accessed and we won’t know will be popular. This is assuming that CDNs have a bounded size. Maybe there is a fancy one out there that isn’t bounded. I think you could make an argument that you won’t have records that are accessed for a long time after they are created.

Learned a lot, concise, well explained, and also funny I have a sys design interview today, thank you so much

One comment about the writer - if the writer is an API instance serving the requests to the user, and we're writing to the CDN/S3/DB, this could potentially take a long time and you'd likely want some kind of async mechanism to do these writes with a way of updating the user on its progress.

Awesome Content. I wasn't expecting this much detail in url shortener. Two questions though: 1. How does partition to kafka will be done? Ideally, servers need to know which kafka patition the message should be sent to and also, some coordination service would be required to maintain that? 2. For writing large files for Pastebin. CDN is a cache and cache will be have eviction policy, so if any url will be hit with gigantic file, which is not used for days and someone hit it after lets say weeks. Considering, we use LRU, it might get evicted and CDN anyways would need to load it again. Is the only reason to put it in CDN first is to make sure popular urls will be in CDN itself and when even first few users hit it, they all will get it pretty quickly?

11:21 hi here you mention about the race condition when 2 users would add/create for a same actual url, but I’m confused as to why would this happen if the hash functions accounts for the userID already when generating the tinyURL? Wouldn’t that make the tinyurls unique for 2 users even for same links?

Thanks for explaining the rationale behind your design decisions, very few videos do that

Can you explain a bit more why an on-disk hash index would not work for this problem? I understand that on-disk hash indexes will suffer from poor data locality and disk I/O optimization, but in this case we don't care about range queries, so locality is not a concern. Also, it seems to me that we can cache disk pages in memory for a hash index just as we would for a B+tree or similar and achieve similar a similar probability for cache hits, as co-located shortURLs on disk have no increased probability of access. At the very least, it seems like we could use a hybrid solution with a B+tree to index our on-disk hash table and achieve constant time value access once the hash table range containing our target key is paged into memory. PS love your channel dude really interesting stuff 🫡

oh wow u changed the original system design vids! Great I was thinking of reviewing soon :)

hey jordan, curious, why do we avoid multi leader and use single leader when both can have stale data issue

great video, man. a lot of system design videos are super generic with just "here's some lego blocks that I know off the top of my head" and don't start from a bottom-up approach with the system architecture designed to support a specific algorithm, not just a top-level cookie-cut use case.

This series is definitely in a league of its own. Who da man! Jordan da man - Fellow dork

Great Video, Have a question 29:51 , it is exactly 1 idempotency key per row and not few if we partition the kafka topic by short URL. can you please clarify.

Why do you need predicate locks for solving inserts in MySQL DB ? Why can't we just use primary key constraints / unique key constraints given by DB to achieve uniqueness ?

Great Stuff!! So, to maintain the unique constraint using predicate locks, serializable transactions will have to be used with first a select and then insert, right?

for multi leader / leaderless cant we resolve the issues of conflicting writes by using consistent hashing?

Hi Jordan, I have a few questions on how this can be deployed globally. Suppose you need to generate URL's for different users across the world. Then you will need to deploy the generator and datastores in different regions and generate unique hashes for each region. If not, there could be hash collisions which will require you to check different data bases in different continents. Maybe we need to generate a UUID kind of solution, so that each region can have its own local store which can create and serve the content better. Also, the view count you might be getting it from different continents. Even in this case, you need to have some sort of sharded counter type of thing to consolidate counts from different regions. What are your thoughts.

That Google logo and the stand behind looks like ghost to me 😰😱

Great video! However, can you elaborate the following things related to the short URL generation? 1. Most of the common hash function, e.g. MD5, SHA-2, generate the string way longer than you need. How do you use it while still keep the hash collision low? 2. Can you elaborate how to detect the hash collision? You mention using the linear probing so it kinda imply you want to do it in the memory, so my guess is the service probably need to first query the DB to check if this hash/key already exist. Won't that be a performance concern? 3. I've read a few other designs of generating the unique short URL, and some of them raise the issues of using the hashing of the original URL (with optionally including other data like timestamp). They usually suggest to use a separate unique ID generation service/component, and perform proper encoding like Base 62 and use it as the short URL(besides the domain name part). Have you ever considered this and what's your thought of this? Btw, unique ID generation strategy in the distributed system may be an interesting topic to discuss as well if you haven't done it yet 🙂

You have drawn multiple instances of kafka in the same partition. Does it also follow Single leader replication? If not, how does it determine which click count event should go to which replica of the same partition?

Thanks for this video. One of the best I have seen in this topic. Question for you: You are saying we will partition by shortKey url where in keys from A-M will go to one node and keys from N-Z will go to another node. How do we know in advance which bucket we will be generating the key for?

Also, could you explain the sequence of workflows for pastebin? Does it redirect to the long url and then fetches the paste content from CDN?

Great video. I wonder if it would be considering overengineering to go for a keyed time windowed stream in flink, sink each trigger to the db idempotently (semi-event sourcing style) and trigger a reduce on the db once in x updates/once in a while (something like what rocksdb does). You know what, I think I just answered my own question writing this comment 😅

For the issue with multi leader potentially causing write conflicts, a simple fix could be to hash both the incoming url and outgoing url together. That would leave the chances of same hashed value being infinitely less unless the business is also looking up p0rn sites

In interviews, do we have to talk about all the ways we can do a part. eg all ways to hash/partition/caches

For the caches, since we want to handle hot-keys, why not use LFU as opposed to LRU for the eviction policy?

Is it really worth the trade off to use a relational db here due to the fear of write conflicts? We are giving up on a ton of write throughput by making this choice aren't we? What if we instead not take the input of the tinyURL from the user, instead just take his longUrl, have our cassandra already prepolulated with tinyURLs and then round robin requests among our leaderless architecture?

Been watching all your videos.. Can you do a video on Lucence OR how in general how search index work with a given edit distance?

Thanks for the vid, wondering what if the URL read succeeds and the write to the Kafka queue doesn't? Is there any decent way to to solve this, I know you mention 2p commit a bit, but was wondering if there's anything faster.

Just found the channel, and now watching all your videos from a year ago. Appreciate that you're going through the rationale and building intuition about these concepts. Also, what would be you're top 3 book recommendations?

Good content technically speaking, but a bit removed from an actual System Design interview. I found HelloInterview to be more geared towards passing the actual interviews (I swear I'm not shilling, just giving you feedback because I genuinely love your channel for the technical aspect).

At 28:55 why do we need to store an extra idempotency key for each additional SS consumer? im not quite understanding that part

If you write to S3 first and then the DB write fails, you’re left with untracked orphaned junk data from the failed request. Another approach would be to write to the DB first to persist the intent to upload the pastebin, do the rest async, and make sure to communicate something reasonable to the user while the upload is in progress.

Hi Jordan! Great video. I have a question about probing. Should the application logic check if the hash is available? Since we are creating a hash based on the long URL + userID + timestamp, why would there be any conflict? Should we also think of UUID or Twitter's snowflake or Base 62 conversions to avoid probing? Could you please explain more about the Hashing function?

Hey Jordan, Great video. Wanted to ask how analytics calculation would work in this case if in the system we were to use Atomic write operations (I am referencing DDIA Chapter 7 - Preventing Lost Updates - Atomic Write Operations). From my understanding we are basically trying to implement a read modify write cycle and it would still boil down to a lock which you mentioned. If we designed a distributed Redis store partitioned by URL to handle the counter incrementing would the main issue at hand be maintaining an accurate count during failover? Could using a consensus algorithm help with solving with this issue or would this reduce performance and throughout too much?

25:25 What is the difference b/t Spark Streaming and Flink, if you were to just use a larger batch in Flink that your example (you said 10, but consider we use a more comparable 100)?

Hi Jordan! If we are pre-generating the keys, then we cannot use user-ID and long url for the hash right? Then how do we generate 8character unique short url?

When you say you would use database partitioning, do you actually mean sharding? How do you approach discussing these two topics during an interview?

Sup Jordan! After 2:35 I went ahead and made a design too and I'm looking forward to hear an opinion about my thoughts, feel free to confront and bully me based on my decision. You have hard constrained the choices around no write conflicts (with the example of an identical hash for two different urls by two users made simultaneously). I thought, that situation could be extremally rare in real life (and even if - we could add extra complexity on how we generate tinyurl to assure its uniqueness, with a salt maybe, or a distributed counter, but tbh, only after such event would happen considerable number of times). Thus, I wouldn't want to discard options based on that edge case. That enables the Cassandra option, which looks very nice for a system which is in-fact read heavy as you said, but! each tinyurl visit (which is a read) is also a write because of inc() counter requirement. I really like your idea of going with mini batch updates and Spark Streaming, though. I think this is also a good design, and I'm not holding a strong opinion on either of those, and now what? :D Cheers! Thank you for the content, keep up great work!

Another question: when mentioning a few TB should be good for one single machine, I am wondering in practice what storage usually can be done in one machine? a few hundred TB?

Hey Jordan, you mentioned that we shouldn't use write back cache b/c that will incur the same issue as multi-leader/leaderless replication. Curious why we cannot use Redis for write back cache here? Redis supports single leader replication right? Thanks in advance!

What strikes me is a question if kafka can actually handle 2 trillion partitions 👀 for example firehose can handle max of 5k partitions per delivery stream. I think some more hybrid approach would be in order here.

If we are single leader, why do we need predicate lock? Only one client will accès the row, right ?

Great Video Jordan. I have couple of questions. 1. You are saying we will partition by shortKey url where in keys from A-M will go to one node and keys from N-Z will go to another node. But why do we need to do this kind of partitioning ? Consistent Hashing offers a good evenly distributed keys among available servers isn't it. Is it wise to use ConsistentHashing everywhere i.e., For DB partitioning, Cache Partitioning & Kafka Queue Partitioning. 2. At kzfaq.info/get/bejne/a7xmf8Sena2-n2g.html, Can you shed some more light on the Idempotency key for achieving the Exactly once processing. How does keeping the last written key will help in avoiding duplicate updates for clicks ? Because we might get the clicks for that same key later as well right i.e., Subsequent clicks on the url ? How do we differentiate between these two ?

Hi Jordan, nice content! A question -- why would it be a problem if we use spark streaming to calculate total counts? You mentioned that specifically the it will fail if there are multiple spark streaming consumers. What does that mean?

Hi Jordan, thanks for this video! I dont get why we need to worry about two people adding rows with the same primary "tinyUrl" key, doesnt every ACID compliant db prevent adding two of the same row like that or am I missing something very obvious??

Can you please clarify how you assign short URL’s ? The second option with materialized conflicts ?

Hi Jordan, great vid. Just had a question. In your DB schema, you mentioned having an index on the tinyURL. But given that the tinyURLs in each row are unique, wouldn't they be the primary key for our rows? And if so, why would we add an index on a primary key?

Thanks for the great content! I am wondering for the write-back cache and data consistency, is it possible to make sure the same user always write and read from the same cache? in that case will there still be any data consistency problem or anything I am not considering correctly? (apart from edge cases that the cache node is failing and they can only read from a new cache?

Hey Jordan, love your content! I'm a bit confused about when the S3 data is being used here, if we are always writing to CDN first and fetching from it as well. Is it a fallback if some data gets evicted from a particular edge CDN server?

How can we achieve or guarantee uniqueness of the tiny url field across multiple shards. Wouldn’t this be too expensive especially if we are using predicate locks

Hello Jordern is it possible to get these slides (or whatever they are). It will be very helpful for revision. Thank you :)

What are the benefits gained from choosing SQL DB over noSQL? noSQL can scale horizontally much easier

5:27 you mentioned that the hash function provides a unique value. Are you sure? Doesn't the hash function of a hash table typically return an index to map keys to indices in the underlying array?

Creating a partition for each short URL in Kafka could be problematic- large number of partitions in Kafka can lead to increased overhead in terms of memory usage, disk space, and metadata management,Each partition in Kafka consumes system resources such as file descriptors, memory, and network connections,Management Complexity.....

Why do you think hash indexes are only in-memory? Afaik, for example postgres supports materialized hash indexes

@jordan do you have slides for the problems, just like you have for the system design concepts? Thank you, keep rocking!

If we are doing something(probing etc) to avoid collisions then why do we have to care what replication we use? As then there should be no conflict, no?

If we want to add a new feature to the system - to generate QR code instead of short URLs, what'd be the changes if any?

Firstly very awesome content, thanks a ton. Secondly had a query regarding a point you mentioned on using Kafka queue for analytics where each short url would belong to a partition. i.e we might have 2 trillion partitions. I think that would be very bad in general as that would increase the latency and would it even be possible to create that many partitions? (there should be some upper bound I think) thanks!!

1 trillion urls? That's a moderately sized pornography collection 😏

I have a question - how we would get the same shortlinks "abc" at 5:58 if we are using hash function( userid, timestamp, long url). if hash function is generating the same value then wouldn't it be resolved by probing? Also hash function has different values in it like userid, long url.

How to find out when the tinyURL was accessed for the first time?

You've got good humor

Hey man, Just came across this channel and i see two playlists for system design problems Are the videos from first playlist good enough to cover ground for now until you keep coming up for videos in this playlist ? Just asking if there's any reason behind updating them as they were only 1 year old

How do you generated hashcode (base36) from url & timestamp with minimal collisions? I've seen other designs generating Sequence no in a distributed fashion and converting number to base36. We can avoid this approach, if you can share how to generate such a hashcode ?

Any thoughts on using sharded counters for click count vs kafka stream processing ?

Can you explain a bit more about the technology choices? you picked mySQL as it has all the requirements you came up with. but wouldn't scaling be easier with something like mongodb compared to mySQL. mongodb also has indexes. so wouldn't mongo be the choice in terms of faster development

btree is not scalable, and kafka uses LSM tables as its main system, and is highly scalable. so using ULID or UUIDs and replicating over a kafka queue might increase capaity without degrading your performance i think (although am not an expert in this system type)

Hi, could you estimate cost of all sql dbs from your example? I'm guessing it's pretty huge :)

Hey Jordan, In the case of one publisher Per Row(29:34) you mentioned that we will have one spark streamer per tiny url id. But here we have trillions of URLs how is that feasible to have trillion streamers for this case?

Great video jordan, one question though. Will this playlist have different questions than your last system designs questions playlist or will it be the same??

V good content

Great content!

Loving your videos - as a n enterprise system architect for the past 7 years i feel however that I dont understand WHY you're using hashing, do you plan to find that hash again ? this is classic ULID approach that was intended because of replication and consistency issue. when looking up the ULID as an index it can be indexed and this would solve all the issues and problems you faced. hashing is when you need to take the raw data and authenticate it somehow. i think you need to revisit this solution, you are using hashing as an indexing method and that is a red flag for me