The B-tree and the Log-Structured Merge-tree (LSM-tree) are the two most widely used data structures for data-intensive applications to organize and store data. However, each of them has its own advantages and disadvantages.
LSM Tree is not a single data structure as a whole but combines multiple data structures that exploit the response times of different storage devices in the storage hierarchy. Being append only, it provides high rates of writes while still providing low cost reads via indexes maintained in RAM. In contrast to B+ tree based storage engine which performs in-place updates, there are no in-place updates in a LSM Tree and this helps in avoiding random I/Os.
Comparing B-Trees and LSM-Trees
Even though B-tree implementations are generally more mature than LSM-tree implementations, LSM-trees are also interesting due to their performance character‐istics. As a rule of thumb, LSM-trees are typically faster for writes, whereas B-trees are thought to be faster for reads. Reads are typically slower on LSM-trees because they have to check several different data structures and SSTables at different stages of compaction.
However, benchmarks are often inconclusive and sensitive to details of the workload. You need to test systems with your particular workload in order to make a valid comparison. In this section we will briefly discuss a few things that are worth considering when measuring the performance of a storage engine.
Advantages of LSM-trees
A B-tree index must write every piece of data at least twice: once to the write-ahead log, and once to the tree page itself (and perhaps again as pages are split). There is also overhead from having to write an entire page at a time, even if only a few bytes in that page changed.
- Some storage engines even overwrite the same page twice in order to avoid ending up with a partially updated page in the event of a power failure.
Log-structured indexes also rewrite data multiple times due to repeated compaction and merging of SSTables. This effect—one write to the database resulting in multiple writes to the disk over the course of the database’s lifetime—is known as write amplification. It is of particular concern on SSDs, which can only overwrite blocks a limited number of times before wearing out.
In write-heavy applications, the performance bottleneck might be the rate at which the database can write to disk. In this case, write amplification has a direct performance cost: the more that a storage engine writes to disk, the fewer writes per second it can handle within the available disk bandwidth.
Moreover, LSM-trees are typically able to sustain higher write throughput than B-trees,
- partly because they sometimes have lower write amplification (although this depends on the storage engine configuration and workload),
- and partly because they sequentially write compact SSTable files rather than having to overwrite several pages in the tree.
This difference is particularly important on magnetic hard drives, where sequential writes are much faster than random writes.
LSM-trees can be compressed better, and thus often produce smaller files on disk than B-trees. B-tree storage engines leave some disk space unused due to fragmentation: when a page is split or when a row cannot fit into an existing page, some space in a page remains unused. Since LSM-trees are not page-oriented and periodically rewrite SSTables to remove fragmentation, they have lower storage overheads, especially when using leveled compaction.
On many SSDs, the firmware internally uses a log-structured algorithm to turn random writes into sequential writes on the underlying storage chips, so the impact of the storage engine’s write pattern is less pronounced. However, lower write amplification and reduced fragmentation are still advantageous on SSDs: representing data more compactly allows more read and write requests within the available I/O bandwidth.
Downsides of LSM-trees
A downside of log-structured storage is that the compaction process can sometimes interfere with the performance of ongoing reads and writes. Even though storage engines try to perform compaction incrementally and without affecting concurrent access, disks have limited resources, so it can easily happen that a request needs to wait while the disk finishes an expensive compaction operation. The impact on throughput and average response time is usually small, but at higher percentiles (see “Describing Performance” on page 13) the response time of queries to log-structured storage engines can sometimes be quite high, and B-trees can be more predictable [28].
Another issue with compaction arises at high write throughput: the disk’s finite write bandwidth needs to be shared between the initial write (logging and flushing a memtable to disk) and the compaction threads running in the background. When writing to an empty database, the full disk bandwidth can be used for the initial write, but the bigger the database gets, the more disk bandwidth is required for compaction.
If write throughput is high and compaction is not configured carefully, it can happen that compaction cannot keep up with the rate of incoming writes. In this case, the number of unmerged segments on disk keeps growing until you run out of disk space, and reads also slow down because they need to check more segment files. Typ‐ically, SSTable-based storage engines do not throttle the rate of incoming writes, even if compaction cannot keep up, so you need explicit monitoring to detect this situation [29, 30].
An advantage of B-trees is that each key exists in exactly one place in the index, whereas a log-structured storage engine may have multiple copies of the same key in different segments. This aspect makes B-trees attractive in databases that want to offer strong transactional semantics: in many relational databases, transaction isolation is implemented using locks on ranges of keys, and in a B-tree index, those locks can be directly attached to the tree [5]. In Chapter 7 we will discuss this point in more detail.
B-trees are very ingrained in the architecture of databases and provide consistently good performance for many workloads, so it’s unlikely that they will go away anytime soon. In new datastores, log-structured indexes are becoming increasingly popular. There is no quick and easy rule for determining which type of storage engine is better for your use case, so it is worth testing empirically.
Metrics
In general, there are three critical metrics to measure the performance of a data structure: write amplification, read amplification, and space amplification. This section aims to describe these metrics.
For hard disk drives (HDDs), the cost of disk seek is enormous, such that the performance of random read/write is worse than that of sequential read/write. This article assumes that flash-based storage is used so we can ignore the cost of disk seeks.
Write Amplification
Write amplification is the ratio of the amount of data written to the storage device versus the amount of data written to the database.
For example, if you are writing 10 MB to the database and you observe 30 MB disk write rate, your write amplification is 3.
Flash-based storage can be written to only a finite number of times, so write amplification will decrease the flash lifetime.
There is another write amplification associated with flash memory and SSDs because flash memory must be erased before it can be rewritten.
Read Amplification
Read amplification is the number of disk reads per query.
For example, if you need to read 5 pages to answer a query, read amplification is 5.
Note that the units of write amplification and read amplification are different. Write amplification measures how much more data is written than the application thought it was writing, whereas read amplification counts the number of disk reads to perform a query.
Read amplification is defined separately for point query and range queries. For range queries the range length matters (the number of rows to be fetched).
Caching is a critical factor for read amplification. For example, with a B-tree in the cold-cache case, a point query requires $O(log_BN)$ disk reads, whereas in the warm-cache case the internal nodes of the B-tree are cached, and so a B-tree requires at most one disk read per query.
Space Amplification
Space amplification is the ratio of the amount of data on the storage device versus the amount of data in the database.
For example, if you put 10MB in the database and this database uses 100MB on the disk, then the space amplification is 10.
Generally speaking, a data structure can optimize for at most two from read, write, and space amplification. This means one data structure is unlikely to be better than another at all three. For example a B-tree has less read amplification than an LSM-tree while an LSM-tree has less write amplification than a B-tree.
Analysis
LSM-tree
An LSM-tree periodically performs compaction to merge several SSTables into one new SSTable which contains only the live data from the input SSTables. Compaction helps the LSM-tree to recycle space and reduce read amplification. There are two kinds of compaction strategy: Size-tiered compaction strategy (STCS) and Level-based compaction strategy (LBCS). The idea behind STCS is to compact small SSTables into medium SSTables when the LSM-tree has enough small SSTables and compact medium SSTables into large SSTables when LSM-tree has enough medium SSTables. The idea of LBCS is to organize data into levels and each level contains one sorted run. Once a level accumulates enough data, some of the data at this level will be compacted to the higher level.
B+ Tree
In the B+ tree, copies of the keys are stored in the internal nodes; the keys and records are stored in leaves; in addition, a leaf node may include a pointer to the next leaf node to increase sequential access performance.
To simplify the analysis, assume that the block size of the tree is B measured in bytes, and keys, pointers, and records are constant size, so that each internal node contains O(B) children and each leaf contains O(B) data records. (The root node is a special case, and can be nearly empty in some situations.) Under all these assumptions, the depth of a B+ tree is $$ O(log_BN/B) $$ where N is the size of the database.
Write Amplification
For the worst-case insertion workloads, every insertion requires writing the leaf block containing the record, so the write amplification is �B.
Read Amplification
The number of disk reads per query is at most $O(log_BN/B)$, which is the depth of the tree.
Level-Based LSM-tree
In the Level-based LSM-tree, data is organized into levels. Each level contains one sorted run. Data starts in level 0, then gets merged into the level 1 run. Eventually the level 1 run is merged into the level 2 run, and so forth. Each level is constrained in its sizes. Growth factor k is specified as the magnification of data size at each level. $$ level_i=level_{i-1}*k $$ We can analyze the Level-based LSM-tree as follows. If the growth factor is k and the smallest level is a single file of size B, then the number of levels is $$ O(log_kN/B) $$ where N is the size of the database. In order to simplify the analysis, we assume that database size is stable and grows slowly over time, so that the size of database will be nearly equal to the size of last level.
Write Amplification
Data must be moved out of each level once, but data from a given level is merged repeatedly with data from the previous level. On average, after being first written into a level, each data item is remerged back into the same level about k/2 times. So the total write amplification $$ O(k*log_kN/B) $$ Read Amplification
To perform a short range query in the cold cache case, we must perform a binary search on each of the levels.
For the highest $level_i$, the data size is O(N), so that it performs O*(*logN/B) disk reads.
For the previous $level_{i-1}$, the data size is O(N/k), so that it performs O(log(N/(k*B)) disk reads.
For $level_{i-2}$, the data size is $O(N/k^2)$, so that it performs $O(log(N/k^2/B))$ disk reads.
…
For $level{i-n}$, the data size is $O(N/K^n)$, so that it performs $O(log(N/K^nB))$ disk reads.
So that the total number of disk reads is $$ R=O(logN/B)+O(log(N/(kB)))+O(log(N/K^2B))+…+O(log(N/k^nB))+1=O((log^2N/B)/logk) $$
Summary
Through comparing various kinds of amplification between B+ tree and Level-based LSM-tree, we can come to a conclusion that Level-based LSM-tree has a better write performance than B+ tree while its read performance is not as good as B+ tree.
Reference
- https://dev.to/creativcoder/what-is-a-lsm-tree-3d75
- Designing Data Intensive Applications