The Secret Sauce Behind NoSQL: LSM Tree

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.

[@Kxneki2433]

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.

[@jerichaux9219]

This seems like a fairly important detail.

[@sealuke2724]

Bruh, this is just awesome... keep going

[@JoelBrubaker]

This is the perfect amount of depth and overview I’m looking for. Great videos and visuals!!

[@akash-kumar737]

Yes, awesome video.

[@chrisodillman3355]

+1

[@phanphong3533]

This guy is better than my teamlead in term of explaining a concept on NoSQL, thank you , make my day

[@CommandantNOVA]

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.

[@romannasuti25]

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).

[@greyowl3787]

@@romannasuti25 what do you mean by “W/R set” ?

[@romannasuti25]

@@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.

[@akash-kumar737]

[@ismailmo4]

@@greyowl3787 write/read i assume

[@maxil122]

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!

[@mr_nature]

I appreciate your efforts. Thanks for making system design more palatable than ever.

[@bardhan.abhirup]

These videos are incredible! Very well paced and presented!

[@AminAramoon]

These videos are superb man, keep up the good work

[@nishantgoel769]

One of the concise video to understand how elastic/lucene is using these things to fast write and read. Great work man!

[@danielgospodinow]

I can't recall the last time I stumbled upon such great material! Fascinating work!

[@BRBearUSA]

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.

[@susingh2]

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 !!!

[@bazoo513]

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.

[@arthursoares610]

The dark mode was awesome. I think it could be the default from now on

[@guptaanmol184]

I came here to say this! +1 for dark more, finally!

[@rafaelacioly3252]

This channel is by far the best channel that I've found on yt about tech

[@tomtomsiesie5436]

Another amazing video! This format is so vaiuable.

[@bobdinitto]

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!

[@balaclava351]

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.

[@LeoFuso]

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!

[@Konservator69]

Good video. For the further topic development it'd be interesting to see a LSM tree vs Redis RDM/AOF persistence schema comparison.

[@sampleshawn5380]

Man this video is awesome, so much information loved it!

[@richsadowsky8580]

Really awesome overview of how SQL and NoSQL differ. Agree with Joel below me just the right level of detail to provide value.

[@jiamingliu192]

Absolutely amazing. Thank you for making the video!

[@Andrew-rc3vh]

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.

[@BRBearUSA]

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.

[@cexploreful]

LOVE THE DARK BACKGROUND! :D:D:D:D (Also the video of course!!)

[@alamelu85]

Alex - Your lectures and contents are great assets to software engineering community.

[@frederickbarbarossa2746]

besides bloom filter, a sparse index is to help find a key quickly so we only look into a small number of sstables

[@modolief]

Sublime, superb, excellent ... again.

[@arno.claude]

This channel is such a gold mine!

[@lechprotean]

great, you make it sound so simple, I'm writing my own nosql db this weekend ;)

[@chaoluncai4300]

did you start writing

[@EduardAlexandru]

well, did you?

[@eliyahubasa9401]

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.

[@TheOnlyRealBreadIntheWorld]

amazing content, thank you for all the hard work you do!

[@roct07]

This is so high quality. Thank you :)

[@obedgennius1401]

I really appreciated these videos !! Thanks you very much I would to know what software are you using to produce such presentation 🙏

[@MostafaZeinali]

Thank you for the great video. Keep up the good work. ❤

[@ibgib]

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 🤞

[@KristjanKask]

Awesome video! I'd love to know how densely ordered vectors for database storage work next :)

[@anilkaliya3375]

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

[@shakedrosenblat1925]

Thank you. great video, as always. I'd like if you guys could go into more detail

[@aaronprindle385]

Awesome work, thanks for this!

[@BiggRanger]

Excellent presentation!

[@javisartdesign]

very well explained. Thanks

[@AllOfMyWat]

I can't wait for my next systems design interview!

[@sanzharsuleimenov6380]

Great explanation!

[@peepeepoopoo2243]

Great video!

[@pashachechehov3483]

Great visualization of "Designing Data-Intensive Applications" book

[@ethanmye-rs]

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.

[@quirkyquerty]

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

[@dhpark7509]

great explanation!

[@mnchester]

amazing video!

[@jrabelo_]

perfect explanation, thanks

[@carolinegr]

One additional thing to mention (around kzbin.info/www/bejne/f2fNc2Okgp6Ggbc 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.

[@ByteByteGo]

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.

[@ibgib]

I was actually wondering if this were a difference with what I understand of relational dbs. Thanks for pointing it out.

[@faris_id_music]

one of the best videos so far

[@AndyThomasStaff]

Great explanation, thank you, this helped reinforce my learnings about LSM-trees from reading. The graphics were especially helpful

[@aus10d]

Very interesting! Loved this video

[@galeop]

Amazing video 1:15 what is that "object key" ? The row key that is being edited/added to the keyspace ?

[@caseyspaulding]

Thank you!

[@axa993]

Awesome overview.

[@raviv5109]

Thank you so much!

[@chaoluncai4300]

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?

[@StephenGillie]

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.

[@rbelatamas]

great explanation ❤

[@allisonmachado]

awesome video indeed! thank you

[@arunkutube]

great explanation for beginners

[@adamaiken00]

This is a great video. If I want ti go further is there any good reference for nosql?

[@dmytrosolovei6025]

Love your videos!

[@shoobidyboop8634]

Stuff like this is the future of many forms of education.

[@DK-ox7ze]

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?

[@bojandolinar1535]

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.

[@GyroCannon]

Not at all a question I had, but glad I watched because I extensively use Mongo for my own app

[@LuccasMaso]

Amazing!

[@plussin2760]

LSM Tree에 대한 이해와 작동 방식에 대한 개요를 알 수 있었습니다. ㄳ 합니다

[@DarknessGu1deMe]

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.

[@wrondonparticual5113]

What is the animation software used? It is beautiful

[@willl0014]

So much knowledge!!!

[@noahgsolomon]

awesome explanation

[@thomasrobin]

Amazing Content! Does anyone know how these animations are made?

[@doxologist]

Perhaps the best educational systems content on the whole of KZbin right now. Great stuff

[@pdteach]

Simply best

[@Chauhannitin]

Very good animation

[@paddyd7642]

Thank you! When you say sorted, is it by some object id or time?

[@big0bad0brad]

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.

[@vikasgupta1828]

Thanks

[@ThangNguyen-je8kv]

The next step after watching this video is to … watch it again 😂. Awesome as always.

[@sophiiisticated]

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

[@Garvitatri]

thx and subscribed

[@singhsaubhik]

This is an awesome overview of LSM tree. If someone wants dig deeper read "Design Data intensive applications".

[@venkataramaraoemmadi378]

It is an awesome book.

[@akash-kumar737]

thanks

[@VirgoBoy2991]

Hi, i just wonder why the second volume has not been available in kindle yet :( i'm from Vietnam and shipping is expensive

[@badrbellaj]

brilliant

[@thisisnotok2100]

yeah I freakin love this channel

[@geck1204]

Wow this was great

[@lesmatheson6001]

Very interesting

[@AmrishPandey]

This is amazing video

[@paramvirsingh5640]

Looking at how beautifuly my tired brain understood this, this video deserves a noble prize.

[@adatalearner8683]

Is the concept of SS tables specific to a specific type of NOSQL database(Cassandra), or generic ?

[@wave9303]

hi , can you do a video on how Splunk is use for devops and how it storing its data ?

[@thelonearchitect]

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 ?

[@lwfeagan]

Cassandra, for example, still has a write ahead log.

[@nitinagrawalbst]

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.

[@anvogel99]

Impressive

[@BuyHighSellLo]

How does Mongodb compare to the two types explained in the video?

[@ckirkyg]

This was my question as well. Does it also use an lsm tree or some other approach

[@mohawkgwai]

Cassandra also has Leveled Compaction Strategy so that slide comparing it to RocksDB is a little misleading

[@raphaelcarvalho4288]

Cassandra initially had size tiered only and later borrowed leveled from RocksDB to solve the space amplification problem, so it's not completely misleading.