How databases scale writes: The power of the log ✍️🗒️
Summary
TLDRIn this informative video, G KCS explores the optimization of database write operations using log-structured merge trees (LSM trees). The script explains how traditional B+ trees in databases can be inefficient for scaling, and introduces the concept of LSM trees that prioritize fast writes using linked lists while also maintaining quick read times through sorted string tables. The video delves into the mechanics of LSM trees, including compaction and the use of bloom filters to speed up search queries, offering a comprehensive look at balancing performance in database management.
Takeaways
- 🌐 The video discusses optimizing database operations by reducing unnecessary data exchanges and I/O calls to improve response times.
- 📚 Traditional databases use B+ trees for efficient insertion and search operations, which are both O(log n) in complexity.
- 🔧 To scale databases, the video suggests condensing multiple data operations into a single query to minimize acknowledgments and headers.
- 🔑 The trade-off for condensing data is the need for additional memory on the server to temporarily store the queries before flushing them to the database.
- ✂️ Write operations can be optimized using linked lists, which offer O(1) constant time complexity for appending data.
- 🔍 However, linked lists are inefficient for read operations, which require a sequential search, leading to O(n) time complexity.
- 📈 The Log-Structured Merge Tree (LSM Tree) is introduced as a hybrid data structure that combines the fast write benefits of a log with the fast read benefits of a sorted array.
- 🔄 LSM Trees work by periodically merging sorted arrays in the background, reducing the number of required read operations and improving efficiency.
- 📊 The video explains the concept of 'compaction' in LSM Trees, where smaller sorted arrays are merged into larger ones to optimize read performance.
- 🛠️ Bloom filters are suggested as a method to speed up search queries by reducing the number of chunks that need to be checked, albeit with a chance of false positives.
- 🔑 The script concludes with the importance of balancing fast writes with efficient reads in database optimization, highlighting the LSM Tree as a practical solution.
Q & A
What is the main topic of the video script?
-The main topic of the video script is optimizing database operations by discussing the use of data structures like B+ trees, linked lists, and log-structured merge trees for efficient write and read operations.
Why are B+ trees preferred in traditional databases?
-B+ trees are preferred in traditional databases because they provide good insertion and search times, both of which are of the order log n, making them efficient for handling SQL commands like insert and select.
What is the main idea behind condensing data queries into a single query?
-The main idea behind condensing data queries into a single query is to reduce unnecessary data exchange, such as acknowledgments and headers, and to decrease I/O calls, which in turn can free up resources and reduce request-response times.
What is the time complexity of write operations in a linked list?
-The time complexity of write operations in a linked list is O(1), which means it is constant time because appending data to the end of the list is a straightforward operation.
What is the disadvantage of using a log for database storage in terms of read operations?
-The disadvantage of using a log for database storage is that read operations are slow, as they require a sequential search through the entire log, which is an O(n) operation where n is the number of records in the log.
What is a log-structured merge tree (LSM tree) and how does it help with database optimization?
-A log-structured merge tree (LSM tree) is a data structure that combines the fast write capabilities of a linked list with the fast read capabilities of sorted arrays or trees. It optimizes databases by allowing fast writes through sequential log appends and fast reads through sorted string tables that are created and merged in the background.
What is the purpose of merging sorted arrays in the background of an LSM tree?
-The purpose of merging sorted arrays in the background of an LSM tree is to improve read performance by reducing the number of chunks that need to be searched during a query, thus decreasing the overall time complexity for read operations.
What is compaction in the context of LSM trees?
-Compaction in the context of LSM trees is the process of taking multiple sorted string tables and merging them into a single, larger sorted array to facilitate faster search queries.
What is a bloom filter and how can it be used to speed up read queries in a database?
-A bloom filter is a probabilistic data structure that can be used to test whether an element is a member of a set. In the context of databases, it can speed up read queries by quickly determining the presence of a record in a chunk, reducing the need for full sequential searches and thus speeding up the overall read operation, albeit with a possibility of false positives.
How does the script suggest managing the trade-off between fast writes and fast reads in database optimization?
-The script suggests using a hybrid approach where writes are fast due to the use of a linked list-like structure, while reads are optimized by merging sorted arrays in the background to form sorted string tables. Additionally, bloom filters can be used to further speed up read queries by reducing unnecessary searches.
Outlines
📚 Database Optimization with B+ Trees and Logs
In this paragraph, the speaker discusses the challenges of scaling databases and introduces the B+ tree data structure, which is crucial for efficient SQL command execution. The B+ tree is likened to a binary search tree but with multiple paths from each node, offering good insertion and search times. The speaker then explores the idea of reducing unnecessary data exchange and I/O calls to improve database performance. The concept of condensing data queries into a single operation is proposed to enhance efficiency, although this comes with the trade-off of requiring additional memory. The paragraph concludes with a teaser about the fastest data structure for write operations, hinting at the linked list's advantages.
🔄 Leveraging Linked Lists and Sorted Arrays for Optimal Performance
The speaker elaborates on the use of linked lists for fast write operations and the subsequent need for a data structure that supports quick read operations. The concept of a log-structured merge tree (LSM tree) is introduced as a hybrid approach, combining the benefits of fast writes from a linked list and efficient reads from sorted arrays. The mechanics of how data is appended to a log and then sorted before being persisted in the database are explained. The speaker also addresses the inefficiency of constantly sorting large datasets and introduces the idea of maintaining sorted chunks to optimize read operations. The paragraph ends with a discussion on the trade-offs between read and write speeds and the strategy for merging sorted arrays to improve performance.
🔍 Enhancing Database Read Efficiency with Merging and Bloom Filters
This paragraph delves into the process of merging sorted arrays to form larger chunks, which reduces the time complexity for search queries. The speaker explains how the database can manage chunks of varying sizes and the decision-making process for when to merge these chunks, drawing parallels to the merge sort algorithm. The concept of a bloom filter is introduced as a method to speed up search queries by reducing false positives, which in turn decreases read times. The speaker suggests that creating a bloom filter for each chunk can help avoid unnecessary reads and improve the overall efficiency of the database system.
🌐 Conclusion on LSM Trees and Future Optimization Techniques
In the final paragraph, the speaker wraps up the discussion on log-structured merge trees, summarizing the key points about using linked lists for fast writes and sorted arrays for efficient reads. The process of compaction, which merges multiple sorted string tables into a single array, is highlighted as a critical component of LSM trees. The speaker also hints at further optimization techniques, such as the use of bloom filters, to enhance search query performance. The paragraph concludes with an invitation for feedback and suggestions from the audience, emphasizing the ongoing nature of database optimization and the potential for further improvements.
Mindmap
Keywords
💡Database Optimization
💡B+ Tree
💡I/O Calls
💡Condensing Data
💡Linked List
💡Log Structured Merge Tree (LSM Tree)
💡Compaction
💡Sorted String Table
💡Bloom Filter
💡False Positives
Highlights
Optimizing database writes by reducing unnecessary data exchange and I/O calls for faster response times.
Introduction to the B+ tree data structure, which offers good insertion and search times due to its multiple paths per node.
The concept of condensing data into a single block for efficient bandwidth use and reduced I/O operations.
Trade-off between using additional memory for condensed data queries and the benefits of fewer I/O operations.
The LinkedList data structure's advantage in write operations due to its constant time complexity.
The Log-Structured Merge Tree (LSM Tree) as a hybrid approach combining the benefits of fast writes and sorted arrays for efficient reads.
The disadvantages of using a log for read operations, which require sequential search and are slow compared to tree-based structures.
The importance of maintaining fast writes and reducing I/O operations while addressing the slow read issue.
The use of sorted arrays to improve search times from O(n) to O(log n) after converting a linked list.
Mechanics of persisting data in sorted order to the database to facilitate efficient querying.
The process of merging sorted chunks in the background to maintain a balance between write and read performance.
The concept of compaction in LSM Trees, which merges sorted string tables to optimize read queries.
The management of memory and chunks to prevent slowing down write operations while optimizing read times.
The use of bloom filters to speed up search queries by reducing the number of chunks that need to be searched.
The strategy of merging sorted arrays in the background to form larger sorted arrays for faster searches.
The decision-making process for when to merge sorted arrays in LSM Trees, similar to merge sort.
The impact of varying block sizes on read operations and the use of bloom filters to speed up queries across blocks.
The introduction to log-structured merge trees and their role in optimizing both write and read operations in databases.
Transcripts
hey everyone this is G kcs today we'll
be talking about a way in which we can
optimize rights in our database so you
have your client which sends information
to your server the server has to write
to the database because it needs to
maintain some state how do you scale
this you can think of your database as a
data structure the speedup queries the
traditional database uses a data
structure called a B+ tree this is like
a binary search tree without the binary
inside it there's multiple paths that
each node can follow and the B+ tree is
preferred because it gives you good
insertion and search times both of them
are order log n so whenever you fire a
SQL command of an insert or a select
that maps to an insertion or a search
operation in the B+ tree and the
underlying data structure is manipulated
each of these operations requires an
acknowledgment from the database which
says yes I have successfully executed
the request the scale our database we
want to reduce the unnecessary exchange
of data which is acknowledgments and
headers and also we want to reduce the
i/o calls which will help us free up
some resources and reduce the request
response times if we can condense all of
this data into one block and send it in
one shot to the database and get one
acknowledgment that's a good idea
so that would be more efficient use of
your bandwidth because you don't have
any extra data that you are sending
around and also you're going to be doing
less work because there'll be one i/o
called one I or response condense data
queries into a single query that's our
first idea the server has to give up
some memory to condense this data query
these bunch of data queries so that
requires additional memory so this is
one of the drawbacks and the reason we
did this which is one of the advantages
is that we need to use lesser i/o
operations if you have a lot of write
operations what is the fastest data
structure which can help you write
operations quickly
[Music]
the link list it's the most basic data
structure if you think of it all you
need to do is when whenever there's a
write in a linked list you just go to
the end and append something to it and
that's exactly what we are trying to
optimize your so the write operations in
a linked list are order one it's
constant time because all you need to do
is you have this linked list over here
and you go to the end and you just add a
node and it goes to the next node we
have a well-known data structure which
follows the philosophy of a linked list
which is called a log okay and you can
get the idea of whether log structured
merge tree is coming from we are going
to be using a log to assist data because
it's really fast when it comes to write
operations what is the disadvantage of a
log read operations are really slow in a
log if you need to find something you
just can't jump to one point you have to
actually search through sequentially the
entire log and if you can think about
your database as a log that's a huge
amount of data which you'll need to read
for every query that a person will be
sending so the advantage of this is that
you have fast writes but the clear
disadvantage is that you have slow reads
so we have two clear advantages with us
which we want to keep because fast
writes and lesser i/o operations is
something that sounds really good but
the drawbacks are something that we want
to cut down on so the additional memory
you can't really help much because if
you need to condense the queries and
keep them somewhere they have to be
somewhere so the additional memory is
fine it's not something we can optimize
on much all you can do is you can kind
of constrain the maximum number of
blocks that you'll be keeping in memory
before you flush into the database so
this thing can be managed what we really
don't want to do is we don't want to
slow down our read operations if you're
thinking about Facebook where there's a
lot of people who are posting things the
only worse thing compared to a slow post
is a slow reader operation where you
want to know what your friends are doing
and it takes you 30 seconds to actually
get that news feed onto your onto your
browser so slow leagues is something
that we definitely want to avoid and
what can we do about that well this is
some good
- the first thing is that slow reads on
what you know your your reading not on
the log you don't want to be reading on
this linked list because it gives you by
definition a sequential search which is
order n so that's pretty bad
can you improve on this no not as a
linguist you can't but if you convert
your data to a far more sensible data
structure which is something like a tree
or something like a sorted list a sorted
array that makes your searching really
fast yeah so if you have instead of the
linked list if you use something like a
sorted array then your search time
becomes order log n but this seems
counterintuitive because you already had
a B plus tree which was giving you log
in such time it was giving you log in
insertion time so what should we take a
B plus tree or a linked list a linked
list is great at writing but terrible at
reading but the reason we have moved on
to it is because B trees give us or a
write performance and that's why we have
the MAGIX addition of using a linked
list with a sorted array to get great
write speeds and great read speeds so if
we would have this data in a sorted
array it would take us login time which
is really fast this takes less time
compared to order n of course the
sequential search is really slow so can
we convert our linked list to a sorted
array we can we can we don't want to do
it in the memory because that defeats
the purpose the whole point of having a
linked list was so that you do fast
insertions if you want a sorted arrays
insertions are really slow so you won't
do it here you instead will do it
somewhere over here in the database okay
so whatever information you get from the
client you sort it and then you persist
it so that the read operations are super
fast let's talk about the mechanics of
how this is going to work firstly we
mentioned that we need some sort of a
log that's over here which is being
appended to by the server so every time
a new record comes in the latest record
over here is J
so point 31 you keep appending to this
log after a certain point which is a
threshold of the number of Records you
can keep in memory you persist this to
the database in one shot so what's
happening here in the DB is that this
data is going to be sorted before it is
persisted or rather it's going to be
persisted in a sorted fashion so you can
see that the numbers here are jumbled up
while here it's 12 17 19 23 31 47 it's a
nice sorted way what you can do here on
top of this is do a binary search which
allows you to query this data in a
efficient manner but what if you have
some more data coming in so if after
this append is complete you want to
append new stuff to your database so you
don't just take it and immediately push
it to the database if we do the same
thing as we did over here now that we
have these records and you want to
persist them the database all you need
to do is you need to send this
information to the DB when you want to
persist this in the DB the DB can do two
things one is it can take these six
records and merge it with these six
records so it'll create a sorted file of
size twelve but that's not maybe the
smartest thing to do because if you
think of it this is going to happen all
the time after 10,000 records in the DB
you send in six more records what it
needs to do is it needs to sort n
thousand and six records for the
additional six records that you sent
here so the increment of six records is
actually forcing the entire database to
be sorted you know flushing is nothing
compared to sorting huge bunch of
numbers this is time complexity and log
in so how do we optimize this one of the
things you can do is instead of merging
arrays all the time you can keep them in
sorted chunks so your database is going
to be represented by chunks this is a
chunk of size six this chunk after being
sorted will be of size six now whenever
there's a read query in your database
all you need to do is you need to search
through this chunk do a binary search on
this chunk if you don't find it then you
do a binary search on this chunk and
there's just two chunks that you have to
go through this is better than slowing
down your write operations tremendously
so
you're right operations are reasonably
fast even now but your read operations
are slightly slower so if you have n
insertions the number of chunks you'll
have is divided by six if you draw the
graph for this you know it's after all a
linear graph so this is again order n n
by six is the graph literally so your
read times are extremely slow even now
imagine in something like Facebook you
have billions of records in the database
1 billion divided by 6 is still very
very slow so how do you optimize this
well you can use some sort of a hybrid
approach which is taking some records
and merging it with the other records as
long as the short time is not too high
so when you have six ecords in six
Eckerd's over here you merge them
together to get one sorted array and
this uses the standard mode sort
technique so I take the first two
elements over here because they're
sorted I know that they're the smallest
in their respective areas so twelve and
one of the smallest elements in these
two respective areas which one is
smaller one so I take one and Sam and I
pump it out over here now my point is
still at twelve over here while my
pointer has changed to 26 over here 2l
is smaller than 36 I get Tim pointer
changes to this point John which is at
position 17 so 17 is smaller than 36 I
take John and this is the basic merging
process when you're taking two sorted
arrays and you want to merge them into a
single sorted array what you need to do
is you need to move with the two
pointers and keep taking the smaller
element so the next one will be iris
which is 19 and then push the pointer
forward so it had moved here these are
now gone so there's 23 again it is
bigger than 36 so gada will come and
they'll be Jane and then finally after
Jane when the pointers are 47 with Mac
47 is greater than 36 so you will pull
out Larry and then so on and so forth so
you get this nice sorted array of size
12 so now what's happening is that every
time you are getting a chunk you are
deciding on whether or not you should
merge this chunk with the existing
chunks in the background what we are
going to do is we are going to take
chunks and we are going to merge them
together to make
just sorted Aries so that when there is
a search query this large sorted array
can help us reduce the overall time
complexity in the background what we are
going to do is we are going to take
chunks and we are going to merge them
together to make larger sorted areas so
that when there is a search query this
large sorted array can help us reduce
the overall time complexity to clarify
things if you get three chunks in total
so that means you have 18 records in
total which are broken into three chunks
then the time required to search in one
chunk is log to the base 2 of 6 so that
is approximately equal to 3 and if you
have to search in all the chunks for a
particular record let's say I'm
searching for record number 8 I saw sure
I don't find it I searched sure I don't
find it answer and I find it in the end
so the total number of operations I'll
need to do here are log of 6 to the base
2 3 times so that is in total around 9
operations while instead if in the
background I was able to merge two
sorted arrays and change that into a
sorted array of size 12 then the total
number of operations I have to do in
this for these two chunks is just 4
operations and the number of operations
I have to do here are 3 so 3 plus 4
gives you 7 operations so there's a
clear saving here but obviously you need
to sort I mean you need to merge two
sorted arrays and then persist it so
that has some overhead let's see what is
the best approach
if you get another sorted chunk of size
six what I'll do is I'll take these two
chunks and merge them together and have
two sorted chunks of size 12 can I do
better yeah I can take those two sort
chunks of size 12 and merge them into a
single sort of chunk of size 24 so log
of 24 to the base 2 is equal to 5
approximately and instead if I had them
all 4 if I had all four chunks unmerged
then I would have 3 into 4 which is 12
operations so you can see that there's a
clear saving of 5 instead of 12 if you
sort arrays together so when do we
decide to sort arias it's very similar
to how the merge sort works if you have
two blocks of size 6 you convert them
into a block of size 12 if you have two
blocks of size 12 you convert them into
a block of size 24 and so on all the way
up till your maximum size which is going
to be n number of insertions that's the
maximum possible size you can have what
happens with this strategy is that you
have a large number of blocks of varying
size for example this one is of size six
this one is of size 12 and so on and so
forth you'll have some blocks of 24 also
which have been merged after some time
so your read operation is spread across
these blocks and to speed up your read
operation you can try some clever hacks
the idea you can apply here is something
called a bloom filter there's a video I
made on that you can check it out
the basic idea of a bloom filter is
quite simple if you have a book let's
say with a lot of words in it so you
want to find the word cat in that book
sociaty now one of the things you can do
is you can search the entire book for
the word cat or if the book provides you
a particular data structure which is
called a bloom filter yeah I had 26
positions in this bloom filter there's 1
for a 1 for B 1 for C D and so on and so
forth if there exists any word in the
book starting with the letter C I mark
this as true I mark this as 1 so the
position of C will be marked as 1 so if
the word cat exists in this book
definitely this point is going to give
marked as true
think about some edge cases what if I
have the word Karuna in this book will
this letter be marked yes but what if I
don't have the word cat and I just have
the word karana in this book will this
letter be mark yes so that's called a
false positive
so in bloom filters you can have false
positives you cannot have false
negatives if C if there is no word with
C there's no way that this letters going
to be marked that's the general idea of
a bloom filter and you can think about
you know your book being the database
and your search query being the bloom
filter query if you are looking for
whether this record exists in this chunk
all you need to do is you need to create
a bloom filter on top of this chunk
which tells you whether or Eckerd exists
in this in this list or not so this
speeds up your querying because you get
false positives the rate of false
positive can be managed by increasing
the number of bits yeah instead of
saying whether there's a letter with but
there's a word with C I can say are
there any words it's C a so I'm taking
combinations now so Co is going to be
marked but C is not going to be marked
so this is going to be a proper negative
and I can speed up queries that way I
can use that concept to create bloom
filters here and speed up my search
queries also anytime I merge two areas
I'm going to be requiring a separate
bloom filter for this one a good idea is
to create a bloom filter of larger size
because there's more information here
the chance of a false positive is higher
therefore I need to increase the
information in the bloom filter to
reduce the chance of a false positive
this way when you are reducing the false
positives you are indirectly reducing
the read times also you don't have any
useless reading that you are doing
because this is accurate there's a lot
more to log structured merge trees but
this is a reasonable introduction to the
concept what you want to do is you want
to speed up writes for that you use the
data structure which is a linked list
but you can't read well on linked lists
so you in the background merge sorted
arrays which can be binary searched to
get fast read operations so your rights
are fast because you're flushing rights
in in a sequential fashion but your
reads also fast because you are reading
from sorted tables which have been made
in the background that's the general
idea for lsdm some of the important
terms you can take from here are this
sorted set of Records is called a sorted
string table yeah the reason being that
it is a sorted string table the other
thing that we did off of taking these
two arrays and merging them together is
called compaction so compaction is
taking lots of sorted string tables and
using the merge process condensing them
into a single array so that we can do
fast search queries if you have any
doubts or suggestions on this you can
leave them in the comments below if you
like the video then make sure to hit the
like button and if you want
notifications for further videos like
this hit the subscribe button I'll see
you next time
Ver Más Videos Relacionados
Google SWE teaches systems design | EP1: Database Design
Choosing a Database for Systems Design: All you need to know in one video
Google SWE teaches systems design | EP22: HBase/BigTable Deep Dive
Google SWE teaches systems design | EP27: Search Indexes
Introduction to NoSQL databases
Binary Search Trees (BST) Explained in Animated Demo
5.0 / 5 (0 votes)