IMPORTANT: Don't forget the Memtable is stored in memory, so if the system crashes, that data will be lost. To avoid losing data, we can maintain a separate log file on disk. Every time we write to the Memtable, we'll also append that write to the log file (no need to sort it as we just use it to restore after a crash). Then once the Memtable contents get written out to a SSTable file, we can erase the log file. That way the log helps us avoid losing writes stuck in memory when a crash happens.
That's the best system design content I have ever seen on youtube ! This channel is absolutely amazing. It must be tough to squeeze all that valuable knowledge into less than a 10 minutes video. Keep up the excellent work!
This is the most information-dense video on what's so special about NoSQL databases I ever saw. Not a word was superfluous, but the key concepts were clearly transmitted.
VERY informative without going into too much complexity. THANKS and congrats for a great video. I'm an MS SQL Server DBA, and the high level explanation you provided was awesome. Thanks again. Best, R.
Great explanation. Resolved all my doubts on how NoSql DBs work. However, I wanted to understand 1) Whether the balanced tree and keys in sorted set is only the object key with pointer to data value or it also contains the actual data? 2) Can a NoSql DB index multiple keys? 3) Why can't SQL DB also implement flushing mechanism in order to speed up writes? I know that they are highly consistent so they need to persist data to disk, but they can simply append the entry in a log file just like NoSql DBs do, and in case of a network partition, first check the log file to sync data in actual database?
I never experienced such a communicative video with such a simple and easy explanation.. Thanks Alex ..Please keep it up and upload more such videos. I have anyway bought both volume of System Design Book. Thank you so much !!!
That's a cool trick. So what it is essentially doing is spreading out the computer's resources across time, where with a traditional database you will get lots of spikes in processing on the timeline when doing reads and writes. Mind you the attraction of SQL was that you could have multiple indexes and create custom views on the data in a highly relational way, but granted that was very expensive on resources. I think traditional databases were mostly optimised for the deficiencies of the mechanical hard disk drive. I think it may end up as redundant in future as we store our data more on chips. Thanks for the video. I like videos that don't waste your time with long BS intros.
You read my mind when it comes to "spreading the computer's resources across time"... Which for some use cases makes perfect sense, but not all use cases. Not sure I agree with the "deficiencies of mechanical HDDs" part of your comment though. But great comment overall.
Nicely explained. I read all this information in designing data intensive application book. But few topics like memorable and sstables were still bit unclear to me. Got the whole idea now. Great stuff. Keep going
I've often wondered how NOSQL databases can achieve higher write throughput than relational DB. Thank you for sharing the techniques involved. Your explanation is clear and the graphics are excellent!
Great work! I wish I had watched this video before trying to learn the architecture behind RocksDB by only looking their documentation, hahaha! Awesome work!
6:56 correction regarding Bloom Filter If the Key doesn't exist, bloom filter will NOT return False Negative If the Key doesn't exist, bloom filter MAY return False Positive In other words. If bloom filter says there's NO key in page, there's definitely no key in page. If it says that there's the key in page, there MIGHT be the key in page with some probability. This probability data structure helps to reduce unnecessary reads.
One additional thing to mention (around th-cam.com/video/I6jB0nM9SKU/w-d-xo.html perhaps) is that the writes are written to memory AND a transaction log to ensure durability. Otherwise whatever was in the MemTable will not persist after a crash. The transaction log can be replayed to rebuild the MemTable.
Thank you for the feedback. We did have that initially, but decided to take it out to focus on the LSM tree itself. We knew someone would bring it up, but didn't think it would take this long. 😂 We are glad you did.
You’ve been hitting it out of the park with these videos! Really enjoy the content. 6:50 “(bloom filters) return a firm no if a key does not exist”. That’s not quite right. Bloom filters returns a firm yes if a key exists. If a key does not exist, it might still return yes with a low probability.
That’s exactly right! The subtlety here is in his claim that 1. Key does not exist -> returns no 2. Key “might” exist -> probably returns yes Whereas bloom filters really guarantees 1. Returns no -> key does not exist 2. Returns yes -> key probably exists i.e. “bloom filters returns a firm no (only) if a key does not exist”
in other words, a query returns either "possibly in set" or "definitely not in set". definitely not in set -> if the key does not exists, 100 % no answer. en.wikipedia.org/wiki/Bloom_filter#:~:text=A%20Bloom%20filter%20is%20a,a%20member%20of%20a%20set.
What is wrong with you people ? That's exactly what's said in the video. And much simpler than what you try to explain. Am I missing something ? There's other comments like this too, arguing that somehow the video is incorrect, when in fact it is, or at least what they say is the same as what the video says. Which is if the bloom filter says there's no key, you can trust that and skip to the next level.
Like many have said, this is a great dense video at a good beginner depth for people like me. I hope there will be a relational db video that complements this if at all possible, since the quality level is so high 🤞
Thanks for the video. Your explanation rises a concern to me : since the memtable is in memory, what happens if the server crashes before flushing ? Is that memtable distributed or replicated ?
Generally for the memory table write ahead log is maintained. Once the memory table is moved to create SSDTable write ahead log is deleted. In case of crashes write ahead log can be used to restore the memory table.
Very cool. Could have - one process just taking DB writes and putting them in memory - another writes too-big variables to files on disk - next would go through files and flatten them (like continuous truncate/shrink on a transaction log) - last would take DB reads and go through the memory, bloom filters, and file structure to find and return the requested data.
I think the movie is recommended to left 30 seconds instead of 10s for the ending credit because the next suggestion video covers (in the left bottom side) in the summary time
Question regarding the books: volume 1 and volume 2 are considered as two separate editions for the same content or the same edition for different contents? Another way to ask: Should I but both volumes or just volume 2?
What would be a good example of an application benefiting from "fast write slow read" property of NoSQL DB? Based on what's presented, I'd say most user-facing application, like a typical service a startup would build (e.g. personal calendar organization, etc) doesn't sound like a good fit given reads are pretty important in user-facing traffic.
Object ID, unless you design the system to use a high precision timestamp as the id, which could maybe be an interesting idea. If the Object ID is a timestamp, then object creations are already sorted which could further boost write performance, though there is probably no advantage in the case of updates or deletes.
The explanation of why SStables have to be sorted is not sufficient. In my opinion, the reason is that allowing the SSTables to be sorted allows faster merging and allows the index for the table to be sparse. It doesn't really allow faster table retrieval since running a binary search on disk is not so efficient.
Cassandra initially had size tiered only and later borrowed leveled from RocksDB to solve the space amplification problem, so it's not completely misleading.
this is brilliant! I'm also wondering would this amount/level of knowledge for an advanced DS is enough for tech/system design interview? Obviously I think the interviewer won't ask for implementation so... ig im trying to know how deeper do we need to go than e.g. this channel's few minutes videos?
How is a key-value actually stored and retrieved from disk? Although a SSTable is sorted within itself, since the keys in different SSTables are not related, how does a read request find a key? Surely not by trying all SSTables one by one, that'd be too slow.
Thanks! One of the things I find difficult to find good information on is structuring data. Given I want these x properties, how do so arrange the information to get them, and what technologies are required to do it.
IMPORTANT: Don't forget the Memtable is stored in memory, so if the system crashes, that data will be lost. To avoid losing data, we can maintain a separate log file on disk. Every time we write to the Memtable, we'll also append that write to the log file (no need to sort it as we just use it to restore after a crash). Then once the Memtable contents get written out to a SSTable file, we can erase the log file. That way the log helps us avoid losing writes stuck in memory when a crash happens.
This seems like a fairly important detail.
Kafka is used as the logging system by default in most scenarios
a write-ahead log.
That's the interesting information. Thank you so much.
Bruh, this is just awesome... keep going
This is the perfect amount of depth and overview I’m looking for. Great videos and visuals!!
Yes, awesome video.
+1
This guy is better than my teamlead in term of explaining a concept on NoSQL, thank you , make my day
That's the best system design content I have ever seen on youtube ! This channel is absolutely amazing. It must be tough to squeeze all that valuable knowledge into less than a 10 minutes video. Keep up the excellent work!
This is the most information-dense video on what's so special about NoSQL databases I ever saw. Not a word was superfluous, but the key concepts were clearly transmitted.
I appreciate your efforts. Thanks for making system design more palatable than ever.
One of the concise video to understand how elastic/lucene is using these things to fast write and read.
Great work man!
I can't recall the last time I stumbled upon such great material! Fascinating work!
This channel is by far the best channel that I've found on yt about tech
These videos are superb man, keep up the good work
This channel is such a gold mine!
VERY informative without going into too much complexity. THANKS and congrats for a great video. I'm an MS SQL Server DBA, and the high level explanation you provided was awesome. Thanks again. Best, R.
Really awesome overview of how SQL and NoSQL differ. Agree with Joel below me just the right level of detail to provide value.
besides bloom filter, a sparse index is to help find a key quickly so we only look into a small number of sstables
These videos are incredible! Very well paced and presented!
LOVE THE DARK BACKGROUND! :D:D:D:D (Also the video of course!!)
Great explanation. Resolved all my doubts on how NoSql DBs work. However, I wanted to understand
1) Whether the balanced tree and keys in sorted set is only the object key with pointer to data value or it also contains the actual data?
2) Can a NoSql DB index multiple keys?
3) Why can't SQL DB also implement flushing mechanism in order to speed up writes? I know that they are highly consistent so they need to persist data to disk, but they can simply append the entry in a log file just like NoSql DBs do, and in case of a network partition, first check the log file to sync data in actual database?
Re 3 afaik that's what they already do. But sooner or later it has to write them to b-tree, which I guess is the real bottleneck.
The dark mode was awesome. I think it could be the default from now on
I came here to say this! +1 for dark more, finally!
I love these byte sized video, helps introduce new concepts.
I never experienced such a communicative video with such a simple and easy explanation.. Thanks Alex ..Please keep it up and upload more such videos. I have anyway bought both volume of System Design Book. Thank you so much !!!
That's a cool trick. So what it is essentially doing is spreading out the computer's resources across time, where with a traditional database you will get lots of spikes in processing on the timeline when doing reads and writes. Mind you the attraction of SQL was that you could have multiple indexes and create custom views on the data in a highly relational way, but granted that was very expensive on resources. I think traditional databases were mostly optimised for the deficiencies of the mechanical hard disk drive. I think it may end up as redundant in future as we store our data more on chips.
Thanks for the video. I like videos that don't waste your time with long BS intros.
You read my mind when it comes to "spreading the computer's resources across time"... Which for some use cases makes perfect sense, but not all use cases.
Not sure I agree with the "deficiencies of mechanical HDDs" part of your comment though. But great comment overall.
Perhaps the best educational systems content on the whole of TH-cam right now. Great stuff
Nicely explained. I read all this information in designing data intensive application book. But few topics like memorable and sstables were still bit unclear to me. Got the whole idea now. Great stuff. Keep going
great, you make it sound so simple, I'm writing my own nosql db this weekend ;)
did you start writing
well, did you?
Stuff like this is the future of many forms of education.
I've often wondered how NOSQL databases can achieve higher write throughput than relational DB. Thank you for sharing the techniques involved. Your explanation is clear and the graphics are excellent!
Great work! I wish I had watched this video before trying to learn the architecture behind RocksDB by only looking their documentation, hahaha! Awesome work!
6:56 correction regarding Bloom Filter
If the Key doesn't exist, bloom filter will NOT return False Negative
If the Key doesn't exist, bloom filter MAY return False Positive
In other words.
If bloom filter says there's NO key in page, there's definitely no key in page.
If it says that there's the key in page, there MIGHT be the key in page with some probability.
This probability data structure helps to reduce unnecessary reads.
That's exactly what is said in the video
One additional thing to mention (around th-cam.com/video/I6jB0nM9SKU/w-d-xo.html perhaps) is that the writes are written to memory AND a transaction log to ensure durability. Otherwise whatever was in the MemTable will not persist after a crash. The transaction log can be replayed to rebuild the MemTable.
Thank you for the feedback.
We did have that initially, but decided to take it out to focus on the LSM tree itself.
We knew someone would bring it up, but didn't think it would take this long. 😂
We are glad you did.
I was actually wondering if this were a difference with what I understand of relational dbs. Thanks for pointing it out.
Another amazing video! This format is so vaiuable.
You’ve been hitting it out of the park with these videos! Really enjoy the content.
6:50 “(bloom filters) return a firm no if a key does not exist”. That’s not quite right. Bloom filters returns a firm yes if a key exists. If a key does not exist, it might still return yes with a low probability.
He is correct .. false positive is possible but not false negative
That’s exactly right!
The subtlety here is in his claim that
1. Key does not exist -> returns no
2. Key “might” exist -> probably returns yes
Whereas bloom filters really guarantees
1. Returns no -> key does not exist
2. Returns yes -> key probably exists
i.e. “bloom filters returns a firm no (only) if a key does not exist”
You are correct. Video didn't communicate properties of Bloom Filter well.
in other words, a query returns either "possibly in set" or "definitely not in set".
definitely not in set -> if the key does not exists, 100 % no answer.
en.wikipedia.org/wiki/Bloom_filter#:~:text=A%20Bloom%20filter%20is%20a,a%20member%20of%20a%20set.
What is wrong with you people ? That's exactly what's said in the video. And much simpler than what you try to explain. Am I missing something ? There's other comments like this too, arguing that somehow the video is incorrect, when in fact it is, or at least what they say is the same as what the video says.
Which is if the bloom filter says there's no key, you can trust that and skip to the next level.
Great video. I'm a junior dev that has to implement a chat feature in the next few weeks. This really helped me understand NoSQL. Thanks.
Great visualization of "Designing Data-Intensive Applications" book
This is so high quality. Thank you :)
Great explanation, thank you, this helped reinforce my learnings about LSM-trees from reading. The graphics were especially helpful
Good video. For the further topic development it'd be interesting to see a LSM tree vs Redis RDM/AOF persistence schema comparison.
Sublime, superb, excellent ... again.
Looking at how beautifuly my tired brain understood this, this video deserves a noble prize.
in their book, bloom filters are stored on disk, but here they're shown to be in memory. Hopefully we'll get some eventual consistency
amazing content, thank you for all the hard work you do!
Man this video is awesome, so much information loved it!
Alex - Your lectures and contents are great assets to software engineering community.
one of the best videos so far
I can't wait for my next systems design interview!
Thank you. great video, as always.
I'd like if you guys could go into more detail
This is an awesome overview of LSM tree. If someone wants dig deeper read "Design Data intensive applications".
It is an awesome book.
Excellent presentation!
Very interesting! Loved this video
Great video!
Like many have said, this is a great dense video at a good beginner depth for people like me. I hope there will be a relational db video that complements this if at all possible, since the quality level is so high 🤞
Great Content, thank you very much.
I'm already waiting for Tuesday for a new video, as much as I wait for a new One Piece episode.
Not at all a question I had, but glad I watched because I extensively use Mongo for my own app
Please create a video on size tiered and level compaction strategy as well
Absolutely amazing. Thank you for making the video!
The next step after watching this video is to … watch it again 😂. Awesome as always.
amazing video!
great explanation for beginners
Thanks for the video. Your explanation rises a concern to me : since the memtable is in memory, what happens if the server crashes before flushing ?
Is that memtable distributed or replicated ?
Cassandra, for example, still has a write ahead log.
Generally for the memory table write ahead log is maintained. Once the memory table is moved to create SSDTable write ahead log is deleted. In case of crashes write ahead log can be used to restore the memory table.
LSM Tree에 대한 이해와 작동 방식에 대한 개요를 알 수 있었습니다. ㄳ 합니다
Thank you for the great video. Keep up the good work. ❤
Freaking intuitive talk.
Very cool. Could have
- one process just taking DB writes and putting them in memory
- another writes too-big variables to files on disk
- next would go through files and flatten them (like continuous truncate/shrink on a transaction log)
- last would take DB reads and go through the memory, bloom filters, and file structure to find and return the requested data.
I really appreciated these videos !! Thanks you very much
I would to know what software are you using to produce such presentation 🙏
Amazing video
1:15 what is that "object key" ? The row key that is being edited/added to the keyspace ?
Awesome work, thanks for this!
What software do you use for animation in your videos?
I am very curious
I want to know as well. It is perfect!!!
@@wrondonparticual5113 Maybe this is something :-) th-cam.com/video/H5GETOP7ivs/w-d-xo.html
perfect explanation, thanks
great explanation ❤
I think the movie is recommended to left 30 seconds instead of 10s for the ending credit because the next suggestion video covers (in the left bottom side) in the summary time
Thank you very much.
great explanation!
So much knowledge!!!
Awesome overview.
yeah I freakin love this channel
Thank you!
Question regarding the books: volume 1 and volume 2 are considered as two separate editions for the same content or the same edition for different contents? Another way to ask: Should I but both volumes or just volume 2?
Simply best
Amazing!
Love your videos!
very well explained. Thanks
What would be a good example of an application benefiting from "fast write slow read" property of NoSQL DB? Based on what's presented, I'd say most user-facing application, like a typical service a startup would build (e.g. personal calendar organization, etc) doesn't sound like a good fit given reads are pretty important in user-facing traffic.
awesome video indeed! thank you
Thank you so much!
relational databases don't use btrees, they use b+ trees. the only db i know of that uses btrees is actually mongodb.
No, mongodb use b+ tree
Thank you! When you say sorted, is it by some object id or time?
Object ID, unless you design the system to use a high precision timestamp as the id, which could maybe be an interesting idea. If the Object ID is a timestamp, then object creations are already sorted which could further boost write performance, though there is probably no advantage in the case of updates or deletes.
awesome explanation
The explanation of why SStables have to be sorted is not sufficient. In my opinion, the reason is that allowing the SSTables to be sorted allows faster merging and allows the index for the table to be sparse. It doesn't really allow faster table retrieval since running a binary search on disk is not so efficient.
This is a great video. If I want ti go further is there any good reference for nosql?
Gold Standard vidios.
Cassandra also has Leveled Compaction Strategy so that slide comparing it to RocksDB is a little misleading
Cassandra initially had size tiered only and later borrowed leveled from RocksDB to solve the space amplification problem, so it's not completely misleading.
Wow this was great
This is amazing video
Very good animation
Any idea how Domino databases work in this regard? Do they follow the same concepts? Is the compaction process "Tiering" or "Leveling"?
Actually, many modern SQL are also LSM Tree based, it's not limited to no-sql
hi , can you do a video on how Splunk is use for devops and how it storing its data ?
this is brilliant! I'm also wondering would this amount/level of knowledge for an advanced DS is enough for tech/system design interview? Obviously I think the interviewer won't ask for implementation so... ig im trying to know how deeper do we need to go than e.g. this channel's few minutes videos?
How is a key-value actually stored and retrieved from disk? Although a SSTable is sorted within itself, since the keys in different SSTables are not related, how does a read request find a key? Surely not by trying all SSTables one by one, that'd be too slow.
Thanks! One of the things I find difficult to find good information on is structuring data. Given I want these x properties, how do so arrange the information to get them, and what technologies are required to do it.