So, I've always been working with databases, a lot of traditional databases, like DB2 or
Wackel Postgres, using traditional Beatriz.
I've also been developing a rocket for you, gabaite, that uses robs DB and SM trees.
And now I'm developing a rocket for MongoDB, that uses right tiger for the storage that
has as Beatriz, but a modern version of Beatriz.
So, the goal is to compare not only the main differences, but the different optimizations
that were made on it, because we can go fast and have only one slide and say,
LSM tree is better to write, Beatriz is better to read.
First, it's not completely true, both improve the two workloads, but also there is no
database where you're only right, and there is no database where you're only read, usually
you put something in the database with the goal of growing it later.
And even if you write, if you have a writer, we work load on your database.
When you write, you may read a lot also.
For example, except if you, when you insert in a skill database, the database must check
if the key already exists, or raise a narrow if not, it has to read for that.
Even if you upset, you don't have to read, but if you have secondary indexes, you cannot
just upset them, you have to write something.
And think about the MVC visibility, think about checking if something is locked or not,
checking the foreign keys, so finally, you may think that you have a write every workload
because you're ingesting a lot of data, but the database is doing a lot of reads behind
that.
Something that is sure in databases, you need sorted structures.
You can write to a log, you can write to it table, but if you want to query, you want
to query some values, and then you need to get a structure to find those values.
For point queries, the structure can use a hash or be sorted, for range queries, it must be sorted.
So the data must be indexed because you query it, and it must be indexed with a sorted
structure.
And there is an additional constraint in most of databases.
You have a lot of data, so this sorted structure, the index, cannot fit entirely in memory.
We need a structure that has some optimization for some parts in memory, but also when
it comes from disk.
If I take an example of sorted data, so this data is sorted, each line is sorted, I think
of it like blocks on disk, for example, they are not all sorted, but they are not overlapping,
which is quite good.
With this data, I can get it sorted quite easily.
If I know where to start, I just need a pointer to the block where I need to start.
And if in addition to that, in each block, I have a pointer to the offset of the next block
logically sorted.
I can just follow the pointers and get something sorted.
But this is a lot of pointers to follow if it's on disk.
This is a lot of latency.
So to accelerate those search, we can put more metadata in memory to get faster to a specific
value.
For example, if I search for my name in that, I can pick a pointer, go to it, I see that
it is after it, then I take another one that is later, it is before it, and with this
deco to me, I can finally find my name with following less pointers just because I had
a bit more information in memory.
We can put even more in memory.
We can put also not only some pointers, but some values.
For example, the skip list where I can read the list and see that everything that starts
after F, I can skip directly to a pointer there and go directly to the block.
So that's really effective.
Having a structure that is optimized in memory, I can skip list and having a structure
on disk where I don't have to follow too many offsets in the file, too many six in the
files.
And we can go further with a bit free because the problem is at some point the metadata
that you put in memory to be efficient and if you have a lot of data may not fit entirely
in memory.
So the idea of B3 is to have multiple levels of metadata before going to the final
block that holds your data.
This is a B3 where at the top, I have root information with some value that will tell
me where I can find more detailed information about the ranges and if I search again
for a value there, I start at the root, there is only one root, I know where to start.
And then I see that the F, I may have more information in another block at a lower level.
And finally, after some levels, I can go directly to the block that holds my value.
So this is quite efficient to read.
The idea of the B3, the B3 plus 3 is that the data is only on the leaf nodes and the
internal nodes, the root and the branches, just help to go to the right leaf.
And initially the idea of a B3 was that the same format was used for the branches,
the internal nodes and the values and it's just those that are read more often that stay
in memory, like probably the root will be in memory.
But there are some betrays with more optimisation when it is in memory.
Before that, this is a point query.
If I want to do a range query, I need some more information.
For example, like we have seen before, a pointer to the next one so that I can just follow
to the next one to do my one scan.
Lot of B3s use that, but on the right, it means that those pointers must be updated.
And when you update, you need to lock.
There is an alternative, for example, wide tiger B3s, they do not store links between the
leaves to one scan horizontally.
They go back to the branches to see the next block, which is more efficient on the right
because you don't have to update those pointer, less efficient on reads, but the optimisation
on the read there is that wide tiger doesn't really put the offset on files there.
It adds real burn tells addresses in memory when the internal nodes are in memory.
So more optimisation for the branches for the internal nodes and navigation for it to avoid
writing too much on the others.
The big problem with B3s is that everything has a place and this is why it is easy to find,
but if everything has a place, an insert must go to a specific block and when this
block is full, then we need to make some room on it, like split it, and the big problem
is that we have multiple pointers to update.
So you see, for example, that this one is the one that we want to avoid to update in right
tiger in traditional B3s, it is updated there.
So to go faster on wide, because this involves a block split sometimes for some insertion,
to go faster, the idea of the LSM tree is that there is not this constraint that a value
is at a specific place, you see multiple, it's not blocks, it's larger, it's multiple files,
that are sorted inside them, but they have overlapping values and it's not only files,
there is also one in memory, which means that if I'm looking for a specific value, I need
to read from multiple places, so you see how it is less efficient for reads, because you need
to read from multiple places, but again, this can be optimized, for example, in RoadsDB and
in many LSM trees, you have Bloom filters that can just tell you this value, no need to look
at this file, it's not in this file, there are also, for example, in RoadsDB, at least in
UGABITDB improvements on RoadsDB, the minimum value and maximum value of which columns
is stored, so that maybe you can just keep some files, so everything can be faster, but finally,
it has to be read from multiple places and do a merge of it and of sort merge to preserve
the order there, but when you write, it's easier, because there is no specific place, you can
write where you want, then you choose the first term, you write in the memory table, that is
on top of it, and of course you are looking at a specific size for it, so when it is full,
the memory table will be flushed to a file and you can use again another memory table for that,
so it's a flushed in the background to more file, then it's increased the number of files,
you don't want to increase the number of files too much, because when you read it,
you have to read a lot of files, so there is a background compaction that happens that reads a few
files, a few small files to build a larger file and have less to read, but again, so this is additional
work, but again there are some optimizations, for example, in Postgres, anyway, you have vacuumed
that has to read data, so this can be offloaded to the compaction, so the compaction is additional
work, but can also do some work that the database has to do, maybe you can gather statistics
during that, you can do a lot of things that database must do in the background, so the compaction
runs there to have less files, okay, so to summarize, when we compare big difference,
the bitery as a specific place for our value, the other cemetery may have multiple places,
so the bitery is maintained sorted on white, because it is written at a specific place where the
LSM tree is partially maintained sorted, because you insert in the memory table and it can be
sorted in memory easily, but you need compaction and you need the merge source when you read it
at the end, so this is why we say that bitery is faster for reads and LSM trees are faster for
writes, but there are many optimizations, bitery can be efficient on write, if a lot of branches
are in memory, if you have to follow the free of all levels of the bitery and go to this, that's
too much, so usually, bitery needs memory, LSM tree, you may allocate less memory for them,
which we have the space amplification depending on what you write, if you write random values,
it will go to random blocks and then those will be full or split and then alpha full, so on
other edge you have 25% of free space there, but again, you can optimize it first all that
bases that use bitery, have some ways where it can recompact or rebuild the index on 9,
and also on the application, you try to avoid random values like a random UID for a primary
key, if you don't want to go to this space amplification, space amplification is not only about
the space, it means that it will use also more memory to get things in case, and for the
write amplification, that happens when blocks are split, again, there are many optimizations in
white tiger, for example, there are many optimizations where it doesn't update a leaf in place,
it does some kind of copy on write for that, and not having pointers between blocks also
to avoid locks or latches when it reads the structure, and also the same trees have their
own optimizations, as I mentioned, the red amplification with blue filter, minmarks, also you
go by the BDB decide to use only one level of the LSM tree to optimize the red and the
compaction, space amplification for LSM tree comes when, for example, when it has to compact,
you need double space for it, so for one big database you don't want to compact all files,
but sometimes you need to compact all files, because maybe you inserted a very long time ago,
and you deleted recently, so you inserted a tombstone that is in a different file,
but if you do shorting like a uGabaret or TIDB, they showed before storing in the LSM tree,
if you do shorting, you control the size of it, and then the compaction, you can do a full
compaction on a moment of data that is limited, for the write amplification, that is low when you
write to the memory table, but the compaction needs to keep up with that, because you cannot
allocate as many as memory table as u, and if it is not flushed and compacted efficiently behind
it, but again there are a lot of things that can be off-loaded to the compaction and optimize it.
If I compare more specifically, but I think I will go faster on that, the optimizations that
were made on write-dagger B3, so I mentioned a few of them, the log 3 algorithm is quite nice,
it was really built for databases with multiple threads updating data,
and also the usage of it, for example, write-dagger is used in MongoDB, when it generates,
it doesn't store directly in the primary key index,
using the primary key from the application, it generates a sequence that is increasing,
so you don't have this space amplification, so the way you use it is also a possibility where
it is optimized, and what's the being you get by it already mentioned a few of them, but for example,
they support only assess this, because the redamplification, if you add the latency of making
a mechanical disk, then we complicated, but on-modern storage that works, and something that is
really nice for databases on a essentially, you have incremental backups coming from it,
because the files, the assesses files are imitable once they are flushed, so your incremental
backup, your snapshot, is just keeping the files, that's quite nice.
Something also to keep in mind about the storage, so the the mechanical disks used to be slow
for everything random with unwrites, this is why we try to do as much as possible in memory,
because the random access is faster, and to do things more sequential when writing to wall
or at checkpoint, we assess this, the reads are faster, so you can accept a bit more read
amplification, but the writes can still be slow, so it's something that is optimized,
by transforming the random writes to sequential writes, because it writes to memory, and then the
flush is sequential, the compaction is sequential. So I started with this, because I wanted to be sure
that I mentioned it, writes intensive workload, so whether the same tree, the writes is faster,
because you write directly to the main table and the all compaction can keep it behind, you write
on it to the main table, where for Beatriz, you have to write to the cache, maybe in memory,
but you may need to read some blocks, the blocks that you need, the block where the value goes,
so additional work, but not all workloads are write intensive, and the same trees were really made
for big data, where you upset, where you don't have secondary index, for things like
Cassandra, for example, but on a WLTP on SQL databases, as I mentioned at the beginning,
you read a lot, you need to read a lot even when you insert, which means that with the Beatriz,
you already have this read done, so this additional thing that you do when you write,
you need it to read, where in other centuries the reads goes to a completely different path,
and even a different cache, so it is an overhead there, so need to think about it, it's not as easy,
as I do a lot of writes, I will pick a database with the same trees, those are examples of
databases using Beatriz or the same trees, just to show that it's not only the old databases,
that use Beatriz, for example AWS has all kinds of databases, most of them use Beatriz,
and in the SM trees, of course, you see the big data databases, but you see SQL databases,
so finally, so this is my LinkedIn, if you have any question later, the main message is that
yeah, SM trees are faster for writes, but your database is probably doing more reads than writes,
even if you think that your application is writing a lot, SM trees are very complex to tune
there are a lot of parameters to control, the compaction is aggressive or not,
so they can be complex to tune, where Beatriz may look simpler, but be careful with what you do,
be careful with the random keys, for example, and there are different implementations,
I was really surprised by writes, take an implementation, because it has a lot of
optimizations compared to older databases, it was really made up for a time where multiple
trade access the same data, and the most important is to understand that it works and understand
the trade-off, there is not one that is better than another, but the rest is if you use one
without really understanding what happens, be I lead. Okay, thank you.