Це відео не доступне.
Перепрошуємо.
The Secret Sauce Behind NoSQL: LSM Tree
Вставка
- Опубліковано 29 сер 2022
- Subscribe to our weekly system design newsletter: bit.ly/3tfAlYD
Checkout our bestselling System Design Interview books:
Volume 1: amzn.to/3Ou7gkd
Volume 2: amzn.to/3HqGozy
Digital version of System Design Interview books: bit.ly/3mlDSk9
Animation tools: Illustrator and After Effects
ABOUT US:
Covering topics and trends in large-scale system design, from the authors of the best-selling System Design Interview series.
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
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
LSM trees are actually used a lot in modern SQL databases as well. the idea is to represent a relational table as a series of packed records - [k: primary key v: field 1, field 2]. Indices can be created on other fields by creating additional k:v pairs - [k: field 1 v: primary key] so an index scan just becomes two NoSQL lookups for each result.
Spot on. One thing to keep in mind is that all databases, SQL or noSQL, are based on the principles of key value operations and the transaction consistency algorithms that allow for data integrity. The core calculus and proofs behind these systems are all done in the perspective of only two types of operation: read and write, each to some concept of a key.
These algorithms vary wildly and come with varied pros and cons, some with very weird limitations that actually DO prevent SQL semantics (the FaunaDB and FoundationDB distributed algorithms require the W/R set to be known before starting the transaction, and SQL requires conditional and unbounded W/R sets to fully abide by the spec).
@@romannasuti25 what do you mean by “W/R set” ?
@@greyowl3787 write/read. Basically, Fauna and Foundation use a distributed transaction system that can only provide full ACID guarantees with exact read and write keys known before the transaction even starts. This means dependent querying is usually not possible, like "SELECT name IN users WHERE id = (SELECT friend IN users WHERE name = x);" simply because the result of the inner query changes the write set of the outer query based on its result. In some cases a good query engine can narrow down to a fixed "maybe W/R" set if the results are well bounded (either single element or known countable range), but generally they don't bother with SQL support for this reason.
@@greyowl3787 write/read i assume
I appreciate your efforts. Thanks for making system design more palatable than ever.
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!
These videos are superb man, keep up the good 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.
One of the concise video to understand how elastic/lucene is using these things to fast write and read.
Great work man!
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.
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!
This channel is by far the best channel that I've found on yt about tech
great, you make it sound so simple, I'm writing my own nosql db this weekend ;)
did you start writing
well, did you?
I can't recall the last time I stumbled upon such great material! Fascinating work!
These videos are incredible! Very well paced and presented!
besides bloom filter, a sparse index is to help find a key quickly so we only look into a small number of sstables
LOVE THE DARK BACKGROUND! :D:D:D:D (Also the video of course!!)
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?
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.
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!
Really awesome overview of how SQL and NoSQL differ. Agree with Joel below me just the right level of detail to provide value.
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 !!!
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
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
Good video. For the further topic development it'd be interesting to see a LSM tree vs Redis RDM/AOF persistence schema comparison.
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!
Another amazing video! This format is so vaiuable.
One additional thing to mention (around ua-cam.com/video/I6jB0nM9SKU/v-deo.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.
This channel is such a gold mine!
amazing content, thank you for all the hard work you do!
LSM Tree에 대한 이해와 작동 방식에 대한 개요를 알 수 있었습니다. ㄳ 합니다
Sublime, superb, excellent ... again.
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.
Please create a video on size tiered and level compaction strategy as well
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.
Thank you. great video, as always.
I'd like if you guys could go into more detail
Great visualization of "Designing Data-Intensive Applications" book
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.
Man this video is awesome, so much information loved it!
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 🤞
This is an awesome overview of LSM tree. If someone wants dig deeper read "Design Data intensive applications".
It is an awesome book.
great explanation for beginners
Stuff like this is the future of many forms of education.
I really appreciated these videos !! Thanks you very much
I would to know what software are you using to produce such presentation 🙏
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
Perhaps the best educational systems content on the whole of UA-cam right now. Great stuff
Great explanation, thank you, this helped reinforce my learnings about LSM-trees from reading. The graphics were especially helpful
Very interesting! Loved this video
Not at all a question I had, but glad I watched because I extensively use Mongo for my own app
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
I can't wait for my next systems design interview!
This is so high quality. Thank you :)
The next step after watching this video is to … watch it again 😂. Awesome as always.
Alex - Your lectures and contents are great assets to software engineering community.
Absolutely amazing. Thank you for making the video!
Looking at how beautifuly my tired brain understood this, this video deserves a noble prize.
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.
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.
Great video!
amazing video!
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?
Amazing video
1:15 what is that "object key" ? The row key that is being edited/added to the keyspace ?
Excellent presentation!
Thank you for the great video. Keep up the good work. ❤
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.
Thank you!
Any idea how Domino databases work in this regard? Do they follow the same concepts? Is the compaction process "Tiering" or "Leveling"?
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.
hi , can you do a video on how Splunk is use for devops and how it storing its data ?
perfect explanation, thanks
very well explained. Thanks
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?
So much knowledge!!!
great explanation ❤
one of the best videos so far
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 :-) ua-cam.com/video/H5GETOP7ivs/v-deo.html
Why DynamoDB uses B-Tree?
DynamoDB is highly optimized for low latency reads.
Awesome work, thanks for this!
awesome explanation
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.
Amazing!
How does Mongodb compare to the two types explained in the video?
This was my question as well. Does it also use an lsm tree or some other approach
When searching why does it need to search at all levels? It needs to search at the latest level right? Can someone help me understand this.
The keys, when compacted, are deleted from their original level, and added to the next level.
yeah I freakin love this channel
great explanation!
I don't really understand them, but it's cool!
Awesome video! I'd love to know how densely ordered vectors for database storage work next :)
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.
Awesome overview.
This is a great video. If I want ti go further is there any good reference for nosql?
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 so much!
Thanks
Great explanation!
awesome video indeed! thank you
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.
Hi, i just wonder why the second volume has not been available in kindle yet :( i'm from Vietnam and shipping is expensive
This is amazing video
Very good animation