Wednesday, September 19, 2018

Durability debt

I define durability debt to be the amount of work that can be done to persist changes that have been applied to a database. Dirty pages must be written back for a b-tree. Compaction must be done for an LSM. Durability debt has IO and CPU components. The common IO overhead is from writing something back to the database. The common CPU overhead is from computing a checksum and optionally from compressing data.

From an incremental perspective (pending work per modified row) an LSM usually has less IO and more CPU durability debt than a B-Tree. From an absolute perspective the maximum durability debt can be much larger for an LSM than a B-Tree which is one reason why tuning can be more challenging for an LSM than a B-Tree.

In this post by LSM I mean LSM with leveled compaction.

B-Tree

The maximum durability debt for a B-Tree is limited by the size of the buffer pool. If the buffer pool has N pages then there will be at most N dirty pages to write back. If the buffer pool is 100G then there will be at most 100G to write back. The IO is more random or less random depending on whether the B-Tree is update-in-place, copy-on-write random or copy-on-write sequential. I prefer to describe this as small writes (page at a time) or large writes (many pages grouped into a larger block) rather than random or sequential. InnoDB uses small writes and WiredTiger uses larger writes. The distinction between small writes and large writes is more important with disks than with SSD.

There is a small CPU overhead from computing the per-page checksum prior to write back. There can be a larger CPU overhead from compressing the page. Compression isn't popular with InnoDB but is popular with WiredTiger.

There can be an additional IO overhead when torn-write protection is enabled as provided by the InnoDB double write buffer.

LSM

The durability debt for an LSM is the work required to compact all data into the max level (Lmax). A byte in the write buffer causes more debt than a byte in the L1 because more work is needed to move the byte from the write buffer to Lmax than from L1 to Lmax.

The maximum durability debt for an LSM is limited by the size of the storage device. Users can configure RocksDB such that the level 0 (L0) is huge. Assume that the database needs 1T of storage were it compacted into one sorted run and the write-amplification to move data from the L0 to the max level (Lmax) is 30. Then the maximum durability debt is 30 * sizeof(L0). The L0 is usually configured to be <= 1G in which case the durability debt from the L0 is <= 30G. But were the L0 configured to be <= 1T then the debt from it could grow to 30T.

I use the notion of per-level write-amp to explain durability debt in an LSM. Per-level write-amp is defined in the next section. Per-level write-amp is a proxy for all of the work done by compaction, not just the data to be written. When the per-level write-amp is X then for compaction from Ln to Ln+1 for every key-value pair from Ln there are ~X key-value pairs from Ln+1 for which work is done including:
  • Read from Ln+1. If Ln is a small level then the data is likely to be in the LSM block cache or OS page cache. Otherwise it is read from storage. Some reads will be cached, all writes go to storage. So the write rate to storage is > the read rate from storage.
  • The key-value pairs are decompressed if the level is compressed for each block not in the LSM block cache.
  • The key-value pairs from Ln+1 are merged with Ln. Note that this is a merge, not a merge sort because the inputs are ordered. The number of comparisons might be less than you expect because one iterator is ~X times larger than the other and there are optimizations for that.
The output from the merge is then compressed and written back to Ln+1. Some of the work above (reads, decompression) are also done for Ln but most of the work comes from Ln+1 because it is many times larger than Ln. I stated above that an LSM usually has more IO and less CPU durability debt per modified row. The extra CPU overheads come from decompression and the merge. I am not sure whether to count the compression overhead as extra.

Assuming the per-level growth factor is 10 and f is 0.7 (see below) then the per-level write-amp is 7 for L1 and larger levels. If sizeof(L1) == sizeof(L0) then the per-level write-amp is 2 for the L0. And the per-level write-amp is always 1 for the write buffer.

From this we can estimate the pending write-amp for data at any level in the LSM tree.
  1. Key-value pairs in the write buffer have the most pending write-amp. Key-value pairs in the max level (L5 in this case) have none. Key-value pairs in the write buffer are further from the max level. 
  2. Starting with the L2 there is more durability debt from a full Ln+1 than a full Ln -- while there is more pending write-amp for Ln, there is more data in Ln+1.
  3. Were I given the choice of L1, L2, L3 and L4 when first placing a write in the LSM tree then I would choose L4 as that has the least pending write-amp.
  4. Were I to choose to make one level 10% larger then I prefer to do that for a smaller level given the values in the rel size X pend column.

legend:
w-amp per-lvl   : per-level write-amp
w-amp pend      : write-amp to move byte to Lmax from this level
rel size        : size of level relative to write buffer
rel size X pend : write-amp to move all data from that level to Lmax

        w-amp   w-amp   rel     rel size 
level   per-lvl pend    size    X pend
-----   ------- -----   -----   --------
wbuf    1       31          1      31      
L0      2       30          4     120     
L1      7       28          4     112     
L2      7       21         40     840     
L3      7       14        400    5600    
L4      7       7        4000   28000   
L5      0       0       40000       0  

Per-level write-amp in an LSM

The per-level write-amplification is the work required to move data between adjacent levels. The per-level write-amp for the write buffer is 1 because a write buffer flush creates a new SST in L0 without reading/re-writing an SST already in L0.

I assume that any key in Ln is already in Ln+1 so that merging Ln into Ln+1 does not make Ln+1 larger. This isn't true in real life, but this is a model.

The per-level write-amp for Ln is approximately sizeof(Ln+1) / sizeof(Ln). For n=0 this is 2 with a typical RocksDB configuration. For n>0 this is the per-level growth factor and the default is 10 in RocksDB. Assume that the per-level growth factor is equal to X, in reality the per-level write-amp is f*X rather than X where f ~= 0.7. See this excellent paper or examine the compaction IO stats from a production RocksDB instance. Too many excellent conference papers assume it is X rather than f*X in practice.

The per-level write-amp for Lmax is 0 because compaction stops at Lmax.

Tuesday, September 18, 2018

Bloom filter and cuckoo filter

The multi-level cuckoo filter (MLCF) in SlimDB builds on the cuckoo filter (CF) so I read the cuckoo filter paper. The big deal about the cuckoo filter is that it supports delete and a bloom filter does not. As far as I know the MLCF is updated when sorted runs arrive and depart a level -- so delete is required. A bloom filter in an LSM is per sorted run and delete is not required because the filter is created when the sorted run is written and dropped when the sorted run is unlinked.

I learned of the blocked bloom filter from the cuckoo filter paper (see here or here). RocksDB uses this but I didn't know it had a name. The benefit of it is to reduce the number of cache misses per probe. I was curious about the cost and while the math is complicated, the paper estimates a 10% increase on the false positive rate for a bloom filter with 8 bits/key and a 512-bit block which is similar to a typical setup for RocksDB.

Space Efficiency

I am always interested in things that use less space for filters and block indexes with an LSM so I spent time reading the paper. It is a great paper and I hope that more people read it. The cuckoo filter (CF) paper claims better space-efficiency than a bloom filter and the claim is repeated in the SlimDB paper as:
However, by selecting an appropriate fingerprint size f and bucket size b, it can be shown that the cuckoo filter is more space-efficient than the Bloom filter when the target false positive rate is smaller than 3%
The tl;dr for me is that the space savings from a cuckoo filter is significant when the false positive rate (FPR) is sufficiently small. But when the target FPR is 1% then a cuckoo filter uses about the same amount of space as a bloom filter.

The paper has a lot of interesting math that I was able to follow. It provides formulas for the number of bits/key for a bloom filter, cuckoo filter and semisorted cuckoo filter. The semisorted filter uses 1 less bit/key than a regular cuckoo filter. The formulas assuming E is the target false positive rate, b=4, and A is the load factor:
  • bloom filter: ceil(1.44 * log2(1/E))
  • cuckoo filter: ceil(log2(1/E) + log2(2b)) / A == (log2(1/E) + 3) / A
  • semisorted cuckoo filter: ceil(log2(1/E) + 2) / A

The target load factor is 0.95 (A = 0.95) and that comes at a cost in CPU overhead when creating the CF. Assuming A=0.95 then a bloom filter uses 10 bits/key, a cuckoo filter uses 10.53 and a semisorted cuckoo filter uses 9.47. So the cuckoo filter uses either 5% more or 5% less space than a bloom filter when the target FPR is 1% which is a different perspective from the quote I listed above. Perhaps my math is wrong and I am happy for an astute reader to explain that.

When the target FPR rate is 0.1% then a bloom filter uses 15 bits/key, a cuckoo filter uses 13.7 and a semisorted cuckoo filter uses 12.7. The savings from a cuckoo filter are larger here but the common configuration for a bloom filter in an LSM has been to target a 1% FPR. I won't claim that we have proven that FPR=1% is the best rate and recent research on Monkey has shown that we can do better when allocating space to bloom filters.

The first graph shows the number of bits/key as a function of the FPR for a bloom filter (BF) and cuckoo filter (CF). The second graph shows the ratio for bits/key from BF versus bits/key from CF. The results for semisorted CF, which uses 1 less bit/key, are not included.  For the second graph a CF uses less space than a BF when the value is greater than one. The graph covers FPR from 0.00001 to 0.09 which is 0.001% to 9%. R code to generate the graphs is here.


CPU Efficiency

From the paper there is more detail on CPU efficiency in table 3, figure 5 and figure 7. Table 3 has the speed to create a filter, but the filter is much larger (192MB) than a typical per-run filter with an LSM and there will be more memory system stalls in that case. Regardless the blocked bloom filter has the least CPU overhead during construction.

Figure 5 shows the lookup performance as a function of the hit rate. Fortunately performance doesn't vary much with the hit rate. The cuckoo filter is faster than the blocked bloom filter and the block bloom filter is faster than the semisorted cuckoo filter.

Figure 7 shows the insert performance as a function of the cuckoo filter load factor. The CPU overhead per insert grows significantly when the load factor exceeds 80%.

Thursday, September 13, 2018

Review of SlimDB from VLDB 2018

SlimDB is a paper worth reading from VLDB 2018. The highlights from the paper are that it shows:
  1. How to use less memory for filters and indexes with an LSM
  2. How to reduce the CPU penalty for queries with tiered compaction
  3. The benefit of more diversity in LSM tree shapes
Overview

Cache amplification has become more important as database:RAM ratios increase. With SSD it is possible to attach many TB of usable data to a server for OLTP. By usable I mean that the SSD has enough IOPs to access the data. But it isn't possible to grow the amount of RAM per server at that rate. Many of the early RocksDB workloads used database:RAM ratios that were about 10:1 and everything but the max level (Lmax) of the LSM tree was in memory. As the ratio grows that won't be possible unless filters and block indexes use less memory. SlimDB does that via three-level block indexes and multi-level cuckoo-filters.

Tiered compaction uses more CPU and IO for point and range queries because there are more places to check for data when compared to level compaction. The multi-level cuckoo filter in SlimDB reduces the CPU overhead for point queries as there is only one filter to check per level rather than one per sorted run per level.

The SlimDB paper shows the value of hybrid LSM tree shapes, combinations of tiered and leveled, and then how to choose the best combination based on IO costs. Prior to this year, hybrid didn't get much discussion -- the choices were usually tiered or leveled. While RocksDB and LevelDB with the L0 have always been hybrids of tiered (L0) and leveled (L1 to Lmax), we rarely discuss that. But more diversity in LSM tree shape means more complexity in tuning and the SlimDB solution is to make a cost-based decision (cost == IO overhead) subject to a constraint on the amount of memory to use.

This has been a great two years for storage engine efficiency. First we had several papers from Harvard DASLab that have begun to explain cost-based algorithm design and engine configuration and SlimDB continues in that tradition. I have much more reading to do starting with The Periodic Table of Data Structures.

Below I review the paper. Included with that is some criticism. Papers can be great without being perfect. This paper is a major contribution and worth reading.

Semi-sorted

The paper starts by explaining the principle of semi-sorted data. When the primary key can be split into two parts -- prefix and suffix -- there are some workloads that don't need data ordered over the entire primary key (prefix + suffix). Semi-sorted supports queries that fetch all data that matches the prefix of the PK while still enforcing uniqueness for the entire PK. The PK can be on (a,b,c,d) and (a,b) is prefix and queries are like "a=X and b=Y" without predicates on (c,d) that require index ordering. SlimDB takes advantage of this to use less space for the block index.

There are many use cases for this, but the paper cites Linkbench which isn't correct. See the Linkbench and Tao papers for queries that do an exact match on the prefix but only want the top-N rows in the result. So ordering on the suffix is required to satisfy query response time goals when the total number of rows that match the prefix is much larger than N. I assume this issue with top-N is important for other social graph workloads because some graph nodes are popular. Alas, things have changed with the social graph workload since those papers were published and I hope the changes are explained one day.

Note that MyRocks can use a prefix bloom filter to support some range queries with composite indexes. Assume the index is on (a,b,c) and the query has a=X and b=Y order by c limit 10. A prefix bloom on (a,b) can be used for such a query.

Stepped Merge

The paper implements tiered compaction but calls it stepped merge. I didn't know about the stepped merge paper prior to reading the SlimDB paper. I assume that people who chose the name tiered might also have missed that paper.

LSM compaction algorithms haven't been formally defined. I tried to advance the definitions in a previous post. One of the open issues for tiered is whether it requires only one sorted run at the max level or allows for N runs at the max level. With N runs at the max level the space-amplification is at least N which is too much for many workloads. With 1 run at the max level compaction into the max level is always leveled rather than tiered -- the max level is read/rewritten and the per-level write-amplification from that is larger than 1 (while the per-level write-amp from tiered == 1). With N runs at the max level many of the compaction steps into the max level can be tiered, but some will be leveled -- when the max level is full (has N runs) then something must be done to reduce the number of runs.

3-level block index

Read the paper. It is complex and a summary by me here won't add value. It uses an Entropy Coded Trie (ECT) that builds on ideas from SILT -- another great paper from CMU.

ECT uses ~2 bits/key versus at least 8 bits/key for LevelDB for the workloads they considered. This is a great result. ECT also uses 5X to 7X more CPU per lookup than LevelDB which means you might limit the use of it to the largest levels of the LSM tree -- because those use the most memory and the place where we are willing to spend CPU to save memory.

Multi-level cuckoo filter

SlimDB can use a cuckoo filter for leveled levels of the LSM tree and a multi-level cuckoo filter for tiered levels. Note that leveled levels have one sorted run and tiered levels have N sorted runs. SlimDB and the Stepped Merge paper use the term sub-levels, but I prefer N sorted runs.

The cuckoo filter is used in place of a bloom filter to save space given target false positive rates of less than 3%. The paper has examples where the cuckoo filter uses 13 bits/key (see Table 1) and a bloom filter with 10 bits/key (RocksDB default) has a false positive rate of much less than 3%. It is obvious that I need to read another interesting CMU paper cited by SlimDB -- Cuckoo Filter Practically Better than Bloom.

The multi-level cuckoo filter (MLCF) extends the cuckoo filter by using a few bits/entry to name the sub-level (sorted run) in the level that might contain the search key. With tiered and a bloom filter per sub-level (sorted run) a point query must search a bloom filter per sorted run. With the MLCF there is only one search per level (if I read the paper correctly).

The MLCF might go a long way to reduce the point-query CPU overhead when using many sub-levels which is a big deal. While a filter can't be used for general range queries, SlimDB doesn't support general range queries. Assuming the PK is on (a,b,c,d) and the prefix is (a,b) then SlimDB supports range queries like fetch all rows where a=X and b=Y. It wasn't clear to me whether the MLCF could be used in that case. But many sub-levels can create more work for range queries as iterators must be positioned in each sub-level in the worst case and that is more work.

This statement from the end of the paper is tricky. SlimDB allows for an LSM tree to use leveled compaction on all levels, tiered on all levels or a hybrid. When all levels are leveled, then performance should be similar to RocksDB with leveled, when all or some levels are tiered then write-amplification will be reduced at the cost of read performance and the paper shows that range queries are slower when some levels are tiered. Lunch isn't free as the RUM Conjecture asserts.
In contrast, with the support of dynamic use of a stepped merge algorithm and optimized in-memory indexes, SlimDB minimizes write amplification without sacrificing read performance.
The memory overhead for MLCF is ~2 bits. I am not sure this was explained by the paper but that might be to name the sub-level, in which case there can be at most 4 sub-levels per level and the cost would be larger with more sub-levels.

The paper didn't explain how the MLCF is maintained. With a bloom filter per sorted run the bloom filter is created when SST files are created during compaction and memtable flush. This is an offline or batch computation. But the MLCF covers all the sub-levels (sorted runs) in a level. And the sub-levels in a level arrive and depart one at a time, not at the same time. They  arrive as output from compaction and depart when they were compaction input. The arrival or departure of a new sub-level requires incremental changes to the MLCF. 

LSM tree shapes

For too long there has not been much diversity in LSM tree shapes. The usual choice was all tiered or all leveled. RocksDB leveled is really a hybrid -- tiered for L0, leveled for L1 to Lmax. But the SlimDB paper makes the case for more diversity. It explains that some levels (smaller ones) can be tiered while the larger levels can be leveled. And the use of multi-level cuckoo filters, three-level indexes and cuckoo filters is also a decision to make per-level.

Even more interesting is the use of a cost-model to choose the best configuration subject to a constraint -- the memory budget. They enumerate a large number of LSM tree configurations, generate estimated IO-costs per operation (write-amp, IO per point query that returns a row, IO per point query that doesn't return a row, memory overhead) and then the total IO cost is computed for for a workload -- where a workload specifies the frequency of each operation (for example - 30% writes, 40% point hits, 30% point misses).

The Dostoevsky paper also makes the case for more diversity and uses rigorous models to show how to choose the best LSM tree shape.

I think this work is a big step in the right direction. Although cost models must be expanded to include CPU overheads and constraints expanded to include the maximum write and space amplification that can be tolerated.

I disagree with a statement from the related work section. We can already navigate some of the read, write and space amplification space but I hope there is more flexibility in the future. RocksDB tuning is complex in part to support this via changing the number of levels (or growth factor per level), enabling/disabling the bloom filter, using different compression (or none) on different levels, changing the max space amplification allowed, changing the max number of sorted runs in the L0 or max number of write buffers, changing the L0:L1 size ratio, changing the number of bloom filter bits/key. Of course I want more flexibility in the future while also making RocksDB easier to tune.

Existing LSM-tree based key-value stores do not allow trading among read cost, write cost and main memory footprint. 

Performance Results


Figuring out why X was faster than Y in academic papers is not my favorite task. I realize that space constraints are a common reason for the lack of details but I am wary of results that have not been explained and I know that mistakes can be made (note: don't use serializable with InnoDB). I make many mistakes myself. I am willing to provide advice for MyRocks, MySQL and RocksDB. AFAIK most authors who hack on RocksDB or compare with it for research are not reaching out to us. We are happy to help in private.

SlimDB was faster than RocksDB on their evaluation except for range queries. There were few details about the configurations used, so I will guess. First I assume that SlimDB used stepped merge with MLCF for most levels. I am not sure why point queries were faster with SlimDB than RocksDB. Maybe RocksDB wasn't configured to use bloom filters. Writes were about 4X faster with SlimDB because stepped merge (tiered) compaction was used, write-amplification was 4X less and when IO is the bottleneck then an approach that has less write-amp will go faster.



Wednesday, September 5, 2018

5 things to set when configuring RocksDB and MyRock

The 5 options to set for RocksDB and MyRocks are:
  1. block cache size
  2. number of background threads
  3. compaction priority
  4. dynamic leveled compaction
  5. bloom filters
I have always wanted to do a "10 things" posts but prefer to keep this list small. It is unlikely that RocksDB can provide a great default for the block cache size and number of background threads because they depend on the amount of RAM and number of CPU cores in a server. But I hope RocksDB or MyRocks are changed to get better defaults for the other three which would shrink this list from 5 to 2.

Options

My advice on setting the size of the RocksDB block cache has not changed assuming it is configured to use buffered IO (the default). With MyRocks this option is rocksdb_block_cache_size and with RocksDB you will write a few lines of code to setup the LRU.

The number of background threads for flushing memtables and doing compaction is set by the option rocksdb_max_background_jobs in MyRocks and max_background_jobs in RocksDB. There used to be two options for this. While RocksDB can use async read-ahead and write-behind during compaction, it still uses synchronous reads and a potentially slow fsync/fdatasync call. Using more than 1 background job helps to overlap CPU and IO. A common configuration for me is number-of-CPU-cores / 4. With too few threads there will be more stalls from throttling. With too many threads there the threads handling user queries might suffer.

There are several strategies for choosing the next data to compact with leveled compaction in RocksDB. The strategy is selected via the compaction_pri option in RocksDB. This is harder to set for MyRocks -- see compaction_pri in rocksdb_default_cf_options. The default value is kByCompensatedSize but the better choice is kMinOverlappingRatio. With MyRocks the default is 0 and the better value is 3 (3 == kMinOverlappingRatio). I first wrote about compaction_pri prior to the arrival of kMinOverlappingRatio. Throughput is better and write amplification is reduced with kMinOverlappingRatio. An awesome paper by Hyeontaek Lim et al explains this.

Leveled compaction in RocksDB limits the amount of data per level of the LSM tree. A great description of this is here. There is a target size per level and this is enforced top down (smaller to larger levels) or bottom up (larger to smaller levels). With the bottom up approach the largest level has ~10X (or whatever the fanout is set to) more data than the next to last level. With the top down approach the largest level frequently has less data than the next to last level. I strongly prefer the bottom up approach to reduce space amplification. This is enabled via the level_compaction_dynamic_level_bytes option in RocksDB. It is harder to set for MyRocks -- see rocksdb_default_cf_options.

Bloom filters are disabled by default for MyRocks and RocksDB. I prefer to use a bloom filer on all but the largest level. This is set via rocksdb_default_cf_options with MyRocks. The reason for not using it with the max level is to consume less memory (reduce cache amplification). The bloom filter is skipped for the largest level in MyRocks via the optimize_filter_for_hits option. The example at the end of this post has more information on enabling bloom filters. All of this is set via rocksdb_default_cf_options.

Examples

A previous post recently explained how to set rocksdb_default_cf_options for compression with MyRocks. Below I share an example my.cnf for MyRocks to set the 5 options I listed above. I set transaction isolation because read committed is a better choice for MyRocks today. Repatable read will be a great choice after gap locks are added to match InnoDB semantics. In rocksdb_default_cf_options block_based_table_factory is used to enable the bloom filter, level_compaction_dynamic_level_bytes enables bottom up management of level sizes, optimize_filters_for_hits disables the bloom filter for the largest level of the LSM tree and compaction_pri sets the compaction priority.

transaction-isolation=READ-COMMITTED
default-storage-engine=rocksdb
rocksdb

rocksdb_default_cf_options=block_based_table_factory={filter_policy=bloomfilter:10:false};level_compaction_dynamic_level_bytes=true;optimize_filters_for_hits=true;compaction_pri=kMinOverlappingRatio
rocksdb_block_cache_size=2g
rocksdb_max_background_jobs=4