A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing

I'm no expert, but it seems like you need to guess at some key ranges and start the BTree at some minimum size even if most of the leaves start out empty. Either that, or don't write anything until the tree grows a bit and rely on a writeahead log for durability.

Hotspots could still show up further down, though, if writes aren't fairly random.

Just scanning the beginning, parts of this are pretty misleading.

For example:

"... if a database row contains 100 bytes, and a B tree such as InnoDB employs 16KiB pages [11], then the B tree may perform 16KiB of I/O to write a single 100-byte row, for a write amplification of 160, compared to a write amplification of 30 to 70 for the other data structures."

Reading this gives the impression that the only way pages are updated is by writing the page in whole. Storage engines commonly use a slotted page layout to avoid this. That is, variable length records are stored contiguously from the start of the page, and are indexed by an array of fixed sized offset entries that grows up from the end of the page. Inserting a 100 byte row will append it to the end of data area, then prepend a new offset to the slot array. On spinning disks this is typically two 512 byte writes (assuming page size is decently larger than block size, as is common). On SSD's it's more complicated due to the FTL, and state of the art systems tend to use a log structured approach. See the Bw-tree paper from Microsoft Research for example.

IMO they're being quite disingenuous in that note. InnoDB is the default storage engine in MySQL, and there are very few production SQL databases with a tiny 100 bytes per row. A typical DB row in common apps is a couple KB at least. As a further example, MySQL's NDB Cluster engine has a maximum row size of 8KB, and this is frequently a problem for apps that want to migrate to it.

If you start a discussion of write amplification with such an unrealistic record size, that pretty much moots the rest of the discussion.

For a real-world examination of write amplification, at multiple record sizes: http://symas.com/mdb/ondisk/

"Academic math" means nothing when you get to real-world software. Tokutek FT code is a pig, by every measure.

Thanks

In a DB with LSM storage you are free to do whatever you need to do.

For example, you can compact size-tiered levels when their size ratio exceeds some threshold. This approach will make situation presented in paper impossible.

In short, levels 1..N should be compacted into one when sum_{i=1..N-1}level_size(i)>=C*level_size(N).

The multiplier C is important. Compactions will be rare and writes will be faster if C is bigger than 1. The read performance will be worse - we have to read more levels. To make compactions more often, we make C smaller. This way we prioritize read speed.

And the most important thing here that we can compact levels even for read transactions. If we have many read transactions, it is necessary to make then faster.

This very important point of LSM design is not mentioned in any literature I read.

Fractal trees can be seen as basically LSM trees with fixed coefficient C=1. And with embedded index, as smaller levels provide indexing for bigger levels.

So they force database designer into some corner. Which is different from corner of B+trees, but corner nevertheless. LSM trees are more flexible in that regard, in my opinion.