Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging
Niv Dayan, Stratos Idreos Harvard University
ABSTRACT
We show that all mainstream LSM-tree based key-value stores in the literature and in industry suboptimally trade between the I/O cost of updates on one hand and the I/O cost of lookups and storage space on the other. The reason is that they perform equally expensive merge operations across all levels of LSM-tree to bound the number of runs that a lookup has to probe and to remove obsolete entries to reclaim storage space. With state-of-the-art designs, however, merge operations from all levels of LSM-tree but the largest (i.e., most merge operations) reduce point lookup cost, long range lookup cost, and storage space by a negligible amount while significantly adding to the amortized cost of updates. To address this problem, we introduce Lazy Leveling, a new design that removes merge operations from all levels of LSM-tree but the largest. Lazy Leveling improves the worst-case complexity of update cost while maintaining the same bounds on point lookup cost, long range lookup cost, and storage space. We further introduce Fluid LSM-tree, a generalization of the entire LSM-tree design space that can be parameterized to assume any existing design. Relative to Lazy Leveling, Fluid LSM-tree can optimize more for updates by merging less at the largest level, or it can optimize more for short range lookups by merging more at all other levels. We put everything together to design Dostoevsky, a key-value store that adaptively removes superfluous merging by navigating the Fluid LSM-tree design space based on the application workload and hardware. We implemented Dostoevsky on top of RocksDB, and we show that it strictly dominates state-of-the-art designs in terms of performance and storage space.
ACM Reference Format: Niv Dayan, Stratos Idreos. 2018. Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging . In Proceedings of 2018 International Conference on Management of Data (SIGMOD’18). ACM, New York, NY, USA, 16 pages. https://doi.org/10.1145/3183713.3196927
1 INTRODUCTION
Key-Value Stores and LSM-Trees. A key-value store is a database that efficiently maps from search keys to their corresponding data values. Key-value stores are used everywhere today from graph processing in social media [8, 17] to event log processing in cyber security [18] to online transaction processing [27]. To persist key-value entries in storage, most key-value stores today use LSM-tree [41]. LSM-tree buffers inserted/updated entries in main memory and flushes the buffer as a sorted run to secondary storage every time that it fills up. LSM-tree later sort-merges these runs to bound the number of runs that a lookup has to probe and to remove obsolete entries, i.e., for which there exists a more recent entry with the same key. LSM-tree organizes runs into levels of exponentially increasing capacities whereby larger levels contain older runs. As entries are updated out-of-place, a point lookup finds the most recent version of an entry by probing the levels from smallest to largest and terminating when it finds the target key. A range lookup, on the other hand, has to access the relevant key range from across all runs at all levels and to eliminate obsolete entries from the result set. To speed up lookups on individual runs, modern designs maintain two additional structures in main memory. First, for every run there is a set of fence pointers that contain the first key of every block of the run; this allows lookups to access a particular key within a run with just one I/O. Second, for every run there exists a Bloom filter; this allows point lookups to skip runs that do not contain the target key. This overall design is adopted in a large number of modern key-value stores including LevelDB [32] and BigTable [19] at Google, RocksDB [29] at Facebook, Cassandra [34], HBase [7] and Accumulo [5] at Apache, Voldemort [38] at LinkedIn, Dynamo [26] at Amazon, WiredTiger [52] at MongoDB, and bLSM [48] and cLSM [31] at Yahoo. Relational databases today such as MySQL (using MyRocks [28]) and SQLite4 support this design too as a storage engine by mapping primary keys to rows as values.
The Problem. The frequency of merge operations in LSM-tree controls an intrinsic trade-off between the I/O cost of updates on one hand and the I/O cost of lookups and storage space-amplification (i.e., caused by the presence of obsolete entries) on the other. The problem is that existing designs trade suboptimally among these metrics. Figure 1 conceptually depicts this by plotting point lookup cost and space-amplification on the y-axis against update cost on the x-axis (while these y-axis metrics have different units, their trade-off curves with respect to the x-axis have the same shape). The two points at the edges of the curves are a log and a sorted array. LSM-tree degenerates into these edge points when it does not merge at all or when it merges as much as possible, respectively. We place mainstream systems along the top curve between these edge points based on their default merge frequencies, and we draw a superior trade-off curve for Monkey [22], which represents the current state of the art. We show that there exists an even superior trade-off curve to Monkey. Existing designs forgo a significant amount of performance and/or storage space for not being designed along this bottom curve.
The Problem’s Source. By analyzing the design space of state-of-the-art LSM-trees, we pinpoint the problem to the fact that the worst-case update cost, point lookup cost, range lookup cost, and space-amplification derive differently from across different levels.
• Updates. The I/O cost of an update is paid later through the merge operations that the updated entry participates in. While merge operations at larger levels entail exponentially more work, they take place exponentially less frequently. Therefore, updates derive their I/O cost equally from merge operations across all levels.
• Point lookups. While mainstream designs along the top curve in Figure 1 set the same false positive rate to Bloom filters across all levels of LSM-tree, Monkey, the current state of the art, sets exponentially lower false positive rates to Bloom filters at smaller levels [22]. This is shown to minimize the sum of false positive rates across all filters and to thereby minimize I/O for point lookups. At the same time, this means that access to smaller levels is exponentially less probable. Therefore, most point lookup I/Os target the largest level.
• Long range lookups1. As levels in LSM-tree have exponentially increasing capacities, the largest level contains most of the data, and so it tends to contain most of the entries within a given key-range. Therefore, most I/Os issued by long range lookups target the largest level.
• Short range lookups. Range lookups with extremely small key ranges only access approximately one block within each run regardless of the run’s size. As the maximum number of runs per level is fixed in state-of-the-art designs, short range lookups derive their I/O cost equally from across all levels.
• Space-Amplification. The worst-case space-amplification derives mostly from the presence of obsolete entries at the largest level.
Since the worst-case point lookup cost, long range lookup cost and space-amplification derive mostly from the largest level, merge operations at all levels of LSM-tree but the largest (i.e., most merge operations) hardly improve on these metrics while significantly adding to the amortized cost of updates. This leads to suboptimal trade-offs. We solve this problem from the ground up in three steps.
Solution 1: Lazy Leveling to Remove Superfluous Merging. We expand the LSM-tree design space with Lazy Leveling, a new design that removes merging from all but the largest level of LSM-tree. Lazy Leveling improves the worst-case cost complexity of updates while maintaining the same bounds on point lookup cost, long range lookup cost, and space-amplification and while providing a competitive bound on short range lookup cost. We show that the improved update cost can be traded to reduce point lookup cost and space-amplification. This generates the bottom curve in Figure 1, which offers richer space-time trade-offs that have been impossible to achieve with state-of-the-art designs until now.
Solution 2: Fluid LSM-Tree for Design Space Fluidity. We introduce Fluid LSM-tree as a generalization of LSM-tree that enables transitioning fluidly across the whole LSM-tree design space. Fluid LSM-tree does this by controlling the frequency of merge operations separately for the largest level and for all other levels. Relative to Lazy Leveling, Fluid LSM-tree can optimize more for updates by merging less at the largest level, or it can optimize more for short range lookups by merging more at all other levels.
Solution 3: Dostoevsky to Navigate the Design Space. We put everything together in Dostoevsky: Space-Time Optimized Evolvable Scalable Key-Value Store. Dostoevsky analytically finds the tuning of Fluid LSM-tree that maximizes throughput for a particular application workload and hardware subject to a user constraint on space-amplification. It does this by pruning the search space to quickly find the best tuning and physically adapting to it during runtime. Since Dostoevsky spans all existing designs and is able to navigate to the best one for a given application, it strictly dominates existing key-value stores in terms of performance and space-amplification. We depict Dostoevsky in Figure 1 as a black star that can navigate the entire design space.
Contributions. Our contributions are summarized below.
• We show that state-of-the-art LSM-trees perform equally expensive merge operations across all levels of LSM-tree, yet merge operations at all but the largest level (i.e., most merge operations) improve point lookup cost, long range lookup cost, and space-amplification by a negligible amount while adding significantly to the amortized cost of updates.
• We introduce Lazy Leveling to remove merge operations at all but the largest level. This improves the cost complexity of updates while maintaining the same bounds on point lookups, long range lookups, and space-amplification and while providing a competitive bound on short range lookups.
• We introduce Fluid LSM-tree, a generalization of LSM-tree that enables transition across the entire LSM-tree design space.
• We introduce Dostoevsky, a key-value store that dynamically adapts across the Fluid LSM-tree design space to the design that maximizes the worst-case throughput based on the application workload and the hardware subject to a constraint on space-amplification.
• We implemented Dostoevsky on RocksDB and show that it dominates existing designs for any application scenario.
1In Section 3, we distinguish formally between short and long range lookups.
2 BACKGROUND
LSM-Tree Structure. LSM-tree optimizes for write-heavy workloads. This is an important performance goal for systems today because the proportion of writes is continuously increasing (e.g., in 2012 Yahoo! reported that the proportion of writes targeting their web-service was 50% and projected to continue accelerating [48]). To optimize for writes, LSM-tree initially buffers all updates, insertions, and deletes (henceforth referred to as updates unless otherwise mentioned) in main memory, as shown in Figure 2. When the buffer fills up, LSM-tree flushes the buffer to secondary storage as a sorted run. LSM-tree sort-merges runs in order to (1) bound the number of runs that a lookup has to access in secondary storage, and to (2) remove obsolete entries to reclaim space. It organizes runs into L conceptual levels of exponentially increasing sizes. Level 0 is the buffer in main memory, and runs belonging to all other levels are in secondary storage.
The balance between the I/O cost of merging and the I/O cost of lookups and space-amplification can be tuned using two knobs. The first knob is the size ratio T between the capacities of adjacent levels; T controls the number of levels of LSM-tree and thus the overall number of times that an entry gets merged across levels. The second knob is the merge policy, which controls the number of times an entry gets merged within a level. All designs today use either one of two merge policies: tiering or leveling (e.g., Cassandra and RocksDB use tiering and leveling by default, respectively [6, 29]). With tiering, we merge runs within a level only when the level reaches capacity [33]. With leveling, we merge runs within a level whenever a new run comes in [41]. We compare these policies in Figure 2 (with a size ratio of 4 and a buffer size of one entry).
In both cases, the merge is triggered by the buffer flushing and causing Level 1 to reach capacity. With tiering, all runs at Level 1 get merged into a new run that gets placed at Level 2. With leveling, the merge also includes the preexisting run at Level 2. We formally study this design space in the next section. We discuss further details of merge mechanics in Appendix D and other log-structured designs in Appendix E.
Number of Levels. The buffer at Level 0 has a capacity of B · P entries, where B is the number of entries that fit into a storage block, and P is the size of the buffer in terms of storage blocks. In general, Level i has a capacity of B · P · T^i entries, and the capacity at the largest level can be approximated as having N · (T-1)/T entries. To derive the number of levels, we divide the capacity at the largest level by the capacity of the buffer and take log base T of the quotient, as shown in Equation 1.
L = ⌈log_T( (N / (B·P)) · ((T-1)/T) )⌉
We restrict the size ratio to the domain of 2 ≤ T ≤ Tlim, where Tlim is defined as N/(B·P). As the size ratio increases and approaches Tlim, the number of levels decreases and approaches 1. Increasing T beyond Tlim has no structural impact. Furthermore, restricting T to be 2 or greater ensures that the resulting run from a merge operation at level i is never large enough to move beyond level i + 1. In other words, this ensures that runs do not skip levels. Thus, the highest possible number of levels Lmax is ⌈log2(N/(B·P))⌉ (i.e., when the size ratio is set to 2).
Finding Entries. Since entries are updated out-of-place, multiple versions of an entry with the same key may exist across multiple levels (and even across runs within a level with tiering). To ensure that a lookup is always able to find the most recent version of an entry, LSM-tree takes the following measures. (1) When an entry is inserted into the buffer and the buffer already contains an entry with the same key, the newer entry replaces the older one. (2) When two runs that contain an entry with the same key are merged, only the entry from the newer run is kept because it is more recent. (3) To be able to infer the order at which different entries with the same key across different runs were inserted, a run can only be merged with the next older or the next younger run. Overall, these rules ensure that if there are two runs that contain different versions of the same entry, the younger run contains the newer version.
Point Lookups. A point lookup finds the most recent version of an entry by probing the levels from smallest to largest and terminating when it finds the target key.
Range Lookups. A range lookup has to find the most recent versions of all entries within the target key range. It does this by sort-merging the relevant key range across all runs at all levels. While sort-merging, it identifies entries with the same key across different runs and discards older versions.
Deletes. Deletes are supported by adding a one-bit flag to every entry. If a lookup finds that the most recent version of an entry has this flag on, it does not return a value to the application. When a deleted entry is merged with the oldest run, it is discarded as it has replaced all entries with the same key that were inserted prior to it.
Fragmented Merging. To smooth out performance slumps due to long merge operations at larger levels, mainstream designs partition runs into files (e.g., 2 to 64 MB [29, 32]) called Sorted String Tables (SSTables), and they merge one SSTable at a time with SSTables with an overlapping key range at the next older run. This technique does not affect the worst-case I/O overhead of merging but only how this overhead gets scheduled across time. For readability throughout the paper, we discuss merge operations as having the granularity of runs, though they can also have the granularity of SSTables.
Space-Amplification. The factor by which the presence of obsolete entries amplify storage space is known as space-amplification. Space-amplification has traditionally not been a major concern for data structure design due to the affordability of disks. The advent of SSDs, however, makes space-amplification an important cost concern (e.g., Facebook has recently switched from B-trees to leveled LSM-trees due to their superior space-amplification properties [27]). We include space-amplification as a cost metric to give a complete picture of the designs that we introduce and evaluate.
Fence Pointers. All major LSM-tree based key-value stores index the first key of every block of every run in main memory. We call these fence pointers (see Figure 2). Formally, the fence pointers take up O(N /B) space in main memory, and they enable a lookup to find the relevant key-range at every run with one I/O.
Bloom Filters. To speed up point lookups, which are common in practice [16, 48], each run has a Bloom filter [14] in main memory, as shown in Figure 2. A Bloom filter is a space-efficient probabilistic data structure used to answer set membership queries. It cannot return a false negative, though it returns a false positive with a tunable false positive rate (FPR). The FPR depends on the ratio between the number of bits allocated to the filter and the number of entries in the set according to the following expression [50]:
FPR = e^(-(bits/entries)·ln(2))
If the Bloom filter returns a negative, the lookup skips the run thereby saving one I/O. Otherwise, we have a false positive, meaning the lookup wastes one I/O by accessing the run, not finding a matching entry, and having to continue searching for the target key in the next run.
A Bloom filter has a useful property that if it is partitioned into smaller equally-sized Bloom filters with an equal division of entries among them, the FPR of each one of the new partitioned Bloom filters is asymptotically the same as the FPR of the original filter (though slightly higher in practice) [50]. For ease of discussion, we refer to Bloom filters as being non-partitioned, though they can also be partitioned (e.g., per every block of every run) as some designs in industry to enable greater flexibility for space management (e.g., Bloom filters for blocks that are not frequently read by point lookups can be offloaded to storage to save memory) [32].
Applicability Beyond Key-Value Stores. In accordance with designs in industry, our discussion assumes that a key is stored adjacently to its value within a run [29, 32]. For readability, all figures in this paper depict entries as keys, but they represent key-value pairs. Our work also applies to applications where there are no values (i.e., the LSM-tree is used to answer set-membership queries on keys), where the values are pointers to data objects stored outside of LSM-tree [39], or where LSM-tree is used as a building block for solving a more complex algorithmic problem (e.g., graph analytics [17], flash translation layer design [23], etc.). We restrict the scope of analysis to the basic operations and size of LSM-tree so that it can easily be applied to each of these other cases.
3 DESIGN SPACE AND PROBLEM ANALYSIS
Analyzing Updates. The I/O cost of updating an entry is paid through the subsequent merge operations that the updated entry participates in. Our analysis assumes a worst-case workload whereby all updates target entries at the largest level. This means that an obsolete entry does not get removed until its corresponding updated entry has reached the largest level. As a result, every entry gets merged across all levels (i.e., rather than getting discarded at some smaller level by a more recent entry and thereby reducing overhead for later merge operations).
With tiering, an entry gets merged O(1) time per level across O(L) levels for a total of O(L) merge operations. With leveling, the jth run that arrives at Level i triggers a merge operation involving the existing run at Level i, which is the merged product of the previous T − j runs that arrived since the last time Level i was empty. Overall, an entry gets merged on average T/2, or O(T), times per level before that level reaches capacity, and across O(L) levels for a total of O(T · L) merge operations. As with tiering, we divide this by the block size B to get the amortized I/O cost for one update: O(L·T /B) I/O.
We now take a closer look at how update cost derives from across different levels. With tiering, Level i fills up every B · P · T^i application updates, and the resulting merge operation copies B · P · T^i entries. With leveling, a merge operation takes place at Level i every B · P · T^{i-1} updates (i.e., every time that a new run comes in), and it copies on average B·P·T^2/2 entries. By dividing the number of copied entries by the frequency of a merge operation at Level i for either leveling or tiering, we observe that in the long run the amount of work done by merge operations at every level is the same, as shown with the cost breakdown in Figure 3 (A). The intuition is that while merge operations at larger levels do exponentially more work, they are also exponentially less frequent.
Analyzing Point Lookups. To analyze the worst-case point lookup cost, we consider the cost of zero-result point lookups, which is highest when every Bloom filter returns a false positive. In this case, a point lookup issues one I/O to every run, amounting to O(L) wasted I/Os with leveling and O(T · L) wasted I/Os with tiering. In practice, however, the Bloom filters eliminate most I/Os to runs that do not contain the target key; key-value stores in industry use 10 bits per entry for every Bloom filters leading to a false positive rate (FPR) of ≈ 1% for each filter [29, 32, 34]. For this reason, we focus on the expected worst-case point lookup cost, which estimates the number of I/Os issued by point lookups as a long-run average with respect to the Bloom filters’ FPRs. We estimate this cost as the sum of FPRs across all the Bloom filters. The reason is that the I/O cost of probing an individual run is an independent random variable with an expected value equal to the corresponding Bloom filter’s FPR, and the expected sum of multiple independent random variables is equal to the sum of their individual expected values [44].
In key-value stores in industry, the number of bits per entry is typically set to 10, leading to an FPR of ≈ 1% for each filter. The product of the FPR at the largest level pL and the number of runs in the system gives the expected worst-case point lookup cost: O(e^(-M/N) · L) I/Os with leveling and O(e^(-M/N) · L · T) I/Os with tiering.
The most recent paper on this issue named Monkey [22] shows that setting the same number of bits per entry for filters across all levels does not minimize the expected number of wasted I/Os. Instead, Monkey reallocates ≈ 1 bit per entry from the filter(s) at the largest level, and it uses these bits to set the number of bits per entry across smaller levels as an increasing arithmetic progression: Level i gets a + b ·(L − i) bits per entry, where a and b are small constants. This causes a small, asymptotically constant increase to the FPR at the largest level and an exponential decrease to the FPRs across smaller levels, as they contain exponentially less entries. Since the FPRs are exponentially decreasing for smaller levels, the sum of FPRs converges to a multiplicative constant that is independent of the number of levels. As a result, Monkey shaves a factor of L from the complexity of point lookups leading to O(e^(-M/N)) I/Os with leveling and O(e^(-M/N) · T) I/Os with tiering, as we illustrate in Figure 3 (B). It is always beneficial to use Monkey, for zero and non-zero result point lookups alike and with any kind of skew [22].
Overall, we observe that point lookup cost using Monkey derives mostly from access to the largest level, which is a significant optimization.
Analyzing Space-Amplification. We define space-amplification as the factor amp by which the overall number of entries N is greater than the number of unique entries unq: amp = N/unq - 1.
To analyze the worst-case space-amplification, we observe that levels 1 to L − 1 of LSM-tree comprise a fraction of 1/T of its capacity, whereas level L comprises the remaining fraction of (T-1)/T of its capacity. With leveling, the worst-case space-amplification occurs when entries at Levels 1 to L − 1 are all updates to different entries at Level L, thereby rendering at most a fraction of 1/T entries at level L obsolete. Space-amplification is therefore O(1/T), as shown in Figure 4 (A). For example, in production environments using SSDs at Facebook, RocksDB uses leveling and a size ratio of 10 to bound space-amplification to ≈ 10% [27]. With tiering, the worst-case occurs when entries at Levels 1 to L − 1 are all updates to different entries at Level L, and where every run at Level L contains the same set of entries. In this case, Level L entirely consists of obsolete entries, and so space-amplification is O(T) as level L is larger by a factor of T-1 than all other levels combined. Overall, space-amplification with both leveling and tiering in the worst case derives mostly from the presence of obsolete entries at the largest level.
Analyzing Range Lookups. We denote the selectivity of a range lookup s as the number of unique entries across all runs that fall within the target key range. A range lookup scans and sort-merges the target key range across all runs, and it eliminates obsolete entries from the result set. For analysis, we consider a range lookup to be long if the number of blocks accessed is at least twice as large as the maximum possible number of levels: s/B > 2 · Lmax. Under uniformly randomly distributed updates, this condition implies with a high probability that most entries within a target key range are at the largest level. For all practical purposes, we generalize the treatment of long and short range lookups in Section 4.2.
A short range lookup issues approximately one I/O to every run, amounting to O(T · L) I/Os with tiering and O(L) I/Os with leveling, as shown in Figure 3 (C). For a long range lookup, the size of the result set before eliminating obsolete entries is on average the product of its selectivity and space-amplification. We divide this product by the block size to get the I/O cost: O(T·s /B) with tiering and O(s /B) with leveling, as shown in Figure 3 (D).
A key distinction is that a short range lookup derives its cost approximately equally from across all levels, whereas a long range lookup derives most of its cost from access to the largest level.
Mapping the Design Space to the Trade-Off Space. There is an intrinsic trade-off between update cost on one hand and the costs of lookups and space-amplification on the other. We illustrate this trade-off in conceptual Figure 5, whereon the solid line plots the different costs of lookups and space-amplification on the y-axis against update cost on the x-axis for both leveling and tiering as we vary the size ratio, all based on the properties in Figures 3 and 4. When the size ratio is set to its limiting value of Tlim (meaning there is only one level in storage), a tiered LSM-tree degenerates into a log whereas a leveled LSM-tree degenerates into a sorted array. When the size ratio is set to its lower limit of 2, the performance characteristics for leveling and tiering converge as their behaviors become identical: the number of levels is the same and a merge operation is triggered at every level when the second run comes in. In general, as the size ratio increases with leveling/tiering, lookup cost and space-amplification decrease/increase and update cost increases/decreases. Thus, the trade-off space is partitioned: leveling has strictly better lookup costs and space-amplification and strictly worse update cost than tiering.
The Holy Grail. The solid line in Figure 5 reflects the properties of Monkey, the current state of the art. Figure 5 also shows a dotted line labeled the elusive optimal. The question guiding our research is whether other designs are possible with space-time trade-offs that more closely approach or even reach the elusive optimal.
The Opportunity: Removing Superfluous Merging. We have identified an asymmetry: point lookup cost, long range lookup cost, and space-amplification derive mostly from the largest level, while update cost derives equally from across all levels. This means that merge operations at smaller levels significantly amplify update cost while yielding a comparatively insignificant benefit for space-amplification, point lookups, and long range lookups. There is therefore an opportunity of a merge policy that merges less at smaller levels.
4 LAZY LEVELING, FLUID LSM-TREE, AND DOSTOEVSKY
We now present Lazy Leveling, Fluid LSM-Tree, and Dostoevsky to fluidly and dynamically adapt across an expanded LSM-tree design space with richer performance and space trade-offs.
4.1 Lazy Leveling
Lazy Leveling is a merge policy that eliminates merging at all but the largest level of LSM-tree. The motivation is that merging at these smaller levels significantly increases update cost while yielding a comparatively insignificant improvement for point lookups, long range lookups, and space-amplification. Relative to leveling, we show that Lazy Leveling (1) improves the cost complexity of updates, (2) maintains the same complexity for point lookups, long range lookups, and space-amplification, and (3) provides competitive performance for short range lookups. We summarize the structure and performance characteristics of Lazy Leveling in Figure 6, and we discuss this figure in detail in the rest of the section.
Basic Structure. The top part of Figure 6 illustrates the structure of Lazy Leveling and compares it to tiering and leveling. Lazy leveling at its core is a hybrid of leveling and tiering: it applies leveling at the largest level and tiering at all other levels. As a result, the number of runs at the largest level is 1 and the number of runs at all other levels is at most T − 1 (i.e., a merge operation takes place when the Tth run arrives).
Bloom Filters Allocation. Next, we show how to keep the cost of zero-result point lookups R low. The worst-case expected number of wasted I/Os per lookup is issued by a zero-result point lookup and is equal to the sum of false positive rates across every run’s Bloom filters. We model this cost for Lazy Leveling in Equation 3. The additive term pL corresponds to the FPR for the single run at Level L, and the other term sums up the products of FPRs and number of runs at Levels 1 to L − 1.
R = p_L + (T-1) * Σ(p_i) for i=1 to L-1; where 0 < p_i < 1
Next, we model the memory footprint Mi for the Bloom filters at Level i with respect to the number of entries Ni and the FPR pi at that level. We do this by rearranging Equation 2 in terms of bits and applying it to each level. Since the filters at any given level all have the same FPR, we can directly apply this equation regardless of the numbers of runs at a level. The result is Mi = -Ni · ln(pi) / (ln(2)^2).
Next, we express Ni more generally as the product of the capacity at the largest level N · (T-1)/T and a discounting factor to adjust for the capacity at Level i: 1/T^(L-i). We then sum up the memory footprint across all levels to get the overall memory footprint M. The result is Equation 4.
M = - (N / ln(2)^2) · ((T-1)/T) · Σ(ln(pi) / T^(L-i)) for i=1 to L
Zero-Result Point Lookups. Next, we analyze the cost of zero-result point lookups R with Lazy Leveling. We plug the optimal FPRs from Equation 5 into Equation 4, simplify into closed-form, and rearrange in terms of R. The complete derivation is in Appendix B. The result is Equation 6.
R = e^(-(M/N)·ln(2)^2) · (T^(T/(T-1))) / ((T-1)^((T-1)/T))
This equation allows to quickly find the optimal FPRs with respect to a given memory budget M by plugging in the corresponding value of R from Equation 6 into Equation 5.
To analyze the complexity of zero-result point lookups, we observe that the multiplicative term at the right-hand side of Equation 6 is a small constant for any value of T. Therefore, the cost complexity is O(e^(-M/N)), the same as with leveling despite having eliminated most merge operations.
Memory Requirement. As the number of entries N grows relative to the memory budget M, the FPRs increase and eventually converge to one (starting from larger to smaller levels because the FPR at larger levels is higher). We identify the ratio of bits per entry M/N at which point the FPR at Level L converges to one by plugging in one for pL in Equation 5, plugging the corresponding value of R into Equation 6, and rearranging in terms of M.
Threshold for M/N = (1 / ln(2)^2) · (ln(T)/(T-1) + ln(T-1)/T)
Equation 7 has global maximum of M/N = 1.62 bits per entry (which occurs when T is set to 3). For mainstream key-value stores used for server applications, the default ratio is an order of magnitude larger, typically 10 [29, 32, 48] or 16 [52], and so the FPRs are all lower than one. For systems with less than 1.62 bits per entry (e.g., mobile devices or sensors), we adapt Lazy Leveling and its analysis in Appendix C by merging more at larger levels.
Point Lookups for Existing Entries. The worst-case point lookup cost to an existing key occurs when the target key is at the oldest run at the largest level. The expected I/O cost is one I/O to this target run plus the sum of FPRs across all other runs. We use Equation 8 to model this, and we plug in the optimal FPRs from Equation 5. The result is V = 1 + R - pL.
Range Lookups. A short range lookup issues at most O(T) I/Os to each of the first L − 1 levels and one I/O to the largest level, and so the cost complexity is O(1 + (L − 1)· T) I/Os. Note that this expression initially increases as T increases, but as T approaches its limiting value of Tlim this term converges to 1 as the additive term (L − 1)· T on the right-hand size becomes zero (i.e., at this point Lazy Leveling degenerates into a sorted array).
A long range lookup is dominated by sequential access to Level L because it contains exponentially more entries than all other levels. The cost is O(s /B) I/Os, where s is the size of the target key range relative to the size of the existing key space. This is the same as with leveling despite having eliminated most merge operations.
Updates. An updated entry with Lazy Leveling participates in O(1) merge operations per level across Levels 1 to L−1 and in O(T) merge operations at Level L. The overall number of merge operations per entry is therefore O(L + T), and we divide it by the block size B to get the cost for a single update: O((L+T)/B). This is an improvement over the worst-case cost with leveling.
Space-Amplification. In the worst case, every entry at Levels 1 to L − 1 is an update to an existing entry at Level L. Since the fraction of entries at Levels 1 to L − 1 is 1/T of the overall number of entries, space-amplification is at most O(1/T). This is the same bound as with leveling despite having eliminated most merge operations.
Limits. Figure 7 compares the behaviors of the different merge policies as we vary the size ratio T for each policy from 2 to its limit of Tlim (i.e., at which point the number of levels drops to one). Firstly, we observe that these policies converge in terms of performance characteristics when the size ratio T is set to 2 because at this point their behaviors become identical: the number of levels is the same and a merge operation occurs at every level when the second run arrives. Secondly, Part (A) of Figure 7 shows that the improvement that Lazy Leveling achieves for update cost relative to leveling can be traded for point lookup cost by increasing the size ratio. This generates a new trade-off curve between update cost and point lookup cost that dominates leveling, and converges with it again as T approaches Tlim (i.e., at which point both merge policies degenerate into a sorted array). Parts (B) shows that the cost of small range lookups is competitive, and part (C) shows that this cost difference becomes negligible as the target range grows.
Lesson: No Single Merge Policy Rules. Our analysis in figure Figure 7 shows that no single design dominates the others universally. Lazy leveling is best for combined workloads consisting of updates, point lookups and long range lookups, whereas tiering and leveling are best for workloads comprising mostly updates or mostly lookups, respectively. In the rest of the paper, we take steps towards a unified system that adapts across these designs depending on the application scenario.
To be able to strike all possible trade-offs for different workloads, we next introduce Fluid LSM-tree, a generalization of LSM-tree that enables switching and combining merge policies. It does this by controlling the frequency of merge operations separately for the largest level and for all other levels.
Basic Structure. Figure 8 illustrates the basic structure of Fluid LSM-tree. There are at most Z runs at the largest level and at most K runs at each of the smaller levels. To maintain these bounds, every Level i has an active run into which we merge incoming runs from Level i − 1. Each active run has a size threshold with respect to the capacity of its level: TK percent for Levels 1 to L − 1 and TZ percent for Level L. When an active run reaches this threshold, we start a new active run at that level. Ultimately when a level is at capacity, all runs in it get merged and flushed down to the next level.
Parameterization. The bounds K and Z are used as tuning parameters that enable Fluid LSM-tree to assume the behaviors of different merge policies.
• K = T − 1 and Z = T − 1 give tiering.
• K = 1 and Z = 1 give leveling.
• K = T − 1 and Z = 1 give Lazy Leveling.
Fluid LSM-tree can transition from Lazy Leveling to tiering by merging less frequently at the largest level by increasing Z, or it can transition to leveling by merging more frequently at all other levels by decreasing K. Fluid LSM-tree spans all possible trade-offs along and between the curves in Figure 7.
Bloom Filters Allocation. Next, we derive the optimal FPRs that minimize the cost of zero-result point lookups R. The generalized optimal FPRs are given in Equation 9.
p_i = R/Z * (T-1)/T for i=L p_i = R/K * (T-1)/T * 1/T^(L-i) for 1 <= i < L
Equation 9 generalizes the optimal Bloom filters allocation strategy in Monkey [22] across a significantly wider design space, which now, in addition to tiering and leveling, also includes Lazy Leveling as well as custom merge policies with any parameter values for K and Z. Next, we model and map the new space-time trade-offs that this expanded design space offers.
Zero-Result Point Lookups. We model the cost of zero-result point lookups by plugging the generalized optimal FPRs in Equation 9 into Equation 4, simplifying into closed-form, and rearranging in terms of R. The derivation is in Appendix B, experimental validation is in Appendix I, and the result is Equation 10. The generalized complexity is O(Z · e^(-M/N)) I/Os.
R = e^(-(M/N)·ln(2)^2) · Z^((T-1)/T) · K^(1/T) · (T^(T/(T-1))) / ((T-1)^((T-1)/T))
Point Lookups for Existing Entries. The worst-case lookup cost to an existing key occurs when the target key is at the oldest run at the largest level. The expected I/O cost is one I/O to this target run plus the sum of FPRs across all other runs. We use Equation 8 to model this, and we plug in Equation 10 for R and Equation 9 for pL. The generalized complexity is O(1 + Z · e^(-M/N)).
Memory Requirement. In Appendix C, we derive the memory requirement M/N that guarantees that FPRs across all Levels are lower than one. The generalized result is 1.62 bits per entry as in the last subsection, which is well below the default ratio in mainstream systems. In Appendix C, we show how to adapt Fluid LSM-tree to extremely low-memory environments.
Range Lookups. A short range lookup issues at most K I/Os per relevant key range at each run issuing at least s sequential I/Os, where s is the number of unique entries in the target key range. To account for obsolete entries, the number of sequential I/Os is amplified by a factor of 1 + 1/T for updated entries at Levels 1 to L − 1 and Z for updated entries at Level L, which we model together as Z + 1/T. The sequential scan cost is therefore at most (s/B)·(Z + 1/T) I/Os with a complexity of O(s·Z /B) I/Os. The generalized range lookup cost is given in Equation 11 as the sum of costs for short and long range lookups weighted by the constant µ, the amount of which sequential access is faster than random access on a given storage devices (e.g., disk).
Q = K·(L-1) + Z + 1/µ · (s/B) · (Z + 1/T)
Updates. In the worst case, an entry participates in O(T/K) merge operations within an active run across each of Levels 1 to L − 1, and in O(T/Z) merge operations within the active run at Level L. The overall update cost is the sum of these terms across all levels divided by the block size: O( (T/K · (L-1) + T/Z) / B ). We model this cost more precisely using arithmetic series to obtain Equation 12, which we validate in Appendix I. We divide by the constant µ since the cost of updates is incurred through sequential merge operations, and we introduce an additional constant ϕ to account for the property of some storage devices that writes are more expensive than reads (e.g., flash).
W = (ϕ / (µ·B)) · ( (T-1)/(K+1) · (L-1) + (T-1)/(Z+1) )
Space-Amplification. Levels 1 to L − 1 contain a fraction of 1/T of the dataset, and so they may render up to this fraction of entries obsolete at the largest level. In Level L, at most Z − 1 of the runs may be completely filled with obsolete entries. We model space-amplification as the sum of these terms in Equation 13.
amp = Z - 1 + 1/T
Mapping the Design Space. Figure 9 is an instance of conceptual Figure 7 that uses our cost models to map the different trade-offs with Fluid LSM-tree. We generate Part (A) of Figure 9 by plotting point lookup cost R in Equation 10 against update cost W in Equation 12. We generate Parts (B) and (C) for short and long range lookups by plotting Q in Equation 11 against update cost W in Equation 12 for selectivities s of 10^-7 and 10^-10, respectively. We leave an evaluation of space-amplification for the experimental analysis. The configuration is fixed to a 1TB dataset with 128 byte entries, 4KB storage blocks, and overall 10 bits per entry across the filters. We generate the curves for leveling, tiering, and Lazy Leveling by using their corresponding fixed values for the parameters K and Z, and varying the size ratio T. The circle indicates the convergence point of all three merge policies where the size ratio T is set to two. The squares indicate a size ratio of ten, which most mainstream key-value stores use by default in practice [29, 32], to enable comparison of corresponding points across the three sub-figures. The figure also illustrates two transition curves labeled Trans1 and Trans2, which demonstrate how Fluid LSM-tree transitions fluidly across designs thereby achieving trade-offs that would not have been possible using a fixed merge policy.
Transition 1: Lazy Leveling to Tiering. We observe in Part (A) of Figure 9 that the curve for Lazy Leveling has an inflection point beyond which decreasing the size ratio degrades update cost. The reason is that update cost is O((L+T)/B), and as we decrease T the value of L grows and comes to dominate T. In this example, the inflection point occurs when the size ratio T is set to 5. We generate the curve labeled Transition 1 (Trans1) by fixing T to the inflection point value and instead varying Z from 1 to T − 1 (4 in this example). The resulting curve dominates both Lazy Leveling and tiering for this part of the design space until it converges with tiering. Thus, Transition 1 enables optimal trade-offs between point lookup cost and update cost as we transition between Lazy Leveling and tiering to optimize more for point lookups or updates, respectively.
Transition 2: Lazy Leveling to Leveling. In order to achieve more competitive range lookup costs with Lazy Leveling, we introduce Transition 2. The idea is to vary K, the bound on runs at Levels 1 to L − 1, between 1 and T − 1 to fluidly transition between Lazy Leveling and leveling. In Figure 9 we generate the curve labeled Trans2 by fixing K to 4 and varying T. Part (A) shows that this enables navigating a trade-off curve similar to Lazy Leveling, and parts (B) and (C) show that Trans2 achieves nearly the same range lookup cost as with leveling. Thus, Transition 2 enables fine control over how much we optimize for short range lookups.
4.3 Dostoevsky
We now introduce Dostoevsky to find and adapt to the best tuning of Fluid LSM-tree subject to a constraint on space-amplification. Dostoevsky models and optimizes throughput with respect to update cost W in Equation 12, zero-result point lookup cost R in Equation 10, non-zero result point lookup cost V in Equation 8, and range lookup cost Q in Equation 11. It monitors the proportion of these operations in the workload and weights their costs using coefficients w, r, v, and q, respectively. We multiply this weighted cost by the time to read a block from storage Ω and taking the inverse to obtain the weighted worst-case throughput τ.
τ = Ω^-1 / (w·W + r·R + v·V + q·Ω)
Dostoevsky maximizes Equation 14 by iterating over different values of the parameters T, K, and Z. It prunes the search space using two insights. The first is that LSM-tree has at most Lmax levels, each of which has a corresponding size ratio T, and so there are only ⌈log2(N/(P·B))⌉ meaningful values of T to test. The second insight is that the lookup costs R, Q and V increase monotonically with respect to K and Z, whereas update cost W decreases monotonically with respect to them. As a result, Equation 14 is convex with respect to both K and Z, and so we can divide and conquer their value spaces and converge to the optimum with logarithmic runtime complexity. Overall, auto-tuning takes O(log2(N/(P·B))) iterations as each parameter contributes one multiplicative log factor to runtime. To satisfy a given constraint on space-amplification, we ignore tunings for which Equation 13 is above the constraint. Since we iterate over a closed-form model, execution takes a fraction of a second, making it possible to find the optimal tuning at runtime without affecting overall system performance. We invoke auto-tuning between time windows consisting of X buffer flushes (16 in our implementation). A more detailed description of the adaptation workflow and the transition overheads is given in Appendix G.
We evaluate Dostoevsky across a range of workloads and show that it dominates existing designs in terms of performance and space-amplification.
Implementation. We implemented Dostoevsky on RocksDB [29], an LSM-tree based key-value store that is widely used in industry [8, 27]. RocksDB only supports leveling and assigns fixed FPR to Bloom filters across all levels. We optimized the Bloom filters allocation by embedding Equation 9 within the code. We then implemented Fluid LSM-tree using a RocksDB API that enables listening to internal events and scheduling merge operations using custom logic. We implemented auto-tuning by measuring the proportion of different operations in the workload and using the derived throughput model to find the optimal tuning. The number of combinations is O((N/(B·P))^3).
Baselines. We compare
